×

Multiple parents crossover operators: a new approach removes the overlapping solutions for sequencing problems. (English) Zbl 1351.90170

Summary: Maintaining population diversity throughout generations of Genetic Algorithms (GAs) is key to avoid premature convergence. Redundant solutions is one cause for the decreasing population diversity. To prevent the negative effect of redundant solutions, we propose a framework that is based on the multi-parents crossover (MPX) operator embedded in GAs. Because MPX generates diversified chromosomes with good solution quality, when a pair of redundant solutions is found, we would generate a new offspring by using the MPX to replace the redundant chromosome. Three schemes of MPX will be examined and will be compared against some algorithms in literature when we solve the permutation flowshop scheduling problems, which is a strong NP-Hard sequencing problem. The results indicate that our approach significantly improves the solution quality. This study is useful for researchers who are trying to avoid premature convergence of evolutionary algorithms by solving the sequencing problems.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Burke, E. K.; Gustafson, S.; Kendall, G., Diversity in genetic programming: an analysis of measures and correlation with fitness, IEEE Trans. Evolutionary Comput., 8, 1, 47-62 (2004)
[3] Burke, R.; Gustafson, S.; Kendall, G., A survey and analysis of diversity measures in genetic programming, (Proceedings of the Genetic and Evolutionary Computation Conference Table of Contents (2002), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 716-723
[4] Lin, W.; Chen, T., Analysis of two restart algorithms, Neurocomputing, 69, 16-18, 2301-2308 (2006)
[5] Raman, N.; Talbot, F., The job shop tardiness problem: a decomposition approach, Eur. J. Operat. Res., 69, 2, 187-199 (1993) · Zbl 0783.90055
[6] Ahuja, R.; Orlin, J.; Tiwari, A., A greedy genetic algorithm for the quadratic assignment problem, Comput. Operat. Res., 27, 10, 917-934 (2000) · Zbl 0970.90067
[7] Cheng, H.; Yang, S., Genetic algorithms with immigrants schemes for dynamic multicast problems in mobile ad hoc networks, Eng. Appl. Artificial Intell., 23, 5, 806-819 (2010)
[8] Xing, L.; Chen, Y.; Yang, K.; Hou, F.; Shen, X.; Cai, H., A hybrid approach combining an improved genetic algorithm and optimization strategies for the asymmetric traveling salesman problem, Eng. Appl. Artificial Intell., 21, 8, 1370-1380 (2008)
[11] Ahmed, Z., Multi-parent extension of sequential constructive crossover for the travelling salesman problem, Int. J. Operat. Res., 11, 3, 331-342 (2011) · Zbl 1254.90183
[12] António, C., A study on synergy of multiple crossover operators in a hierarchical genetic algorithm applied to structural optimisation, Struct. Multidiscip. Optim., 38, 2, 117-135 (2009)
[13] Chang, W. D., A multi-crossover genetic approach to multivariable PID controllers tuning, Expert Syst. Appl., 33, 3, 620-626 (2007)
[15] Ting, C. K.; Su, C. H.; Lee, C. N., Multi-parent extension of partially mapped crossover for combinatorial optimization problems, Expert Syst. Appl., 37, 3, 1879-1886 (2010)
[16] Yoon, H. S.; Moon, B. R., An empirical study on the synergy of multiple crossover operators, IEEE Trans. Evolution. Comput., 6, 2, 212-223 (2002)
[17] Carvalho, A. G.; Araujo, A. F.R., Improving NSGA-II with an adaptive mutation operator, (Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference (2009), ACM), 2697-2700
[18] Eiben, A.; Michalewicz, Z.; Schoenauer, M.; Smith, J., Parameter Control in Evolutionary Algorithms (2007), Springer
[19] Smit, S.; Eiben, A., Parameter tuning of evolutionary algorithms: generalist vs specialist, Appl. Evolution. Comput., 542-551 (2010)
[20] Jin, Y.; Branke, J., Evolutionary optimization in uncertain environments-a survey, IEEE Trans. Evolution. Comput., 9, 3, 303-317 (2005)
[21] Nojima, Y.; Narukawa, K.; Kaige, S.; Ishibuchi, H., Effects of removing overlapping solutions on the performance of the NSGA-II algorithm, (Proceedings of Third International Conference on Evolutionary Multi-criterion Optimization (2005), Springer), 341-354, vol. 3410 · Zbl 1109.68627
[24] Cedeño, W.; Vemuri, V., Analysis of speciation and niching in the multi-niche crowding GA, Theor. Comput. Sci., 229, 1, 177 (1999) · Zbl 0938.68078
[25] Lozano, M.; Herrera, F.; Cano, J., Replacement strategies to preserve useful diversity in steady-state genetic algorithms, Inform. Sci., 178, 23, 4421-4433 (2008)
[26] Muhlenbein, H., Parallel genetic algorithms in combinatorial optimization, (Balci, O.; Sharda, R.; Zenios, S., Computer Science and Operations Research (1992), Pergamon Press: Pergamon Press New York), 441-456
[27] Porumbel, D.; Hao, J.; Kuntz, P., Diversity control and multi-parent recombination for evolutionary graph coloring algorithms, (Proceedings of the 9th European Conference on Evolutionary Computation in Combinatorial Optimization (2009), Springer), 121-132
[29] Eiben, A.; Raué, P.; Ruttkay, Z., Genetic algorithms with multi-parent recombination, Lecture Notes Comput. Sci., 866, 78-87 (1994)
[31] Eiben, A.; Van Kemenade, C.; Kok, J., Orgy in the computer: multi-parent reproduction in genetic algorithms, Lecture Notes Comput. Sci., 929, 934-945 (1995)
[33] Taillard, E., Benchmarks for basic scheduling instances, Eur. J. Operat. Res., 64, 278-285 (1993) · Zbl 0769.90052
[34] Montgomery, D., Design and Analysis of Experiments (2008), John Wiley & Sons Inc
[35] Chang, P. C.; Chen, S. H.; Fan, C. Y., Genetic algorithm integrated with artificial chromosomes for multi-objective flowshop scheduling problems, Appl. Math. Comput., 205, 2, 550-561 (2008) · Zbl 1152.90432
[36] Chen, S.; Chang, P.; Zhang, Q.; Wang, C., A Guided Memetic Algorithm with Probabilistic Models, Int. J. Innovative Comput. Inform. Control, 5, 12B, 4753-4764 (2009)
[37] Chang, P. C.; Chen, S. H.; Fan, C. Y., Mining gene structures to inject artificial chromosomes for genetic algorithm in single machine scheduling problems, Appl. Soft Comput. J., 8, 1, 767-777 (2008)
[38] Chen, S. H.; Chang, P. C.; Cheng, T. C.E.; Zhang, Q., A self-guided genetic algorithm for permutation flowshop scheduling problems, Comput. Operat. Res., 39, 7, 1450-1457 (2012) · Zbl 1251.90122
[39] Chang, P. C.; Chen, S. H.; Mani, V., A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties, Appl. Math. Model., 33, 1, 579-596 (2009) · Zbl 1167.90503
[40] Zheng, D. Z.; Wang, L., An effective hybrid heuristic for flow shop scheduling, Int. J. Adv. Manufac. Technol., 21, 1, 38-44 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.