Конструирование приближенных алгоритмов

Размещено на http://www.allbest.ru/

Оглавление

Введение

Глава 1

1.1 NP-полнота

1.2 Задача маршрутизации транспорта

1.3 Построение математической модели

1.4 Способы решения задач маршрутизации

Глава 2

2.1 Обзор алгоритмов

2.1.1 Муравьиный алгоритм

2.1.2 Particle Swarm Optimization (PSO)

2.1.3 Artificial Bee Colony

2.1.4 Меметические алгоритмы

2.2 Биоиспирированные алгоритмы в задачах VRP

2.2.1 Разработка модифицированного муравьиного алгоритма для решения VRP

2.2.2 Разработка пчелиного алгоритма

2.3 Разработка гибридного алгоритма

2.4 Экспериментальная часть

Заключение

Список использованной литературы

меметический муравьиный маршрутизация транспорт



Введение

Многие задачи, которые интересны с практической точки зрения, имеют полиномиальные алгоритмы решения. Это значит, что время работы алгоритма на входе длины n составляет не более O(nk) для некоторой константы k, при этом k не зависит от длины входа. Однако далеко не каждая задача имеет алгоритм решения, который удовлетворял бы данному свойству. Более того, существуют задачи, для которых имеется решающий их алгоритм, но он работает «долго». Алгоритмы, трудоемкость которых не ограничена полиномом от длины входа, называются экспоненциальными.

Рассмотрим задачи, называемые NP-полными. Для таких задач не найдены полиномиальные алгоритмы, но и не доказано, что таких алгоритмов не существует. Изучение NP-полных задач связано с так называемым вопросом «P = NP». Этот вопрос был поставлен в 1971 году и является сейчас одной из наиболее сложных проблем теории вычислений.

В работе особое внимание уделено VRP. В различных областях коммерции доля расходов на транспортировку может составлять вплоть до 35% от стоимости продукта. Более того, объем рынка автомобильных перевозок за последние пять лет вырос более чем в два раза. То есть к операторам услуг грузоперевозок и на производителям товаров предъявляются высокие требования, так как оптимизация данных процессов в действительности становится серьезным конкурентным преимуществом. Поэтому ключевая задача в логистике - это нахождение оптимальных маршрутов для транспортных средств. В области комбинаторной оптимизации это одна из наиболее сложных задач. Следует отметить, что эта задача не является новой. Математическая постановка такой задачи упоминалась более 50 лет назад. Она была поставлена в работах G. B. Dantzig и J. H. Ramser и была связана с составлением оптимальных маршрутов для парка транспортных средств с целью обслуживания определенного количества клиентов. Такой вид задач интересен не только с точки зрения практического применения, но и с точки зрения сложности решения. Это NP-полная задача. Над задачей в свое время работали D. Vigo, B. Golden, P. D. Christofides, G. Laporte, Е. М. Бронштейн, В. Г. Дейнеко, Э. Х. Гимади. Следует отметить, что существуют различные модификации задачи VRP - CVRP, VRPTW, MDVRP, SVRP и другие. Такие постановки задачи точнее отражают реальные требования к доставке, предъявляемые клиентами (например ограниченный промежуток времени). Данные модификации включают в себя различные дополнительные ресурсные ограничения.



Глава 1

1.1 NP-полнота

В теории NP-полноты рассматриваются только задачи разрешения. Это задачи, в которых поставлен вопрос и на него следует ответить «да» или «нет». Такую задачу рассматривать как функцию, которая отображает множество условий I во множество {0, 1}. К примеру, задача разрешения связана с задачей поиска кратчайшего пути в графе: «по заданному графу G = (V, E), паре вершин u, v ? V и натуральному числу k определить, существует ли в G путь между вершинами u и v, такой что его длина не превосходит k».

Встречаются и задачи оптимизации. В них необходимо минимизировать или максимизировать значение некоторой величины. До постановки вопроса об их NP-полноте, такие задачи следует преобразовать в задачи разрешения. То есть, в задаче о поиске кратчайшего пути в графе был выполнен переход от задачи оптимизации к задаче разрешения, т.к. было добавлено ограничение на длину пути.

Будем называть задачу полиномиальной, если существует константа k и некоторый алгоритм, который решает эту задачу за время O(nk), т.е. полиномиальное время. Рассмотрим определения классов P и NP:

Сложностной класс P -- это множество всех строковых задач разрешения. Решение для них может быть найдено за полиномиальное время, т. е. за время O(nk), при этом k не зависит от входа.

Сложностной класс NP -- это класс языков, для которых существуют проверяющие алгоритмы. Они также работают за полиномиальное время, при этом длина сертификата ограничена полиномом.

По определению, язык L принадлежит классу NP, если существует такой полиномиальный алгоритм А с двумя аргументами и многочлен p(x) с целыми коэффициентами, что L = {x ? {0, 1}* : ?y, для которого |y| ? p(|x|) и A(x, y) = 1}. Говорят, что A проверяет L за полиномиальное время.

Существует множество различных мнений об отношениях классов P и NP между собой. Наиболее убедительным аргументом в пользу того, что классы P и NP различны, является существование т.н. NP-полных задач. Данный класс обладает важным свойством: если какая-нибудь NP-полная задача разрешима за полиномиальное время, то все задачи из данного класса могут быть разрешимы за полиномиальное время. То есть научившись решать эти задачи за полиномиальное время, мы получим полиномиальные алгоритмы для любой задачи из класса NP.

