A Genetic Algorithm with Dynamic Population Size
This paper introduces a modified version of a simple genetic algorithm (SGA) in which the size of the population changes according to a model inspired from mathematical biology. The primary purpose of this research described is to use the growth of the po
- PDF / 772,209 Bytes
- 4 Pages / 595.28 x 793.7 pts Page_size
- 81 Downloads / 244 Views
Abstract This paper introduces a modified version of a simple genetic algorithm (SGA) in which the size of the population changes according to a model inspired from mathematical biology. The primary purpose of this research described is to use the growth of the population to vary the selective pressure through the scaling of the fitness function. The experimental results presented in the paper are used to demonstrate the behavior of the proposed algorithms in comparison with a SG A using fixed size population.
1
Introduction
It has been proven that in several applications (see for instance [Filipic 1992]) fitness scaling can significantly improve the performance of genetic algorithms (GA's). Those results were however mostly experimental, without any theoretical explanation and without well-founded suggestions on how fitness scaling has to be applied. In [Balazs 1995] it was shown how the selective pressure in a simple genetic algorithm (SGA) using proportional selection depends on the convexity of the fitness function. Based on those results it was suggested that during the genetic search the convexity of the fitness function has to be increased (from concave to convex). This would gradually increase the selective pressure from very low to very high. While this result is interesting and gives an explanation of why fitness scaling works for a particular class of GA's it still lacks any suggestion of how the change of the convexity of the fitness function (and through this of the selective pressure) can be controlled. The current paper proposes an approach to controlling the selective pressure by gradually changing the convexity of the fitness function in a SGA using proportional selection. The approach is based on an assumption inspired form a mathematical model of A. Dobnikar et al., Artificial Neural Nets and Genetic Algorithms © Springer-Verlag/Wien 1999
the dynamics of a population composed of a single species. According to this assumption, in an environment with limited resources (e.g. food) inhabited by a single species, the selective pressure during evolution increases with the increase of the size of the population. This mathematical model suggests a modified version of the SG A in which the size of the population varies with time. Other GA's with dynamic population sizes have been suggested earlier [Smith 1993], however in those approaches the variation of the population size was rather a goal than a means. The paper first presents the mathematical model used for varying the population size explaining why that specific a model was chosen. Then a modified SG A with dynamic population size is described. The performance of the presented algorithm is compared to that of a generic SGA using a set of examples. Finally it is suggested how the variation of the population size can be used to vary the convexity of the fitness function and by this the selective pressure during different stages of the genetic search. The paper concludes with suggesting further benefits from using a SGA with a dynamic population si
Data Loading...
