Multi-agent genetic algorithm based on fuzzy clustering in solving multi-objective optimization problems

 
PIIS207751800009622-3-1
DOI10.18254/S207751800009622-3
Publication type Article
Status Published
Authors
Occupation: Principal Scientific Researcher
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Occupation: Senior Research Scholar
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Occupation: Leading Researcher
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Affiliation: Central Economic and Mathematic Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Journal nameArtificial Societies
EditionVolume 15 Issue 2
Abstract

This article presents a new multi-agent genetic algorithm based on fuzzy clustering for solving multi-objective optimization problems in systems of the "black box" type. The central element of such a genetic algorithm (GA) is the proposed fuzzy clustering procedure, which allows forming subgroups of potential solutions taking into account the distance between them in the criteria space and other important characteristics, in particular, their individual contribution to the hypervolume metric, distance to the nearest solution, etc. The developed multi-agent genetic algorithm was tested and validated using well-known test instances (in particular, the Binh and Korn function, the Fonseca–Fleming function, etc.) and the best efficiency of the proposed method was demonstrated in comparison with other known GAs (e.g., SPEA, SPEA2, NSGA-II) according to the criteria for assessing the quality of the Pareto-front, in particular, the Logarithmic Hypervolume (LHV), Inverted Generational Distance (IGD), etc.

Keywordsgenetic algorithm, multi-agent system, Pareto-front, multi-objective optimization, fuzzy clustering
AcknowledgmentThis work was supported by the Russian Foundation for Basic Research (grant No. 18-51-45001 IND_a), as well as the Department of Science and Technology, Government of India (project No. INT/RUS/RFBR/305).
Received29.04.2020
Publication date09.06.2020
Number of characters14085
Cite   Download pdf To download PDF you should sign in
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной
1

Введение

2

В настоящее время развивается новое направление, относящееся к проектированию интеллектуальных систем поддержки принятия решений социально-экономического и экологического планирования [1]. Особенностью подобных систем является наличие множественных ограничений и целевых функций, которые не могут быть представлены аналитически и, как правило, являются результатом имитационного моделирования. Поэтому такие системы, в которых применение более точных ньютоновских методов оптимизации [13] невозможно или существенно затруднено, относят к классу «black box optimization» («оптимизация черного ящика») [6]. В этом случае, целесообразно применение многокритериальных ГА класса SPEA [17], SPEA2 [10] и NSGA-II [12] и др., основанных на методах прямого эволюционного поиска (т.е. не требующих вычисления производных для оценки градиента целевой функции). Вместе с тем, подобные методы имеют известные недостатки, в частности, относящиеся, к недостаточно эффективной процедуре формирования подгрупп потенциальных решений, основанной, как правило, на турнирной селекции [15], когда, все особи популяции разбиваются на подпопуляции, как правило, одинаковой размерности с последующим выбором в каждой из них родительских особей с наилучшей приспособленностью (для генерации особей-потомков). При этом, формирование таких подгрупп основано на простом разбиении популяции потенциальных решений без учета их индивидуальных характеристик (например, близости друг к другу в пространстве критериев). В результате, формируемые подпопуляции могут состоять из близких (почти одинаковых) решений, а также решений, локализованных преимущественно на удалении от истинного фронта Парето.

3

Поэтому, для преодоления обозначенных проблем и обеспечения большего разнообразия отбираемых родительских особей, предлагается применение метода нечёткой кластеризации, впервые предложенного в [8, 9], предназначенного для эффективного разбиения популяции потенциальных решений на кластеры на основе оценки взвешенного расстояния между особями в пространстве критериев, и с учетом индивидуального вклада этих решений (особей) в характеристики качества фронта Парето (например, логарифмический логарифмического гиперобъема (LHV), инвертированного расстояния между поколениями (IGD), мощности множества Парето-оптимальных решений (CPF) и др., подробно описанных в [14]. Отметим, что общая постановка задачи многокритериальной оптимизации в системах типа «черного ящика», имеет следующий вид:

4 minF(x)=f1(x), f2(x), ...,  fM(x) ,
5 при условии
6 x=(x1, x2, ..., xn)' Ω ,
7 где x=(x1, x2, ..., xn)' вектор искомых переменных размерностью n , Ω=j=1n[aj, bj] диапазон допустимых решений ( j=1, 2, ..., n индексы искомых переменных), fm(x) m-ые целевые функции (m=1, 2, ..., M) , вычисляемые в результате имитационного моделирования (Рис. 1).

views: 313

Readers community rating: votes 0

1. Akopov A.S., Beklaryan A.L., Tkhakur M., Verma B.D. Razrabotka parallel'nykh geneticheskikh algoritmov veschestvennogo kodirovaniya dlya sistem podderzhki prinyatiya reshenij sotsial'no-ehkonomicheskogo i ehkologicheskogo planirovaniya // Biznes-informatika. 2019. T. 13. № 1. c. 33-44.

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. 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.

4. 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.

5.  Akopov A. S., Hevencev M.A. A Multi-agent genetic algorithm for multi-objective optimization, in Proceedings of 2013 IEEE International Conference on Systems, Man and Cybernetics, Manchester, 2013, pp. 1391–1395.

6. Akopov A.S., Beklaryan L.A., Thakur M., Verma D.B. Parallel multi-agent real-coded genetic algorithm for large-scale black-box single-objective optimisation // Knowledge-Based Systems. 2019. Vol. 174. pp. 103-122.

7. Beklaryan A.L, Akopov A.S. Simulation of Agent-rescuer Behavior 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. pp. 1275–1276.

8. Bezdek C.J. Cluster Validity with Fuzzy Sets // Journal of Cybernetics, vol. 3, no. 3, pp. 58–73, 1974.

9. Bezdek C.J., Pattern Recognition with Fuzzy Objective Function Algorithms. Norwell, Mass.: Kluwer Academic Publishers, 1981.

10. Bleuler S., Brack M., Thiele L., Zitzler E. Multiobjective genetic programmin.g: reducing bloat using SPEA2, in Proc. 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546), Seoul, South Korea, 2001, pp. 536–543.

11. Darrell W., Rana S.B., Heckendorn R.B. The Island Model Genetic Algorithm: On Separability, Population Size and Convergence // Journal of Computing and Information Technology. 1999. Vol. 7, no. 1, pp. 33-47.

12. Deb K., Pratap A., Agarwal S., Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II // IEEE Trans. Evol. Comp. Vol. 6, no. 2, pp. 182-197, 2002.

13. Fliege J., Drummond L.M.G., Svaiter B.F. Newton’s Method for Multiobjective Optimization // SIAM J. Optim., vol. 20, no. 2, pp. 602–626, 2009.

14. Jiang S., Ong Y., Zhang J., Feng L. Consistencies and Contradictions of Performance Metrics in Multiobjective Optimization // IEEE Transactions on Cybernetics, 2014. Vol. 44, no. 12, pp. 2391–2404.

15. Miller B., Goldberg D. Genetic Algorithms, Tournament Selection, and the Effects of Noise // Complex Systems, vol. 9, pp. 193–212, 1995.

16. Zhang Q., Zhou A., Zhao S., Suganthan P.N., Liu W. Multiobjective optimization Test Instances for the CEC 2009 Special Session and Competition // Tech. Rep. CES-487. 2009. pp. 1–30.

17. Zitzler E., Thiele L. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach // IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, pp. 257–271, 1999.

Система Orphus

Loading...
Up