Михайлова А.Н.
ИСПОЛЬЗОВАНИЕ МЕТОДА КОЛЕСА РУЛЕТКИ ПРИ РЕШЕНИИ ЗАДАЧИ МАРШРУТИЗАЦИИ С ПОМОЩЬЮ ГЕНЕТИЧЕСКОГО АЛГОРИТМА *
Аннотация:
в статье описывается один из методов отбора особей популяции при решении задач маршрутизации с помощью генетического алгоритма – метод колеса рулетки, основанный на вероятностных значениях
Ключевые слова:
генетический алгоритм, задачи маршрутизации, метод колеса рулетки, мутации, скрещивание
На сегодняшний день использование логистических информационных систем, а в частности построение маршрутов для перевозки грузов, является несомненно актуальным, так как это эффективный способ экономии ресурсов при транспортировке грузов [4]. Для разработки программных средств для решения задач, рассматриваемой области, необходимо проведение научно-исследовательских работ, результатом которых является выявление эффективных алгоритмов, подходящих для применения на практике. Одна из важных функций таких программных средств – расчет и построение эффективных маршрутов транспортировки грузов [2]. Для решения задач маршрутизации применяются несколько подходов: точные методы, эвристические методы, а также мета-эвристические методы. Из перечисленных методов решения задач маршрутизации наиболее популярными стали эвристические и мета-эвристические методы, так как для задач большой размерности они дают приемлемое решение за ограниченное время, в отличие от точных методов, которые требуют большого временного ресурса. Эвристические алгоритмы – алгоритмы решения задачи, включающие практический метод, который не является гарантированно точным (оптимальным), но является рациональным и достаточно хорошим для решения поставленной задачи. Мета-эвристические алгоритмы – методы, в которых изучаются наиболее перспективные пространства решений. Главным условием успешного мета-эвристического алгоритма является получение результата, качественно превосходящего классические эвристики. На сегодняшний день наибольший интерес для изучения и развития представляют мета-эвристические алгоритмы, так как они хорошо зарекомендовали себя и с точки зрения быстроты нахождения решения, и с точки зрения качества найденного решения [1]. Одним из эффективных мета-эвристических алгоритмов является генетический алгоритм для решения NP-трудных задач с большим количеством данных. Простота расчетов и быстродействие выполняемых операций позволяет производить большое количество итераций, тем самым найти эффективное решение в условиях ограниченного времени. Основная идея генетического алгоритма – организация «естественного отбора» и «борьбы за существование» среди полученных решений. Приспособленность особи определяет значение целевой функции. При этом невозможно заранее сказать, насколько близким будет локальный экстремум по отношению к оптимальному, также, как и определить вектор направления новой локальной точки, так как это случайные процессы. Генетический алгоритм использует биологические аналогии, и при формулировке и решении задач применяется терминология, напоминающая биологическую, например особью или хромосомой называется произвольное допустимое решение, содержащее n генов, которые сцеплены между собой и расположены в линейной последовательности (последовательность пунктов для посещения с начальной и конечной точкой на складе) [3]. А ген, в свою очередь, - единица наследственного материала, отвечающая за формирование альтернативных признаков особи (пункт для посещения). Популяцией называется набор всех пробных решений. При работе с генетическим алгоритмом применяются скрещивание и мутации. Скрещивание – это создание из исходной популяции дочерней, при этом в новой популяции пробные решения ближе к исходному глобальному экстремуму целевой функции. Для проведения процедуры скрещивания необходимо выбрать брачную пару для скрещивания. Затем между исходными особями происходит обмен хромосомами. После процедуры скрещивания проводится корректировка, то есть удаление дублирующийся генов и добавление недостающих. Затем с некоторой степенью вероятности проводится мутация. Мутации имеют случайный характер, и не зависят ни от генетического кода особи, ни от количественных значений целевой функции. В процессе мутации в одном или нескольких генах происходит замена одного нескольких пунктов для посещения на другие, при этом они принадлежат к генофонду (конечное множество всех последовательностей пунктов для посещения). Главная их задача мутации– переход в область другого локального оптимума. Существует большое множество схем для осуществления отбора хромосом в следующее поколение. Рассмотрим подробнее метод, основанный на принципе колеса рулетки. Его можно описать следующим образом: сектора колеса рулетки соотносятся с хромосомами, и чем больше значении функции приспособленности хромосомы, тем больше размер сектора на колесе рулетки, то есть, величина сектора пропорциональна значению целевой функции. Таким образом, чем больше сектор на колесе рулетке, тем выше шанс, что именно эта хромосома будет выбрана. Однако особи с слишком малым значением целевой функции могут слишком быстро исключится из популяции, что может привести к сходимости генетического алгоритма, поиску решения только в одной области. Чтобы этого не произошло, используются мутации разного вида. Для выявления эффективности метода при решении задач маршрутизации, нужно проводить более глубокое исследование.
Номер журнала Вестник науки №5 (26) том 1
Ссылка для цитирования:
Михайлова А.Н. ИСПОЛЬЗОВАНИЕ МЕТОДА КОЛЕСА РУЛЕТКИ ПРИ РЕШЕНИИ ЗАДАЧИ МАРШРУТИЗАЦИИ С ПОМОЩЬЮ ГЕНЕТИЧЕСКОГО АЛГОРИТМА // Вестник науки №5 (26) том 1. С. 88 - 91. 2020 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/3043 (дата обращения: 25.04.2024 г.)
Вестник науки СМИ ЭЛ № ФС 77 - 84401 © 2020. 16+