Я построил алгоритм GA для решения TSP.
Это упражнение в книге Норвига (AIAMA). Он предложил нам прочитать точку зрения Ларраньяги на проблему представлений и тому подобное. Там я изучил некоторые операторы скрещивания и мутации и опробовал несколько из них, чтобы понять, какие из них мне больше подходят. Я также разработал фитнес-функцию, основанную на стоимости каждого пути.
Что ж, несмотря на все, что у меня есть вопрос о разработке моего алгоритма, я никогда раньше не работал с ИИ, поэтому я не знаю, подходит ли мой подход для ГА.
Вот что я сделал:
Я взял вектор путей (моя начальная популяция)
а затем в каждом цикле я упорядочивал этот вектор, увеличивая порядок затрат, выбирал лучшие пути X в этом векторе и удалял другие пути.
Затем я применяю XOver и Mutation (с определенной скоростью) и помещаю их в положение старых удаленных значений вектора.
Затем я делаю то же самое (заказать вектор - извлечь лучший и т.д.)
и продолжайте это делать, пока он не стабилизируется.
Это хороший подход? Если это не дайте мне немного севера. Потому что, когда я выбирал лучшие и не сохранял их (просто создал из них целую новую группу с помощью Xover и мутации), я не получил хороших результатов. Таким образом (сохраняя лучшие - в некоторых экспериментах я сохранял только САМОЕ лучшее) я получаю лучшие результаты, и результат всегда сходится и очень быстро.
Представление состояния: для представления состояния я решил использовать представление пути (я уже использовал его с самого начала и решил придерживаться его после того, как прочитал Ларраньягу и все остальное), оно выглядит следующим образом: если у нас есть, скажем, 5 городов и посетить первый город, затем второй, затем третий... наше представление пути будет (1, 2, 3, 4, 5)
Начальная генерация населения: на самом деле я генерирую случайные точки для представления городов (это то, что книга попросила меня сделать, генерировать случайные точки в замкнутом квадрате), но ради сравнения я создал население и придерживаюсь его при сравнении. результаты - я думаю, что если бы я не придерживался одной конкретной группы населения, я бы мало что знал о своих улучшениях
Наиболее подходящие люди : наиболее подходящие люди - это те, у кого самые лучшие расходы на поездку. (Я не знаю, должен ли я - в этой задаче - использовать что-то еще в качестве параметра
Кроссовер: я попробовал несколько операторов кроссовера и сравнил свои результаты с тем, что представлен в книге, и в итоге использовал один из Кроссоверов Порядка (Ларраньяга и др. (1999)): этот кроссовер берет два случайных разреза (формируя подпуть) из обоих родительские пути, а затем копирует остальную часть пути (еще не посещенные города внутри этого подпути) из другого родителя (начиная со второго разреза, а не с позиции «0») — добавляя города, которые они появляются в другом родитель.
пример: пути (1 2 3 4 5) (3 4 2 1 5) выбирая подпути (234) и (421), которые будут потомками (5 |2 3 4| 1) (5 |4 2 1| 3) ‹- часть внутри | | произошло от одного родителя, а другая часть от другого родителя
мутация: для мутации я выбрал подход IVM (Inversion Mutation). он берет подпуть из исходного пути и вставляет его обратно (инвертированный) в случайную точку.
пример: путь (1 2 3 4 5) подпуть ( 2 3 4 ) и случайная вставка после 5
генерировать : ( 1 5 | 4 3 2 )
