Multi-agent genetic algorithm based on fuzzy clustering in solving multi-objective optimization problems
Table of contents
Share
Metrics
Multi-agent genetic algorithm based on fuzzy clustering in solving multi-objective optimization problems
Annotation
PII
S207751800009622-3-1
DOI
10.18254/S207751800009622-3
Publication type
Article
Статус публикации
Published
Authors
Andranick Akopov 
Occupation: Principal Scientific Researcher
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Fedor Belousov
Affiliation: Central Economic and Mathematic Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Gayane Beklaryan
Occupation: Senior Research Scholar
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Levon Beklaryan
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Nerses Khachatryan
Occupation: Leading Researcher
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
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.

Keywords
genetic algorithm, multi-agent system, Pareto-front, multi-objective optimization, fuzzy clustering
Received
29.04.2020
Date of publication
09.06.2020
Number of purchasers
27
Views
485
Readers community rating
0.0 (0 votes)
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).
8

Рисунок 1. Иллюстрация задачи многоцелевой оптимизации «черного ящика».

9 Отметим, что предлагаемый ГА является многоагентным. При этом, агентами являются процессы, на уровне которых осуществляется собственный эволюционный поиск Парето-оптимальных решений. Подобные агенты-процессы взаимодействуют друг с другом посредством глобальной популяции, обновляемой по результатам выполнения операторов селекции, кроссовера и мутации на локальном уровне каждого агента-процесса.
10

Таким образом, подобные агенты обновляют глобальную популяцию, которая в свою очередь является поставщиком наилучших потенциальных решений (особей) для агентов-процессов по принципу хорошо известной «островной модели» [3]. Однако, в отличие от островной модели, каждый подобный агент-процесс характеризуется набором некоторых состояний, между которыми заданы переходы, управляемые с использованием метода конечных автоматов («карта состояний агента») (рис. 2).

11

Рисунок 2. Схема взаимодействия агентов-процессов и карта состояний агента-процесса.

12

Отметим, что ранее нами были разработаны параллельные многоагентные генетические алгоритмы вещественного кодирования для одноцелевой оптимизации [6], а также для решения задач многоцелевой оптимизации, но с использованием операторов бинарного кодирования и применения метода турнирной селекции [2, 3, 4, 5].

13 Цель данной статьи – разработка нового многоагентного генетического алгоритма вещественного кодирования (real-coded genetic algorithm) на основе нечёткой кластеризации для решения задач многокритериальной оптимизации в системах типа «черного ящика», обеспечивающего возможность формирования наилучших решений за полиномиальное время и с максимально возможным уровнем качества фронта Парето, оцениваемого с использованием известных метрик (например, LHV, GD, CPF и др.).
14

Описание многоагентного генетического алгоритма

15 Особенностью разработанного ГА является процедура формирования подгрупп потенциальных решений на основе метода нечёткой кластеризации (рис. 3). Данный подход позволяет обеспечить большее разнообразие для отбираемых родительских особей, т.к. соответствующие подгруппы сформированы с учетом расстояния между потенциальными решениями в пространстве критериев и других важных характеристик, влияющих на качество формируемого фронта Парето (например, вклада в гиперобъем, расстояния до ближайшего потенциального решения и др.).
16

Рисунок 3. Блок-схема многоагентного генетического алгоритма.

17 Здесь,
18
  • K=1, 2, ..., K – набор индексов агентов-процессов K –общее количество агентов-процессов;
  • Tk={1, 2, ..., Tk}, kK – набор индексов внешних итераций k-го агента-процесса, Tk – общее количество внешних итераций;
  • Gtk=1, 2, ..., Gtk, tkTk – набор внутренних итераций k-го агента-процесса, Gtk –общее количество внутренних итераций;
  • {LX, SBX, MSBX, DMSBX} – набор операторов кроссовера (где LX – Лаплас-кроссовер, SBX – simulated binary crossover, MSBX – модифицированный SBX-кроссовер, DMSBX – дискретный модифицированный SBX-кроссовер), описанных в [3];
  • {PM, UM, DUM, SUM} – набор операторов мутации (где – степенная мутация, – равномерная мутация, –дискретная равномерная мутация, – масштабируемая равномерная мутация), описанных в [3];
  • Ik=1, 2, ..., Ik, kK набор индексов особей, принадлежащих k-ому агенту-процессу, Ik общее количество особей;
  • dik, ikIk, kK – Евклидово расстояние от i-ой особи до ближайшей особи;
  • вклад i-ой особи (ikIk, kK) в значение метрики LHV;
  • wik, ikIk, kK – сумма Парето-сил всех особей, которые доминируют i -ую особь («Парето-слабость»);
  • xik(gtk), gtkGtk, tkTk, kK – вектор значений искомых переменных, принадлежащих i-ой особи, заданный на момент gtk .
