Алгоритм клеточной эволюции - Википедия - Cellular evolutionary algorithm

А клеточный эволюционный алгоритм (cEA) является своего рода эволюционный алгоритм (EA), в котором особи не могут произвольно спариваться, но каждый из них взаимодействует со своими ближайшими соседями, к которым применяется базовый EA (выбор, изменение, замена).

Пример эволюции КЭА в зависимости от формы популяции от квадрата (слева) до одномерного кольца (справа). Более темные цвета означают лучшие решения. Обратите внимание на то, как формы, отличные от традиционного квадрата, сохраняют разнообразие (более высокое исследование) в течение более длительного времени. Четыре снимка КЭА ​​поколений 0-50-100-150.

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

Вступление

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

Примеры моделей окрестностей в клеточных советниках: линейные, компактные, ромбовидные и ... любые другие!

Сетка обычно представляет собой двумерную тороидальную структуру, хотя количество измерений может быть легко расширено (до трехмерного) или уменьшено (до одномерного, например, кольца). Окрестность конкретной точки сетки (где помещается индивидуум) определяется в терминах из Манхэттен расстояние от него до других в населении. Каждая точка сетки имеет окрестности, которые перекрывают окрестности ближайших людей. В базовом алгоритме все окрестности имеют одинаковый размер и одинаковые формы. Двумя наиболее часто используемыми районами являются L5, также называемыеФон Нейман или NEWS (север, восток, запад и юг) и C9, также известный как Мур район. Здесь, L означает Линейный пока C означает Компактный.

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

Синхронный против асинхронного

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

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

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

Перекрытие окрестностей обеспечивает неявный механизм миграции решения в cEA. Поскольку лучшие решения беспрепятственно распространяются по всей популяции, генетическое разнообразие в популяции сохраняется дольше, чем в неструктурированных советниках. Такое мягкое распространение лучших решений среди населения - одна из главных проблем хорошего компромисса между исследованиеи эксплуатация что КЭА выполняют во время поиска. Тогда легко увидеть, что мы могли настройте этот компромисс (и, следовательно, настраивать уровень генетического разнообразия в процессе эволюции), изменяя (например) размер используемого района, поскольку степень перекрытия между районами растет в соответствии с размером района.

CEA можно рассматривать как клеточный автомат (CA) с вероятностно повторяемыми правилами, где алфавит CA эквивалентен потенциальному количеству решений проблемы. Следовательно, если мы рассматриваем cEAs как своего рода CA, можно импортировать знания из области CA в cEA, и на самом деле это интересное открытое направление исследований.

Параллелизм

Сотовые советники очень подвержены параллелизму, поэтому обычно можно найти в литературе параллельная метаэвристика. В частности, мелкозернистый параллелизм может использоваться для назначения независимых потоков выполнения каждому индивиду, что позволяет всему cEA работать на параллельной или фактически параллельной аппаратной платформе. Таким образом можно добиться значительного сокращения времени при запуске cEA на ПЛИС или же GPU.

Однако важно подчеркнуть, что cEA - это модель поиска, во многих смыслах отличная от традиционных EAs. Кроме того, их можно запускать на последовательных и параллельных платформах, что подтверждает тот факт, что модель и реализация - это две разные концепции.

Видеть здесь для полного описания основ понимания, разработки и применения CEA.

Смотрите также

Рекомендации

внешняя ссылка