4.1. Структуризация ГА
Для нетривиальных задач выполнение одного репродуктивного цикла – поколения в ГА требует значительных вычислительных ресурсов. При решении многих задач используется не двоичное представление особи – решения проблемы, а более сложные структуры – массивы (матрицы) действительных чисел, связные списки, деревья, графы [[1] и т.д. Поэтому вычисление значения фитнесс-функции для каждой особи, потенциального решения проблемы, часто является самой трудоемкой операцией в ГА. Для повышения эффективности разрабатываются новые методы кодирования особей, генетические операторы кроссинговера и мутации, гибридные алгоритмы, параллельные алгоритмы и т.п.[][2,][3,][4].]
Первые работы в этом направлении появились в 60-х годах, но только в 80-е годы, когда были разработаны доступные средства параллельной реализации, исследования ПГА приняли систематический массовый характер и практическую направленность. В этом направлении разработано множество моделей и реализаций, некоторые из которых представлены ниже.
Прежде всего, необходимо отметить, что в основе ПГА лежит структуризация популяции (множества потенциальных решений) – его разбиения на несколько подмножеств (подпопуляций). Это разбиение можно сделать различными способами, которые и определяют различные виды ПГА. Согласно современной классификации различают глобальные ПГА, распределенные ГА (РГА), клеточные ГА (КГА) и коэволюционные ГА (КЭГА). В простом ГА, графически представленном на [рис. 4.1а), используется одна популяция особей, каждая из которых может взаимодействовать с любой другой особью. На ][рис. 4.1а) каждая особь представлена точкой. Глобальный ПГА реализуется фактически по схеме "клиент - сервер" (][рис. 4.1б)), где на сервере, в основном, выполняется генетический алгоритм, а клиенты выполняют "черновую работу" - оценку значений фитнесс-функции всех особей популяции, которая требует больших вычислительных ресурсов. В РГА популяция разбивается на множество подпопуляций, каждая из которых эволюционирует независимо (согласно ПГА) и обменивается через некоторое "время изоляции" с соседними подпопуляциями по определенной схеме, что графически представлено на ][рис. 4.1в. В КГА имеется множество подпопуляций, каждая из которых состоит только из одной особи. В один момент времени данная особь может взаимодействовать только с соседними особями. Отношение соседства задается в виде некоторой регулярной структуры – сетки, что графически представлено на ][рис. 4.1г.]
(рис 4.1) а) Простой ГА, б) Распределенный ГА, в) Модель островов, г) Клеточный ГА.
При заданной структуризации ГА реализуется собственно распараллеливание ГА. При этом ожидаются следующие преимущества:
поиск альтернативных решений одной и той же проблемы;
параллельный поиск из различных точек в пространстве решений;
допускают хорошую реализацию в виде островов или клеточной структуры;
большая эффективность поиска даже в случае реализации не на параллельных вычислительных структурах;
хорошая совместимость с другими эволюционными и классическими процедурами поиска;
существенное повышение быстродействия на многопроцессорных системах.
Рассмотрим основные современные методы распараллеливания ГА.
4.2. Параллельный генетический алгоритм на основе модели "рабочий-хозяин"
В данном разделе для распараллеливания ГА используется модель "с" (иногда она называется "клиент-сервер"), поскольку она требует наименьших изменений в существующей версии программного обеспечения, реализующего последовательный ГА и дает неплохие результаты. Ниже представлен укрупненный алгоритм параллельного ГА на основе модели "рабочий - хозяин".
Параллельный ГА "Рабочий - хозяин"
{
Генерация популяции P хромосом случайным образом;
выполнение параллельно для всех особей
{
Оценка значения фитнесс-функции для каждой особи;
}
While(критерий останова не выполнен)
{
отбор лучших особей;
выполнение генетических операторов кроссиговера и мутации;
формирование промежуточной популяции;
выполнение параллельно для всех особей
{
Оценка значения фитнесс-функции для каждой особи;
}
внесение лучших новых особей;
удаление худших старых особей;
формирование новой популяции ;
}
}
При этом затраты по вычислению значений фитнесс-функций равномерно распределяются по всем процессорам, для которых используется одна и та же фитнесс-функция. Поэтому для $$n$$ особей и $$P$$(одинаковых) процессоров мы каждому процессору относим $$n/P$$ особей. Значения фитнесс-функции вычисляются соответствующими (рабочими) процессорами и посылаются в один процессор (хозяин), который собирает всю информацию, обрабатывает и передает ее снова рабочим процессорам. Процессор "хозяин" имеет информацию о значениях фитнесс-функции для всех особей и может генерировать следующее поколение на этой основе.
Итак, процессор–хозяин выполняет центральную часть (ядро) алгоритма, в то время как "черновая работа" - вычисление значений фитнесс-функции для всех особей реализуется на процессорах–рабочих. Для баланса множество обрабатываемых особей популяции разбивается на примерно одинаковые подмножества.
В конце каждого из этапов помещаются точки синхронизации. Когда процессор-хозяин достигает эти точки, он переходит в режим ожидания, пока все рабочие процессоры не закончат свои задания, что гарантирует глобальную корректность алгоритма. При этом работа между процессором-хозяином и рабочими распределяется следующим образом.
Процессор-хозяин:
выполняет все вход-выходные операции с пользователем и файловой системой, читает задание и записывает результаты;
первоначально запускает "рабочие" процессы на доступных ресурсах;
распределяет задания каждому рабочему процессору;
организует управление процессом поиска решения и по мере необходимости посылает соответствующие сообщения активации рабочих процессоров; по окончании задания рабочим процессором процессор-хозяин принимает полученные результаты и соответственно изменяет глобальные структуры данных (общий список заданий, значения фитнесс-функции для особей и т.п.).
Каждый "рабочий" принимает задание от "хозяина" и определяет значение фитнесс-функции для особей, полученный результат посылает хозяину и ожидает следующего задания. Поскольку размер популяции много больше числа процессоров, достигается хороший баланс в загрузке процессоров. Диаграмма потоков данных в данном алгоритме приведена на [рис.4.2 (на примере распределенного логического моделирования).]
При использовании модели "рабочий - хозяин" окончательные результаты (поиска решения данной задачи) близки к тем, что получены на однопроцессорной компьютерной системе с использованием аналогичного алгоритма. Качество решения при этом не теряется и в большинстве случаев несколько улучшается, а время его поиска существенно сокращается. В целом данная модель позволяет быстро (с минимальными модификацями) выполнить параллелизацию ГА и дает, прежде всего, ускорение процесса поиска решения. Данную модель не сложно реализовать в локальной сети с использованием технологии сокетов.
Типичный график увеличения быстродействия (для задачи построения проверяющих тестов) представлен на [рис.4.3. [][5]. Здесь вверху для сравнения представлен "идеальный" линейный график роста ускорения в зависимости от увеличения числа процессоров. Реальное ускорение (особенно для большого числа процессоров) естественно несколько меньше.]
(рис 4.2) Потоки данных в модели "рабочий-хозяин"("клиент-сервер")
Следует отметить, что для задач большей размерности выигрыш в увеличении быстродействия обычно больше, так как "накладные расходы" на пересылки по сравнению с основными затратами на поиск решения составляют меньшую долю. На [рис.4.4 для примера представлен график увеличения быстродействия с ростом размерности задачи (сложности обрабатываемой схемы) [][5].]
(рис 4.3) Рост быстродействия при увеличении числа процессоров-клиентов
(рис 4.4) Увеличение быстродействия с ростом размерности задачи (сложности схемы)
Эксперименты показывают, что при грамотной реализации этой модели даже в локальной сети можно выиграть порядок в увеличении быстродействия (при относительно небольших модификациях исходного программного обеспечения).
4.3. Параллельные генетические алгоритмы на основе "модели островов"
Распределенные ГА используют, в основном, так называемую "модель островов", где каждая подпопуляция развивается на своем "острове". Между островами производится (достаточно редко) обмен лучшими особями. Эта модель может быть реализована в распределенной памяти компьютерной системы, имеющей MIMD-архитектуру согласно классификации Flynn. Преимущество РГА в том, что они работают быстрее даже на однопроцессорных компьютерных системах вследствие лучшей структуризации. Причина заключается в том, что число вычислений сокращается благодаря распределению поиска в различных областях пространства решений. Разработаны различные виды РГА, но практически все они являются вариациями базового алгоритма, который представлен следующим псевдокодом.
Основными факторами, которые влияют на миграцию в модели островов (и следовательно, на их эффективность), являются следующие.
Топология, определяющая отношение соседства между подпопуляциями. Здесь обмен особями происходит только между соседними подпопуляциями. Существует также несколько стандартных схем обмена особями между подпопуляциями, которые представлены ниже на [рис.4.5.]
Для каждой подпопуляции формируется "пул" - множество потенциальных эмигрантов из других подпопуляций. Далее из этого "пула" по определенному закону выбираются эмигранты для данной подпопуляции.
Степень миграции, которая определяет количество мигрирующих особей.
Время изоляции, определяющее число поколений между сеансами миграции.
Стратегия отбора особей в пул обмена. Здесь наиболее распространенными являются два подхода. При первом подходе из подпопуляции особи выбираются случайным образом – при этом сохраняется разнообразие генетического материала. При втором подходе из каждой подпопуляции выбираются лучшие в некотором смысле особи, что делает процесс более направленным. При этом также существуют различные методы отбора лучших хромосом (раздел 3.2).
Стратегия замены особей на мигрировавшие хромосомы из соседних подпопуляций. Здесь также существуют различные подходы: из подпопуляции удаляются худшие, случайные особи и т.п.
Стратегия репликации мигрирующих особей. При первом подходе мигрирующая особь остается также и в "родной" подпопуляции. Второй подход требует удаления мигрирующей особи из "родной" подпопуляции. Первая стратегия может привести к доминированию в различных подпопуляциях одних и тех же сильных особей. При второй стратегии особь может через некоторое время вернуться назад в исходную подпопуляцию, что ведет к лишним затратам вычислительных ресурсов.
Распределенные ГА можно классифицировать по следующим признакам.
По методу миграции принято разделять:
изолированные РГА (isolated DGA), где нет миграции между подпопуляциями (иногда называются разделенные РГА – partitioned DGA);
синхронные РГА (synchronous DGA), в которых миграции между подпопуляциями синхронизированы – выполняются в одно и тоже время;
асинхронные РГА (asynchronous DGA), где миграции могут происходить по событию в разные моменты времени в различных подпопуляциях, в зависимости от активности в каждой подпопуляции (асинхронное поведение характерно для естественной эволюции, которая развивается по-разному в зависимости от внешней среды).
По изменению схемы обмена особями различаются:
статическая схема соединений между подпопуляциями, которая не изменяется в процессе эволюции;
динамическая схема соединений, в которой вид обмена особями между подпопуляциями может изменяться в процессе эволюции.
По однородности подпопуляций принято разделять на:
однородные РГА (homogeneous DGA), где кажлая подпопуляция использует одни и те же способы кодирования хромосомы, генетические операторы, вид фитнесс-функций и т.п.;
неоднородные РГА (heterogeneous DGA), в которых каждая подпопуляция может иметь различные параметры управления, метод кодирования хромосомы, генетические операторы и т.п.
(рис 4.5) Типовые схемы обмена особями в модели островов
Неоднородные РГА по мнению некоторых авторов являются хорошим инструментом для предотвращения преждевременной сходимости к локальным экстремумам и позволяют эффективно решать проблему расширения (исследования) и эксплуатации зоны поиска решений. В этой области разработаны некоторые интересные модификации РГА, которые представлены ниже.
Адаптация конкурирующих подпопуляций. Здесь для каждого возможного вида генетических операторов формируется подпопуляция. Общее число особей фиксировано (во всех подпопуляциях), в то время как мощность каждой подпопуляции может варьироваться. Каждая подпопуляция соревнуется с конкурентами таким образом, что она приобретает или теряет особи в зависимости от ее качества относительно других подпопуляций. Например, разные подпопуляции могут иметь различный шаг мутации (над вещественным представлением) или отличающиеся арифметические операторы рекомбинации. С другой стороны каждая подпопуляция может иметь различные схемы обмена, степень миграции и т.п. Через определенное число поколений происходит ранжирование различных стратегий и параметры каждой адаптируются к значениям лучшей подпопуляции.
РГА, основанные на миграции и искусственной селекции (GAMAS). Эта модификации использует четыре подпопуляции – "породы" I – IV. Сначала создаются "породы" I – IV. Порода I является основной и накапливает найденные лучшие решения. Порода II предназначена для исследования (новых) областей поиска (exploration). Для этого в ней применяется мутация с высокой вероятностью $$p_m=0,05$$. Порода III используется как для исследования, так и для эксплуатации зон поиска решений и имеет среднее значение вероятности мутации $$p_m=0,005$$. Порода IV используется для эксплуатации найденной зоны поиска решений (exploitation). Поэтому в ней применяется низкая вероятность мутации $$p_m=0,003$$. РГА отбирает лучшие особи из пород II-IV и вводит их в породу I, если они лучше уже имеющихся в этой породе (I). Таким образом, порода I сохраняет лучшие хромосомы, появляющиеся в других породах. Через заданное число поколений ее хромосомы вводятся в породу IV и вытесняют ее текущие особи.
Неоднородные РГА с различным кодированием. В этой модификации РГА, иногда называемой "модель островов с инжекцией" , в каждой подпопуляции особи кодируются с различной точностью. Это дает возможность исследовать пространство поиска в разных подпопуляциях с различным шагом. Из подпопуляции с "крупной сеткой" лучшие особи "впрыскиваются" в подпопуляцию с "мелкой сеткой". При этом подпопуляция с низкой точностью имеет меньшую размерность пространства поиска и поэтому зона возможного экстремума обычно находится быстрее. Далее лучшие особи "впрыскиваются" в подпопуляцию с большей точностью, где решение уточняется с меньшим шагом.
Известны также модификации РГА, в которых в разных подпопуляциях используются арифметические операторы кроссинговера с различной точностью. Здесь, как и в предыдущей модификации, производится впрыскивание лучших решений из "грубой" подпопуляции в "тонкую" для последующей "доводки".
В целом распределенные ПГА более целесообразно использовать для повышения качества решения, в том случае, если его не удается достичь с помощью обычного (последовательного) ГА. При этом мощность каждой подпопуляции должна быть достаточно большой, чтобы не происходило "вырождение особей", которое часто ведет к преждевременной сходимости к локальному экстремуму. Увеличение быстродействия по сравнению с последовательным ГА также имеет место, но может быть меньше, чем у модели "рабочий-хозяин". Для повышения быстродействия в этом случае мощность подпопуляций должна быть небольшой, что существенно увеличивает быстродействие (ценой потери качества решения).
4.4. Клеточные ГА
Модель клеточных ГА (cellular GA), часто называемой также диффузией или "модель с тонкой структурой" (fine grain model), основана на пространственно распределенной популяции, в которой эволюционные взаимодействия возможны только с (в некотором смысле) ближайшими соседними особями. При этом особи обычно расположены в узлах некоторой регулярной структуры – сетки размерности $$d=1,2$$ или 3. Параметрами КГА являются: тип и топология сетки, размерность структуры, тип окрестности, вид отбора особей и т.п. КГА итеративно рассматривают взаимодействие группы особей, принадлежащих определенному локальному окружению. В простейшем случае рассматривается окрестность фон Неймана, где центральный элемент и его четыре ближайших соседа по вертикали и горизонтали образуют небольшой пул, в котором применяются генетические операторы. В каждом поколении КГА рассматривает в качестве центрального элемента окрестности только одну особь. Так как особь может принадлежать только нескольким окрестностям, то ее изменение влияет на соседей "мягко". Это обеспечивает хороший компромисс между медленной сходимостью и расширением пространства поиска.
Эта модель работает с каждой особью индивидуально и выбирает партнера для скрещивания подобно локальному отбору. Таким образом, имеет место диффузия информации в популяции. Интересно отметить, что в процессе поиска решения возникают и эволюционируют виртуальные острова – смежные области особей с примерно одинаковыми значениями ЦФ, что хорошо видно на [рис.4.6]
(рис 4.6) Виртуальные острова вследствие диффузии информации.
По синхронизации взаимодействия соседних элементов различают синхронные и асинхронные КГА. В синхронных КГА по синхросигналу (одновременно) вычисляется все новое поколение и записывается во временную (буферную) популяцию, которая затем заменяет старую популяцию согласно следующему алгоритму.
Клеточные ГА часто рассматриваются как стохастические клеточные автоматы, где мощность множества состояний равна числу точек в пространстве поиска решений. В синхронном КГА все клетки формально одновременно изменяют свое значение. Разработаны также и асинхронные КГА, где изменение клеток происходит "по событию" – изменению соседних элементов структуры.
4.5. Гибридные параллельные ГА
Представленные выше основные методы распараллеливания ГА могут использоваться в различных комбинациях на различных уровнях, что дает возможность строить гибридные модели ПГА. Например, на [рис.4.7 а-в) представлены гибридные модели, в которых при распараллеливании используется двухуровневый подход.]
(рис 4.7) Различная реализация параллельных ГА.
В данном случае на верхнем уровне для распараллеливания применяется РГА (coarse-grain implementation). В модели [рис.4.7 а каждый из островов реализуется (на нижнем уровне) в виде клеточного ГА, что позволяет объединить преимущества этих двух различных подходов. Модель ][рис.4.7 б - каждый из островов на нижнем уровне реализуется по схеме глобального распараллеливания - "раб (рабочий)- хозяин". Таким образом, здесь параллелизм используется для ускорения вычислений (на нижнем уровне) и в то же время он применяется при реализации взаимодействующих подпопуляций – островов (на верхнем уровне). И, наконец, в модели ][рис.4.7 в - на верхнем и нижнем уровнях реализуется модель островов. Таким образом, как классический ГА, так и структурированный ГА могут быть реализованы различными способами как на монопроцессорной так и на многопроцессорных компьютерных системах.]
4.6. Иерархические (многоуровневые) ГА
Иерархические ГА по своей идеологии примыкают к параллельным, и как мы видели в разделе 4.5, часто используются совместно с ними. Это позволяет комбинировать различные модели ПГА и разрабатывать гибридные ГА. Рассмотрим ГА как сложную систему, в которой есть, по крайней мере, два уровня объектов – хромосомы нижнего уровня, каждая из которых представляет решение конкретной проблемы. Объекты верхнего уровня представляют собой параметры ГА, такие как размер популяции, вероятность скрещивания и мутации, тип ЦФ и т.д. Схематически это показано на [рис.4.8.]
Заметим, что объекты верхнего уровня существенно влияют на эффективность ГА нижнего уровня. Рассмотрим популяцию структурных объектов верхнего уровня, каждая из которых представляет по сути ГА нижнего уровня. На верхнем уровне работает ГА над ГА нижнего уровня. Здесь в качестве оператора скрещивания может выступать обмен параметрами ГА, а в качестве мутации изменение этих параметров. Таким образом, имеем двухуровневый иерархический ГА.
На нижнем уровне протекают параллельно процессы обычных ГА, в которых каждая особь представляет решение конкретной проблемы и развивается обычным образом. На верхнем уровне в качестве особей используют ГА параметры нижнего уровня.
Здесь каждая особь представляет свой вариант значений параметров ГА нижнего уровня. Таким образом, на верхнем уровне подбираются рациональные параметры ГА нижнего уровня, которые далее передаются на нижний уровень для эффективного поиска решения проблемы.
Разработаны и многоуровневые (более 2-х) иерархические ГА, которые развивают этот подход. Заметим, что объекты верхнего уровня существенно влияют на эффективность ГА нижнего уровня. Рассмотрим популяцию структурных объектов верхнего уровня, каждая из которых представляет по сути ГА
(рис 4.8) Иерархический ГА
4.7. Коэволюционные ГА
Данный тип ГА заимствует у природы явления кооперации и конкуренции и использует обычно две подпопуляции (в общем случае число подпопуляций может быть и больше). Разработаны несколько видов кооэволюционных ГА, которые разделяются на кооперативные и конкурирующие ГА [[6]. Коэволюция между видами достаточно широко распространена в природе.]
Рассмотрим известный пример Дж.Холланда [[7] коэволюции конкурирующего типа на примере эволюции взаимодействия растения и насекомых. Некоторые виды растений живут в среде, содержащей насекомые, которые поедают эти растения. В этом случае "игра на выживание" содержит две основные компоненты: 1) чтобы выжить, растения используют механизм эволюции для защиты от насекомых; 2) насекомые используют растение в качестве пищи для выживания. И растения и насекомые эволюционируют вместе и стремятся приобрести (или усилить) свойства, которые помогают им выжить. Например, растения могут в результате эволюции приобрести твердую защитную поверхность (кожицу), что ведет к эволюции насекомых с более сильными челюстями. Или насекомые в результате эволюции начинают вырабатывать ядовитые вещества для данного вида насекомых. В этом случае последующие поколения насекомых начинают вырабатывать энзимы, которые нейтрализуют этот яд. Эффект коэволюции заключается в том, что каждое последующее поколение и растений и насекомых становится лучше, что помогает им выживать в окружающей среде. Данный биологический пример представляет коэволюцию конкурирующего вида типа "хищник-жертва", где присутствует обратная отрицательная связь между видами. Здесь победа для одного вида означает поражение для другого вида. Чтобы выжить проигравший вид адаптируется к новым свойствам победителя. В течение этого процесса сложность как хищника, так и жертвы могут сильно возрасти.]
Альтернативой является коэволюционный процесс симбиоза, где различные виды не конкурируют, а вступают в кооперацию. В этом случае успех одного вида улучшает способность выживания других видов и достигается это за счет положительной обратной связи.
В стандартных ГА эволюция обычно рассматривается как попытка адаптации в фиксированной внешней среде. Напротив, в коэволюционных ПГА реализуется эволюция во внешней среде, которая изменяется вследствие воздействия других популяций. Кроме этого, коэволюционные ПГА существенно отличаются от стандартных ГА по методу вычисления фитнесс-функции. В обычных ГА используется абсолютные значения фитнесс-функции, определяющие качество особи в популяции. С другой стороны, в коэволюционных ГА не применяются абсолютные значения фитнесс-функции, а используется значения фитнесс-функции относительно некоторых оппонентов.
Как указано ранее, разработаны два основных класса коэволюционных ГА: конкурирующие и кооперативные. Для каждого из них различают согласно [[7] ряд подклассов. Для конкурирующей коэволюции это: 1) Конкуренция (Competition), где оба вида соперничают друг с другом. Благодаря отрицательной обратной связи между видами успех одного вида воспринимается как неудача для другого вида. 2) Аменсализм (Amensalism), где неудача одного вида не воздействует на другой вид.]
Для кооперативной эволюции различают: 1) мутуализм (mutualism), где оба вида сотрудничают с выгодой для себя и между ними существует положительная обратная связь; 2) комменсализм (commensalism), где выигрывает один вид, в то время как на как второй вид этот процесс не оказывает воздействия; 3) Паразитизм (parasitizm), где один вид (паразиты) выигрывает, в то время как второму виду причиняется вред. Далее мы более подробно рассмотрим только два подкласса: конкурирующая коэволюция типа "хищник-жертва" и кооперативная коэволюция типа мутуализм.
4.7.1. Конкурирующая коэволюция
На практике более распространены кооперативные коэволюционные ГА. Здесь взаимодействие между подпопуляциями осуществляется только за счет оценки значений фитнесс-функций. В этом случае обычно эволюционируют одновременно две популяции. Особи первой популяции представляют решение проблемы, в то время как особи второй популяции представляют тесты для особей первой популяции. Особи первой популяции эволюционируют чтобы решить как можно больше тестовых задач из второй популяции, а эволюция особей тестовой популяции повышает сложность тестовых задач. Значение фитнесс-функции особей основной популяции пропорционально числу тестов, решаемых данной особью. Наоборот, значение фитнесс-функции второй популяции обратно пропорционально числу особей (стратегий), которые решают ее. Таким образом, движущей силой конкурирующей эволюции является относительная фитнесс-функция, которая оценивает характеристики особей основной популяции относительно особей тестовой популяции, в отличие от классичекого ГА, где используется абсолютное значение фитнесс-функции.
Для вычисления значения относительной фитнесс-функции важны, прежде всего, два следующих аспекта: 1) какие особи конкурирующей популяции используются; 2) каким образом эти особи используются для вычисления значения относительной фитнесс-функции
Рассмотрим первый аспект, в котором определяется, как могут отбираться особи конкурирующей популяции для вычисления значений относительной фитнесс-функции. Используются следующие основные методы отбора:
Все против всех, где каждая особь тестируется относительно каждой особи другой популяции.
Случайный отбор, где фитнесс-значение каждой особи тестируется относительно случайно выбранной группы особей другой популяции. Очевидно, что этот метод требует меньших вычислительных ресурсов, чем предыдущий.
Турнирный отбор, который использует значения относительной фитнесс-функции для отбора лучших особей – оппонентов.
Все против лучшего, при котором все особи тестируются относительно лучшей особи конкурирующей популяции.
Совместное тестирование, где тест выбирается в виде особи оппонента с максимальной конкурирующей совместной фитнесс-функцией. Этот вид тестирования ведет к выбору оппонентов, которые побеждают (решают тесты) большое число особей из конкурирующей популяции.
Далее рассмотрим второй аспект, где представлены различные варианты относительной фитнесс-функции в которых измеряется относительное фитнесс-значение для каждой особи популяции. Предположим, что две популяции $$C_1$$ и $$C_2$$ коэволюционируют и для этого необходимо оценить относительную фитнесс-функцию каждой особи $$C_1\cdot x_i$$ популяции $$C_1$$. Наиболее распространенными являются следующие виды задания относительных фитнесс-функций:
Простая фитнесс-функция, где тестируемые особи берутся из популяции $$C_2$$ и подсчитывается число особей $$C_2$$, для которых $$C_1\cdot x_i$$ является победителем. В этом случае значение относительной фитнесс-функции определяется суммой успешных тестирований для $$C_1\cdot x_i$$.
Раздельная фитнесс-функция, которая определяется с учетом подобия особей популяции $$C_1$$. При этом значение фитнесс-функции особи делится на сумму его подобий с другими особями этой популяции. Подобие можно определить как число особей, которые также побеждают особи из популяции $$C_2$$. Такое определение поощряет необычные особи, непохожие на остальные особи популяции.
Конкурирующая раздельная фитнесс-функция, где значение фитнесс-функции для особи $$C_1\cdot x_i$$ определяется следующим образом $$f(C_1\cdot x_i)=\sum_{i=1}^{C_2\cdot n_i}\frac{1}{C_1\cdot n_i}$$, где $$C_2\cdot x_1,\dots ,C_2\cdot x_{C_2\cdot n_i}$$ определяет тестовую популяцию и $$C_1\cdot n_i$$ -общее число особей в популяции $$C_1$$, которые побеждают особь $$C_2\cdot n_i$$. Эта фитнесс-функция поощряет особи популяции побеждающие особи популяции $$C_2$$, которые не могут "побить" другие особи $$C_1$$. Это не является необходимым в том случае, когда лучшая особь побеждает большую часть особей $$C_2$$.
Турнирная фитнесс-функция использует для ранжирования особей двоичный турнир с уничтожением одной слабой особи. В результате функция дает дерево турниров с лучшей особью в корне. На каждом уровне дерева случайно выбираются два оппонента этого уровня и лучший из них продвигается на следующий уровень. В случае нечетного числа конкурентов единственная имеющаяся особь этого уровня продвигается на следующий уровень. После турнирного ранжирования любой стандартный оператор может быть использован для выбора родителей.
В стандартных ГА элитизм является механизмом, который обеспечивает выживание лучших родительских особей, которые в результате попадают в следующую популяцию. Чтобы выжить в течение многих поколений, особь должна иметь высокие значения фитнесс-функции почти в каждом поколении. Для коэволюции введен механизм "hall of fame" [[8] ("зал славы"), который обобщает элитизм во времени. Здесь в каждом поколении лучшая особь популяции запоминается в этом "зале популярности". Естественно он имеет фиксированный размер, и при пополнении новые лучшие особи вытесняют половину худших старых особей. Особи одной популяции здесь соревнуются с текущей тестовой популяцией и половиной "зала популярности".]
Общий алгоритм А4.1 конкурирующей коэволюции предполагает использование двух популяций. Здесь $$C_1$$ представляет популяцию решений, и $$C_2$$ - тестовую популяцию. Случай с одной популяцией представлен в алгоритме А4.2.
Характеристики коэволюционных алгоритмов можно улучшить если две конкурирующие популяции сильно отличаются друг от друга. Такое разнообразие можно поддерживать путем ввода механизма, который содействует образованию ниш. В этом случае эффективны раздельное тестирование с применением раздельных фитнесс-функций.
4.7.2. Кооперативная коэволюция
Рассмотрим кооперативный ПГА, где значение фитнесс-функции особи зависит от ее способности "сотрудничать" с особями других подпопуляций. Этот подход часто позволяет произвести декомпозицию сложной проблемы на несколько менее сложных задач, каждая из которых решается с помощью ГА. Данный тип ПГА наиболее широко применяется при решении задач многокритериальной оптимизации. Одной из наиболее сложных задач при разработке кооперативной коэволюции является метод определения "премии" (credit assignment) для особи. Основной вопрос - как построить фитнесс-функцию для отдельных особей так, чтобы она учитывала коллективный эффект всех видов.
В некоторых работах [[9] предложен общий подход к эволюции сложных решений путем расщепления на подкомпоненты, которые эволюционируют независимо друг от друга. При этом используется отдельная популяция для эволюции каждой подкомпоненты и соответствующий эволюционный алгоритм. Представления (кодирование) каждой компоненты затем комбинируются для образования сложного решения, которое оценивается с помощью глобальной фитнесс-функции. На ее основе определяются обратные кредитные потоки к каждой компоненте, отражающие как хорошо данный компонент сотрудничает с другими. Эта локальная фитнесс-функция затем используется в подпопуляции для эволюции лучшего решения.]
Данный подход, в частности, применялся для оптимизации функций многих переменных [[10]. При этом для задачи размерности $$n_x$$ используется $$n_x$$ подпопуляций – по одной для каждой координаты. Каждая подпопуляция отвечает за оптимизацию по одному из параметров, но в целом ни одна подпопуляция не может образовать полное решение сама по себе. Сотрудничество достигается путем объединения представлений решений для каждой подпопуляции. Эффективность такого сотрудничества оценивается следующим образом. При рассмотрении $$j$$-ой подпопуляции $$C_j$$ каждая особь $$C_j\cdot x_i$$ "сотрудничает" с лучшей особью их каждой подпопуляции путем объединения этих лучших компонент с $$C_j\cdot x_i$$ в полное решение. В этом случае определение "премии" особи сводится просто к вычислению значения глобальной фитнесс-функции полного решения.]
Экспериментальные исследования показали [[10], что этот подход не дает хорошие результаты в том случае, когда параметры задачи сильно взаимосвязаны вследствие использования жадной эвристики в определении премии особи. Для уменьшения этого эффекта предложено использовать два дополнительных вектора. Первый вектор строится на основе лучших особей каждой подпопуляции, как описано ранее. Второй вектор выбирает случайные особи из других подпопуляций и "склеивает" их с $$C_j\cdot x_i$$. Лучшее значение фитнесс-функции этих двух векторов затем используется в качестве премии (кредита) для $$C_j\cdot x_i$$. Кроме решения задач многомерной оптимизации авторы использовали этот подход при обучении каскадных нейронных сетей[][11] и обучения роботов[][12].]
4.8. Инструментарий распараллеливания
Как отмечалось выше, для реализации ПГА могут быть использованы компьютерные системы с различными архитектурами: SISD, SIMD, MIMD и т.д. Вместо описания многочисленных специальных архитектур и программных конструкций, которые используются при реализации ПГА, далее мы кратко рассмотрим те параллельные и распределенные модели, которые не зависят от конкретных структур. Почти все ПГА реализуются на основе модели каналов для передачи сообщений в коммуникациях, поскольку они позволяют описывать многопроцессорные системы с распределенной памятью, которые являются наиболее удобным и распространенным средством реализации ПГА. В модели передачи сообщений процессы в одном или физически различных процессорах сообщаются между собой путем передачи друг другу сообщений через среду коммуникации, которая представлена стандартом или специальной схемой соединения. Основными элементами здесь являются процедуры отправления и приема сообщений. В простейшей форме, отправление определяет локальный буфер передаваемых данных. Процедура приема обычно определяет процесс отправления и локальный буфер, в котором сохраняются входящие данные. В качестве инструментария чаще всего используются следующие средства: сокет (sockets), параллельная виртуальная машина (parallel virtual machine -PVM), интерфейс передачи сообщений (message passing interface - MPI), Ява (Java), архитектура общего назначения запрос-посредник (common object request broker architecture) - CORBA и Globus, которые обеспечивают большие функциональные возможности, чем простой сервис передачи сообщений.
Контрольные вопросы
Какие свойства ГА способствуют его распараллеливанию?
Опишите модель "рабочий - хозяин".
Каковы функции процессора – хозяина?
Что делает процессор – рабочий?
Какой выигрыш дает модель "рабочий - хозяин"?
Чем отличается модель "рабочий - хозяин" от "модели островов"?
Какие факторы влияют на миграцию в "модели островов"?
Какие вы знаете виды распределенных ГА?
Опишите клеточные ГА.
Что такое виртуальные острова?
Что такое коэволюционные ГА?
Приведите различные варианты реализации параллельных ГА.
Какой инструментарий можно использовать при реализации ГА?
Опишите возможный вариант иерархического ГА.
Краткие итоги:
изложены основы параллельных ГА, их структура и параметры;
представлен глобальный параллельный ГА на основе модели "рабочий-хозяин Ю.А.";
описан распределенный ГА на базе "модели островов";
рассмотрен клеточный ГА, его структура и параметры;
представлены коэволюционные ГА на основе двух моделей - "кооперативная эволюция" и "конкурирующая эволюция".
4.1. Структуризация ГА
Для нетривиальных задач выполнение одного репродуктивного цикла – поколения в ГА требует значительных вычислительных ресурсов. При решении многих задач используется не двоичное представление особи – решения проблемы, а более сложные структуры – массивы (матрицы) действительных чисел, связные списки, деревья, графы [[1] и т.д. Поэтому вычисление значения фитнесс-функции для каждой особи, потенциального решения проблемы, часто является самой трудоемкой операцией в ГА. Для повышения эффективности разрабатываются новые методы кодирования особей, генетические операторы кроссинговера и мутации, гибридные алгоритмы, параллельные алгоритмы и т.п.[][2,][3,][4].]
Первые работы в этом направлении появились в 60-х годах, но только в 80-е годы, когда были разработаны доступные средства параллельной реализации, исследования ПГА приняли систематический массовый характер и практическую направленность. В этом направлении разработано множество моделей и реализаций, некоторые из которых представлены ниже.
Прежде всего, необходимо отметить, что в основе ПГА лежит структуризация популяции (множества потенциальных решений) – его разбиения на несколько подмножеств (подпопуляций). Это разбиение можно сделать различными способами, которые и определяют различные виды ПГА. Согласно современной классификации различают глобальные ПГА, распределенные ГА (РГА), клеточные ГА (КГА) и коэволюционные ГА (КЭГА). В простом ГА, графически представленном на [рис. 4.1а), используется одна популяция особей, каждая из которых может взаимодействовать с любой другой особью. На ][рис. 4.1а) каждая особь представлена точкой. Глобальный ПГА реализуется фактически по схеме "клиент - сервер" (][рис. 4.1б)), где на сервере, в основном, выполняется генетический алгоритм, а клиенты выполняют "черновую работу" - оценку значений фитнесс-функции всех особей популяции, которая требует больших вычислительных ресурсов. В РГА популяция разбивается на множество подпопуляций, каждая из которых эволюционирует независимо (согласно ПГА) и обменивается через некоторое "время изоляции" с соседними подпопуляциями по определенной схеме, что графически представлено на ][рис. 4.1в. В КГА имеется множество подпопуляций, каждая из которых состоит только из одной особи. В один момент времени данная особь может взаимодействовать только с соседними особями. Отношение соседства задается в виде некоторой регулярной структуры – сетки, что графически представлено на ][рис. 4.1г.]
(рис 4.1) а) Простой ГА, б) Распределенный ГА, в) Модель островов, г) Клеточный ГА.
При заданной структуризации ГА реализуется собственно распараллеливание ГА. При этом ожидаются следующие преимущества:
поиск альтернативных решений одной и той же проблемы;
параллельный поиск из различных точек в пространстве решений;
допускают хорошую реализацию в виде островов или клеточной структуры;
большая эффективность поиска даже в случае реализации не на параллельных вычислительных структурах;
хорошая совместимость с другими эволюционными и классическими процедурами поиска;
существенное повышение быстродействия на многопроцессорных системах.
Рассмотрим основные современные методы распараллеливания ГА.
4.2. Параллельный генетический алгоритм на основе модели "рабочий-хозяин"
В данном разделе для распараллеливания ГА используется модель "с" (иногда она называется "клиент-сервер"), поскольку она требует наименьших изменений в существующей версии программного обеспечения, реализующего последовательный ГА и дает неплохие результаты. Ниже представлен укрупненный алгоритм параллельного ГА на основе модели "рабочий - хозяин".
Параллельный ГА "Рабочий - хозяин"
{
Генерация популяции P хромосом случайным образом;
выполнение параллельно для всех особей
{
Оценка значения фитнесс-функции для каждой особи;
}
While(критерий останова не выполнен)
{
отбор лучших особей;
выполнение генетических операторов кроссиговера и мутации;
формирование промежуточной популяции;
выполнение параллельно для всех особей
{
Оценка значения фитнесс-функции для каждой особи;
}
внесение лучших новых особей;
удаление худших старых особей;
формирование новой популяции ;
}
}
При этом затраты по вычислению значений фитнесс-функций равномерно распределяются по всем процессорам, для которых используется одна и та же фитнесс-функция. Поэтому для $$n$$ особей и $$P$$(одинаковых) процессоров мы каждому процессору относим $$n/P$$ особей. Значения фитнесс-функции вычисляются соответствующими (рабочими) процессорами и посылаются в один процессор (хозяин), который собирает всю информацию, обрабатывает и передает ее снова рабочим процессорам. Процессор "хозяин" имеет информацию о значениях фитнесс-функции для всех особей и может генерировать следующее поколение на этой основе.
Итак, процессор–хозяин выполняет центральную часть (ядро) алгоритма, в то время как "черновая работа" - вычисление значений фитнесс-функции для всех особей реализуется на процессорах–рабочих. Для баланса множество обрабатываемых особей популяции разбивается на примерно одинаковые подмножества.
В конце каждого из этапов помещаются точки синхронизации. Когда процессор-хозяин достигает эти точки, он переходит в режим ожидания, пока все рабочие процессоры не закончат свои задания, что гарантирует глобальную корректность алгоритма. При этом работа между процессором-хозяином и рабочими распределяется следующим образом.
Процессор-хозяин:
выполняет все вход-выходные операции с пользователем и файловой системой, читает задание и записывает результаты;
первоначально запускает "рабочие" процессы на доступных ресурсах;
распределяет задания каждому рабочему процессору;
организует управление процессом поиска решения и по мере необходимости посылает соответствующие сообщения активации рабочих процессоров; по окончании задания рабочим процессором процессор-хозяин принимает полученные результаты и соответственно изменяет глобальные структуры данных (общий список заданий, значения фитнесс-функции для особей и т.п.).
Каждый "рабочий" принимает задание от "хозяина" и определяет значение фитнесс-функции для особей, полученный результат посылает хозяину и ожидает следующего задания. Поскольку размер популяции много больше числа процессоров, достигается хороший баланс в загрузке процессоров. Диаграмма потоков данных в данном алгоритме приведена на [рис.4.2 (на примере распределенного логического моделирования).]
При использовании модели "рабочий - хозяин" окончательные результаты (поиска решения данной задачи) близки к тем, что получены на однопроцессорной компьютерной системе с использованием аналогичного алгоритма. Качество решения при этом не теряется и в большинстве случаев несколько улучшается, а время его поиска существенно сокращается. В целом данная модель позволяет быстро (с минимальными модификацями) выполнить параллелизацию ГА и дает, прежде всего, ускорение процесса поиска решения. Данную модель не сложно реализовать в локальной сети с использованием технологии сокетов.
Типичный график увеличения быстродействия (для задачи построения проверяющих тестов) представлен на [рис.4.3. [][5]. Здесь вверху для сравнения представлен "идеальный" линейный график роста ускорения в зависимости от увеличения числа процессоров. Реальное ускорение (особенно для большого числа процессоров) естественно несколько меньше.]
(рис 4.2) Потоки данных в модели "рабочий-хозяин"("клиент-сервер")
Следует отметить, что для задач большей размерности выигрыш в увеличении быстродействия обычно больше, так как "накладные расходы" на пересылки по сравнению с основными затратами на поиск решения составляют меньшую долю. На [рис.4.4 для примера представлен график увеличения быстродействия с ростом размерности задачи (сложности обрабатываемой схемы) [][5].]
(рис 4.3) Рост быстродействия при увеличении числа процессоров-клиентов
(рис 4.4) Увеличение быстродействия с ростом размерности задачи (сложности схемы)
Эксперименты показывают, что при грамотной реализации этой модели даже в локальной сети можно выиграть порядок в увеличении быстродействия (при относительно небольших модификациях исходного программного обеспечения).
4.3. Параллельные генетические алгоритмы на основе "модели островов"
Распределенные ГА используют, в основном, так называемую "модель островов", где каждая подпопуляция развивается на своем "острове". Между островами производится (достаточно редко) обмен лучшими особями. Эта модель может быть реализована в распределенной памяти компьютерной системы, имеющей MIMD-архитектуру согласно классификации Flynn. Преимущество РГА в том, что они работают быстрее даже на однопроцессорных компьютерных системах вследствие лучшей структуризации. Причина заключается в том, что число вычислений сокращается благодаря распределению поиска в различных областях пространства решений. Разработаны различные виды РГА, но практически все они являются вариациями базового алгоритма, который представлен следующим псевдокодом.
Основными факторами, которые влияют на миграцию в модели островов (и следовательно, на их эффективность), являются следующие.
Топология, определяющая отношение соседства между подпопуляциями. Здесь обмен особями происходит только между соседними подпопуляциями. Существует также несколько стандартных схем обмена особями между подпопуляциями, которые представлены ниже на [рис.4.5.]
Для каждой подпопуляции формируется "пул" - множество потенциальных эмигрантов из других подпопуляций. Далее из этого "пула" по определенному закону выбираются эмигранты для данной подпопуляции.
Степень миграции, которая определяет количество мигрирующих особей.
Время изоляции, определяющее число поколений между сеансами миграции.
Стратегия отбора особей в пул обмена. Здесь наиболее распространенными являются два подхода. При первом подходе из подпопуляции особи выбираются случайным образом – при этом сохраняется разнообразие генетического материала. При втором подходе из каждой подпопуляции выбираются лучшие в некотором смысле особи, что делает процесс более направленным. При этом также существуют различные методы отбора лучших хромосом (раздел 3.2).
Стратегия замены особей на мигрировавшие хромосомы из соседних подпопуляций. Здесь также существуют различные подходы: из подпопуляции удаляются худшие, случайные особи и т.п.
Стратегия репликации мигрирующих особей. При первом подходе мигрирующая особь остается также и в "родной" подпопуляции. Второй подход требует удаления мигрирующей особи из "родной" подпопуляции. Первая стратегия может привести к доминированию в различных подпопуляциях одних и тех же сильных особей. При второй стратегии особь может через некоторое время вернуться назад в исходную подпопуляцию, что ведет к лишним затратам вычислительных ресурсов.
Распределенные ГА можно классифицировать по следующим признакам.
По методу миграции принято разделять:
изолированные РГА (isolated DGA), где нет миграции между подпопуляциями (иногда называются разделенные РГА – partitioned DGA);
синхронные РГА (synchronous DGA), в которых миграции между подпопуляциями синхронизированы – выполняются в одно и тоже время;
асинхронные РГА (asynchronous DGA), где миграции могут происходить по событию в разные моменты времени в различных подпопуляциях, в зависимости от активности в каждой подпопуляции (асинхронное поведение характерно для естественной эволюции, которая развивается по-разному в зависимости от внешней среды).
По изменению схемы обмена особями различаются:
статическая схема соединений между подпопуляциями, которая не изменяется в процессе эволюции;
динамическая схема соединений, в которой вид обмена особями между подпопуляциями может изменяться в процессе эволюции.
По однородности подпопуляций принято разделять на:
однородные РГА (homogeneous DGA), где кажлая подпопуляция использует одни и те же способы кодирования хромосомы, генетические операторы, вид фитнесс-функций и т.п.;
неоднородные РГА (heterogeneous DGA), в которых каждая подпопуляция может иметь различные параметры управления, метод кодирования хромосомы, генетические операторы и т.п.
(рис 4.5) Типовые схемы обмена особями в модели островов
Неоднородные РГА по мнению некоторых авторов являются хорошим инструментом для предотвращения преждевременной сходимости к локальным экстремумам и позволяют эффективно решать проблему расширения (исследования) и эксплуатации зоны поиска решений. В этой области разработаны некоторые интересные модификации РГА, которые представлены ниже.
Адаптация конкурирующих подпопуляций. Здесь для каждого возможного вида генетических операторов формируется подпопуляция. Общее число особей фиксировано (во всех подпопуляциях), в то время как мощность каждой подпопуляции может варьироваться. Каждая подпопуляция соревнуется с конкурентами таким образом, что она приобретает или теряет особи в зависимости от ее качества относительно других подпопуляций. Например, разные подпопуляции могут иметь различный шаг мутации (над вещественным представлением) или отличающиеся арифметические операторы рекомбинации. С другой стороны каждая подпопуляция может иметь различные схемы обмена, степень миграции и т.п. Через определенное число поколений происходит ранжирование различных стратегий и параметры каждой адаптируются к значениям лучшей подпопуляции.
РГА, основанные на миграции и искусственной селекции (GAMAS). Эта модификации использует четыре подпопуляции – "породы" I – IV. Сначала создаются "породы" I – IV. Порода I является основной и накапливает найденные лучшие решения. Порода II предназначена для исследования (новых) областей поиска (exploration). Для этого в ней применяется мутация с высокой вероятностью $$p_m=0,05$$. Порода III используется как для исследования, так и для эксплуатации зон поиска решений и имеет среднее значение вероятности мутации $$p_m=0,005$$. Порода IV используется для эксплуатации найденной зоны поиска решений (exploitation). Поэтому в ней применяется низкая вероятность мутации $$p_m=0,003$$. РГА отбирает лучшие особи из пород II-IV и вводит их в породу I, если они лучше уже имеющихся в этой породе (I). Таким образом, порода I сохраняет лучшие хромосомы, появляющиеся в других породах. Через заданное число поколений ее хромосомы вводятся в породу IV и вытесняют ее текущие особи.
Неоднородные РГА с различным кодированием. В этой модификации РГА, иногда называемой "модель островов с инжекцией" , в каждой подпопуляции особи кодируются с различной точностью. Это дает возможность исследовать пространство поиска в разных подпопуляциях с различным шагом. Из подпопуляции с "крупной сеткой" лучшие особи "впрыскиваются" в подпопуляцию с "мелкой сеткой". При этом подпопуляция с низкой точностью имеет меньшую размерность пространства поиска и поэтому зона возможного экстремума обычно находится быстрее. Далее лучшие особи "впрыскиваются" в подпопуляцию с большей точностью, где решение уточняется с меньшим шагом.
Известны также модификации РГА, в которых в разных подпопуляциях используются арифметические операторы кроссинговера с различной точностью. Здесь, как и в предыдущей модификации, производится впрыскивание лучших решений из "грубой" подпопуляции в "тонкую" для последующей "доводки".
В целом распределенные ПГА более целесообразно использовать для повышения качества решения, в том случае, если его не удается достичь с помощью обычного (последовательного) ГА. При этом мощность каждой подпопуляции должна быть достаточно большой, чтобы не происходило "вырождение особей", которое часто ведет к преждевременной сходимости к локальному экстремуму. Увеличение быстродействия по сравнению с последовательным ГА также имеет место, но может быть меньше, чем у модели "рабочий-хозяин". Для повышения быстродействия в этом случае мощность подпопуляций должна быть небольшой, что существенно увеличивает быстродействие (ценой потери качества решения).
4.4. Клеточные ГА
Модель клеточных ГА (cellular GA), часто называемой также диффузией или "модель с тонкой структурой" (fine grain model), основана на пространственно распределенной популяции, в которой эволюционные взаимодействия возможны только с (в некотором смысле) ближайшими соседними особями. При этом особи обычно расположены в узлах некоторой регулярной структуры – сетки размерности $$d=1,2$$ или 3. Параметрами КГА являются: тип и топология сетки, размерность структуры, тип окрестности, вид отбора особей и т.п. КГА итеративно рассматривают взаимодействие группы особей, принадлежащих определенному локальному окружению. В простейшем случае рассматривается окрестность фон Неймана, где центральный элемент и его четыре ближайших соседа по вертикали и горизонтали образуют небольшой пул, в котором применяются генетические операторы. В каждом поколении КГА рассматривает в качестве центрального элемента окрестности только одну особь. Так как особь может принадлежать только нескольким окрестностям, то ее изменение влияет на соседей "мягко". Это обеспечивает хороший компромисс между медленной сходимостью и расширением пространства поиска.
Эта модель работает с каждой особью индивидуально и выбирает партнера для скрещивания подобно локальному отбору. Таким образом, имеет место диффузия информации в популяции. Интересно отметить, что в процессе поиска решения возникают и эволюционируют виртуальные острова – смежные области особей с примерно одинаковыми значениями ЦФ, что хорошо видно на [рис.4.6]
(рис 4.6) Виртуальные острова вследствие диффузии информации.
По синхронизации взаимодействия соседних элементов различают синхронные и асинхронные КГА. В синхронных КГА по синхросигналу (одновременно) вычисляется все новое поколение и записывается во временную (буферную) популяцию, которая затем заменяет старую популяцию согласно следующему алгоритму.
Клеточные ГА часто рассматриваются как стохастические клеточные автоматы, где мощность множества состояний равна числу точек в пространстве поиска решений. В синхронном КГА все клетки формально одновременно изменяют свое значение. Разработаны также и асинхронные КГА, где изменение клеток происходит "по событию" – изменению соседних элементов структуры.
4.5. Гибридные параллельные ГА
Представленные выше основные методы распараллеливания ГА могут использоваться в различных комбинациях на различных уровнях, что дает возможность строить гибридные модели ПГА. Например, на [рис.4.7 а-в) представлены гибридные модели, в которых при распараллеливании используется двухуровневый подход.]
(рис 4.7) Различная реализация параллельных ГА.
В данном случае на верхнем уровне для распараллеливания применяется РГА (coarse-grain implementation). В модели [рис.4.7 а каждый из островов реализуется (на нижнем уровне) в виде клеточного ГА, что позволяет объединить преимущества этих двух различных подходов. Модель ][рис.4.7 б - каждый из островов на нижнем уровне реализуется по схеме глобального распараллеливания - "раб (рабочий)- хозяин". Таким образом, здесь параллелизм используется для ускорения вычислений (на нижнем уровне) и в то же время он применяется при реализации взаимодействующих подпопуляций – островов (на верхнем уровне). И, наконец, в модели ][рис.4.7 в - на верхнем и нижнем уровнях реализуется модель островов. Таким образом, как классический ГА, так и структурированный ГА могут быть реализованы различными способами как на монопроцессорной так и на многопроцессорных компьютерных системах.]
4.6. Иерархические (многоуровневые) ГА
Иерархические ГА по своей идеологии примыкают к параллельным, и как мы видели в разделе 4.5, часто используются совместно с ними. Это позволяет комбинировать различные модели ПГА и разрабатывать гибридные ГА. Рассмотрим ГА как сложную систему, в которой есть, по крайней мере, два уровня объектов – хромосомы нижнего уровня, каждая из которых представляет решение конкретной проблемы. Объекты верхнего уровня представляют собой параметры ГА, такие как размер популяции, вероятность скрещивания и мутации, тип ЦФ и т.д. Схематически это показано на [рис.4.8.]
Заметим, что объекты верхнего уровня существенно влияют на эффективность ГА нижнего уровня. Рассмотрим популяцию структурных объектов верхнего уровня, каждая из которых представляет по сути ГА нижнего уровня. На верхнем уровне работает ГА над ГА нижнего уровня. Здесь в качестве оператора скрещивания может выступать обмен параметрами ГА, а в качестве мутации изменение этих параметров. Таким образом, имеем двухуровневый иерархический ГА.
На нижнем уровне протекают параллельно процессы обычных ГА, в которых каждая особь представляет решение конкретной проблемы и развивается обычным образом. На верхнем уровне в качестве особей используют ГА параметры нижнего уровня.
Здесь каждая особь представляет свой вариант значений параметров ГА нижнего уровня. Таким образом, на верхнем уровне подбираются рациональные параметры ГА нижнего уровня, которые далее передаются на нижний уровень для эффективного поиска решения проблемы.
Разработаны и многоуровневые (более 2-х) иерархические ГА, которые развивают этот подход. Заметим, что объекты верхнего уровня существенно влияют на эффективность ГА нижнего уровня. Рассмотрим популяцию структурных объектов верхнего уровня, каждая из которых представляет по сути ГА
(рис 4.8) Иерархический ГА
4.7. Коэволюционные ГА
Данный тип ГА заимствует у природы явления кооперации и конкуренции и использует обычно две подпопуляции (в общем случае число подпопуляций может быть и больше). Разработаны несколько видов кооэволюционных ГА, которые разделяются на кооперативные и конкурирующие ГА [[6]. Коэволюция между видами достаточно широко распространена в природе.]
Рассмотрим известный пример Дж.Холланда [[7] коэволюции конкурирующего типа на примере эволюции взаимодействия растения и насекомых. Некоторые виды растений живут в среде, содержащей насекомые, которые поедают эти растения. В этом случае "игра на выживание" содержит две основные компоненты: 1) чтобы выжить, растения используют механизм эволюции для защиты от насекомых; 2) насекомые используют растение в качестве пищи для выживания. И растения и насекомые эволюционируют вместе и стремятся приобрести (или усилить) свойства, которые помогают им выжить. Например, растения могут в результате эволюции приобрести твердую защитную поверхность (кожицу), что ведет к эволюции насекомых с более сильными челюстями. Или насекомые в результате эволюции начинают вырабатывать ядовитые вещества для данного вида насекомых. В этом случае последующие поколения насекомых начинают вырабатывать энзимы, которые нейтрализуют этот яд. Эффект коэволюции заключается в том, что каждое последующее поколение и растений и насекомых становится лучше, что помогает им выживать в окружающей среде. Данный биологический пример представляет коэволюцию конкурирующего вида типа "хищник-жертва", где присутствует обратная отрицательная связь между видами. Здесь победа для одного вида означает поражение для другого вида. Чтобы выжить проигравший вид адаптируется к новым свойствам победителя. В течение этого процесса сложность как хищника, так и жертвы могут сильно возрасти.]
Альтернативой является коэволюционный процесс симбиоза, где различные виды не конкурируют, а вступают в кооперацию. В этом случае успех одного вида улучшает способность выживания других видов и достигается это за счет положительной обратной связи.
В стандартных ГА эволюция обычно рассматривается как попытка адаптации в фиксированной внешней среде. Напротив, в коэволюционных ПГА реализуется эволюция во внешней среде, которая изменяется вследствие воздействия других популяций. Кроме этого, коэволюционные ПГА существенно отличаются от стандартных ГА по методу вычисления фитнесс-функции. В обычных ГА используется абсолютные значения фитнесс-функции, определяющие качество особи в популяции. С другой стороны, в коэволюционных ГА не применяются абсолютные значения фитнесс-функции, а используется значения фитнесс-функции относительно некоторых оппонентов.
Как указано ранее, разработаны два основных класса коэволюционных ГА: конкурирующие и кооперативные. Для каждого из них различают согласно [[7] ряд подклассов. Для конкурирующей коэволюции это: 1) Конкуренция (Competition), где оба вида соперничают друг с другом. Благодаря отрицательной обратной связи между видами успех одного вида воспринимается как неудача для другого вида. 2) Аменсализм (Amensalism), где неудача одного вида не воздействует на другой вид.]
Для кооперативной эволюции различают: 1) мутуализм (mutualism), где оба вида сотрудничают с выгодой для себя и между ними существует положительная обратная связь; 2) комменсализм (commensalism), где выигрывает один вид, в то время как на как второй вид этот процесс не оказывает воздействия; 3) Паразитизм (parasitizm), где один вид (паразиты) выигрывает, в то время как второму виду причиняется вред. Далее мы более подробно рассмотрим только два подкласса: конкурирующая коэволюция типа "хищник-жертва" и кооперативная коэволюция типа мутуализм.
4.7.1. Конкурирующая коэволюция
На практике более распространены кооперативные коэволюционные ГА. Здесь взаимодействие между подпопуляциями осуществляется только за счет оценки значений фитнесс-функций. В этом случае обычно эволюционируют одновременно две популяции. Особи первой популяции представляют решение проблемы, в то время как особи второй популяции представляют тесты для особей первой популяции. Особи первой популяции эволюционируют чтобы решить как можно больше тестовых задач из второй популяции, а эволюция особей тестовой популяции повышает сложность тестовых задач. Значение фитнесс-функции особей основной популяции пропорционально числу тестов, решаемых данной особью. Наоборот, значение фитнесс-функции второй популяции обратно пропорционально числу особей (стратегий), которые решают ее. Таким образом, движущей силой конкурирующей эволюции является относительная фитнесс-функция, которая оценивает характеристики особей основной популяции относительно особей тестовой популяции, в отличие от классичекого ГА, где используется абсолютное значение фитнесс-функции.
Для вычисления значения относительной фитнесс-функции важны, прежде всего, два следующих аспекта: 1) какие особи конкурирующей популяции используются; 2) каким образом эти особи используются для вычисления значения относительной фитнесс-функции
Рассмотрим первый аспект, в котором определяется, как могут отбираться особи конкурирующей популяции для вычисления значений относительной фитнесс-функции. Используются следующие основные методы отбора:
Все против всех, где каждая особь тестируется относительно каждой особи другой популяции.
Случайный отбор, где фитнесс-значение каждой особи тестируется относительно случайно выбранной группы особей другой популяции. Очевидно, что этот метод требует меньших вычислительных ресурсов, чем предыдущий.
Турнирный отбор, который использует значения относительной фитнесс-функции для отбора лучших особей – оппонентов.
Все против лучшего, при котором все особи тестируются относительно лучшей особи конкурирующей популяции.
Совместное тестирование, где тест выбирается в виде особи оппонента с максимальной конкурирующей совместной фитнесс-функцией. Этот вид тестирования ведет к выбору оппонентов, которые побеждают (решают тесты) большое число особей из конкурирующей популяции.
Далее рассмотрим второй аспект, где представлены различные варианты относительной фитнесс-функции в которых измеряется относительное фитнесс-значение для каждой особи популяции. Предположим, что две популяции $$C_1$$ и $$C_2$$ коэволюционируют и для этого необходимо оценить относительную фитнесс-функцию каждой особи $$C_1\cdot x_i$$ популяции $$C_1$$. Наиболее распространенными являются следующие виды задания относительных фитнесс-функций:
Простая фитнесс-функция, где тестируемые особи берутся из популяции $$C_2$$ и подсчитывается число особей $$C_2$$, для которых $$C_1\cdot x_i$$ является победителем. В этом случае значение относительной фитнесс-функции определяется суммой успешных тестирований для $$C_1\cdot x_i$$.
Раздельная фитнесс-функция, которая определяется с учетом подобия особей популяции $$C_1$$. При этом значение фитнесс-функции особи делится на сумму его подобий с другими особями этой популяции. Подобие можно определить как число особей, которые также побеждают особи из популяции $$C_2$$. Такое определение поощряет необычные особи, непохожие на остальные особи популяции.
Конкурирующая раздельная фитнесс-функция, где значение фитнесс-функции для особи $$C_1\cdot x_i$$ определяется следующим образом $$f(C_1\cdot x_i)=\sum_{i=1}^{C_2\cdot n_i}\frac{1}{C_1\cdot n_i}$$, где $$C_2\cdot x_1,\dots ,C_2\cdot x_{C_2\cdot n_i}$$ определяет тестовую популяцию и $$C_1\cdot n_i$$ -общее число особей в популяции $$C_1$$, которые побеждают особь $$C_2\cdot n_i$$. Эта фитнесс-функция поощряет особи популяции побеждающие особи популяции $$C_2$$, которые не могут "побить" другие особи $$C_1$$. Это не является необходимым в том случае, когда лучшая особь побеждает большую часть особей $$C_2$$.
Турнирная фитнесс-функция использует для ранжирования особей двоичный турнир с уничтожением одной слабой особи. В результате функция дает дерево турниров с лучшей особью в корне. На каждом уровне дерева случайно выбираются два оппонента этого уровня и лучший из них продвигается на следующий уровень. В случае нечетного числа конкурентов единственная имеющаяся особь этого уровня продвигается на следующий уровень. После турнирного ранжирования любой стандартный оператор может быть использован для выбора родителей.
В стандартных ГА элитизм является механизмом, который обеспечивает выживание лучших родительских особей, которые в результате попадают в следующую популяцию. Чтобы выжить в течение многих поколений, особь должна иметь высокие значения фитнесс-функции почти в каждом поколении. Для коэволюции введен механизм "hall of fame" [[8] ("зал славы"), который обобщает элитизм во времени. Здесь в каждом поколении лучшая особь популяции запоминается в этом "зале популярности". Естественно он имеет фиксированный размер, и при пополнении новые лучшие особи вытесняют половину худших старых особей. Особи одной популяции здесь соревнуются с текущей тестовой популяцией и половиной "зала популярности".]
Общий алгоритм А4.1 конкурирующей коэволюции предполагает использование двух популяций. Здесь $$C_1$$ представляет популяцию решений, и $$C_2$$ - тестовую популяцию. Случай с одной популяцией представлен в алгоритме А4.2.
Характеристики коэволюционных алгоритмов можно улучшить если две конкурирующие популяции сильно отличаются друг от друга. Такое разнообразие можно поддерживать путем ввода механизма, который содействует образованию ниш. В этом случае эффективны раздельное тестирование с применением раздельных фитнесс-функций.
4.7.2. Кооперативная коэволюция
Рассмотрим кооперативный ПГА, где значение фитнесс-функции особи зависит от ее способности "сотрудничать" с особями других подпопуляций. Этот подход часто позволяет произвести декомпозицию сложной проблемы на несколько менее сложных задач, каждая из которых решается с помощью ГА. Данный тип ПГА наиболее широко применяется при решении задач многокритериальной оптимизации. Одной из наиболее сложных задач при разработке кооперативной коэволюции является метод определения "премии" (credit assignment) для особи. Основной вопрос - как построить фитнесс-функцию для отдельных особей так, чтобы она учитывала коллективный эффект всех видов.
В некоторых работах [[9] предложен общий подход к эволюции сложных решений путем расщепления на подкомпоненты, которые эволюционируют независимо друг от друга. При этом используется отдельная популяция для эволюции каждой подкомпоненты и соответствующий эволюционный алгоритм. Представления (кодирование) каждой компоненты затем комбинируются для образования сложного решения, которое оценивается с помощью глобальной фитнесс-функции. На ее основе определяются обратные кредитные потоки к каждой компоненте, отражающие как хорошо данный компонент сотрудничает с другими. Эта локальная фитнесс-функция затем используется в подпопуляции для эволюции лучшего решения.]
Данный подход, в частности, применялся для оптимизации функций многих переменных [[10]. При этом для задачи размерности $$n_x$$ используется $$n_x$$ подпопуляций – по одной для каждой координаты. Каждая подпопуляция отвечает за оптимизацию по одному из параметров, но в целом ни одна подпопуляция не может образовать полное решение сама по себе. Сотрудничество достигается путем объединения представлений решений для каждой подпопуляции. Эффективность такого сотрудничества оценивается следующим образом. При рассмотрении $$j$$-ой подпопуляции $$C_j$$ каждая особь $$C_j\cdot x_i$$ "сотрудничает" с лучшей особью их каждой подпопуляции путем объединения этих лучших компонент с $$C_j\cdot x_i$$ в полное решение. В этом случае определение "премии" особи сводится просто к вычислению значения глобальной фитнесс-функции полного решения.]
Экспериментальные исследования показали [[10], что этот подход не дает хорошие результаты в том случае, когда параметры задачи сильно взаимосвязаны вследствие использования жадной эвристики в определении премии особи. Для уменьшения этого эффекта предложено использовать два дополнительных вектора. Первый вектор строится на основе лучших особей каждой подпопуляции, как описано ранее. Второй вектор выбирает случайные особи из других подпопуляций и "склеивает" их с $$C_j\cdot x_i$$. Лучшее значение фитнесс-функции этих двух векторов затем используется в качестве премии (кредита) для $$C_j\cdot x_i$$. Кроме решения задач многомерной оптимизации авторы использовали этот подход при обучении каскадных нейронных сетей[][11] и обучения роботов[][12].]
4.8. Инструментарий распараллеливания
Как отмечалось выше, для реализации ПГА могут быть использованы компьютерные системы с различными архитектурами: SISD, SIMD, MIMD и т.д. Вместо описания многочисленных специальных архитектур и программных конструкций, которые используются при реализации ПГА, далее мы кратко рассмотрим те параллельные и распределенные модели, которые не зависят от конкретных структур. Почти все ПГА реализуются на основе модели каналов для передачи сообщений в коммуникациях, поскольку они позволяют описывать многопроцессорные системы с распределенной памятью, которые являются наиболее удобным и распространенным средством реализации ПГА. В модели передачи сообщений процессы в одном или физически различных процессорах сообщаются между собой путем передачи друг другу сообщений через среду коммуникации, которая представлена стандартом или специальной схемой соединения. Основными элементами здесь являются процедуры отправления и приема сообщений. В простейшей форме, отправление определяет локальный буфер передаваемых данных. Процедура приема обычно определяет процесс отправления и локальный буфер, в котором сохраняются входящие данные. В качестве инструментария чаще всего используются следующие средства: сокет (sockets), параллельная виртуальная машина (parallel virtual machine -PVM), интерфейс передачи сообщений (message passing interface - MPI), Ява (Java), архитектура общего назначения запрос-посредник (common object request broker architecture) - CORBA и Globus, которые обеспечивают большие функциональные возможности, чем простой сервис передачи сообщений.
Контрольные вопросы
Какие свойства ГА способствуют его распараллеливанию?
Опишите модель "рабочий - хозяин".
Каковы функции процессора – хозяина?
Что делает процессор – рабочий?
Какой выигрыш дает модель "рабочий - хозяин"?
Чем отличается модель "рабочий - хозяин" от "модели островов"?
Какие факторы влияют на миграцию в "модели островов"?
Какие вы знаете виды распределенных ГА?
Опишите клеточные ГА.
Что такое виртуальные острова?
Что такое коэволюционные ГА?
Приведите различные варианты реализации параллельных ГА.
Какой инструментарий можно использовать при реализации ГА?
Опишите возможный вариант иерархического ГА.
Краткие итоги:
изложены основы параллельных ГА, их структура и параметры;
представлен глобальный параллельный ГА на основе модели "рабочий-хозяин Ю.А.";
описан распределенный ГА на базе "модели островов";
рассмотрен клеточный ГА, его структура и параметры;
представлены коэволюционные ГА на основе двух моделей - "кооперативная эволюция" и "конкурирующая эволюция".
