Entropy Profiles of Ranked and Random Populations

Publisher:
ACM Inc.
Publication Type:
Conference Proceeding
Citation:
Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference (GECCO-2010), 2010, pp. 1843 - 1850
Issue Date:
2010-01
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.
Please use this identifier to cite or link to this item: