Theoretical issues and modern problems concerning development of cognitive bioinspiral optimization algorithms (a survey).

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 Other publications by this author

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 Other publications by this author

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

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

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

Наиболее значительный вклад в разработку когнитивных биоинспирированных методов внесли следующие ученые: Л. Растригин предложил методы случайного поиска ^[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). Данное значение используется алгоритмом при отборе и формировании новых решений.

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

X_opt = (x_1opt, x_2opt,…, x_nopt).

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

Возникает вопрос: каковы общие правила их проектирования? Например, Голдберг в ^[39] определил два общих шаблона для проектирования генотипа в генетическом алгоритме:

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

К настоящему времени разработаны различные способы кодирования для обеспечения эффективного выполнения когнитивных биоинспирированных. Эти способы могут быть разделены на следующие классы:

• бинарное кодирование;
• кодирование действительными числами;
• целочисленное кодирование;
• кодирование общей структуры данных.

Недостатки бинарного кодирования заключаются в существовании хеммингова сдвига для пары закодированных значений, имеющих большое хеммингово расстояние, в то время как эти величины принадлежат к точкам с минимальным расстоянием в фенотипическом пространстве. Например, пара хромосом 01111111 и 10000000 принадлежит соседним точкам в фенотипическом пространстве (точки с минимальным евклидовым расстоянием), но имеют максимальное хеммингово расстояние в генотипическом пространстве. Для преодоления хеммингова сдвига все биты должны изменяться одновременно, но вероятность такого события очень мала. Поэтому для многих задач, встречающихся в современных проблемах, затруднительно представить их решение с помощью только бинарного кодирования.

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

Практика применения различных разновидностей эволюционных алгоритмов показывает, что целочисленное кодирование лучше всего подходит для комбинаторных оптимизационных задач ^[40].

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

Согласно представленной в ^[29] теории эволюционных вычислений, шаблоны Голдберга дополняются следующими правилами:

• представление генотипа должно быть сюръективным по отношению ко всем фенотипам, т.е. каждый элемент множества S является образом хотя бы одного элемента Х:

• для пары фенотипов мощность их генотипов должна быть примерно одинакова:

• небольшие изменения в генотипе должны приводить к небольшим изменениям в фенотипе:

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

Таким образом, отображение (φ^-1: S → X) из генотипического пространства в фенотипическое оказывает значительное влияние на поведение когнитивных биоинспирированных алгоритмов. Проблема здесь заключается в том, что некоторые хромосомы могут быть или недопустимым или незаконным решением задачи. Это представлено на рис. 4 в виде отображения пространств генотип-фенотип.

Рис. 4 – Отображение из генотипа в фенотип

Уточним эти термины, поскольку в некоторых литературных источниках они используются не вполне корректно.

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

Поэтому необходимо дать предварительную оценку способу кодирования. Одна из таких оценок известна – легальность кодирования ^[41]. Свойство легальности кодирования означает, что любая перестановка в хромосоме, вследствие применения большинства операторов эволюции, должна соответствовать законному решению. Другими свойствами являются недостаточность, полнота, причинность.

Свойство недостаточности вытекает из правил (4) – (6) и означает, что отображение между кодированием (генотипом) и решением (фенотипом) должно иметь вид 1–k–1. В общем случае такое отображение может относиться к одному из следующих типов:

• 1 – k – 1 («один к одному»);
• n – k – 1 («многие к одному»);
• 1 – k – n («один ко многим»),

Типы отображений пространств генотип/фенотип представлены на рис. 5.

Рис. 5 – Типы отображений пространств генотип/фенотип

Самый лучший способ – это отображение «один к одному».

Свойство полноты означает, что любое решение имеет соответствующее кодирование и любая точка в пространстве решений доступна для поиска.

Свойство причинности связывает малые вариации в хромосомах пространства генотипов, которые появляются вследствие мутации, с малыми вариациями в фенотипическом пространстве. Это свойство было предложено, в первую очередь, для эволюционных стратегий ^[42]. Оно определяет сохранение родственных (соседних) структур. В частности, для успешного введения новой информации посредством мутации ее оператор должен сохранять структуру соседства в фенотипическом пространстве.

Представленная на рис. 3 структура системы эволюционных вычислений, является адаптивной, так как в ней предусмотрена возможность системы модифицировать свое поведение для достижения лучших результатов за счет расширения когнитивных возможностей композиции различных эволюционных операторов Q в разностной вычислительной схеме P_t+1 = Q (P_t). Когнитивные возможности эволюционных операторов тесно связаны с такими понятиями как самоадаптация и самоорганизация природных систем.

Все когнитивные биоинспирированные алгоритмы используют практически одни и те же процедуры инициализации. Общие рекомендации по инициализации следующие. Создается популяция из n случайных особей. Если имеется информация о «хороших» начальных областях пространства поиска, то можно адаптировать случайное создание особей в сторону генерации особей из этих областей. В действительности, можно даже сгенерировать начальную популяцию, по крайней мере, частично, с использованием особей с заранее заданными параметрами. Хотя подобного рода подход следует использовать осторожно: всегда существует вероятность, что информация о «хороших» начальных областях пространства поиска является не достоверной. Лучше если инициализация использует существенную долю равномерной случайности.

Для усиления разнообразия начальной популяции также имеет смысл проверить, является ли каждая особь уникальной. Однако это не значит, что при создании каждой особи необходимо просматривать всю популяцию и производить сравнение со всеми уже созданными особями: эта операция будет иметь вычислительную сложность O(n²). Логично создать хеш-таблицы, в которых особи представляют собой ключи, а в качестве значения хранится что-нибудь другое. При создании особи нужно проверять содержится ли соответствующий ключ в хеш-таблице. Если да, то особь отбрасывается и генерируется новая. В противном случае особь добавляется в популяцию, а в хеш-таблицу заносится новый ключ.

Когнитивные биоинспирированные алгоритмы, как правило, создают новые наборы решений (популяции) на основании свойств предыдущих наборов решений. Хотя имеются исключения, например, алгоритм роящихся частиц ^[43]. Базовый цикл алгоритмов начинает свою работу с создания популяции, к которой итерационно применяются следующие процедуры. Вначале вычисляется целевая функция (приспособленность каждой особи в популяции). Затем полученная информация о приспособленностях используется для размножения – получения популяции потомков. На заключительном этапе базового цикла вычислений некоторым образом объединяются популяции родителей и потомков для формирования популяции нового поколения, после чего цикл начинается сначала.

Имеется отличие от однопопуляционных (траекторных) алгоритмов – до размножения необходимо иметь информацию о приспособленности всех особей. Популяционные алгоритмы отличаются друг от друга тем, как осуществляется селекция особей из популяции и их улучшение, какие эволюционные операторы при этом используются, а также тем полностью заменяются родители потомками, либо в следующее поколение включаются наиболее приспособленные родительские особи и потомки. Например, стратегия вымирания предполагает, что популяция на следующем шаге эволюции состоит только из потомков предыдущей популяции. Другая стратегия предполагает, что продолжительность жизни отдельных особей в популяции может превышать одно поколение, следовательно, родители и их потомки конкурируют друг с другом за выживание. Например, в эволюционных стратегиях ^[42] для описания перехода от одного поколения к другому используются следующие обозначения: l - число потомков, m - число родителей. Тогда запись вида (m, l) при l >= m означает, что из созданных l потомков от m родителей (l- m) худших потомков будут исключены из следующего поколения. Стратегия (l + m) при l > m будет обозначать, что в следующее поколение будут отобраны по определенной стратегии m особей из родителей и их потомков.

Алгоритм организации вычислений в базовом цикле на псевдокоде имеет следующий вид:

Input: Функция для оценки качества решений F

Input: n – размер популяции решений

Data: t – текущий номер поколения

Data: P( t= 0) – исходная популяция решений

Data: параметры алгоритма, включая целевую функцию

Output: X* – найденное оптимизированное решение

begin

t: = 0

Pop: = init Pop(n) /*функция init выполняет первоначальную случайную инициализацию популяции */

while (критерий останова) do

v: = F (Pop, F)

P(t): = selection (Pop, v)

t:= t + 1

Pop: = P(t) /*репродукция потомков из отобранных родительских решений с использованием композиции операторов эволюции Q: P(t+1) = Q(P(t))*/

return /*восстановление фенотипа Pop*/

end

Если используется стратегия элитизма, то в следующем поколении обеспечивается сохранение, по крайней мере, одного лучшего решения из текущего поколения. Следствием этой стратегии является то, что если найден глобальный оптимум, то алгоритм гарантирует сходимость процесса, хотя возрастает риск попадания в «локальную яму».

Алгоритм организации элитизма в процессе эволюционных вычислений, представленный на псевдокоде, имеет следующий вид:

Input: n – размер популяции решений

Input: as – размер архива элитных решений

Data: t – текущий номер поколения

Data: P(t= 0) – исходная популяция решений

Data: Arc – архив элитных решений

Data: параметры алгоритма, включая целевую функцию

Output: X* - найденное оптимизированное решение

begin

t: = 0

Arc: = О

Pop: = init Pop(n)

while (критерий останова) do

Arc: = updateOptimalSetN(Arc, Pop) /*обновленное оптимальное множество*/

Arc: = pruneOptimalSet(Arc, as) (сокращение оптимального множества решений до размера n)

v : = функция качества (Pop, Arc, F)

Р(t): = selection (Pop, Arc, v, n)

t: = t + 1

Pop : = репродукция P(t)

return/*восстановление фенотипа оптимального множества решений

(Pop + Arc)*/

end

Как видно, имеются определенные различия в представленных выше на псевдокоде алгоритмах, реализующих базовый цикл и стратегию элитизма. Во-первых, создается архив Arc элитных решений, который первоначально является пустым множеством, а затем обновляется функцией «updateOptimalSetN», которая сохраняет и обновляет полученные элитные решения. Во-вторых, если множество элитных решений становится слишком большим, то функция «pruneOptimalSet» сокращает его до величины n. В алгоритмах, построенных по принципам, отличным от элитизма, такой архив можно сделать пустым множеством (Arc: = О).

Рассмотрим пути и способы расширения когнитивных возможностей операторных конструкций различных биоинспирированных алгоритмов.

Для генетических алгоритмов (ГА) расширение их когнитивных возможностей связано, прежде всего, с представлением пространства поиска решений и целевой функцией, а также с применением разнообразных генетических операторов и механизмов селективного отбора.

Традиционной для ГА формой представления пространства поиска решений является двоичное кодирование с применением кода Грэя. Причина состоит в следующей особенности кода Грэя: расстояние по Хеммингу между соседними целыми числами для этого кода всегда равно 1, поэтому инвертирование отдельного бита не приводит к существенному изменению кодируемого значения переменной, от которой зависит решение. К тому же код Грэя преобразуется в стандартный код, и наоборот.

Для некоторых практических приложений успешно применяется проблемно-ориентированное кодирование в форме векторов, матриц или древовидных структур данных. Длина кода при этом не обязательно является постоянной. Это дает некоторые преимущества, например, при решении таких задач, как проектирование и оптимизация архитектуры искусственных нейросетей ^[44].

Еще одной возможной формой представления решений являются диплоиды ^[45], содержащие два гомологичных набора хромосом. Ответ на вопрос о том, какая аллель будет выбрана при декодировании и оценке решения, зависит от ее доминантности или рецессивности. Такой подход к представлению решений дает определенные преимущества, если целевая функция является не стационарной.

Когнитивные возможности операторов ГА могут быть расширены.

Традиционно считалось, что вероятность мутации в ГА невысокая, а сам оператор имеет вспомогательное значение. Однако в ^[45] показано, что оптимальное значение вероятности мутации p_m зависит от длины стринга L: p_m ≈ 1/L. Однако теоретические исследования показали, что при проблемно-ориентированном кодировании оператор мутации отличается от мутации при двоичном кодировании ^[29].

В качестве альтернативной формы мутации предлагается формула, согласно которой компонента вектора u_j после мутации определяется случайным образом:

u_j' = u_j + (β_1j – 0,5)·2T, если β_2j ≤ p_co.

В противном случае, если β_2j > p_co, то u_j' = u_j. Здесь β_1j, β_2j – независимые величины, случайно распределенные на интервале ^{[0, 1]}, T, p_co – параметры, устанавливаемые пользователем.

Оператор инверсии был предложен в ^[5] для изменения последовательности генов, когда в хромосоме между двумя случайно выбранными точками происходит инвертирование аллелей, а значение целевой функции при этом не изменяется. Инверсия приводит к увеличению пространства поиска решений, за счет этого появляется возможность для подбора подходящей позиции и значения гена.

Несмотря на то, что существуют разные мнения относительно того, насколько конструктивным является влияние оператора кроссинговера, особенно вблизи точки оптимума, тем не менее, кроссинговер – это основной оператор репродукции и получения новых решений в ГА. Оператор кроссинговера характеризуется вероятностью его применения p_k, а также величинами позиционного и дистрибутивного смещения. Существует множество разновидностей этого оператора: N-точечный, универсальный, смешанный кроссинговер и т.д.

В частности, при выполнении N-точечного кроссинговера происходит обмен родительских стрингов хромосом. Чем больше N, тем меньше позиционное смещение и тем больше дистрибутивное смещение. Число обмениваемых битов с ростом N приближается к биномиальному распределению с математическим ожиданием L/2. Согласно универсальному кроссинговеру для каждой позиции бита в стринге c заданной вероятностью p_uk происходит обмен родительских генов. При этом отсутствует позиционное смещение. Дистрибутивное смещение универсального кроссинговера, напротив, является очень высоким, т.е. число обмениваемых бит соответствует биномиальному распределению с математическим ожиданием p_uk·L. Другим вариантом оператора, расширяющим его когнитивные возможности, является смешанный кроссинговер, который можно использовать в сочетании с одноточечным или N-точечным кроссинговером. Какой кроссинговер является более предпочтительным, удовлетворительного ответа не имеет. При небольших популяциях (до 50 особей) предпочтительнее универсальный кроссинговер и не рекомендуется применять одноточечный кроссинговер, в основном из-за высокого позиционного смещения, а предлагается использовать диагональный кроссинговер, который является обобщением N-точечного кроссинговера. Еще одним источником для расширения когнитивных возможностей и вариабельности оператора кроссинговера является форма представления хромосом в виде вектора вещественных чисел. В этом случае рекомендуется применять такие разновидности кроссинговера как универсальный циклический кроссинговер, реберная рекомбинация, упорядоченный кроссинговер и др. ^[44].

Перспективным направлением расширения когнитивных возможностей операторов ГА является использование фрактальных множеств, алгоритмов одномерного дихотомического поиска, Фибоначчи, золотого сечения и других поисковых процедур ^{[40, 46–48]}. Например, оператор мутации, используя числа Фибоначчи, строится по следующей схеме: в хромосоме определяем точку разрыва, которая соответствует третьему числу ряда Фибоначчи, далее выбираются точки мутации, соответствующие следующим числам ряда, до достижения заданного номера.

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

Генетическое программирование (ГП) направлено на решение задач автоматического синтеза программ путем индуктивного вывода на основе входных обучающих данных ^[49]. В традиционных моделях вычислений (ввод-обработка-вывод) исходная информация на входе обрабатывается заданной программой вычислений для получения заранее неизвестного результата ^[50]. Иначе обстоит дело в ГП: здесь целью является поиск неизвестной программы по известным входным данным и выходным образцам. Эффективность применения алгоритмов ГП также определяется адаптивной настройкой их параметров. В частности, в ГП существует эффект «компрессионного давления», когда программы, генерируемые алгоритмом ГП, зачастую содержат «лишние» блоки, не влияющие на функциональные возможности программы и на значение её функции пригодности ^[29]. Теоретически обоснованное и эмпирически наблюдаемое явление «компрессии» таит в себе опасность преждевременной сходимости алгоритма генетического программирования к субоптимальным решениям.

Согласно основной теореме теории генетических алгоритмов ^[5], доказанной Дж. Холландом и дающей обоснование эффективности ГА, нижняя оценка количества примеров схем после очередной смены поколений определяется следующим неравенством:

где N(h, t) – количество примеров схемы hна шаге t, N(h, t + 1) – то же на следующем шаге, f(h, t) – функция приспособленности схемы на шаге t, f(t) – среднее значение функции приспособленности во всей популяции на том же шаге t, L – число позиций в хромосоме, d(h) – определяющая длина схемы, o(h) – порядок схемы, p_c – вероятность уничтожения схемы под действием оператора кроссинговера, p_m – вероятность уничтожения схемы под действием оператора мутации. Согласно (7) шаблоны, обладающие малой определяющей длиной, низким порядком и пригодностью, выше средней в популяции, будут увеличивать число строк, сходных с шаблоном, в последующих генерациях по экспоненциальному закону.

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

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

Для любого метода оптимизации особый теоретический интерес представляет вопрос о сходимости к глобальному оптимуму и об условиях сходимости. Из теоремы Холланда не следует сходимость ГА к глобальному оптимуму. Исследования в области сходимости ГА сконцентрированы в основном на простейших ГА, а сходимость многочисленных модификаций ГА для решения практических оптимизационных задач является малоисследованной проблемой. Доказано, что простейший ГА не сходится к глобальному оптимуму за конечное время. Доказательство основано на фундаментальной теории цепей Маркова. Следует признать, что методология управления сходимостью даже для простейшего ГА до сих пор не выработана, хотя подтверждением эффективности алгоритма является доказательство его сходимости и оценка вычислительной сложности. Но, как правило, это возможно только в случае упрощенной постановки задачи. Другой альтернативой является проверка алгоритмов на тестовых задачах (benchmarks) данной проблемной области. К сожалению, в настоящее время не существует согласованного каталога таких задач для оценки старых или новых алгоритмов решения, хотя для многих типовых задач, таких как задача коммивояжера, построения расписания, поиск минимального связывающего дерева, задача о рюкзаке они уже сложились и широко используются.

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

