АссистентНовый вопросИсторияОбласти знаний
Партнёрские проектыСпецпроектыСтать автором
Сменить язык
О РУВИКИ

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

Конструктивная кооперативная коэволюция (англ. constructive cooperative coevolutionary algorithm) — это алгоритм глобальной оптимизации в области искусственного интеллекта, основанный на мультистартовой архитектуре жадного рандомизированного адаптивного поиска[1][2]. Алгоритм включает существующий алгоритм кооперативной коэволюции[3]. Решаемая задача декомпозируется на подзадачи, которые оптимизируются по отдельности с обменом информацией для нахождения решения всей задачи. Для оптимизации подзадач в C3 внедряется определённый алгоритм оптимизации, обычно (но не обязательно) эволюционный алгоритм. От выбора этого вложенного алгоритма зависит, будет ли поведение C3 детерминированным или стохастическим.

Описание

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

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

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

Алгоритм

Как показано в псевдокоде ниже, одна итерация C3 состоит из двух фаз. В фазе 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})
    конец пока
конец пока

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

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

Применения

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

Примечания

  1. ↑ T.A. Feo, M.G.C. Resende. A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8:67–71, 1989. Feo, T.A.; Resende, M.G.C. (1989). “A probabilistic heuristic for a computationally difficult set covering problem”. Operations Research Letters [англ.]. 8: 67—71. Дата обращения 2024-06-17.
  2. ↑ T.A. Feo, M.G.C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133, 1995. Feo, T.A.; Resende, M.G.C. (1995). “Greedy randomized adaptive search procedures”. Journal of Global Optimization [англ.]. 6: 109—133. Дата обращения 2024-06-17.
  3. ↑ M.A. Potter, K.A.D. Jong. A cooperative coevolutionary approach to function optimization. В книге: PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature. Лондон: Springer-Verlag, 1994, стр. 249–257. Potter, M.A. A cooperative coevolutionary approach to function optimization : [англ.] / M.A. Potter, K.A.D. Jong. — Springer-Verlag, 1994. — P. 249–257.
  4. ↑ 1 2 3 4 Glorieux E., Danielsson F., Svensson B., Lennartson B. Optimisation of interacting production stations using a Constructive Cooperative Coevolutionary approach. 2014 IEEE International Conference on Automation Science and Engineering (CASE), стр. 322–327, август 2014, Тайбэй, Тайвань. Optimisation of interacting production stations using a Constructive Cooperative Coevolutionary approach (англ.). IEEE International Conference on Automation Science and Engineering (CASE) (август 2014). Дата обращения: 17 июня 2024.
  5. ↑ 1 2 3 Glorieux E., Svensson B., Danielsson F., Lennartson B. A Constructive Cooperative Coevolutionary Algorithm Applied to Press Line Optimisation. Proceedings of the 24th International Conference on Flexible Automation and Intelligent Manufacturing (FAIM), стр. 909–917, май 2014, Сан-Антонио, Техас, США. A Constructive Cooperative Coevolutionary Algorithm Applied to Press Line Optimisation (англ.). International Conference on Flexible Automation and Intelligent Manufacturing (FAIM) (май 2014). Дата обращения: 17 июня 2024.
  6. ↑ 1 2 Glorieux E., Svensson B., Danielsson F., Lennartson B. Constructive cooperative coevolution for large-scale global optimisation. Journal of Heuristics, 2017. Glorieux, E.; Svensson, B.; Danielsson, F.; Lennartson, B. (2017). “Constructive cooperative coevolution for large-scale global optimisation”. Journal of Heuristics [англ.]. Дата обращения 2024-06-17.
  7. ↑ Glorieux E., Danielsson F., Svensson B., Lennartson B. Constructive cooperative coevolutionary optimisation for interacting production stations. International Journal of Advanced Manufacturing Technology, 2015. Glorieux, E.; Danielsson, F.; Svensson, B.; Lennartson, B. (2015). “Constructive cooperative coevolutionary optimisation for interacting production stations”. International Journal of Advanced Manufacturing Technology [англ.]. Дата обращения 2024-06-17.
  8. ↑ Glorieux E., Svensson B., Danielsson F., Lennartson B. Improved Constructive Cooperative Coevolutionary Differential Evolution for Large-Scale Optimisation. 2015 IEEE Symposium Series on Computational Intelligence, декабрь 2015. Improved Constructive Cooperative Coevolutionary Differential Evolution for Large-Scale Optimisation (англ.). IEEE Symposium Series on Computational Intelligence (декабрь 2015). Дата обращения: 17 июня 2024.
  9. ↑ 1 2 Glorieux E., Svensson B., Danielsson F., Lennartson B. Multi-objective constructive cooperative coevolutionary optimization of robotic press-line tending. Engineering Optimization, Vol. 49, Iss. 10, 2017, стр. 1685–1703. Glorieux, E.; Svensson, B.; Danielsson, F.; Lennartson, B. (2017). “Multi-objective constructive cooperative coevolutionary optimization of robotic press-line tending”. Engineering Optimization [англ.]. 49 (10): 1685—1703. Дата обращения 2024-06-17.
  10. ↑ Storn R., Price K. Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization 11.4 (1997): 341–359. Storn, Rainer; Price, Kenneth (1997). “Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces”. Journal of Global Optimization [англ.]. 11 (4): 341—359. Дата обращения 2024-06-17.
  11. ↑ Eberhart R.C., Kennedy J. A new optimizer using particle swarm theory. Proceedings of the sixth international symposium on micro machine and human science. Vol. 1. 1995. A new optimizer using particle swarm theory (англ.). Proceedings of the sixth international symposium on micro machine and human science (1995). Дата обращения: 17 июня 2024.

Категории