Stochastic Populations, Power Law and Fitness Aggregation in Genetic Algorithms

• Autorzy: Ma Z. S.
• Języki publikacji: EN

Abstrakty

EN

Natural populations are dynamic in both time and space. In biological populations such as insects, spatial distribution patterns are often studied as the first step to characterize population dynamics. In nature, the spatial distribution patterns of insect populations are considered as the emergent expression (property) of individual behaviors at population levels and are fine-tuned or optimized by natural selection. This inspiration prompts us to investigate the possibly similar mechanisms in Genetic Algorithms (GA) populations. In this study, we introduce the mathematical models for the spatial distribution patterns of insect populations to GA with the conjecture that the emulation of biological populations in nature may lead to computational improvement. In particular, we introduce three modeling approaches from the research of spatial distribution patterns of insect populations: (i) probability distribution modeling approach, (ii) aggregation index approach, and (iii) Taylor’s (1961, 1977) Power Law, Iwao’s (1968, 1976) Mean Crowding Model and Ma’s (1991c) population aggregation critical density (PACD), to characterize populations in GA. With these three approaches, we investigate four mappings from the research field of insect spatial distribution patterns to GA populations in order to search for possible counterpart mechanisms or features in GA. They are: (i) mapping insect spatial distribution patterns to GA populations or allowing GA populations to be controlled by stochastic distribution models that describe insect spatial distributions; (ii) mapping insect population distribution to GA population fitness distribution via Power Law and PACD modeling; (iii)mapping population aggregation dynamics to GA fitness progression across generations (or fitness aggregation dynamics in GA) via insect population aggregation index; (iv) mapping insect population sampling model to optimal GA population sizing. With regard to the mapping (i), the experiment results show the significant improvements in GA computational efficiency in terms of the reduced fitness evaluations and associated costs. This prompts us to suggest using probability distribution models, or what we call stochastic GA populations, to replace the fixed-size population settings. We also found the counterpart for the second mapping, the wide applicability of Power Law and Mean Crowding model to the fitness distribution in GA populations. The testing of the third and fourth mappings is very preliminary; we use example cases to suggest two further research problems: the potential to use fitness aggregation dynamics for controlling the number of generations iterated in GA searches, and the possibility to use fitness aggregation distribution parameters [(obtained in mapping (ii)] in determining the optimum population size in GA. A third interesting research problem is to investigate the relationship between mapping (i) and (iii), i.e., the controlling of both population sizes and population generations.

Słowa kluczowe

EN

genetic algorithm (GA); GA; spatial distribution pattern; power law; dynamic population; fitness distribution; fitness aggregation; fitness aggregation dynamics; insect population dynamics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 122, nr 3
• Strony: 173--206
• Opis fizyczny: Bibliogr. 42 poz., tab., wykr.

Twórcy

autor

Ma Z. S.

• Computational Biology and Medical Ecology Lab State Key Laboratory of Genetic Resources and Evolution, Kunming Institute of Zoology Chinese Academy of Sciences, China
• Computer Science Department, University of Idaho, Moscow, ID 83844, USA

Bibliografia

• [1] Alander, J.: On optimal population size of genetic algorithms. IEEE Proceedings of CompEuro ’92. “Computer Systems and Software Engineering”. 4–8 May 1992:65–70.
• [2] Arabas, J., Z. Michalewicz, and J. Mulawka.: GAVaPS -a Genetic Algorithm with Varying Population Size. Proceedings of the First IEEE Conference on Evolutionary Computation. v(1)1994:73–78.
• [3] Cantrell, R. S. and C. Cosner.: Spatial Ecology via Reaction-Diffusion Equations. Wiley-Intersciences. 2003
• [4] Costa, J.C., Tavares, R., Rosa, A.: An experimental study on dynamic random variation of population size. Proceedings of 1999 IEEE International Conference on Systems, Man, and Cybernetics, 1999. Vol. 1, 12-15 Oct. 1999:607–612.
• [5] De Jong, K. A.: An analysis of the behaviors of genetic adaptive systems. Ph.D. Thesis, University of Michigan, Ann Arbor, MI. 1975.
• [6] Eiben, A. E., and Smith, J. E.: Introduction to Evolutionary Computing. Springer. 2003.
• [7] Felsenstein, J.: Theoretic Evolutionary Genetics. University of Washington, Seattle, WA. USA. 2007.
• [8] Gates, G. H., Merkle, L. D., Lamont, G. B.: Simple Genetic Algorithm Parameter Selection for Protein Structure Prediction. IEEE International Conference on Evolutionary Computation, 29 Nov.-1 Dec. 1995 vol.2 P:620–624.
• [9] Givens, G. H. and J. A.: Hoeting. Computational Statistics. Wiley. 2005.
• [10] Goldberg, D. E.: Sizing populations for serial and parallel genetic algorithms. in “Proceedings of the Third International Conference on Genetic Algorithms”, ed. by David Schaffer. Morgan Kaufman Publishers. 1989:70–79.
• [11] Goldberg, D. E., M. Rundnick.: Genetic algorithms and variance of fitness. Complex Systems.1991, 5(3):265–278. rrrr
• [12] Goldberg, D. E. et al.: Genetic algorithms, Noise, and the Sizing of Populations. Complex Systems. 1992(6):333–362.
• [13] Given, G. H. and J. A. Hoeting. Computational Statistics. Wiley Inter Science. 2005:418pp.
• [14] Harik, G., E. Cantu-Paz, D. E.: Goldberg, and B. L. Miller. The Gambler’s ruin problem, genetic algorithms, and the sizing of populations. Evol. Comput. 1999, 7(3):231–253.
• [15] Hutchinson, G. E. The Ecological Theater and the Evolutionary Play. Yale University Press. 1966.
• [16] Iwao, S.: A new regression method for analyzing the aggregation pattern of animal populations. Res. Popul. Ecol. 1968(10):1–20.
• [17] Iwao, S.: A note on the related concepts ‘mean crowding’ and ‘mean concentration’. Res. Popul. Ecol. 1976 (17):240–242.
• [18] Khor, E. F., Tan, K. C., Wang, M. L., Lee, T. H.: Evolutionary algorithm with dynamic population size for multi-objective optimization. 26th Annual Conference of the IEEE Industrial Electronics Society, IECON 2000. 22–28 Oct. 2000, V(4): 2768 –2773.
• [19] Kuno, E.: Sampling and analysis of insect population. Annu. Rev. Entomol. 1991,36:285–304.
• [20] Lu, H, and Yen, G. G.: Dynamic population size in multi-objective evolutionary algorithms. Proceedings of the 2002 Congress on Evolutionary Computation, 12–17 May 2002, Vol. 2: 1648–1653.
• [21] Lu, H., and Yen, G. G.: Rank-Density-Based Multi-objective Genetic Algorithm and Benchmark Test Function Study. IEEE Trans. Evol. Comp. 2003,Vol. 7(4):325–343.
• [22] Ma, Z. S.: Revised Taylor’s Power Law and Population Aggregation Critical Density. Proceedings of Annual National Conference of the Ecological Society of China. 1988, Nanjing, China. (In Chinese with English Abstract)
• [23] Ma, Z. S.: Estimating the dispersion indices of animal populations with Jackknifing method. J. of Biomath. 1989,4(2):125–131. (In Chinese with English Abstract)
• [24] Ma, Z. S.: Application of grey clustering analysis to natural habitat unit of insect populations. J. Grey System. 1990a:179–187.
• [25] Ma, Z. S.: Sampling insect populations: a literature review. Scientia Silvae Sinicae. 1990b, 26(3):254–161. (In Chinese with English Abstract)
• [26] Ma, Z. S.: Weibull distribution: as a spatial distribution model of insect populations and its ecological interpretations. J. of Biomath. 1991a,6(3):34–45. (In Chinese with English Abstract)
• [27] Ma, Z. S.: Studies on the population aggregation dynamics of Dendrolimus tabulaeformis (Tsai et Liu), Lasiocampidae. J. of Biomath. 1991b, 6(1):79–86. (In Chinese with English Abstract)
• [28] Ma, Z. S.: Further interpreted Taylor’s Power Law and Population Aggregation Critical Density. Trans. Ecol. Soc. China. 1991c,1:284–288. (In Chinese with English Abstract)
• [29] Ma, Z. S. and A. W. Krings.: Dynamic Populations in Genetic Algorithms. SIGAPP, the 23rd Annual ACM Symposium on Applied Computing, Ceara, Brazil, March 16–20, 2008. 5 Pages.
• [30] Neyman, J.: On a new class of contagious: distributions, applicable in entomology and bacteriology. Ann. Math. Stat. 1939,10:35–57.
• [31] Odetayo, M. O.: Optimal population size for genetic algorithms: an investigation. IEE Colloquium on Genetic Algorithms for Control Systems Engineering. May 28, 1993. London, UK.
• [32] Olofsson, P.: Probability, Statistics, and Stochastic Processes. Wiley Inter Science. 2005:486pp.
• [33] Perry, J. N. and Taylor, L. R.: Ades: New Ecological Families of Species-Specific Frequency Distributions that Describe Spatial Samples with an Intrinsic Power–Law Variance–Mean Property. J. Anim. Ecol. 1985,54(3):931–953.
• [34] Rylander, B.: Computational Complexity and Genetic Algorithms. Ph.D. Dissertation. Computer Science Department, University of Idaho, Moscow, ID 83844. 2001.
• [35] Schaffer, J., Caruanna, R., Eshelman, L., Das, K.: A study of control parameters affecting online performance of genetic algorithms for function optimization. Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufman. 1989.
• [36] Skellam, J. G.: On the derivation and applicability of Neyman’s type A distribution. Biometrika. 1958,45:32–36.
• [37] Tan, K. C., Lee, T. H., Khor, E. F.: Evolutionary algorithms with goal and priority information for multiobjective optimization. Proceedings of the 1999 Congress on Evolutionary Computation, 1999. CEC 99. 6–9 July 1999, V( 1):113–.
• [38] Tan, K. C., Lee, T. H, and Khor, E. F.: Evolutionary Algorithms with Dynamic Population Size and Local Exploration for Multi-objective Optimization. IEEE Trans. Evol. Comp. 2001, 5(6): 565–588.
• [39] Taylor, L. R.: Aggregation, variance, and the mean. Nature, 1961(189):732–735.
• [40] Taylor, L. R., and R. A. J. Taylor.: Aggregation, migration, and population mechanisms. Nature. 1977(265):451–421.
• [41] Taylor, L. R.: Assessing and interpreting the spatial distributions of insect populations. Ann. Rev. Entomol. 1984(29):321–57.
• [42] Yuen, S. Y., and Ma, C. H.: Genetic Algorithm with Competitive Image Labeling and Least Square. Proceedings. International Conference on Image Analysis and Processing, Sept. 1999:364–369.