Friday, May 14, 2010

Ранг частично упорядоченного множества

Понятие ранга у-множества было введено в [1] и развито в [2]. Оно определяется аналогично размерности Душника-Миллера [3], только вместо мощности наименьшого минимального реализатора нас интересует мощность наибольшего минимального реализатора (= множество линейных расширений у-множества, пересечение которых совпадает с самим у-множеством).

Тема эта интересна тем, что минимального реализатора всего пространства перестановок достаточно для вывода об избыточности оператора мутации на текущем шаге работы эволюционного алгоритма (рассматривается задача оптимизации, заданная на перестановках).
  1. Maurer S. Large Minimal Realizers of a Partial Order / Stephen B. Maurer, I. Rabinovitch // Proceedings of the American Mathematical Society, Vol. 66, No. 2 (Oct., 1977), pp. 211-216.
  2. Maurer S. Large Minimal Realizers of a Partial Order II / Stephen B. Maurer, I. Rabinovitch, William T. Trotter // Discrete Mathematics. - Vol. 31. - 1980. - P. 297-313.
  3. Dushnik B. Partially Ordered Sets / Ben Dushnik and E. W. Miller // American Journal of Mathematics, Vol. 63, No. 3 (Jul., 1941), pp. 600-610.

No comments:

Post a Comment