Применение эвристических алгоритмов для поиска решений задачи о покрытии множества
ВВЕДЕНИЕ
Проблема покрытия множества имеет множество приложений в различных областях, таких как логистика, составление расписаний и распределение ресурсов. Это хорошо известная комбинаторная оптимизационная задача, которая включает в себя выбор подмножества элементов из множества, чтобы покрыть все остальные элементы в этом множестве. Например, в логистике проблема покрытия множества возникает при планировании маршрутов для транспортных средств доставки, чтобы охватить все необходимые места с минимальным использованием ресурсов.Оптимальное решение проблемы покрытия множества является NP-трудной задачей, что означает, что нахождение точного решения для больших экземпляров задачи может занять много времени или даже быть невозможным. Поэтому были разработаны эвристические алгоритмы для эффективного и практичного решения этой проблемы. В данной работе мы сосредоточились на разработке эвристических алгоритмов для решения задачи покрытия множества.
ВВЕДЕНИЕ 4
1 Постановка задачи 6
1.1 Задача о покрытии множества 6
1.2 Матричный вид задачи о покрытии множества 6
2 Методы решения задачи покрытия множества 7
2.1 Генетические алгоритмы 7
2.2 реализация генетического алгоритма 14
2.3 Метод роя частиц 16
2.4 Метод имитации отжига 20
3 Тестирование 21
3.1 Сравнительный анализ выбранных алгоритмов 21
3.2 Результат работы алгоритмов и их сравнение 22
ЗАКЛЮЧЕНИЕ 33
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 34
ПРИЛОЖЕНИЕ А 36
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Коновалов, И. С. Сравнительный анализ работы жадного алгоритма Хватала и модифицированной модели Голдберга при решении взвешенной задачи нахождения минимального покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Труды СКФ МТУСИ. 2015. Ч. I. С. 366-370.
Еремеев, А. В. Генетический алгоритм для задачи о покрытии / А. В. Еремеев // Дискретный анализ и исследование операций. — 2000. — Т. 7, № 1. — С. 47–60
Вирсански Э. Генетические алгоритмы на Python / пер. с англ. А. А. Слинкина. М.: ДМК Пресс, 2020. 286 с.: ил. ISBN 978-5-97060-857-9
J. Kennedy and R. C. Eberhart. Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks, Piscataway, 1995.
J. Dr´eo, A. P´etrowksi, P. Siarry and E. Taillard. Metaheuristics for hard optimization. Springler, Heidelberg, 2006.
J. Kennedy and R. C. Eberhart. A new optimizer using particle swarm theory. In Proceedings of the 6th International Symposium on Micromachine and Human Science, Nagoya, 1995.
J. Kennedy and R. C. Eberhart. A discrete binary version of the particle swarm algorithm. InConference on Systems, Man and Cybernetics, Hyatt, 1997.
Khalil Amine, "Multiobjective Simulated Annealing: Principles and Algorithm Variants", Advances in Operations Research, vol. 2019, Article ID 8134674, 13 pages, 2019. https://doi.org/10.1155/2019/8134674Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик. — Москва : Физматлит, 2010. — 368 с.
Применение генетических алгоритмов к решению задач дискретной оптимизации / Батищев Д.И., Неймарк Е.А., Старостин Н.В., 2007.
В отличии от эволюционных алгоритмов, которые основываются на колониях социальных насекомых, таких как муравьи, пчелы и термиты, была предложена новая метаэвристика Кеннеди и Эбехартом [4] для решения неограниченных задач нелинейной оптимизации, которую они назвали оптимизацией роя частиц (PSO). Идея PSO заключается в следующем: генерируется начальная популяция частиц, каждая из которых находится в начальной позиции пространства решений и имеет определенную начальную скорость. Каждая частица i характеризуется своим положением и вектором изменения положения, называемым скоростью [5].Частица - это кандидат на решение роя на одном из шагов поиска. Рой - это весь набор частиц на данной итерации. Скорость - это число, которое определяет движение частиц. Каждая частица проходит через n-мерное пространство поиска, и ее скорость обновляется в соответствии со скоростью других частиц.Для каждой частицы сохраняется ее лучшее значение в процессе поиска, и это значение называется pbest. Общее значение pbest, полученное при оценке всех частиц в популяции, является лучшим решением данного алгоритма, которое называется gbest. Значения pbest и gbest используются для обновления скоростей частиц в пространстве поиска. У частиц, которые находятся далеко от перспективных областей пространства поиска, скорость увеличивается, а у остальных частиц - уменьшается.