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

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

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

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

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

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

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

NFL-теорема

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

Это следует из классического результата в теории когнитивных биоинспирированных алгоритмов - 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] определил два общих шаблона для проектирования генотипа в генетическом алгоритме:

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

· алфавит и кодирование длин различных генов должны быть, по-возможности, минимальными.

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

· бинарное кодирование;

· кодирование действительными числами;

· целочисленное кодирование;

· кодирование общей структуры данных.