wg3
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
wg3 [2018/09/26 16:24] sudholt [PART A: Identifying the benchmark functions] |
wg3 [2018/09/26 16:28] (current) sudholt [PART A: Identifying the benchmark functions] |
||
|---|---|---|---|
| Line 101: | Line 101: | ||
| 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]. | 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. | + | 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): | |
| - | The following graph Ising model classes are of particular interest. All graphs 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. | - **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]. | - **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]. | ||
wg3.1537975457.txt.gz · Last modified: 2018/09/26 16:24 by sudholt
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
