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

Question

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

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

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

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

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

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

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

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

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

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

Представление состояния: Для представления состояния я решил использовать представление пути (я уже использовал его с самого начала и решил придерживаться его после прочтения Larrañaga и др.), это так: если мы имеем, скажем, 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) <- часть внутри | | пришел от одного родителя, а другая часть от другого родителя </p>

мутация: Для мутации я выбрал подход 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 итерацию вы экономите с меньшими затратами. После построения графика она должна выглядеть примерно так: