Алгоритм клеточной эволюции
Клеточный эволюционный алгоритм ( КЭА ) — это разновидность эволюционного алгоритма (ЭА), в котором особи не могут спариваться произвольно, но каждая взаимодействует со своими более близкими соседями, к которым применяется базовый ЭА (отбор, вариация, замена).
Клеточная модель моделирует естественную эволюцию с точки зрения индивидуум, который кодирует предварительное (оптимизация, обучение, поиск) решение проблемы. Основная идея этой модели состоит в том, чтобы предоставить популяции 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 г.