Entropy Profiles of Ranked and Random Populations
- ACM Inc.
- Publication Type:
- Conference Proceeding
- Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference (GECCO-2010), 2010, pp. 1843 - 1850
- Issue Date:
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: