Métaheuristiques pour l'optimisation multi-objectifsspanjaard/pmwiki/uploads/madmc4_versionImprimable.pdfRappel MetaH Rappel optimisation MO MetaH pour l’optimisation MO Applications

Rappel MetaH Rappel optimisation MO MetaH pour l’optimisation MO Applications to academic problems

Métaheuristiques pour l’optimisationmulti-objectifs

Thibaut Lust

M2 ANDROIDE - MADMC - 2018

1 T. Lust MétaH pour l’OMO


Métaheuristiques

Le mot Métaheuristique est dérivé de la composition de deuxmots grecs :I Meta : qui est un suffixe signifiant “au-delà”, “dans un

niveau supérieur”I Heuristique : qui vient du verbe “heuriskein” et qui signifie

“trouver”Plusieurs définitions ont été proposées pour expliquerclairement ce qu’est une métaheuristique.Aucune de ces définitions n’est universellement reconnue.



I I.H. Osman and G. Laporte, Metaheuristics : a bibliography. Annals ofOperations Research 63, 513-623, 1996 :“A metaheuristic is formally defined as an iterative generation processwhich guides a subordinate heuristic by combining intelligently differentconcepts for exploring and exploiting the search space, learningstrategies are used to structure information in order to find efficientlynear-optimal solutions.”

I S. Voß, S. Martello, I.H. Osman and C. Roucairol (Eds), Meta-Heuristics- Advances and Trends in Local Search Paradigms for Optimization.Kluwer Academic Publishers, Dordrecht, The Netherlands, (1999)“A metaheuristic is an iterative master process that guides and modifiesthe operations of subordinate heuristics to efficiently producehigh-quality solutions. It may manipulate a complete (or incomplete)single solution or a collection of solutions at each iteration. Thesubordinate heuristics may be high (or low) level procedures, or asimple local search, or just a constructive method’.’



I T. Stützle, Local Search Algorithms for Combinatorial Problems -Analysis, Algorithms and New Applications. DISKI - Dissertationen zurKünstliken Intelligenz. Infix, Sankt Augustin, Germany (1999)”Metaheuristics are typically high level strategies which guide anunderlying more problem specific heuristic, to increase theirperformance. The main goal is to avoid the disadvantages of iterativeimprovement and, in particular, multiple descent by allowing the localsearch to escape from local optima. This is achieved by either allowingworsening moves or generating new starting solutions for the localsearch in a more “intelligent” way than just providing random initialsolutions.“

I Metaheuristics Network Website http ://www.metaheuristics.net”A metaheurisic is a set of concepts that can be used to define heuristicmethods that can be applied to a wide set of different problems. In otherwords, a metaheuristic can be seen as a general algorithmic frameworkwhich can be applied to different optimization problems with relativelyfew modifications to make them adapted to a specific problem.”



Propriétés fondamentales des métaheuristiquesI Stratégies qui permettent de guider la recherche d’une solution optimaleI Explorer l’espace de recherche efficacementI Les techniques qui vont de la simple procédure de recherche locale à

des processus d’apprentissage complexesI En général non-déterministes et ne donnent aucune garantie

d’optimalitéI Peuvent contenir des mécanismes qui permettent d’éviter d’être bloqué

dans des régions de l’espace de rechercheI Peuvent être décrites de manière abstraite, sans faire appel à un

problème spécifiqueI Peuvent faire appel à des heuristiques qui tiennent compte de la

spécificité du problème traité, mais contrôlées par une stratégie deniveau supérieur

I Peuvent faire usage de l’expérience accumulée durant la recherche del’optimum, pour mieux guider la suite du processus de recherche



Métaheuristiques à solution unique

I Recherche locale, algorithmes de descenteI Recuit Simulé (Simulated Annealing) (Kirkpatrick et al,

1983)I Recherche Tabou (Tabu search) (Glover, 1986)



Voisinage d’une solutionI S : ensemble de solutions (espace de recherche)I f : S → R : fonction objectif à optimiserI N (s) : ensemble des voisins d’une solution s



Recherche locale (LS)

3 ingrédients indispensables :I S : ensemble de solutions (espace de recherche)I f : S → R : fonction objectif à optimiserI N (s) : ensemble des voisins d’une solution s

Algorithme d’une recherche locale

Choisir solution initiale s ∈ Srépéter

choisir s′ ∈ N (s)s ← s′

jusqu’à critère d’arrêt vérifié



Méthode de descente - best improvement

Hill-climbing - best improvement (minimisation)


choisir s′ ∈ N (s) telle que f (s′) est minimalesi f (s′) ≤ f (s) alors

s ← s′

jusqu’à s minimum local (i.e. f (s′) > f (s))



Méthode de descente - first improvement

Hill-climbing - first improvement (minimisation)


choisir s′ ∈ N (s) aléatoirementsi f (s′) ≤ f (s) alors

s ← s′

fin sijusqu’à s minimum local OU nbr d’iter. ≤ maxNbrIter



Méthode de descente - Inconvénients



Autre méthode de recherche locale

Recherche locale aléatoire - Random Walk


choisir s′ ∈ N (s) aléatoirements ← s′

jusqu’à s minimum local OU nbr d’iter. ≤ maxNbrIter



Recherche locale : random walk / hill-climbing

Random walk

Maximal exploration,diversification

Hill-climbing

Maximal exploitation,intensification

Enjeu principal : compromis exploration/exploitationS’échapper d’optimum local⇒ recuit simulé, recherche tabou.



Recuit Simulé (Simulated Annealing)

Utilisé depuis les années 80 :

I Metropolis (1953) simulation du refroidissement dematériaux (thermodynamique)

I Kirkpatrick (1983) utilisation pour la résolution deproblèmes d’optimisation

But : échapper aux optima locauxPrincipe : probabilité non nulle de sélection d’une solutionvoisine dégradée



Recuit Simulé : analogieSystème physique Problème d’optimisation

Energie Fonction objectifEtats du système Solution

Etats de basse énergie Bonne solutionTempérature Paramètre de contrôle



Recuit simulé

Choisir solution initiale s ∈ S et température initiale Trépéter

Choisir aléatoirement s′ ∈ N (s), ∆ = f (s′)− f (s)Si ∆ < 0 alors

s ← s′

sinonu nombre aléatoire de [0,1]

si u < e−∆T alors

s ← s′

fin sifin siMise à jour de la température

jusqu’à Critère d’arrêt vérifié



Recuit simulé : remarques

Si ∆ > 0 alors la probabilité e−∆T est proche de 0 lorsque :

I la différence |∆ = f (s′)− f (s)| est grandeI la température est petite

Conséquences :

I Lorsque la température est grande (début de recherche) :→ recherche aléatoire

I Lorsque la température est petite (fin de la recherche) :→descente



Recuit simulé : température initiale

Evaluer ∆0 = f (s′0)− f (s0) :

I Choisir n (grand si possible) solutions aléatoires initiales s0et une solution voisine s′0

I Calculer la moyenne de ∆0 sur l’échantillon

Température initiale T0 telle que p0 = e−∆0

T0 désiré :

I Qualité “médiocre” (p0 = 0.5) : démarrage à hautetempérature

I Qualité “bonne” (p0 = 0.2) : démarrage à bassetempérature



Recuit simulé : décroissance de température

Décroissance suivant une loi géométrique Tk+1 = αTk suivant0.8 ≤ α < 1.0Changement par pallier de température suivant l’une des deuxconditions (par exemple) :

I 10*N perturbations acceptées (mouvement de solution)I 100*N perturbations tentées (mouvement ou non

mouvement)

où N est un paramètre qui décrit la taille du problème (nombrede villes, de variables, etc.)Critère d’arrêt : Par exemple après 3 palliers successifs sansaucune acceptation.



Recherche Tabou (Tabu search)Introduite par Glover en 1986 :

F. GloverFuture paths for Integer Programming and Links to ArtificialIntelligence.Computers and Operations Research, (5) :533-549, 1986.

But : Echapper aux optima locauxPrincipe : Introduction d’une notion de mémoire dans lastratégie d’exploration

Interdiction de reprendre des solutions déjà (ou récemment)rencontrées



Recherche tabou

Choisir solution initiale s ∈ SInitialiser la liste Tabou Mrépéter

Choisir s′ ∈ N (s) telle que :f (s′) meilleure solution de N (s) ET critère d’aspiration

vérifiéOU f (s′) meilleure solution de N (s) non taboue

s ← s′

Mise à la jour de la liste tabou Mjusqu’à Critère d’arrêt vérifié



Recherche tabou : mémoire des tabousLes tabous sont des mouvements tabous pendant une durée t(longueur de la liste tabou) :

ExempleProblème du sac à dos avec n = 10M = (0,3,0,0,0,0,0,0,0,0)→ Le deuxième objet ne peut être modifié pendant 3 itérations.M = (0,2,0,0,3,0,0,0,0,0)→ Le cinquième objet ne peut être modifié pendant 3 itérations.Etc.

Lorsqu’un mouvement est effectué : interdiction pendant titérations.BSi t est trop faible, tabou peu efficace, si t trop grand, troppeu de voisins admissibles.



Recherche tabou : critère d’aspiration

Permet de lever l’interdiction lorsqu’un mouvement interditpermet d’obtenir la meilleure solution enregistrée jusqu’àmaintenant.

ExempleProblème du sac à dos avec n = 10M = (0,2,0,0,3,0,0,0,0,0)→ Si un mouvement sur le deuxième objet permet d’améliorerla meilleure solution, le mouvement peut être réalisé.



Autres méthodes de recherche locale

I Greedy randomized adaptive search procedure (GRASP)(construction qui combine les méthodes gloutonnes etaléatoires)

I Variable neighborhood search (VNS) (changement devoisinage lorsque l’on tombe dans un minimum local)

I Very large-scale neighborhood search (utilisationd’heuristique/méthode exacte pour l’exploration duvoisinage)

I Etc.



Méthode à population de solutions

I Parfois appelées méthodes évolutives : font évoluer unepopulation de solutions selon des règles bien précises

I Alternance de périodes d’adaptation individuelle et depériodes de coopération pendant lesquelles les individuspeuvent échanger de l’information



Méthode évolutive

Générer une population initiale d’individusTant que aucun critère d’arrêt n’est satisfait faire

Exécuter une procédure de coopérationExécuter une procédure d’adaptation individuelle

Fin du tant que



Principales caractéristiques

I Types d’individus (individus 6= solutions)I Type d’évolution (survie de la population) : remplacement

générationnel ou remplacement stationnaireI Sources d’information : à partir de quelle information les

nouveaux individus sont générésI Intensification : adaptation individuelleI Diversification : bruitage appliqué sur chacun des individus



Algorithmes génétiquesJ. HollandAdaptation In Natural And Artificial Systems.Adaptation In Natural And Artificial Systems, University ofMichigan Press (1975).

Générer une population initiale P0 de p individusi = 0Tant que aucun critère d’arrêt n’est satisfait fairei = i + 1Pi = ∅

Répéter p foisCréer un enfant E en croisant I1 et I2 de Pi−1Appliquer l’opérateur de mutation à ERajouter l’enfant modifiée à Pi

Fin du tant que



I Types d’individus : en général les solutionsI Type d’évolution : remplacement générationnel avec une

population de taille constanteI Sources d’information : deux parentsI Intensification : aucuneI Diversification : mutation



Autres méthodes à population de solutions

I Colonies de fourmisI Recherche dispersée (Scatter search)I Méthodes à essaims particulaires (Particle swarm

optimization)I Etc.



Théorème “no-free-lunch”I Méthode d’optimisation universelle n’existe pas. La seule

façon qu’une stratégie soit meilleure qu’une autre c’est dela spécialiser à la structure du problème considéré.

I Aucune métataheuristique ne bat tous les autresmétaheuristiques sur tous les problèmes

D.H. Wolpert and W.G. MacreadyNo Free Lunch Theorems for Optimization.IEEE Transactions on Evolutionary Computation, (1) :67,1997.

Y.C. Ho and D.L. PepyneSimple Explanation of the No-Free-Lunch Theorem and ItsImplications.Journal of Optimization Theory and Applications, 115 :549,2002.



Mathematical Formulation

min f (x)

subject to g(x) ≤ 0x ∈ Rn

x ∈ Rn → n variables, i = 1, . . . ,ng : Rn → Rm → m constraints, j = 1 . . . ,mf : Rn → Rp → p objective functions, k = 1 . . . p



Feasible Sets

I X = {x ∈ Rn : g(x) ≤ 0} :feasible set in decision space

I Y = f (X ) = {f (x) : x ∈ X} :feasible set in objectivespace



Pareto optimalityLet y1 and y2 ∈ Rp :

1. Weak component-wise order : y1 ≤ y2 ⇔ y1k ≤ y2

k fork = 1, . . . ,p

2. Component-wise order : y1 ≺ y2 ⇔ y1k ≤ y2

k fork = 1, . . . ,p and y1 6= y2

3. Strict component-wise order : y1 < y2 ⇔ y1k < y2

k fork = 1, . . . ,p

In multiobjective optimization (x : feasible solution, f (x) :evaluation) :

1. if f (x) ≤ f (x ′) : f (x) weakly Pareto dominates f (x ′)2. if f (x) ≺ f (x ′) : f (x) Pareto dominates f (x ′)3. if f (x) < f (x ′) : f (x) strictly Pareto dominates f (x ′)

f (x) < f (x ′)⇒ f (x) ≺ f (x ′)⇒ f (x) ≤ f (x ′)

≤,≺, < are not a total order



Example

6

-

a

b

c

d

z1

z2

I a < d ⇒ a ≺ d ⇒ a ≤ dI a ≺ b ⇒ a ≤ bI a ≺ c ⇒ a ≤ cI b ≺ d ⇒ b ≤ dI c ≺ d ⇒ c ≤ dI b||c → In multiobjective optimization : solutions cannot always

be compared.39 T. Lust MétaH pour l’OMO


Example

min f1(x1, x2, x3, x4) = 3x1 + 2x2 − 4x3 + x4

min f2(x1, x2, x3, x4) = x1 − 3x2 + 4x3 − 2x4

min f3(x1, x2, x3, x4) = −x1 + x2 + 3x3 + x4

(n = 4,p = 3)I X = {x1 = (2,1,3,1), x2 = (−2

9 ,−44

9 , 89 ,10), x3 =

(1,2,2,2), x4 = (172 ,

92 ,4,1), x5 = (3,−10,2,16)} :

arbitrary feasible set in decision spaceI Y = f (X ) = {f (x1), f (x2), f (x3), f (x4), f (x5)} ={(−3,9,9), (−4,−2,−8), (1,−1,9), (39

2 ,9,9), (−3,9,9)} :feasible set in objective space

What can you say aboutf (x1), f (x2), f (x3), f (x4), f (x5) (≤,≺, <, ||) ?



Weakly Efficient Solutions

I Weakly Efficient SolutionsXwEI There is no x with

f (x) < f (x̂)I f (x̂) is weakly dominatedI YwN := f (XwE )



Efficient Solutions

I Efficient Solutions XEI There is no x with

f (x) ≺ f (x̂)I f (x̂) is non-dominatedI YN := f (XE )→ Pareto

front.



Lexicographic Optimality

lexminx∈X

(f1(x), . . . , fp(x)

)I Let y1 and y2 ∈ Rp :

Lexicographic order : y1 <lex y2 if y1q < y2

q whereq = min{k : y1

k 6= y2k }

I Lexicographic optimal solution :A feasible solution x̂ ∈ X is lexicographically optimal or alexicographic solution if there is no x ∈ X such thatf (x) <lex f (x̂).

I The relation <lex is a total preorder - all solutions can becompared, ex-aequo are possible.



Examples

I Example 1 :I f (x) = (f1(x), f2(x), f3(x))I Y = f (X ) = {f (x1), f (x2), f (x3), f (x4)} ={(−3,10,10), (−3,11,11), (−3,10,12), (−2,8,7)}

I x1 is lexicographically optimalI Example 2 :

I f (x) = (f3(x), f1(x), f2(x))I Y = f (X ) = {f (x1), f (x2), f (x3), f (x4)} ={(10,10,−3), (11,11,−3), (12,10,−3), (7,8,−2)}

I x4 is lexicographically optimal



Ideal and Nadir Points

I Ideal point y I

y Ik = min{yk : y ∈ Y}

I Nadir point yN

yNk = max{yk : Y ∈ YN}

I Anti-Ideal point yAI

yAIk = max{yk : y ∈ Y}

I Utopian point yU

yUk = y I

k − εk



Bounds

For any y ∈ YN , we have :I y I

k ≤ yk

I yk ≤ yNk

y I and yN are tight lower and upper bounds on the efficient set.



Multiobjective Combinatorial Optimization Problems(MOCO problems)

“minx

” f (x) = Cx

subject to {x : Ax ≤ b}x ∈ {0,1}n

x ∈ {0,1}n −→ n variables, i = 1, . . . ,nC ∈ Zp×n −→ p objective functions, k = 1, . . . ,pA ∈ Zm×n −→ m constraints, j = 1, . . . ,m

Combinatorial structure : path, trees, flow, tour, etc.



Feasible Sets

I X = {x ∈ {0,1}n : Ax ≤ b} :feasible set in the decisionspace

I Y = f (X ) = {Cx : x ∈ X} :feasible set in the objectivespace

6

-f1

f2 c

c

cc

c

c

c

c

ccccccc



Example : Assignment Problem

min fk (x) =n∑

i=1

n∑j=1

ckij xij k = 1, . . . ,p

subject ton∑

i=1

xij = 1 j = 1, . . . ,n

n∑j=1

xij = 1 i = 1, . . . ,n

xij ∈ {0,1} i , j = 1, . . . ,nExample :

C1 := (c1ij ) =

5 1 4 76 2 2 62 8 4 43 5 7 1

C2 := (c2ij ) =

3 6 4 21 3 8 35 2 2 34 2 3 5



Assignment Problem



Weakly Efficient Set

I Weakly efficient solution x ∈ X : afeasible solution x∗ ∈ X is calledweakly efficient if there does notexist any other feasible solutionx ∈ X such as f (x) < f (x∗).I XwE ∈ X : set of weakly efficient

solutions (weakly efficient set).I YwN := f (XwE )(∈ Y ) : set of

weakly non-dominated points.

6

-f1

f2 ss s ss s ss s s

c cccc



Efficient Set

I Efficient solution : a feasiblesolution x∗ ∈ X is called efficientif there does not exist any otherfeasible solution x ∈ X such asf (x) ≺ f (x∗).I XE ∈ X : set of efficient

solutions (efficient set).I YN := f (XE )(∈ Y ) (Pareto front,

set of non-dominated points).

6

-f1

f2 s s ss s s s

c

cc

c cccc



Efficient Set

6

-f1

f2 s s ss s s s

c

cc

c cccc

In general, in combinatorial multiobjective optimization, we tryto generate the efficient set.54 T. Lust MétaH pour l’OMO


Classification of efficient sets

Hansen 1979 :I x1, x2 ∈ XE are equivalent if f (x1) = f (x2)

I Complete set : X̂ ⊂ XE such that for all y ∈ YN there isx ∈ X̂ with f (x) = y

I Minimal complete set (or reduced efficient set) contains noequivalent solutions

I Maximal complete set contains all equivalent solutions (=efficient set)

→ Efficient set is unique, but the reduced efficient set is not.



Supported - Non-supported efficient solutions

I Supported efficient solutionsXSE : There is λ > 0 withλT Cx̂ ≤ λT Cx for all x ∈ X .I Cx̂ is extreme point of conv(Y )

+ Rp≥ → XSE1

I Cx̂ is in the relative interior ofthe faces of conv(Y ) +Rp

≥ → XSE2

I Non-supported efficient solutionsXNE : Cx̂ is in the interior ofconv(Y ) + Rp

≥

6

-f1

f2 c

c

cc

c

c

c

c

ccccccc

s s sss

λ = (56 ,

16)

λ = (12 ,

12)

λ = (13 ,

23)

λ = (23 ,

13) s s



Non-supported Efficient Solutions



Number of Efficient Solutions

Empirically often :I |XSE | (supported) grows polynomially with instance sizeI |XNE | (non-supported) grows exponentially with instance

size



Summary

6

-x1

x2

z1

z26

-

xa

xc

xexd

xb

xf

xgxh

xi xjxk

->1

z

j-: 1

c

::1

c cc ccc

c c

Decision Space Objective Space

I XwE = {xa, xb, xc , xd , xe, xf , xg , xh, xi , xj , xk} (Weakly Efficient Set)I XE ={xc , xd , xe, xf , xg , xi , xj} (Efficient Set)I XSE = {xc , xd , xe, xf , xj} (Supported Efficient Solutions Set)I XSE1 = {xc , xe, xf , xj} (Extreme Supported Efficient Solutions Set)I XSE2 = {xd} (Non-Extreme Supported Efficient Solutions Set)I XNE = {xg , xi} (Non-Supported Efficient Set)I A minimal complete set= {xc , xd , xe, xg , xi , xj}.



Solving a multiobjective combinatorial optimizationproblem

Three approaches :I A posteriori approach : generation of the Pareto optimal setI A priori approach : elicitation and optimization of an

aggregation function (weighted sum, weighted Tchebycheffnorm, ordered weighted average, Choquet integral, etc.)→single-objective optimization

I Interactive approach : dynamic elicitation of an aggregationfunction according to the preferences expressed by thedecision maker



Why is it difficult to generate the Pareto optimal set1. Supported and non-supported efficient solutions

minx∈D

p∑k=1

λk fk (x)

6

-f1

f2 c

c

cc

c

c

c

c

ccccccc

s s sss

λ = (56 ,

16)

λ = (12 ,

12)

λ = (13 ,

23)

λ = (23 ,

13) s s



Why is it difficult to solve a MOCO problem?2. For many MOCO problems, the number of supported efficientsolutions grows polynomially with instance size while the number ofnon-supported efficient solutions grows exponentially with instancesize



Why is it difficult to solve a MOCO problem?

3. NP-Hardness

Combinatorial Problem p = 1 p ≥ 2Shortest path Polynomial NP-HardMinimum spanning tree Polynomial NP-HardAssignment Polynomial NP-HardMinimal cut s-t Polynomial NP-HardKnapsack NP-Hard NP-HardTraveling salesman NP-Hard NP-Hard

4. Intractability

Most of the standard MOCO problems have been proved to beintractable, that is the number of non-dominated points can beexponential in the size of the instance



Why is it difficult to solve a MOCO problem?5. Many non-dominated points (knapsack instance, 3 crit, 250 items)



Methods

I Exact methods (two-phase method, ε-constraint, branchand bound, . . . ) : work only for small size multiobjectiveproblems (1000 items for a biobjective knapsack, 100items for a three-objective knapsack)

I Approximation algorithms : fewI Metaheuristics : quite a lot, adapted since 1984



Metaheuristics for solving MOCO problems

I Many papers present the adaptation of metaheuristics tomultiobjective problems

I The majority of the developed methods follows the idea ofone (hybrid) metaheuristic

I But all metaheuristics for MOCO problems use apopulation P to store the non-dominated solutions (with thenon-dominated property : ∀p1,p2 ∈ P,p1 ⊀ p2 ∧ p2 ⊀ p1)

I Search space : same as in the single-objective problem



Updating the potentially efficient set (Update)

IN ↓ : x (solution)IN-OUT l : X̂E (set of potentially efficient solutions)OUT ↑ : Booleanif (@ x ′ ∈ X̂E | x ′ � x) thenX̂E ← X̂E ∪ {x}for all (x ′ ∈ X̂E | x ≺ x ′) doX̂E ← X̂E \ {x ′}

end forReturn True

elseReturn False

end if



How to update efficiently the efficient set?

Let a set of m potentially non-dominated points :

y11 y12 y13 . . . y1py21 y22 y23 . . . y2p. . . . . . . . . . . . . . .ym1 ym2 ym3 . . . ymp

We want to check if ym+1 is a new non-dominated point and toupdate the set.

