/dev/random

L'epsilon-dominance est une relaxation de la dominance à un epsilon près. Il est cependant fâcheux de voir que comme pour le rang, tout le monde n'utilise pas exactement la même définition. Voir par exemple l'implémentation qui en est faite dans les algorithmes OMOPSO et Omni-Optimizer. 

Heureusement, cela ne change pas fondamentalement la notion d'epsilon-dominance, mais il faut se méfier de la valeur que l'on donne aux paramètres.

Dans ce billet, je pointais les différentes définitions de rang trouvées. La définition donnée par Caspard, Leclerc et Monjardet est plus communément appelée graduation en théorie des ordres, le terme de rang étant autrefois utilisé par la communauté francophone. La définition utilisée par Bernd S. W. Schröder est la plus communément admise et viendrait de la définition du rang dans un graphe orienté. En résumé la seconde définition est cohérente avec la théorie des graphes et plus largement répandue, tandis que la deuxième peut prêter à confusion. Pour cette dernière on lui préférera le terme de graduation qui n'est pas ambigu.

De quoi parle-t-on quand on parle du rang d'un élément d'un ensemble ? Voilà a priori une question de définition mathématique pour les personnes travaillant sur les ensembles ordonnés. Problème : j'ai trouvé deux définitions du rang d'un ensemble ordonné. Pis ! Ce terme est utilisé avec encore d'autres définitions quand on change de domaine, par exemple dans les algorithmes génétiques multiobjectifs.

Caspard, Leclerc et Monjardet [1] définissent le rang de la manière suivante : y est le successeur de x implique que rang(x) = rang(y) + 1. Dans [2], Schröder définit le rang récursivement en attribuant le rang 0 aux éléments minimaux, puis en attribuant un rang de n pour les éléments minimaux de l'ensemble privé des éléments de rang < n. Le rang de l'élément x est alors le cardinal de la chaîne maximale ayant x pour maximum. Cette définition du rang de x dans [2] correspond à la définition de la hauteur de x dans [1].

Goldberg, dans [3] suggère l'utilisation d'un rang pour comparer les individus d'un algorithme génétique. Ce rang est le même que celui défini dans [1] à ceci près qu'il commence à 1 et non à 0. Ce rang sera utilisé par Srinivas et Deb pour le fameux NSGA [4]. Précédemment, Fonseca et Fleming proposèrent un autre rang que celui de Goldberg pour l'algorithme MOGA [5]. Le rang de l'élément x de Fonseca et Fleming correspond en fait au cardinal de l'idéal de x (le nombre de minorants de x).

Références :

• [1] Nathalie Caspard, Bruno Leclerc, and Bernard Monjardet. Ensembles ordonnés finis : concepts, résultats et usages, volume 60 of Mathématiques & Applications. Springer, 2007.
• [2] Bernd S. W. Schröder. Ordered Sets : An introduction. Birkhäuser, December 2002.
• [3] David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, Massachusetts, 1989.
• [4] N. Srinivas and Kalyanmoy Deb. Multiobjective optimization using nondominated sorting in genetic algorithm. Evolutionary Computation, 2(3) :221– 248, 1994.
• [5] Carlos M. Fonseca and Peter J. Fleming. Genetic algorithms for multiobjective optimization : Formulationdiscussion and generalization. In Proceedings of the 5th International Conference on Genetic Algorithms, pages 416–423, San Francisco, CA, USA, 1993. Morgan Kaufmann Publishers Inc.