The relationship between a network's degree-degree correlation and a loose version of graph coloring is studied on networks with broad degree distributions. We find that, given similar conditions on the number of nodes, number of links, and clustering levels, fewer colors are needed to color disassortative than assortative networks. Since fewer colors create fewer independent sets, our finding implies that disassortative networks may have higher concurrency potential than assortative networks. This in turn suggests another reason for the disassortative mixing pattern observed in biological networks such as those of protein-protein interaction and gene regulation. In addition to the functional specificity and stability suggested by Maslov and Sneppen, a disassortative network topology may also enhance the ability of cells to perform crucial tasks concurrently. Hence, increased concurrency may also be a driving force in the evolution of biological networks.

The performances (success) of a hill climber (RMHC) and a genetic algorithm (upGA) on a set of test problems with varied structural characteristics are compared to learn whether problem structural characteristic can be a feasible solution-independent indicator of when a problem will be more easily solved by a genetic algorithm than by hill climbing. Evidence supporting this hypothesis is found in this initial study. In particular, other factors (modularity, transitivity and fitness distribution) being equal, highly modular problems with broad right-skewed degree distributions are more easily solved by upGA than by RMHC. Suggestions are made for further research in this direction.

The relevance of degree distribution to evolutionary search is supported by experiments. Hubs and their locality sit at the schwerpunkt of the explanation for this find. A full version of this paper including the method to generate hierarchically modular networks with link switching is available on-line at arXiv: 0903.2516.

A variant of the HIFF problem called HIFF-M is compared with HIFF-D - the discrete version of the original HIFF problem. By the SWO statistic, HIFF-M is less epistatic than HIFF-D. Using operator specific FDC measurements, we find that HIFF-M is less crossover-easy and less mutation-hard than HIFF-D. Nevertheless, from our experiments, HIFF-M is still difficult for an unspecialized hill climber and for a mutation-only multi-individual stochastic search algorithm to solve efficiently and reliably. HIFF-M also has a more symmetrical fitness distribution than HIFF-D thus increasing the possibility of useful neutral spaces at higher levels of fitness. Notably, explicit mechanisms to reduce diversity loss made it more difficult for crossover-only GAs to solve HIFF-M than HIFF-D. Over all configurations that we experimented with, the best search performance for HIFF-M was obtained with upGA - a single-population, steady-state GA which uses random parent selection, 1-2 point crossover and no explicit diversity preservation mechanism. This result suggests that HIFF-M has the kind of epistasis to create fitness landscapes where genetic drift, crossover and mutation work well together to balance the exploitative and explorative facets of a GA.

We show how a random mutation hill climber that does multi-level selection utilizes transposition to escape local optima on the discrete Hierarchical-If-And-Only-If (HIFF) problem. Although transposition is often deleterious to an individual, we outline two population models where recently transposed individuals can survive. In these models, transposed individuals survive selection through cooperation with other individuals. In the multi-population model, individuals were allowed a maturation stage to realize their potential fitness. In the genetic algorithm model, transposition helped maintain genetic diversity even within small populations. However, the results for transposition on the discrete Hierarchical-Exclusive-Or (HXOR) problem were less positive. Unlike HIFF, HXOR does not benefit from random drift. This led us to hypothesize that two conditions necessary for transposition to enhance evolvability are (i) the presence of local optima and (ii) susceptibility to random drift. This hypothesis is supported by further experiments. The findings of this paper suggest that epistasis and large mutations can sustain artificial evolution in the long-term by providing a way for individuals and populations to escape evolutionary dead ends. Paradoxically, epistasis creates local optima and holds a key to its resolution, while deleterious mutations such as transposition enhance evolvability. However, not all large mutations are equal.

A new test problem called HIFF-II is presented. We propose that HIFF-II discriminates evolutionary algorithms that use recombination from those that do not. HIFF-II is a variant of the hierarchical-if-and-only-if (HIFF) problem proposed by Watson (2006). HIFF-II differs from HIFF in one significant way. The dependency matrix for HIFF-II is sparser than that for HIFF. Two important consequences from this are HIFF-II has inter-level interdependencies and there are distinct sets of optimal solutions of the same cardinality at every level. We tested the performance of a random mutation hill climbing algorithm and a genetic algorithm on HIFF-II. This experiment was conducted under "ideal" circumstances for each algorithm on the HIFF-II problem. For the random mutation hill climbing algorithm, this involved using an altruistic selection scheme to induce progress at all levels simultaneously and using a reasonably low mutation rate. For the genetic algorithm, this meant using the gene-invariant genetic algorithm (GIGA) which preserves population diversity throughout a run and selecting pairs of parents that are close in aggregate fitness value. This experiment confirmed that random mutation hill climbers experienced more difficulty evolving an optimal solution for HIFF-II than a genetic algorithm. The disparity between the performances of the two algorithms became more apparent as the problem size increases

We consider how accretive evolution is able to evolve optimal solutions to hierarchical decomposable non-separable problems epitomized by hierarchically consistent test problems. We find that this feat is not as improbable as previously thought if a suitable phenotype which reflects the levels in the hierarchy is used as the object of a selection scheme which applies level directed selection pressure. An ideal selection scheme is first described and tested experimentally, followed by a meta-population model to evolve the ideal selection scheme. Experiments with the model revealed that evolution of the ideal selection scheme is not a pre-requisite to evolving optimal solutions. Optimal solutions were found even when the ideal selection scheme was not. No recombination of partial solutions is used in this paper. The findings of this paper reopen the question: what type of hierarchical structure is difficult to evolve through random mutation and selection