Evolvability in Optimization Problems: the Role of Representations and Heuristics

Authors

Abstract

One of the fundamental issues in the development of evolutionary algorithms is the representation of a candidate solution. The success of this type of approaches relies on choosing a genetic representation that allows the algorithm to be efficient and accurate. To address this goal we have to answer a set of questions: What is the most suitable representation for a problem? Which representation gives more guarantees of discovery solutions with better quality or even optimal? It is possible to arrive quickly to a solution?

Being perceivable that the representation plays a fundamental part in the development of an evolutionary algorithm, additionally it is important to understand its role and the interplay with heuristics and local methods. Does a particular representation need auxiliary mechanisms, e.g., heuristics, in order to achieve and/or accuracy? Which of these complementary procedures are influential? In which way the representation is really important? Within combinatorial optimization problems, this fact becomes even more relevant since they possess a strong practical application in many diverse fields.

Our interest relies on the development of evolutionary algorithms for combinatorial optimization problems. It is fundamental to perceive the influence of a given representation. Therefore, we want to better perceive the respective influence through the application of fitness landscape analysis techniques to combinatorial optimization problems. This work studies the influence of genetic representations for combinatorial optimization problems. The Multidimensional Knapsack Problem (MKP) and the Optimal Golomb Ruler (OGR) problem are used as test cases. We analyze in detail the issues related to genetic representations usually applied and developed for these problems.

Analyzing the behavior showed by the MKP and the OGR problems, we identify some common aspects: the importance of decoder-based representations and the need of auxiliary methods for binary encoding. The use of representations with decoders can help in designing a more standard architecture for an evolutionary algorithm. The base encoding is simple enough to ensure the use of classical operators and other standard options when constructing an evolutionary algorithm.

Therefore, results show that for combinatorial optimization problems decoder-base representations are preferable to other encodings. The decoding mechanisms can be simple. If designed with problem knowledge, it can transform the representation into a very efficient one. The use of additional methods, like heuristics and local improvement methods should be carefully studied. In general, adding a heuristic or a local search mechanism to an evolutionary algorithm helps to improves its efficiency and performance. Sometimes the role of these auxiliary methods might prove to be crucial to the search process. Despite this fact, there is not a single answer although these auxiliary procedures can be valuable, particularly on simple direct encodings.

Subject

Evolutionary Optimization

PhD Thesis

Evolvability in Optimization Problems: the Role of Representations and Heuristics, July 2007