Computational Technology Resources - CCP

Keywords: genetic algorithms, variable population, micro-GA.

Summary

Genetic Algorithms (GAs) are search algorithms based on the concepts of natural selection and survival of the fittest (Goldberg 1989) [1]. A number of methods have been developed, based on the standard GA scheme, to improve the robustness and computational efficiency of GAs (Smith and Fogarty, 1997) [2]. Moreover, an effort to categorize the developed methodologies devoted to the parameter control of evolutionary algorithms is presented by Eiben (Eiben et al. 1999) [3].

One of the main parameters that affect the robustness and computational efficiency of the GAs is the population size. In this work a Genetic Algorithm (GA) is proposed that uses a variable population size in the form of a saw-tooth function, having a specific amplitude and period of variation . The aim is to enhance the overall behaviour of the algorithm relying on the dynamics of the evolution of the GA in a way that magnifies its efficiency. The convergence behaviour of the linearly decaying population size is similar to a constant population size GA but requires less computing effort. At the end of each period of the saw-tooth scheme, the solutions that are retained comprise a small population that has almost converged. At the beginning of the next period randomly selected individuals are introduced into the population. This random re-initialization of the process at specific periods resembles the features of the Micro GA [4]. Therefore, comparison is based on both the Standard GA and Micro GA which have the same computing cost.

The performance of the three different algorithms is evaluated on the basis of the statistics of their maximum and average fitness histories over the generations for a number of GA runs based on different random seeds. The mean curves of these fitness histories for the different GA runs are plotted to reveal the convergence behaviour and performance features of the examined algorithms.

The proposed scheme is applied into two categories of problems that are often used as benchmark tests. These correspond to two n-dimensional multimodal peak functions with different features. Numerical results are presented for a wide range of parameters. The main finding is that for large amplitudes and a broad range of values for the period of variation of the population size, the overall performance of the proposed scheme reaches the performance of a Standard GA of substantial bigger population size. This trend is justified also on the basis of schema theorem [5,6].

The previous theoretical and statistical analysis can be used to form guidelines towards the selection of optimum and parameters of the Saw-tooth GA. The general conclusion that was deduced is that the optimum performance is achieved for big amplitudes combined with medium periods . The amplitude should be as big as possible, preferably where is the mean population size of the Saw-tooth GA. Smaller values of may be appropriate for multi-modal problems with sub-regions of equal importance. The period should be neither very small, nor very big. Thus, the best approach to select the optimum range of periods is by following the evolution rate of the average fitness history of the Saw-Tooth GA. For bigger periods the performance of the Saw-tooth GA is delayed although it is not affected considerably. For the examined problems the performance of the saw-tooth GA was superior as compared to that of the corresponding Micro GA and Standard GA of equal computing cost.

References

1: Goldberg D.E., "Genetic Algorithms in Search, Optimization and Machine Learning", Addison-Wesley, 1989.
2: Smith J.E., Fogarty T.C. (1997) "Operator and parameter adaptation in genetic algorithms", Soft Computing, Springer-Verlag, 1, 81-87. doi:10.1007/s005000050009
3: Eiben E. A., Hinterding R., Michalewicz Z. (1999) "Parameter Control in Evolutionary Algorithms", IEEE-CE, 3(2), 124-143. doi:10.1109/4235.771166
4: Carroll D.L., "Fortran Genetic Algorithm" (http://www.cuaerospace.com/carroll/ga.html)
5: Holland J.H. (1975) "Adaptation in Natural and Artificial Systems", Ann Arbor: The University of Michigan Press.
6: Goldberg D.E. and Kumara S., "A Practical Schema Theorem for Genetic Algorithm Design and Tuning", GECCO 2001 Proceedings, pp. 328-335

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)

	Computational & Technology Resources an online resource for computational, engineering & technology publications
	not logged in - login
