The quest for optimal sensing matrices is crucial in the design of efficient Compressed Sensing architectures. In this paper we propose a maximum entropy criterion for the design of optimal Hadamard sensing matrices (and similar deterministic ensembles) when the signal being acquired is sparse and non-white. Since the resulting design strategy entails a combinatorial step, we devise a fast evolutionary algorithm to find sensing matrices that yield high-entropy measurements. Experimental results exploiting this strategy show quality gains when performing the recovery of optimally sensed small images and electrocardiographic signals. © 2014 IEEE.