Entropy profiles of ranked and random populations

Publication Type:
Conference Proceeding
Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference, GECCO '10 - Companion Publication, 2010, pp. 1843 - 1849
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2010001553OK.pdf1.6 MB
Adobe PDF
The paper describes the concept of entropy profile, how it is derived, its relationship to the number partition problem and to the information extracted from an objective function. It is hoped that discussion and criticism of this idea may shed light on why some problem representations are NP hard and other, very similar problems are relatively simple. Entropy profiles illustrate the difference between ranked and randomly ordered populations of individuals in a GA in a way which quantifies the information extracted from the objective function by the ranking process. The entropy profiles of random populations are shown to arise from the fact that there are many more of such 'paths' through the entropy coordinate space than periodic or ranked paths. Additionally, entropy profile provides a measurable difference between periodic low-frequency sequences, periodic high-frequency sequences, random sequences and those which are in some way structured, ie by an objective function or other signal. The entropy coordinate space provides a visualisation and explanation of why these profiles differ and perhaps, by way of the integer partition phase transition, also a means to understand why some problems are hard while other seemingly similar problems are straightforward to solve. © 2010 ACM.
Please use this identifier to cite or link to this item: