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.