Построение модифицированной базисной структуры бионического поиска для задач об экстремальном пути на основе стратегии адаптации
Использование стратегий, концепций, методов и механизмов эволюционного моделирования на основе бионического поиска при решении задач об экстремальных путях. Эффективность бионических алгоритмов при решении трудоемких задач оптимизации и аппроксимации.
| Рубрика | Математика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 30.05.2017 |
| Размер файла | 91,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Построение модифицированной базисной структуры бионического поиска для задач об экстремальном пути на основе стратегии адаптации
А.Ю. Полуян, П.А. Панасенко
Введение
При решении задач об экстремальных путях, эффективно используют стратегии, концепции, методы и механизмы эволюционного моделирования на основе бионического поиска. Бионический поиск (БП) - это последовательное преобразование одного конечного нечеткого множества альтернативных решений в другое.
Бионические алгоритмы доказали свою эффективность при решении трудоемких задач оптимизации, аппроксимации, интеллектуальной обработки данных. К преимуществам бионического поиска относятся адаптивность, способность к обучению, параллелизм, возможность построения гибридных систем на основе комбинирования.
Основная часть
бионический алгоритм моделирование экстремальный
Бионический алгоритм построен на создании единой концепции эволюционных вычислений, включающих генетические алгоритмы (ГА), генетическое программирование (ГП), эволюционные стратегии и эволюционное программирование (ЭП) [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 Гистограмма сравнения качества решения, получаемого разработанными алгоритмами
Литература
1. Курейчик, В.М. Совместные методы квантового и бионического поиска [Текст]/ В.М. Курейчик//Труды конференций IEEE AIS'04, CAD-2004, М.: Физматлит, 2004. с. 12-19.
2. Развитие теории эволюционного моделирования на основе генетических методов поисковой адаптации при решении оптимальных задач проектирования, сверхбольших интегральных схем (СБИС) [Текст]: отчет о НИР / РГАСХМ; рук. Чернышев Ю.О.; исп. Басова А.В., Венцов Н.Н., Полуян А.Ю. Ростов н/Д, 2009. № ГР 018.00.62.42.02.
3. Чернышев, Ю.О. Решение задач транспортного типа генетическими алгоритмами [Текст]: Монография/ Ю.О. Чернышев, А.В. Басова, А.Ю. Полуян. Ростов н/Д: Изд-во ЮФУ, 2008. 73 с.
Размещено на Allbest.ru
Подобные документы
Проектирование методов математического моделирования и оптимизации проектных решений. Использование кусочной интерполяции при решении задач строительства автомобильных дорог. Методы линейного программирования. Решение специальных транспортных задач.
методичка [690,6 K], добавлен 26.01.2015Деятельность при решении задач складывается из умственных действий и осуществляется эффективно, если первоначально она происходит на основе внешних действий с предметами. Главная проблема - дети не могут перейти от текста задачи к математической модели.
дипломная работа [79,2 K], добавлен 24.06.2008Применение теоремы Лагранжа при решении задач. Ее использование при решении неравенств и уравнений, при нахождении числа корней некоторого уравнения. Решение задач с использованием условия монотонности. Связи между возрастанием или убыванием функции.
реферат [726,8 K], добавлен 14.03.2013Методика нахождения различных решений геометрических задач на построение. Выбор и применение методов геометрических преобразований: параллельного переноса, симметрии, поворота (вращения), подобия, инверсии в зависимости от формы и свойств базовой фигуры.
курсовая работа [6,4 M], добавлен 13.08.2011Данный электронный учебник по математике предназначен для изучения темы "Использование неравенств при решении олимпиадных задач". Постановка и реализация задачи. Теоретические сведения по неравенствам Йенсена, Коши, Коши-Буняковского и Бернулли.
научная работа [124,1 K], добавлен 12.12.2009Математическое программирование - область математики, в которой изучаются методы решения задач условной оптимизации. Основные понятия и определения в задачах оптимизации. Динамическое программирование – математический метод поиска оптимального управления.
презентация [112,6 K], добавлен 23.06.2013Общая характеристика факультативных занятий по математике, основные формы и методы проведения. Составление календарно-тематического плана факультативного курса по теме: "Применение аппарата математического анализа при решении задач с параметрами".
курсовая работа [662,1 K], добавлен 27.09.2013Численные методы представляют собой набор алгоритмов, позволяющих получать приближенное (численное) решение математических задач. Два вида погрешностей, возникающих при решении задач. Нахождение нулей функции. Метод половинного деления. Метод хорд.
курс лекций [81,2 K], добавлен 06.03.2009Основные понятия математического моделирования, характеристика этапов создания моделей задач планирования производства и транспортных задач; аналитический и программный подходы к их решению. Симплекс-метод решения задач линейного программирования.
курсовая работа [2,2 M], добавлен 11.12.2011Метод последовательного исключения неизвестных (метод Гаусса) при решении задач аппроксимации функции в прикладной математике. Метод Гаусса с выбором главного элемента и оценка погрешности при решении системы линейных уравнений, итерационные методы.
контрольная работа [94,4 K], добавлен 04.09.2010
