Недостатки бинарного кодирования заключаются в существовании хеммингова сдвига для пары закодированных значений, имеющих большое хеммингово расстояние, в то время как эти величины принадлежат к точкам с минимальным расстоянием в фенотипическом пространстве. Например, пара хромосом 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 в разностной вычислительной схеме Pt+1 = Q (Pt) . Когнитивные возможности эволюционных операторов тесно связаны с такими понятиями как самоадаптация и самоорганизация природных систем.
Базовый цикл когнитивных биоинспирированных алгоритмов
Все когнитивные биоинспирированные алгоритмы используют практически одни и те же процедуры инициализации. Общие рекомендации по инициализации следующие. Создается популяция из n случайных особей. Если имеется информация о «хороших» начальных областях пространства поиска, то можно адаптировать случайное создание особей в сторону генерации особей из этих областей. В действительности, можно даже сгенерировать начальную популяцию, по крайней мере, частично, с использованием особей с заранее заданными параметрами. Хотя подобного рода подход следует использовать осторожно: всегда существует вероятность, что информация о «хороших» начальных областях пространства поиска является не достоверной. Лучше если инициализация использует существенную долю равномерной случайности.
Для усиления разнообразия начальной популяции также имеет смысл проверить, является ли каждая особь уникальной. Однако это не значит, что при создании каждой особи необходимо просматривать всю популяцию и производить сравнение со всеми уже созданными особями: эта операция будет иметь вычислительную сложность O(n2). Логично создать хеш-таблицы, в которых особи представляют собой ключи, а в качестве значения хранится что-нибудь другое. При создании особи нужно проверять содержится ли соответствующий ключ в хеш-таблице. Если да, то особь отбрасывается и генерируется новая. В противном случае особь добавляется в популяцию, а в хеш-таблицу заносится новый ключ.
Когнитивные биоинспирированные алгоритмы, как правило, создают новые наборы решений (популяции) на основании свойств предыдущих наборов решений. Хотя имеются исключения, например, алгоритм роящихся частиц [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, поэтому инвертирование отдельного бита не приводит к существенному изменению кодируемого значения переменной, от которой зависит решение. К тому же код Грэяпреобразуется в стандартный код, и наоборот.