Performance analysis of permutation cross—over genetic operators

ABSTRACT

We are interested here in the utilization of Genetic Algorithms (GA) as approximation methods for combinatorial optimization. They are stochastic methods using genetic operators on a population. For their design, two points must be worked: the general scheme of the algorithm with parameter adjustment and the design of chromosome contents and genetic operators. The first point poses globally no specific problem. The latter one involves difficulties when binary genes inside the chromosomes are replaced by more general information such as permutations, in this case, the performance of the genetic operators must be analyzed with respect to the considered specific problems and their specific criteria. As performance of mutation operators are analogous to those of neighborhood operators used in well known local search methods, we will focus here only on cross—over operator (COO) performances. The aims of this paper are first to design permutation cross—over performance indicators which express the probable trend of associated criterion variations, second to list literature proposed permutation cross—over operators and to propose some new ones with particular properties, third to present a numerical experiment which compares the different cross—over operators using the defined performance indicators.

RÉSUMÉ

Nous nous intéressons ici à l'utilisation des Algorithmes Génétiques (AG) comme méthodes approchées pour résoudre des problèmes d'optimisation combinatoire. Ce sont des méthodes stochastiques qui font progresser la qualité d'une population au moyen d'opérateurs génétiques. Pour leur conception, il faut définir le schéma général de l'algorithme avec l'ajustement des paramètres associés ainsi que le codage des chromosomes et les opérateurs génétiques. La première partie n'est pas spécifique au problème considéré. La deuxième partie soulève des difficultés pour les problèmes où les chromosomes ne contiennent plus un codage binaire, mais un codage plus complexe comme par exemple des permutations. Dans ce cas, la performance des opérateurs génétiques doit être analysée en fonction du problème à résoudre. Comme la performance des opérateurs de mutation est analogue à la performance des opérateurs de voisinage utilisés dans des méthodes bien connues d'amélioration par voisinage local, nous allons nous intéresser ici uniquement à la performance des opérateurs de croisement. Le but de ce papier est tout d'abord de concevoir des indicateurs de performance des opérateurs de croisement qui donnent la tendance de variation probable de critères associés, ensuite, de lister les opérateurs de croisement de permutations présentés dans la littérature et d'en proposer quelques nouveaux présentant des propriétés particulières, enfin, de présenter une série d'expériences qui comparent les opérateurs de croisement au moyen des indicateurs de performance définis auparavant.

KEY WORDS:

• genetic algorithms
• performance analysis
• permutation scheduling problems

MOTS-CLÉS:

• algorithmes génétiques
• analyse des performances
• ordonnancement de permutation