Построение модифицированной базисной структуры бионического поиска для задач об экстремальном пути на основе стратегии адаптации
Аннотация
В статье рассматривается проблема разработки алгоритма бионического поиска для задач об экстремальном пути на графе. В настоящее время разработка эффективных методов и алгоритмов для задач данного типа осуществляется много лет, являясь по - прежнему актуальной проблемой. Перспективной является разработка бионических алгоритмов (БА) на основе эволюционных стратегий, особенно при решении трудоемких задач оптимизации. К преимуществам можно отнести: возможность выполнения эволюционного и генетического поиска, а также то, что БА состоит в параллельной генерации наборов квазиоптимальных альтернативных решений с возможной «миграцией» решений между этими наборами. Предложена реализация общей стратегии адаптации размера популяции использованием последовательности решета Эратосфена, позволяющая адаптироваться к характеристикам бионического поиска.
Ключевые слова: эволюция, бионический алгоритм, задача об экстремальном пути, адаптация
Введение
При решении задач об экстремальных путях, эффективно используют стратегии, концепции, методы и механизмы эволюционного моделирования на основе бионического поиска. Бионический поиск (БП) – это последовательное преобразование одного конечного нечеткого множества альтернативных решений в другое.
Бионические алгоритмы доказали свою эффективность при решении трудоемких задач оптимизации, аппроксимации, интеллектуальной обработки данных. К преимуществам бионического поиска относятся адаптивность, способность к обучению, параллелизм, возможность построения гибридных систем на основе комбинирования.
Основная часть
Бионический алгоритм построен на создании единой концепции эволюционных вычислений, включающих генетические алгоритмы (ГА), генетическое программирование (ГП), эволюционные стратегии и эволюционное программирование (ЭП) [1]. К достоинствам применения бионического алгоритма (БА) для решения задачи об экстремальном пути можно отнести:
- Возможность выполнения двух видов поиска: эволюционного (ВСА – одной генерации ≈О(n)) и генетического (ВСА – одной генерации ≈О(n) - О(n3)). Кроме того, выбор начальных решений осуществляется из «оптимизационных» методов нахождения кратчайшего пути.
- Бионические алгоритмы, по мнению авторов, дадут лучшие решения, т.е. хорошая приспособленность к внешней изменяющейся среде.
- БА состоит в параллельной генерации наборов квазиоптимальных альтернативных решений с возможной «миграцией» решений между этими наборами.
Основная часть
При выполнении бионического поиска нахождении экстремального пути, предлагается выполнить микро-, макро-, мета - эволюцию. При этом, используя мета - эволюцию, здесь создается не одна, а некоторое множество популяций. Поиск решений осуществляется путем объединения хромосом в различных популяциях.
На рис. 1 представлена модифицированная базисная структура оптимизационного процесса, основанная на принципах бионического поиска для решений задач об экстремальных путях. Ее преимущество состоит в том, что в ней все строительные блоки связаны с блоком адаптации, так и между собой. Блок адаптации определяет эволюцию не в простой форме связи между наследственной изменчивостью популяции и средой, а в более сложной форме. Предназначение данного блока состоит в настройке и изменении порядка использования и применения различных генетических операторов и схем поиска. В блоке МОР (модифицированный оператор рекомбинации), предложена адаптивная стратегия работы оператора. Пути выполнения рекомбинации разбиты на два этапа:
1. Исследование влияния изменения размера популяции на характеристики бионического поиска.
2. Разработка стратегии адаптации размера популяции на основе результатов, полученных на первом этапе.
В результате решения задачи первого этапа на основании экспериментальных данных сформулирована следующая стратегия адаптации размера популяции: «Если значение целевой функции в текущей популяции хуже или остается неизменным, как и в предыдущей популяции, то есть отсутствует прогресс, то размер популяции необходимо увеличить. В случае если значение целевой функции в популяции улучшается, то размер популяции следует уменьшить».
Предложена следующая реализация общей стратегии адаптации размера популяции использованием последовательности решета Эратосфена, позволяющая адаптироваться к характеристикам бионического поиска:
,
,
где KI – количество элитных особей, Rp – размер популяции, где N(t) – размер популяции в поколении t ; uk– k-й член последовательности решета Эратосфена; q(t) – направление изменения (увеличение или уменьшение) размера популяции в поколении t ; F(t) – значение целевой функции в популяции; k – количество поколений, в течение которых, направление qизменения размера популяции остается постоянным.
При дальнейшей реализации алгоритма лучшие и отобранные элементы из родителей и потомков будут выбираться для формирования новой популяции.
 |
Рис. 1. – Модифицированная базисная структура оптимизационного процесса
Определяющими эволюцию, служат модифицированные операторы мутации, реализующиеся под действием естественного отбора [2,3].
Проводимая сортировка текущей популяции альтернативных решений позволяет повысить эффективность бионического поиска за счет большей структурированности множества альтернативных решений и дает возможность динамического регулирования направления поиска. Таким образом, появляется дополнительный инструмент для самоадаптации и настройки параметров бионического поиска.
Блок анализа неперспективных решений собирает и анализирует решения, получаемые в процессе выполнения бионического поиска. В результате проведенного анализа полученные решения сортируются. К неперспективным решениям применяется эволюционный алгоритм, с целью улучшения качества решений.
Заключение
На основе модифицированной базисной структуры оптимизационного процесса, основанной на принципах бионического поиска, был построен параллельный бионический алгоритм (ПБА), для задачи об экстемальном пути. По результатам экспериментальных исследований параллельный бионический алгоритм для задачи об экстремальном пути показали преимущество по сравнению с последовательными методами (ПА) и простыми генетическими алгоритмами (ПГА) и позволяет повысить качество решений ориентировочно на 20% - 25%. На рис.2 представлена гистограмма сравнения качества решения, получаемого разработанными алгоритмами.
Рис. 2. – Гистограмма сравнения качества решения, получаемого разработанными алгоритмами
Литература
- Курейчик, В.М. Совместные методы квантового и бионического поиска [Текст]/ В.М. Курейчик//Труды конференций IEEE AIS’04, CAD-2004, М.: Физматлит, 2004. с. 12-19
- Развитие теории эволюционного моделирования на основе генетических методов поисковой адаптации при решении оптимальных задач проектирования, сверхбольших интегральных схем (СБИС) [Текст]: отчет о НИР / РГАСХМ; рук. Чернышев Ю.О.; исп. Басова А.В., Венцов Н.Н., Полуян А.Ю. – Ростов н/Д, 2009. – № ГР 018.00.62.42.02.
- Чернышев, Ю.О. Решение задач транспортного типа генетическими алгоритмами [Текст]: Монография/ Ю.О. Чернышев, А.В. Басова, А.Ю. Полуян. – Ростов н/Д: Изд-во ЮФУ, 2008. – 73с.