Родзин С.И., Курейчик В.В

Родзин С.И., Курейчик В.В. Состояние, проблемы и перспективы развития биоэвристик

(Опубликовано в журнале «Программные системы и вычислительные методы» -2, 2016)

Введение

Многие процессы в науке и технике, экономике и бизнесе формулируются как задача оптимизации: минимизировать время, стоимость, риск или максимизировать прибыль, производительность, эффективность. Перспективным классом приближенных методов, применимых к разнообразным оптимизационным задачам являются биоэвристические алгоритмы или, просто, биоэвристики. Биоэвристики - это алгоритмические приёмы, которые позволяют ограничить перебор,и основаны на правилах моделирования процессов эволюции, природных аналогиях, на статистике и итерационном поиске решения задачи. Целью работы является анализ фундаментальных результатов, полученных в области разработки биоэвристик, закономерностей, лежащих в их основе, особенностей кодирования решений и базового цикла вычислений, а также оценка времени работы биоэвристик.

Обзор фундаментальных результатов в области биоэвристик

Наиболее значительный вклад в разработку когнитивных биоинспирированных методов внесли следующие ученые: Л. Растригин предложил методы случайного поиска [1], Nelder и Mead представили эвристики, которые для некоторых задач сходятся в нестационарных точках [2], Fogel и др. разработали алгоритм эволюционного программирования [3], Kernighan и Lin создали метод поиска в глубину [4], Holland предложил генетический алгоритм [5], Smith разработал алгоритм генетического программирования [6], Kirkpatrick и др. предложили метод имитации отжига [7], Glover разработал алгоритм табуированного поиска [8], Moscato представил меметический алгоритм [9], Dorigo предложил муравьиный алгоритм [10], Wolpert и Macready доказали NFL-теорему [11]. Большой вклад в развитие теории и практики биоэвристик внесли научные школы Д. Батищева, И. Букатовой, Д. Голдберга, Ж. Гонкальвеса, Б. Доерра, В. Емельянова, К. Игеля, К. де Йонга, В.М. Курейчика, Р. Мииккулайнена,С. Нолфи,И. Норенкова, В. Редько, Л. Уитли, К. Феррейры, Д. Флореано, Н. Хансена, Дж. Шапиро,З. Яо.

В информатике и математической оптимизации теоретические вопросы создания биоэвристик весьма разнообразны: сходимость алгоритмов; наличие стратегий, которые направляют процесс поиска оптимума; наличие цели для эффективного исследованияпространства поиска оптимальных решений; оценка временной сложности алгоритмов и др.

Существуют самые различные классификации биоэвристик [12]. Например, классификация по типу стратегии поиска: улучшение простых локальных алгоритмов поиска, таких как моделирование отжига, поиск с запретами, локальный поиск с возвратами, поиск в переменной окрестности и др.; обучение в ходе поиска, например, алгоритмы колонии муравьев, эволюционные алгоритмы. Другой способ классификации алгоритмов зависит от того одно или множество решений улучшается в процессе поиска оптимума, например, траекторные и популяционные алгоритмы. В свою очередь, популяционные алгоритмы разделяются на следующие категории: эволюционные, моделирующие коллективное поведение агентов в популяции или рое (например, рой частиц, колония муравьев, пчелиный рой, рой светлячков, гнездовый паразитизм в поведении кукушки, роение бактерий, обезьяний поиск, алгоритм, инспирированный летучими мышами, поиск косяком рыб, сорняковый алгоритм, алгоритм растущих деревьев); алгоритмы, вдохновленные неживой природой (например, гравитационный, диффузионный, гармонический поиск); алгоритмы, инспирированные человеческим обществом (алгоритм меметики, культурный алгоритм, алгоритм эволюции разума), и др.

Читать статью: http://nbpublish.com/library_read_article.php?id=-37360

Источник: nbpublish.com

Комментарии: