Application of genetic optimization algorithms in decision-making systems
Table of contents
Share
Metrics
Application of genetic optimization algorithms in decision-making systems
Annotation
PII
S265838870000188-9-1
DOI
10.33276/S0000188-9-1
Publication type
Article
Status
Published
Authors
Andranik Akopov 
Occupation: Chief Researcher
Affiliation: CEMI RAS
Address: Moscow, Nakhimovsky Prospect 47
Gayane Beklaryan
Occupation: Senior researcher
Affiliation: CEMI RAS
Address: Russian Federation, Moscow, Nakhimovky prospect 47
Edition
Abstract
This paper presents an approach to the development of decision-making systems using genetic optimization algorithms (GA) of different classes (in particular, binary and real coding). The feature of this approach is the use of simulation systems (Powersim, AnyLogic), aggregated by target functional with parallel genetic algorithms to provide the procedure for finding suboptimal solutions. The architecture of the decision-making system in which simulation models are integrated with a problem-oriented database, web server and parallel genetic algorithms that allow forming and visualizing a subset of the Pareto optimal solutions was developed. Some examples of application of GA for decision-making at management of investment activity of vertically integrated petroleum company, the financial corporations, etc. are described.
Keywords
genetic algorithms, decision-making systems, simulation modeling.
Received
19.02.2019
Date of publication
19.02.2019
Number of characters
6074
Number of purchasers
4
Views
356
Readers community rating
0.0 (0 votes)
Cite Download pdf

To download PDF you should sign in

1 В настоящее время, разработка систем поддержки принятия решений (СППР) предполагает создание имитационных моделей с целью прогнозирования динамики соответствующих организационных структур [1]. Подобные имитационные модели могут быть также использованы для вычисления целевых функционалов и модельных характеристик, необходимых для проверки множественных ограничений и предпочтений, задаваемых со стороны лица принимающего решения (ЛПР). При этом, как правило, зависимость целевых функционалов от управляющих параметров не может быть описана аналитически из-за сложности объекта управления и необходимости использования реальных данных большого объема (Big Data).
2 Так, например, рациональное управление производственной и инвестиционной деятельностью вертикально-интегрированной нефтяной компании (ВИНК) требует создание комплекса интегрированных имитационных моделей, реализующих динамику соответствующих подсистем, в частности, звена нефтедобычи, нефтепереработки, транспортировки и сбыта [4, 5, 6, 8, 9, 10]. Для моделирования характеристик каждого подобного звена ВИНК используются методы системной динамики, учитывающей наличие внутренних обратных связей и лаговых зависимостей между множественными показателями (например, объемом добычи, объемом поставок на нефтеперерабатывающие заводы и ценой на нефть “net back”, т.е. за вычетом транспортных издержек).
3 Аналогичные трудности наблюдаются при решении задачи максимизации акционерной стоимости крупной финансовой корпорации, состоящей из множественных видов бизнеса, имеющих общие финансовые потоки (например, единые источники внешних заимствований).
4 В результате, применение хорошо известных ньютоновских и квазиньютоновских методов оптимизации [11] трудно применимо в условиях, когда целевые функционалы вычисляются в результате имитационного моделирования поведения крупномасштабных организационных структур (нефтяных компаний, финансовых корпораций, коммерческих банков, предприятий розничной торговли и др.). Поэтому требуется принципиально иной поход, основанный на разработке генетических оптимизационных алгоритмов, интегрируемых с имитационными моделями (Powersim, AnyLogic и др.), обеспечивающими вычисление значений фитнес-функций.
5 Впервые ГА был системно изложен в работе Дж. Холланда [24] в 1975 г., хотя первые опыты по использованию методов поисковой адаптации были проведены в 1954 году Нильсом Баричелли [21]. 
6 В настоящее время осуществляются исследования по развитию двух крупных классов ГА с бинарным и вещественным кодированием.
7 В первом случае, все потенциальные решения предварительно кодируются с использованием специального метода (кода Грея), что позволяет применять операторы одноточечного, двухточечного и многоточёчного кроссовера (скрещивания) для формирования новых (более приспособленных) решений на каждой итерации ГА. Данный подход особенно эффективен, когда необходимо обеспечить эффективный поиск решений в дискретном пространстве, либо в условиях бинарного управления характеристиками соответствующего объекта. Например, в работе [5, 6, 17, 18] ГА бинарного кодирования эффективно используется для формирования инвестиционного портфеля ВИНК. При этом, поиск осуществляется в дискретном пространстве, для этого используется специальная «матрица отключения проектов», в которой 1 – означает включить проект в портфель, 0 – означает исключить проект из портфеля.
8 Также нами были предложены различные модификации ГА с бинарным кодированием, например, параллельный ГА с угасающей селекцией [11]; многоагентный ГА, предназначенный для многоцелевой оптимизации [16], адаптивный многоагентный ГА [2] и др.
9 В работах [12, 13] описано применение многоагентного генетического алгоритма (MAGAMO) для поиска оптимальных стратегических и оперативных решений для многокритериальной оптимизации (с визуализацией фронта Парето) характеристик предприятия дистанционной торговли (крупного интернет-магазина). При этом, целевыми функционалами являются: прибыль (EBITDA), размер клиентской базы и оборачиваемость запасов.
10 В работах [7, 8, 9, 17, 18] описано генетического алгоритма c угасающей селекцией для задачи максимизации акционерной стоимости ВИНК. При этом, целевыми функционалами являются дисконтированные финансовые потоки от звена нефтедобычи (DCF1) и нефтепереработки (DCF2).
11 В работе [14] представлен пример применения ГА с бинарным кодированием для задачи рационального управления процессор экологической модернизации предприятий в Республике Армения. Отметим, что с помощью предложенного ГА осуществляется поддержка механизма бинарного управления переходами между различными состояниями агентов-предприятий.
12 В работах [3, 22] ГА используется для управления поведением интеллектуальных агентов-спасателей, обеспечивающих эффективную эвакуацию в модели поведения толпы в условиях чрезвычайных ситуаций.
13 Далее, предлагается следующая архитектура системы поддержки принятия решений, позволяющая формировать и визуализировать подмножество решений оптимальных по Парето для оптимизационных задач, целевые функционалы которых получены с использованием имитационного моделирования (рис.1).
14

Рис.1. Архитектура разработанной системы поддержки принятия решений.

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

References

1. Akopov A. S. Imitatsionnoe modelirovanie: uchebnik i praktikum dlya akademicheskogo bakalavriata. M.: Yurajt, 2015. 389 s.

2. Akopov A. S., Beklaryan A. L., Khachatryan N. K., Fomin A. V. Razrabotka adaptivnogo geneticheskogo optimizatsionnogo algoritma s ispol'zovaniem metodov agentnogo modelirovaniya // Informatsionnye tekhnologii. 2018. T. 24. № 5. S. 321-329.

3. Akopov A.S., Beklaryan L.A. Agentnaya model' povedeniya tolpy pri chrezvychajnykh situatsiyakh // Avtomatika i telemekhanika. 2015. № 10. S. 131-143.

4. Akopov A.S., K voprosu proektirovaniya intellektual'nykh sistem upravleniya slozhnymi organizatsionnymi strukturami. Ch. 2. Programmnaya realizatsiya sistemy upravleniya investitsionnoj deyatel'nost'yu vertikal'no-integrirovannoj neftyanoj kompanii // Problemy upravleniya. 2011. № 1. S. 47-54.

5. Akopov A.S. K voprosu proektirovaniya intellektual'nykh sistem upravleniya slozhnymi organizatsionnymi strukturami. Ch. I. Matematicheskoe obespechenie sistemy upravleniya investitsionnoj deyatel'nost'yu vertikal'no integrirovannoj neftyanoj kompanii. // Problemy upravleniya. 2010. № 6. S. 12-18.

6. Akopov A.S., Beklaryan G.L. Intellektual'nye gibridnye sistemy upravleniya deyatel'nost'yu vertikal'no-integrirovannymi organizatsionnymi strukturami / Preprint #WP/2009/267. – M.: TsEhMI RAN, 2009. – 54 c.

7. Akopov A.S. O skhodimosti i ustojchivosti modifitsirovannogo geneticheskogo algoritma v zadache upravleniya investitsionnym portfelem vertikal'no-integrirovannoj neftyanoj kompanii // V kn.: Dinamika neodnorodnykh sistem. Trudy instituta sistemnogo analiza RAN T. 32. Vyp. 1. M.: LKI, 2008. S. 168-179.

8.  Akopov A. S. Primenenie modifitsirovannogo geneticheskogo algoritma v sisteme upravleniya neftepererabatyvayuschim predpriyatiem // V kn.: Dinamika linejnykh i nelinejnykh sistem. Trudy instituta sistemnogo analiza RAN T. 25. Vyp. 1. M.: KomKniga, 2006. S. 7-19.

9. Akopov A.S. Sistemno-dinamicheskij podkhod v upravlenii investitsionnoj deyatel'nost'yu neftyanoj kompanii // Audit i finansovyj analiz. 2006. № 2. S. 165-200.

10. Akopov A.S. Problemy upravleniya sub'ektom TEhK v sovremennykh usloviyakh: Monografiya. — M.: TsEhMI RAN, 2004.

11. Gill F., Myurrej U., Rajt M. Prakticheskaya optimizatsiya. — M.: Mir, 1985. — 509 s.

12. Khivintsev M. A., Akopov A. S. Primenenie mnogoagentnogo geneticheskogo algoritma dlya poiska optimal'nykh strategicheskikh i operativnykh reshenij // Biznes-informatika. 2014. № 1(27). S. 23-33.

13. Khivintsev M. A., Akopov A. S. Raspredelennaya ehvolyutsionnaya set' dlya resheniya mnogokriterial'nykh optimizatsionnykh zadach v sistemakh imitatsionnogo modelirovaniya // Biznes-informatika. 2013. № 3(25). S. 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.