An Experimental Comparison of Algebraic Crossover Operators for Permutation Problems

• Autorzy: Baioletti Marco , Di Bari Gabriele , Milani Alfredo , Santucci Valentino

Identyfikatory

DOI

10.3233/FI-2020-1940

• Języki publikacji: EN

Abstrakty

EN

Crossover operators are very important components in Evolutionary Computation. Here we are interested in crossovers for the permutation representation that find applications in combinatorial optimization problems such as the permutation flowshop scheduling and the traveling salesman problem. We introduce three families of permutation crossovers based on algebraic properties of the permutation space. In particular, we exploit the group and lattice structures of the space. A total of 34 new crossovers is provided. Algebraic and semantic properties of the operators are discussed, while their performances are investigated by experimentally comparing them with known permutation crossovers on standard benchmarks from four popular permutation problems. Three different experimental scenarios are considered and the results clearly validate our proposals.

Słowa kluczowe

EN

algebraic crossovers; lattice operators; permutation crossovers

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 174, nr 3/4
• Strony: 201--228
• Opis fizyczny: Bibliogr. 51 poz., tab., wykr.

Twórcy

autor

Baioletti Marco

• Department of Mathematics and Computer Science, University of Perugia, Italy

autor

Di Bari Gabriele

• Department of Mathematics and Computer Science, University of Florence, Italy

autor

Milani Alfredo

• Department of Mathematics and Computer Science, University of Perugia, Italy

autor

Santucci Valentino

• Department of Humanities and Social Sciences, University for Foreigners of Perugia, Italy

Bibliografia

• [1] Michalewicz Z, Hartley SJ. Genetic algorithms+ data structures= evolution programs. Mathematical Intelligencer, 1996. 18(3):71.
• [2] Milani A, Santucci V. Asynchronous Differential Evolution. In: Proc. of 2010 IEEE Congress on Evolutionary Computation (CEC 2010). 2010 pp. 1-7. doi:10.1109/CEC.2010.5586107.
• [3] Umbarkar A, Sheth P. Crossover Operators in Genetic Algorithms: a Review. ICTACT journal on soft computing, 2015. 6(1). doi:10.21917/ijsc.2015.0150.
• [4] Nagata Y, Kobayashi S. A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS Journal on Computing, 2013. 25(2):346-363. doi:10.1287/ijoc.1120.0506.
• [5] Whitley D, Hains D, Howe A. Tunneling between optima: partition crossover for the traveling salesman problem. In: Proceedings of the 11th Annual conference on Genetic and evolutionary computation. ACM, 2009 pp. 915-922. doi:10.1145/1569901.1570026.
• [6] Martí R, Reinelt G. The linear ordering problem: exact and heuristic methods in combinatorial optimization, volume 175. Springer Science & Business Media, 2011. ISBN: 978-3-642-16728-7, 978-3-642-26656-0.
• [7] Santucci V, Ceberio J. Using pairwise precedences for solving the linear ordering problem. Applied Soft Computing, 2020. 87. doi:https://doi.org/10.1016/j.asoc.2019.105998.
• [8] Santucci V, Baioletti M, Milani A. Algebraic Differential Evolution Algorithm for the Permutation Flowshop Scheduling Problem With Total Flowtime Criterion. IEEE Transactions on Evolutionary Computation, 2016. 20(5):682-694. doi:10.1109/TEVC.2015.2507785.
• [9] Baioletti M, Milani A, Santucci V. Algebraic Crossover Operators for Permutations. In: Proc. of 2018 IEEE Congress on Evolutionary Computation (CEC 2018). 2018 pp. 1-8. doi:10.1109/CEC.2018.8477867.
• [10] Baioletti M, Milani A, Santucci V. Algebraic Particle Swarm Optimization for the permutations search space. In: Proc. of 2017 IEEE Congress on Evolutionary Computation (CEC 2017). 2017 pp. 1587-1594. doi:10.1109/CEC.2017.7969492.
• [11] Baioletti M, Milani A, Santucci V. Automatic Algebraic Evolutionary Algorithms. In: Proc. of International Workshop on Artificial Life and Evolutionary Computation (WIVACE 2017). 2018 pp. 271-283. doi:10.1007/978-3-319-78658-2_20.
• [12] Baioletti M, Milani A, Santucci V. Learning Bayesian Networks with Algebraic Differential Evolution. In: Proc. of 15th International Conference on Parallel Problem Solving from Nature (PPSN XV). 2018 pp. 436-448. doi:10.1007/978-3-319-99259-4_35.
• [13] Burkard RE, Karisch SE, Rendl F. QAPLIB-a quadratic assignment problem library. Journal of Global optimization, 1997. 10(4):391-403.
• [14] Schiavinotto T, Stützle T. A review of metrics on permutations for search landscape analysis. Computers & Operations Research, 2007. 34(10):3143-3153. doi:10.1016/j.cor.2005.11.022.
• [15] Baioletti M, Milani A, Santucci V. An Extension of Algebraic Differential Evolution for the Linear Ordering Problem with Cumulative Costs. In: Proc. of 14th Int. Conf. on Parallel Problem Solving from Nature (PPSN XIV). 2016 pp. 123-133. doi:10.1007/978-3-319-45823-6_12.
• [16] Baioletti M, Milani A, Santucci V. MOEA/DEP: An Algebraic Decomposition-Based Evolutionary Algorithm for the Multiobjective Permutation Flowshop Scheduling Problem. In: Evolutionary Computation in Combinatorial Optimization. 2018 pp. 132-145. doi:10.1007/978-3-319-77449-7_9.
• [17] Baioletti M, Milani A, Santucci V, Tomassini M. Search Moves in the Local Optima Networks of Permutation Spaces: The QAP Case. In: Proc. of the 2019 Genetic and Evolutionary Computation Conference Companion (GECCO 2019). 2019 p. 15351542. doi:10.1145/3319619.3326849.
• [18] Baioletti M, Milani A, Santucci V. Variable neighborhood algebraic Differential Evolution: An application to the Linear Ordering Problem with Cumulative Costs. Information Sciences, 2020. 507:37-52. doi:10.1016/j.ins.2019.08.016.
• [19] Herstein IN. Abstract Algebra, 3rd Edition. Wiley & Sons, 1996. ISBN 978-0-471-36879-3.
• [20] Bespamyatnikh S, Segal M. Enumerating longest increasing subsequences and patience sorting. Information Processing Letters, 2000. 76(1-2):7-11. doi:http://dx.doi.org/10.1016/S0020-0190(00)00124-1.
• [21] Baioletti M, Milani A, Santucci V, Bartoccini U. An Experimental Comparison of Algebraic Differential Evolution Using Different Generating Sets. In: Proc. of the Genetic and Evolutionary Computation Conference Companion (GECCO 2019). 2019 p. 15271534. doi:10.1145/3319619.3326854.
• [22] Grätzer G, Wehrung F. Lattice Theory: Special Topics and Applications - Vol. 2. Springer, 2016.
• [23] Larranaga P, Kuijpers CMH, Murga RH, Inza I, Dizdarevic S. Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, 1999. 13(2):129-170.
• [24] Andreica A, Chira C. Best-order crossover for permutation-based evolutionary algorithms. Applied Intelligence, 2015. 42(4):751-776. doi:10.1007/s10489-014-0623-0.
• [25] Goldberg DE, Lingle R, et al. Alleles, loci, and the traveling salesman problem. In: Proceedings of an international conference on genetic algorithms and their applications, volume 154. Lawrence Erlbaum, Hillsdale, NJ, 1985 pp. 154-159.
• [26] Davis L. Applying Adaptive Algorithms to Epistatic Domains. In: Proceedings of the 9th International Joint Conference on Artificial Intelligence - Volume 1, IJCAI’85. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. ISBN 0-934613-02-8, 1985 pp. 162-164. URL http://dl.acm.org/citation.cfm?id=1625135.1625164.
• [27] Syswerda G. Schedule Optimization Using Genetic Algorithms. In: Handbook of Genetic Algorithms. 1991 pp. 332-349.
• [28] Oliver IM, Smith DJ, Holland JRC. A Study of Permutation Crossover Operators on the Traveling Salesman Problem. In: Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application. L. Erlbaum Associates Inc., Hillsdale, NJ, USA. ISBN 0-8058-0158-8, 1987 pp. 224-230. URL http://dl.acm.org/citation.cfm?id=42512.42542.
• [29] Larrañaga P, Kuijpers CMH, Poza M, Murga RH. Decomposing Bayesian networks: triangulation of the moral graph with genetic algorithms. Statistics and Computing, 1997. 7(1):19-34. doi:10.1023/A:1018553211613. URL https://doi.org/10.1023/A:1018553211613.
• [30] WHITLEY D. Traveling Salesman and Sequence Scheduling: Quality Solutions Using Genetic Edge Reconbination. Handbook of Genetic Algorithms, 1991. pp. 350-372.
• [31] Gavanelli M, Nonato M, Peano A, Alvisi S, Franchini M. Scheduling Countermeasures to Contamination Events by Genetic Algorithms. AI Commun., 2015. 28(2):259-282. URL http://dl.acm.org/citation.cfm?id=2733572.2733579.
• [32] Gopal R, Rosmaita B, Van Gucht D. Genetic algorithms for the traveling salesman problem. In: Proc. of 1st International Conference on Genetic Algorithms and their Applications. 1985 pp. 160-165.
• [33] Schiavinotto T, Sttzle T. The Linear Ordering Problem: Instances, Search Space Analysis and Algorithms. J. Math. Model. Algorithms, 2004. 3:367-402. doi:10.1023/B:JMMA.0000049426.06305.d8.
• [34] Glover F, Laguna M, Martí R. Fundamentals of scatter search and path relinking. Control and cybernetics, 2000. 29(3):653-684.
• [35] Kennedy J, Eberhart R. Particle swarm optimization. In: Proc. of IEEE Intern. Conf. on Neural Networks, volume 4. 1995 pp. 1942-1948.
• [36] Poli R, Kennedy J, Blackwell T. Particle swarm optimization: An overview. Swarm Intelligence, 2007. 1(1):33-57. doi:10.1007/s11721-007-0002-0.
• [37] del Valle Y, Venayagamoorthy GK, Mohagheghi S, Hernandez JC, Harley RG. Particle Swarm Optimization: Basic Concepts, Variants and Applications in Power Systems. IEEE Transactions on Evolutionary Computation, 2008. 12(2):171-195. doi:10.1109/TEVC.2007.896686.
• [38] Kennedy J, Eberhart RC. A discrete binary version of the particle swarm algorithm. In: Proc. of IEEE International Conference on Systems, Man, and Cybernetics, volume 5. 1997 pp. 4104-4108.
• [39] Tasgetiren MF, Liang YC, Sevkli M, Gencyilmaz G. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research, 2007. 177(3):1930-1947. doi:10.1016/j.ejor.2005.12.024.
• [40] Ai TJ, Kachitvichyanukul V. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 2009. 36(5):1693-1702. doi:10.1016/j.cor.2008.04.003.
• [41] Koulinas G, Kotsikas L, Anagnostopoulos K. A particle swarm optimization based hyper-heuristic algorithm for the classic resource constrained project scheduling problem. Information Sciences, 2014. 277:680-693. doi:10.1016/j.ins.2014.02.155.
• [42] Gao H, Kwong S, Fan B, Wang R. A Hybrid Particle-Swarm Tabu Search Algorithm for Solving Job Shop Scheduling Problems. IEEE Transactions on Industrial Informatics, 2014. 10(4):2044-2054. doi:10.1109/TII.2014.2342378.
• [43] Cagnina L, Esquivel S, Gallard R. Particle swarm optimization for sequencing problems: a case study. In: Proc. of Congress on Evolutionary Computation, volume 1. 2004 pp. 536-541.
• [44] Bean JC. Genetic Algorithms and Random Keys for Sequencing and Optimization. ORSA Journal on Computing, 1994. 6(2):154-160.
• [45] Bratton D, Kennedy J. Defining a Standard for Particle Swarm Optimization. In: Proc. of IEEE Swarm Intelligence Symposium. 2007 pp. 120-127.
• [46] Hutter F, Hoos HH, Leyton-Brown K. Sequential Model-Based Optimization for General Algorithm Configuration. In: Proc. of LION-5 (Learning and Intelligent Optimization Conference). 2011 pp. 507-523. doi:10.1007/978-3-642-25566-3_40.
• [47] Birattari M. Tuning Metaheuristics: A Machine Learning Perspective. Springer, 2009. ISBN:978-3-642-00482-7, 978-3-642-10149-6.
• [48] Derrac J, Garca S, Molina D, Herrera F. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 2011. 1(1):3-18. doi:10.1016/j.swevo.2011.02.002.
• [49] Baioletti M, Milani A, Santucci V. A discrete differential evolution algorithm for multi-objective permutation flowshop scheduling. Intelligenza Artificiale, 2016. 10(2):81-95. doi:10.3233/IA-160097.
• [50] Ayodele M, McCall JAW, Regnier-Coudert O. RK-EDA: A Novel Random Key Based Estimation of Distribution Algorithm. In: Parallel Problem Solving from Nature - PPSN XIV - 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings. 2016 pp. 849-858. doi:10.1007/978-3-319-45823-6_79.
• [51] Santucci V, Baioletti M, Di Bari G, Milani A. A Binary Algebraic Differential Evolution for the MultiDimensional Two-Way Number Partitioning Problem. In: Evolutionary Computation in Combinatorial Optimization. 2019 pp. 17-32. doi:10.1007/978-3-030-16711-0_2.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).