Алгоритм клеточной эволюции
Клеточный эволюционный алгоритм ( КЭА ) — это разновидность эволюционного алгоритма (ЭА), в котором особи не могут спариваться произвольно, но каждая взаимодействует со своими более близкими соседями, к которым применяется базовый ЭА (отбор, вариация, замена).
Клеточная модель моделирует естественную эволюцию с точки зренияиндивидуум, который кодирует предварительное (оптимизация, обучение, поиск) решение проблемы. Основная идея этой модели состоит в том, чтобы предоставить популяции EAсо специальной структурой, определяемой как связный граф, в котором каждая вершина представляет собой индивидуальность, общающуюся со своимиближайшие соседи. В частности, индивиды концептуально помещены в тороидальную систему.сети, и им разрешено воссоединяться только с близкими людьми. Это приводит наск своего рода локальности, известной как изоляция расстоянием . Набор потенциальных партнеровиндивида называется его окрестностью . Известно, что в этом родеалгоритма, похожие люди склонны группироваться, создавая ниши, и эти группыдействуют так, как если бы они были отдельными субпопуляциями (островами). Во всяком случае, нетчеткая граница между соседними группами и тесные ниши могут быть легкоколонизированы конкурентными нишами и, возможно, объединяют содержимое решений в процессе. Одновременно,дальние ниши могут быть затронуты медленнее.
Введение [ править ]
Клеточный эволюционный алгоритм (cEA) обычно создает структурированную двумерную структуру.сетка индивидуумов, хотя возможны и другие топологии. В этой сетке в ходе эволюции естественным образом создаются скопления сходных особей, способствующие освоению их границ, тогда как эксплуатация осуществляется преимущественно путем прямой конкуренции и слияния внутри них.
Сетка обычно представляет собой двумерную тороидальную структуру, хотяколичество измерений можно легко увеличить (до 3D) или уменьшить (до 1D, например, кольцо).Окрестность конкретной точки сетки (где находится индивидуум)размещен) определяется с точки зрения расстояния Манхэттена от него до других членов населения. Каждая точка сетки имеет окрестность, которая перекрывает окрестности соседних индивидуумов. В базовом алгоритме все окрестности имеют одинаковый размер и одинаковую форму. дванаиболее часто используемые районы — L5, также называемые Фон Нейман или НОВОСТИ (Север, Восток, Запад и Юг) и C9, также известный как Мура район . Здесь L означает Linear , а C означает Compact .
В СЕА особи могут взаимодействовать только со своими соседями в репродуктивном плане.цикл, в котором применяются операторы вариации. Это репродуктивноецикл выполняется внутри окрестности каждого индивидуума и, как правило,состоит в выборе двух родителей среди своих соседей по определенномукритерием, применяя к ним операторы вариации (рекомбинации и мутациинапример), и замену рассматриваемого индивидуума на недавносозданный потомок по заданному критерию, например, заменить, если потомокпредставляет собой лучшее решение, чем рассматриваемый индивидуум.
Синхронный и асинхронный [ править ]
В обычном синхронном CEA алгоритм переходит от самого первого верхнего левого индивидуума вправо, а затем к нескольким строкам, используя информацию из популяции для создания новой временной популяции. После завершения работы с последней особью в правом нижнем углу временная популяция заполняется вновь вычисленными особями, и начинается этап замены. В нем старая популяция полностью и синхронно заменяется вновь рассчитанной по некоторому критерию. Обычно замена удерживает лучшую особь на одном и том же положении в обеих популяциях, то есть используется элитарность.
Мы должны отметить, что в соответствии с используемой политикой обновления совокупности мы также можем определить асинхронный CEA. Это также хорошо известная проблема клеточных автоматов . В асинхронных CEA порядок обновления отдельных лиц в сетке меняется в зависимости от используемого критерия: сканирование строки, фиксированное случайное сканирование, новое случайное сканирование и единый выбор. Это четыре наиболее распространенных способа обновления населения. Все они продолжают немедленно использовать вновь вычисленную единицу (или оригинал, если лучше) для вычислений его соседей. Это заставляет популяцию в любой момент времени удерживать особей на разных стадиях эволюции, определяя очень интересное новое направление исследований.
Перекрытие окрестностей обеспечивает неявный механизм миграции решений.в ЦЭА. Поскольку лучшие решения плавно распространяются повсей популяции, генетическое разнообразие в популяции сохраняется дольше, чемв неструктурированных советниках. Это мягкое рассеивание лучших решений черезнаселение является одним из основных вопросов хорошего компромисса между разведкой и эксплуатация , которую CEA осуществляют во время поиска. Тогда легко увидетьчто мы могли бы настроить этот компромисс (и, следовательно, настроить уровень генетического разнообразия в соответствии сэволюцию) путем изменения (например) размера используемой окрестности, какстепень перекрытия между окрестностями растет в зависимости от размераокрестности.
СЕА можно рассматривать как клеточный автомат (КА) с вероятностнымперезаписываемые правила, где алфавит CA эквивалентен потенциальномуколичество решений задачи. Следовательно, если мы рассматриваем СЕА как разновидность СА,можно импортировать знания из области CA в CEA, и по сути это интересное открытое направление исследований.
Параллелизм [ править ]
Сотовые ЭА очень хорошо поддаются параллелизму, поэтому его обычно можно встретить в литературе по параллельной метаэвристике . В частности, мелкозернистый параллелизм может использоваться для назначения независимых потоков выполнения каждому человеку, что позволяет всему CEA работать на параллельной или фактически параллельной аппаратной платформе. Таким образом, можно добиться значительного сокращения времени при запуске CEA на FPGA или GPU .
Однако важно подчеркнуть, что CEA представляют собой модель поиска, во многих смыслах отличающуюся от традиционных EA. Кроме того, их можно запускать на последовательных и параллельных платформах, что подтверждает тот факт, что модель и реализация — это две разные концепции.
вы найдете Здесь полное описание основ понимания, разработки и применения СЕА.
См. также [ править ]
- Клеточный автомат
- Двухфазная эволюция
- Энрике Альба
- Эволюционный алгоритм
- Метаэвристический
- Параллельная метаэвристика
Ссылки [ править ]
- Э. Альба, Б. Дорронсоро, Клеточные генетические алгоритмы , Springer-Verlag, ISBN 978-0-387-77609-5 , 2008 г.
- А. Дж. Сосед, Дж. Дж. Дурилло, Ф. Луна, Б. Дорронсоро, Э. Альба, MOCell: новый клеточный генетический алгоритм для многокритериальной оптимизации, Международный журнал интеллектуальных систем, 24: 726-746, 2009 г.
- Э. Альба, Б. Дорронсоро, Ф. Луна, А. Дж. Нейбор, П. Буври, Л. Хоги, Клеточный многоцелевой генетический алгоритм для оптимальной стратегии вещания в городских сетях MANET , Компьютерные коммуникации, 30 (4): 685-697, 2007 год
- Э. Альба, Б. Дорронсоро, Вычисление девяти новых лучших на данный момент решений для емкостного VRP с сотовым ГА , Письма по обработке информации, Elsevier, 98(6):225-230, 30 июня 2006 г.
- М. Джакобини, М. Томассини, А. Теттаманци, Э. Альба, Интенсивность отбора в клеточных эволюционных алгоритмах для регулярных решеток , Транзакции IEEE на эволюционных вычислениях, IEEE Press, 9 (5): 489-505, 2005 г.
- Э. Альба, Б. Дорронсоро, Компромисс исследования/эксплуатации в динамических клеточных генетических алгоритмах , Транзакции IEEE на эволюционных вычислениях, IEEE Press, 9(2)126-142, 2005 г.