How can you do that efficiently for p = 2?



Aim of a metaheuristic for solving MOCO problems

To find a good approximation of a Pareto set = set of feasiblesolutionsBut what is a good approximation?I ψ : consists of all potential Pareto sets approximations (set

of sets)I An appropriate order on ψ is required to specify when an

approximation is better than an another.



Set preference relations : what we can saystrictly dominates A ≺≺ B every b ∈ B is strictly dominated by at least a ∈ A

dominates A ≺ B every b ∈ B is dominated by at least a ∈ A

better A / B every b ∈ B is weakly dominated by at least a ∈ A and A 6= B

weakly dominates A � B every b ∈ B is weakly dominated by at least a ∈ A

incomparable A||B neither A weakly dominates B nor B weakly dominates A

6

-z1

z2

ss

s

s

sss



Some quality indicators generally used (unary)z2

z1

rrr r r

-

H

SM

bR

D1

D2

6

r r r r

b

�

�

>=

jY

U

K r



Problem with unary quality indicators (Zitzler et al.,2003)

Considering :I Combinatorial multiobjective problem with p ≥ 2I A and B two approximation setsI A finite combination I of unary indicatorsI A comparison method C based on I and an interpretation

function E , CI,E (A,B) = E(I(A), I(B)).Then, there is no comparison method based on a finitecombination of unary quality indicators such that :

CI,E ⇔ A / B

Example (H indicator)A / B ⇒ H(A) < H(B) but we cannot say :H(A) < H(B)⇒ A / B.



Example (Lizarraga et al., 2008)



Multiobjective Neighborhood Search Algorithms

Multiobjective Simulated Annealing

I Initial solution

I Neighbourhod structure

I Scalarizing function s(z(x), λ)

I Set of weights (directions) λ

I Simulated Annealing based on s

I Merge sets of solutions

Multiobjective Tabu Search

I Initial solution

I Neighbourhod structure

I Scalarizing function s(z(x), λ)

I Set of weights (directions) λ

I Tabu Search based on s

I Merge sets of solutions



Multiobjective caseHow to choose a solution of minimal cost?

min z2 6

-min z1

u X

uu

u uu

N (x)

�

If only one criterion

If two (or more) criteria?

I Selection of the solution by using different rules(dominance relation, density, . . .)

I Selection of all the non-dominated solutions77 T. Lust MétaH pour l’OMO


Example : Pareto Ranking Tabu Search + Density(PRTS+D)

I Based on Tabu SearchI Selection of the neighbor based on dominance relation and

density



Neighbor Selection of PRTS+D

Best neighbor selection inspired by the individuals selection ofa genetic algorithm (PFGA)[Elaoud et al., 2005], which uses :I A rank for each individual, calculated thanks to the strong

dominance relationI A density, calculated starting from a division of the

objectives space in hypervolumes



The Double Pareto Ranking DPR

PR ,DPR6

-

max z2(x)

max z1(x)

ssss

6

6

-

-

0

0

6

-2

6

-3,5

,2

,0

,0



The individuals density measure

6

-

z2(x)

z1(x)

s ss

s

ss s

ss

ss

ss

s4

3

1

2

1

1

1

1



Use of DPR and D in a Tabu method

⇒ Neighbors selection :

I Population considered for the calculation of DPR and thedensity D : L neighbors generated at each iteration +potentially efficient solutions

I The selected neighbor is the one that presents a maximumevaluation for the following function :

f (i) =1

eDPR(i) × D(i)



Functioning of PRTS+D

6

-

z2(x)

z1(x)

: N(X): X

: PEaaa aa a a

�

a aa aa

a

ay1

y2

y3

06

0

,1

,6,3

�

Y*� XaaIteration iGenerate L neighbors Yl in N(X)Create hp hypervolumesFor each neighbor Yl :

Calculate the rank DPRCalculate the density D

Select the best neighbor Y∗ ( 1eDPR(Yl )×D(Yl )

)

Give to the movement Y∗ → X the Tabu statuteX ← Y∗For each neighbor Yl , if DPR(Yl ) = 0 then

PE ← PE +{Yl}Actualize PE



Hybrid Algorithm : MEMOX Scheme

Initialization phase : we apply a local search method or aheuristic X to produce at least r + 1 non-dominated solutions.

6

-

z2(x)

z1(x)

: PE

a a a a a a a a a a a a a a a

aX1*

X2*X3qX3q

Iteration iChoose a solution X1 among PE of minimaldensityChoose a solution X2 among the r closestsolutions of X1Cross the two solutions X1 and X2 → X3If X3 does not respect the constraints, applicationof a repair procedureApply a local search method from X3, stop if nomore improvement while itstop



Pareto Local Search (PLS) (Paquete, 2004) : Selection of all the

non-dominated solutionsExploration of the neighborhood of each potentially efficient solutiongenerated until all the neighborhoods of all the potentially efficient solutionsare explored.

-

6

min z1

min z2

