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

Размещено на http://www.allbest.ru/

4

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

Родзин Сергей Иванович

кандидат технических наук

профессор, Южный федеральный университет

Курейчик Владимир Викторович

доктор технических наук

профессор, Южный федеральный университет



Аннотация

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

Ключевые слова: когнитивный биоинспирированный алгоритм, метаэвристика, оптимизация, эволюционные вычисления, эволюционный оператор, NFL-теорема, анализ дрейфа, функция приспособленности, моделирование, программирование

An overview concerns topical issues and the current situation regarding cognitive bioinspiral optimization algorithms research. Optimization problems form the majority among the many problems, which are faced by the researchers in the theoretical sphere as well as in the sphere of practical application. For some such problems the solution requires a full search for options. However, the dimensions of these problems are such that the implementation of the search for options is almost impossible due to the extremely high time costs. An alternative approach to solving these problems involves the application of methods based on the methodology of cognitive bioinspiral algorithms. When the computer systems became sufficiently fast and inexpensive, the bioengineered algorithms formed an important tool for finding solutions close to optimal solutions for the problems,which were previously been considered insoluble. The methodological and theoretical basis of the survey was found in the provisions of the theory of artificial intelligence and bioinspired computing, decision theory and optimization methods. The review includes a list of world scientific schools and scientists who have made a significant contribution to the development of cognitive bioinspiral algorithms, and also a brief description of the classification, terminology and libraries of bioengineered algorithms. A classical result is presented in the theory of cognitive bioinspiral algorithms - the CPT theorem and the NFL-theorem. The authors provide analysis of regularities, basic elements and structure of cognitive bioinspired calculations, they analyze the issues concerning representation (coding) of solutions, basic cycle of bioinspired algorithms, extension of cognitive capabilities of operators of bioinspiral algorithms, and drift analysis as a promicing direction in the sphere of time of cognitive bioinspiral algorithms analysis.

Keywords:

metaheuristics, fitness function, evolutionary computation, evolution operator, NFL-theorem, drift analysis, optimization, modeling, programming, cognitive bioinspired algorithm

алгоритм кодирование оптимальное решение



Введение

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

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

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



Научные школы

Наиболее значительный вклад в разработку когнитивных биоинспирированных методов внесли следующие ученые: Л. Растригин предложил методы случайного поиска ^[1], Nelde r и Mead представили эвристики, которые для некоторых задач сходятся в нестационарных точках ^[2], Fogel и др. разработали алгоритм эволюционного программирования ^[3], Kernighan и Lin создали метод поиска в глубину ^[4], Holland предложил генетический алгоритм ^[5], Smith разработал алгоритм генетического программирования ^[6], Kirkpatrick и др. предложили метод имитации отжига ^[7], Glove r разработал алгоритм табуированного поиска ^[8], Moscato представил меметический алгоритм ^[9], Dorigo предложил муравьиный алгоритм ^[10], Wolpert и Macready доказали NFL -теорему ^[11]. Фундаментальные результаты в области теории и методов принятия оптимальных решений получены А. Петровским ^[12], А. Еремеевым , В. Вагиным ^[13], В. Городецким ^[14], А. Смирновым ^[15]. Известно несколько современных книг и обзорных статей, опубликованных по этой теме ^[16-24]. Получены некоторые теоретические результаты, указывающие на возможность нахождения глобального оптимума биоинспирированными алгоритмами для отдельных задач ^[19]. Были опубликованы несколько десятков новых когнитивных биоинспирированных алгоритмов для эффективного решения трансвычислительных задач ^[25-30].

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

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

· тематика исследований, ведущихся в университете Остина (США) под руководством Р. Мииккулайнена , включает разработку когнитивных биоинспирированных алгоритмов кооперативной коэволюции в многоагентных системах;

· лаборатория интеллектуальных систем в Цюрихе под руководством Д. Флореано ведет разработки эволюционного аппаратного и программного обеспечения для программных робототехнических систем, исследует поведение коллективных и роевых систем;

· основное направление исследований лаборатории в Риме под руководством С. Нолфи - изучение адаптивных систем, взаимодействующих с внешней средой и управляемых гибридными принципами «мягких» вычислений;

· центр исследований вычислительного интеллекта и его приложений в университете Бирмингема под руководством З. Яо выполняет проекты по разработке и применению нейроэволюционных алгоритмов с использованием эволюционного программирования;

· группа исследователей оптимизации адаптивных систем в институте нейроинформатики в университете Бохума (Германия) под руководством К. Игеля изучает взаимодействие обучения и эволюции при создании адаптивных информационных систем;

· лаборатория эволюционных вычислений Департамента компьютерных наук в университете Дж. Мейсона в США под руководством К. де Йонга исследует гибридные биоинспирированные методы, работает над проектами и приложениями моделей эволюции, необходимыми для лучшего понимания эволюционных систем, для обеспечения робастности, гибкости и адаптивности информационных систем. Главное внимание специалисты лаборатории уделяют решению сложных научных и технических проблем, таких как инновационное проектирование, оптимизация и машинное обучение;

· в аналогичном направлении, но с акцентом на генетические алгоритмы, работает под руководством Д. Голдбергалаборатория генетических алгоритмов в Иллинойском университете;

· активным научным центром, известным своими работами по вопросам развития теории и разработки эволюционных алгоритмов оптимизации с приложениями к сложным оптимизационным проблемам транспортного типа, является лаборатория информатики и автоматизации академии наук и университета Артца (Франция). Руководителем научной школы является профессор Ж. Гонкальвес ;

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

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

Классификация, терминология, библиотеки когнитивных биоинспирированных вычислений

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

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



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

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

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

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

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

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

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

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

Недостатки бинарного кодирования заключаются в существовании хеммингова сдвига для пары закодированных значений, имеющих большое хеммингово расстояние, в то время как эти величины принадлежат к точкам с минимальным расстоянием в фенотипическом пространстве. Например, пара хромосом 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]. Теоретически обоснованное и эмпирически наблюдаемое явление «компрессии» таит в себе опасность преждевременной сходимости алгоритма генетического программирования к субоптимальным решениям.