Всем доброго времени суток!
Уже достаточно давно изучаю материалы по ГА, но написать свою реализацию решился только сейчас )))
Реализация написана на Матлабе.
В качестве задачи взял классическую задачу коммивояжера.
Начальные условия такие:
- сколько-то городов (задается);
- один коммивояжер;
- максимальная дистанция между двумя соседними городами (для генерации начальной популяции);
- размер эволюции (количество поколений);
- количество особей;
- коммивояжер каждый город может посетить только один раз;
Генная структура хромосомы такая: (далее все примеры будут для 5 городов)
X X X X X, где Х - номер города, например: 1 4 2 3 5. Таким образом, коммивояжер, выйдя и 1 города, в него же и вернется. Хромосомы генерируются с учетом условия однократного посещения каждого города, так что повторов в генах нет.
Сразу оговорюсь что пока решил гены не кодировать в двоичный формат.
Однако, при написании кроссовера столкнулся с интересной (для меня на данном этапе
) проблемой. Если, например, два родителя имеют хромосомы:
X1 = 3 4 2 1 5;
X2 = 5 2 1 4 5;
И если точка разрыва хромосомы пришлась так, что для формирования потомка берутся гены:
X1(1,2) и X2(3,4,5), то потомок будет выглядеть следующим образом:
Y = 3 4 1 4 5.
Как видим, в хромосоме потомка появляется дублирующий ген (со значением 4). Применительно к пути коммивояжера это некорректно, так как получается, что он дважды посетит город с номером 4, что несоответствует условиям задачи.
Я сделал так, что сейчас повторные гены (в слуае, если они есть, конечно же) заменяются так, чтобы в хромосоме потомка не было дублей. Таким образом, хромосома Y в данном примере будет выглядеть так:
Y = 3 4 1 2 5.
Тут у меня возникает вопрос. Так как я пока не храню гены в двоичном формате, а работаю сразу с реальными числами, то правильно ли делать так как делаю я (я имею в виду кроссовер)? И даже, если кодировать в бин, то все равно могут появляться дубли...
И еще вопрос. Как в таком случае реализовать мутацию? Я думаю, что достаточно просто менять местами два случайно выбранных гена в хромосоме потомка.
И вопрос третий. Я пока не очень понял следующий момент. Если, допустим, было 50 родителей, и после скрещивания каждой пары появляется ОДИН потомок, то получается, что очень быстро уменьшается объем популяций. В моем случае это выливается в то, что фитнесс-функция не успевает максимизироваться до приемлемого (по результатам опытов) значения. Так что сейчас я порождаю ДВУХ потомков, обеспечивая тем самым поддержание численности особей на уровне первоначальной популяции. Благодаря этому фитнесс-функция в конце всей эволюции у всех конечных особей получается примерно одинакова (различается в числах после запятой). А теперь вопрос: существуют ли какие-то критерии выбора количества потомков? Или какие-то правила?
Заранее спасибо всем за ответы!!!