- \n
- Les probl\u00e8mes d\u2019optimisation combinatoire sur des nombres entiers sont d\u00e9finis comme suit :\n
- \n
- un groupe de variable.<\/li>\n
- un groupe de contraintes associ\u00e9es \u00e0 celles-ci.<\/li>\n
- un fonction objective<\/li>\n<\/ul>\n
Le probl\u00e8me est de trouver une solution qui satisfait les contraintes et optimise (minimise ou maximise) la fonction objective.<\/p><\/li>\n
- L\u2019id\u00e9e de base de la P<\/strong>rogrammation L<\/strong>ogique par C<\/strong>ontrainte (Constraint Logic Programming(FD)\u00b9)
\nest de remplacer le m\u00e9canisme d\u2019unification de la Programmation Logique par la r\u00e9solution de contraintes sur des domaines particuliers, en consid\u00e9rant le r\u00e9solveur de contraintes comme une bo\u00eete noire qui se charge de tester la satisfiabilit\u00e9 des contraintes.<\/li>\n- La compr\u00e9hension et l\u2019imitation des ph\u00e9nom\u00e8nes naturels d\u2019\u00e9volution et d\u2019adaptation des individus et des populations a donn\u00e9 lieu \u00e0 de nombreux algorithmes d\u2019intelligence artificielle regroup\u00e9s sous le terme g\u00e9n\u00e9rique d\u2019algorithmes \u00e9volutionnaires. Les plus connus sont les algorithmes g\u00e9n\u00e9tiques (GA), les Evolution Strategies (ES) et les Evolutionary Programming (EP).<\/li>\n
- Ces algorithmes se r\u00e9v\u00e8lent robustes et efficaces dans la r\u00e9solution de nombreux probl\u00e8mes et en particulier des probl\u00e8mes d\u2019optimisation et de satisfaction de contraintes (p. ex. la planification, l\u2019ordonancement et l\u2019affectation de ressources). Ils sont largement utilis\u00e9s dans les industries, le transport, les t\u00e9l\u00e9communications, la d\u00e9fence, les soins de sant\u00e9 , etc. De nombreuses recherches sont aujourd\u2019hui r\u00e9alis\u00e9es dans ce domaine tr\u00e8s actif de l\u2019intelligence artificielle.<\/li>\n
- Le principe de base de ces algorithmes est la mise en oeuvre de processus de s\u00e9lection, mutation et recombinaison au sein d\u2019une population d\u2019individus; chaque individu repr\u00e9sentant un point particulier dans l\u2019espace de recherche.<\/li>\n
- La litt\u00e9rature scientifique propose une large game d\u2019algorithmes \u00e9volutionnaires, de strat\u00e9gies de s\u00e9lection, d\u2019op\u00e9rateurs de mutation et de recombinaison. N\u00e9anmoins, la mise en oeuvre de ces algorithmes pour la r\u00e9solution de probl\u00e8mes sp\u00e9cifiques d\u2019optimisation reste encore, aujourd\u2019hui, un art et laisse une grande part \u00e0 la cr\u00e9ativit\u00e9.<\/li>\n<\/ul>\n
Base du probl\u00e8me<\/h1>\n
- \n
- Probl\u00e8me d\u2019optimisation combinatoire<\/li>\n
- Programmation Logique par Contrainte sur des Domaines Finis (CLP-FD)<\/li>\n
- Paradigme utilis\u00e9 : \u00ab\u00a0Constraint & Generate\u00a0\u00bb, 3 phases
\n1) Phase de contrainte : r\u00e9duction de l\u2019espace de recherche
\n2) Phase d\u2019\u00e9num\u00e9ration ou Labeling : invoque la r\u00e9solution compl\u00e8te des contraintes
\n3) Phase de recherche de la solution optimale : heuristique sp\u00e9cifique ou m\u00e9thode g\u00e9n\u00e9rale ( Branch & Bound )<\/li>\n - Mais les limites existent\u2026<\/li>\n<\/ul>\n
L\u2019alternative<\/h1>\n
- \n
- Les algorithmes d\u2019approximation<\/li>\n
- Pas de garantie pour trouver la solution optimale<\/li>\n
- Haute probabilit\u00e9 de trouver une bonne solution en explorant seulement une partie de l\u2019espace des solutions.<\/li>\n
- Int\u00e9gration d\u2019une technique d\u2019approximation appel\u00e9e \u00ab\u00a0Evolutionary Programming into CLP(FD)\u00a0\u00bb<\/li>\n<\/ul>\n
Labeling with evolutionary programming<\/h1>\n
- \n
- But : Am\u00e9liorer CLP(FD)<\/li>\n
- Par une technique d\u2019optimisation qui : suivant une liste de variables de domaines et une expression de co\u00fbt qui retourne une solution (la plus optimale) en respectant l\u2019expression de co\u00fbt.<\/li>\n<\/ul>\n
Algorithmes \u00e9volutionnaires<\/h1>\n
- \n
- La compr\u00e9hension et l\u2019imitation des ph\u00e9nom\u00e8nes naturels d\u2019\u00e9volution et d\u2019adaptation des individus et des populations a donn\u00e9 lieu \u00e0 de nombreux algorithmes d\u2019intelligence artificielle regroup\u00e9s sous le terme g\u00e9n\u00e9rique d\u2019algorithmes \u00e9volutionnaires.<\/li>\n
- Ils permettent une recherche effective dans un espace de recherche tr\u00e8s large.<\/li>\n
- Le principe de base de ces algorithmes est la mise en oeuvre de processus de s\u00e9lection, mutation et recombinaison au sein d\u2019une population d\u2019individus; chaque individu repr\u00e9sentant un point particulier dans l\u2019espace de recherche.<\/li>\n
- \u00ab\u00a0Genetic Algorithms + Data structures = evolution programs\u00a0\u00bb<\/li>\n<\/ul>\n
Evolutionary program (1)<\/h1>\n
Procedure evolutionary program\r\nBegin\r\n t:=0;\r\n initialize P(t); \r\n evaluate P(t);\r\n while not termination-condition do begin\r\n t := t + 1;\r\n select P(t) from P(t-1);\r\n alter P(t);\r\n evaluate P(t);\r\n end;\r\nEnd.<\/pre>\n
Evolutionary program (2)<\/h1>\n
- \n
- Population de \u00ab\u00a0chromosomes\u00a0\u00bb, P(t) = {Xt1 \u2026,Xtn } pour l\u2019it\u00e9ration t.<\/li>\n
- Chaque chromosome repr\u00e9sente une solution potentiele du probl\u00e8me et est repr\u00e9sent\u00e9 par une structure de donn\u00e9e : S<\/li>\n
- La premi\u00e8re \u00e9tape dans tous les programmes \u00e9volutionnaires est la g\u00e9n\u00e9ration de la population initiale : P(0), qui est g\u00e9n\u00e9r\u00e9 de fa\u00e7on al\u00e9atoire (INITIALIZE)<\/li>\n
- La population est ensuite \u00e9valu\u00e9e. A chaque g\u00e9n\u00e9ration, une valeur \u00abfitness \u00bb (adaptation) est calcul\u00e9e pour chaque chromosome Xti<\/li>\n
- Fitness indiquant le degr\u00e9 de \u00ab\u00a0justesse\u00a0\u00bb du chromosome comme \u00e9tant solution du probl\u00e8me d\u2019optimisation. (EVALUATE)<\/li>\n
- La fonction objective du probl\u00e8me qui doit \u00eatre optimis\u00e9e est \u00e0 la base du calcul de la valeur \u00ab\u00a0fitness\u00a0\u00bb<\/li>\n<\/ul>\n
Evolutionary program (3)<\/h1>\n
- \n
- Une nouvelle population P(t+1) est form\u00e9e par s\u00e9lection d\u2019un certain nombre de chromosomes de la population P(t) (SELECT)<\/li>\n
- Les chromosomes, ayant la meilleure valeur d\u2019 \u00abadaptation\u00bb, ont plus de chance d\u2019\u00eatre retenu par la proc\u00e9dure de s\u00e9lection.<\/li>\n
- Quelques chromosomes de la population P(t) seront pr\u00e9sent dans la population P(t+1)<\/li>\n
- Tous les \u00ab\u00a0mauvais\u00a0\u00bb chromosomes ne sont pas tous jet\u00e9s car ils pourraient \u00e9ventuellement conduire \u00e0 la g\u00e9n\u00e9ration d\u2019une bonne solution.<\/li>\n<\/ul>\n
Evolutionary program (4)<\/h1>\n
- \n
- Quelques membres de la nouvelle population subiront des transformations (op\u00e9rateurs g\u00e9n\u00e9tiques) afin de former de nouvelles solutions. (ALTER)<\/li>\n
- Ces op\u00e9rateurs g\u00e9n\u00e9tiques vont g\u00e9n\u00e9rer de nouveaux chromosomes qui seront additionn\u00e9s \u00e0 la population P(t)<\/li>\n
- La mutation : la mutation cr\u00e9e des nouvelles solutions par de petit changement dans un simple chromosomes. S S, elle permet de \u00ab\u00a0sauter\u00a0\u00bb vers des zones encore inexplor\u00e9e de l\u2019espace de recherche.<\/li>\n<\/ul>\n
Condition de terminaison<\/h1>\n
- \n
- Soit on atteint un nombre d\u2019it\u00e9ration maximum<\/li>\n
- Soit on arr\u00eate apr\u00e8s un temps d\u00e9termin\u00e9 par l\u2019utilisateur<\/li>\n
- Soit on obtient un chromosome ayant le co\u00fbt sp\u00e9cifi\u00e9 par l\u2019utilisateur<\/li>\n
- Soit on atteint une population invariante et\u00a0sans espoir<\/li>\n<\/ul>\n
Param\u00e9trisation<\/h1>\n
- \n
- Taille de la population<\/li>\n
- Pourcentage de survivant \u00e0 chaque g\u00e9n\u00e9ration, \u2026<\/li>\n
- Affecte dramatiquement les performances du syst\u00e8me<\/li>\n<\/ul>\n
Exemple<\/h1>\n
Recherche d\u2019un plan de transport de co\u00fbt minimum pour un produit unique<\/p>\n
- \n
- Soit n sources et k destination<\/li>\n
- Nombre de provision \u00e0 la source i : sour(i)<\/li>\n
- Nombre de demande \u00e0 la destination : dest(j)<\/li>\n
- Co\u00fbt de transport entre la source i et la destination j : cost(i,j)<\/li>\n
- Volume transport\u00e9 entre la source i et la destination j : X i,j<\/li>\n<\/ul>\n
![\"\"](\"https:\/\/i0.wp.com\/imalogic.com\/blog\/wp-content\/uploads\/2017\/05\/formule.jpg?ssl=1\")
<\/a><\/p>\n