ffffff

f fff f

ffff

ffff



Pareto local search

Parameters ↓ : an initial population P0, a neighborhood functionN (x).Parameters ↑ : an approximation X̃E of the efficient set XE .

- -| Initialization of X̃E and a population P with the initial population P0X̃E ← P0P ← P0- -| Initialization of an auxiliary population PaPa ← ∅while P 6= ∅ do

- -| Generation of all neighbors p′ of each solution p ∈ Pfor all p ∈ P do

for all p′ ∈ N (p) doif f (p) � f (p′) then

if Update(X̃E l, p′ ↓) thenUpdate(Pa l, p′ ↓)

end ifend if

end forend for- -| P is composed of the new potentially efficient solutionsP ← Pa- -| Reinitialization of PaPa ← ∅

end while



Multiobjective genetic algorithmParameters ↓ : an initial population P0, a procedure SP1(P) of selection of the first parent, a procedure SP2(P)of selection of the second parent, a crossover operator CO(x1, x2), a mutation operator M(x), the number nP′ ofreproduction, a selection procedure S(P).Parameters ↑ : an approximation X̃E of the efficient set XE .

- -| Initialization of the population PP ← P0- -| Initialization of X̃Efor all x i ∈ P do

AddSolution(X̃E l, x i ↓)end forrepeat

- -| Generation of a new population P′ from P and X̃EP′ ← ∅for i = 1 to nP′ do

x1 ← SP1({P ∪ X̃E})

x2 ← SP2({P ∪ X̃E})

x3 ← CO(x1, x2)

AddSolution(X̃E l, x3 ↓)

x4 ← M(x3)

AddSolution(X̃E l, x4 ↓)

P′ ← P′ + {x4}end for- -| Selection between {P ∪ P′ ∪ X̃E} to update the population PP ← S({P ∪ P′ ∪ X̃E})

until stopping criterion met



NSGA-II (most popular MOGA)I Developed by Deb et al. in 2002

K. Deb, A. Pratap, S. Agarwal and T. MeyarivanA Fast and Elitist Multiobjective Genetic Algorithm :NSGA-II.IEEE Transactions on Evolutionary Computation,6(2) :182-197, 2002.

Cited 25718 times ! (October 2018)I Fitness based on the Goldberg rankI No elitism in the selectionI The elitist population is used in the selectionI A diversity measure is introduced with the notion of

crowding : the value of the perimeter of the hypercubehaving as vertices the points the closest to the individualfor each objective.



Goldberg rank

6

-f1

f2

uu

uuu

uuuu uFront 1

uuFront 2

uuuu

uFront 3



Crowding distance



Two-Phase Pareto local search

AimTo speed-up the Pareto local search (very time-consuming ifstarts from one single solution)

1. Phase 1 : Find a good approximation of the supportedefficient solutions→ a solver for solving the correspondingsingle-objective problems

2. Phase 2 : Find a good approximation of the non-supportedefficient solutions→ a neighborhood (allowing to connectthe potentially supported efficient solutions)

→ No numerical parameters have to be tuned→ Natural stopping criterion



Phase 1 : Supported Efficient SolutionsI Generation of an approximation of the extremal supported efficient solutions

6

-z1

z2

s s

s s

cc

c c cccc

s

ss

s

ss

I Dichotomic scheme : method that allows to generate the weight setsI Single-objective problems obtained are solved with a heuristic



Aneja and Nair Procedureλ = (1,0)

z1

z2

z(xr )

λ = (0,1)z(xs)

λ = (z2(xr )− z2(xs), z1(xs)− z1(xr ))

z(xt )



Stopping criterion of the Aneja and Nair procedurez(xt )

z(xs)

λ = (z2(xt )− z2(xs), z1(xs)− z1(xt ))

We stop when a point is outside the triangle and does notdominated any other points.



Phase 2 : Finding non-supported efficient solutionsI Pareto Local Search (PLS) :

z1

z2

� ��

� ��



Pareto Local Search (TSP, 2 Obj, 100 cities, 1 Rd)



Pareto Local Search (TSP, 2 Obj, 100 cities, 10 WS)









Multiobjective Traveling Salesman Problem

(c1, c2, . . . , cp)

d d

ddd

dd

dd

ddd

dd

d

d

“ min ”zk (π) =N−1∑i=1

ck (vπ(i), vπ(i+1)) + ck (vπ(N), vπ(1)) (k = 1, · · · ,p)

→We are interested here only in the symmetrical biobjectiveTSP (bTSP), i.e. ck (vi , vj) = ck (vj , vi) for 1 ≤ i , j ≤ N and p = 2.102 T. Lust MétaH pour l’OMO


Adaptation of 2PPLS

I Phase 1 : Dichotomic method coupled with theLin-Kernighan heuristic (clever implementation of localsearch with a combination of 2-opt and 3-opt moves)

I Phase 2 : PLS with with the 2-opt neighborhood



2-opt neighborhood









