Теоретические вопросы и современные проблемы развития когнитивных биоинспирированных алгоритмов оптимизации (обзор)

Родзин Сергей Иванович кандидат технических наук профессор, Южный федеральный университет 347928, Россия, Ростовская область, г. Таганрог, ул. Чехова, 80-1 Rodzin Sergey Ivanovich PhD in Technical Science Professor, Department of Software and Computer Usage, Southern Federal University 347928, Russia, Rostovskaya oblast', g. Taganrog, ul. Chekhova, 80-1 srodzin@yandex.ru Другие публикации этого автора

Курейчик Владимир Викторович доктор технических наук профессор, Южный федеральный университет 347928, Россия, Ростовская область, г. Таганрог, пер. Некрасовский, 44, оф. Г-435 Kureichik Vladimir Viktorovich Doctor of Technical Science Professor, Department of Computer Aided Design, Southern Federal University 347928, Russia, Rostovskaya oblast', g. Taganrog, per. Nekrasovskii, 44, of. G-435 vkur@sfedu.ru Другие публикации этого автора

Исследование выполнено в рамках проектной части госзадания Министерства образования и науки Российской Федерации (проект № 8.823.2014), а также при частичной финансовой поддержке гранта РФФИ (проект № 16-07-00336) в Южном федеральном университете.

Задач поиска оптимальных решений в условиях различных ограничений бесчисленное множество. Каждый процесс в науке и технике, экономике и бизнесе имеет потенциал для оптимизации и может быть сформулирован как оптимизационная задача. Оптимизация состоит в минимизации времени, стоимости, риска или максимизации прибыли, качества, эффективности. Большинство реальных задач оптимизации сложны, их трудно точно решить в течение разумного времени. Основной альтернативой для решения этих задач являются приближенные методы. Наиболее общим классом приближенных методов, применимых к разнообразным оптимизационным задачам являются метаэвристические методы. Они могут быть адаптированы, чтобы решить любую проблему оптимизации, обеспечив достаточно хорошее решение в задаче оптимизации, особенно с неполной информацией или ограниченными возможностями вычисления. Многие метаэвристики основаны на процедурах, содержащих элементы стохастической оптимизации со случайными переменными. Если множество допустимых решений велико, то метаэвристики зачастую позволяют найти близкие к оптимальным решения с меньшими вычислительными затратами, нежели классические методы. Это перспективный подход к решению многих оптимизационных проблем.

Особое место среди метаэвристик занимают когнитивные биоинспирированные алгоритмы, как математические преобразования, трансформирующие входной поток информации в выходной и основанные на правилах имитации механизмов эволюции, природных аналогий, на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому решению. Под термином «когнитивные» здесь понимается совокупность принципов и подходов, моделирующих познавательные и поведенческие процессы для решения конкретных прикладных задач. Используя компьютерное моделирование на основе когнитивных биоинспирированных алгоритмов, можно создавать и оптимизировать сложные системы, для которых не существует аналитического описания. Когнитивные биоинспирированные алгоритмы способствуют решению не только оптимизационных проблем, но также представлению сложного поведения в виде результата взаимодействия относительно простых структур. Они демонстрируют целенаправленное, устойчивое к флуктуациям и почти оптимальное поведение, не являясь инструктивным процессом, вполне подходят в качестве основы когнитивной обработки данных при решении задач обучения без учителя. Это мощные методы, особенно в контексте параллельных и распределенных вычислений.

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

Наиболее значительный вклад в разработку когнитивных биоинспирированных методов внесли следующие ученые: Л. Растригин предложил методы случайного поиска ^[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], А. Еремеевым, В. Вагиным ^[13], В. Городецким ^[14], А. Смирновым ^[15]. Известно несколько современных книг и обзорных статей, опубликованных по этой теме ^[16-24]. Получены некоторые теоретические результаты, указывающие на возможность нахождения глобального оптимума биоинспирированными алгоритмами для отдельных задач ^[19]. Были опубликованы несколько десятков новых когнитивных биоинспирированных алгоритмов для эффективного решения трансвычислительных задач ^[25-30].

Отметим следующие исследовательские группы и научные школы в области разработки когнитивных биоинспирированных алгоритмов:

• научная школа Дж. Холланда является наиболее известной мировой школой, представляющей направление машинного обучения генетических алгоритмов. Основное направление исследований сосредоточено на понимании процессов индуктивных рассуждений и обучения. Алгоритмы, разрабатываемые представителями школы, рассматривают обучаемость как качество адаптивной системы, способной совершенствовать свое поведение, накапливая, например, опыт решения интеллектуальных задач анализа информации. Главное внимание специалисты школы уделяют разработке индуктивных программ способных обучаться на основе обобщения правил классификации и извлечения из предъявляемых примеров (прецедентов) полезных закономерностей;
• тематика исследований, ведущихся в университете Остина (США) под руководством Р. Мииккулайнена, включает разработку когнитивных биоинспирированных алгоритмов кооперативной коэволюции в многоагентных системах;
• лаборатория интеллектуальных систем в Цюрихе под руководством Д. Флореано ведет разработки эволюционного аппаратного и программного обеспечения для программных робототехнических систем, исследует поведение коллективных и роевых систем;
• основное направление исследований лаборатории в Риме под руководством С. Нолфи – изучение адаптивных систем, взаимодействующих с внешней средой и управляемых гибридными принципами «мягких» вычислений;
• центр исследований вычислительного интеллекта и его приложений в университете Бирмингема под руководством З. Яо выполняет проекты по разработке и применению нейроэволюционных алгоритмов с использованием эволюционного программирования;
• группа исследователей оптимизации адаптивных систем в институте нейроинформатики в университете Бохума (Германия) под руководством К. Игеля изучает взаимодействие обучения и эволюции при создании адаптивных информационных систем;
• лаборатория эволюционных вычислений Департамента компьютерных наук в университете Дж. Мейсона в США под руководством К. де Йонга исследует гибридные биоинспирированные методы, работает над проектами и приложениями моделей эволюции, необходимыми для лучшего понимания эволюционных систем, для обеспечения робастности, гибкости и адаптивности информационных систем. Главное внимание специалисты лаборатории уделяют решению сложных научных и технических проблем, таких как инновационное проектирование, оптимизация и машинное обучение;
• в аналогичном направлении, но с акцентом на генетические алгоритмы, работает под руководством Д. Голдберга лаборатория генетических алгоритмов в Иллинойском университете;
• активным научным центром, известным своими работами по вопросам развития теории и разработки эволюционных алгоритмов оптимизации с приложениями к сложным оптимизационным проблемам транспортного типа, является лаборатория информатики и автоматизации академии наук и университета Артца (Франция). Руководителем научной школы является профессор Ж. Гонкальвес;
• известной мировой школой, представляющей направление эволюционного моделирования, является школа К. Феррейры в Великобритании. Основное направление исследований сосредоточено на программировании генетических выражений. Алгоритмы, разрабатываемые представителями школы, используют специфичные операторы комбинаторного поиска, которые увеличивают их эффективность.

Большой вклад в развитие теории и практики когнитивных биоинспирированных алгоритмов внесли научные школы Д. Батищева, И. Букатовой, Б. Доерра, В. Емельянова, В.М. Курейчика, И. Норенкова, В. Редько, Л. Уитли, Н. Хансена, Дж. Шапиро.

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

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

Рис. 1 – Пример классификации эвристических вычислений

Многие термины, используемые при описании когнитивных биоинспирированных алгоритмов, заимствованы из биологии, и обозначают элементы алгоритма, сходные с аналогичными объектами и процессами в природе. Например, в эволюционных алгоритмах используется следующая терминология: особь – потенциальное решение; потомок – копия потенциального решения (родителя); популяция - набор потенциальных решений; приспособленность (фитнесс) – качество; селекция – отбор особей на основе их приспособленностей; рекомбинация или кроссинговер – размножение, которое использует двух родителей; генотип или геном – структура данных особи, используемая в процессе размножения; хромосома – закодированное решение; ген - определенная позиция в хромосоме; аллель - частное значение гена; фенотип – раскодированное решение; поколение - один цикл оценивания, размножения и обновления популяции; либо популяция, создаваемая в каждом таком цикле.

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

Теоретические исследования стараются подкрепить экспериментами для решения конкретного типа задач с учетом их специфики. При этом вопросы о сравнении алгоритмов и настройке их параметров решаются путем компьютерного моделирования. Важную роль здесь играет создание общедоступных библиотек тестовых задач (бенчмарок), размещенных в сети Интернет, которые позволяют исследователю сравнивать свои результаты с работами других авторов. В качестве примеров можно привести библиотеку генетических алгоритмов GAlib ^[34], библиотеку для выполнения эволюционных вычислений в Perl ^[35], библиотеку для построения популяционных алгоритмов EAlib ^[36], библиотеку тестовых задач Института математики им. С.Л. Соболева ^[37], фреймворк для эволюционных вычислений в Java ^[38] и др. Надо сказать, что между результатами теоретических и экспериментальных исследований наблюдается определенный разрыв: построенные модели, как правило, описывают лишь простейшие алгоритмы для задач с несложной структурой поиска и с заранее известными оптимальными решениями. Напротив, успешные практические реализации когнитивных биоинспирированных алгоритмов пока не имеют достаточного теоретического обоснования. Такую ситуацию не следует считать недостатком этих алгоритмов, а только свидетельством сложности возникающих здесь вопросов, а также подтверждением важности экспериментальных исследований.

Одним из основных вопросов при анализе когнитивных биоинспирированных алгоритмов, по-видимому, можно считать вопрос о том, какой из алгоритмов предпочесть при решении некоторой задачи, и, наоборот, для каких типов задач определенный алгоритм будет показывать наилучшие результаты, и для каких задач его нецелесообразно применять? Например, существует ли некоторый лучший эвристический алгоритм, который дает всегда лучшие результаты при решении различных оптимизационных задач и можно ли выбрать такие параметры, чтобы алгоритм давал лучшие результаты независимо от решаемой задачи? К сожалению, ответ на эти вопросы отрицательный – такого лучшего алгоритма не существует!

Это следует из классического результата в теории когнитивных биоинспирированных алгоритмов - NFL-теоремы (No Free Lunch, бесплатных завтраков не бывает) ^[11], доказанной в 1996 г. и вызвавшей оживленную дискуссию. Пусть P(d_m^y| f, m, A) – условная вероятность получения частного решения d_m^y после m прогонов алгоритма A на функции f:X→Y(где xϵX множество входных значений, yϵY – множество выходных значений). Тогда для любых алгоритмов А₁ и А₂ согласно NFL-теореме после m прогонов справедливо:

Таким образом, сумма условных вероятностей посещения в пространстве решений каждой точки d_m^y одинакова для множества всевозможных целевых функций независимо от используемого алгоритма. Отсюда следует, что при любой мере производительности алгоритма в среднем для всевозможных целевых функций f вероятность Р не зависит от алгоритма А. Иначе, не существует лучшего алгоритма (биоинспирированного или любого другого эвристического алгоритма) для решения всех проблем. Если алгоритм А выигрывает по своим характеристикам при решении некоторого класса задач, то это неминуемо компенсируется проигрышем (худшими характеристиками) для остальных задач. Дискуссия среди специалистов по эволюционным вычислениям была вызвана тем, что ранее были предприняты значительные усилия по разработке и поиску лучших значений параметров эволюционных (в частности, генетических) алгоритмов и эволюционных операторов (кроссинговера, мутации и их многочисленных клонов). Эти разработки апробировалось на сложившихся в каждой проблемной области тестовых задачах. Но из NFL-теоремы следует, что полученные результаты справедливы только на использованных тестовых задачах, а не для произвольных задач. Оказалось, что усилия по поиску лучших операторов, оптимальных значений параметров алгоритмов при отсутствии ограничений для исследуемого класса задач не имеют смысла!

