Клеточный эволюционный алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

• Клеточный автомат
• Двухфазная эволюция
• Энрике Альба
• Эволюционный алгоритм
• Метаэвристический
• Параллельный метаэвристический

• Э. Альба, Б. Дорронсоро, Клеточные генетические алгоритмы, Springer-Verlag, ISBN  978-0-387-77609-5 , 2008 г.
• AJ Neighbor, JJ Durillo, F. Luna, B. Dorronsoro, E. Alba, MOCell: новый клеточный генетический алгоритм для многоцелевой оптимизации, Международный журнал интеллектуальных систем, 24:726-746, 2009
• E. Alba, B. Dorronsoro, F. Luna, AJ Neighbor, P. Bouvry, L. Hogie, Клеточный многоцелевой генетический алгоритм для оптимальной стратегии вещания в городских сетях MANET, Computer Communications, 30(4):685-697, 2007
• Э. Альба, Б. Дорронсоро, Вычисление девяти новых лучших на сегодняшний день решений для VRP с емкостью с использованием сотового GA, Information Processing Letters, Elsevier, 98(6):225-230, 30 июня 2006 г.
• М. Джакобини, М. Томассини, А. Теттаманци, Э. Альба, Интенсивность отбора в клеточных эволюционных алгоритмах для регулярных решеток, Труды IEEE по эволюционным вычислениям, IEEE Press, 9(5):489-505, 2005
• Э. Альба, Б. Дорронсоро, Компромисс между исследованием и эксплуатацией в динамических клеточных генетических алгоритмах, Труды IEEE по эволюционным вычислениям, IEEE Press, 9(2)126-142, 2005

• Сайт по клеточным эволюционным алгоритмам
• Исследовательская группа NEO в Университете Малаги, Испания. Архивировано 28 сентября 2018 г. на Wayback Machine