Calcul de la d´ecomposition arborescente `a partir des coupes minimales

Télécharger le fichier pdf d’un mémoire de fin d’études

Le formalisme des WCSP

Soit les deux variables x1 et x2 de domaines Dx1 = Dx2 = {1, 2}, la contrainte x1 = x2 est satisfaite si x1 est aﬀect´ee `a la valeur 1 et x2 `a 2 (ou inversement).

Un tuple autoris´e est une aﬀectation de toutes les variables de la port´ee d’une contrainte cS satisfaisant celle-ci. Par opposition, un tuple interdit pour une contrainte cS correspond `a une aﬀectation des variables de S ne satisfaisant pas cS .

Les contraintes portant sur une seule variable sont dites unaires. Les variables portant sur deux variables, trois variables et n variables sont respectivement appel´ees binaires, ternaires et n-aires.

Le formalisme des WCSP

Nous pr´esentons dans cette section les d´efinitions de base. Nous pr´ecisons tout d’abord la notion de structure de valuations. Nous introduisons ensuite le cadre g´en´eral des VCSP. Enfin, nous d´efinissons les particularit´es des WCSP par rapport a` ce cadre.

Structure de valuations

Une structure de valuations permet de repr´esenter les coˆuts (ou valuations) des tuples des contraintes ainsi que la mani`ere de les agr´eger.

D´efinition 5 (Structure de valuations). Une structure de valuations, not´ee S, est repr´esent´ee par un quintuplet (E, ≻, ⊕, ⊥, ⊤), avec :

– E, l’ensemble des valuations associ´ees aux tuples des contraintes, avec ⊥ et ⊤ les valuations minimale et maximale,

– ≻, un op´erateur d’ordre total sur les valuations de E,

– ⊕, un op´erateur d’agr´egation des valuations poss´edant les propri´et´es suivantes :

– commutativit´e : ∀a, b ∈ E, a ⊕ b = b ⊕ a,

– monotonie : ∀a, b, c ∈ E, a c → (a ⊕ b) (c ⊕ b),

– un el´ement absorbant : ∀a ∈ E, a ⊕ ⊤ = ⊤,

– un el´ement neutre : ∀a ∈ E, a ⊕ ⊥ = a.

La commutativit´e de l’op´erateur d’agr´egation assure que l’ordre d’agr´egation des valuations ne modifie pas le r´esultat. De mˆeme, la monotonie garantit que l’ajout d’insatisfactions (la g´en´eration d’un coˆut par l’aﬀectation d’une variable) a` une solution ne peut am´eliorer la qualit´e de celle-ci. ⊤ repr´esente l’´el´ement absorbant qui repr´esente l’insatisfaction totale. A contrario, ⊥ repr´esente l’´el´ement neutre associ´e a` la satisfaction totale.

Le cadre g´en´eral des VCSP

Le formalisme des VCSP ´etend le formalisme des CSP en associant une valuation `a chaque tuple de chaque contrainte. Pour un tuple, sa valuation exprime le degr´e d’insatisfaction engendr´ lorsque les variables de la contrainte sont aﬀect´ees aux valeurs du tuple.

D´efinition 6 (VCSP). un VCSP est d´efini par un quadruplet (X, D, C, S), avec :

– X l’ensemble des variables,

– D leurs domaines finis associ´es,

– C un ensemble de contraintes valu´ees. Chaque contrainte valu´ee c est d´efinie par une application c de xi∈vars(c) Di dans E repr´esentant les valuations des tuples de la contrainte,

– S une structure de valuations.

D´efinition 7 ´

(Projection). Etant donn´ee une aﬀectation A et un ensemble de variables S ⊆ X, on note A[S] la projection des valeurs de A sur l’ensemble S.

D´efinition 8 (Valuation d’une aﬀectation compl`ete). La valuation d’une aﬀectation compl`ete A est ´egale a` l’agr´egation par l’op´erateur ⊕ des valuations des tuples des contraintes aﬀect´ees par A.

M V(A) = c(A[vars(c)])

Dans la suite de ce document, nous nommerons solution, une aﬀectation compl`ete dont la valuation est strictement inf´erieure a` ⊤. Une aﬀectation compl`ete est dite solution optimale si sa valuation est inf´erieure ou ´egale `a la valuation de toute aﬀectation compl`ete. Une contrainte c compl`etement aﬀect´ee pour une aﬀectation A, est dite satisfaite si c(A[vars(c)]) = ⊥ et viol´ee sinon.

Pour une contrainte cS , une aﬀectation des variables de S dont la valuation est ´egale a` ⊥ est un tuple autoris´e et interdit sinon.

D´efinition 9 (Tuple dur, tuple mou). Un tuple interdit dont la valuation est ´egale `a ⊤ est dit dur et mou sinon.

D´efinition 10 (Contrainte dure, contrainte molle). une contrainte dont tous les tuples interdits ont une valuation ´egale a` ⊤ est dite DURE ; dans le cas contraire la contrainte est dite MOLLE.

Par abus de langage, nous dirons qu’une contrainte a une valuation ´egale a` p lorsque tous ses tuples interdits ont une valuation de p.

Les WCSP

Le formalisme WCSP est une variante des VCSP dont l’objectif consiste `a trouver une aﬀectation compl`ete qui minimise des fonctions de coˆut.

D´efinition 11 (Structure de valuations d’un WCSP). La structure de valuations associ´ee a` un WCSP est un quintuplet S = (E+, ⊕, ≤, 0, ⊤) o`u E+ = [0 . . . ⊤] avec ⊤ ∈ N ∪ +∞ la valuation maximale associ´ee `a un tuple. ⊕ est une somme born´ee dans N : ∀a, b ∈ E+, a ⊕ b = min(a + b, ⊤)

D´efinition 12 (WCSP). Un WCSP est d´efini par un quadruplet (X, D, W, S) o`u :

– X = {x1, . . . , xn} est l’ensemble de variable du probl`eme,

– D = {D1, . . . , Dn} l’ensemble des domaines finis associ´es aux variables,

– W = {wS1 , . . . , wSe } l’ensemble des fonctions de coˆut,

– S une structure de valuation.

D´efinition 13 (Fonction de coˆut). Une fonction de coˆut wSi , d´efinie sur un ensemble Si ⊂ X appel´ port´ee, associe `a chaque aﬀectation des variables de sa port´ee un coˆut :

xYk i wSi : ( Dk) → E+ ∈S

On appelle arit´e de wSi la taille de sa port´ee (|Si|).

On associe au WCSP une fonction w∅ d’arit´e nulle. C’est une constante ajout´ee `a toute aﬀectation et sert de minorant utilis´e par DFBB (voir section 1.3.1).

L’objectif est de trouver une aﬀectation compl`ete A de coˆut f (A) minimal.

Un WCSP peut ˆetre repr´esent´ sous la forme d’un graphe non orient´.

D´efinition 15 (Graphe de contraintes d’un WCSP). Soit P = (X, D, W, S) un WCSP, le graphe

G = (V, E) associ´e `a P est d´efini par :

– un sommet ui est associ´e `a chaque variable xi ∈ X ;

– {ui, uj } ∈ E si, et seulement si, ∃ wS ∈ W, xi, xj ∈ S.

Par abus de langage, on appelle le graphe associ´e a` un WCSP son graphe de contraintes. La fig-ure 1.1 pr´esente un exemple de WCSP et son graphe de contraintes. Il est compos´e de six variables (X = {A, B, C, D, E, F }) et de cinq fonctions de coˆut (W = {wA,B,E , wAC , wC,D, wB,D, wD,F }). L’aﬀectation compl`ete A = {(A, a), (B, a), (C, a), (D, c), (E, b), (F, c)} est une solution optimale de coˆut 20.

soit P = (X, D, W, S) avec :

– X = {A,B,C,D,E,F},

– D = {{a, b}, {a, b}, {a, c}, {b, c}, {b, c}, {a, c}},

– W = {wA,B,E , wAC , wC,D, wB,D, wD,F }.

Depth First Branch and Bound (DFBB)

Le sch´ema classique de r´esolution d’un WCSP repose sur une recherche arborescente en profondeur d’abord bas´ee sur le calcul d’un minorant, DFBB (Depth First Branch and Bound).

A chaque noeud de l’arbre de recherche, un minorant ( ) du coˆut de toutes les extensions (aﬀectations compl`etes) issues de l’aﬀectation partielle courante est calcul´e. Ce minorant est ensuite compar´e au majorant du coˆut d’une solution optimale du probl`eme. Celui ci correspond au coˆut de la meilleure solution trouv´ee `a ce point de la recherche. Ainsi, si le minorant est sup´erieur au majorant, aucune extension de la solution partielle courante ne pourra ˆetre de meilleure qualit´e, et le sous-arbre peut ˆetre elagu´e.

L’algorithme 1 d´etaille le pseudo-code de DFBB. Le premier appel `a DFBB est DFBB(X,∅,⊤). Soit un probl`eme P = (X, D, W, S), DFBB est une fonction r´ecursive prenant comme param`etres Y ⊆ X, l’ensemble des variables non aﬀect´ees, une aﬀectation partielle A et le majorant courant UB. Tout d’abord, un minorant f (A) de la solution partielle courante est calcul´e. Si celui est inf´erieur ou ´egal au majorant UB, on teste tout d’abord si la solution courante est compl`ete, auquel cas, LB est retourn´. Sinon, une variable xi ∈ Y est s´electionn´ee, puis, pour chaque valeur aj possible du domaine de xi, DFBB est appel´ en retirant xi de Y et en aﬀectant aj `a xi. Le majorant UB est retourn´. Il sera alors le plus petit coˆut trouv´e sur les extensions de A.

La complexit´ de DFBB est en O(edn) avec d la taille du plus grand domaine, e le nombre de contraintes et n le nombre de variables. L’eﬃcacit´ de DFBB d´epend de la qualit´e du calcul du minorant LB. Un minorant trivial consiste a` sommer le coˆut des fonctions dont les variables sont aﬀect´ees. Nous allons voir dans la section 1.4.2 comment calculer de bien meilleurs minorants.

Limited discrepancy search (LDS)

La recherche LDS a et´ introduite par William D. HARVEY et Matthew L. GINSBERG [Harvey et Ginsberg, 1995]. C’est une recherche arborescente, tout comme DFBB, dans laquelle l’ordre de visite des noeuds est modifi´e. Soit h une heuristique de choix de valeurs dans laquelle on a une grande confiance. Le principe de LDS est de suivre l’heuristique h lors du parcours de l’arbre de recherche, mais en permettant seulement un petit ´ecart (δ) par rapport aux choix de h. On s’autorise donc δ ´ecarts (ou discrepancies) `a l’heuristique h. Pour un nombre maximal δmax d’´ecarts autoris´es, LDS explore l’arbre de recherche de mani`ere it´erative selon un nombre croissant d’´ecarts allant de i=0 `a i=δmax. A chaque it´eration, i est incr´ement´ de 1.

Dans la suite, nous ne consid´erons que des arbres d-aires. Dans un tel cas, l’heuristique h va ordonner toutes les valeurs du domaine d’une variable. La premi`ere valeur, selon l’ordre donn´e par h, n’engendre aucune augmentation de δ. La deuxi`eme valeur augmente la valeur de δ de 1 et la troisi`eme de 2, etc.

L’int´erˆet de LDS est d’explorer seulement les parties les plus int´eressantes de l’arbre de recherche (selon les heuristiques) et non son int´egralit´ comme le fait DFBB.

La figure 1.2 repr´esente les branches de l’arbre de recherche explor´e (en trait plein) lors des diﬀ´erentes it´erations de LDS (avec δmax=2).

Reformulation de W CSP

Les m´ethodes de reformulation de WCSP, aussi appel´ees m´ethodes d’inf´erence, ont pour but de transformer le probl`eme afin de le rendre plus facile `a r´esoudre. Nous pr´esentons dans la section suivante deux approches d’inf´erence pour les WCSP. La premi`ere, dite exacte, consiste a` ´eliminer des variables du probl`eme afin de le r´eduire. La seconde approche, dite incompl`ete, est fond´ee sur la reformulation locale en un probl`eme ´equivalent et consiste a` d´eplacer les coˆuts entre les fonctions et les variables pour faire apparaˆıtre un bon minorant de l’optimum du probl`eme.

L’objectif de la m´ethode d’´elimination de variable (Variable Elimination (VE) [Dechter, 1999]) est d’´eliminer progressivement les variables du probl`eme en pr´eservant le coˆut de la solution optimale. La m´ethode repose sur deux op´erateurs : l’addition et la projection de fonctions.

D´efinition 16 (Addition de deux fonctions). Soient deux ensemble de variables S1 et S2 et deux fonctions wS1 et wS2 d´efinies respectivement sur S1 et S2. L’addition des deux fonctions (wS1 ⊕ wS2 ) d´efinie sur l’ensemble S1 ∪ S2 est d´efinie par A ∈ DS1∪S2, (wS1 ⊕ wS2 )(A) = wS1 (A[S1]) ⊕ wS2 (A[S2])

D´efinition 17 (Projection d’une fonction). Soient deux ensemble de variables S et S′ et une fonctions wS d´efinie sur l’ensemble S. La projection de la fonction wS sur un sous-ensemble de ses variables S′ ⊂ S, not´ee wS [S′] est d´efinie par ∀B ∈ DS′ , wS [S′](B) = min A∈DS , A[S′]=B wS (A)

Ainsi, l’´elimination d’une variable xi dans un probl`eme P = (X, D, W, S) s’eﬀectue en trois ´etapes :

1. recherche de toutes les fonctions de coˆut wS telle que xi ∈ S.

2. ajout d’une fonction de coˆut wS′ dans W , portant sur les variables xi ∪ V ois(xi) dans P, r´esultant de la somme de toutes les fonctions identifi´ees en 1.

3. projection de wS′ sur l’ensemble V ois(xi).

L’algorithme se termine lorsque toutes les variables ont et´ supprim´ees. A la fin, le r´eseau ne contient que la fonction de coˆut w∅, ´egale au coˆut de la solution optimale du probl`eme.

L’eﬃcacit´ de cette m´ethode d´epend fortement de l’ordre dans lequel les variables sont elimin´ees. En eﬀet, chaque ´elimination de variable cr´ee une nouvelle fonction de coˆut dont l’arit´e correspond au nombre de variables voisines de celle elimin´ee dans le r´eseau. La complexit´ est exponentielle par rapport au nombre maximal de variables voisines d’une variable elimin´ee. Trouver un ordre d’´elimination optimal est un probl`eme NP-diﬃcile.

M´ecanismes de coh´erence par transformations du probl`eme

L’arc coh´erence est un m´ecanisme important dans la r´esolution des CSP puisqu’elle permet d’acc´el´erer la recherche de solutions. Il semble alors naturel de l’´etendre aux W CSP . Le but principal est de permettre la d´eduction de valeurs impossibles et de fournir `a la recherche un minorant le plus pr´ecis possible afin d’arrˆeter au plus tˆot la recherche dans un sous arbre ne pouvant conduire `a une meilleure solution. Pour cela, on recherche une reformulation du WCSP pr´eservant l’´equivalence, dans laquelle on va transf´erer les coˆuts des fonctions de coˆut vers la fonction d’arit´e nulle w∅.

Cette section traite d’´etablissement de la coh´erence par transformations pr´eservant l’´equivalence. Le principe de ces m´ethodes consiste `a d´eplacer les coˆuts entre fonctions afin de les concentrer sur w∅. Nous commen¸cons par d´efinir une notion d’´equivalence pour les W CSP . Puis, nous introduisons un nouvel op´erateur ⊖ et les algorithmes de projection permettant de transf´erer les coˆuts entre les fonctions, tout en pr´eservant l’´equivalence avec le probl`eme initial. Enfin, nous d´ecrivons diﬀ´erents m´ecanismes de coh´erence bas´es sur ces notions.

Nous supposons par la suite l’existence d’une fonction de coˆut unaire portant sur chaque variable du probl`eme. Dans cette partie, nous noterons wi la fonction de coˆut unaire portant sur xi.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela clepfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction
1 Contexte
1.1 M´ethodes de r´esolution
1.2 Variable Neighborhood Decomposition Search
1.3 D´ecomposition arborescente
2 Motivations et objectifs
3 Contributions
I ´Etat de l’art
1 R´eseaux de fonctions de coˆut
1.1 Le formalisme CSP
1.1.1 Variables et domaines
1.1.2 Contraintes
1.2 Le formalisme des WCSP
1.2.1 Structure de valuations
1.2.2 Le cadre g´en´eral des VCSP
1.2.3 Les WCSP
1.3 M´ethodes de recherche arborescente pour les WCSP
1.3.1 Depth First Branch and Bound (DFBB)
1.3.2 Limited discrepancy search (LDS)
1.4 Reformulation de WCSP
1.4.1 ´Elimination de Variable (VE)
1.4.2 M´ecanismes de coh´erence par transformations du probl`eme
1.4.3 Coh´erences pour les WCSP
1.4.4 Arc coh´erences optimales pour les WCSP
1.5 Hi´erarchie des coh´erences d’arc pour les WCSP
2 M´ethodes de d´ecomposition arborescente
2.1 D´efinitions
2.2 M´ethodes de d´ecomposition bas´ees sur la triangulation
2.2.1 Rappel du probl`eme de triangulation
2.2.2 De la triangulation `a la d´ecomposition arborescente
2.2.3 D´ecomposition arborescente d’un graphe quelconque
2.2.4 Algorithmes de triangulation
2.2.5 Recherche de cliques maximales
2.2.6 Calcul de l’arbre de jonction
2.3 Une m´ethode bas´ee sur les coupes minimales
2.3.1 Recherche de coupes minimales dans un graphe
2.3.2 Calcul de la d´ecomposition arborescente `a partir des coupes minimales
2.3.3 Comparaison entre MSVS et la m´ethode bas´ee sur la triangulation
2.4 ´Evaluation des heuristiques de triangulation
2.4.1 Protocole exp´erimental
2.4.2 R´esultats
2.4.3 Bilan sur les heuristiques de triangulation
2.5 Exploitation de la d´ecomposition arborescente pour les m´ethodes de recherche compl`ete
2.5.1 Une m´ethode d’inf´erence : Cluster Tree Elimination (CTE)
2.5.2 Les m´ethodes ´enum´eratives
2.5.3 Conclusion sur l’exploitation de la d´ecomposition arborescente pour les m´ethodes de recherche compl`ete
2.6 Conclusions
3 M´eta-heuristiques
3.1 Recherches locales
3.2 M´eta-heuristiques
3.2.1 Algorithmes bas´es sur les p´enalit´es
3.2.2 M´eta-heuristiques bio-inspir´ees
3.2.3 M´eta-heuristiques bas´ees sur la notion de voisinage
3.3 M´eta-heuristiques pour la r´esolution des WCSP
3.3.1 ID-Walk
3.3.2 VNS/LDS+CP
3.4 Crit`eres d’´evaluation des performances des m´eta-heuristiques
3.4.1 Taux de r´eussite
3.4.2 Profil de performance
3.4.3 Profils de rapport de performance
3.5 Conclusion sur les m´eta-heuristiques
4 Jeux de test
4.1 Probl`eme d’allocation de fr´equences `a des liens radio
4.1.1 Description du probl`eme
4.1.2 Mod´elisation sous forme d’un WCSP
4.1.3 Description des instances
4.2 Instances g´en´er´ees par GRAPH
4.3 Probl`eme de planification d’un satellite de prise de vue
4.3.1 Description du probl`eme
4.3.2 Mod´elisation sous forme d’un WCSP
4.3.3 Pr´esentation des instances
4.4 Probl`eme de s´election de TagSNP
4.4.1 Description du probl`eme
4.4.2 Mod´elisation sous forme d’un WCSP
4.4.3 Pr´esentation des instances
4.4.4 D´ecomposition arborescente
II Contributions
5 VNS guid´ee par la d´ecomposition arborescente
5.1 VNS Guid´ee par la D´ecomposition (DGVNS)
5.1.1 Structures de voisinage bas´ees sur la notion de cluster
5.1.2 Pseudo-code de DGVNS
5.2 Strat´egies d’intensification et de diversification dans DGVNS
5.2.1 Intensification versus diversification
5.2.2 DGVNS-1 : changer syst´ematiquement de cluster
5.2.3 DGVNS-2 : changer de cluster en l’absence d’am´elioration
5.2.4 DGVNS-3 : changer de cluster apr`es chaque am´elioration
5.3 Exp´erimentations
5.3.1 Protocole exp´erimental
5.3.2 Apport de la d´ecomposition arborescente
5.3.3 Impact de la largeur de d´ecomposition
5.3.4 Comparaison des trois strat´egies d’intensification et de diversification
5.3.5 Profils de performance des rapports de temps et de succ`es
5.4 Conclusions
6 Raffinements de la d´ecomposition arborescente
6.1 Raffinement bas´e sur la duret´e des fonctions de coˆut
6.1.1 Tightness Dependent Tree Decomposition (TDTD)
6.1.2 Influence du param`etre λ sur la d´ecomposition arborescente
6.1.3 R´eglage de la valeur du param`etre λ
6.2 Raffinement par fusion de clusters
6.2.1 Fusion de clusters bas´ee sur smax
6.2.2 Fusion de clusters bas´ee sur l’absorption
6.2.3 Influence des m´ethodes de fusion sur la d´ecomposition arborescente
6.2.4 Bilan des deux m´ethodes de fusion
6.3 Exp´erimentations
6.3.1 Apports de la TDTD
6.3.2 Apports de la fusion bas´ee sur smax
6.3.3 Apports de la fusion bas´ee sur l’absorption
6.3.4 Comparaison des deux m´ethodes de fusion
6.3.5 Profils de performance des rapports de temps et de succ`es
6.4 Conclusions
7 VNS guid´ee par les s´eparateurs
7.1 Separator-Guided VNS (SGVNS
7.1.1 Pseudo-code de SGVNS
7.2 Intensified Separator-Guided VNS (ISGVNS)
7.2.1 Pseudo-code de ISGVNS
7.3 Exp´erimentations
7.3.1 Comparaison entre SGVNS et DGVNS-1
7.3.2 Comparaison entre ISGVNS et DGVNS-1
7.3.3 Comparaison entre SGVNS et ISGVNS
7.3.4 Bilan sur les apports de SGVNS et ISGVNS
7.3.5 Apports de la TDTD pour SGVNS et ISGVNS
7.3.6 Profils de performance des rapports de temps et de succ`es
7.4 Conclusions
Conclusions et Perspectives
A Impact de la TDTD
Bibliographie