Design

Complex systems have some common features: elementary bricks and/or functional entities interacting locally and globally. The nature and intensity of the coupling between bricks and functional entities have an influence on the whole structure and behavior of the system. In certain cases it is important to have antagonist elements to preserve the dynamics of the system by inducing formation of compartments or islands.

Interactions inside a system and with its environment concern different interacting levels with emergence from lower levels to higher levels and, in some cases immergence from higher levels to lower levels. The number of levels can be greater than two. It is important to design efficient interfaces between constitutive bricks, islands and between the system and its environment.

Design of Evolutionary Algorithms

Evolutionary mechanisms are complex systems, as evolution can be seen at different organisation levels. At the molecular level, Jean-Marie Lehn (Nobel Prize in chemistry 1987) introduced reconfigurable supra-molecular structures with helix shapes that are close to the DNA. In his book "The selfish gene," Richard Dawkins takes the theory of George Williams by placing the gene in the centre of the evolution, an individual being made up of a collection of genes, allowing them to reproduce more efficiently than if they were isolated.

At a higher level, one can consider the individuals as entities of the complex system: interaction takes place during reproduction, that allows to create a child who is a recombination of the genotype of several parents chosen by a selection mechanism. At an even higher level, it is possible to get several populations to evolve in different ecological niches (like birds on different islands), which led Darwin to develop the concept of evolution. Things can be made yet more complex, by introducing the concept of multi-modality, where several species in co-evolution interact in a predator-prey model. Beyond, many competing species sharing the same environment will lead to an ecosystem.

The concept is very rich, with emergent properties at all levels, allowing very diverse species to evolve that are very well adapted to their environment, from viruses and cyanobacteria, multi-cellular organisms and finally, man.

Because remarkable emergent properties have been observed in natural evolution, researchers have implemented artificial evolution mechanisms on computers as soon as those were available by trying to evolve solutions to simple problems as early as in 1953. In 1957 [2], Fraser evolves bit strings by using a crossover mechanism. In 1958 [3], Friedberg describes how computers cold program themselves through mutations. In 1959 [4], Friedman evokes in silico evolution.

One can therefore see that rather than being a novel optimisation technique, artificial evolution is among the very first complex algorithms to be implemented on computers. Ever since, things have well improved, and thanks to their emergence properties, evolutionary algorithms play a major role in stochastic optimization, in order to find solutions to generic problems, that are too vast to be tackled by deterministic methods. They are extensively used to optimize large industrial problems (optimising where cranes should be positioned on large building sites, how to restart railroad service after an incident, optimization of water distribution, of concrete mixture composition, of frequency allocations, …) in applied research (evolutionary robotics, determination of crystalline structures in chemistry, of the shape of satellite antennas, of analog and digital circuits, …) but also in fundamental research (travelling salesman problem, constraint problem solving, understanding fitness landscapes, emerging behaviour, …).

Artificial evolution regularly produces human competitive results (cf. results obtained through Genetic Programming, presented in Koza IV, Humies Awards of the Gecco Conference, …).

Study of evolutionary algorithms as reflexive adaptive systems

Evolutionary algorithms have not yet been studied with the mathematical tools of adaptive complex systems. They can feature self-observation properties to quantify their performance, based on the shape of the search space (irregularity, dimension), on the number of individuals involved in the search, the number of implemented levels of abstraction implemented (island based parallelism or not, number of islands), of the complexity of the genome of the individual (number of genes, gene type), selection pressure, genetic operators (crossover, mutation). Self-assessment of their performance will allow them to self-optimize their numeric value parameters and maybe even to self-configure the organization levels of the evolutionary algorithm. Self-configuration and self-optimisation are essential properties for a self-adaptation to perturbation of the internal and external environment. This may lead to self-programming for an even stronger reflexivity leading to an ecosystem of autonomic computing.

This work would allow to make progress not only the theory of adaptive stochastic optimization by artificial evolution, but also on the knowledge of the mechanisms of natural evolution on which it draws.

Study of other adaptive computational paradigms inspired from nature

Evolutionary algorithms are not the only adaptive computational paradigms that can be used to find results to complex problems. Ant colonies also are complex systems that have been a source of inspiration to the development of Ant Colony Optimization [6]. Animal behaviour has also been used for the same objective with Particle Swarm Optimization [7]. The same goes with the natural immune system on which inspired artificial immune systems, to analyse input streams and detect computer virus attacks in order to protect important systems of distributed computers.

Because they get their inspiration from Nature, these algorithms are good candidates to run on hierarchical massively parallel machines, which have the ideal architecture to run multi-level complex systems (only basic entities interact locally and asynchronously, which allows to not lose time in synchronization and inter-processor communication, that usually make massively parallel machines unusable on traditional algorithms). Theoretical study of these algorithms inspired by Nature would here also lead to a better understanding not only of their mode of operation, but also of the natural patterns on which they draw.