РАЗРАБОТКА и АНАЛИЗ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ ПРОИЗВОДСТВА НА МЕСТНОСТИ

ВВЕДЕНИЕ 6
1 АЛГОРИТМЫ, ИСПОЛЬЗУЕМЫЕ ДЛЯ РЕШЕНИЯ ЗАДАЧ
РАЗМЕЩЕНИЯ 11
1.1 История возникновения генетических алгоритмов 11
1.2 Описание общего принципа работы генетического алгоритма 18
1.3 Пример простой реализации на C++ 22
1.4 Тестовый пример генетического алгоритма для исследуемой
задачи 23
1.5 Алгоритм поиска с чередующимися окрестностями для
простейшей задачи размещения 24
1.6 Описание общего принципа работы VNS алгоритма 25
2 ГИБРИДНАЯ МЕТАЭВРИСТИКА ДЛЯ ПРОСТЕЙШЕЙ
ЗАДАЧИ РАЗМЕЩЕНИЯ 27
2.1 Описание проблем генетического алгоритма 27
2.2 Описание общих идей алгоритмов локального поиска 29
2.3 Описание алгоритма основанного на улучшенном алгоритме
локального поиска 29
2.4 Гибридные схемы 32
3 ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРЕМЕНТ 35
3.1 Применение алгоритма локального поиска с чередующимися окрестностями для решения задачи размещения и его исследование 35
ЗАКЛЮЧЕНИЕ 44
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 46

Купить

Теория и методы решения задач оптимизации является одним из интенсивно развивающихся направлений математической кибернетики. Причиной развития данного направления стали проблемы, возникающие в управлении, планировании, проектировании и других областях. Применение таких моделей позволяет обосновать рекомендации при принятии решений и повысить их качество.
Одним из важных направлений исследования в рассматриваемой области является анализ и решение задач оптимального размещения объектов. Среди задач оптимального размещения обычно выделяют два класса: задачи размещения взаимосвязанных объектов и задачи размещения- распределения. Их основное отличие в том, что в задачах первого типа нужно найти места расположения объектов, между которыми имеются связи (необязательно между всеми). В задачах второго типа связи устанавливаются в результате их решения[1]. Примером первого типа являются квадратичная задача о назначениях и задача Вебера. Квадратичной задачей о назначениях является задача, целевая функция которой выражается через квадраты. Задача о назначениях - одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе. В наиболее общей форме задача формулируется следующим образом: имеется некоторое число работ
и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы,
но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами. Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют в виду линейную задачу о назначениях. Немалый вклад в разработку данной проблемы внесли Ахмедов И.С., Демиденко В.А., Жак С.Б., Зинченко А.Б., Иорданский М.А., Панюков А.В., Сигал И.Х., Стоян Ю.Г., Трубин В.А., Яковлев С.В., Adolfson D., Beckmann M.J., Francis L.R., Koopmans T.C., Wesolowsky G.O. и ряд других авторов [2,3,4,6,7,8,9,13,16,17,18,19,20,21]. Классическими представителями второго типа задач является: простейшая задача размещения, задачи о р-медиане и р-центре. Разработкой занимались Агеев А.А., Бахтин
A. Е., Береснев В.Л., Гимади Э.Х., Глебов Н.И., Дементьев В.Т., Емеличев
B. А., Колоколов В.А., Кочетов Ю.А., Леванова Т.В.,
Лореш М.А., Hakimi S.L., Kariv O., Krarup J., Pruzan P.M. и другие [22,23,24,25,26,27,28,29].
При решении задач оптимального размещения необходимо учитывать различные ограничения на расположение объектов. Строительные нормы и правила определяют противопожарные, санитарные и другие нормативы при проектировании генпланов задают ограничения на минимально допустимые расстояния между объектами. Технологией производства определяются максимально допустимые расстояния между объектами.
Структура области, в которой производится размещение, является одной из основных характеристик рассматриваемых задач размещения. Она может быть непрерывной или дискретной. Размерность непрерывной области может быть различной: одномерная - линия, двумерной - плоскость т.д. Существенное значение для анализа и разработки методов решения таких задач имеет метрика, в которой измеряются расстояния между объектами. Например, минимально допустимые расстояния между объектами измеряются в евклидовой метрике, а длина связей - в прямоугольной метрике.
Актуальность темы: обуславливается востребованностью найти такое множество открываемых предприятий, которое с минимальными затратами позволяет удовлетворить потребности всех потребителей.
Объект исследования: алгоритмы, применяемые для простейшей задачи размещения.
Предмет исследования: реализация алгоритмов.
Цель исследования: сравнение точности и времени работы алгоритмов на различных группах тестовых примеров.
Задачи исследования:
1. Обзор существующих алгоритмов решения рассматриваемых задач.
2. Применение алгоритмов для простейшей задачи размещения.
3. Анализ разработанных алгоритмов.
Научная новизна исследования: в работе получены результаты сравнительных тестов двух алгоритмов: генетического и локального поиска с чередующимися окрестностями. Среди полученных результатов можно выделить следующие.
1. Генетический алгоритм для задач размещения имеет невысокую точность, требует много итераций и больших временных затрат.
2. Алгоритм локального поиска с чередующимися окрестностями для задач размещения имеет более высокую точность по сравнению с генетическим алгоритмом.
3. Использование алгоритма, основанного на улучшенном алгоритме локального поиска для задач размещения, является более эффективным.
Практическая значимость исследования:
Практическая значимость работы состоит в том, что ее результаты могут служить основой для разработки программноалгоритмического обеспечения решения реальных прикладных задач в области проектирования и оптимизации функционирования логистических систем предприятий, а также при решении задач управления вычислительными ресурсами.
Работа состоит из введения, трех глав, заключения и списка литературы. Объем работы составляет 51 страниц. Список литературы содержит 55 наименований.
Во введении описаны актуальность данной темы, цели и задачи исследования, научная новизна исследования и практическая значимость.
В первой главе описывается история создания генетических алгоритмов. Рассматривается описание общего принципа работы генетического алгоритма и описание алгоритма для исследуемой задачи. Приведен пример простой реализации алгоритма на языке С++. Приведен тестовый пример алгоритма для простейшей задачи размещения. Описывается алгоритм поиска с чередующимися окрестностями, много вариантов ее реализации, особенно для задач большой размерности. Приведен общий принцип работы VNS алгоритма.
Во второй главе рассмотрены проблемы генетического алгоритма, такие как: невысокая точность, большие затраты по времени, большое количество итераций и т.д. Описаны общие идеи алгоритмов локального поиска, рассмотрены алгоритмы, основанных на улучшенном алгоритме локального поиска (VNDS, SVNS, PVNS), а также гибридные схемы алгоритма, такие как «VNS и поиск с запретами», «VNS и вероятностные жадные алгоритмы с адаптацией» и другие.
В третьей главе проведен вычислительный эксперимент, связанный с вопросами применения алгоритма локального поиска
с чередующимися окрестностями для задач дискретной оптимизации. Разработаны алгоритмы решения двухстадийной задачи размещения, экспериментально исследовано их поведение при различных наборах окрестностей и значениях параметров на трудных классах тестовых задач.
В заключении перечислены основные результаты работы.

Купить