Введение в эволюционное моделирование. Каширина И.Л. - 21 стр.

                                      21
• Следующий в списке L - 4, берем 4-й город из оставшегося списка
   C =[ 5 6 7 8 9] (это 8). Маршрут: 1 →2 → 4 → 3 → 8.
• Следующий номер в списке L - 1. Берем из списка С = [ 5 6 7 9] 1-й город
  – с номером 5. Маршрут: 1 →2 → 4 → 3 → 8→ 5.
• Следующий номер в списке L - 3. Берем третий город из списка С=[ 6 7 9]
  (это 9). Удаляем его из С. Маршрут: 1 →2 → 4 → 3 → 8→ 5→9.
• Следующий номер в списке L - 1, поэтому берем первый город из теку-
  щего списка С = [ 6 7] (город номер 6), и удаляем его из С. Частичный
  маршрут имеет вид: 1 →2 → 4 → 3 → 8→ 5→9→6.
• Последним номером в списке L всегда будет 1, поэтому берем последний
  оставшийся город из текущего списка С = [7], и удаляем его из С. Окон-
  чательно маршрут имеет вид: 1 →2 → 4 → 3 → 8→ 5→9→6→7→1.
Основное преимущество порядкового представления в том, что классиче-
ский кроссовер в данном случае работает! Любые два маршрута в порядко-
вом представлении, разрезанные в любой позиции и склеенные вместе, по-
родят два потомка, каждый из которых будет правильным маршрутом. На-
пример, два родителя Р1 = [1 1 2 1| 4 1 3 1 1] и Р2 = [5 1 5 5 | 5 3 3 2 1], ко-
торые обозначают соответственно маршруты 1 → 2 → 4 → 3 → 8 → 5 → 9
→ 6 → 7 →1 и 5 → 1 → 7 → 8 → 9 → 4 → 6 → 3 → 2→5, с точкой разреза,
обозначенной " | " породят следующих потомков: П1 = [1 1 2 1 5 3 3 2 1] и
П2 = [5 1 5 5 4 1 3 1 1].
Эти потомки обозначают маршруты 1 →2 → 4 → 3 → 9 → 7 → 8 → 6 → 5
→1 и 5 → 1 → 7 → 8 → 6 → 2 → 9 → 3 → 4→5.
    Легко заметить, что части маршрута слева от линии разреза не измени-
лись, тогда как части маршрута справа от линии разреза имеют достаточно
много отличий от окончаний родительских хромосом.
    В качестве мутации используется изменение с вероятностью pm i-го
элемента порядкового представления на случайный номер от 1 до n-i-1
                           3. Путевое представление
     Путевое представление – это наиболее естественное представление
маршрута. Например, тур 5 → 1 → 7 → 8 → 9 → 4 → 6 → 2 → 3 →5 будет
представлен как строка [5 1 7 8 9 4 6 2 3].
Частично отображаемый кроссовер
Частично отображаемый кроссовер берет сначала часть пути одного родите-
ля и сохраняет последовательность и позиции как можно большего числа го-
родов другого родителя. Точка кроссовера выбирается случайно.
                                 V 1 = 12 | 543
                                 V 2 = 35 | 421