Метод алгоритма GA для TSP

Question

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

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

Ну, несмотря на все, что у меня есть вопрос о моем дизайне алгоритмов, я никогда не работал с AI, поэтому не знаю, подходит ли мой подход для GA.

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

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

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

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

Я тогда сделать то же самое (вектор заказа - извлечь лучшее и т.д.)

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

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

Государственное представление: для представления состояния я решил использовать представление пути (я был уже используя его с самого начала и решил придерживаться его после того, как я прочитал Larrañaga et all), это так: если у нас есть, скажем, 5 городов и посетите первый город, затем второй, затем третий ... наше представление пути было бы (1, 2, 3, 4, 5)

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

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

кроссовер: я пробовал некоторые операторы кроссовера и сравнивал мои повторные действия с представленным в книге и в итоге использовал один из Заказ CrossOvers (Larrañaga и др. (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 (инверсионная мутация). он берет суб-путь от исходного пути и вставляет его обратно (инвертируется) в случайную точку.

пример: путь (1 2 3 4 5) суб путь (2 3 4) и случайные вставки после 5

генерации: (1 5 | 4 3 2)

Answer 1

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

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

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

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

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

EDIT: Вы используете опубликованные алгоритмы, поэтому проблема не связана с конкретными операциями. Для фитнеса вы правы с дорогой.Вы говорите:

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

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

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

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