Expériences et analyses des résultats [614302]

111
Expériences et analyses des résultats

Ce nouveau modèle d’optimisation met en interaction toutes les contraintes, et alors le
problème de MaxCSP peut être traité globalement lors de la résolution. Par exemple, lors de
la modélisation du problème MaxCSP, nous avons intégré toutes les contraintes binaires du
problème MaxCSP dans notre modèle qui contient toutes les informations nécessaires sur le
problème MaxCSP.
4.4.2 Description de l’algorithme proposé pour résoudre le problème Max -CSP
Afin de trouver une solution au problème de satisfaction maximale de contraintes via
l’algorithme génétique , un algorithme a été développé. Rappelons qu’une solution est une
affectation de valeurs à toutes les variables de sorte qu’un maximum de contraintes soient
satisfaites. Les principales étapes de cet algorithme sont les suivantes :
1. La première étape consis te à extraire les données d’un problème Max-CSP, ces données
sont stockées dans un fichier XML (base de données). Cette lecture exige des techniques
assez développer pour extraire c es données de Max-CSP (les domaines, les variables, les
relations et les co ntraintes).
2. La deuxième étape modélise le problème Max-CSP en termes d’un programme quadratique
(détermination des matrices Q, A et du vecteur b).
3. La dernière étape concerne l’utilisation de l’algorithme génétique pour obtenir la solution
de ce modèle , de sorte que le nombre de contraintes violées dans le Max-CSP est égal à la
valeur optimale obtenu e par l’algorithme génétique .
4.4.3 Résultats numériques
Afin de montrer l’intérêt pratique de l’approche proposée, des expériences sont réalisées pou r
résoudre certains problèmes typiques de différentes natures . Ces expériences sont effectuée
dans un ordinateur personnel équipé d’un processeur 2.40 GHz et 4Go de RAM. La
performance a été mesuré e en termes de temps de calcul par seconde. Ce solveur est modélisé
et implémenté par le langage Java. Le processus de résolution conduira à une affectation de
valeurs à des variables telle que le nombre de contraintes satisfaites soit maximal. Par
conséquent , le maximum des contraintes dans le problème (Max -CSP) soient satisfaites.
Une étude expérimentale a été représentée pour examiner la qualité de notre approche. Cette
étude est basée sur le calcul de la performance des opérateurs. En fait, la qualité des solutions
obtenues par notre approche a été é valuée en termes de rapport sur le rendement :

112
Expériences et analyses des résultats

𝑝=𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑣𝑖𝑜𝑙é𝑒𝑠 𝑜𝑏𝑡𝑒𝑛𝑢𝑒 𝑝𝑎𝑟 𝑛𝑜𝑡𝑟𝑒 𝑎𝑝𝑝𝑟𝑜𝑐ℎ𝑒
𝑚𝑒𝑖𝑙𝑙𝑒𝑢𝑟 𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑣𝑖𝑜𝑙é𝑒𝑠 𝑜𝑏𝑡𝑒𝑛𝑢𝑒 𝑝𝑎𝑟 𝑙𝑒 𝑚𝑒𝑖𝑙𝑙𝑒𝑢𝑟 𝑠𝑜𝑙𝑣𝑒𝑢𝑟
Par cet o pérateur de performance, on a (t ableau 4.4 )
 Ratio minimum : le rapport entre le plus petit nombre de contraintes violées
(meilleurs résultats obtenus par notre solveur) et le meilleur résultat exis tant dans la
littérature obtenu par d’autre solveur.
 Le temps d’execution : le temps consommé pour obtenir la solution à un certain
nombre d’exécution.
Nous montrons que, pour chaque exemple, si le ratio minimum est inférieur à 1, alors
l’approche proposée donne des me illeurs résultats que les autres, Autrement dit, donne une
solution qui viole moins de contraintes en comparaison avec le meilleur solveur existant dans
le benchmarks. Sinon, si le ratio minimum est supérieur à 1, alors l’approche proposée donne
une soluti on qui viole plus de contraintes par rapport au meilleur solveur existant dans la
littérature, c’est à dire, n’arrive pas à trouver les résultats donnés par le meilleur solveur. Par
ailleurs, si le ratio minimum est égal à 1, dans ce cas, les résultats don nés sont similaires que
le meilleur solveur (tableau 4.4 ).
En comparaison avec d’autres solveurs de Max -CSP, le temps de résolution obtenu par notre
approche est mieux que d’autres. En règle générale, notre solveur est très réussi, il arrive à
trouver la s olution aux problèmes de satisfaction maximale de contraintes en un minimum de
temps que les autres solveurs de Max -CSP[136] .
instance NC RB Temps ben RM Temps app
maxcut -30-340-2 340 102 20.1629 s 0.98 18.010s
maxcut -30-400-5 400 179 160.628 s 0.94 123. 597s
maxcut -40-420-5 420 161 84.7451 s 0.99 67.300s
maxcut -40-520-10 520 213 461.111 s 0.98 398.02s
maxcut -50-560-10 560 212 1151.8 s 1.03 790.326s
maxcut -50-580-10 580 221 1508.98 s 1 681.250 s
maxcut -60-420-2 420 135 176.564 s 0.96 163.560s
maxcut -60-580-2 580 207 3316.9 s 1.01 717.983s
vcsp-25-10-100-18-15 300 2 100.907 s 1 116.846s
vcsp-15-10-100-93-14 105 73 12.3021 s 1.09 11.587s

113
Expériences et analyses des résultats

c-fat500 -2 116111 474 22.0556 s 1.1 13.592s
c-fat500 -10 78623 374 14.0389 s 1.05 12.042s
Tableau 4. 4 Les instances de Max -CSP
Légende du tableau
 NC : nombres de contraintes
 RB : Résultat de benchmark
 Temps ben : temps d’exécution de benchmark
 RM : Ratio minimum
 Temps app : Temps d’exécution de l’approche proposée
Par exemple, pour les instances “ maxcut -30-340-2”, ”maxcut -30-400-5”, etc., le solveur
proposé donne une solution qui viole moins de contraintes par rapport au meilleur solveur
existant. Toutefois, dans certains cas, “ maxcut -50-560-10”, “vcsp-15-10-100-93-14”, etc.,
notre approche viole ainsi des contraintes en plus d’autres solveurs. Enfin, nous pouvons
conclure que les meilleurs résultats sont obtenus par cette approche.
4.5 Conclusion
Dans ce chapitre, nous nous sommes intéressés à l'optimisation des requêtes su r une base de
données massives, à l’amélioration du réseau de Hopfield continu et aux problèmes de
satisfaction maximale de contraintes .
La manipulation des données en base de données passe par des requêtes. Leur traitement
nécessite beaucoup de temps et de ressources. Dans la première contribution , nous avons
adopté une approche de matérialisation pour l’optimisation des requêtes dans les bases de
données massives. Vue le coût de stockage qui n’a pas été étudié dans les diff érentes
littératures existantes, n ous avons modélisé le problème de sélection des vues sous forme d’un
problème de satisfaction de contraintes pondérées tout en essayant de trouver le meilleur
compromis entre tous les coûts de traitement des requêtes, de maintenance et de stockage.
Cette modélisation a été à base d’un espace de recherche, ce dernier est construit par la fusion
de huit requêtes afin d’avoir un espace avec un coût minimal . Nous avons évalué l’approche
de matérialisation via l’ algorithme génétique pour optimis er l’exécution des requêtes en
utilisant le benchmark TCP -H[16]. Nous avons constaté que notre approche donne de
meilleurs résultats pour notre cas d’expérimentation .