Применение генетических оптимизационных алгоритмов в системах поддержки принятия решений

Акопов Андраник С.; Бекларян Гаянэ Л.

doi:10.33276/S0000188-9-1

Русский

Войти Регистрация

Главная>Выпуск 4>Применение генетических оптимизационных алгоритмов в системах поддержки принятия решений

Применение генетических оптимизационных алгоритмов в системах поддержки принятия решений

Оглавление

Аннотация Оценить Содержание публикации

Библиография Комментарии

Применение генетических оптимизационных алгоритмов в системах поддержки принятия решений

Аннотация

Код статьи

S265838870000188-9-1

DOI

10.33276/S0000188-9-1

Тип публикации

Статья

Статус публикации

Опубликовано

Авторы

Акопов Андраник Сумбатович Связаться с автором

Должность: Главный научный сотрудник
Аффилиация: Центральный экономико-математический институт РАН
Адрес: Москва, Нахимовский проспект 47

Бекларян Гаянэ Левоновна

Должность: Старший научный сотрудник
Аффилиация: Центральный экономико-математический институт РАН
Адрес: Российская Федерация, Москва, Нахимовский проспект, 47

Выпуск

Том 1 Выпуск 4

Аннотация

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

Ключевые слова

генетические алгоритмы, системы поддержки принятия решений, имитационное моделирование.

Классификатор

Получено

19.02.2019

Дата публикации

19.02.2019

Всего подписок

Всего просмотров

2881

Оценка читателей

0.0 (0 голосов)

Цитировать Скачать pdf

ГОСТ	Акопов А. С. , Бекларян Г. Л. Применение генетических оптимизационных алгоритмов в системах поддержки принятия решений // Вестник ЦЭМИ РАН. – 2018. – T. 1. – Выпуск 4. URL: https://cemi.jes.su/s265838870000188-9-1/. DOI: 10.33276/S0000188-9-1
MLA	Akopov, Andranik, Beklaryan, Gayane "Application of genetic optimization algorithms in decision-making systems." Herald of CEMI. 1.4 (2018). DOI: 10.33276/S0000188-9-1
APA	Akopov A., Beklaryan G. (2018). Application of genetic optimization algorithms in decision-making systems. Herald of CEMI. vol. 1, no. 4 DOI: 10.33276/S0000188-9-1

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

1. Акопов А. С. Имитационное моделирование: учебник и практикум для академического бакалавриата. M.: Юрайт, 2015. 389 с.

2. Акопов А. С., Бекларян А. Л., Хачатрян Н. К., Фомин А. В. Разработка адаптивного генетического оптимизационного алгоритма с использованием методов агентного моделирования // Информационные технологии. 2018. Т. 24. № 5. С. 321-329.

3. Акопов А.С., Бекларян Л.А. Агентная модель поведения толпы при чрезвычайных ситуациях // Автоматика и телемеханика. 2015. № 10. С. 131-143.

4. Акопов А.С., К вопросу проектирования интеллектуальных систем управления сложными организационными структурами. Ч. 2. Программная реализация системы управления инвестиционной деятельностью вертикально-интегрированной нефтяной компании // Проблемы управления. 2011. № 1. С. 47-54.

5. Акопов А.С. К вопросу проектирования интеллектуальных систем управления сложными организационными структурами. Ч. I. Математическое обеспечение системы управления инвестиционной деятельностью вертикально интегрированной нефтяной компании. // Проблемы управления. 2010. № 6. С. 12-18.

6. Акопов А.С., Бекларян Г.Л. Интеллектуальные гибридные системы управления деятельностью вертикально-интегрированными организационными структурами / Препринт #WP/2009/267. – М.: ЦЭМИ РАН, 2009. – 54 c.

7. Акопов А.С. О сходимости и устойчивости модифицированного генетического алгоритма в задаче управления инвестиционным портфелем вертикально-интегрированной нефтяной компании // В кн.: Динамика неоднородных систем. Труды института системного анализа РАН Т. 32. Вып. 1. М.: ЛКИ, 2008. С. 168-179.

8. Акопов А. С. Применение модифицированного генетического алгоритма в системе управления нефтеперерабатывающим предприятием // В кн.: Динамика линейных и нелинейных систем. Труды института системного анализа РАН Т. 25. Вып. 1. М.: КомКнига, 2006. С. 7-19.

9. Акопов А.С. Системно-динамический подход в управлении инвестиционной деятельностью нефтяной компании // Аудит и финансовый анализ. 2006. № 2. С. 165-200.

10. Акопов А.С. Проблемы управления субъектом ТЭК в современных условиях: Монография. — М.: ЦЭМИ РАН, 2004.

11. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985. — 509 с.

12. Хивинцев М. А., Акопов А. С. Применение многоагентного генетического алгоритма для поиска оптимальных стратегических и оперативных решений // Бизнес-информатика. 2014. № 1(27). С. 23-33.

13. Хивинцев М. А., Акопов А. С. Распределенная эволюционная сеть для решения многокритериальных оптимизационных задач в системах имитационного моделирования // Бизнес-информатика. 2013. № 3(25). С. 35-41.

14. Akopov A.S., Beklaryan L. A., Saghatelyan A. K. Agent-based modelling for ecological economics: A case study of the Republic of Armenia // Ecological Modelling. 2017. Vol. 346. P. 99-118.

15. Akopov A. S. Parallel genetic algorithm with fading selection // International Journal of Computer Applications in Technology. 2014. Vol. 49. No. 3/4. P. 325-331.

16. Akopov A.S., Hevencev M.A. A multi-agent genetic algorithm for multi-objective optimization // Proceedings of IEEE International Conference on Systems, Man and Cybernetics, Manchester, 13–16 October 2013. P. 1391–1395.

17. Akopov A.S. Designing of integrated system-dynamics models for an oil company // International Journal of Computer Applications in Technology. 2012. Vol. 45. No. 4. P. 220-230

18. Akopov A. S. Parallel genetic algorithm with fading selection // International Journal of Computer Applications in Technology. 2014. Vol. 49. No. 3/4. P. 325-331.

19. Akopov A.S., Hevencev M.A. A multi-agent genetic algorithm for multi-objective optimization // Proceedings of IEEE International Conference on Systems, Man and Cybernetics, Manchester, 13–16 October 2013. P. 1391–1395.

20. Akopov A.S. Designing of integrated system-dynamics models for an oil company // International Journal of Computer Applications in Technology. 2012. Vol. 45. No. 4. P. 220-230

21. Barricelli, N.A.. Esempi numerici di processi di evoluzione. Methodos: 45–68. 1954.

22. Beklaryan A., Akopov A. S. Simulation of Agent-rescuer Behaviour in Emergency Based on Modified Fuzzy Clustering, in: AAMAS'16: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. Richland: International Foundation for Autonomous Agents and Multiagent Systems, 2016. P. 1275-1276.

23. Lotov, A.V., Bushenkov, V.A., Kamenev, G.K. Interactive Decision Maps. Approximation and Visualization of Pareto Frontier. Kluwer Academic Publishers, Boston. 2004.

24. Holland J.H. Adaptation in Natural and Artificial Systems. MIT Press. 1975.


1	В настоящее время, разработка систем поддержки принятия решений (СППР) предполагает создание имитационных моделей с целью прогнозирования динамики соответствующих организационных структур [1]. Подобные имитационные модели могут быть также использованы для вычисления целевых функционалов и модельных характеристик, необходимых для проверки множественных ограничений и предпочтений, задаваемых со стороны лица принимающего решения (ЛПР). При этом, как правило, зависимость целевых функционалов от управляющих параметров не может быть описана аналитически из-за сложности объекта управления и необходимости использования реальных данных большого объема (Big Data).	В настоящее время, разработка систем поддержки принятия решений (СППР) предполагает создание имитационных моделей с целью прогнозирования динамики соответствующих организационных структур [1]. Подобные имитационные модели могут быть также использованы для вычисления целевых функционалов и модельных характеристик, необходимых для проверки множественных ограничений и предпочтений, задаваемых со стороны лица принимающего решения (ЛПР). При этом, как правило, зависимость целевых функционалов от управляющих параметров не может быть описана аналитически из-за сложности объекта управления и необходимости использования реальных данных большого объема (Big Data). В настоящее время, разработка систем поддержки принятия решений (СППР) предполагает создание имитационных моделей с целью прогнозирования динамики соответствующих организационных структур [1]. Подобные имитационные модели могут быть также использованы для вычисления целевых функционалов и модельных характеристик, необходимых для проверки множественных ограничений и предпочтений, задаваемых со стороны лица принимающего решения (ЛПР). При этом, как правило, зависимость целевых функционалов от управляющих параметров не может быть описана аналитически из-за сложности объекта управления и необходимости использования реальных данных большого объема (Big Data).

2	Так, например, рациональное управление производственной и инвестиционной деятельностью вертикально-интегрированной нефтяной компании (ВИНК) требует создание комплекса интегрированных имитационных моделей, реализующих динамику соответствующих подсистем, в частности, звена нефтедобычи, нефтепереработки, транспортировки и сбыта [4, 5, 6, 8, 9, 10]. Для моделирования характеристик каждого подобного звена ВИНК используются методы системной динамики, учитывающей наличие внутренних обратных связей и лаговых зависимостей между множественными показателями (например, объемом добычи, объемом поставок на нефтеперерабатывающие заводы и ценой на нефть “net back”, т.е. за вычетом транспортных издержек).	Так, например, рациональное управление производственной и инвестиционной деятельностью вертикально-интегрированной нефтяной компании (ВИНК) требует создание комплекса интегрированных имитационных моделей, реализующих динамику соответствующих подсистем, в частности, звена нефтедобычи, нефтепереработки, транспортировки и сбыта [4, 5, 6, 8, 9, 10]. Для моделирования характеристик каждого подобного звена ВИНК используются методы системной динамики, учитывающей наличие внутренних обратных связей и лаговых зависимостей между множественными показателями (например, объемом добычи, объемом поставок на нефтеперерабатывающие заводы и ценой на нефть “net back”, т.е. за вычетом транспортных издержек). Так, например, рациональное управление производственной и инвестиционной деятельностью вертикально-интегрированной нефтяной компании (ВИНК) требует создание комплекса интегрированных имитационных моделей, реализующих динамику соответствующих подсистем, в частности, звена нефтедобычи, нефтепереработки, транспортировки и сбыта [4, 5, 6, 8, 9, 10]. Для моделирования характеристик каждого подобного звена ВИНК используются методы системной динамики, учитывающей наличие внутренних обратных связей и лаговых зависимостей между множественными показателями (например, объемом добычи, объемом поставок на нефтеперерабатывающие заводы и ценой на нефть “net back”, т.е. за вычетом транспортных издержек).

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

4	В результате, применение хорошо известных ньютоновских и квазиньютоновских методов оптимизации [11] трудно применимо в условиях, когда целевые функционалы вычисляются в результате имитационного моделирования поведения крупномасштабных организационных структур (нефтяных компаний, финансовых корпораций, коммерческих банков, предприятий розничной торговли и др.). Поэтому требуется принципиально иной поход, основанный на разработке генетических оптимизационных алгоритмов, интегрируемых с имитационными моделями (Powersim, AnyLogic и др.), обеспечивающими вычисление значений фитнес-функций.	В результате, применение хорошо известных ньютоновских и квазиньютоновских методов оптимизации [11] трудно применимо в условиях, когда целевые функционалы вычисляются в результате имитационного моделирования поведения крупномасштабных организационных структур (нефтяных компаний, финансовых корпораций, коммерческих банков, предприятий розничной торговли и др.). Поэтому требуется принципиально иной поход, основанный на разработке генетических оптимизационных алгоритмов, интегрируемых с имитационными моделями (Powersim, AnyLogic и др.), обеспечивающими вычисление значений фитнес-функций. В результате, применение хорошо известных ньютоновских и квазиньютоновских методов оптимизации [11] трудно применимо в условиях, когда целевые функционалы вычисляются в результате имитационного моделирования поведения крупномасштабных организационных структур (нефтяных компаний, финансовых корпораций, коммерческих банков, предприятий розничной торговли и др.). Поэтому требуется принципиально иной поход, основанный на разработке генетических оптимизационных алгоритмов, интегрируемых с имитационными моделями (Powersim, AnyLogic и др.), обеспечивающими вычисление значений фитнес-функций.

5	Впервые ГА был системно изложен в работе Дж. Холланда [24] в 1975 г., хотя первые опыты по использованию методов поисковой адаптации были проведены в 1954 году Нильсом Баричелли [21].	Впервые ГА был системно изложен в работе Дж. Холланда [24] в 1975 г., хотя первые опыты по использованию методов поисковой адаптации были проведены в 1954 году Нильсом Баричелли [21]. Впервые ГА был системно изложен в работе Дж. Холланда [24] в 1975 г., хотя первые опыты по использованию методов поисковой адаптации были проведены в 1954 году Нильсом Баричелли [21].

6	В настоящее время осуществляются исследования по развитию двух крупных классов ГА с бинарным и вещественным кодированием.	В настоящее время осуществляются исследования по развитию двух крупных классов ГА с бинарным и вещественным кодированием. В настоящее время осуществляются исследования по развитию двух крупных классов ГА с бинарным и вещественным кодированием.

