Антагонизм в генетических алгоритмах для коммивояжера Проб. среди противоположных путей по тому же маршруту
Я почти уверен, что мой вопрос должен быть расследован, но мне не хватает жаргона, который поможет мне искать литературу. Я пишу генетический алгоритм, который решает тип задачи коммивояжера (TSP). Как и в стандартном TSP, мой вариант не имеет понятия ориентации. В стандартном TSP, поскольку существует требование сформировать цепь обратно в начальный город, для любого оптимального решения должно быть 2 одинаково оптимальных маршрута, которые являются только 2 противоположными маршрутами вокруг этого канала.
В генетическом алгоритме я бы предположил, что иногда появляются хорошие решения для одного и того же (или сходного) маршрута, но закодированные в разных направлениях в разных генотипах. Я также предположил бы, что большинство пересечений между этими противоположными маршрутами будут иметь тенденцию противодействовать друг другу, поскольку я имею в виду, что их потомство будет непригодным, потому что они пытаются оптимизировать один и тот же / похожий маршрут только с противоположных направлений. Два генотипа будут подниматься на один и тот же холм только с противоположных сторон. Казалось бы, эта проблема замедлит поиск.
Верны ли мои предположения выше? Знаете ли вы, какой жаргон использовал для описания этой проблемы, или какие-нибудь хитрости, которые помогают обойти это? В идеальном мире вам бы хотелось, чтобы два подходящих, но почти противоположных генотипа были закодированы или пересечены таким образом, чтобы они сохраняли общую структуру маршрута независимо от ориентации.
1 ответ
Для GA и TSP я предполагаю, что вы используете перестановочную кодировку ваших хромосом.
Теперь, предполагая, что единственный отдельный путь является оптимальным - это обычно так; т.е. нет вырождения среди оптимальных решений --- обратная циклическая перестановка также будет оптимальной. То же самое верно для одного и того же пути с разными стартовыми городами; для n городов одни и те же различные пути могут быть найдены в 2*n различного рода кодировках перестановок в ваших хромосомах (2 для обратной циклической последовательности, n для первого входа = начальный город в хромосоме).
На практике, однако, это не проблема. Число неоптимальных путей настолько велико, что возможный эффект "антагонизма" между обратными циклическими хорошими путями на практике будет несуществующим.
Однако, очень важная проблема, о которой вы, возможно, уже хорошо знаете, - это способ кроссовера. При кодировании с перестановкой простой кроссовер приведет к невозможным путям, поэтому кодирование должно выполняться с учетом того, что полученные дочерние хромосомы все еще описывают действительные перестановки TSP.
Упаковать; Вы должны беспокоиться об антагонизме по отношению к циклическим обратным путям, так как на практике это не проблема. Вместо этого сосредоточьтесь на изучении методов кроссовера различий.
См., Например, Генетический алгоритм для задачи коммивояжера с использованием оператора последовательного конструктивного кроссовера.
Последнее замечание: исходно из опыта классической оптимизации, сначала мне было трудно принять "на практике..." утверждения относительно методов стохастической оптимизации, таких как генетические алгоритмы или оптимизация колоний муравьев, и так далее. Но я научился признавать, что для этих методов выражения "на практике...", как правило, являются лучшими, к которым мы стремимся, поскольку эти методы по своей природе не являются детерминированными.