Разработка архитектуры гибридного алгоритма

Обобщенная схема гибридного алгоритма выглядит следующим образом:

Задача VRP состоит из двух задач: задачи упаковки и задачи коммивояжера. Задача упаковки представляет собой задачу разбиения графа. Для нее будем использовать модифицированный пчелиный алгоритм, который доказал свою эффективность. Далее будем использовать вложенную схему гибридизации алгоритмов — генетического и муравьиного.

В этом случае крепко связаны идеи коллективной адаптации (МА) и эволюционного подхода (ГА). В течение каждой итерации муравьи в соответствии с МА оставляют феромоны, проходя по своему маршруту. Муравей делает выбор на основании «личного» (выбор кратчайших «зримых» вершин) и «коллективного» опыта текущего поколения (согласно отложенным колонией феромонам). Но при небольшой размерности колонии это вероятно приведет к преждевременной сходимости. Чтобы этого избежать, можно увеличить размерность колонии. Однако размерность колонии сильно влияет на время работы алгоритма.

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

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

Также в данном подходе ключевым моментом является определение длительности жизни поколения. Дело в том, что чем дольше живут муравьи, тем больше они ориентируются на свой опыт, а не на знания предыдущих поколений. Поэтому изначально заложенные знания от родителей теряются со временем (в течение одной жизни). Если же длительности эволюции и жизни одного поколения равны, то гибридный алгоритм вырождается до муравьиного. Чем меньше продолжительность жизни муравьи, тем большее значение имеют эволюционные механизмы (ГА).

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

Однако недостатком подхода, представленного на рисунке выше, является значительное увеличение вычислительной сложности алгоритма. Поэтому будем использовать оператор кроссинговера в муравьином алгоритме. Размерность колонии при этом не изменится, но будут сгенерированы дополнительные решения. Муравьи будут исследовать новые маршруты, полученные этим оператором, и откладывать на них феромоны. Это позволяет лучше избегать локального оптимума, при этом вычислительная сложность не изменится. Структурная схема данного подхода приведена ниже: