Report

A comparison of estimation of distribution algorithms for the linear ordering problem Josu Ceberio Alexander Mendiburu Jose A. Lozano X Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados - MAEB2015 Outline • The linear ordering problem • The Mallows and Plackett-Luce EDAs • Experimentation • On the Boltzmann distribution associated to the LOP • Conclusions and future work 2 Permutation optimization problems Definition Combinatorial optimization problems 3 Permutation optimization problems Definition Problems whose solutions are naturally represented as permutations 4 Permutation optimization problems Goal To find the permutation solution that minimizes a fitness function The search space consists of solutions. 5 Permutation optimization problems Examples • Travelling salesman problem (TSP) • Permutation Flowshop Scheduling Problem (PFSP) • Linear Ordering Problem (LOP) • Quadratic Assignment Problem (QAP) 6 Permutation optimization problems Examples • Travelling salesman problem (TSP) • Permutation Flowshop Scheduling Problem (PFSP) • Linear Ordering Problem (LOP) • Quadratic Assignment Problem (QAP) 7 The linear ordering problem Definition 0 16 11 15 7 21 0 14 15 9 26 23 0 26 12 22 22 11 0 13 30 28 25 24 0 Example extracted from R. Martí and G. Reinelt (2011) The linear ordering problem: exact and heuristic methods in combinatorial optimization. 8 The linear ordering problem Definition 1 2 3 4 5 1 0 16 11 15 7 2 21 0 14 15 9 3 26 23 0 26 12 4 22 22 11 0 13 5 30 28 25 24 0 Example extracted from R. Martí and G. Reinelt (2011) The linear ordering problem: exact and heuristic methods in combinatorial optimization. 9 The linear ordering problem Definition 5 3 4 2 1 5 0 25 24 28 30 3 12 0 26 23 26 4 13 11 0 22 22 2 9 14 15 0 21 1 7 11 15 16 0 Example extracted from R. Martí and G. Reinelt (2011) The linear ordering problem: exact and heuristic methods in combinatorial optimization. 10 The linear ordering problem Some applications - Aggregation of individual preferences - Kemeny ranking problem - Triangulation of input-output tables of the branches of an economy - Ranking in sports tournaments - Optimal weighted ancestry relationships 11 The linear ordering problem It is an NP-hard problem (Garey and Johnson 1979) 12 Estimation of distribution algorithms Definition 13 In previous works • Implement probability models for permutation domains – The Mallows model – The Generalized Mallows model – The Plackett-Luce model 14 In previous works • Implement probability models for permutation domains – The Mallows model – The Generalized Mallows model – The Plackett-Luce model Promising performance on the LOP 15 The Mallows model Definition • A distance-based exponential probability model • Central permutation • Spread parameter • A distance on permutations 16 The Mallows model Definition • A distance-based exponential probability model • Central permutation • Spread parameter • A distance on permutations 17 The Mallows model Definition • A distance-based exponential probability model • Central permutation • Spread parameter • A distance on permutations 18 The Ulam distance Definition Calculates the minimum number of insert operations to convert . in 19 Distances and neighborhoods Swap neighborhood – Two solutions and and are neighbors if the Kendall’s-τ distance between is Interchange neighborhood – Two solutions and and are neighbors if the Cayley distance between and are neighbors if the Ulam distance between is Insert neighborhood – Two solutions and is 20 Distances and neighborhoods Swap neighborhood – Two solutions and and are neighbors if the Kendall’s-τ distance between is Interchange neighborhood – Two solutions and and are neighbors if the Cayley distance between and are neighbors if the Ulam distance between is Insert neighborhood – Two solutions and is 21 The Plackett- Luce model Definition The probability of under the Plackett-Luce model is given by The vector of scores defines the preference of each item to be ranked in top rank 22 The Plackett- Luce model Vase model interpretation A vase of infinite colored balls With known proportions of each color Draw balls from the vase until a permutation of colored balls is obtained 23 The Plackett- Luce model Vase model interpretation Stage 1 We draw a ball. And it is red. The probability to extract a red ball at this stage is: 24 The Plackett- Luce model Vase model interpretation Stage 2 We draw another ball. And it is green. The probability to extract a green ball from the remaining balls is: 25 The Plackett- Luce model Vase model interpretation Stage 3 We draw the blue ball. The probability to extract a blue ball is: 26 L-decomposability 1 2 3 4 5 1 0 16 11 15 7 2 21 0 14 15 9 3 26 23 0 26 12 4 22 22 11 0 13 5 30 28 25 24 0 27 L-decomposability 1 2 3 4 5 2 1 3 5 4 1 0 16 11 15 7 2 0 21 14 9 15 2 21 0 14 15 9 1 16 0 11 7 15 3 26 23 0 26 12 3 23 26 0 12 26 4 22 22 11 0 13 5 28 30 25 0 24 5 30 28 25 24 0 4 22 22 11 13 0 28 Experiments Design • Algorithms: - Mallows EDA under the Ulam distance (MaEDA) - Plackett-Luce EDA (PLEDA) • 50 instances of sizes: {10, 20, 30, 40, 50, 60, 70, 80, 90, 100} • Average Relative Percentage Deviation (ARPD) of 20 repetitions • Stopping criterion: 100n-1 generations 29 Experiments Results ARPD ARPD results of 20 repetitions of the EDAs for the LOP instances 0.05 MaEDA PLEDA 0.04 0.03 0.02 0.01 0 10 20 30 40 50 60 70 Instance Size 80 90 100 30 Discussion Which is the most efficient model to optimize the LOP ? 31 Discussion Theoretically, the Boltzmann distribution associated to the LOP Boltzmann constant 32 Discussion Calculate from the Boltzmann distribution associated to the LOP: • the Mallows model under the Ulam distance • the Plackett-Luce model Learn from a sample of 106 permutations Perform a weighted computation of the parameters 4 instances of size n=7 Boltzmann constant c: [0,300] Kullback-Leibler divergence: 33 Probability concentrates in the fittest solutions Discussion Near uniform distribution 34 Conclusions • For small instances, MaEDA and PLEDA obtain similar results. • For large instances, MaEDA is the preferred algorithm. • With respect to the Boltzmann distribution of the LOP: – When the fitness of the solutions is very different, the Mallows model under the Ulam distance is the preferred option. – When the fitness of the solutions is similar, the Plackett-Luce is more accurate. 35 Future work Compare Mallows EDA under the Ulam distance with state-of-the-art algorithms 36 Future work Study the properties of the Boltzmann distribution on the LOP 37 A comparison of estimation of distribution algorithms for the linear ordering problem Josu Ceberio Alexander Mendiburu Jose A. Lozano X Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados - MAEB2015