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

                                   19
опять следующее от первого и т.д. Если новое ребро представляет замкну-
тый цикл, берут ребро из того же родителя (нарушая чередование). Если и
оно образует цикл, берут случайное ребро, которое еще не выбиралось и не
образует замкнутого цикла. Второй потомок строится аналогично, но первое
ребро берут от второго родителя. Для примера рассмотрим построение од-
ного из потомков двух хромосом:
         P1 = [2 3 8 7 9 1 4 5 6] ,
         Р2 = [7 5 1 6 9 2 8 4 3].
Шаг 1.   П1 = [2 _ _ _ _ _ _ _ _]. (В маршрут входит ребро 1→2).
Шаг 2.   П1 = [2 5 _ _ _ _ _ _ _]. (Маршрут содержит фрагмент 1→2→5).
Шаг 3.   П1 = [2 5 8 _ _ _ _ _ _]. (Маршрут содержит фрагменты 1→2→5,
3→8).
Шаг 4. П1 = [2 5 8 6 _ _ _ _ _]. (Маршрут содержит фрагменты 1→2→5,
       3→8, 4→6).
Шаг 4. П1 = [2 5 8 6 9 _ _ _ _]. (Маршрут содержит фрагменты 1→2→5→9,
       3→8, 4→6).
Шаг 5. П1 = [2 5 8 6 9 1 _ _ _]. (Маршрут содержит фрагменты
       4→6→1→2→5→9, 3→8).
Шаг 6. П1 = [2 5 8 6 9 1 4 _ _]. (Маршрут содержит фрагменты
       7→4→6→1→2→5→9, 3→8).
Шаг 7.     П1 = [2 5 8 6 9 1 4 7 _]. (Маршрут содержит фрагмент
       3→8→7→4→6→1→2→5→9 ). На этом этапе потомок получил реб-
       ро 8→7, не присутствующее ни у кого из родителей, т. к. добавление
       в маршрут 5-го или 4-го родительских городов привело бы к обра-
       зованию замкнутого подцикла.
Шаг 8. П1 = [2 5 8 6 9 1 4 7 3]. (Маршрут имеет вид:
       3→8→7→4→6→1→2→5→9 →3).
Кроссовер фрагментов
     Кроссовер subtour chunks создает потомков, выбирая (случайно) фраг-
мент от одного из родителей, затем случайной длины фрагмент от другого из
родителей, и т.д. И опять, если на каком-то уровне образуется замкнутый
цикл, он решается аналогичным образом (выбирается другой случайный
фрагмент, который еще не выбирался).
Эвристический кроссовер
      Heuristic crossovers строит потомков, выбирая случайный город как
стартовую точку для маршрута - потомка. Потом он сравнивает два соответ-
ствующих ребра от каждого из родителей и выбирает белее короткое. Затем
конечный город выбирается как начальный для выбора следующего более
короткого ребра из этого города. Если на каком-то шаге получается замкну-