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

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

Позднее была предложена усовершенствованная версия — Улучшенная конструктивная кооперативная коэволюционная дифференциальная эволюция, устраняющая ряд ограничений предыдущей версии. Ключевым элементом является продвинутая инициализация подпопуляций; первоначальная оптимизация подпопуляций проводится частично коадаптивно: во время начального этапа для коадаптации учитывается лишь подмножество других подкомпонентов, и это подмножество увеличивается, пока не будут учтены все компоненты. Такой подход делает особенно эффективной для крупномасштабных задач глобальной оптимизации (до 1000 измерений) по сравнению с алгоритмами кооперативной коэволюции и дифференциальной эволюции^[8].

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

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

{Sphase1} ← ∅
пока критерии прекращения не выполнены делать
    если {Sphase1} = ∅ тогда
        {Sphase1} ← SubOpt(∅, 1)
    конец если
    пока pphase1 не полностью сформировано делать
        pphase1 ← GetBest({Sphase1})
        {Sphase1} ← SubOpt(pphase1, iследующая подзадача)
    конец пока
    pphase2 ← GetBest({Sphase1})
    пока не стагнация делать
        {Sphase2} ← ∅ 
        для каждой подзадачи i делать
            {Sphase2} ← SubOpt(pphase2,i)
        конец для
        {Sphase2} ← Collab({Sphase2})
        pphase2 ← GetBest({Sphase2})
    конец пока
конец пока

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

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