Биоиспирированные алгоритмы в задачах 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). Данные, представленные на рисунке ниже могут подтвердить данный результат.

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