Abstract

Structured-population Genetic Algorithm (GA) usually leads to more superior performance than the panmictic genetic algorithm; since it can control two opposite processes, namely exploration and exploitation in the search space. Several spatially structured-population GAs have been introduced in the literature such as cellular, patchwork, island-model, terrain-based A, graph-based, religion-based and social-based GA. All the aforementioned works did not construct the sub-populations based on the genes information of the individuals themselves. The structuring of sub-populations based on this information might help in attaining better performance and more efficient search strategy. In this paper, the structured population is represented as hierarchical hypercube of sub-populations that are dynamically constructed and adapted at search time. Each sub-population represents a sub-division of the real genes space. This structure could help in directing the search towards the promising sub-spaces. Finally, a comparative study with other known structured population GA is provided.

References

• Whitley, D. "Cellular genetic algorithms". In Proceedings of the Fifth International Conference on Genetic Algorithms S. Forrest (Ed. ), San Mateo, CA : Morgan Kaufman Publishers,, 1993, pp. 658.
• Back, T. , Fogel, D. B. , Michalewicz, Z. , Et Al. , Eds. Handbook on "Evolutionary Computation". IOP Publishing Ltd and Oxford University Press, 1997.
• Krink, T. , Mayoh, B. H. , and Michalewicz, Z. "A Patchwork model for evolutionary algorithms with structured and variable size populations". In Proceedings of the Genetic and Evolutionary Computation Conference, Vol. 2, 1999, pp. 1321-1328.
• Krink, T. , and Ursem, R. K. "Parameter control using the agent based patchwork model". In Proceedings of the Second Congress on Evolutionary Computation (CEC-2000). San Diego, CA, USA: 77-83, 2000.
• Gorden, V. S. , Pirie, R. , Wachter, A. , and Sharp, S. "Terrain-based genetic algorithm (TBGA): Modeling parameter space as terrain". In Proceedings of the Genetic and Evolutionary Computation Conference, vol. 1, 1999, pp. 299- 235.
• René Thomsen, Peter Rickers, Thiemo Krink, "A Religion-Based Spatial Model for Evolutionary Algorithms", proceedings of the 6th International Conference on Parallel Problem Solving from Nature (PPSN VI)
• Nagham Azmi AL-Madi, Ahamad Tajudin Khader, "De Jong's Sphere Model Test for A Social-Based Genetic Algorithm (SBGA)", IJCSNS International Journal of Computer Science and Network Security, Vol. 8 No. 3 pp. 179-185, 2008.
• Gordon V. S. , Whitley D. : "Serial and Parallel Genetic Algorithms as Function Optimizers". In Forrest S. (ed. ): Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA (1993) 177-183
• Enrique Alba, Antonio J. Nebro, and Jose' M. Troya, "Heterogeneous Computing and Parallel Genetic Algorithms", Journal of Parallel and Distributed Computing 62, 1362–1385 (2002)
• Paulo M. Franca, Jatinder N. D. Gupta, Alexandre S. Mendes, Pablo Moscato, Klaas J. Veltink, "Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups", Computers & Industrial Engineering 48, Elsevier (2005) 491–506
• Daniel Ashlock, Mark Smucker, and John Walker, Graph Based Genetic Algorithms, in Proceedings of the Congress on Evolutionary Computation: (1999) 1362-1368.
• Manderik, B. and Spiessens, P. , "Fine-Grained Parallel Genetic Algorithms", Proceedings of the 3rd International Conference on Genetic Algorithms, 1989.
• Hillis D. , "Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procddure", physics D 42 (1990): 228-234.
• Collins R. and Jefferson, D. , "Selection in Massively Parallel Genetic Algorithms", Proceedings of the 4th International Conference on Genetic Algorithms, Morgan-Kaufmann (1991), pp. 249-256.
• E. K. Burke, S. Gustafson, and G. Kendall. Diversity in genetic programming: An analysis of measures and correlation with fitness. IEEE Transactions on Evolutionary Computation, 8(1):47–62, 2004.
• E. Zitzler, K. Deb, and L. Thiele. Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8(2):173–195, 2000.
• Y. Leung, Y. Gao, and Z. B. Xu. Degree of population diversity—a perspective on premature convergence in genetic algorithms and its Markov chain analysis. IEEE Transactions on Neural Networks, 8(5):1165–1176, 1997.
• J. C. Costa, R. Tavares, and A. Rosa. An experimental study on dynamic random variation of population size. In IEEE International Conference on Systems, Man, and Cybernetics, pages 607–612, 1999.
• A. Piszcz and T. Soule. Genetic programming: Optimal population sizes for varying complexity problems. In Generic and Evolutionary Computation Conference, pages 953–954, 2006.
• V. K. Koumousis and C. P. Katsaras. A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance. IEEE Transactions on Evolutionary Computation, 10(1):19–28, 2006.
• F. G. Lobo and C. F. Lima. A review of adaptive population sizing schemes in genetic algorithms. In Genetic and Evolutionary Computation Conference, pages 228–234, 2005.
• G. R. Harik and F. G. Lobo. A parameter-less genetic algorithm. In Genetic and Evolutionary Computation Conference, pages 258–265, 1999.
• B. Thomas, A. Eiben, and V. der Vaart. An empirical study on GAs without parameters. In Parallel Problem Solving from Nature V, pages 315–324, 2000.
• Espinoza, F. , Minsker, B. S. and Goldberg, D. A Self-Adaptive Hybrid Genetic Algorithm. Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco, Morgan Kaufmann Publishers, p. 759, (2001).
• Krink, T. and Ursem, R. K. Parameter Control Using the Agent Based Patchwork Model. Proceedings of the Congress on Evolutionary Computation, pp. 77–83, (2000).
• Kee, E. , Airey, S. and Cye, W. An Adaptive Genetic Algorithm. Proceedings of the Genetic and Evolutionary Computation Conference, pp. 391–397, (2001).
• Tanese, R. Distributed Genetic Algorithms. In Proceedings of the Third International Conference on Genetic Algorithms, pp. 434–439, (1989).
• H. Homayounfar, S. Areibi, F. Wang, "An Advanced Island Based GA For Optimization Problems", DCDIS Conference Guelph, Ontario, Canada, pp: 46-51, May 2003.
• Shisanu Tongchim, Prabhas Chongstitvatana: Parallel genetic algorithm with parameter adaptation. Inf. Process. Lett. 82(1): 47-54 (2002)
• Dirk Schlierkamp-Voosen and Heinz Mühlenbein (1994). Strategy adaptation by competing subpopulations. PPSN 3, pages 199-208.
• Cantu'-Paz, E. , Designing efficient and accurate parallel genetic algorithms, PhD thesis, Graduate College of the University of Illinois at Urbana Champaign 1999.
• Malott B. , Averill R. C. , Goodman E. D. , Ding Y. , Punch W. F. , Use of Genetic Algorithms for optimal design of laminated composite sandwich panels with bending-twisting coupling, presented at AIAA SDM (Structures, Dynamics and Materials), Apr 96, 1996
• Eby D. , Averill R. , Goodman E. , and Punch W. , The Optimization of Flywheels Using an Injection Island Genetic Algorithm, in Bentley, P. (ed. ), Evolutionary Design by Computers, Morgan Kaufmann, San Francisco, 1999, pp. 167-190.
• Z. Skolicki and K. D. Jong. Improving evolutionary algorithms with multi-representation island models. In Parallel Problem Solving from Nature – PPSN VIII 8th International Conference. Springer-Verlag, 2004.
• D. Whitley, S. Rana, and R. B. Heckendorn. Island model genetic algorithms and linearly separable problems. In Selected Papers from AISB Workshop on Evolutionary Computing, volume 1305 of Lecture Notes In Computer Science, pages 109– 125. Springer-Verlag, 1997.
• Cengiz Kahraman, Orhan Engin, Ihsan Kaya, Mustafa Kerim Yilmaz. An application of effective genetic algorithms for Solving Hybrid Flow Shop Scheduling Problems. International Journal of Computational Intelligence Systems, 1(2): 134-147, 2008.
• Alireza Fasih, Jean Chamberlain Chedjou, Kyandoghere Kyamakya. Cellular Neural Networks-Based Genetic Algorithm for Optimizing the Behavior of an Unstructured Robot. International Journal of Computational Intelligence Systems, 2(2): 124-131, 2009.
• Yanbing Liu, Jun Huang. A Novel Fast Multi -objective Evolutionary Algorithm for QoS Multicast Routing in MANET. International Journal of Computational Intelligence Systems, 2(3): 288-297, 2009.
• Nikolas Geroliminis, Konstantinos Kepaptsoglou, Matthew G. Karlaftis, A hybrid hypercube – Genetic algorithm approach for deploying many emergency response mobile units in an urban network, Elsevier, pp 278-300, doi:10. 1016/j. ejor. 2010. 08. 031, 2010.
• ystein Langangen, Eric Edeline, Jan Ohlberger, Ian J. Winfield, Janice M. Fletcher, J. Ben James, Nils Chr. Stenseth, L. Asbjorn Vollestad, Six decades of pike and perch population dynamics in Windermere, Elsevier, pp 131-139, doi:10. 1016/j. fishres. 2011. 01. 029, 2011
• Michael Barfield, Robert D. Holt and Richard Gomulkiewicz, Evolution in Stage-Structured Populations, The American Naturalist, vol. 177, no. 4, pp. 397–409, DOI: 10. 1086/65890, April 2011
• Ting Y. Lim, Structured population genetic algorithms: a literature survey, Artificial Intelligence Review pp. 1-15, doi:10. 1007/s10462-012-9314-6, February 2012
• XianBin CAO, YuanPing GUO and Hong QIAO, A New Strategy of Dynamically Adjusting Population Size for Coevolutionary Algorithms, InternationalJournal of Intelligent Control and Systems, vol. 10, no. 3, pp 251-257, September 2005
• Isabel Gordo and Paulo R. A. Campos, Adaptive evolution in a spatially structured asexual population, Springer, Genetica (2006) 127:217–229, DOI 10. 1007/s10709-005-4012-9, 2006
• F. G. Lobo and C. F. Lima, Adaptive Population Sizing Schemes in Genetic Algorithms, Studies in Computational Intelligence (SCI) 54, 185–204, Springer-Verlag Berlin Heidelberg, 2007