19 Тогда, фитнес-функция многоагентного генетического алгоритма на основе нечёткой кластеризации может быть определена в следующем виде:
20 f~ik(xik(gtk)=hik(xik(gtk)1+wik(xik(gtk)+12+dik(xik(gtk) .
21 Важнейшим элементом разработанного многоагентного ГА является предложенная процедура нечёткой кластеризации (рис. 4), предназначенная для формирования подпопуляции потенциальных решений и последующей селекции родительских особей.
22

Рисунок 4. Блок-схема алгоритма нечёткой кластеризации.

23

Разработанная процедура позволяет разбить исходную популяцию потенциальных решений, состоящую как из недоминируемых, так и доминируемых особей на подгруппы с учетом взвешенного расстояния между решениями в пространстве критериев, и другими важными характеристиками (например, LHV). Подобный метод нечёткой кластеризации ранее был нами описан в работе [7] применительно к модели поведения толпы в условиях чрезвычайных ситуаций. Использование процедуры нечёткой кластеризации позволяет сформировать подгруппы с учетом близости особей друг к другу по целому набору критериев, определяющих индивидуальный вклад потенциальных решений в качество фронта Парето. Подобный подход нацелен на достижение большего разнообразия отбираемых из сформированных кластеров родительских решений, участвующих в генерации нового поколения особей-потомков. Кроме того, при кластеризации недоминируемых решений данная процедура позволяет определить центры наиболее плотностных кластеров и обеспечить множественную мутацию потенциальных решений в соответствующем (наиболее перспективном) направлении.

24 Для повышения временной эффективности ГА, процедура нечёткой кластеризации (рис. 4) выполняется только во внешних итерациях для формирования подгрупп потенциальных родительских особей, отбираемых в дальнейшем на каждой внутренней итерации ГА случайным образом.
25

Результаты тестирования и оптимизации

26

Для тестирования и валидации разработанного генетического алгоритма применялись следующие хорошо известные тестовые задачи многокритериальной оптимизации [16] (Табл. 1).

27 Таблица 1. Тестовые задачи многокритериальной оптимизации.
Название тестовой задачи Постановка задачи Допустимые диапазоны для искомых переменных
Функци я Бина и Корна f1=4x2+4y2f2=(x-5)2+(y-5)2 при условии g1=(x-5)2+y225g2=(x-8)2+(y+3)27.7 0x5 0y3
Функция Ффонсеки и Флеминга f1=1-exp-j=1nxj-1n2f2=1-exp-j=1nxj+1n2 0xj41jn
Двухцелевая функция Полони f1=1+A1-B12+A2-B22f2=(x+3)2+(y+1)2 где A1=0.5sin(1)-2cos(1)+sin(2)-1.5cos(2)A2=1.5sin(1)-cos(1)+2sin(2)-0.5cos(2)B1=0.5sin(x)-2cos(x)+sin(y)-1.5cos(y)B2=1.5sin(x)-cos(x)+2sin(y)-0.5cos(y) -πxπ-πyπ
28 В таблице 2 представлены результаты оптимизационных экспериментов, выполненные не мене чем стократно для каждой тестовой оптимизационной задачи.
29

Таблица 2. Тестовые задачи многокритериальной оптимизации.

Метрики эффективности ГА Генетические алгоритмы
SPEA SPEA2 NSGA-II Многоагентный ГА
Функция Бина и Корна
LHV макс. 3.8050 3.8056 3.8048 3.8070
  ср. 3.8030 3.8034 3.8038 3.8068
  мин. 3.8050 3.8015 3.8023 3.8066
IGD макс. 0.1348 0.1859 0.1528 0.0910
  ср. 0.1178 0.1525 0.1344 0.0829
  мин. 0.0978 0.1338 0.1143 0.0757
CPF макс. 144 128 125 229
  ср. 135 113 114 209
  мин. 114 104 104 177
  Функция Ффонсеки и Флеминга
LHV макс. -0.0197 -0.0243 -0.0245 -0.0142
  ср. -0.0256 -0.0447 -0.0370 -0.0161
  мин. -0.0197 -0.0586 -0.0436 -0.0207
IGD макс. 0.0084 0.0242 0.0226 0.0061
  ср. 0.0062 0.0136 0.0157 0.0046
  мин. 0.0035 0.0077 0.0106 0.0033
CPF макс. 55 38 25 71
  ср. 29 26 23 64
  мин. 0 18 19 49
  Двухцелевая функция Полони
LHV макс. 2.7049 2.7014 2.7036 2.7043
  ср. 2.7003 2.6971 2.7006 2.7031
  мин. 2.7049 2.6910 2.6979 2.7019
IGD макс. 0.1606 0.2651 0.2438 0.1421
  ср. 0.1120 0.1492 0.1575 0.0929
  мин. 0.0603 0.0441 0.0773 0.0650
CPF макс. 52 30 28 41
  ср. 40 20 24 38
  мин. 30 14 20 34
30 В Табл. 2 используются следующие обозначения:
31
  • LHV – логарифмический гиперобъем (т.е. логарифмическая площадь доминирующего пространства, образуемого фронтом Парето, который вычислен с использованием ГА), который должен быть максимизирован;
  • IGD – инвертированное расстояние между поколениями (т.е. усредненное расстояние между решениями, принадлежащими вычисленному с помощью ГА, фронта Парето и ближайшими точками, принадлежащими истинному фронту Парето), которое должно быть минимизировано;
  • CPF – мощность фронта Парето (т.е. количество недоминируемых решений (альтернатив), принадлежащему фронту Парето), которая должна быть максимизирована.
32 Как следует из Таблицы 2 по всем трем ключевым критериям оценки качества фронта Парето – LHV, IGD и CPF, предлагаемый многоагентный генетический алгоритм на основе нечёткой кластеризации демонстрирует существенно большую эффективность в сравнении с другими известными генетическими алгоритмами (SPEA, SPEA2, NSGA-II).
33 На рис. 5 продемонстрирована эволюционная динамика недоминирумеых решений ( tk=1, 2, ..., 10 ) с соответствующей нечёткой кластеризацией (в пространстве решений), полученная с использованием разработанного многоагентного ГА, подтверждающая рост числа Парето-оптимальных решений с увеличением числа внешних итераций ГА.
34

Рисунок 5. Эволюционная динамика недоминируемых решений с кластеризацией.

35 В процессе эволюционного поиска в предложенном многоагентном ГА на основе нечёткой кластеризации обеспечивается монотонное возрастание значений метрики гиперобъема (LHV) и мощности Парето множества (CPF) и уменьшение расстояния между генерируемым («поколенческим») и истинным фронтами Парето (IGD). Подобная динамика подтверждает эффективность (по характеристике качества фронта Парето) предлагаемого ГА для решения многокритериальных оптимизационных задач.
36

Заключение

37 В данной статье представлен новый многоагентный генетический алгоритм на основе нечёткой кластеризации, предназначенный для решения многокритериальных задач, в которых целевые функционалы являются результатом имитационного моделирования. Продемонстрирована эффективность предлагаемого ГА, в сравнении с другими эвристическими методами (например, SPEA, SPEA2, NSGA-II).
38 Разработанный алгоритм может быть агрегирован по целевым функционалам с имитационными моделями, реализованными, в частности, в системе AnyLogic, что позволит использовать подобный подход при проектировании систем поддержки принятия решений социально-экономического и экологического планирования.

References

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.