Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Введение [ править ]

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

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

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

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

Синхронный и асинхронный [ править ]

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

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

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

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

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

Параллелизм [ править ]

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

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

См. Здесь полное описание основ понимания, разработки и применения cEA.

См. Также [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]