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

                                    20
тый маршрут, он продолжается любым случайным городом, который еще не
посещался.
     Преимущества соседского представления в том, что оно позволяет схе-
матически анализировать создаваемые маршруты. Это представление имеет
в основании "строящие блоки" – связи между городами. Например, схема (
* * * 3 * 7 * * * ) описывает множество всех маршрутов с ребрами (4→3) и
(6→7). Основной же недостаток данного представления - в том, что множе-
ство всех его операций очень бедно. В частности, для него не существует
простых алгоритмов мутации. Кроссовер alternating edges часто разрушает
хорошие маршруты, которые были у обоих родителей до применения этой
операции. Кроссовер subtour chunks имеет лучшие характеристики, чем пер-
вый, благодаря тому, что его разрушительные свойства меньше. Но все рав-
но его эксплуатационные качества все же достаточно низки. Кроссовер
heuristic crossover, конечно же, наилучший оператор для данного представ-
ления. Причина в том, что предыдущие операции слепы, они не берут в рас-
чет настоящую длину ребер. С другой стороны, heuristic crossover выбирает
лучшее ребро из двух возможных. Может получиться, что дальнейший путь
будет невозможен и придется выбирать ребро, длина которого неоправданно
большая.
                       2. Порядковое представление
       Порядковое представление определяет маршрут как список из n горо-
дов; i-й элемент списка � � номер от 1 до n-i-1. Идея порядкового представ-
ления состоит в следующем. Есть упорядоченный список городов, который
служит для связи маршрутов с их порядковым представлением. Предполо-
жим, что такой упорядоченный список прост: C = [1 2 3 4 5 6 7 8 9]. Тогда
маршрут 1→2→4→3→8→5→9→6→7→1 будет представлен как список :
L=[1 1 2 1 4 1 3 1 1].
Он может быть интерпретирован следующим образом.
• Так как первый номер списка L равен 1, берем первый город из списка С
   как первый город маршрута (город номер 1) и исключаем его из списка.
   Текущий фрагмент маршрута � � это 1.
• Следующий номер в списке L также 1, поэтому берем первый номер из
   оставшегося списка C=[ 2 3 4 5 6 7 8 9]. Так как мы исключили из списка
   С 1-й город, следующий город - 2. Исключаем и этот город из списка.
   Маршрут на данном шаге приобретает вид: 1 → 2.
• Следующий номер в списке L- 2. Берем из списка С = [ 3 4 5 6 7 8 9] 2-ой
   по порядку оставшийся город. Это - 4. Исключаем его из списка. Мар-
   шрут: 1 → 2 → 4.
• Следующий номер в списке L - 1. Берем из списка С =[ 3 5 6 7 8 9] 1-й го-
   род – с номером 3. Имеем маршрут : 1 →2 → 4 → 3.