2-exchange neighborhood

t tttt

t �

t1 t2

t3 ?

t1 t2

t3

t tttt

t

t4

⇒ List of k-nearest neighbors for each city (with a small valuefor k )



Neighbor list

I One criterion : one list for each city according to the uniquecost. The size of the neighbor list is limited to k .

I Two criteria : two lists for each city. One list for the cost 1and the other for the cost 2. The size of the neighbor list isequal to k ∗ 2.



k-nearest neighbors



Results





D-Dominance

I Used of the non-dominated edges (D = 0)I Used of the non-dominated edges after removing the

preceding edges (D = 1)I Etc.



D-Dominance





Results





Results





Multiobjective Multidimensional Knapsack Problem (MOMKP)

Profit1 : p1 (French)Profit2 : p2 (Belgian)Volume : w1Weight : w2

“ max ” fk (x) =n∑

i=1

c ik xi k = 1, . . . ,p

subject ton∑

i=1

w ij xi ≤Wj j = 1, . . . ,m

xi ∈ {0,1} i = 1, . . . ,n



Example of non-dominated points for the MOMKP



MOKP and MOMKP

MOMKP

“ max ” fk (x) =

n∑i=1

c ik xi k = 1, . . . , p

s.t.n∑

i=1

w ij xi ≤ Wj j = 1, . . . ,m (m = 1→ MOKP)

xi ∈ {0, 1} i = 1, . . . , n

Recall KP (p=1 ; m=1) Martello-Toth (1990) ; Kellerer-Pferschy-Pisinger (2004)

I Efficiency of object i : ci

w i → Order ci

w i ↘

I Split (critical) object : s |∑s−1

i=1 w i ≤ W <∑s

i=1 w i → Optimal solution of LKPI Core : C = {i | n1 ≤ i ≤ n2} with n1 < s < n2

I Difficulty of the instances :I Correlation between (c i ,w i ), i = 1, . . . , n

I W = 12

n∑i=1

w i



Very large-scale neighborhood search (VLSNS)Local search algorithm which makes use of a neighborhood, which islarge and possibly exponentially-sized (Ahuja et al., 2000).

Larger⇒

Better quality⇔ Higher running time

⇒ Needs an efficient method to explore the neighborhood andto select the best move(s) among all the possible moves.

VLSNS also knows under :I Dynasearch (dynamic programming)I Variable depth search (heuristics)I In the CP community : Large Neighborhood Search

→ One of the best-known VLSNS heuristic : the Lin-Kernighanheuristic→ Very few studies in MO124 T. Lust MétaH pour l’OMO


Adaptation of 2PPLSI Initial population : simple greedy algorithm applied with

different weight sets

p∑k=1

λkcsk

m∑j=1

(ws

j

Wj −∑n

i=1 w ij xi + 1

)

I Neighborhood in PLS : VLSNSI Subset of variables is selectedI The generation of the neighbors is done by applying a

subroutine that allows to solve efficiently thesubproblem induced by the selected variables.



VLSNS for the MOMKPI Two lists are created, both of size L : one list (L1) containing the items candidate

to be removed (xi = 1) (ratio

p∑k=1

λk csk

m∑j=1

wsj

) and another list (L2) containing the items

candidate to be added (xi = 0) (ratio

p∑k=1

λk csk

m∑j=1

(ws

j

Wj −∑n

i=1 wsj xi + 1

) ).

L1 L21 1 1 1 1 1 1 0 0 0 0 0 0 0

L1 L20 0 0 0 0 0 0 0 0 0 0 0 0 0

W Newj = Wj −

n∑i=1i /∈L1

w ij xi with j = 1, . . . ,m



VLSNS for the MOMKP

I The new problem is of small size and could be solved withan exact method

⇒ Multiobjective Branch and Bound



Multiobjective Branch and BoundDefinition of the upper bound (Florios et al., 2010) :If the evaluation of the partial solution + the evaluation of the idealpoint of the remaining items is dominated by the lower bound, thenode is fathomed.

6

-

f2

f1

tt t

t t t t t ttss



Pareto local search for many-objective optimizationproblems

Number of non-dominated solutions of the multi-objectivetraveling salesman problem :

nbCrit nbCities nbParetoOpt3 100 > 193 8184 50 > 2 547 317

⇒ Pareto dominance does not scale with the number ofobjectives



Many-objective optimization

I Need for new and better algorithms that can efficientlyhandle the growing number of objectives

I Reasonable computation time and memory usage

General solutions :I Bounded-size set : often based on a division of the

objective space into different regions (and only onesolution represents a region)

I Refinement of Pareto dominance with aggregationfunctions

I Interactive method (integration of the preferences of thedecision maker during the execution of the algorithm)


Documents

Métaheuristiques pour l'optimisation multi-objectifsspanjaard/pmwiki/uploads/madmc4_versionImprimable.pdfRappel MetaH Rappel optimisation MO MetaH pour l’optimisation MO Applications