[benoit@guedas.com:~]

Aller au contenu | Aller au menu | Aller à la recherche

mardi 17 mai 2011

Rangs et graduations

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).

Faire commencer le rang à 1 ou a 0 n'a pas grande importance et est une affaire de convention.

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.

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.

mercredi 2 février 2011

Multi(-)objectif, multi(-)disciplinaire

On voit souvent écrit multi-objectif (avec un trait d'union), mais multidisciplinaire (avec un trait d'union). On peut d'ailleurs constater que le site Google Fight donne 130000 résultats pour multi-iobjectif contre seulement 4350 pour multiobjectif. Inversement, on obtient seulement 128000 résultats pour multi-disciplinaire contre 245000 résultats pour multidisciplinaire.

D'après l'Académie Française : Le préfixe multi- permet de former librement toutes sortes de néologismes. Conformément à l'usage et en accord avec les recommandations formulées en 1990 par le Conseil supérieur de la langue française, dont l'Académie a approuvé les principes, ces composés se traitent comme des mots ordinaires : bien que multi- signifie « plusieurs », la marque du pluriel est réservée au pluriel (un multimoteur ; une assurance multirisque, des assurances multirisques) ; le préfixe multi- se soude à l'élément qui suit, on n'emploierait le trait d'union que devant un i.

Il faut donc écrire multiobjectif et multidisciplinaire.