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

Многие задачи, которые интересны с практической точки зрения, имеют полиномиальные алгоритмы решения. Это значит, что время работы алгоритма на входе длины n составляет не более O(nk) для некоторой константы k, при этом k не зависит от длины входа. Однако далеко не каждая задача имеет алгоритм решения, который удовлетворял бы данному свойству. Более того, существуют задачи, для которых имеется решающий их алгоритм, но он работает «долго». Для таких задач не найдены полиномиальные алгоритмы, но и не доказано, что таких алгоритмов не существует.К примеру, задача разрешения связана с задачей поиска кратчайшего пути в графе: «по заданному графу G = (V, E), паре вершин u, v ? V и натуральному числу k определить, существует ли в G путь между вершинами u и v, такой что его длина не превосходит k». То есть, в задаче о поиске кратчайшего пути в графе был выполнен переход от задачи оптимизации к задаче разрешения, т.к. было добавлено ограничение на длину пути. Будем называть задачу полиномиальной, если существует константа k и некоторый алгоритм, который решает эту задачу за время O(nk), т.е. полиномиальное время. Данный класс обладает важным свойством: если какая-нибудь NP-полная задача разрешима за полиномиальное время, то все задачи из данного класса могут быть разрешимы за полиномиальное время. То есть научившись решать эти задачи за полиномиальное время, мы получим полиномиальные алгоритмы для любой задачи из класса NP.Фактически решить классическую задачу маршрутизации - это значит построить непересекающиеся гамильтоновы циклы в связном взвешенном графе, в вершинах которого находятся заказчики, а ребра же указывают стоимость маршрута - расстояние и/или время. Как известно, задачи VRP лежат на пересечении двух других задач: Задача коммивояжера (TSP) В случае с TSP задачу VRP можно свести к MTSP. Если же в случае BPP все расстояния принять равными нулю, тот ее решение будет эквивалентно решению VRP, то есть имеем одинаковую эффективность для всех решений. VRPTW: задача с временными окнами, т.е. клиент обслуживается в удобное ему время («временное окно»)Построим математическую модель для задачи CVRP, т.е с ограничением грузоподъемности. Имеем граф G(V, Е), где V = {v0, v1, ..., vn} - множество вершин (v0 - депо, v1..n - клиенты) и E - множество ребер {(vi, vj) | i ? j}. h - вектор принадлежности машины к депо, hi - депо, к которому привязана i-ая машина; w - вектор вместимости машины, где wi - вместимость i-й машины, длина этого вектора равна т. Используя принятые выше обозначения, можно формализовать задачу таким образом: где rjj-j-й клиент i-й машины, |ri| - количество клиентов, обслуженных i-й машиной.Рассмотрим наиболее часто используемые способы решения задачи VRP. Точные алгоритмы не всегда дают решение за приемлемое время при больших входных данных. Осуществляется поиск по пространству решений за приемлемое время. Метод, основанный на совпадениях В таких алгоритмах изучаются наиболее перспективные части пространства решений.Алгоритм основан на поведении колоний муравьев в процессе поиска пищи в реальной жизни. Если муравей находит пищу, то он собирает кусочки пищи и на обратном пути в гнездо распыляет вещество (феромон). За короткое время муравьи создают более короткий маршрут к источнику пищи, чем предыдущие маршруты. Кроме того, если на более короткий маршрут поместить препятствие, которое затруднит движение, муравьи могут найти еще один короткий маршрут из доступных вариантов обходов препятствия. след феромона, под имеется в виду локальная эвристическая информация, - итерация, - это множество узлов, доступных для муравья, ? и ? - параметры, управляющие изменением следа феромона.В алгоритме используются три класса пчел: разведчики, рабочие пчелы и пчелы наблюдатели. Пчелы-наблюдатели остаются в гнезде в ожидании доклада разведчиков, рабочие пчелы после просмотра танца пчел-разведчиков приступают к уборке источника питания. Например, разведчик может стать рабочей пчелой, если он участвует в уборке источника пищи, и наоборот. То есть пчелы могут изменять свой статус в определенный момент времени в зависимости от потребностей алгоритма. Более того, предполагается, что каждая из рабочих пчел использует единственный источник пищи, т.е. число рабочих пчел соответствует количеству источников пищи.В меметических алгоритмах используется эволюционный подход, который основан на понятии популяции, а также связан с обучением каждой особи в отдельности для получения более качественных решений для задач поиска глобального экстремума. По аналогии с геном в генетике, в меметике вводится термин «мем». Впервые термин «меметический алгоритм» был предложен П.Москато (P.Moscato) в [5]. Он вводит меметический алгоритм как комбинацию генетического алгоритма, к которому добавлена процедура индивидуального обучения с целью уточнения решения задачи. Меметические алгоритмы иногда называют гибридными эволюционными, а также алгоритмами Ламарка, алгоритмами Болдуина, генетическими алгоритмами локального поиска или культурными алгоритма

Оглавление

Введение

Глава 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 и другие. Такие постановки задачи точнее отражают реальные требования к доставке, предъявляемые клиентами (например ограниченный промежуток времени). Данные модификации включают в себя различные дополнительные ресурсные ограничения.