Novel Diversity-Preservative Strategies for Genetic Algorithms and Its Application for Large-Scale Optimization

Author

Faculty of Engineering, University of Bonab, Bonab, Iran

Abstract

In order to increase performance of genetic algorithms, many approaches with aim of preserving diversity have been published. However, most of these approaches can be only applied to continuous optimization problems. This does not mean that genetic algorithms do not need population diversity, when they are applied to combinatorial optimization problems. In fact, defining the concept of similarity between solutions of combinatorial optimization problems, due to their apparent differences, is not straightforward. For example, for travelling salesman problem, how to measure similarity between solutions? This paper presents diversity preservative strategies which are based on similarity between solutions. These strategies not only can be applied to continuous optimization problems, but also by proposing novel semantic-oriented approaches to compute similarity between solutions of combinatorial optimization problems, it is possible to apply to combinatorial optimization problems, successfully.

Keywords

References

[1] مجید محمدپور، حمید پروین, «الگوریتم ژنتیک آشوب‌گونه مبتنی بر حافظه و خوشه‌بندی برای حل مسائل بهینه‌سازی پویا», مجله مهندسی برق دانشگاه تبریز, 46، 3، 318-299، 1395.
[2] فرناز درخشان، فاطمه خضرلو, «طراحی و پیاده‌سازی یک روش تلفیقی هوشمند برای کنترل ترافیک شهری در تقاطع‌ها», مجله مهندسی برق دانشگاه تبریز, 47، 3، 1024-1013، 1396.
[3] علی حسامی نقشبندی، هیوا شمس, «پخش بار بهینه مقید به پایداری سیگنال کوچک با استفاده از الگوریتم ژنتیک», مجله مهندسی برق دانشگاه تبریز, 47، 3، 950-939، 1396.
[4] E. Zitzler and L. Thiele, "Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach," Ieee transactions on evolutionary computation, vol. 6, no. 4, pp. 257-271, 1999.
[5] K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: nsga-ii," IEEE transactions on evolutionary computation, vol. 3, no. 2, pp. 182-197, 2002.
[6] Zaharie, Daniela, "Control of population diversity and adaptation in differential evolution algorithms," in 9th international conference on soft computing, Brno, czech republic, 2003.
[7] O. Lehman, K. O. Stanley and R. Miikkulainen, "Effective diversity maintenance in deceptive domains," in Genetic and evolutionary computation conference, New york, 2013.
[8] M. Hutter, "Fitness uniform selection to preserve genetic diversity," Technical Report IDSIA-01-01, Manno-Lugano, Switzerland, 2001.
[9] M. Laumanns, L. Thiele, K. Deb and E. Zitzler, "Combining convergence and diversity in evolutionary multi-objective optimization," Evolutionary computation, vol. 10, no. 3, pp. 263-282, 2002.
[10] A. Toffolo and E. Benini, "Genetic diversity as an objective in multi-objective evolutionary algorithms," Evolutionary computation, vol. 11, no. 2, pp. 151-167, 2003.
[11] C. C. D. Ronco and E. Benini, "A simplex crossover based evolutionary algorithm including the genetic diversity as objective," Applied soft computing, vol. 13, no. 4, pp. 2104-2123, 2013.
[12] H. Xie and M. Zhang, "Impacts of sampling strategies in tournament selection for genetic programming," Soft computing, vol. 16, no. 4, pp. 615-633, 2012.
[13] R. K. Ursem, "Diversity-guided evolutionary algorithms," in PPSN VII Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, Granada, Spain, 2002.
[14] K. Q. Zhu, "A diversity-controlling adaptive genetic algorithm for the v ehicle routing problem with time windows," in IEEE international conference on tools with artificial intelligence, 2003.
[15] X. Zhao and J. Hao, "Exploration/exploitation tradeoff with cell-shift and heuristic crossover for evolutionary algorithms," Journal of system science & complexity, vol. 20, no. 1, pp. 66-74, 2007.
[16] R. Patel, M. M. Raghuwanshi and A. N. Jaiswal, "Modifying genetic algorithm with species and sexual selection by using k-means algorithm," in IEEE international advance comnputing conference, Patiala, india, 2009.
[17] H. Ishibuchi, Y. Sakane, N. Tsukamoto and Y. Nojima, "Implementation of cellular genetic algorithms with two neighborhood structures for single-objective and multi-objective optimization," Soft computing, vol. 15, no. 9, pp. 1749-1767, 2011.
[18] B. Dorronsoro and P. Bouvry, "Cellular genetic algorithms without additional parameters," The journal of supercomputing, vol. 63, no. 3, pp. 816-835, 2013.
[19] G. Dick and P. A. Whigham, "Spatially-structured evolutionary algorithms and sharing: do they mix," in Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time (Natural Computing Series), New York, Springer-Verlag, 2005.
[20] K. M. Bryden, D. A. Ashlock, S. Corns and S. J. Willson, "Graph-based evolutionary algorithms," IEEE transactions on evolutionary computation, vol. 10, no. 5, pp. 550-567, 2006.
[21] M. Crepinsek, S. H. Liu and M. Mernik, "Exploration and exploitation in evolutionary algorithms: a survey," Acm computing surveys, vol. 45, no. 3, pp. A1-A33, 2013.
[22] E. Alba and B. Dorronsoro, "The exploration/exploitation tradeoff in dynamic cellular genetic algorithms," IEEE transactions on evolutionary computation, vol. 9, no. 2, pp. 126-142, 2005.
[23] H. B. Amor and A. Rettinger, "Intelligent exploration for genetic algorithms using self-organizing maps in evolutionary computation," in Gecco, Washington, DC, USA, 2005.
[24] M. Črepinšek and M. Mernik, "Analysis of exploration and exploitation in evolutionary algorithms by ancestry trees," International journal of innovative computing and applications, vol. 3, no. 1, pp. 11-19, 2011.
[25] T. Park and K. R. Ryu, "A dual-population genetic algorithm," IEEE transactions on evolutionary computation, vol. 14, no. 6, pp. 865-884, 2010.
[26] S. Ronald, "More Distance Functions for Order-Based Encoding," in IEEE international conference on evolutionary computation, 1998.
[27] G. S. Hornby, "Alps: the age-layered population structure for reducing the problem of premature convergence," in The 8th annual conference on genetic and evolutionary computation, New york, 2006.
[28] Y. Li and X. Zeng, "Multi-population co-genetic algorithm with double chain-like agents structure for parallel global numerical optimization," Applied intelligence, vol. 32, no. 3, pp. 292-310, 2010.
[29] T. Park and k. R. Ryu, "A dual population genetic algorithm with evolving diversity," in IEEE congress on evolutionary computation, 2007.
[30] G. Dick, "The spatially-dispersed genetic algorithm," in GECCO'03 Proceedings of the 2003 international conference on Genetic and evolutionary computation: PartII, 2003.
[31] T. Park, R. Choe and K. R. Ryu, "Dual-population genetic algorithm for nonstationary optimization," in The 10th annual conference on genetic and evolutionary computation, 2008.
[32] Y. Li and X. Zeng, "Feature selection method with multi-population agent genetic algorithm," in Advances in Neuro-Information Processing, Springer-Verlag, 2009, pp. 493-500.
[33] S. Tsutsui, A. Ghosh, D. Corne and Y. Fujimoto, "A real coded genetic algorithm with an explorer and an exploiter populations," in The 7th international conference on genetic algorithms, San Francisco, CA, 1997.
[34] E. Alba, H. Alfonso and B. Dorronsoro, "Advanced models of cellular genetic algorithms evaluated on sat," in the 7th Annual Conference on Genetic and Evolutionary Computation, Washington DC, USA, 2005.
[35] J. Song and D. H. Kim, "Subcarrier and bit allocation scheme for the ma problem based on the ant colony optimization to minimize power consumption in ofdma systems," International journal of innovative computing, information and control, vol. 7, no. 8, pp. 4755-4764, 2011.
[36] L. Lin and M. Gen, "Auto-tuning strategy for evolutionary algorithms: balancing between exploration and exploitation," Soft computing, vol. 13, no. 2, pp. 157-168, 2009.
[37] M. Lozano, F. Herrera and J. R. Cano, "Replacement strategies to preserve useful diversity in steady-state genetic algorithms," Information sciences, vol. 178, no. 23, pp. 4421-4433, 2008.
[38] O. J. Mengshoel and D. E. Goldberg, "The crowding approach to niching in genetic algorithms," Evolutionary computation, vol. 16, no. 3, pp. 315-354, 2008.
[39] S. W. Mahfoud, "Niching methods for genetic algorithms," Doctoral Dissertation, University of Illinois at Urbana-Champaign, Champaign, 1995.
[40] 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, vol. 10, no. 1, pp. 19-28, 2006.
[41] A. Zhou, Y. Jin, Q. Zhang and B. Sendhoff, "Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization," in the 4th International Conference on Evolutionary Multi-criterion Optimization, Matsushima, Japan, 2007.
[42] J. Yao, N. Kharma and P. Grogono, "Bi-objective multipopulation genetic algorithm for multimodal function optimization," IEEE transactions on evolutionary computation, vol. 14, no. 1, pp. 80-102, 2010.
[43] H. Ismkhan, "A Novel Intelligent Algorithm to Control Mutation Rate Using the Concept of Local Trap," New Generation Computing, vol. 34, no. 1, pp. 177-192, 2016.
[44] L. M. Yi, C. Z. Xing and S. G. Yun, "An adaptive genetic algorithm with diversity-guided mutation and its global convergence property," Journal of central south university technology, vol. 11, no. 3, pp. 323-327, 2004.
[45] L. J. Eshelman, "The CHC adaptive search algorithm. How to have safe search when engaging in non-traditional genetic recombination," in Foundation of Genetic Algorithms I, San Mateo, California, Morgan Kaufmann, 1991, pp. 265-283.
[46] S. Kundu, S. Biswas, S. Das and P. N. Suganthan, "Crowding-based local differential evolution with speciation-based memory archive for dynamic multimodal optimization," in the 15th annual conference on Genetic and evolutionary computation, Amsterdam, The Netherlands, 2013.
[47] M. M. Kordmahalleh, A. Homaifar and D. B. Kc, "Hierarchical multi-label gene function prediction using adaptive mutation in crowding niching," in IEEE 13th international conference on bioinformatics and bioengineering, Chania, 2013.
[48] H. Satoh, M. Yamamura and S. Kobayashi, "Minimal generation gap model for GAs considering both exploration and exploitation," in the 4th International Conference on Fuzzy Logic, Neural Nets and Soft Computing, Iizuka, Japan, 1996.
[49] P. H. Tang and M. H. Tseng, "Adaptive directed mutation for real-coded genetic algorithms," Applied soft computing, vol. 13, no. 1, pp. 600-614, 2013.
[50] H. Ismkhan and K. Zamanifar, "Developing Programming Tools to Handle Traveling Salesman Problem by Three Object Oriented Languages," Applied Computational Intelligence and Soft Computing, 2014.
[51] G. Reinelt, "Tsplib—a traveling salesman problem library," Orsa journal on computing, vol. 3, pp. 376-384, 1991.
[52] H. Ismkhan, "Effective three-phase evolutionary algorithm to handle the large-scale colorful traveling salesman problem," Expert Systems With Applications, vol. 67, p. 148–162, 2017.
[53] Y. Chen, N. Cornick, A. O. Hall, R. Shajpal, J. Silberholz, I. Yahav and B. L. Golden, "Comparison of Heuristics for Solving the Gmlst Problem," in Telecommunications Modeling, Policy, and Technology, Springer, 2008, pp. 191-217.

Files

Share

How to cite

Statistics