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

                                       18
 Функция приспособленности
     Значение функции приспособленности должно соответствовать рас-
стоянию, которое проходит коммивояжер согласно пути, представляемого
хромосомой.
Поскольку это значение должно быть минимально, то конечная формула
функции приспособленности j-й хромосомы часто выглядит следующим об-
разом: f j = d max ⋅1,1 − d j , где d max � � длина максимального маршрута в те-
кущей популяции d j    � �     длина маршрута, представляемого j-й хромосо-
мой.
Значение этой функции чем больше, тем лучше.
Кодирование решений
В настоящее время существует четыре основных представления маршрута
коммивояжера в виде хромосомы: соседское, порядковое, путевое и мат-
ричное. Поскольку классические операторы скрещивания и мутации для них,
как правило, неприменимы, каждое из этих представлений имеет собствен-
ные "генетические" операторы, все они очень сильно различаются. Некото-
рые из рассмотренных ниже кроссоверов могут создавать потомство, не
имеющее решения (невалидные решения). Невалидные решения могут быть
полезны для создания и внесения разнообразия в популяцию, однако этим
они могут замедлить или даже предотвратить сходимость ГА. Одним из ре-
шений этой проблемы может стать идея восстановления невалидных реше-
ний.
                             1. Соседское представление
      Соседское представление представляет маршрут как список из n горо-
дов. Город j находится на позиции i только в том случае, если маршрут про-
ходит из города i в город j. Например, маршрут со следующим порядком
обхода городов: 1→2→4→3→8→5→9→6→7→1 представляется как хромо-
сома P=[2 4 8 3 9 7 1 5 6].
 Каждый маршрут имеет только одно соседское представление, но не каж-
дый вектор в соседском представлении соответствует какому-либо маршру-
ту. Например, вектор [2 4 8 1 9 3 5 7 6] обозначает последовательность
1→2→4→1..., т.е. часть маршрута � � это замкнутый цикл, что недопусти-
мо.
      Соседское представление не поддерживает классическую операцию
кроссовера (он практически всегда порождает недопустимые маршруты).
Для него разработаны три собственных оператора.
Кроссовер альтернативных ребер
     Кроссовер alternating edges строит потомков, выбирая поочередно
первое ребро от первого родителя, потом второе ребро от второго, потом