stringtranslate.com

Конструктивная кооперативная коэволюция

Конструктивный кооперативный коэволюционный алгоритм (также называемый C 3 ) — это глобальный алгоритм оптимизации в искусственном интеллекте, основанный на архитектуре многостартового жадного рандомизированного адаптивного поиска (GRASP). [1] [2] Он включает в себя существующий кооперативный коэволюционный алгоритм (CC). [3] Рассматриваемая задача разлагается на подзадачи. Эти подзадачи оптимизируются отдельно при обмене информацией для решения полной задачи. Алгоритм оптимизации, обычно, но не обязательно, эволюционный алгоритм , встроен в C 3 для оптимизации этих подзадач. Природа встроенного алгоритма оптимизации определяет, является ли поведение C 3 детерминированным или стохастическим .

Алгоритм оптимизации C 3 изначально был разработан для оптимизации на основе моделирования [4] [5], но его можно использовать для глобальных задач оптимизации в целом. [6] Его преимущество перед другими алгоритмами оптимизации, в частности, кооперативной коэволюцией, заключается в том, что он лучше справляется с неразделимыми задачами оптимизации. [4] [7]

Позже была предложена улучшенная версия, названная Improved Constructive Cooperative Coevolutionary Differential Evolution (C 3i DE), которая устраняет несколько ограничений предыдущей версии. Новым элементом C 3i DE является расширенная инициализация субпопуляций. C 3i DE изначально оптимизирует субпопуляции частично коадаптивным образом. Во время начальной оптимизации субпопуляции для коадаптации рассматривается только подмножество других субкомпонентов. Это подмножество увеличивается пошагово, пока не будут рассмотрены все субкомпоненты. Это делает C 3i DE очень эффективным для крупномасштабных глобальных задач оптимизации (до 1000 измерений) по сравнению с кооперативным коэволюционным алгоритмом (CC) и дифференциальной эволюцией . [8]

Улучшенный алгоритм затем был адаптирован для многокритериальной оптимизации . [9]

Алгоритм

Как показано в псевдокоде ниже, итерация C 3 состоит из двух фаз. В фазе I, конструктивной фазе, допустимое решение для всей проблемы строится поэтапно. Рассматривая другую подзадачу на каждом шаге. После последнего шага рассматриваются все подзадачи и строится решение для всей проблемы. Это построенное решение затем используется в качестве начального решения в фазе II, фазе локального улучшения. Алгоритм CC используется для дальнейшей оптимизации построенного решения. Цикл фазы II включает оптимизацию подзадач по отдельности, при этом параметры других подзадач фиксируются на центральном решении на доске. Когда это делается для каждой подзадачи, найденные решения объединяются во время шага «совместной работы», и лучшее из полученных комбинаций становится решением на доске для следующего цикла. В следующем цикле то же самое повторяется. Фаза II, а следовательно, и текущая итерация, завершаются, когда поиск алгоритма CC останавливается и не находится существенно лучших решений. Затем начинается следующая итерация. В начале следующей итерации строится новое допустимое решение, использующее решения, найденные в ходе Фазы I предыдущей итерации(й). Это построенное решение затем используется в качестве начального решения в Фазы II таким же образом, как и в первой итерации. Это повторяется до тех пор, пока не будет достигнут один из критериев завершения оптимизации, например, максимальное количество оценок.

{ S phase1 } ← ∅ пока критерии завершения не удовлетворены do  if { S phase1 } = ∅ then { S phase1 } ← SubOpt(∅, 1) end if  пока  p phase1 не полностью построен do  p phase1 ← GetBest({ S phase1 }) { S phase1 } ← SubOpt( p phase1 , i следующая подзадача ) конец while  p phase2 ← GetBest({ S phase1 }) пока не стагнация сделать { S phase2 } ← ∅ для каждой подзадачи i сделать { S phase2 } ← SubOpt( p phase2 ,i) конец для { S phase2 } ← Collab({ S phase2 }) p phase2 ← GetBest({ S phase2 }) конец while конец while

Многоцелевая оптимизация

Многокритериальная версия алгоритма C 3 [ 9] — это алгоритм на основе Парето, который использует ту же стратегию «разделяй и властвуй», что и однокритериальный алгоритм оптимизации C 3. Алгоритм снова начинается с продвинутых конструктивных начальных оптимизаций подпопуляций, рассматривая увеличивающееся подмножество подзадач. Подмножество увеличивается до тех пор, пока не будет включен весь набор всех подзадач. Во время этих начальных оптимизаций подпопуляция последней включенной подзадачи эволюционирует с помощью многокритериального эволюционного алгоритма. Для расчетов приспособленности членов подпопуляции они объединяются с решением коллаборатора из каждой из ранее оптимизированных подпопуляций. После того, как все подгруппы подзадач изначально оптимизированы, алгоритм оптимизации C 3 с несколькими критериями продолжает оптимизировать каждую подзадачу в циклическом режиме , но теперь решения коллабораторов из всех подгрупп подзадач объединяются с членом подгруппы, которая оценивается. Решение коллаборатора выбирается случайным образом из решений, которые составляют Парето-оптимальный фронт подгруппы. Назначение пригодности решениям коллаборатора выполняется оптимистичным образом (т. е. «старое» значение пригодности заменяется, когда новое оказывается лучше).

Приложения

Конструктивный кооперативный алгоритм коэволюции был применен к различным типам задач, например, набору стандартных функций эталонного теста, [4] [6] оптимизации линий прессования листового металла [4] [5] и взаимодействующих производственных станций. [5] Алгоритм C 3 был встроен, среди прочего, в алгоритм дифференциальной эволюции [10] и оптимизатор роя частиц [11] для оптимизации подзадач.

Смотрите также

Ссылки

  1. ^ TA Feo и MGC Resende (1989) «Вероятностная эвристика для вычислительно сложной задачи покрытия множеств». Operations Research Letters , 8:67–71, 1989.
  2. ^ TA Feo и MGC Resende (1995) «Жадные рандомизированные адаптивные процедуры поиска». Журнал глобальной оптимизации , 6:109–133, 1995.
  3. ^ MA Potter и KAD Jong, «Кооперативный коэволюционный подход к оптимизации функций», в PPSN III: Труды Международной конференции по эволюционным вычислениям. Третья конференция по параллельному решению проблем от Nature London, UK: Springer-Verlag, 1994, стр. 249–257.
  4. ^ abcd Glorieux E., Danielsson F., Svensson B., Lennartson B., «Оптимизация взаимодействующих производственных станций с использованием конструктивного кооперативного коэволюционного подхода», 2014 IEEE Международная конференция по автоматизации науки и техники (CASE), стр. 322-327, август 2014, Тайбэй, Тайвань
  5. ^ abc Glorieux E., Svensson B., Danielsson F., Lennartson B., "Конструктивный кооперативный коэволюционный алгоритм, применяемый для оптимизации прессовой линии", Труды 24-й Международной конференции по гибкой автоматизации и интеллектуальному производству (FAIM), стр. 909-917, май 2014 г., Сан-Антонио, Техас, США
  6. ^ ab Glorieux E., Svensson B., Danielsson F., Lennartson B.: «Конструктивная кооперативная коэволюция для крупномасштабной глобальной оптимизации», Journal of Heuristics , 2017.
  7. ^ Глорьё Э., Даниэльссон Ф., Свенссон Б., Леннартсон Б.: «Конструктивная кооперативная коэволюционная оптимизация для взаимодействующих производственных станций», Международный журнал передовых производственных технологий , 2015.
  8. ^ Глорьё Э., Свенссон Б., Даниэльссон Ф., Леннартсон Б., «Улучшенная конструктивная кооперативная коэволюционная дифференциальная эволюция для крупномасштабной оптимизации», серия симпозиумов IEEE 2015 года по вычислительному интеллекту, декабрь 2015 г.
  9. ^ ab Glorieux E., Svensson B., Danielsson F., Lennartson B., «Многоцелевая конструктивная кооперативная коэволюционная оптимизация обслуживания роботизированной прессовой линии», Engineering Optimization, т. 49, вып. 10, 2017, стр. 1685-1703
  10. ^ Сторн, Райнер и Кеннет Прайс. «Дифференциальная эволюция — простая и эффективная эвристика для глобальной оптимизации в непрерывных пространствах», Журнал глобальной оптимизации 11.4 (1997): 341-359.
  11. ^ Эберхарт, Расс К. и Джеймс Кеннеди. «Новый оптимизатор, использующий теорию роя частиц», Труды шестого международного симпозиума по микромашинам и наукам о человеке. Том 1. 1995.