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

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

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

Позже была предложена улучшенная версия, получившая название «Улучшенная конструктивная кооперативная коэволюционная дифференциальная эволюция» (C ^3я DE), что устраняет некоторые ограничения предыдущей версии. Новый элемент C ^3я DE — это расширенная инициализация субпопуляций. С ^3я DE изначально оптимизирует субпопуляции частично коадаптивным образом. Во время первоначальной оптимизации субпопуляции для совместной адаптации рассматривается только подмножество других субкомпонентов. Это подмножество постепенно увеличивается, пока не будут учтены все подкомпоненты. Это делает С ^3я DE очень эффективен при решении крупномасштабных задач глобальной оптимизации (до 1000 измерений) по сравнению с кооперативным коэволюционным алгоритмом (CC) и дифференциальной эволюцией .

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

Алгоритм

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

{Sphase1} ← ∅
while termination criteria not satisfied do
    if {Sphase1} = ∅ then
        {Sphase1} ← SubOpt(∅, 1)
    end if
    while pphase1 not completely constructed do
        pphase1 ← GetBest({Sphase1})
        {Sphase1} ← SubOpt(pphase1, inext subproblem)
    end while
    pphase2 ← GetBest({Sphase1})
    while not stagnate do
        {Sphase2} ← ∅ 
        for each subproblem i do
            {Sphase2} ← SubOpt(pphase2,i)
        end for
        {Sphase2} ← Collab({Sphase2})
        pphase2 ← GetBest({Sphase2})
    end while
end while

Многокритериальная оптимизация

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

Приложения

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

См. также

• Кооперативная коэволюция
• Метаэвристический
• Стохастический поиск
• Дифференциальная эволюция
• Роевой интеллект
• Генетические алгоритмы
• Гиперэвристика