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

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

Автор: Лореш, Максим Андреевич

Шифр специальности: 05.13.01

Научная степень: Кандидатская

Год защиты: 2006

Место защиты: Омск

Количество страниц: 113 с. ил.

Артикул: 3300861

Автор: Лореш, Максим Андреевич

Стоимость: 250 руб.

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

Оглавление
Введение
Глава 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 по данному параметру проведено экспериментальное сравнение предложенных схем алгоритмов муравьиной колонии с мультистартовыми процедурами, основанными на локальном поиске.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.239, запросов: 244