Для некоторых практических приложений успешно применяется проблемно-ориентированное кодирование в форме векторов, матриц или древовидных структур данных. Длина кода при этом не обязательно является постоянной. Это дает некоторые преимущества, например, при решении таких задач, как проектирование и оптимизация архитектуры искусственных нейросетей [44].
Еще одной возможной формой представления решений являются диплоиды [45], содержащие два гомологичных набора хромосом. Ответ на вопрос о том, какая аллель будет выбрана при декодировании и оценке решения, зависит от ее доминантности или рецессивности. Такой подход к представлению решений дает определенные преимущества, если целевая функция является не стационарной.
Когнитивные возможности операторов ГА могут быть расширены.
Традиционно считалось, что вероятность мутации в ГА невысокая, а сам оператор имеет вспомогательное значение. Однако в [45] показано, что оптимальное значение вероятности мутации pm зависит от длины стринга L : pm ? 1/L . Однако теоретические исследования показали, что при проблемно-ориентированном кодировании оператор мутации отличается от мутации при двоичном кодировании [29].
В качестве альтернативной формы мутации предлагается формула, согласно которой компонента вектора uj после мутации определяется случайным образом:
uj' = uj + (в1j - 0,5)·2T , если в2j ? pco .
В противном случае, если в2j > pco , то uj' = uj . Здесь в1j , в2j - независимые величины, случайно распределенные на интервале [0, 1], T , pco - параметры, устанавливаемые пользователем.
Оператор инверсии был предложен в [5] для изменения последовательности генов, когда в хромосоме между двумя случайно выбранными точками происходит инвертирование аллелей, а значение целевой функции при этом не изменяется. Инверсия приводит к увеличению пространства поиска решений, за счет этого появляется возможность для подбора подходящей позиции и значения гена.
Несмотря на то, что существуют разные мнения относительно того, насколько конструктивным является влияние оператора кроссинговера, особенно вблизи точки оптимума, тем не менее, кроссинговер - это основной оператор репродукции и получения новых решений в ГА. Оператор кроссинговера характеризуется вероятностью его применения pk , а также величинами позиционного и дистрибутивного смещения. Существует множество разновидностей этого оператора: N -точечный, универсальный, смешанный кроссинговер и т.д.
В частности, при выполнении N -точечного кроссинговера происходит обмен родительских стрингов хромосом. Чем больше N , тем меньше позиционное смещение и тем больше дистрибутивное смещение. Число обмениваемых битов с ростом N приближается к биномиальному распределению с математическим ожиданием L /2. Согласно универсальному кроссинговеру для каждой позиции бита в стринге c заданной вероятностью puk происходит обмен родительских генов. При этом отсутствует позиционное смещение. Дистрибутивное смещение универсального кроссинговера, напротив, является очень высоким, т.е. число обмениваемых бит соответствует биномиальному распределению с математическим ожиданием puk·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 ) - порядок схемы, pc - вероятность уничтожения схемы под действием оператора кроссинговера, pm - вероятность уничтожения схемы под действием оператора мутации. Согласно (7) шаблоны, обладающие малой определяющей длиной, низким порядком и пригодностью, выше средней в популяции, будут увеличивать число строк, сходных с шаблоном, в последующих генерациях по экспоненциальному закону.
Теорема Холланда весьма упрощенно описывает поведение генетических алгоритмов, а её доказательство, построенное на элементах теории вероятности, не учитывает достаточно большой разброс значений функций пригодности шаблонов в некоторых практических задачах. Была установлена вычислительная ошибка, которая приводит к неверным результатам для задачи об игровых автоматах. К тому же, поскольку популяция в генетических алгоритмах имеет конечную величину, то возникает неизбежная ошибка при определении значения функции пригодности шаблона. Эта ошибка в оценке ставит под сомнение значение теоремы в плане ее практического применения, за исключением очень простых приложений, для которых теорема становится почти тавтологией, описывающей пропорциональный селективный отбор. Эффект ошибки при определении значения пригодности шаблона состоит в том, что в популяции реального размера, действительное значение функции пригодности может существенно отличаться от среднестатистического значения, даже для начальной популяции.
Другое критическое замечания относительно теоремы Холланда касается предположения о независимости экземпляров, выбираемых из различных шаблонов популяции. Нельзя считать независимыми экземпляры хромосом, если популяции на основе двух пересекающихся шаблонов имеют различную скорость сходимости. Этот факт имеет место даже для бесконечно больших популяций. Он состоит в том, что значение функции пригодности шаблона в популяции быстро начинает отклоняться от теоретического среднего значения, что никак нельзя объяснить на основании теоремы Холланда . Для любого метода оптимизации особый теоретический интерес представляет вопрос о сходимости к глобальному оптимуму и об условиях сходимости. Из теоремы Холланда не следует сходимость ГА к глобальному оптимуму. Исследования в области сходимости ГА сконцентрированы в основном на простейших ГА, а сходимость многочисленных модификаций ГА для решения практических оптимизационных задач является малоисследованной проблемой. Доказано, что простейший ГА не сходится к глобальному оптимуму за конечное время. Доказательство основано на фундаментальной теории цепей Маркова . Следует признать, что методология управления сходимостью даже для простейшего ГА до сих пор не выработана, хотя подтверждением эффективности алгоритма является доказательство его сходимости и оценка вычислительной сложности. Но, как правило, это возможно только в случае упрощенной постановки задачи. Другой альтернативой является проверка алгоритмов на тестовых задачах (benchmarks ) данной проблемной области. К сожалению, в настоящее время не существует согласованного каталога таких задач для оценки старых или новых алгоритмов решения, хотя для многих типовых задач, таких как задача коммивояжера, построения расписания, поиск минимального связывающего дерева, задача о рюкзаке они уже сложились и широко используются. Вероятно, для практики более важным является не вопрос сходимости, а другой вопрос: находит или нет биоинспирированный алгоритм близкое к оптимальному решение за возможно более короткое время? Ответ на этот вопрос также не выглядит однозначным, поскольку в теории пока не получено исчерпывающих объяснений успешных эмпирических результатов, связанных с практическим решением многих оптимизационных задач. Каковы критерии того, насколько подходящим является ГА для решения тех или иных задач? В [39] исследовались так называемые обманчивые проблемы (deceptive problems ), при решении которых интуитивно можно предположить, что алгоритм должен найти глобальный оптимум. Очевидно влияние эволюционных операторов на результаты работы биоинспирированного алгоритма. Обозначим эту взаимосвязь применяемого эволюционного оператора через коэффициент корреляции r eo . Этот коэффициент устанавливает взаимосвязь между значениями функций приспособленности родительских хромосом и хромосом-потомков. В [29] приводится несколько тестовых задач с известным значением глобального максимума, для которых определялись значения reo , после чего исследуемые задачи классифицировались на следующие группы:
· легко разрешимые (r eo ? - 0,15);
· трудно разрешимые (- 0,15 < r eo < 0,15);
· обманчивые (r eo ? 0,15)
Если значение глобального оптимума заранее неизвестно, то можно использовать вместо него лучшее из известных решений.
Дрейф-анализ
Перспективным направлением в анализе времени работы когнитивных биоинспирированных алгоритмов на сегодняшний день является анализ дрейфа (d rift ) [51].
Например, пусть задана следующая задача комбинаторной оптимизации. В конечном пространстве состояний S имеется некоторая функция f ( x ), x ?S . Найти
Пусть x * - состояние с максимальным значением функции fmax = f ( x * ). Абстрактный биоинспирированный алгоритм для решения поставленной оптимизационной задачи включает следующие шаги.
Шаг 1. Инициализация популяции (случайным образом или эвристически) x 0 = (x 1,…, x 2n ) из 2n особей (n - целое число). Присвоить k = 0. Для каждой популяции x k определить
x k = max {f(xi) : xi ? x k }.
Шаг 2. Генерация популяции x k +1/2 с помощью эволюционных операторов.
Шаг 3. Селекция и репродукция 2n особей из популяций x k +1/2 и x k и получение новой популяции x k + S .
Шаг 4. Если f ( x k + S ) = fmax ,, то 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 *.