Приведем понятие сводимости. Говорят, что язык L1 сводится за полиномиальное время к языку L2 (L1 ?P L2), если существует вычислимая за полиномиальное время функция f: {0,1}* > {0, 1}*, такая что для любого x ? {0, 1}*: x ? L1 равносильно f(x) ? L2.

При этом функцию f называют сводящей, а алгоритм F, вычисляющий f -- сводящим. Запись L1 ?P L2 можно интерпретировать следующим образом: сложность языка L1 не более чем полиномиально превосходит сложность языка L2.

Сводимость позволяет формализовать сравнение языков по их трудности. В этом смысле наиболее трудными являются NP-полные задачи. Язык L ? {0, 1}* называется NP-полным, если L ? NP и L? ?P L для любого L? ? NP. Обозначим данный класс языков как NPC (NP-complete). Ниже представлена диаграмма Венна для случаев P = NP и P != NP.



Рассмотрим несколько NP-полных задач:

Простой цикл в неориентированном графе G = (V, E), проходящий через все его вершины называется гамильтоновым.

Собственно сама задача о гамильтоновом цикле заключается в ответе на вопрос, имеет ли заданный граф G гамильтонов цикл. Это NP-полная задача. На рисунке ниже приведены примеры графов. На левом рисунке изображен гамильтонов граф, а граф на правом рисунке не обладает таким свойством.

Задача коммивояжёра вероятно является самой известной задачей комбинаторной оптимизации. Она заключается в нахождении самого выгодного маршрута, проходящего через города хотя бы единожды с последующим возвратом в начальную точку. Как правило, маршрут должен проходить только один раз через определенный город. То есть выбор осуществляется среди гамильтоновых циклов. Таким образом, можно данную задачу сформулировать и по-другому, а именно найти в графе гамильтонов цикл минимальной длины.

Задача о клике была сформулирована в 1972 году Ричардом Карпом. Это NP-полная задача в области теории графов.



Граф с кликой размера 3.

Клика в неориентированном графе - это подмножество вершин, каждые две из которых соединены ребром. То есть это полный подграф начального графа. Размер клики - число вершин в ней. Существует два варианта этой задачи: в задаче распознавания необходимо определить, существует ли в заданном графе G клика размера k, а в вычислительном варианте необходимо найти в заданном графе G клику максимального размера.

Существуют и другие NP-полные задачи: задача о выполнимости булевых формул, задача о раскраске графа, о вершинном покрытии, о независимом множестве и другие.

В дальнейшем в работе будем рассматривать задачу маршрутизации транспорта (VRP).

1.2 Задача маршрутизации транспорта

Задача маршрутизации транспорта (Vehicle Routing Problems, VRP) - это задача комбинаторной оптимизации. Предполагается, что имеется некоторый автопарк, который расположен в одном депо (или нескольких). Требуется определить набор маршрутов до клиентов, который находятся на определенном расстоянии. Интерес к VRP вызван ее практической значимостью.

Задача маршрутизации автотранспорта (Vehicle Routing Problem-VRP) является одной из самых актуальных проблем в логистике[21].

Фактически решить классическую задачу маршрутизации - это значит построить непересекающиеся гамильтоновы циклы в связном взвешенном графе, в вершинах которого находятся заказчики, а ребра же указывают стоимость маршрута - расстояние и/или время. Эта задача относится к NP-полным[24]. На рисунке ниже приведен пример решения классической задачи маршрутизации автотранспорта.

клиенты

VRP - это задача целочисленного программирования. Ее вычислительная сложность зависит от размера входных данных экспоненциально.

Для таких задач (NP-полных) обычно достаточно найти приближенное решение с определенной точностью. Обычно это получается сделать, используя различные эвристические методы. Как известно, задачи VRP лежат на пересечении двух других задач:

Задача коммивояжера (TSP)

Задача об упаковке рюкзака (Bin Packing Problem, BPP)

В случае с TSP задачу VRP можно свести к MTSP. Например, если принять грузоподъемность каждого автотранспорта бесконечной (или достаточно большой). Это достигается с помощью добавления к исходному графу k-1 копий нулевой вершины и ее ребер, k -- число маршрутов. Если же в случае BPP все расстояния принять равными нулю, тот ее решение будет эквивалентно решению VRP, то есть имеем одинаковую эффективность для всех решений.

Задачи маршрутизации - важные задачи в области транспортных перевозок. В некоторых областях рынка доставка товара может значительно увеличивать стоимость товара, иногда сравнимую со стоимостью самого товара. При использовании методов оптимизации возможна экономия до 10-20% стоимости товара.

Классический вариант задачи маршрутизации

Маршрутизация транспорта - комбинаторная задача. Ее можно представить в виде графа G(V, E), где

V = {v0, v1, ..., vn} -- множество вершин (v0 -- депо, v1..n -- потребители)

E -- множество ребер {(vi, vj) | i ? j}

C -- матрица неотрицательных расстояний cij между потребителями, здесь они являются стоимостями пути

m -- число машин

Ri -- маршрут i-й машины (i=1..m)

C(Ri) -- стоимость маршрута Ri

qi - объем груза, который поставляется i-му потребителю

С каждой вершиной Vi связано определенное количество товаров. Они должны быть доставлены соответствующему покупателю. То есть, сама задача маршрутизации состоит в нахождении множества маршрутов m с минимальной общей стоимостью, таким образом, чтобы каждая вершина множества V была посещена одним автомобилем один раз. Более того, все маршруты начинаются и заканчиваются в депо (v0). Решением задачи является:

разбиение множества V на подмножества (маршруты);

задание порядка обхода на каждом подмножестве, т.е. перестановка вершин маршрута.

Целевой функцией является стоимость решения задачи:

FVRP = ?C(Ri), i = 1..m

где C(Ri) -- сумма длин ребер маршрута Ri.

То есть нам необходимо найти приемлемое решение с минимальной стоимостью. Существует несколько разновидностей VRP. Дело в том, что в реальности в задачах оптимизации может возникать множество различных ограничений и вариаций:

CVRP: задача с ограниченной грузоподъемностью.

VRPTW: задача с временными окнами, т.е. клиент обслуживается в удобное ему время («временное окно»)

MDVRP: задача с несколькими депо.

VRPPD: модификация VRP, в которой клиенты имеют право возвращать товары в депо.

VRPB: аналогична VRPPD с той разницей, что товар возвращается только после того, как выполнена доставка всех товаров.

SDVRP: заказчик обслуживается несколькими средствами транспорта

SVRP: некоторые характеристики (длина маршрута, запросы клиентов) - случайны

VRPSF: возможна дополнительная загрузка машины по пути

Как видно из приведенной классификации, данная задача имеет весьма разнообразные ограничения, которые тем не менее применимы к реальной жизни. Этим объясняется актуальность данной проблемы. Далее рассмотрим подробнее задачи:

Маршрутизация с ограничением по грузоподъемности

Для всех машин грузоподъемность на маршруте ограничена некоторой величиной. Она одинакова для всех машин. Цель данной задачи заключается в том, чтобы минимизировать число машин, которое необходимо для обслуживания заказчиков, и время выполнения.

Маршрутизация с ограничением по времени

Для каждого клиента существует свой временной интервал, в который ему удобно принять заказ. На рисунке выше представлено решение задачи маршрутизации с ограничением по времени. Белым цветом показан допустимый интервал времени, черта означает реальное время исполнения. Также как и в предыдущей задаче, требуется минимизировать число машин, задействованных в обслуживании клиентов, а также время в пути и время ожидания. Таким образом, нельзя обслуживать клиента после его временного интервала, а в случае если машина приехала на место раньше назначенного времени, то она ожидает наступление этого интервала. При опоздании к целевой функции добавляется штраф. Решив эту задачу, можно избежать простоя автотранспорта, а также рассчитывать время выезда авто, для того чтобы во время оказаться у клиента.

Маршрутизация с несколькими депо

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

Маршрутизация с возвратом товаров

Данная задача отражает тот случай, когда необходимо забрать товар у заказчика и отвезти обратно в депо. Поэтому вместимость единицы транспорта не должна быть меньше объема товаров, которые клиент возвращает.

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

Маршрутизация с возвратом товаров

Отличие от предыдущего случая заключается в том, что сначала автотранспорт полностью проводит доставку, и лишь после этого выполняет выезд для приема возврата. Дело в том, что переставлять груз не является экономически целесообразным решением, когда машина уже загружена. Аналогично предыдущему варианту, вместимость машины должна быть как минимум не меньше объема товаров при возврате и доставке.

Маршрутизация с различным транспортом

В данной модификации задачи маршрутизации допускается обслуживать одного клиента разными единицами транспорта, особенно в случае если это уменьшает стоимость. К примеру, если объем заказа достаточно большой. При этом, обычно решить такую задачу сложнее, чем стандартную. Также предполагается, что в автопарке имеются машины разной грузоподъемности. Если разбить заказ на несколько неделимых, то из SDVRP можно получить стандартную VRP.

Маршрутизация со случайными данными

В этой модификации VRP несколько характеристик могут быть случайными. Например, запрос клиента может быть случайной величиной. Время поездки также может быть случайным. Более того, сам клиент может быть «случайным», т.е. существовать с некоторой вероятностью.

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

Например, в задаче SVRP с возвратом товаров и ограничением по вместимости могут использоваться такие способы коррекции:

если машина заполнена, то необходимо вернуться в депо, а затем оптимизировать оставшийся маршрут;

если известно, что груз следующего клиента превосходит грузоподъемность машины, то она возвращается в депо.

Маршрутизация с возможностью дозагрузки

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

Как и в предыдущих модификациях VRP, необходимо минимизировать расходы, связанные с доставкой. При этом вполне возможно, что в ближайшей перспективе стоимость такого решения возрастет. Такая постановка задачи VRP является частью более сложной задачи распределения товара, и она выходит за рамки этой работы.

1.3 Построение математической модели

Построим математическую модель для задачи СVRP, т.е с ограничением грузоподъемности. Имеем граф G(V, Е), где V = {v0, v1, ..., vn} -- множество вершин (v0 -- депо, v1..n -- клиенты) и E -- множество ребер {(vi, vj) | i ? j}.

Рассмотрим следующие входные данные:

С -- матрица расстояний;

d - вектор запросов клиентов. В нем хранятся данные о грузе;

т - число машин (доступное);

h - вектор принадлежности машины к депо, hi - депо, к которому привязана i-ая машина;

w -- вектор вместимости машины, где wi - вместимость i-й машины, длина этого вектора равна т.

Можно ввести несколько критериев для оптимизации. Одним из них может быть по суммарной длине маршрутов для всех машин парка. Вторым критерием оптимизации может выступать число автомобилей, задействованных в обслуживании клиентов. То есть целью оптимизации может являться и уменьшение их общего количества. Пусть т' - число задействованного транспорта. Используя принятые выше обозначения, можно формализовать задачу таким образом:



где rjj --j-й клиент i-й машины,

|ri| - количество клиентов, обслуженных i-й машиной.

Цель - минимизировать функцию F. По факту для решения этой задачи необходимо минимизировать длину маршрута (суммарную), число машин задействованных в обслуживании клиентов, а также расход топлива. Решением же является маршрутный лист для каждой машины.

Данная задача является многокритериальной. При этом важность критериев в течение времени не остается постоянной. Целевая функция может представлять собой функцию вида:

В (1.2) т' - число задействованных автомобилей,

т - число всех автомобилей в парке,

F- суммарная длина полученных маршрутов,

Q - суммарная длина маршрутов в самом начале решения,

а - характеристика «важности» количества задействованных автомобилей,

b - характеристика «важности» длины маршрута (суммарного).

1.4 Способы решения задач маршрутизации

Рассмотрим наиболее часто используемые способы решения задачи VRP. Почти все из них -- эвристические и метаэвристические методы. Точные алгоритмы не всегда дают решение за приемлемое время при больших входных данных.

Существует следующая классификация методов:

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

Метод ветвей с отсечением

Метод ветвей и границ

Эвристические алгоритмы. Осуществляется поиск по пространству решений за приемлемое время.

Конструктивные алгоритмы

Механизм сбережений

Метод, основанный на совпадениях

Эвристики улучшения многих маршрутов

Двухфазные методы. Состоят из 2 этапов. На первом вершины организуются в группы, на втором по каждой группе строится маршрут.

The Petal Algorithm

The Sweep Algorithm

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

Ant Algorithms

Bee Algorithms

Simulated Annealing

Genetic Algorithms

Tabu Search

The adaptative memory procedure

Granular Tabu

В данной работе уделяется внимание именно метаэвристическим подходам в решении VRP. Рассматриваются алгоритмы роевого интеллекта (Swarm Intelligence): муравьиный, пчелиный, роевой и меметический алгоритмы. В этих алгоритмах каждый агент (муравей, пчела и др.) по отдельности достаточно просто взаимодействует с другими и окружающей средой, однако в целом система таких агентов обладает разумным поведением.



Глава 2

2.1 Обзор алгоритмов

2.1.1 Муравьиный алгоритм

Алгоритм ACO (Ant Colony Optimization) является способом оптимизации на основе популяции. Он был разработан Марко Дориго, успешно применяется для решения нескольких NP-трудных задач комбинаторной оптимизации. Алгоритм основан на поведении колоний муравьев в процессе поиска пищи в реальной жизни. Когда муравьи покидают муравейник, они беспорядочно перемещаются вокруг районов непосредственной близости от их гнезда в поисках пищи. Если муравей находит пищу, то он собирает кусочки пищи и на обратном пути в гнездо распыляет вещество (феромон). Это способ общения с его коллегами, означающий, что он нашел источник пищи. Другие муравьи, находящиеся рядом, воспринимают аромат феромона и начинают двигаться в его направлении. После обнаружения источник пищи, они обновляют феромонный след для предупреждения и других муравьев.

Более того, после возращения муравьев обратно в гнездо, происходит оптимизация маршрута. За короткое время муравьи создают более короткий маршрут к источнику пищи, чем предыдущие маршруты. Кроме того, если на более короткий маршрут поместить препятствие, которое затруднит движение, муравьи могут найти еще один короткий маршрут из доступных вариантов обходов препятствия.

Существуют различные модификации муравьиных алгоритмов (Ant System (AS), Ant Colony System (ACS), Min-Max System Ant (ММАС), Ant Colony Optimization (ACO) и т.д.) [17]. В ACO колония муравьев высчитывает вероятность на каждой итерации, на основе которой муравей в узле выбирает следующий узел , к которому он будет дальше двигаться. Выбор узла зависит от значения следа феромона и доступных эвристик . В TSP . Так что муравей перемещается от места к с вероятностью

(7)

- след феромона, под имеется в виду локальная эвристическая информация, - итерация, - это множество узлов, доступных для муравья, б и в - параметры, управляющие изменением следа феромона. В конце итерации на каждом ребре след феромона будет модернизирован:

(8),

где - след феромона в итерации , параметр отвечает за скорость испарения феромона. Количество феромона, которое оставлено лучшим муравьём, может быть представлено в виде:

(9)

В (9), - стоимость лучшего решения .

2.1.2 Particle Swarm Optimization (PSO)

Метод роя частиц основан на поведении стаи птиц или косяке рыб. Был разработан Эберхартом и Кеннеди [18]. Алгоритм получает решения, используя т.н. рой частиц. При этом каждая частица представляет собой вариант решения. Рой похож на население, а частица представляет собой индивидуума. В поисках решения частицы перелетают через многомерное пространство, положение каждой частицы регулируется в соответствии с собственным опытом и информацией от соседей. Процесс оптимизации управляется вектором скорости. Также этот вектор обрабатывает опыт каждой частицы, учитывая информацию в рамках ее окрестности. PSO имеет два управляющих уравнения для поиска решения.

(10),

где - текущая скорость, _ предыдущая скорость, и -коэффициенты ускорения, - фактор сужения, - наилучшее положение отдельных частиц, и _ случайные числа, _ текущее положение, - лучшее положение роя.

Это уравнение отвечает за положение роя

(11)

В этом алгоритме частицы движутся в области целевой функции , представляет переменные, которые будут оптимизированы. Каждая частица на определенной итерации связана с тремя векторами:

Текущая позиция - записывает текущую позицию конкретной частицы.

Текущая скорость - сохраняет направление частицы поиска.

Индивидуальное личное положение - содержит наилучшее решение конкретной частицы до текущего времени (с момента начала выполнения алгоритма).

2.1.3 Artificial Bee Colony

Алгоритм основан на поведении пчелиного роя при сборе меда. Он был предложен Karaboga и Akay в 2009 году [20]. В алгоритме используются три класса пчел: разведчики, рабочие пчелы и пчелы наблюдатели. Пчелы-разведчики - это те, которые летают в поиске решений (источник питания). Пчелы-наблюдатели остаются в гнезде в ожидании доклада разведчиков, рабочие пчелы после просмотра танца пчел-разведчиков приступают к уборке источника питания. При этом пчела одного класса может стать пчелой другого класса. Например, разведчик может стать рабочей пчелой, если он участвует в уборке источника пищи, и наоборот.

То есть пчелы могут изменять свой статус в определенный момент времени в зависимости от потребностей алгоритма. Источник питания является решением задачи оптимизации. Объем нектара представляет собой качество (пригодность) решения. Более того, предполагается, что каждая из рабочих пчел использует единственный источник пищи, т.е. число рабочих пчел соответствует количеству источников пищи. Пчелы-разведчики всегда ищут новые источники пищи с более высоким количеством нектара и/или качество в близлежащем районе. Они оценивают пригодность нектара, используя

(12)

где - случайно выбранный индекс; - случайное число в заданном диапазоне; - источник пищи. Качество решения рассчитывается следующим образом:

(13)

Видно, что есть существует некоторое сходство (10) в PSO и (12) в ABС. Каждый алгоритм вычитает переменные из лучших личных и индивидуальных частиц/пчел. При этом, для PSO вычитаемая переменная представляет нынешнее положение, а для АВC - разведанное местоположение. Но тем не менее, эти два уравнения отличаются: PSO использует (будучи фактором сужения) или (как фактор инерции, в некоторых версиях PSO), а в ABC не существует подобных эквивалентов. В то время как PSO использует случайные числа ( и ), АВC содержит только обучаемые параметры. PSO в отличие от ABC использует коэффициенты ускорения ( и ).

2.1.4 Меметические алгоритмы

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

Первоначально меметика как теория была предложена Ричардом Докинзом [4]. Он предполагал, что сам термин эволюции может быть применен не только к биологическим видам, но и, вообще говоря, к любым другим системам - тем, которые могут изменяться, а также наследовать некоторые свойства. По факту меметику можно считать той наукой, которая является аналогичной генетике в культурной среде. По аналогии с геном в генетике, в меметике вводится термин «мем». Это «единица передачи культурной информации, распространяемая от одной особи к другой посредством имитации, научения и др.» [4].

Впервые термин «меметический алгоритм» был предложен П.Москато (P.Moscato) в [5]. Он вводит меметический алгоритм как комбинацию генетического алгоритма, к которому добавлена процедура индивидуального обучения с целью уточнения решения задачи. Если новое полученное решение имеет большую приспособленность на втором этапе (индивидуального обучения), то старое им заменяется. Таким образом, данная особь «культурно развивается», и эти свойства в дальнейшем могут быть переданы потомкам.

Меметические алгоритмы иногда называют гибридными эволюционными, а также алгоритмами Ламарка, алгоритмами Болдуина, генетическими алгоритмами локального поиска или культурными алгоритмами. Существует несколько поколений меметических алгоритмов.

Первое поколение меметических алгоритмов - гибридные алгоритмы эволюционного подхода. Они используются для глобального поиска. Однако данный подход не вполне соответствует теории дарвинизма. Дело в том, что такие процессы как наследование, изменение и селекция здесь отсутствуют, а присутствуют лишь некоторые характеристики культурной эволюции. Именно поэтому термин «меметический алгоритм» неоднократно подвергался критике и вызывал споры исслеователей в самом начале [6].

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

Третье поколение меметических алгоритмов включает в себя коэволюцию и самогенерирующиеся МА. Отличие от второго поколения заключается в том, что во втором поколении полагается, что используемые мемы известны изначально, а третьем поколении МА используется локальный поиск, который основан на некоторых правилах.

Меметические алгоритмы достаточно интенсивно исследуются в последнее время. Они успешно применяются для множества задач: задача коммивояжёра, задача о назначениях, задача о минимальной раскраске графа, задача упаковки в контейнеры. 

2.2 Биоиспирированные алгоритмы в задачах VRP

Как уже выше было замечено, основной идея муравьиного алгоритма основана на моделировании их поведения. Дело в том, что несмотря на достаточно примитивное поведение каждого отдельно взятого муравья, поведение всей колонии в целом является разумным. То есть сама колония муравьев является сложной системой, которую образуют особи с простыми правилами поведения. У муравьев вырабатывается специальное вещество - феромон. Это их средство общения, таким образом они между собой взаимодействуют. Муравьи откладывают феромон на протяжении своего пути. Когда муравей выбирает свой маршрут, он руководствуется не только своим желанием найти наиболее краткий путь, но и полагается на опыт других. По сути концентрация феромона и определяет желание муравья пройти определенный путь. Более того, было выяснено экспериментально, что муравьи по-разному выделяют феромон в процессе поиска пищи и после находки [26]. При поиске они выделяют его прерывисто, а в тот момент, когда они находят пищу, они образуют непрерывную линию феромонов. Это дает возможность остальным муравьям узнать местоположение источника пищи. То есть, муравьи различают запахи феромонов, которые ведут к источнику пищи от других запахов. Рисунок ниже иллюстрирует эти ситуации:



Во процессе поиска пищи сигнал, оставляемый муравьем, достаточно слаб. Несмотря на это, муравей найдет обратный путь. Допускается и то, что другие муравьи могут последовать за этим сигналом, но на самом деле вероятность этого крайне низка, т.к. уровень феромонов действительно очень низкий. Когда же муравей нашел источник пищи, он оставляет на обратном пути след большей интенсивности. И уже эта интенсивность достаточна для привлечения остальных муравьев.

Однако из-за того, что в самом начале движения муравьи осуществляют свой выбор направления движения случайно, то неизбежно попадание в локальный оптимум. Процесс испарения феромонов решает эту проблему. По всей площади ареала испарение происходит равномерно. Поэтому, на более кратком маршруте испарение будет осуществляться медленнее, а концентрация феромонов на оптимальном маршруте сохраняться будет дольше [28].

а) б) в)

Рассмотрим три этапа проложения маршрута из начального пункта до источника пищи на рисунках выше: а) инициализация, когда феромон отсутствует, б) поиск пищи, откладывание феромонов, в) испарение феромонов, нахождение оптимального пути. Данная симуляция проведена при помощи программы Ants Viewer. В ней видно, что часть муравьев выбрала неоптимальный маршрут. Этот маршрут менее привлекателен для муравьев, т.к. концентрация феромона на нем ниже.2.2.1 Разработка модифицированного муравьиного алгоритма

Для того, чтобы рассмотреть муравьиный алгоритм в контексте задачи маршрутизации транспорта, наложим на свойства муравья некоторые дополнительные ограничения. Муравей обходит все точки при сборе пищи кратчайшим образом. При этом он может «забирать груз» только определенного ограниченного веса. Когда муравей наберет груз максимально возможного веса, он должен вернуться в колонию для «разгрузки». В дальнейшем он повторяет данные действия, т.е. забирает грузы на не посещенных раннее местах до тех пор, пока пища не будет собрана. Данная модель поведения муравья позволяет решить задачу CVRP [27].

Поведение муравья с дополнительным ограничением

Загруженность муравья отражается полоской на рисунке выше. Когда муравей достигает вершины 4, он возвращается в колонию (или депо - в VRP), не вычисляя вероятности перехода в остальные вершины. Далее муравей продолжит свое путешествие уже с нулевой загруженностью. При этом в его табу-листе будут вершины 1,4,5,6 - он их уже посетил. Как упоминалось раннее, данную задачу можно свести к задаче коммивояжера (нахождения гамильтонова цикла минимальной длины), если грузоподъемность муравья принять за бесконечность или достаточно большой.

Стратегия расположения муравьев в данном случае - это так называемая «фокусировка», т.е. когда все муравьи изначально находятся в одном месте - депо. Если же решаем задачу MDVRP (Multi Depot), то используем стратегию «дробовик». В этом случае муравьи находятся в разных вершинах (депо или склады) и находят маршруты последовательно. На рисунке ниже приведен пример решения задачи MDVRP.

Пример решения задачи MDVRP

Для решения задачи VRPTW (с временными окнами) добавим зависимость от временных ограничений при расчете вероятности перехода к-м муравьем из і в j. Введем правила:

Правило 1. Если муравей достиг j из i, и при этом загруженность муравья будет больше заданной грузоподъемности, то вероятность его перехода равна нулю

Правило 2. Если муравей достиг j из i, и при этом продолжительность его маршрута будет больше интервала временного окна, то вероятность перехода равна нулю

Правило 3. Если муравей раннее не посещал определенную вершину, и вероятность перехода в нее из i равна нулю, то муравей возвращается в депо.

Правило 4. Если муравей посетил j до начала временного окна Sj, то он будет ждать наступления Sj.

Таким образом, выражение принимает следующий вид:

(1.3)

Здесь Pjj,k(t) - вероятность перехода к-го муравья из i в j в момент времени t,

фij(t) - количество феромона на ребре Dij в момент времени t,

а, в- задают значения веса для следа феромона;

Tkj - время, которое затратил к-ый муравей при достижении і;

Ji,k - список вершин, которые были посещены;

fj - конец интервала для j-го клиента;

Wki - загруженность к-го муравья, когда он достиг i;

dj - вес товара для j-ого клиента;

с - грузоподьемность муравья.

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

Рассмотрим вычислительную сложность муравьиного алгоритма (ВСА). В работах Марко Дориго [21] было показано, что ВСА зависит от числа вершин п, размера колонии т и числа итераций Т (время жизни колонии). Но если мы рассмотрим выражение (1.3), то заметим , что ВСА зависит также от параметров а и в. Докажем это.

Дело в том, что данные параметры не являются постоянными. Поэтому необходимо определить их влияние на ВСА. То есть сложность алгоритма зависит еще и от параметров самого алгоритма, а не только от размерности задачи. Определим О-функцию вычислительной сложности в зависимости от параметров муравьиного алгоритма. Наиболее трудоемкой операцией в этом алгоритме является вычисление вероятности, необходимой для выбора ребра муравьем.

При расчете этой вероятности используются операции умножения, суммирования и возведения в степень. Для возведения в степень используем алгоритм быстрого возведения. Его ВСА может быть оценена как 0( log2n+ 1), п - это степень алгоритма. Поэтому ВСА муравьиного алгоритма можно ограничить следующей оценкой:

Здесь T - время жизни колонии, m - размер колонии, n - число вершин, б и в - коэффициенты, задающие веса следа феромона.

При этом рекомендуется использовать целые числа при возведении в степень, т.к. это более трудоемкая операция для нецелочисленных операндов.

К примеру, для того чтобы возвести число в степень 1,99 требуется гораздо больше операций, чем возведение в степень 2. В данном подходе муравьиный алгоритм в среднем эффективнее в 3-4 раза по быстродействию.

Далее, чтобы еще увеличить быстродействие алогоритма, необходимо многократное повторение операций с одинаковыми операндами. Например, это может быть операция возведения «зрения» муравья зij в степень в. Числа являются константами, и нет необходимости вычислять эти значения на протяжении всей жизни колонии, т.к. они остаются одинаковыми. Таким образом, можно видоизменить предыдущую формулу:

При этом изменится и вычислительная сложность:

о(T*т*п2 *log2a)

Зависимость времени работы муравьиного алгоритма от коэффициента а доказана экспериментально. На рисунке ниже представлена зависимость времени работы алгоритма от коэффициента а, при этом использована стратегия «дробовик», т.е. муравьи расположены в разных вершинах. Число вершин равно 30, коэффициент испарения равен 0.5, количество муравьев в колонии равно 1000, а длительность жизни колонии равно 100 итерациям.



Получаем, что время работы алгоритма прямо пропорционально значению коэффициента а, если а - целое. Но если а принять дробным числом, то зависимость времени работы алгоритма станет нелинейной. При этом если параметры Т, т, а принять константами, то вычислительная сложность будет зависеть квадратично лишь от размерности задачи. Данная оценка может быть справедлива, если заранее определены оптимальные параметры алгоритма и их зафиксировали константами.

Если рассматривать пространственную сложность муравьиного алгоритма, то она окажется значительно ниже сложности генетического. Дело в том, что в муравьином алгоритме не требуется хранить данные о всей колонии, а в генетический алгоритм невозможно реализовать, не производя хранение этой информации о всей популяции. В так называемой феромонной матрице хранятся все данные об опыте каждого муравья. То есть пространственная сложность муравьиного алгоритма также может быть оценена квадратично 0(п2). Данные, представленные на рисунке ниже могут подтвердить данный результат.



Зависимость занимаемого объема оперативной памяти от размера задачи

2.2.2 Разработка пчелиного алгоритма

Пчелиный алгоритм является одним из алгоритмов класса роевых. Этот алгоритм моделирует поведение пчел в естественной среде [11]. Суть пчелиного алгоритма заключается в том, что пчелы на каждом шаге выбирают для исследования как элитные участки, так и участки в окрестности элитных. Это в свою очередь позволяет разнообразить популяцию решений на следующих итерациях, а также увеличивает вероятность обнаружения решений, близких к оптимальным.

Решение в данном случае - это вектор целочисленных значений Н. При этом область поиска нектара - пространство поиска, размерностью п! То есть это количество возможных перестановок вектора Н. В данном случае конкретная перестановка Н характеризует расположение источника нектара. Поэтому координаты источника есть не что иное как решение Н. Количество нектара на источнике обратно пропорционально целевой функции. Количество решений, «близких» к Н, характеризует размер участка. Для нахождения степени близость между векторами используется расстояние Хэмминга. Например, решения {5,4,7,3,2,1,6} и {5,2,7,3,4,1,6} являются «близкими». Они располагаются рядом в пространстве поиска, находясь на одном «участке».

Приведём описание пчелиного алгоритма:

Создаем популяцию;

Производим оценку ЦФ пчёл;

Выбор участков поиска в их окрестности;

Отправляем разведчиков;

Отбираем пчел с лучшими значениями ЦФ (для каждого участка);

Отправляем фуражиров. Они осуществляют случайный поиск, происходит оценка их ЦФ;

Формируем новую популяцию пчел;

Если условие останова не выполнено, то идем в п.2.

Конец работы алгоритма.

Пчелиный алгоритм имеет квадратичную сложность, т.е О(п2). Рассмотрим пример - задачу поиска глобального минимума функции: f(x, у) = х2+у2. Модель представлена на рисунке выше.

Границы участка определим как:

[x1-r; x1+r][x2-r; x2+r]...[xn-r; xn - r],

где Xj - координата пчелы,

r - радиус участка,

п - число параметров функции, в этом случае их 2 (х, у).

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

Приведем описание пчелиного алгоритма для данного случая:

Генерируем участки поиска нектара;

Оцениваем полезности найденных участков;

Выбираем участков для поиска в окрестностях;

Отправляем фуражиров;

Осуществляем поиск в окрестностях источников нектара;

Отправляем разведчиков;

Производим случайный поиск;

Оцениваем полезность новых участков;

Если условие останова не выполнено, то переходим в п.2.

Конец работы алгоритма.

Теперь приведем основные положения данного алгоритма.

Пространство поиска представляет собой все возможные перестановки А из п, его размерность есть n!;

Количество нектара в источнике А обратно пропорционально ЦФ F(A);

Источник нектара определен одним решением из пространства поиска и представлен в виде определенной перестановки;

Расстояние L между перестановками А и В есть расстояние Хемминга. Оно равно числу различий в позициях между ними;

Два источника {А, В) находятся на одном участке, если расстояние L(A, В) < r. r - это размер участка;

Рассмотрим подробнее каждый пункт:

Инициализируем начальные параметры алгоритма

Производим случайную генерацию участков для поиска нектара. Решение Н - координаты источника.

Производим расчет ЦФ (т.е. оценка качества решений). При этом количество нектара на источнике обратно пропорционально ЦФ.

Выбираем т лучших участков

Отправка рабочих пчел заключается в выборе к пчел для исследования т лучших участков.

Поиск в т участках. Каждый участок имеет определенные размеры. Размер в данном случае - это количество «близких» к Н решений. Для оценки степени близости между векторами используем расстояние Хемминга. Чем меньше расстояния между решениями, тем больше они похожи.

Производим случайный поиск разведчиками. Участки, на которых должен быть произведен локальный поиск, выбираются случайно.

Расчет ЦФ на участках - количество нектара

Проверяем условие останова, алгоритм завершает работу по истечению определенного времени.

Ключевая операция в пчелином алгоритме - это совместное исследование перспективных областей и их окрестностей. То есть в конце алгоритма имеем популяцию решений, которая состоит из двух частей. Первая - это пчелы с лучшими ЦФ элитных участков, вторая - рабочие пчелы со случайными значениями ЦФ. При этом временная сложность алгоритма зависит от числа вершин квадратично. Представление кодирование позволяет пчелиному алгоритму решать широкий класс графовых задач. Структурная схема представлена ниже:



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

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



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

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

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

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

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

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

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



2.4 Экспериментальная часть

Для решения задачи маршрутизации автотранспорта создана программа в интегральной среде разработки Microsoft Visual Studio 2013. Пример эксперимента приведен на рисунке ниже. Использованы следующие параметры: т=20, t=1 мин, а=1,в =4.

Приведем в таблице ниже зависимость ЦФ от размера колонии т. Для каждого значения т проведем 5 экспериментов, а также укажем среднее значение ЦФ. Если будем увеличивать ее размер дальше, то это приведет к избыточному влиянию параметра а.

Зависимость ЦФ от значений параметров эвристик а и в



Оптимальные значения ЦФ получаются в области в=2-4. Оптимальные решения получены при значениях б и в 1 и 4 соответственно.



Ниже приведена таблица, в которой столбец номер эксперимента, а строка - размер колонии. Оптимальный размер колонии оказался равным 20. Для расчетов принималось, что б= 1, в = 4, коэффициент испарения равен 0.5, а время жизни = 5 секунд.

Зависимость ЦФ от размера колонии для задачи CVRP (41 вершина)

Графики ниже иллюстрируют решение задачи разбиения с использованием пчелиного алгоритма.



График зависимости ЦФ от числа фуражиров

Зависимость ЦФ от числа фуражиров и разведчиков

Зависимость ЦФ от времени для генетического, муравьиного и пчелиного алгоритмов соответственно



В среднем качество решений муравьиного и пчелиного алгоритмов одинаково. Однако в муравьином алгоритме решение основано на знаниях о задаче. В пчелином же не используются особенности задачи (за исключением кодирования решения). Поэтому он и предпочтителен. Более того, при увеличении размерности задачи пчелиный алгоритм показывает лучшее решение. Дело в том, что временная сложность пчелиного алгоритма меньше, чем у муравьиного. За счет этого возможно выполнение большего числа итераций. Степень стохастичности в алгоритмах роевого поиска достаточна высока. Это позволяет быстрее выходить из локальных оптимумов по сравнению с ГА. Были проведены тестирования для графов от 50 до 1000 вершин.



Заключение

В работе были приведены примеры NP-полных задач, основное внимание было уделено задаче маршрутизации транспорта, а также рассмотрены ее различные модификации: CVRP, VRPTW, MDVRP и др. Также была приведена математическая модель задачи маршрутизации транспорта и проведены анализ существующих методов решения задачи. Одним из перспективных подходов к решению VRP является разработка биоинспирированных алгоритмов, а также их модификаций. Эти алгоритмы позволяют достаточно эффективно решить проблему попадания в локальный оптимум, а также получать оптимальные и квазиоптимальные решения. Был разработан гибридного алгоритм, представляющий собой последовательно-вложенную модель, проведены его анализ и оценка временной сложности. Преждевременную сходимость муравьиного алгоритма можно предотвратить с помощью использования операторов генетического алгоритма. Был подобран оптимальный набор параметров алгоритма. При этом, эксперименты подтвердили преимущество данной модификации перед генетическим и муравьиным алгоритмами, а также показали зависимость параметров от размерности задачи. Также была выявлена зависимость значений оптимальных параметров алгоритмов и целевой функции.

...