7	В первом случае, все потенциальные решения предварительно кодируются с использованием специального метода (кода Грея), что позволяет применять операторы одноточечного, двухточечного и многоточёчного кроссовера (скрещивания) для формирования новых (более приспособленных) решений на каждой итерации ГА. Данный подход особенно эффективен, когда необходимо обеспечить эффективный поиск решений в дискретном пространстве, либо в условиях бинарного управления характеристиками соответствующего объекта. Например, в работе [5, 6, 17, 18] ГА бинарного кодирования эффективно используется для формирования инвестиционного портфеля ВИНК. При этом, поиск осуществляется в дискретном пространстве, для этого используется специальная «матрица отключения проектов», в которой 1 – означает включить проект в портфель, 0 – означает исключить проект из портфеля.	В первом случае, все потенциальные решения предварительно кодируются с использованием специального метода (кода Грея), что позволяет применять операторы одноточечного, двухточечного и многоточёчного кроссовера (скрещивания) для формирования новых (более приспособленных) решений на каждой итерации ГА. Данный подход особенно эффективен, когда необходимо обеспечить эффективный поиск решений в дискретном пространстве, либо в условиях бинарного управления характеристиками соответствующего объекта. Например, в работе [5, 6, 17, 18] ГА бинарного кодирования эффективно используется для формирования инвестиционного портфеля ВИНК. При этом, поиск осуществляется в дискретном пространстве, для этого используется специальная «матрица отключения проектов», в которой 1 – означает включить проект в портфель, 0 – означает исключить проект из портфеля. В первом случае, все потенциальные решения предварительно кодируются с использованием специального метода (кода Грея), что позволяет применять операторы одноточечного, двухточечного и многоточёчного кроссовера (скрещивания) для формирования новых (более приспособленных) решений на каждой итерации ГА. Данный подход особенно эффективен, когда необходимо обеспечить эффективный поиск решений в дискретном пространстве, либо в условиях бинарного управления характеристиками соответствующего объекта. Например, в работе [5, 6, 17, 18] ГА бинарного кодирования эффективно используется для формирования инвестиционного портфеля ВИНК. При этом, поиск осуществляется в дискретном пространстве, для этого используется специальная «матрица отключения проектов», в которой 1 – означает включить проект в портфель, 0 – означает исключить проект из портфеля.

8	Также нами были предложены различные модификации ГА с бинарным кодированием, например, параллельный ГА с угасающей селекцией [11]; многоагентный ГА, предназначенный для многоцелевой оптимизации [16], адаптивный многоагентный ГА [2] и др.	Также нами были предложены различные модификации ГА с бинарным кодированием, например, параллельный ГА с угасающей селекцией [11]; многоагентный ГА, предназначенный для многоцелевой оптимизации [16], адаптивный многоагентный ГА [2] и др. Также нами были предложены различные модификации ГА с бинарным кодированием, например, параллельный ГА с угасающей селекцией [11]; многоагентный ГА, предназначенный для многоцелевой оптимизации [16], адаптивный многоагентный ГА [2] и др.

9	В работах [12, 13] описано применение многоагентного генетического алгоритма (MAGAMO) для поиска оптимальных стратегических и оперативных решений для многокритериальной оптимизации (с визуализацией фронта Парето) характеристик предприятия дистанционной торговли (крупного интернет-магазина). При этом, целевыми функционалами являются: прибыль (EBITDA), размер клиентской базы и оборачиваемость запасов.	В работах [12, 13] описано применение многоагентного генетического алгоритма (MAGAMO) для поиска оптимальных стратегических и оперативных решений для многокритериальной оптимизации (с визуализацией фронта Парето) характеристик предприятия дистанционной торговли (крупного интернет-магазина). При этом, целевыми функционалами являются: прибыль (EBITDA), размер клиентской базы и оборачиваемость запасов. В работах [12, 13] описано применение многоагентного генетического алгоритма (MAGAMO) для поиска оптимальных стратегических и оперативных решений для многокритериальной оптимизации (с визуализацией фронта Парето) характеристик предприятия дистанционной торговли (крупного интернет-магазина). При этом, целевыми функционалами являются: прибыль (EBITDA), размер клиентской базы и оборачиваемость запасов.

10	В работах [7, 8, 9, 17, 18] описано генетического алгоритма c угасающей селекцией для задачи максимизации акционерной стоимости ВИНК. При этом, целевыми функционалами являются дисконтированные финансовые потоки от звена нефтедобычи (DCF1) и нефтепереработки (DCF2).	В работах [7, 8, 9, 17, 18] описано генетического алгоритма c угасающей селекцией для задачи максимизации акционерной стоимости ВИНК. При этом, целевыми функционалами являются дисконтированные финансовые потоки от звена нефтедобычи (DCF1) и нефтепереработки (DCF2). В работах [7, 8, 9, 17, 18] описано генетического алгоритма c угасающей селекцией для задачи максимизации акционерной стоимости ВИНК. При этом, целевыми функционалами являются дисконтированные финансовые потоки от звена нефтедобычи (DCF1) и нефтепереработки (DCF2).

11	В работе [14] представлен пример применения ГА с бинарным кодированием для задачи рационального управления процессор экологической модернизации предприятий в Республике Армения. Отметим, что с помощью предложенного ГА осуществляется поддержка механизма бинарного управления переходами между различными состояниями агентов-предприятий.	В работе [14] представлен пример применения ГА с бинарным кодированием для задачи рационального управления процессор экологической модернизации предприятий в Республике Армения. Отметим, что с помощью предложенного ГА осуществляется поддержка механизма бинарного управления переходами между различными состояниями агентов-предприятий. В работе [14] представлен пример применения ГА с бинарным кодированием для задачи рационального управления процессор экологической модернизации предприятий в Республике Армения. Отметим, что с помощью предложенного ГА осуществляется поддержка механизма бинарного управления переходами между различными состояниями агентов-предприятий.

12	В работах [3, 22] ГА используется для управления поведением интеллектуальных агентов-спасателей, обеспечивающих эффективную эвакуацию в модели поведения толпы в условиях чрезвычайных ситуаций.	В работах [3, 22] ГА используется для управления поведением интеллектуальных агентов-спасателей, обеспечивающих эффективную эвакуацию в модели поведения толпы в условиях чрезвычайных ситуаций. В работах [3, 22] ГА используется для управления поведением интеллектуальных агентов-спасателей, обеспечивающих эффективную эвакуацию в модели поведения толпы в условиях чрезвычайных ситуаций.

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

14	Подпись к рисунку/медиа Рис.1. Архитектура разработанной системы поддержки принятия решений. Рис.1. Архитектура разработанной системы поддержки принятия решений.
15	Системы имитационного моделирования AnyLogic и Powersim [1] в рамках архитектуры СППР, представленной на рис. 1, используются для вычисления целевых функционалов и других модельных характеристик, учитываемых в ограничениях решаемой оптимизационной задачи, система Pareto Front Viewer (PFV) [23] используется для визуализации фронта Парето, СУБД (Oracle, MS SQL Server) используется для хранения исходных данных и результатов имитационного моделирования, веб-сервер (например, Tomcat) необходим для обеспечения многопользовательского доступа к СППР и запуска оптимизационного модуля (ГА) при заданных ограничениях через веб-интерфейс. При этом, оптимизационный модуль, представляет собой программную реализацию ГА (на языке C++) с использованием технологии Message Passing Interface (MPI, интерфейс передачи сообщений).	Системы имитационного моделирования AnyLogic и Powersim [1] в рамках архитектуры СППР, представленной на рис. 1, используются для вычисления целевых функционалов и других модельных характеристик, учитываемых в ограничениях решаемой оптимизационной задачи, система Pareto Front Viewer (PFV) [23] используется для визуализации фронта Парето, СУБД (Oracle, MS SQL Server) используется для хранения исходных данных и результатов имитационного моделирования, веб-сервер (например, Tomcat) необходим для обеспечения многопользовательского доступа к СППР и запуска оптимизационного модуля (ГА) при заданных ограничениях через веб-интерфейс. При этом, оптимизационный модуль, представляет собой программную реализацию ГА (на языке C++) с использованием технологии Message Passing Interface (MPI, интерфейс передачи сообщений). Системы имитационного моделирования AnyLogic и Powersim [1] в рамках архитектуры СППР, представленной на рис. 1, используются для вычисления целевых функционалов и других модельных характеристик, учитываемых в ограничениях решаемой оптимизационной задачи, система Pareto Front Viewer (PFV) [23] используется для визуализации фронта Парето, СУБД (Oracle, MS SQL Server) используется для хранения исходных данных и результатов имитационного моделирования, веб-сервер (например, Tomcat) необходим для обеспечения многопользовательского доступа к СППР и запуска оптимизационного модуля (ГА) при заданных ограничениях через веб-интерфейс. При этом, оптимизационный модуль, представляет собой программную реализацию ГА (на языке C++) с использованием технологии Message Passing Interface (MPI, интерфейс передачи сообщений).

16	Разработанная СППР может быть использована для рационального управления характеристиками крупных предприятий и организационных структур (на региональном, отраслевом и страновом уровнях).	Разработанная СППР может быть использована для рационального управления характеристиками крупных предприятий и организационных структур (на региональном, отраслевом и страновом уровнях). Разработанная СППР может быть использована для рационального управления характеристиками крупных предприятий и организационных структур (на региональном, отраслевом и страновом уровнях).

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

Комментарии

Войти через