В продолжение к моей первой статье решил написать эту, в которой расскажу про более продвинутые алгоритмы поиска гамильтонова цикла в большом полном графе
Рекомендую тем, кто не читал первую статью, прочитать ее, потому что это продолжение, а ни в коем случае не независимая статья.
Идея данного алгоритма впервые пришла в голову к Марко Дориго, который предложил данный алгоритм в 1992 году.
Алгоритм относят к метаэвристическим оптимизациям.
Наблюдали за муравьями в детстве? Ну хотя бы раз? Муравьи обычно ходят за едой. Далеко. Но как они говорят друг другу, куда же идти за едой? Ведь каждый раз искать заново невыгодно, если где-то там вчера какой-то муравей нашел, например, яблоко. Вот тот муравей, который нашел яблоко, на пути домой помечает дорогу феромонами. Так, чуть чуть, он же ведь всего один. На следующий день там пойдут n муравьев, каждый найдет еду, и пометит дорожку. На дорожке больше феромонов, и вероятность того, что следующие муравьи пойдут по ней, растет.Однако феромоны испаряются, и через несколько дней от пометок на дорожке не останется и следа.И чем длиннее дорожка, тем быстрее она разрушится. На этом факте из муравьиной жизни и построен данный алгоритм.
Пример того, что по самой короткой дорожке будут за единицу времени пробегать больше муравьев, и в конце концов, на всех остальных феромоны испарятся, а на этой нет, она и станет путем для всей колонии.
Как это применить к задаче коммивояжера?
Берем метод ветвей и границ, который я описывал в первой статье, и делаем следующие изменения:
1)Если мы в дереве выбора брать/не брать ребро пошли по одному из путей, «положим» на путь из корня до этой вершины некое число феромонов.
2)На каждом ребре феромоны всех путей через это ребро складываются.
3)На каждой итерации алгоритма количество феромонов на каждом пути уменьшается на какое-то количество процентов.
4)При выборе следующей вершины руководствуемся не только ее оценкой затрат, но и количеством феромонов на пути к ней.
Алгоритм считается одним из наиболее эффективных полиномиальных алгоритмов для посика гамильтонова цикла на больших графах.
Имея написанный метод ветвей и границ, прикрутить к нему простейший вариант муравьиной колонии довольно просто, сложность только в верном подборе констант на скорость испарения, сколько феромонов положить, если мы прошли и т.д.
Выигрыш у жадины ~17%, время работы — около часа.
Основным источником идей для этого алгоритма выступает биологическая эволюция.
Основной упор в этом алгоритме делается на так называемый оператор скрещивания, который производит рекомбинации решений-кандидатов.
1)Главное требование — храним решение как вектор чего-нибудь(битов, чисел, символов)
В нашей задаче будем хранить в i-ой ячейке номер вершины, в которую мы из этой i-ой ячейки идем.
2) Новые решения, из которых мы будем выбирать с решения для скрещивания, будем получать как результат мутаций старых решений и скрещивания.
3)Мутация определяется как функция, которая случайно меняет некоторые гены(ячейки массива в нашем случае), и результат закладывается во множество решений.
4)Скрещивание определяется как комбинация(случайная) генов нескольких лучших решений из предыдущей итерации.
5)На каждом этапе мы должны выкидывать неприспособленные решение — те, которые банально не являются гамильтоновым циклом.(например, содержат два цикла размером 250)
6)Решения для мутаций выбираются случайно с некоторой вероятностью.
7)Решения для скрещивания выбираются опять же случайно, но лучшие решения, полученные к данной итерации(у которых вес цикла меньше) должны иметь большую вероятность.
Если жалко памяти на каждом этапе можно выкидывать самые худшие из приспособленных решений.
Наиболее простой способ запустить такой алгоритм- сначала предоставить ему некоторое множество корректных решений, например, данных нам жадиной, запущенной из разных вершин.
Состояние остановки-некоторые параметры алгоритма, которые говорят, что пора заканчивать считать и надо вывести ответ(лучшее решение на данный момент)
В моем случае параметром остановки был time limit.
Простейшая реализация работала за 2 часа и выиграла у жадины всего ~4%
Стоит отметить, что это связано во многом из-за простейшей реализации, многие источники утверждают, что генетический алгоритм один из лучших, если не лучший.
С этим вообще много проблем, т.к. половина источников говорит, что рекордсмен на данный момент ACO, половина — что генетика.
p.s. продолжение написано во многом благодаря комментариям к первой статье, что сподвигло меня попробовать написать хотя бы простейшие реализации этих алгоритмов, за что спасибо mephistopheies и Diversus
Рекомендую тем, кто не читал первую статью, прочитать ее, потому что это продолжение, а ни в коем случае не независимая статья.
1.Муравьиный алгоритм, он же Ant Colony Optimization(ACO)
Идея данного алгоритма впервые пришла в голову к Марко Дориго, который предложил данный алгоритм в 1992 году.
Алгоритм относят к метаэвристическим оптимизациям.
Идея алгоритма
Наблюдали за муравьями в детстве? Ну хотя бы раз? Муравьи обычно ходят за едой. Далеко. Но как они говорят друг другу, куда же идти за едой? Ведь каждый раз искать заново невыгодно, если где-то там вчера какой-то муравей нашел, например, яблоко. Вот тот муравей, который нашел яблоко, на пути домой помечает дорогу феромонами. Так, чуть чуть, он же ведь всего один. На следующий день там пойдут n муравьев, каждый найдет еду, и пометит дорожку. На дорожке больше феромонов, и вероятность того, что следующие муравьи пойдут по ней, растет.Однако феромоны испаряются, и через несколько дней от пометок на дорожке не останется и следа.И чем длиннее дорожка, тем быстрее она разрушится. На этом факте из муравьиной жизни и построен данный алгоритм.
Пример того, что по самой короткой дорожке будут за единицу времени пробегать больше муравьев, и в конце концов, на всех остальных феромоны испарятся, а на этой нет, она и станет путем для всей колонии.
Как это применить к задаче коммивояжера?
Берем метод ветвей и границ, который я описывал в первой статье, и делаем следующие изменения:
1)Если мы в дереве выбора брать/не брать ребро пошли по одному из путей, «положим» на путь из корня до этой вершины некое число феромонов.
2)На каждом ребре феромоны всех путей через это ребро складываются.
3)На каждой итерации алгоритма количество феромонов на каждом пути уменьшается на какое-то количество процентов.
4)При выборе следующей вершины руководствуемся не только ее оценкой затрат, но и количеством феромонов на пути к ней.
Алгоритм считается одним из наиболее эффективных полиномиальных алгоритмов для посика гамильтонова цикла на больших графах.
Имея написанный метод ветвей и границ, прикрутить к нему простейший вариант муравьиной колонии довольно просто, сложность только в верном подборе констант на скорость испарения, сколько феромонов положить, если мы прошли и т.д.
Выигрыш у жадины ~17%, время работы — около часа.
Генетический алгоритм
Идея алгоритма
Основным источником идей для этого алгоритма выступает биологическая эволюция.
Основной упор в этом алгоритме делается на так называемый оператор скрещивания, который производит рекомбинации решений-кандидатов.
1)Главное требование — храним решение как вектор чего-нибудь(битов, чисел, символов)
В нашей задаче будем хранить в i-ой ячейке номер вершины, в которую мы из этой i-ой ячейки идем.
2) Новые решения, из которых мы будем выбирать с решения для скрещивания, будем получать как результат мутаций старых решений и скрещивания.
3)Мутация определяется как функция, которая случайно меняет некоторые гены(ячейки массива в нашем случае), и результат закладывается во множество решений.
4)Скрещивание определяется как комбинация(случайная) генов нескольких лучших решений из предыдущей итерации.
5)На каждом этапе мы должны выкидывать неприспособленные решение — те, которые банально не являются гамильтоновым циклом.(например, содержат два цикла размером 250)
6)Решения для мутаций выбираются случайно с некоторой вероятностью.
7)Решения для скрещивания выбираются опять же случайно, но лучшие решения, полученные к данной итерации(у которых вес цикла меньше) должны иметь большую вероятность.
Если жалко памяти на каждом этапе можно выкидывать самые худшие из приспособленных решений.
Наиболее простой способ запустить такой алгоритм- сначала предоставить ему некоторое множество корректных решений, например, данных нам жадиной, запущенной из разных вершин.
Состояние остановки-некоторые параметры алгоритма, которые говорят, что пора заканчивать считать и надо вывести ответ(лучшее решение на данный момент)
В моем случае параметром остановки был time limit.
Простейшая реализация работала за 2 часа и выиграла у жадины всего ~4%
Стоит отметить, что это связано во многом из-за простейшей реализации, многие источники утверждают, что генетический алгоритм один из лучших, если не лучший.
С этим вообще много проблем, т.к. половина источников говорит, что рекордсмен на данный момент ACO, половина — что генетика.
p.s. продолжение написано во многом благодаря комментариям к первой статье, что сподвигло меня попробовать написать хотя бы простейшие реализации этих алгоритмов, за что спасибо mephistopheies и Diversus
