СТАТЬИ АРБИР
 

  2018

  Июль
  Август   
  Пн Вт Ср Чт Пт Сб Вс
30 31 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 1 2
   

  
Логин:
Пароль:
Забыли свой пароль?


Решение задачи коммивояжера с помощью интегрированного метода


РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА С ПОМОЩЬЮ ИНТЕГРИРОВАННОГО МЕТОДА

Аннотация

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

Ключевые слова

Задача коммивояжера, муравьиный алгоритм, генетический алгоритм, задача с несколькими коммивояжерами.

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

Задача относится к классу NP-полных и является трансвычислительной.

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

Выделяют два типа решения задачи коммивояжера: точные и эвристические [1]. Широко распространенным точным не переборным алгоритмом решения задачи коммивояжера является метод ветвей и границ [2].

К простейшим эвристическим методам решения следует отнести «жадный» алгоритм. На каждом шаге метода выбирается ребро наименьшей стоимости. Будем применять данный алгоритм, чтобы определить, являлся ли входной граф связным. Решение для N вершин будет найдено за (N - 1) шагов.

Одним из эвристических методов искусственного интеллекта является муравьиный алгоритм Марко Дориго. Этот алгоритм имитирует передвижение колонии муравьев в природе [8].

Направление движения муравья определяет случайное число, которое отправляет его из i города в город j с большей вероятностью, если вероятностная направляющая функция примет наибольшее значение [7].

Феромоны - это некоторое вещество, которое «откладывают» муравьи, помечая пройденный маршрут между городами. Как и в природе, феромоны обладают свойством испарения.

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

Генетический алгоритм - эвристический метод поиска с использованием механизмов, напоминающих биологическую эволюцию. Цепочка городов будет ассоциирована с цепочкой генов - хромосомой, с которой могут происходить биологические изменения - мутация, кроссинговер и скрещивание [4, 5].

Схема интегрированного поиска

Основная идея интегрированного поиска - объединение алгоритмов в многоуровневую модель, в зависимости от требований к решению [6].

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

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

На первом этапе, с помощью того же «жадного» алгоритма генерируем несколько случайных решений из различных вершин.

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

Механизмы передачи информации в генетическом и муравьином алгоритмах совершенно различны:

o в ГА хромосомы обмениваются информацией друг с другом, поэтому вся популяция движется, как единая группа, в область оптимума;

о в РА только глобальная (локальная) лучшая позиция передается другим частицам. Это единственный механизм передачи информации.

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

Теоретическая временная сложность работы интегрированной системы, для одного коммивояжера составляет: О(№(1+^), что незначительно превышает время работы роевых алгоритмов, но интегрированный метод обладает повышенной точностью.

Список литературы:

Беспалько В. П. Образование и обучение с помощью компьютеров / В. П. Беспалько. - М. : Высш. шк., 1998. - 135 с.

Борознов В. О. Дополнение метода ветвей и границ для решения задачи коммивояжера // Вестн. Ростов. гос. ун-та путей собщения. - 2007. - № 1. - С. 160-163.

Борознов В. О. Исследования генетических методов решения задачи коммивояжёра / В. О. Борознов, О. Г. Ведерникова // Вестн. Ростов. гос. ун-та путей собщения. - 2004. - № 1. - С. 42-45.

Гладков Л. А., Курейчик В. М., Курейчик В. В. Генетические алгоритмы / Л. А. Гладков. - Ростов-на-Дону: ООО «Ростиздат», 2004г.

Курейчик В.В. Эволюционные методы решения оптимизационных задач. Таганрог, 1999, ТРТУ.

МакКоннелл Дж. Основы современных алгоритмов // Дж. МакКоннелл. - М.: Техносфера, 2004. - 368 с.

Романовский И. В. Алгоритмы решения экстремальных задач / И. В. Романовский. - М. : Наука, 1977. - 352 с.

Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a colony of cooperating objects // IEEE Trans. on Systems, Man, and Cybernetics. - 1996. - Part B.


Боронихина Е.А. Научный руководитель - Сибирякова В.А., ст. пр. НИ ТГУ, Россия, г. Томск





МОЙ АРБИТР. ПОДАЧА ДОКУМЕНТОВ В АРБИТРАЖНЫЕ СУДЫ
КАРТОТЕКА АРБИТРАЖНЫХ ДЕЛ
БАНК РЕШЕНИЙ АРБИТРАЖНЫХ СУДОВ
КАЛЕНДАРЬ СУДЕБНЫХ ЗАСЕДАНИЙ

ПОИСК ПО САЙТУ