Tackling Permutation-based Optimization Problems with an Algebraic Particle Swarm Optimization Algorithm

• Autorzy: Santucci, Valentino , Baioletti, Marco , Milani, Alfredo
• Języki publikacji: EN

Abstrakty

EN

Particle Swarm Optimization (PSO), though originally introduced for continuous search spaces, has been increasingly applied to combinatorial optimization problems. In this paper, we focus on the PSO applications to permutation-based problems. As far as we know, the most popular and general PSO schemes for permutation solutions are those based on random key techniques. After highlighting the main criticalities of the random key approach, we introduce a discrete PSO variant for permutation-based optimization problems. By simulating search moves through a vector space, the proposed algorithm, Algebraic PSO (APSO), allows the original PSO design to be applied to the permutation search space. APSO directly represents both particle positions and velocities as permutations. The APSO search scheme is based on a general algebraic framework for combinatorial optimization based on strong mathematical foundations. However, in order to make this new scheme viable, some challenges have to be overcome: the choice of the order of the velocity terms, and the rationale behind the PSO inertial move. Design solutions have been proposed for both the issues. Furthermore, an alternative geometric interpretation of classical PSO dynamics allows to introduce a major APSO variant based on a novel concept of convex combination between permutation objects. In total, four APSO schemes have been introduced. Experiments have been held to compare the performances of the APSO schemes with respect to the random key based PSO schemes in literature. Widely adopted benchmark instances of four popular permutation problems have been considered. The experimental results clearly show that, with high statistical evidence, APSO outperforms its competitors and it reaches results comparable with state-of-the-art on most of the instances considered.

Słowa kluczowe

EN

algebraic particle swarm optimization; permutation problem; permutation search space

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 167, nr 1-2
• Strony: 133--158
• Opis fizyczny: Bibliogr. 36 poz., rys., tab., wykr.

Twórcy

autor

Santucci, Valentino

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

autor

Baioletti, Marco

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

autor

Milani, Alfredo

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

Bibliografia

• [1] Kennedy J, Eberhart R. Particle swarm optimization. In: Proc. of IEEE Intern. Conf. on Neural Networks, volume 4. 1995 pp. 1942-1948. doi:10.1109/ICNN.1995.488968.
• [2] Santucci V, Milani A. Particle Swarm Optimization in the EDAs Framework. In: Soft Computing in Industrial Applications. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011 pp. 87-96. doi:10.1007/978-3-642-20505-7_7.
• [3] 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.
• [4] 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.
• [5] Marini F, Walczak B. Particle swarm optimization (PSO). A tutorial. Chemometrics and Intelligent Laboratory Systems, 2015. 149:153-165. doi:https://doi.org/10.1016/j.chemolab.2015.08.020.
• [6] 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. doi:10.1109/ICSMC.1997.637339.
• [7] 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. URL https://doi.org/10.1016/j.ejor.2005.12.024.
• [8] 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.
• [9] 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. URL https://doi.org/10.1016/j.ins.2014.02.155.
• [10] 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.
• [11] Bean JC. Genetic Algorithms and Random Keys for Sequencing and Optimization. ORSA Journal on Computing, 1994. 6(2):154-160. URL https://doi.org/10.1287/ijoc.6.2.154.
• [12] Hoos HH, Stützle T. Stochastic local search: Foundations and applications. Elsevier, 2004. ISBN:9781558608726, 9781493303731.
• [13] 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.
• [14] Santucci V, Baioletti M, Milani A. Solving permutation flowshop scheduling problems with a discrete differential evolution algorithm. AI Communications, 2016. 29(2):269-286. doi:10.3233/AIC-150695.
• [15] Santucci V, Baioletti M, Milani A. A Differential Evolution Algorithm for the Permutation Flowshop Scheduling Problem with Total Flow Time Criterion. In: Proc. of 13th International Conference on Parallel Problem Solving from Nature - PPSN XIII. Springer, Cham, 2014 pp. 161-170. doi:10.1007/978-3-319-10762-2_16.
• [16] Baioletti M, Milani A, Santucci V. An Extension of Algebraic Differential Evolution for the Linear Ordering Problem with Cumulative Costs. In: Proc. of 14th International Conference on Parallel Problem Solving from Nature - PPSN XIV. 2016 pp. 123-133. doi:10.1007/978-3-319-45823-6_12.
• [17] Baioletti M, Milani A, Santucci V. Linear Ordering Optimization with a Combinatorial Differential Evolution. In: Proc. of 2015 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2015. 2015 pp. 2135-2140. doi:10.1109/SMC.2015.373.
• [18] 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.
• [19] Santucci V, Baioletti M, Milani A. An Algebraic Differential Evolution for the Linear Ordering Problem. In: Companion Material Proceedings of Genetic and Evolutionary Computation Conference, GECCO 2015. 2015 pp. 1479-1480. doi:10.1145/2739482.2764693.
• [20] Baioletti M, Milani A, Santucci V. MOEA/DEP: An Algebraic Decomposition-Based Evolutionary Algorithm for the Multiobjective Permutation Flowshop Scheduling Problem. In: Proc. of European Conference on Evolutionary Computation in Combinatorial Optimization - EvoCOP 2018. Springer International Publishing, Cham. ISBN 978-3-319-77449-7, 2018 pp. 132-145. doi:10.1007/978-3-319-77449-7_9.
• [21] 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.
• [22] Bratton D, Kennedy J. Defining a Standard for Particle Swarm Optimization. In: Proc. of IEEE Swarm Intelligence Symposium. 2007 pp. 120-127.
• [23] 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.
• [24] Baioletti M, Milani A, Santucci V. A New Precedence-Based Ant Colony Optimization for Permutation Problems. In: Simulated Evolution and Learning. Springer International Publishing, Cham. ISBN 978-3-319-68759-9, 2017 pp. 960-971. doi:https://doi.org/10.1007/978-3-319-68759-9_79.
• [25] Baioletti M, Milani A, Santucci V. Algebraic Crossover Operators for Permutations. In: 2018 IEEE Congress on Evolutionary Computation (CEC 2018). 2018 pp. 1-8. doi:10.1109/CEC.2018.8477867. URL doi:10.1109/CEC.2018.8477867.
• [26] Baioletti M, Milani A, Santucci V. Learning Bayesian Networks with Algebraic Differential Evolution. In: Proc. of 15th Int. Conf. on Parallel Problem Solving from Nature - PPSN XV. Springer International Publishing, Cham, 2018 pp. 436-448. doi:10.1007/978-3-319-99259-4_35.
• [27] Baioletti M, Milani A, Santucci V. Automatic Algebraic Evolutionary Algorithms. In: Proc. of Int. Workshop on Artificial Life and Evolutionary Computation (WIVACE 2017). Springer International Publishing, Cham, 2018 pp. 271-283. doi:10.1007/978-3-319-78658-2_20.
• [28] Carpi A. On the repetition threshold for large alphabets. Lecture Notes in Computer Science, 2006. 4162 LNCS:226-237. doi:https://doi.org/10.1007/11821069_20.
• [29] Carpi A, D’Alessandro F. Independent sets of words and the synchronization problem. Advances in Applied Mathematics, 2013. 50(3):339-355. doi:https://doi.org/10.1016/j.aam.2012.07.003.
• [30] Carpi A, de Luca A. Harmonic and gold Sturmian words. European Journal of Combinatorics, 2004. 25(5):685-705. doi:10.1016/j.ejc.2003.10.007.
• [31] van den Bergh F, Engelbrecht A. A study of particle swarm optimization particle trajectories. Information Sciences, 2006. 176(8):937-971. doi:https://doi.org/10.1016/j.ins.2005.02.003.
• [32] Schiavinotto T, Stützle T. A review of metrics on permutations for search landscape analysis. Computers & Operations Research, 2007. 34(10):3143-3153.
• [33] 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.
• [34] 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.
• [35] Birattari M. Tuning Metaheuristics: A Machine Learning Perspective. Springer, 2009.
• [36] 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.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).

Identyfikatory

DOI

10.3233/FI-2019-1812