Front Page Browse CCP CSETS CTR IJRT Other Authors Search Purchase Guide FAQ Contact us	Civil-Comp Proceedings ISSN 1759-3433 CCP: 76 PROCEEDINGS OF THE THIRD INTERNATIONAL CONFERENCE ON ENGINEERING COMPUTATIONAL TECHNOLOGY Edited by: B.H.V. Topping and Z. Bittnar Paper 74 The Effect of Oscillating Population Size and Re-initialization on the Performance of Genetic Algorithms V.K. Koumousis and C.P. Katsaras Institute of Structural Analysis & Aseismic Research, Department of Civil Engineering, National Technical University of Athens, Greece doi:10.4203/ccp.76.74 purchase the full-text of this paper Full Bibliographic Reference for this paper V.K. Koumousis, C.P. Katsaras, "The Effect of Oscillating Population Size and Re-initialization on the Performance of Genetic Algorithms", in B.H.V. Topping, Z. Bittnar, (Editors), "Proceedings of the Third International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 74, 2002. doi:10.4203/ccp.76.74 Keywords: genetic algorithms, variable population, micro-GA. Summary Genetic Algorithms (GAs) are search algorithms based on the concepts of natural selection and survival of the fittest (Goldberg 1989) [1]. A number of methods have been developed, based on the standard GA scheme, to improve the robustness and computational efficiency of GAs (Smith and Fogarty, 1997) [2]. Moreover, an effort to categorize the developed methodologies devoted to the parameter control of evolutionary algorithms is presented by Eiben (Eiben et al. 1999) [3]. One of the main parameters that affect the robustness and computational efficiency of the GAs is the population size. In this work a Genetic Algorithm (GA) is proposed that uses a variable population size in the form of a saw-tooth function, having a specific amplitude and period of variation . The aim is to enhance the overall behaviour of the algorithm relying on the dynamics of the evolution of the GA in a way that magnifies its efficiency. The convergence behaviour of the linearly decaying population size is similar to a constant population size GA but requires less computing effort. At the end of each period of the saw-tooth scheme, the solutions that are retained comprise a small population that has almost converged. At the beginning of the next period randomly selected individuals are introduced into the population. This random re-initialization of the process at specific periods resembles the features of the Micro GA [4]. Therefore, comparison is based on both the Standard GA and Micro GA which have the same computing cost. The performance of the three different algorithms is evaluated on the basis of the statistics of their maximum and average fitness histories over the generations for a number of GA runs based on different random seeds. The mean curves of these fitness histories for the different GA runs are plotted to reveal the convergence behaviour and performance features of the examined algorithms. The proposed scheme is applied into two categories of problems that are often used as benchmark tests. These correspond to two n-dimensional multimodal peak functions with different features. Numerical results are presented for a wide range of parameters. The main finding is that for large amplitudes and a broad range of values for the period of variation of the population size, the overall performance of the proposed scheme reaches the performance of a Standard GA of substantial bigger population size. This trend is justified also on the basis of schema theorem [5,6]. The previous theoretical and statistical analysis can be used to form guidelines towards the selection of optimum and parameters of the Saw-tooth GA. The general conclusion that was deduced is that the optimum performance is achieved for big amplitudes combined with medium periods . The amplitude should be as big as possible, preferably where is the mean population size of the Saw-tooth GA. Smaller values of may be appropriate for multi-modal problems with sub-regions of equal importance. The period should be neither very small, nor very big. Thus, the best approach to select the optimum range of periods is by following the evolution rate of the average fitness history of the Saw-Tooth GA. For bigger periods the performance of the Saw-tooth GA is delayed although it is not affected considerably. For the examined problems the performance of the saw-tooth GA was superior as compared to that of the corresponding Micro GA and Standard GA of equal computing cost. References 1 Goldberg D.E., "Genetic Algorithms in Search, Optimization and Machine Learning", Addison-Wesley, 1989. 2 Smith J.E., Fogarty T.C. (1997) "Operator and parameter adaptation in genetic algorithms", Soft Computing, Springer-Verlag, 1, 81-87. doi:10.1007/s005000050009 3 Eiben E. A., Hinterding R., Michalewicz Z. (1999) "Parameter Control in Evolutionary Algorithms", IEEE-CE, 3(2), 124-143. doi:10.1109/4235.771166 4 Carroll D.L., "Fortran Genetic Algorithm" (http://www.cuaerospace.com/carroll/ga.html) 5 Holland J.H. (1975) "Adaptation in Natural and Artificial Systems", Ann Arbor: The University of Michigan Press. 6 Goldberg D.E. and Kumara S., "A Practical Schema Theorem for Genetic Algorithm Design and Tuning", GECCO 2001 Proceedings, pp. 328-335 purchase the full-text of this paper (price £20) go to the previous paper go to the next paper return to the table of contents return to the book description purchase this book (price £85 +P&P)
Back to top	©Civil-Comp Limited 2023 - terms & conditions