получиться так, что один город окажется в маршруте не один раз, что противоречит зада-
че. Подойдем к этой проблеме несколько иначе. Пусть число на j-ом месте означает не
номер следующего города в маршруте, а номер города из оставшихся (не пройденных) го-
родов. Так для нашего примера сначала 0-вой город, затем число 3 (11) показывает номер
следующего города из оставшихся 1,2,3 (для 1-ого города номер 0, для 2 – 1 и для 3 – 2),
так как число 3 превышает максимальный номер из оставшихся, то будем использовать
вместо него остаток от деления его же на число оставшихся городов: 3 mod 3 = 0, то есть
следующим городом в маршруте будет оставшийся город с номером 0, то есть 1-ый город,
и так далее. Таким образом, при данном подходе не будет иметь место ситуация, когда
один город окажется в маршруте не один раз. Заметим, что число на последнем месте
хромосомы (самое левое) вовсе не нужно, так как остается один город (после прохожде-
ния трех), кодировать который нет необходимости. И еще важная поправка к хромосоме,
заключается в том, что для кодирования очередного города необходимо не то количество
бит, которое необходимо для хранения общего числа городов, а то, которое достаточно
для кодирования числа оставшихся городов. Например, хромосома «01_10_11_00» преоб-
разуется к виду (для того же маршрута) «1_10_00».
В результате мы уменьшили размер хромосомы с 8 бит до 5, что, во-первых, позво-
ляет сэкономить оперативную память, во-вторых, уменьшить число возможных вариантов
решения задачи (а также исключить невозможные «решения»). Второе качество является
очень важным, так как эффективность генетического алгоритма тем выше, чем ниже чис-
ло вариантов решения. Если одни города не имеют связи с некоторыми другими, то это
также сокращает число вариантов решения.
Следующий этап построения генетического алгоритма – разработка так называе-
мой фитнес-функции. Эта функция является единственной частью программы, которая
должна понимать то, что действительно кодирует хромосома, и возвращать число, которое
можно сопоставить с выживаемостью индивидуума в природе. Используя эту функцию,
мы можем определить, насколько хорошо приспособлен индивидуум (насколько длинный
маршрут). Так как количественной характеристикой решения в нашей задаче является
длина пути, то примем в качестве значения фитнес-функции выражение «1/длина пути»
(чем выше длина маршрута, тем ниже приспособленность).
Сначала генерируется определенное количество хромосом со случайными значе-
ниями (это количество обычно несколько сотен или тысяч). Результатом данного этапа
является создание начальной популяции. Далее реализуется жизненный цикл популяции
(случайное скрещивание, мутация) и отбор. Продолжать это нужно либо определенное
количество раз (сотни, тысячи раз), или до тех пор, пока приспособленность не будет зна-
чительно изменяться.
Для каждой пары хромосом определяется
случайным образом, будут ли они скрещиваться.
Операция кроссовера предполагает выбрать также
случайным образом, точку кроссовера. После этого
две хромосомы обмениваются старшими частями
(слева от точки кроссовера).
точка кроссовера
101 11
011 00
исходные
011 11
101 00
результат
Рис. 2.9 – Кроссовер хромосом
Например, даны две хромосомы: «10111» и
«01100». Точка кроссовера может быть 1, 2, 3 или 4
(исходя из размера хромосомы – 5 бит). Пусть
случайным образом определена точка 2, таким
образом, хромосомы преобразуются в другие (рис. 2.9).
Дальнейший этап – это мутация. Частота мутации обычно очень низкая – отвечаю-
щая за нее виртуальная монетка должна падать орлом вверх один раз за сто или тысячу
21