ЭВОЛЮЦИОННЫЙ ПОПУЛЯЦИОННЫЙ МЕТОД РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

Аннотация

Рассматривается эволюционный популяционный метод решения транспортной за- дачи на основе метаэвристики кристаллизации россыпи альтернатив. Исследуется за- крытая (или сбалансированная) модель транспортной задачи: сумма груза у поставщиков равно общей сумме потребностей в пунктах назначения. Цель оптимизации – минимизация стоимости (достижение минимума затрат на перевозку) или расстояний и критерий вре- мени (затрачивается минимум времени на перевозку). В основу метаэвристики кристалли- зации россыпи альтернатив положена стратегия, основанная на запоминании и повторе- нии прошлых успехов. Стратегия делает упор на «коллективную память», под которой подразумевается любой вид информации, которая отражает прошлую историю развития и хранится независимо от индивидуумов. В качестве кода решения транспортной задачи рассматривается упорядоченная последовательность Dk маршрутов. Объектами являют- ся маршруты, альтернативами – множество позиций P в списке, где np – число позиций в списке Dк. Множество объектов Dк соответствует множеству всех маршрутов. Множе- ство альтернативных состояний P объекта соответствует множеству альтернативных вариантов размещения объекта списке Dк. Работа популяционного эволюционного алго- ритма кристаллизации россыпи альтернатив опирается на коллективную эволюционную память, называемую россыпью альтернатив. Под россыпью альтернатив решения в рабо- те называется структура данных, используемая в качестве коллективной эволюционной памяти, несущая информацию о решении, включающую сведения о реализованных альтер- нативах агентов в данном решении и о полезности решения. Разработан конструктивный алгоритм формирования опорного плана путем декодирования списка Dк. На каждом шаге t решается задача выбора очередного в последовательности Dк маршрута и определения количества груза, перевозимого из пункта отправления Ai в пункт назначения Bj по этому маршруту. Разработанный алгоритм является популяционным, реализующим стратегию случайного направленного поиска. Каждый агент является кодом некоторого решения транспортной задачи. На первом этапе каждой итерации l конструктивным алгоритмом на базе интегральной россыпи альтернатив формируется nk кодов решений Dk.Формирование каждого кода решения Dk выполняется последовательно по шагам путем последовательного выбора объекта и позиции. Для построенного кода решения Dk рассчи- тывается оценка решения ξk и оценка полезности δk. Формируется индивидуальная рос- сыпь альтернатив Rk и переход к построению следующего кода решения. На втором этапе итерации производится суммирования интегральной россыпи альтерна- тив, сформированной на предыдущих итерациях от l до (l-1), cо всеми индивидуальными россыпями альтернатив, сформированных на итерации l. На третьем этапе итерации l производится снижение всех интегральных оценок полезности r*αβ интегральной россыпи альтернатив R*(l) на величину δ*. Алгоритм решения транспортной задачи был реализован на языке С++ в среде Windows. Сравнение значений критерия, на тестовых примерах, сизвестным оптимумом показало, что у 90% примеров полученное решение было оптималь- ным, у 2% примеров решения были на 5% хуже, а у 8% примеров решения отличались ме- нее, чем на 2%. Временная сложность алгоритма, полученная экспериментальным путем, лежит в пределах О(n2).