Une nouvelle génération d'algorithmes génétiques guidés distribués pour la résolution des Max_CSPs
Ce papier présente une nouvelle génération d'algorithmes obtenus par améliorations successives de la version de base de l'algorithme génétique guidé par les templates (Tsang, 1999). Ces améliorations sont validées expérimentalement et ce, séparément et conjointement. Elles vont de la répartition des individus par espèce au contrôle des croisements et des mutations. Notre objectif est de maximiser le nombre de contraintes satisfaites. Pour ceci nous utilisons l'approche multi-agent, l'heuristique de minimisation de conflit et diversification ainsi que l'intensification localement au niveau des agents. Chaque agent est, en effet, responsable d'une espèce donnée ; à savoir un sous-ensemble d'individus violant le même nombre de contraintes.
This paper presents a new generation of algorithms obtained by successive improvements of the initial version of the genetic algorithm guided by the templates (GGA) (Tsang, 1999). These improvements are experimentally validated and this separately and jointly. They go from the distribution of the individuals by species to the control of the crossover and the mutation sub processes. Our objective is to maximize the number of satisfied constraints. For this we use the multiagent approach, the min-conflict heuristic and the diversification as well as the intensification locally on the level of the agents. Each agent is, indeed, responsible for a given species; namely a subset of individuals violating the same number of constraints.
B.SADOK, K.GHÉDIRA
Reçu le 29 août 2005.
Accepté le 3 janvier 2007.
algorithmes génétiques, problèmes de satisfaction maximale de contraintes, systèmes multi-agents, heuristique de minimisation de conflits, probabilité de guidage.
genetic algorithms, maximal constraint satisfaction problems, multi-agent systems, Min-conflict-heuristic, guidance probability.
Français
|
