<. A¡, OPÉRATEURS GÉNÉTIQUES SPÉCIALISÉS 4.2. Opérateurs Procédure arc-mutation (chromosome) Début Pour chaque variable A", Générer un nombre aléatoire r entre [0..1J si r <probabilité de mutation alors I(A; / ) = l i(I-.r J " !1 )Ur,))}'» Fin /* procédure arc-mutation */ '' sa valeur courante, en anglais: backtrack 2. en anglais: look-ahead 4

. Flg, 3 -Structure de la procédure are-mutation sont D, ? {1,2.3},V?' ? 1....4. Supposons que nous voulons changer la valeur de lu variable A" s du chromosome, qui actuellement a la valeur 2. L'ensemble M 3 sera composé par {d, Nous avons donc deux valeurs possibles pour A3 soit 1 soit

C. Mff, = 1,1) = 5 et mff(A 3 = 3,1) = 4, arc-mutation choisira la valeur 3 pour A';-¡. En faisant cela, ce chromosome sera plus facile à réparer ensuite, en lui chauiz;eant, par exemple

H. , M. , A. , and M. D. Johnston, A discrete stochastic neural network algorithm for constraint satisfaction problems, Proceedings International Joint Conference on Neural NetworksAS94] J.M. Alliot and T. Schiex. Intelligence Artificielle & Informatique Théorique . Cépaduès Éditions, pp.65-67, 1990.

J. , I. Blot, and J. Chabrier, Application de la méthode score(fd/i) aux esps binaires, Sème Conference Nationale pour la Resolution Pratique de Problèmes NP-Complets, pp.75-80, 1997.

W. Blazewicz, R. Cellary, . Slowinski, and J. Weglarz, Scheduling under resource constraints: Deterministic models, Annals of Operations Research, 1986.

]. C. Bes94 and . Bessière, Arc-consistency and arc-consistency again, In Artificial Intelligence, vol.65, pp.179-190, 1994.

A. D. Bet80j, . Bethke, and . Genetic, Algorithms as Function Optimizers, 1980.

J. Bessière, E. C. Freuder, and I. C. Régin, Using inference to reduce arc consistency computation, International Joint Conference on Artificial Intelligence, pp.592-598, 1995.

J. [. Bonomi and . Lutton, Le recuit simulé, Pour la Science, 1988.

¡. , M. Y. Dorigo, A. Maniezzo, and . Colorni, The ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Mar, and Cybernetics jDor92] 3VI. Dorigo. Optimization. Learning and Natural Algorithms, 1992.

¡. R. Dechter and J. Pearl, Network-based heuristics for constraint-satisfaction problems, Eib9G| A.E. Eiben. Handbook of Evolutionary Computation, chapter Constraint Satisfaction Problems, pp.1-38, 1988.
DOI : 10.1016/0004-3702(87)90002-6

¡. R. Eiben, P. Raué, and Z. R. Uttkay, Solving constraint satisfaction problems using genetic algorithms, Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, pp.542-547
DOI : 10.1109/ICEC.1994.350002

E. , A. E. Eiben, P. Raué, and Z. Ruttkay, Ga-easy and ga-hard constraint satisfaction problems, Meyer [Mey95j, pp.267-283
DOI : 10.1007/3-540-59479-5_30
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.9820

P. [. Eiben, Z. Raué, and . Ruttkay, Self-adaptivity for constraint satisfaction: learning penalty functions, Proceedings of IEEE International Conference on Evolutionary Computation, pp.258-261
DOI : 10.1109/ICEC.1996.542371

]. A. Evdh97, J. Eiben, and . Van-der-haw, Solving 3-sat by gas adapting constraint weights, Porto [Por97], pp.81-86

F. [. and J. Feriand, Genetic algorithms and hybrids for graph coloring, Annals of Operations Research, 1992.

]. J. Bibliographie-|gres7 and . Grefenstette, Incorporating problem specif knowledge into genetic algorithms, Genetic Algorithms and Simulated Annealing, 1987.

F. E. Glover, D. Taillard, and . De-werra, A users guide to tabu search The steepest ascend mildest descend heuristic for combinatorial programming, Annals of Operations Research Congress on Numerical Methods in Combinatorial Optimisation, pp.3-28, 1986.

A. Hertz and D. De-werra, Die Tabu-Methoden zur Graphenf??rbung, Computing, pp.345-351, 1987.
DOI : 10.1007/BF02239976

E. Haralick, Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence, vol.14, issue.3, pp.263-313, 1980.
DOI : 10.1016/0004-3702(80)90051-X

|. A. Homaifar, H. Lai, and X. Qi, Constrained Optimization Via Genetic Algorithms, Simulation, pp.242-254, 1994.
DOI : 10.1177/003754979406200405

J. R. Hinterding, Z. Michalewicz, and A. Eiben, Adaptation in evolutionary computation: a survey, Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97), pp.65-69
DOI : 10.1109/ICEC.1997.592270

]. R. Hof93 and . Hofmann, Examinations on the algebra of genetic algorithms, 1993.

J. H. Holland, Genetic Algorithms and the Optimal Allocation of Trials, SIAM Journal on Computing, vol.2, issue.2, pp.88-105, 1973.
DOI : 10.1137/0202009

J. H. Holland, Adaptation in Natural and Artificial Systems, 1975.

[. Hao and J. Pannier, Simulated annealing and tabu search for constraint solving, 5th Intl. Symposium on Artificial Intelligence and Mathematics, 1998.

]. P. Bibliographie-¡jegoo and . Jegou, Cyclic-clustering: a compromise between tree-clustering and the cycle-cutset method for improving search efficiency, Proceedings of EC A190, pp.369-371, 1990.

¡. , T. J. Joines, and C. Houck, On the use of non-stationary penalty function to solve non-linear constraint optimization problems with gas, Michalewicz et al, pp.579-584

¡. , D. Johnson, and L. Mcgeoch, The Traveling Salesman Problem: A Case Study in Local Optimization, |Kar95] H. Kaxgupta. {SEARCH}, polynomial complexity, and the fast messy genetic algorithm, 1995.

¡. , S. C. Kirkpatrick, M. Gellat, and . Vecchi, Optimization by simulated annealing, Science, pp.671-680, 1983.

J. Koza, Hierarchical genetic algorithms operating on populations of computer programs, Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, pp.768-774, 1989.

V. Kum92j, G. Kumar, and . Laporte, Algorithms for constraint satisfaction problems:a survey The vehicle routing problem: An overview of exact and approximate algorithms, Artificial Intelligence Magazine, pp.32-44, 1992.

|. S. Lin and B. W. Kernighan, An Effective Heuristic Algorithm for the Traveling-Salesman Problem, Operations Research, vol.21, issue.2, pp.498-516, 1973.
DOI : 10.1287/opre.21.2.498

¡. , G. E. Liepins, and A. Vose, Representational issues in genetic optimization, In Journal of Experimental and Theomcal Artificial Intelligence, vol.2, pp.4-30, 1990.

B. Michalewicz and J. Cezary, Handling constraints in genetic algorithms, Proceedings of the Fourth International Conference on Genetic Algorithms, pp.151-157, 1991.

¡. , R. Mohr, and T. C. Henderson, Arc and path consistency revisited, In Artificial Intelligence, vol.28, pp.225-233, 1986.
DOI : 10.1016/0004-3702(86)90083-4
URL : https://hal.archives-ouvertes.fr/inria-00548487

Z. Mic94j and . Michalewicz, Genetic Algorithms -h Data Structures = Evolution Programs . Artificial Intelligence, 1994.

[. Mintori, M. A. Johnston, P. Philips, and . Laird, Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems, In Artificial Intelligence, vol.58, pp.161-205, 1992.

G. [. Michalewicz and . Nazhiyath, Genocop III: a co-evolutionary algorithm for numerical optimization problems with nonlinear constraints, Proceedings of 1995 IEEE International Conference on Evolutionary Computation
DOI : 10.1109/ICEC.1995.487460

P. Mor93j and . Morris, The breakout method for escaping from local optima, Proceedings of the AAAI, pp.40-45, 1993.

|. Z. Michalewicz and M. Schoenauer, Handbook of Evolutionary Computation , chapter Evolutionary Algorithms for Constrained Parameter Optimization Problems, 1996.

|. B. Naudts and A. Yerschoren, Epistasis and deceptivity

J. Paredis, Co-evolutionary constraint satisfaction, Third International Conference on Parallel Problem Solving Nature, pp.46-55, 1994.
DOI : 10.1007/3-540-58484-6_249

J. Pearl, Heuristic search theory: a survey of recent results, International Joint Conference on Artificial Intelligence Third IEEE International Conference on Evolutionary Computation, pp.24-28, 1981.

]. N. Aisl, N. Radcliffe, and . Radcliffe, Binary constraint satisfaction problems: Some are harder than others Equivalence class analysis of genetic algorithms The algebra of genetic algorithms. Epce-tr-92-11, 11th European Conference on Artificial Intelligence Genetic Neural Networks on MIMD Computers Complex Systems jRawBlj G.J. R.awiins. Foundations of Genetic Algorithms, pp.46-91, 1990.

J. F. Rossi, C. Pétrie, and V. Dhar, On the equivalence of constraint satisfaction problem. Act-ai-222-89, 1989.

[. Rabinovich and A. Wigderson, An analysis of a simple genetic algorithm Stochastic search and phase de transitions: Ai meets physics, Proceedings of the Fourth International Conference on Genetic Algorithms International Joint Conference on Artificial Intelligence, pp.215-222, 1981.

¡. H. Selmaii, B. Kautz, and . Cohen, Noise strategies for improving local search, Proceedings of the. AAAI, pp.337-343, 1994.

J. B. Selrnan, D. Levesque, and . Mitchell, A new method for solving hard satifiability problems In search of exceptionally difficult constraint satisfaction problems, Tenth National Conference on Artificial ' ' " Intelligence Meyer [Mey95j, pp.440-446, 1992.

¡. A. Smith and D. Tate, Genetic optimization using a penalty function, Proceedings of the Fifth International Conference on Genetic Algorithms |Svs89j G. Syswerda. Uniform crossover in genetic algorithmes Third International Conference on Genetic Algorithms, pp.499-503, 1968.

M. Kauffmann, E. Taillard-]-e, and . Taillard, Robust tabu search for the quadratic assignment problem Parallel iterative search methods for vehicle routing problems Genetic algorithms versus simulated annealing: Satisfaction of large sets of algebraic mechanical design constraints Applying genetic algorithms to constraint satisfaction optimization problems, Nineth European Conference on Artificial Intelligence, pp.443-455, 1989.

B. Van-laarhoven, E. Aarts, and U. , Simulated Annealing: Theory and Applications . Klinver, 1988. |War95¡ T. Warwick. .4 GA Approach to Constraint Satisfaction Problems, 1995.

W. T. Warwick and E. Tsang, Using a genetic algorithm to tackle the processors configuration problem, Proceedings of the 1994 ACM symposium on Applied computing , SAC '94, pp.217-221, 1994.
DOI : 10.1145/326619.326726