Чтобы когнитивный биоинспирированный алгоритм решал поставленную задачу лучше, чем случайный поиск (в NFL-теореме случайный поиск является просто другим алгоритмом), в нем необходимо отразить априорные знания об этой задаче. Однако для другой задачи с иной структурой знаний такой алгоритм может показать худшие результаты, т.е. структура проблемы должна быть определена и соответствовать разрабатываемому алгоритму. Редукция проблемной области без указания соответствия между рассматриваемым множеством проблем и алгоритмом недостаточна для получения преимущества данного алгоритма решения этих проблем по сравнению с другими. NFL-теорема просто подтверждает, что разные алгоритмы имеют различную эффективность при решении разных задач. Например, классические методы оптимизации, как правило, более эффективны при решении линейных, квадратичных, строго выпуклых, унимодальных, разделяемых и других специальных классов проблем. С другой стороны, когнитивные биоинспирированные алгоритмы часто успешно решают задачи там, где классические методы не работают: целевые функции не дифференцируемы, разрывны, мультимодальны, зашумлены, имеют сложный ландшафт, фазовое пространство переменных не является метрическим, что характерно для решения реальных практических задач.

Современные тренды в области когнитивных биоинспирированных алгоритмов состоят, в частности, в самоадаптации алгоритмов к решаемой задаче непосредственно в процессе оптимизации. Важное место занимает адаптация параметров алгоритмов. Однако единых и при этом действенных методик пока не разработано.

Сопоставительный анализ различных моделей когнитивных биоинспирированных алгоритмов, гипотез, лежащих в основе этих моделей, и формализованных способов их описания позволяет говорить о следующих закономерностях ^[29]:

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

Суть большинства когнитивных биоинспирированных алгоритмов сводится к следующему.

Фиксируется множество объектов X (популяция решений), обладающих некоторыми параметрами и связанных друг с другом посредством определенной структуры. Среди этих объектов необходимо выбрать наилучшие в смысле некоторого критерия качества (оптимальности) F. Критерий оптимальности формируется на основе свойств объектов и не обязательно существует в виде аналитических выражений. Важно, что существует отображение вида F: X → R, где R - множество действительных чисел и каждому объекту x из множества X сопоставляется значение критерия F(x).

Фенотипическая природа исследуемого множества объектов произвольна, поэтому необходимо построить кодированное представление исходного множества объектов в другом, конечном множестве, обладающем структурой, например, векторного пространства S (генотип).

Отображение вида φ: X → S описывает связь между исследуемыми объектами, которые выступают в качестве потенциальных решений задачи поиска и объектами, управление и манипулирование которыми осуществляет алгоритм.

Существует обратное отображение вида φ^-1: S → X, где каждому вновь сгенерированному элементу представления s соответствует элемент во множестве X. Тогда, например процесс оптимизации с помощью алгоритма, состоит в построении множества объектов-решений X_opt , для которых выполняются следующие условия:

Таким образом, в процессе оптимизации множество X развивается и эволюционирует к оптимальному состоянию, изменяя свой состав и параметры входящих в него объектов. Способ построения множества объектов S определяется когнитивным биоинспирированным алгоритмом.

Например, особенностью эволюционных алгоритмов является то, что в качестве множества S строится так называемое кодовое пространство - множество представлений объектов x в виде кодов (хромосом). Эволюция множества Х задается эволюцией представления S. На множестве S определяется подмножество Р₀ - случайная начальная популяция. Решение на каждом шаге эволюции определяется следующей разностной вычислительной схемой:

где Q - композиция различных эволюционных операторов. Критерий оптимальности вычисляется на каждом шаге в процессе отбора решений по критерию, реализуемому в композиции операторов. На рис. 2 в качестве примера представлены основные элементы эволюционных алгоритмов.

Рис. 2 – Основные элементы эволюционных алгоритмов

Оптимизируемая модель и эволюционный алгоритм разделены, а структура эволюционных вычислений и моделирования представляет собой систему с обратной связью, представленную на рис. 3.

Рис. 3 – Структура системы эволюционных вычислений

В данном случае математическая природа модели не имеет значения. Модель получает от алгоритма очередной набор значений параметров, характеризующих решения Х = (x₁, x₂,…, x_n) и выдает соответствующее значение функции качества F(X). Данное значение используется алгоритмом при отборе и формировании новых решений.

Процесс останавливается, когда текущий набор значений решений удовлетворяет заданному крит