Differences

This shows you the differences between two versions of the page.

--- wg3 [2018/01/15 16:38]
oliveto
+++ wg3 [2018/09/26 15:28] (current)
sudholt [PART A: Identifying the benchmark functions]
@@ Line 94: / Line 94: @@
 Kauffman's NK-landscapes for single-objective optimization and its extensions to multi- and many-objectives (MNK-landacapes and rhoMNK-landscapes) offer the possibility of testing on sub-classes of problems that require binary representation. Are a must for serious benchmarking.
+=== Suggestions by Dirk Sudholt ===
+There are a lot of well-studied problems with a property called **bit-flip symmetry**: flipping all bits gives a solution of the same fitness. This means that there are always at least two global optima. Such problems have been popular as search algorithms need to break the symmetry between good solutions [1].
+Well-known examples include the function **TwoMax** := \max\{\sum_{i=1}^n x_i, \sum_{i=1}^n (1-x_i)\} [1], which has been used as a challenging test bed in theoretical studies of diversity-preserving mechanisms [2-4].
+The function **H-Iff (Hierarchical If and only If)** [5] consists of hierarchical building blocks that need to attain equal values in order to contribute to the fitness. It was studied theoretically in [6,7] and is frequently used in empirical studies, see, e.\,g. [8,9].
+In terms of classical combinatorial problems, the **Graph Colouring** problem asks for an assignment of colours to vertices such that no two adjacent vertices share the same colour. For two colours, a natural setting is to use a binary encoding for the colours of all vertices and to maximise the number of bichromatic edges (edges with differently coloured end points). A closely related setting is that of simple **Ising models**, where the goal is to minimise the number of bichromatic edges. For bipartite (that is, 2-colourable) graphs, this is identical to maximising the number of bichromatic edges as inverting one set of the bipartition turns all monochromatic edges into bichromatic ones and vice versa. An advantage of the Ising model setting is that good quality solutions are easily recognisable: subgraphs with equal colours contribute well to the fitness. So I suggest to add the Ising model to the benchmark suite, but to keep in mind that it's essentially equivalent to the classical Graph Coloring problem.
+The following graph classes are of particular interest; all of them are scalable, subject to mild constraints (square numbers, n being one less than a power of 2):
+  - **Ring/cycle graphs** [10] can be optimised by the (1+1)EA in expected time O(n^3) and by a GA with crossover and fitness sharing in expected time O(n^2) [10]. The landscape contains plateaus that are easy to overcome.
+  - **Toroids** with side lengths sqrt(n)*sqrt(n) [11] are more difficult to optimise as they contain difficult local optima. Nevertheless, a Metropolis algorithm succeeds expected polynomial time [11].
+  - **Complete binary trees** [12] contain many local optima, some of which are extremely difficult to escape from (e.g. a root with differently coloured subtrees). While mutation-only EAs need exponential time in expectation, a (2+2)GA with fitness sharing succeeds in expected time O(n^3) [12].
+<sub>
+[1] Goldberg, D. E., Van Hoyweghen, C., and Naudts, B. (2002). From TwoMax
+to the Ising model: Easy and hard symmetrical problems. In Proceedings
+of the Genetic and Evolutionary Computation Conference (GECCO ’02),
+pages 626–633. Morgan Kaufmann.\\
+[2] Oliveto, P. S., Sudholt, D., and Zarges, C. (2018+). On the benefits and risks of using fitness sharing for multimodal optimisation. Theoretical Computer Science. To appear.\\
+[3] Covantes Osuna, E. and Sudholt, D. (2018+a). On the runtime analysis of
+the clearing diversity-preserving mechanism. Evolutionary Computation.
+To appear.\\
+[4] Covantes Osuna, E. and Sudholt, D. (2018b). Runtime analysis of probabilistic crowding and restricted tournament selection for bimodal optimisation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018), pages 929–936. ACM.\\
+[5] Watson, R. A., Hornby, G. S., and Pollack, J. B. (1998). Modeling building-block interdependency. In Parallel Problem Solving from Nature — PPSN V, pages 97–106. Springer Berlin Heidelberg.\\
+[6] Dietzfelbinger, M., Naudts, B., Hoyweghen, C. V., and Wegener, I. (2003). The analysis of a recombinative hill-climber on H-IFF. IEEE Transactions on Evolutionary Computation, 7(5):417–423.\\
+[7] Goldman, B. W. and Sudholt, D. (2016). Runtime analysis for the parameter-less population pyramid. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2016), pages 669–676. ACM.\\
+[8] Thierens, D. and Bosman, P. A. N. (2013). Hierarchical problem solving
+with the linkage tree genetic algorithm. In Proceedings of the 15th Annual
+Conference on Genetic and Evolutionary Computation (GECCO 2013),
+pages 877–884. ACM.\\
+[9] Goldman, B. W. and Punch, W. F. (2015). Fast and efficient black box
+optimization using the parameter-less population pyramid. Evolutionary
+Computation, 23(3):451–479.\\
+[10] Fischer, S. and Wegener, I. (2005). The one-dimensional Ising model:
+Mutation versus recombination. Theoretical Computer Science, 344(2–3):208–225. \\
+[11] Fischer, S. (2004). A polynomial upper bound for a mutation-based algorithm on the two-dimensional Ising model. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’04), pages 1100–1112.
+Springer.\\
+[12] Sudholt, D. (2005). Crossover is provably essential for the Ising model
+on trees. In Proceedings of the Genetic and Evolutionary Computation
+Conference (GECCO ’05), pages 1161–1167. ACM Press.
+</sub>
 ==== PART B: Evaluating Algorithm performance ====

ImAppNIO-Wiki

User Tools

Site Tools

Differences

Page Tools