Алгоритм подхода GA для TSP

Question

Я построил алгоритм GA для решения TSP.

Это в упражнении в книге Норвига (AIAMA). Он предложил, чтобы мы прочитали взгляд Ларраньяги на проблему для представлений и тому подобное. Я изучил некоторые перекрестные операторы и мутации там и опробовал несколько из них, чтобы увидеть, что подходит мне лучше. Я также разработал фитнес-функцию, основанную на стоимости каждого пути.

Что ж, несмотря на все, что у меня есть вопрос по поводу разработки моего алгоритма, я никогда раньше не работал с ИИ, поэтому я не знаю, является ли мой подход правильным для ГА.

Вот что я сделал:

Я взял вектор путей (мое первоначальное население)

и затем в каждом цикле я организовывал этот вектор, увеличивая порядок затрат, выбирая лучшие X-пути в этом векторе и удалял другие пути.

Затем я применяю XOver и Mutation (с определенной скоростью) и помещаю их в положение старых удаленных значений вектора.

Затем я делаю то же самое (заказываю вектор - лучше всего извлекаю и т.д.)

и продолжайте делать это, пока не стабилизируется.

Это хороший подход? Если это не даст мне немного севера. Потому что, когда я выбрал лучших и не сохранил их (просто создал из них совершенно новый поп, через Xover и мутации), я не получил хороших результатов. Таким образом (сохраняя лучшие - в некоторых экспериментах я оставлял только лучшие), у меня лучшие результаты, и результат всегда сходится и быстро

Представление состояний: Для представления состояний я решил использовать представление пути (я уже использовал его с самого начала и решил придерживаться его после того, как прочитал "Ларраньяга и др."), Это выглядит следующим образом: если у нас есть, скажем, 5 городов и посетите первый город, затем второй, затем третий... наше представление пути будет (1, 2, 3, 4, 5)

Начальное поколение населения: На самом деле, я генерирую случайные точки для представления городов (это то, о чем меня просила книга, генерировать случайные точки в замкнутом квадрате) - но для сравнения я создал население и придерживаюсь его при сравнении результаты - я думаю, что если бы я не придерживался одной конкретной группы населения, у меня не было бы много информации о моих улучшениях

Наиболее подходящие люди: Наиболее подходящие люди - те, которые имеют лучшую стоимость путешествия. (Я не знаю, должен ли я - в этой проблеме - использовать что-то еще в качестве параметра

кроссовер: я попробовал несколько операторов кроссовера и сравнил свои результаты с представленной в книге, и в итоге использовал один из кроссоверов Order ( Larrañaga et al(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)

Answer 1

Прежде всего, избегайте всех этих сокращений (GA, TSP, XOver). Трудно читать, и некоторые люди могут не иметь представления о чем вы говорите. Первая проблема с генетическим алгоритмом - как выбрать исходную популяцию, как выполнить кроссовер, как выполнить мутацию. Вторая проблема заключается в том, что наивное понимание описания может быть ужасным.

Для вас лучше всего подходят те, у кого стоимость уже выше. Вы можете утверждать, что было бы лучше взять самых разных людей, то есть тех, которые с большей вероятностью исследуют разные части проблемного пространства. Опишите, как вы выполняете следующие операции:

• Государственное представительство: просто чтобы убедиться
• Начальное поколение населения: действительно важно. Возможно, есть материалы, доступные для этого шага, как это обычно бывает с локальными алгоритмами поиска.
• лучше всего подходит людям: я предлагаю вам попробовать играть здесь больше. Попробуйте разные стратегии. Вы ищете лучшее, пригодное для воспроизведения, а не для общего решения проблемы.
• кроссовер: как ты это делаешь?
• Мутация. Цель мутации - уклониться от текущей области проблемного пространства, и вы можете создать человека с очень высокой стоимостью. С вашим текущим алгоритмом на следующем шаге он будет исключен при сортировке

Вам также необходимо оценить, как ваше решение улучшается с течением времени. Например, а не n итерации вашего обеспечения 100n, решение становится лучше, насколько? Насколько похожи друг на друга люди последнего поколения, когда алгоритм останавливается и т. Д.

Другой вопрос, вы пытаетесь решить его для фиксированной топологии или переменной топологии?

РЕДАКТИРОВАТЬ: Вы используете опубликованные алгоритмы, поэтому не похоже, что проблема в конкретных операциях. Для фитнеса вы правильно придерживаетесь стоимости пути. Ты говоришь

Потому что, когда я выбрал лучших и не сохранил их (просто создал из них совершенно новый поп, через Xover и мутации), я не получил хороших результатов. Таким образом (сохраняя лучшие из них - в некоторых экспериментах я оставлял только лучшие), я получаю лучшие результаты, и результат всегда сходится и быстро идет.

Вы должны держать лучших людей и их детей. Это следовать злому принципу природы, Только лучшие имеют право воспроизводить. Те, которые должны быть заменены, являются наименее подходящими людьми.

Есть 3 параметра, которые вы можете настроить: пропорция наиболее подходящего индивидуума, у которого есть дети (также будет исключено количество индивидуумов), вероятность мутации и количество прогонов.

Чтобы проверить, как работает ваш алгоритм, вы можете выбрать лучшее решение по итерациям, т.е. t итерацию вы экономите на более низкой стоимости. После того, как построено это должно выглядеть так: