European Symposium on Intelligent Techniques, ESIT2000
Aachen(Germany), Sept. 2000

ABSTRACT: Life and evolution in nature are organized at least into four fundamental levels of structure: the molecular level, the cellular level, the organism level and the population level. At present the tendency is to study the molecular level through wet-bench lab techniques (wetware), the cellular and population levels with software simulations and the organism level with hardware (robotic) experiments. What we propose is a study at population level of artificial evolution through an evolutionary algorithm. The aim underlying the proposed work is not to recreate nature as it is, but to move from classical genetic algorithms towards artificial evolution of populations composed by individuals able to interact among them without external parameter settings. We know that in natural environments population sizes of species, together with their reproduction and competition rates, change and tend to stabilise around appropriate values according to some factors such as the natural resources and carrying capacity of the ecosystem. Unfortunately in standard genetic algorithms these features, population size, crossover and mutation probabilities, are stuck, from generation to generation, on a priori defined values. It means that running such an algorithm entails setting the values of such parameters. Finding settings that work well on one problem is not a trivial task; if poor settings are used, a genetic algorithm performance can be severely impacted. It is clear that in this situation we actually have to deal with two optimization problems : the problem itself and the setting of the GA parameters. To solve this drawback in the last years some researchers proposed several solutions. Within this framework the proposed paper deals with a new solution for dynamically setting the parameters of genetic algorithms during the course of a run. The main feature of our methodology is variable population size based on free interaction among individuals. To implement such a feature we reconsidered some basic concepts. First we reviewed the traditional concept of selection in GAs versus that of direct competition among individuals. Second the two classical genetic operators, crossover and mutation, are viewed not so strictly genetic but, in a little more evolutionary way, like two different ways of reproducing. In this context the metaphor for crossover, mutation and chromosome move towards bisexual reproduction, mono-sexual reproduction and individual. On the base of population size we define reproduction and competition rates. Obviously since population size is variable then such rates are variable too. The underlying idea to define reproduction probabilities is based on the environmental availability of finite natural resources. Roughly speaking we say that the higher the population size is and the less the resources are. It means that, because of the lack of resources, as the population size increases the competition rate gets higher and the reproduction probabilities decrease. To test these ideas we used as testbed common instances of the travelling salesman problem (TSP). We wish to underline that the aim of our work is not a study of such a problem, we used this benchmark only to provide individuals with a fitness criterion and to show the effectiveness of the proposed adaptive parametrization to solve optimization problems. In the paper a detailed description, a discussion of the strategy and the results on TSP are reported. Such results show that the proposed evolutionary algorithm finds by itself the values of the parameters by reaching an equilibrium point and that performances on the considered problem are very good.

KEYWORDS: genetic and evolutionary algorithms, dynamic variation of population size, adaptive parameterisation, artificial evolution

Click here to download the full paper (~71Kb)