✖


Jump to content

Популяционная модель (эволюционный алгоритм)

    Add links

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

    Самой простой и широко используемой популяционной моделью в ЭА является глобальная или панмиктическая модель , которая соответствует неструктурированной популяции. [1] [2] Это позволяет каждой особи выбирать любую другую особь популяции в качестве партнера для производства потомства путем скрещивания , при этом детали отбора не имеют значения, пока значительную роль играет приспособленность особей. Благодаря глобальному отбору партнеров генетическая информация даже немного лучших особей может преобладать в популяции через несколько поколений ( итерация ЭА), при условии, что на этой фазе не появится другое лучшее потомство. Если найденное таким образом решение не является искомым оптимумом , это называется преждевременной сходимостью . [3] Этот эффект чаще можно наблюдать в панмиктических популяциях. [4]

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

    Поэтому очевидно разделение ранее глобальной популяции по подструктурам. С этой целью были введены две основные модели: островные модели , которые основаны на разделении популяции на фиксированные субпопуляции, которые время от времени обмениваются особями, [1] [5] и модели соседства , которые распределяют людей по перекрывающимся районам, [4] [6] также известные как клеточные генетические или эволюционные алгоритмы (cGA или cEA). [7] [8] Связанное с этим разделение населения также предполагает соответствующее распараллеливание процедуры. По этой причине тема популяционных моделей также часто обсуждается в литературе в связи с распараллеливанием ЭА. [1] [2] [4] [5] [9] [10]

    Островные модели

    [ редактировать ]
    Пример островной модели, состоящей из восьми островов и двух соседских структур: простого однонаправленного кольца (черные стрелки) и более сложной структуры (зеленые и черные стрелки)

    В островной модели, также называемой моделью миграции или крупнозернистой моделью , эволюция происходит в строго разделенных субпопуляциях. Их можно организовать панмиктически, но это не обязательно. Время от времени происходит обмен особями, который называется миграцией . [2] [5] Время между обменом называется эпохой , и его окончание может быть вызвано различными критериями: например, после определенного времени или заданного количества завершенных поколений, или после наступления застоя. Стагнацию можно обнаружить, например, по тому факту, что на острове не произошло никакого улучшения приспособленности на протяжении определенного числа поколений. Островные модели вводят множество новых параметров стратегии: [11] [12] [13] [14]

    • Количество субпопуляций
    • Размер субпопуляций
    • Отношения соседства между островами: они определяют, какие острова считаются соседними и, таким образом, могут обмениваться людьми, см. изображение простого однонаправленного кольца (черные стрелки) и его расширение за счет дополнительных двунаправленных отношений соседства (дополнительные зеленые стрелки).
    • Критерии окончания эпохи, синхронная или асинхронная миграция
    • Уровень миграции: количество или доля лиц, вовлеченных в миграцию.
    • Отбор мигрантов. Для этого существует множество альтернатив. Например, лучшие люди могут заменить худших или случайно выбранных. В зависимости от уровня миграции это может затронуть одного или нескольких человек одновременно.

    С помощью этих параметров можно в значительной степени влиять на давление отбора. Например, он увеличивается с увеличением взаимосвязанности островов и уменьшается с увеличением количества субпопуляций или продолжительности эпохи.

    Модели соседства или алгоритмы клеточной эволюции

    [ редактировать ]
    Структура тора (справа) с двумя примерными двумерными фигурами окрестностей (слева). Демы в форме блоков индивидуумов A и B имеют двух общих соседей, показанных желтым цветом.

    Модель соседства, также называемая диффузионной моделью или мелкозернистой моделью , определяет топологические отношения соседства между особями популяции, которые не зависят от их фенотипических свойств. Фундаментальная идея этой модели состоит в том, чтобы предоставить популяции EA специальную структуру, определяемую как связный граф, в котором каждая вершина является индивидуумом, который взаимодействует со своими ближайшими соседями. [2] [6] В частности, люди концептуально помещены в тороидальную сетку, и им разрешено рекомбинировать только с близкими людьми. Это приводит к своего рода локальности, известной как изоляция расстоянием . [6] [7] Совокупность потенциальных партнеров индивидуума называется его соседством или демой . Соседний рисунок иллюстрирует это, показывая два слегка перекрывающихся района проживания двух особей, отмеченных желтым, через которые генетическая информация может распространяться между двумя демами. Известно, что в такого рода алгоритме схожие особи имеют тенденцию группироваться и создавать ниши , независимые от границ демы и, в частности, могут быть больше демы. [6] [7] Четкой границы между соседними группами нет, а близкие ниши могут быть легко колонизированы конкурентами и, возможно, в ходе этого процесса объединять содержание решений. В то же время дальние ниши могут быть затронуты медленнее. [6] [7] ЭА с таким типом популяции также известны как клеточные ЭА (cEA). [8] [15] или клеточные генетические алгоритмы (cGA). [7] [16]

    Примеры окрестностей, называемых также демами, в двумерных сотовых советниках: линейные, компактные, ромбические и... любые другие.
    Два примера перекрывающихся окрестностей (демов) одномерной кольцеобразной модели окрестностей советника. Два дема индивидуумов X и Y перекрываются минимально, тогда как демы A и B перекрываются максимально.

    Обычно используемой структурой для размещения особей популяции является двумерная тороидальная сетка. [1] [2] [15] хотя количество измерений можно легко расширить (до 3D) или уменьшить (до 1D, например кольцо, [6] [15] см. рисунок справа). Соседство конкретного человека в сетке определяется с точки зрения Манхэттенского расстояния от него до других членов популяции. В базовом алгоритме все окрестности имеют одинаковый размер и одинаковую форму. Два наиболее часто используемых района для двумерных CEA — это L5 и C9, см. рисунок слева. Здесь L означает Linear , а C означает Compact . Каждая дема представляет собой панмиктическую субпопуляцию, внутри которой выбор партнера и принятие потомства происходит путем замены родителя. Правила принятия потомства носят локальный характер и основаны на соседстве: например, можно указать, что лучший потомок должен быть лучше, чем заменяемый родитель, или, менее строго, только лучше, чем худший экземпляр в деме. . [2] [6] Первое правило является элитарным и создает более высокое избирательное давление , чем второе неэлитарное правило. В элитарных ЭА всегда выживает лучший экземпляр популяции. В этом отношении они отклоняются от биологической модели.

    Перекрытие окрестностей вызывает в основном медленное распространение генетической информации через границы окрестностей, отсюда и название модели диффузии . Лучшему потомству теперь требуется больше поколений, чем в панмиксии, чтобы распространиться среди населения. Это способствует возникновению локальных ниш и их локальной эволюции, сохраняя таким образом генотипическое разнообразие в течение более длительного периода времени. Результатом является лучший и динамичный баланс между поиском по ширине и глубине, адаптированный к пространству поиска во время прогона. Поиск в глубину происходит в нишах, а поиск в ширину — в границах ниш и посредством эволюции различных ниш всей популяции. [17] При одинаковом размере окрестности разброс генетической информации больше для вытянутых фигур типа L9, чем для блока типа C9, и снова значительно больше, чем для кольца. [18] Это означает, что кольцевые окрестности хорошо подходят для достижения высококачественных результатов, даже если это требует сравнительно длительного времени выполнения. С другой стороны, если вас в первую очередь интересуют быстрые и хорошие, но, возможно, неоптимальные результаты, более подходящими являются 2D-топологии.

    Сравнение

    [ редактировать ]

    При применении обеих популяционных моделей к генетическим алгоритмам [5] [6] эволюционная стратегия [18] [19] и другие советники, [20] [21] разделение всей популяции на субпопуляции обычно снижает риск преждевременной конвергенции и приводит к лучшим результатам в целом, более надежно и быстрее, чем можно было бы ожидать от панмиктических ЭА.

    Островные модели имеют тот недостаток по сравнению с моделями соседства, что они вводят большое количество новых параметров стратегии. Несмотря на существующие исследования по этой теме в литературе, [11] [22] [23] для пользователя сохраняется определенный риск неблагоприятных настроек. С другой стороны, для моделей окрестности необходимо указать только размер окрестности, а в случае двумерной модели добавляется выбор фигуры окрестности.

    Параллелизм

    [ редактировать ]

    Поскольку обе модели населения подразумевают разделение населения, они хорошо подходят в качестве основы для распараллеливания советника. [5] [10] [24] В еще большей степени это относится к сотовым советникам, поскольку они полагаются только на локально доступную информацию о членах своих соответствующих демов. Таким образом, в крайнем случае каждому отдельному человеку может быть назначен независимый поток выполнения, чтобы весь CEA мог работать на параллельной аппаратной платформе. [6] [25] [26] Островная модель также поддерживает распараллеливание, например, путем назначения процессора каждому острову. Если субпопуляции островов организованы панмиктически, все оценки потомков поколения могут быть распараллелены дополнительно. [9] [14] [27] В реальных приложениях оценки обычно являются самой трудоемкой частью. Конечно, также возможно спроектировать островные субпопуляции как CEA, чтобы применимы сделанные ранее утверждения о распараллеливании CEA. Таким образом могут быть созданы иерархические структуры совокупности с соответствующими распараллеливаниями. [9] не только сравнительно дорогие компьютерные кластеры, но и недорогие видеокарты ( GPU ). Для распараллеливания можно использовать [28] [29]

    Однако важно подчеркнуть, что СЕА, или СУ с населением, распределенным по островам, представляют собой модель поиска, которая во многом отличается от традиционных СУ. Более того, они могут работать как на последовательных, так и на параллельных платформах, что подчеркивает тот факт, что модель и реализация — это две разные концепции.

    Библиография

    [ редактировать ]
    • Эрик Канту-Пас (2001): «Эффективные и точные параллельные генетические алгоритмы» (докторская диссертация, Университет Иллинойса, Урбана-Шампейн, США). Спрингер, Нью-Йорк, штат Нью-Йорк. ISBN   978-1-4613-6964-6 дои : 10.1007/978-1-4615-4369-5
    • Мартина Горж-Шлейтер (1990): Генетические алгоритмы и популяционные структуры - массово-параллельный алгоритм. Кандидатская диссертация, Дортмундский университет, факультет компьютерных наук, Германия.
    • Энрике Альба, Бернабе Дорронсоро (2008): Клеточные генетические алгоритмы . Спрингер, Нью-Йорк, штат Нью-Йорк. ISBN   978-0-387-77609-5 дои : 10.1007/978-0-387-77610-1
    • Дирк Судхолт (2015): Параллельные эволюционные алгоритмы . Януш Качпшик, Витольд Педрич (ред.): Параллельные эволюционные алгоритмы. Springer, Берлин, Гейдельберг, стр. 929–959. ISBN   978-3-662-43504-5 дои : 10.1007/978-3-662-43505-2 46
    • Габриэль Луке, Энрике Альба (2011): Параллельные генетические алгоритмы . Шпрингер, Берлин Гейдельберг. ISBN   978-3-642-22083-8 дои : 10.1007/978-3-642-22084-5

    См. также

    [ редактировать ]

    Ссылки

    [ редактировать ]
    1. ^ Jump up to: а б с д Канту-Пас, Эрик (1998). «Обзор параллельных генетических алгоритмов» (PDF) . Калькуляторы Параллели . 10 (2): 141–171.
    2. ^ Jump up to: а б с д и ж Гордон, В.С.; Уитли, Д. (1993), Форрест, С. (ред.), «Последовательные и параллельные генетические алгоритмы как оптимизаторы функций» (PDF) , Материалы Пятой международной конференции по генетическим алгоритмам , Сан-Матео, Калифорния: Морган Кауфманн, стр. 177–183, ISBN .  978-1-55860-299-1
    3. ^ Люнг, Йи; Гао, Юн; Сюй, Цзун-Бен (1997). «Степень разнообразия населения - взгляд на преждевременную конвергенцию генетических алгоритмов и анализ цепей Маркова» . Транзакции IEEE в нейронных сетях . 8 (5): 1165–1176. дои : 10.1109/72.623217 . ISSN   1045-9227 . ПМИД   18255718 .
    4. ^ Jump up to: а б с Горж-Шлейтер, Мартина (1990). Генетические алгоритмы и популяционные структуры - алгоритм массового параллелизма (доктор философии). Дортмундский университет, факультет компьютерных наук, Германия.
    5. ^ Jump up to: а б с д и Канту-Пас, Эрик (1999). «Эффективные и точные параллельные генетические алгоритмы» (докторская диссертация, Университет Иллинойса, Урбана-Шампейн, США). Генетические алгоритмы и эволюционные вычисления. Том. 1. Спрингер, Нью-Йорк, штат Нью-Йорк. дои : 10.1007/978-1-4615-4369-5 . ISBN  978-1-4613-6964-6 .
    6. ^ Jump up to: а б с д и ж г час я Горж-Шлейтер, Мартина (1991), Швефель, Ханс-Пауль; Мэннер, Рейнхард (ред.), «Явный параллелизм генетических алгоритмов через популяционные структуры» , «Параллельное решение проблем из природы », Конспект лекций по информатике, том. 496, Берлин/Гейдельберг: Springer-Verlag, стр. 150–159, doi : 10.1007/bfb0029746 , ISBN.  978-3-540-54148-6 , получено 15 декабря 2022 г.
    7. ^ Jump up to: а б с д и Гордон, В. Скотт; Матиас, Кейт; Уитли, Даррелл (1994). «Клеточные генетические алгоритмы как оптимизаторы функций» . Материалы симпозиума ACM 1994 года по прикладным вычислениям - SAC '94 . Финикс, Аризона, США: ACM Press. стр. 237–241. дои : 10.1145/326619.326732 . ISBN  978-0-89791-647-9 . S2CID   6418773 .
    8. ^ Jump up to: а б Джакобини, М.; Томассини, М.; Теттаманзи, AGB; Альба, Э. (октябрь 2005 г.). «Интенсивность отбора в клеточных эволюционных алгоритмах для регулярных решеток» . Транзакции IEEE в эволюционных вычислениях . 9 (5): 489–505. дои : 10.1109/TEVC.2005.850298 . ISSN   1089-778X . S2CID   3184685 .
    9. ^ Jump up to: а б с Халлуф, Хатем; Мохаммед, Мохаммед; Шахуд, Шади; Дюпмайер, Клеменс; Хагенмейер, Фейт (2 ноября 2020 г.). «Общая гибкая и масштабируемая структура для иерархической распараллеливания метаэвристики на основе совокупности» . Материалы 12-й Международной конференции по управлению цифровыми экосистемами . Виртуальное мероприятие Объединенные Арабские Эмираты: ACM. стр. 124–131. дои : 10.1145/3415958.3433041 . ISBN  978-1-4503-8115-4 . S2CID   227179748 .
    10. ^ Jump up to: а б Судхолт, Дирк (2015), Качпшик, Януш; Педрич, Витольд (ред.), «Параллельные эволюционные алгоритмы» (PDF) , Springer Handbook of Computational Intelligence , Берлин, Гейдельберг: Springer, стр. 929–959, doi : 10.1007/978-3-662-43505-2_46 , ISBN  978-3-662-43504-5 , получено 13 февраля 2023 г.
    11. ^ Jump up to: а б Канту-Пас, Эрик (1999), «Топологии, темпы миграции и параллельные генетические алгоритмы для нескольких популяций» , Proc. 1-й ежегодной конференции. по генетическим и эволюционным вычислениям (GECCO) , стр. 91–98.
    12. ^ Белкади, К.; Гурганд, М.; Бенетту, М. (08 ноября 2006 г.). «Параллельные генетические алгоритмы с миграцией для задачи планирования гибридного потока» . Журнал прикладной математики и наук о принятии решений . 2006 : 1–17. дои : 10.1155/JAMDS/2006/65746 . ISSN   1173-9126 .
    13. ^ Абдельхафез, Амр; Альба, Энрике; Люке, Габриэль (сентябрь 2019 г.). «Анализ производительности синхронных и асинхронных распределенных генетических алгоритмов на мультипроцессорах» . Рой и эволюционные вычисления . 49 : 147–157. doi : 10.1016/j.swevo.2019.06.003 . S2CID   196193164 .
    14. ^ Jump up to: а б Адар, Н.; Куват, Г. (2016). «Параллельные генетические алгоритмы с динамической топологией с использованием кластерных вычислений» . Достижения в области электротехники и вычислительной техники . 16 (3): 73–80. дои : 10.4316/AECE.2016.03011 . ISSN   1582-7445 .
    15. ^ Jump up to: а б с Альба, Энрике; Троя, Хосе Ма (2000), Шенауэр, Марк; Деб, Калянмой; Рудольф, Гюнтер; Яо, Синь (ред.), «Клеточные эволюционные алгоритмы: оценка влияния соотношения» , «Параллельное решение проблем из природы» PPSN VI , том. 1917, Берлин, Гейдельберг: Springer, стр. 29–38, doi : 10.1007/3-540-45356-3_3 , ISBN.  978-3-540-41056-0 , получено 11 февраля 2023 г.
    16. ^ Фолино, Г.; Пиццути, К.; Спеццано, Г. (1998). «Сочетание клеточных генетических алгоритмов и локального поиска для решения задач выполнимости» . Материалы десятой международной конференции IEEE по инструментам с искусственным интеллектом (кат. № 98CH36294) . Тайбэй, Тайвань: IEEE. стр. 192–198. дои : 10.1109/TAI.1998.744842 . ISBN  978-0-7803-5214-8 . S2CID   8048158 .
    17. ^ Дон, Генри; Дорронсоро, Варнава (2008). Клеточные генетические алгоритмы . Нью-Йорк: Спрингер. п. 12. ISBN  978-0-387-77610-1 . OCLC   370728730 .
    18. ^ Jump up to: а б Горж-Шлейтер, Мартина (1998), Эйбен, Агостон Э.; Назад, Томас; Шенауэр, Марк; Сульфур, Ханс-Пол (ред.), «Сравнительное исследование глобального и локального отбора в стратегиях эволюции» , «Параллельное решение проблем из природы» - PPSN V , Конспект лекций по информатике, том. 1498, Берлин, Гейдельберг: Springer, стр. 367–377, doi : 10.1007/bfb0056879 , ISBN.  978-3-540-65078-2 , получено 11 февраля 2023 г.
    19. ^ Справе, Иоахим (1994), «Стратегия линейной эволюции соседства» (PDF) , Материалы 3-й ежегодной конференции по эволюционному программированию , Сингапур: World Scientific, стр. 42–51 , получено 5 ноября 2022 г.
    20. ^ Якоб, Вильфрид (01 сентября 2010 г.). «Общая структура адаптации мультимемных алгоритмов, основанная на затратах и ​​выгодах» . Меметические вычисления . 2 (3). п. 207: 201–218. дои : 10.1007/s12293-010-0040-9 . ISSN   1865-9292 . S2CID   167807 .
    21. ^ Альба, Энрике; Дорронсоро, Бернабе; Альфонсо, Хьюго (2005). «Клеточные меметические алгоритмы» . Журнал компьютерных наук и технологий . 5 (4): 257–263 . Проверено 4 ноября 2022 г.
    22. ^ Вэнь-Ян Линь; Цунг-Пей Хонг; Шу-Мин Лю (2004). «Об адаптации параметров миграции для многопопуляционных генетических алгоритмов» . 2004 Международная конференция IEEE по системам, человеку и кибернетике (номер по каталогу IEEE 04CH37583) . Том. 6. Гаага, Нидерланды: IEEE. стр. 5731–5735. дои : 10.1109/ICSMC.2004.1401108 . ISBN  978-0-7803-8567-2 . S2CID   31844333 .
    23. ^ Хонг, Цунг-Пей; Линь, Вэнь-Ян; Лю, Шу-Мин; Лин, Цзянн-Хорнг (20 апреля 2007 г.). «Динамическая корректировка темпов миграции для многопопуляционных генетических алгоритмов» . Журнал передового вычислительного интеллекта и интеллектуальной информатики . 11 (4): 410–415. дои : 10.20965/jaciii.2007.p0410 . ISSN   1883-8014 .
    24. ^ Люке, Габриэль; Альба, Энрике (2011). Параллельные генетические алгоритмы . Исследования в области вычислительного интеллекта. Том. 367. Берлин, Гейдельберг: Шпрингер. дои : 10.1007/978-3-642-22084-5 . ISBN  978-3-642-22083-8 .
    25. ^ Люке, Габриэль; Альба, Энрике; Дорронсоро, Бернабе (июль 2009 г.). «Асинхронная параллельная реализация клеточного генетического алгоритма комбинаторной оптимизации» . Материалы 11-й ежегодной конференции по генетическим и эволюционным вычислениям . Монреаль, Квебек, Канада: ACM. стр. 1395–1402. дои : 10.1145/1569901.1570088 . ISBN  978-1-60558-325-9 . S2CID   14113702 .
    26. ^ Чжунвэнь Ло; Хунчжи Лю (2006). «Клеточно-генетические алгоритмы и локальный поиск проблемы 3-SAT на графическом оборудовании» . 2006 Международная конференция IEEE по эволюционным вычислениям . Ванкувер, Британская Колумбия, Канада: IEEE. стр. 2988–2992. дои : 10.1109/CEC.2006.1688685 . ISBN  978-0-7803-9487-2 . S2CID   8142372 .
    27. ^ Каон, С.; Мелаб, Н.; Тальби, Э.-Г. (май 2004 г.). «ParadisEO: основа для многократного проектирования параллельных и распределенных метаэвристик» . Журнал эвристики . 10 (3): 357–380. doi : 10.1023/B:HEUR.0000026900.92269.ec . ISSN   1381-1231 . S2CID   14972999 .
    28. ^ Йене, Пауль (2016). Майр, Генрих Кристиан; Пинцгер, Мартин (ред.). Обзор текущего состояния исследований по распараллеливанию эволюционных алгоритмов на графических картах (PDF) . Бонн: Общество информатики, ФРГ. ISBN  978-3-88579-653-4 . OCLC   962381748 . {{cite book}}: |work= игнорируется ( помогите )
    29. ^ Гарсиа-Кальво, Рауль; Гисадо, младший; Диас-дель-Рио, Фернандо; Кордова, Антонио; Хименес-Моралес, Франциско (январь 2018 г.). «Усовершенствованные генетические алгоритмы графического процессора для решения временной динамики сетей регуляции генов» . Эволюционная биоинформатика . 14 . дои : 10.1177/1176934318767889 . ISSN   1176-9343 . ПМК   5898668 . ПМИД   29662297 .
    Retrieved from "https://en.wikipedia.org/w/index.php?title=Population_model_(evolutionary_algorithm)&oldid=1184011552"
    Arc.Ask3.Ru: конец переведенного документа.
    Arc.Ask3.Ru
    Номер скриншота №: f3405c7eeae83fd6234ad2bc62b31d09__1699378140
    URL1:https://arc.ask3.ru/arc/aa/f3/09/f3405c7eeae83fd6234ad2bc62b31d09.html
    Заголовок, (Title) документа по адресу, URL1:
    Population model (evolutionary algorithm) - Wikipedia
    Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)