Atabak Mashhadi KASHTIBAN, Sohrab KHANMOHAMMADI

Solving multimodal optimization problems based on efficient partitioning of genotypic search space

Enhancing the exploration and exploitation of multimodal optimization is still an interesting and challenging problem in optimization. Here we present a new population-based evolutionary algorithm for multiple optimal determinations. The approach is simply based on partitioning the genotypic search space and running a simple genetic algorithm with a small population within each partition. To increase the efficiency of the algorithm, the first-order discrete derivative of the fitness function for elite solutions was used to omit extra solutions. If the derivative of the fitness function is larger than a specified gradient threshold, no optimum exists within a given partition, and no population is created there after the first iteration. Except the adjusted gradient threshold, the proposed algorithm requires no other parameters rather than those of classical genetic algorithms. Moreover, unlike the other well-known algorithms, the proposed algorithm is not sensitive to the niche radius, and it needs no prior knowledge about the fitness function. The algorithm was tested for 10 multimodal benchmark functions, and its results were compared with the other related algorithms considering 4 commonly performance criteria. Our results show that the proposed algorithm is not only acceptable in terms of diversification and function evaluation number, but also has improved efficiency as compared to the others.

PDF

___

[1] De Jong KA. An analysis of the behavior of a class of genetic adaptive systems. PhD, University of Michigan, Ann Arbor, MI, USA, 1975.
[2] Goldberg DE, Richardson J. Genetic algorithms with sharing for multimodal function optimization. In: Proceedings of the Second International Conference on Genetic Algorithms; 1987. pp. 4149.
[3] Yin X, Germay N. A fast genetic algorithm with sharing scheme using cluster analysis methods in multi-modal function optimization. In: Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms; 1993. pp. 450457.
[4] Harik G. Finding multi-modal solutions using restricted tournament selection. In: Proceedings of the Sixth International Conference on Genetic Algorithms; 1997. pp. 2431.
[5] P´etrowski A. A clearing procedure as a niching method for genetic algorithms. In: Proceedings of Third IEEE International Conference on Evolutionary Computation; 1996. pp. 798803.
[6] Li JP, Balazs ME, Parks GT, Clarkson PJ. A species conserving genetic algorithm for multi-modal function optimization. IEEE T Evol Comput 2002; 10: 207234.
[7] Gan J, Warwick K. Dynamic niche clustering: a fuzzy variable radius niching technique for multimodal optimization in gas. In: Proceedings of IEEE Congress on Evolutionary Computation; 2001. pp. 215222.
[8] Beasley D, Bull DR, Matin RR. A sequential niche technique for multimodal function optimization. IEEE T Evol Comput 1993; 1: 101125.
[9] Zhang J, Huang DS, Lok TM, Lyu MR. A novel adaptive sequential niche technique for multimodal function optimization. Neurocomputing 2006; 69: 23962401.
[10] Qing L, Gang W, Zaiyue Y, Qiuping W. Crowding clustering genetic algorithm for multimodal function optimization. Appl Soft Comput 2008; 8: 8895.
[11] Siarry P, Petrowski A, Bessaou M. A multipopulation genetic algorithm aimed at multimodal optimization. Adv Eng Softw 2002; 33: 207213.
[12] Miller BL, Shaw MJ. Genetic algorithms with dynamic niche sharing for multimodal function optimization. In: Proceedings of the IEEE International Conference on Evolutionary Computation; 1996. pp. 786791.
[13] Mahfoud SW. Crowding and Preselection Revisited. Technical report, IlliGAL. Urbana-Champaign, IL, USA: University of Illinois at Urbana Champaign, Illinois Genetic Algorithm Laboratory, 1992.
[14] Mengshoel OJ, Goldberg DE. The crowding approach to niching in genetic algorithms. IEEE T Evolut Comput 2008; 16: 315354.
[15] Li JP, Balazs ME, Parks GT, Glarkson PJ. A species conserving genetic algorithms for multimodal function optimization. IEEE T Evolut Comput 2002; 10: 207234.
[16] Leung KS, Liang Y. Adaptive elitist-population based genetic algorithm for multimodal function optimization. In: Proceedings of Genetic and Evolutionary ComputationGECCO; 2003. pp. 11601171.
[17] Liang Y, Leung KS. Genetic algorithm with adaptive elitist-population strategies for multimodal function optimization. Appl Soft Comput 2011; 11: 20172034.
[18] Elo S. A parallel genetic algorithm on the CM-2 for multi-modal optimization. In: Proceedings of International Conference on Evolutionary Computation; 1994. pp. 818822.
[19] Tsutsui S, Fujimoto Y. Forking genetic algorithms: GAs with search space division schemes. IEEE T Evolut Comput 1997; 5: 6180.
[20] Ursem RK. Multinational evolutionary algorithms. In: Proceedings of International Conference on Evolutionary Computation; 1999. pp. 16331640.
[21] Lung RL. A subpopulation stability based evolutionary technique for multimodal optimization. In: Proceeding of GECCO; 2004. pp. 2630.
[22] Yu EL, Suganthan PN. An ensemble of niching algorithms. Inform Sciences 2010; 180: 28152833.
[23] Parsopoulos KE, Vrahatis MN. On the computation of all global minimizers through particle swarm optimization. IEEE T Evolut Comput 2004; 8: 211224.
[24] Parrot D, Li X. Locating and tracking multiple dynamic optimal by a particle swarm model using speciation. IEEE T Evolut Comput 2006; 10: 440458.
[25] Vitela JE, Castanos O. A sequential niching memetic algorithm for continuous multimodal function optimization. Appl Math Comput 2012; 218: 82428259.
[26] Juang YT, Tung SL, Chiu HC. Adaptive fuzzy particle swarm optimization for global optimization of multimodal functions. Inform Sciences 2011; 181: 45394549.
[27] Qu BY, Suganthan PN, Das S. A distance-based locally informed particle swarm model for multi-modal optimization. IEEE T Evolut Comput 2012; 17: 387402.
[28] Krohling RA, Mendel E, Campos M. Swarm algorithms with chaotic jumps for optimization of multimodal functions. Eng Optimiz 2011; 43: 12431261.
[29] Fan SS, Liang YC, Zahara E. Hybrid simplex search and particle swarm optimization for the global optimization of multimodal functions. Eng Optimiz 2004; 36: 401418.
[30] Wang H, Moon I, Yang S, Wang D. A memetic particle swarm optimization algorithm for multimodal optimization problems. Inform Sciences 2012; 197: 3852.
[31] Imrani AE, Bouroumi A, Abidine ZE, Limouri M, Essaid A. A fuzzy clustering-based niching approach to multimodal function optimization. Cogn Syst Res 2000; 1: 119133.
[32] Li S, Tan M, Tsang W, Kwok JTY. A hybrid PSO-BFGS Strategy for global optimization of multimodal functions. IEEE T Syst Man Cyb 2011; 41: 10031014.
[33] Yang XS. Firefly algorithms for multimodal optimization. In: Proceedings of SAGA09; 2009. pp. 169178.
[34] Yap DFW, Koh SP, Tiong SK, Prajindra SK. A swarm-based artificial immune system for solving multimodal functions. Appl Artif Intell 2011; 25: 693707.
[35] Woldermariam KM, Yen GG. Vaccine-enhanced artificial immune system for multimodal function optimization. IEEE T Syst Man Cyb 2010; 40: 218228.
[36] Shir OM, Emmerich M, Back T. Adaptive niche radii and niche shapes approaches for niching with the CMA-ES. IEEE T Evolut Comput 2010; 18: 97126.
[37] Thomsen R. Multimodal optimization using crowding-based differential evolution. In: Proceedings of the Congress on Evolutionary Computation; 2004. pp. 13821389.
[38] Hendershot ZV. A differential evolution algorithm for automatically discovering multiple global optima in multidimensional discontinuous spaces. In: Proceedings of the Artificial Intelligence and Cognitive Sciences; 2004. pp. 9297.
[39] Zaharie D. Extensions of differential evolution algorithms for multimodal optimization. In: Proceedings of SYNASC; 2004. pp. 523534.
[40] Angus D. Niching for ant colony optimization. In: Lewis A, Mostaghim S, Randall M, editors. Biologically-Inspired Optimisation Methods. Heidelberg, Germany: Springer, 2009. pp. 165188.
[41] Yao J, Kharma N, Grogono P. Bi-objective multipopulation genetic algorithm for multimodal function optimization. IEEE T Evolut Comput 2010; 14: 80102.
[42] Ursem RK. Multinational gas: multimodal optimization techniques in dynamic environments. In: Proceedings of GECCO; 2000. pp. 16331640.
[43] Qu BY, Liang JJ, Suganthan PN. Niching particle swarm optimization with local search for multi-modal optimization. Inform Sciences 2012; 197: 131143.
[44] Lin CY, Wu WH. Niche identification techniques in multimodal genetic search with sharing scheme. Adv Eng Softw 2002; 33: 779791.
[45] Wong KC, Wu CH, Mok RKP, Peng C, Zhang Z. Evolutionary multimodal optimization using the principle of locality. Inform Sciences 2012; 194: 138170.
[46] Otani T, Suzuki R, Arita T. DE/isolated/1: A new mutation operator for multimodal optimization with differential evolution. International Journal of Machine Learning and Cybernetics 2013; 4: 99105.