Каковы критерии того, насколько подходящим является ГА для решения тех или иных задач? В ^[39] исследовались так называемые обманчивые проблемы (deceptive problems), при решении которых интуитивно можно предположить, что алгоритм должен найти глобальный оптимум. Очевидно влияние эволюционных операторов на результаты работы биоинспирированного алгоритма. Обозначим эту взаимосвязь применяемого эволюционного оператора через коэффициент корреляции r_eo. Этот коэффициент устанавливает взаимосвязь между значениями функций приспособленности родительских хромосом и хромосом-потомков.

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

• легко разрешимые (r_eo≤ - 0,15);
• трудно разрешимые (- 0,15 < r_eo< 0,15);
• обманчивые (r_eo≥ 0,15)

Если значение глобального оптимума заранее неизвестно, то можно использовать вместо него лучшее из известных решений.

Перспективным направлением в анализе времени работы когнитивных биоинспирированных алгоритмов на сегодняшний день является анализ дрейфа (drift) ^[51].

Например, пусть задана следующая задача комбинаторной оптимизации. В конечном пространстве состояний S имеется некоторая функция f(x), xϵS. Найти

Пусть x^* - состояние с максимальным значением функции f_max = f(x^*). Абстрактный биоинспирированный алгоритм для решения поставленной оптимизационной задачи включает следующие шаги.

Ш а г 1. Инициализация популяции (случайным образом или эвристически) x₀ = (x₁,…, x_2n) из 2n особей (n - целое число). Присвоить k = 0. Для каждой популяции x_k определить

x_k = max {f(x_i): x_i ϵ x_k }.

Ш а г 2. Генерация популяции x_k+1/2 с помощью эволюционных операторов.

Ш а г 3. Селекция и репродукция 2n особей из популяций x_k+1/2 и x_k и получение новой популяции x_k+S.

Ш а г 4. Если f(x_k+S) = f_max,, то stop, иначе x_k+1 =x_k+S , k = k + 1 и переход к шагу 2.

Приведенная выше структура алгоритма ближе к эволюционной стратегии ^[42] и эволюционному программированию ^[29], чем к генетическим алгоритмам, в том смысле, что селекция применяется после выполнения эволюционных операторов. Однако для анализа дрейфа эти детали не имеют значения.

Пусть х^* - точка оптимума. Обозначим d (x, x^*) расстояние между точкой х и х^*. Если имеется множество оптимумов S^*, то d (x, S^*) = min{d (x, x^*): x^* ϵ S^*)} является расстоянием между точкой x и множеством S^*. Это расстояние будем просто обозначать через d(x). Тогда d(х^*) = 0, d(х) > 0 для любого х не принадлежащего S^*.

Учитывая, что популяции X = min{x₁,…, x_2n}, положим

Формула (9) служит для измерения расстояния между популяцией и оптимальным решением.

Последовательность {d(x_k); k = 0, 1, 2,…}, порожденная биоинспирированным алгоритмом, является случайной последовательностью, которая моделируется однородной цепью Маркова.

Тогда дрейф случайной последовательности в момент времени k определяется как

Время останова алгоритма оценивается как t = min {k : d(x_k) = 0}. Задача состоит в изучении взаимосвязи между временем t и размерностью задачи n. При каких значениях дрейфа D(d(x_k)) можно оценить математическое ожидание E[t]? Найдет ли в среднем алгоритм оптимальное решение за полиномиальное время или ему потребуется экспоненциальное время.

Идея анализа дрейфа довольно проста. Ключевым вопросом здесь является оценка соотношения d и D.

Биоинспирированный алгоритм может решить оптимизационную задачу за полиномиальное среднее время при следующих условиях дрейфа:

• если существует полином h₀(n) > 0 (n - размерность задачи) такой, что d(X) <= h₀(n) для любой данной популяции X, т.е. расстояние от любой популяции до оптимального решения является полиномиальной функцией от размерности задачи;
• в любой момент k >= 0, если d(x_k) > 0, то существует полином h₁(n) > 0 такой, что

т.е. дрейф случайной последовательности {d(x_k); k = 0, 1, 2,…} по отношению к оптимальному решению всегда положителен и ограничен обратным полиномом.

В ^[51] доказано следующее:

• если данные условия соблюдаются для случайной последовательности {d(x_k); k = 0, 1, 2,…}, то уже с начальной популяции X с d(X) > 0 выполняется неравенство

где h(n) - полиномом размерности задачи n;

• если имеется множество задач и биоинспирированный алгоритм для их решения, то для любой начальной популяции X с d(X) > 0, справедливо

• если целевая функция является линейной с положительными коэффициентами

(c₁ > c₂ >…> с_n > 0), то для получения оптимального решения биоинспирированному алгоритму с вероятностью мутации p_m = 1/n потребуется в среднем O(n ln(n)) шагов;

• если целевая функция f: S→R является псевдо модульной для любых x, y ϵ S (например, f(x) = Summa_i=1ⁿ П_j=1i s_j), то при вероятности мутации p_m = 1/n ожидаемое время останова алгоритма удовлетворяет неравенству E[t] <= n²(exp – 1);

Если биоинспирированный алгоритм не в состоянии найти оптимальное решение за полиномиальное время, то тогда есть смысл искать приближенное решение, определив момент останова алгоритма t как t = min{k : d(x_k) <= d_b}, где d_b >= 0. Это выполняется при следующих условиях дрейфа ^[51]:

• для любой популяции X с d_b < d(X) < d_a , где d_b >= 0, d_a > 0 справедливо

Это условие означает, что интервал (d_b , d_a) < d_a) является очень сложным для поиска, если, d(x_k+1) > d(x_k). Другими словами, потомки в популяции в среднем не становятся ближе к оптимальному решению, а, возможно, отдаляются от него;

• для любой популяции X с d(X) > d_a , где d_a > 0, справедливо

Условие (15) означает, что популяция на интервале [d_a, + ∞) не будет в среднем дрейфовать к оптимальному решению, потому что d(x_k) >= (d_a - ln(D)).

В [51] доказано, что при выполнении условий (14), (15), если d(x₀) > d_a , D >= 1, r < 1, то существуют некоторые δ₁ > 0 и δ₂ > 0 такие, что справедливо неравенство

Иными словами, биоинспирированный алгоритм при некоторых условиях может потребовать в среднем экспоненциального времени для поиска оптимального решения.

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

Отметим, что эти результаты были получены в предположении, что число поколений (что эквивалентно числу вычислений функции приспособленности) является наиболее важным фактором при оценке времени вычислений алгоритма. Это, пожалуй, справедливо для большинства приложений биоинспирированных алгоритмов, поскольку в них оценка приспособленности является наиболее трудоёмкой частью алгоритма, в отличие от операций кроссинговера и мутации, трудоемкость которых оценивалась как O(n), и операции селекции, трудоемкость которой оценивалась как O(n ln(n)).

В этом плане заслуживает внимания работа ^[52], в которой использовалась теорема «аддитивного дрейфа». Было предложено множество вариантов теорем такого вида, включая верхние и нижние оценки в случае мультипликативного и переменного дрейфа ^[53]. Значительный прогресс наблюдается в области порождения функций расстояния, которые используются для адаптации процесса оптимизации к входным условиям дрейф-теорем. Теоретический аппарат дрейф-теорем, существующий в настоящее время, позволяет анализировать биоинспирированные алгоритмы на тестовых задачах и задачах комбинаторной оптимизации.

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

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

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

Когнитивные биоинспирированные алгоритмы – один из наиболее перспективных способов решения задач оптимизации, когда точные методы решения задачи неизвестны или слишком трудоемки, при этом требуется найти не доказуемо точное решение, а «достаточно хорошее» решение, или решение, удовлетворяющее каким-либо критериям качества.

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

Когнитивные биоинспирированные алгоритмы в настоящее время активно используются в различных областях: в дизайне космических кораблей и зубных щеток, при разработке антенн для микро спутников, усилителей, фильтров, контроллеров, осцилляторов и других электронных схем ^[54], двигателей самолетов и новых антибиотиков, для конструирования роботов и спам-фильтров, когнитивных музыкальных ди-джеев и др. Среди фирм, использующих когнитивные биоинспирированные технологии, присутствуют такие известные организации и компании, как NASA, General Motors, Boeing, Honda, Yamaha, Gillette, General Electric, Genetic Programming, Cloudmark, Yandex, Hewlett-Packard, Proctor&Gamble, Coca Cola и др.

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

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

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