Разработка и исследование алгоритмов муравьиной колонии для решения задач оптимального размещения предприятий

• Автор: Лореш, Максим Андреевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Омск
• Количество страниц: 113 с. : ил.

Оглавление
Введение

Глава 1. Постановки задач и методы решения.

1.1 Постановки задач.

1.2 Вычислительная сложность и методы решения

1.3 Алгоритмы муравьиной колонии.

Глава 2. Алгоритмы муравьиной колонии для задач оптимального размещения предприятий.

2.1 Алгоритмы муравьиной колонии для задачи о рмедиане

2.2 Алгоритмы муравьиной колонии для простейшей задачи размещения.

2.3 Алгоритм муравьиной колонии для задачи с ограничениями

на мощности производства.

2.4 Локальный поиск в алгоритмах муравьиной колонии.
Глава 3. Теоретические вопросы сходимости алгоритмов муравьиной колонии.
3.1 Известные результаты о сходимости алгоритмов.
3.2 Асимптотические свойства алгоритмов муравьиной колонии
для задачи о рмедиане.
3.3 Простейшая задача размещения
3.4 Алгоритм муравьиной колонии и локальный поиск.
Глава 4. Результаты вычислительного эксперимента
4.1 Простейшая задача размещения
4.2 Задача о рмедиане
4.3 Задача размещения предприятий с ограничениями на мощности производства
Заключение
Литература


Значительное внимание в диссертации уделяется простейшей задаче размещения и задаче о р-медиане на минимум. Для их решения разработаны алгоритмы муравьиной колонии, основанные на искусственном муравье, представляющем собой вероятпостую модификацию жадного алгоритма спуска. Доказаны некоторые асимптотические свойства предложенных алгоритмов. В работе также рассматривается задача размещения предприятий с ограничениями на мощности производства. Для ее решения предложен алгоритм муравьиной колонии, основанный на схеме, для которой доказана асимптотическая сходимость к точному решению []. Все предложенные алгоритмы реализованы, проведено экспериментальное исследование. Диссертация состоит из введения, четырех глав, заключения и списка литературы. В первой главе даются постановки указанных задач размещения предприятий и близких к ним задач. Рассматриваются вопросы сложности решения простейшей задачи размещения, задачи о р-медиане и задачи размещения с ограничениями на мощности производства. Кроме того, в первой главе кратко изложены основные идеи генетических алгоритмов, алгоритмов поиска с запретами, алгоритмов имитации отжига. В этой же главе подробно описываются алгоритмы муравьиной колонии, дается обзор алгоритмов муравьиной колонии, предложенных различными авторами для задачи коммивояжера и квадратичной задачи о назначениях. Глава 2 посвящена алгоритмам муравьиной колонии для простейшей задачи размещения, задачи о р-медиане и задачи размещения предприятий с ограничениями на мощности производства. Для простейшей задачи размещения и задачи о р-медиане предлагаются две различные схемы переопределения уровня феромона. Кроме того, разработаны различные варианты алгоритма искусственного муравья. Для задачи размещения предприятий с ограничениями на мощности производства построен алгоритм муравьиной колонии, основанный на схеме Graph-Based Ant System, для которой доказано, что вероятность нахождения оптимального решения равна единице при бесконечном увеличении числа итераций []. В этой же главе рассматриваются понятие окрестности решения и алгоритмы локального поиска, описывается несколько вариантов окрестностей для указанных задач размещения. Для улучшения качества решений, получаемых разработанными алгоритмами муравьиной колонии, построены гибридные схемы с использованием процедуры локального поиска. Глава 3 посвящена теоретическим вопросам сходимости предложенных алгоритмов муравьиной колонии. Несмотря на то, что экспериментальному исследованию алгоритмов муравьиной колонии посвящено большое количество статей, работы, в которых рассматриваются вопросы сходимости таких алгоритмов, стали появляться относительно недавно [-,9,4]. Причем, все доказательства относятся к упрощенным версиям фактически применяемых схем и не дают прямых рекомендаций для практического использования. Однако они представляют интерес для изучения общих свойств исследуемых алгоритмов. В главе 3 доказаны асимптотические свойства предложенных алгоритмов муравьиной колонии для задачи о р-медиане. В данной главе также установлено, что в схемах с процедурой локального поиска число шагов алгоритма локального поиска стремится к нулю при увеличении номера итерации алгоритма муравьиной колонии. Глава 4 содержит результаты экспериментальных исследований для разработанных алгоритмов. В ней приводятся данные сравнительного анализа предложенных алгоритмов муравьиной колонии, например, по качеству найденных решений. Исследуется влияние использования статистической информации (уровня феромона) на качество получаемых решений. В этой же главе исследуется влияние процедуры локального поиска на качество решений, получаемых алгоритмами муравьиной колонии. В частности, вычислительный эксперимент показал эффективность использования процедуры локального поиска в алгоритмах муравьиной колонии. Кроме того, важным является вопрос о количестве шагов алгоритма локального поиска до локального оптимума, т. В главе 4 по данному параметру проведено экспериментальное сравнение предложенных схем алгоритмов муравьиной колонии с мультистартовыми процедурами, основанными на локальном поиске.