4
Теоретические вопросы и современные проблемы развития когнитивных биоинспирированных алгоритмов оптимизации
Родзин Сергей Иванович
кандидат технических наук
профессор, Южный федеральный университет
Курейчик Владимир Викторович
доктор технических наук
профессор, Южный федеральный университет
Аннотация
Предметом обзора являются проблемные вопросы и современное состояние исследований в области когнитивных биоинспирированных алгоритмов оптимизации. Среди множества проблем, которые возникают перед исследователями, как в области теории, так и в многочисленных практических приложениях значительную долю составляют оптимизационные проблемы. Для некоторых из них решение невозможно найти без полного перебора вариантов. Однако размерности этих задач таковы, что реализация перебора вариантов практически невозможна из-за чрезвычайно больших временных затрат. Альтернативным походом к решению этих задач является применение методов, базирующихся на методологии когнитивных биоинспирированных алгоритмов. После того как компьютерные системы стали достаточно быстродействующими и недорогими, биоинспирированные алгоритмы превратились в важный инструмент поиска близких к оптимальным решений задач, которые до этого считались неразрешимыми. Методологической и теоретической основой обзорного исследования являлись положения теории искусственного интеллекта и биоинспирированных вычислений, теории принятия решений и методов оптимизации. Обзор содержит перечень мировых научных школ и ученых, внесших значительный вклад в разработку когнитивных биоинспирированных алгоритмов, а также краткое описание классификации, терминологии и библиотек биоинспирированных алгоритмов. Представлен классический результат в теории когнитивных биоинспирированных алгоритмов - теорема Холланда и NFL-теорема. Анализируются закономерности, основные элементы и структура когнитивных биоинспирированных вычислений, вопросы представления (кодирования) решений, базовый цикл биоинспирированных алгоритмов, расширение когнитивных возможностей операторов биоинспирированных алгоритмов, а также перспективное направление в анализе времени работы когнитивных биоинспирированных алгоритмов - анализ дрейфа.
Ключевые слова: когнитивный биоинспирированный алгоритм, метаэвристика, оптимизация, эволюционные вычисления, эволюционный оператор, NFL-теорема, анализ дрейфа, функция приспособленности, моделирование, программирование
An overview concerns topical issues and the current situation regarding cognitive bioinspiral optimization algorithms research. Optimization problems form the majority among the many problems, which are faced by the researchers in the theoretical sphere as well as in the sphere of practical application. For some such problems the solution requires a full search for options. However, the dimensions of these problems are such that the implementation of the search for options is almost impossible due to the extremely high time costs. An alternative approach to solving these problems involves the application of methods based on the methodology of cognitive bioinspiral algorithms. When the computer systems became sufficiently fast and inexpensive, the bioengineered algorithms formed an important tool for finding solutions close to optimal solutions for the problems,which were previously been considered insoluble. The methodological and theoretical basis of the survey was found in the provisions of the theory of artificial intelligence and bioinspired computing, decision theory and optimization methods. The review includes a list of world scientific schools and scientists who have made a significant contribution to the development of cognitive bioinspiral algorithms, and also a brief description of the classification, terminology and libraries of bioengineered algorithms. A classical result is presented in the theory of cognitive bioinspiral algorithms - the CPT theorem and the NFL-theorem. The authors provide analysis of regularities, basic elements and structure of cognitive bioinspired calculations, they analyze the issues concerning representation (coding) of solutions, basic cycle of bioinspired algorithms, extension of cognitive capabilities of operators of bioinspiral algorithms, and drift analysis as a promicing direction in the sphere of time of cognitive bioinspiral algorithms analysis.
Keywords:
metaheuristics, fitness function, evolutionary computation, evolution operator, NFL-theorem, drift analysis, optimization, modeling, programming, cognitive bioinspired algorithm
алгоритм кодирование оптимальное решение
Введение
Задач поиска оптимальных решений в условиях различных ограничений бесчисленное множество. Каждый процесс в науке и технике, экономике и бизнесе имеет потенциал для оптимизации и может быть сформулирован как оптимизационная задача. Оптимизация состоит в минимизации времени, стоимости, риска или максимизации прибыли, качества, эффективности. Большинство реальных задач оптимизации сложны, их трудно точно решить в течение разумного времени. Основной альтернативой для решения этих задач являются приближенные методы. Наиболее общим классом приближенных методов, применимых к разнообразным оптимизационным задачам являются метаэвристические методы. Они могут быть адаптированы, чтобы решить любую проблему оптимизации, обеспечив достаточно хорошее решение в задаче оптимизации, особенно с неполной информацией или ограниченными возможностями вычисления. Многие метаэвристики основаны на процедурах, содержащих элементы стохастической оптимизации со случайными переменными. Если множество допустимых решений велико, то метаэвристики зачастую позволяют найти близкие к оптимальным решения с меньшими вычислительными затратами, нежели классические методы. Это перспективный подход к решению многих оптимизационных проблем.
Особое место среди метаэвристик занимают когнитивные биоинспирированные алгоритмы, как математические преобразования, трансформирующие входной поток информации в выходной и основанные на правилах имитации механизмов эволюции, природных аналогий, на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому решению. Под термином «когнитивные» здесь понимается совокупность принципов и подходов, моделирующих познавательные и поведенческие процессы для решения конкретных прикладных задач. Используя компьютерное моделирование на основе когнитивных биоинспирированных алгоритмов, можно создавать и оптимизировать сложные системы, для которых не существует аналитического описания. Когнитивные биоинспирированные алгоритмы способствуют решению не только оптимизационных проблем, но также представлению сложного поведения в виде результата взаимодействия относительно простых структур. Они демонстрируют целенаправленное, устойчивое к флуктуациям и почти оптимальное поведение, не являясь инструктивным процессом, вполне подходят в качестве основы когнитивной обработки данных при решении задач обучения без учителя. Это мощные методы, особенно в контексте параллельных и распределенных вычислений.
Целью обзора является анализ достигнутых результатов в области теории, моделей и когнитивных биоинспирированных алгоритмов поддержки принятия оптимальных решений, а также описание их закономерностей, основных элементов, структуры и кодирования решений, изучение когнитивных возможностей операторов биоинспирированных алгоритмов, представление современных достижений в таком перспективном направлении как дрейф-анализ времени работы когнитивных биоинспирированных алгоритмов.
Научные школы
Наиболее значительный вклад в разработку когнитивных биоинспирированных методов внесли следующие ученые: Л. Растригин предложил методы случайного поиска [1], Nelde r и Mead представили эвристики, которые для некоторых задач сходятся в нестационарных точках [2], Fogel и др. разработали алгоритм эволюционного программирования [3], Kernighan и Lin создали метод поиска в глубину [4], Holland предложил генетический алгоритм [5], Smith разработал алгоритм генетического программирования [6], Kirkpatrick и др. предложили метод имитации отжига [7], Glove r разработал алгоритм табуированного поиска [8], Moscato представил меметический алгоритм [9], Dorigo предложил муравьиный алгоритм [10], Wolpert и Macready доказали NFL -теорему [11]. Фундаментальные результаты в области теории и методов принятия оптимальных решений получены А. Петровским [12], А. Еремеевым , В. Вагиным [13], В. Городецким [14], А. Смирновым [15]. Известно несколько современных книг и обзорных статей, опубликованных по этой теме [16-24]. Получены некоторые теоретические результаты, указывающие на возможность нахождения глобального оптимума биоинспирированными алгоритмами для отдельных задач [19]. Были опубликованы несколько десятков новых когнитивных биоинспирированных алгоритмов для эффективного решения трансвычислительных задач [25-30].
Отметим следующие исследовательские группы и научные школы в области разработки когнитивных биоинспирированных алгоритмов:
· научная школа Дж. Холланда является наиболее известной мировой школой, представляющей направление машинного обучения генетических алгоритмов. Основное направление исследований сосредоточено на понимании процессов индуктивных рассуждений и обучения. Алгоритмы, разрабатываемые представителями школы, рассматривают обучаемость как качество адаптивной системы, способной совершенствовать свое поведение, накапливая, например, опыт решения интеллектуальных задач анализа информации. Главное внимание специалисты школы уделяют разработке индуктивных программ способных обучаться на основе обобщения правил классификации и извлечения из предъявляемых примеров (прецедентов) полезных закономерностей;
· тематика исследований, ведущихся в университете Остина (США) под руководством Р. Мииккулайнена , включает разработку когнитивных биоинспирированных алгоритмов кооперативной коэволюции в многоагентных системах;
· лаборатория интеллектуальных систем в Цюрихе под руководством Д. Флореано ведет разработки эволюционного аппаратного и программного обеспечения для программных робототехнических систем, исследует поведение коллективных и роевых систем;
· основное направление исследований лаборатории в Риме под руководством С. Нолфи - изучение адаптивных систем, взаимодействующих с внешней средой и управляемых гибридными принципами «мягких» вычислений;
· центр исследований вычислительного интеллекта и его приложений в университете Бирмингема под руководством З. Яо выполняет проекты по разработке и применению нейроэволюционных алгоритмов с использованием эволюционного программирования;
· группа исследователей оптимизации адаптивных систем в институте нейроинформатики в университете Бохума (Германия) под руководством К. Игеля изучает взаимодействие обучения и эволюции при создании адаптивных информационных систем;
· лаборатория эволюционных вычислений Департамента компьютерных наук в университете Дж. Мейсона в США под руководством К. де Йонга исследует гибридные биоинспирированные методы, работает над проектами и приложениями моделей эволюции, необходимыми для лучшего понимания эволюционных систем, для обеспечения робастности, гибкости и адаптивности информационных систем. Главное внимание специалисты лаборатории уделяют решению сложных научных и технических проблем, таких как инновационное проектирование, оптимизация и машинное обучение;
· в аналогичном направлении, но с акцентом на генетические алгоритмы, работает под руководством Д. Голдбергалаборатория генетических алгоритмов в Иллинойском университете;
· активным научным центром, известным своими работами по вопросам развития теории и разработки эволюционных алгоритмов оптимизации с приложениями к сложным оптимизационным проблемам транспортного типа, является лаборатория информатики и автоматизации академии наук и университета Артца (Франция). Руководителем научной школы является профессор Ж. Гонкальвес ;
· известной мировой школой, представляющей направление эволюционного моделирования, является школа К. Феррейры в Великобритании. Основное направление исследований сосредоточено на программировании генетических выражений. Алгоритмы, разрабатываемые представителями школы, используют специфичные операторы комбинаторного поиска, которые увеличивают их эффективность.
Большой вклад в развитие теории и практики когнитивных биоинспирированных алгоритмов внесли научные школы Д. Батищева , И. Букатовой , Б. Доерра , В. Емельянова , В.М. Курейчика , И. Норенкова , В. Редько , Л. Уитли , Н. Хансена , Дж. Шапиро .
Классификация, терминология, библиотеки когнитивных биоинспирированных вычислений
В информатике и математической оптимизации теоретические вопросы создания алгоритмов, инспирированных природными процессами, весьма разнообразны. К ним относятся сходимость алгоритмов; наличие стратегий, которые направляют процесс поиска оптимума; наличие цели для эффективного исследования пространства поиска оптимальных решений; адаптивность алгоритмов, которая варьируется от простых локальных процедур поиска до сложных процедур машинного обучения; возможность обеспечить достаточно хорошее решение трансвычислительных задач, а также задач оптимизации с неполной информацией; недетерминированный характер биоинспирированных вычислений, оценка временной сложности алгоритмов, теория многокритериальной оптимизации и др.
Существуют самые разнообразные классификации когнитивных биоинспирированных вычислений [31-32]. Например, классификация по типу стратегии поиска: улучшение простых локальных алгоритмов поиска, таких как моделирование отжига, поиск с запретами, локальный поиск с возвратами, поиск в переменной окрестности и др.; обучение в ходе поиска, например, алгоритмы колонии муравьев, эволюционные алгоритмы. Другой способ классификации алгоритмов зависит от того одно или множество решений улучшается в процессе поиска оптимума, например, траекторные и популяционные алгоритмы. В свою очередь, популяционные алгоритмы разделяются на следующие категории: эволюционные, моделирующие коллективное поведение децентрализованных, самоорганизующихся агентов в популяции или рое (например, рой частиц, колония муравьев, пчелиный рой, рой светлячков, гнездовый паразитизм в поведении кукушки, роение бактерий, обезьяний поиск, алгоритм, инспирированный летучими мышами, поиск косяком рыб, сорняковый алгоритм, алгоритм растущих деревьев и др.); алгоритмы, вдохновленные неживой природой (например, гравитационный, диффузионный, гармонический поиск); алгоритмы, инспирированные человеческим обществом (например, алгоритм меметики, культурный алгоритм, алгоритм эволюции разума), и др. [33]. На рис. 1 приводится пример классификации эвристических вычислений [29].