MetaTrader 5 / Тестер
preview
Популяционные алгоритмы оптимизации: Устойчивость к застреванию в локальных экстремумах (Часть II)

Популяционные алгоритмы оптимизации: Устойчивость к застреванию в локальных экстремумах (Часть II)

MetaTrader 5 — Тестер | 12 марта 2024, 17:27
508 0
Andrey Dik
Andrey Dik

Содержание:

1. Обсуждение алгоритмов
2. Доработка агента для BGA
3. Выводы


В рамках нашего исследования мы углубляемся в изучение устойчивости популяционных алгоритмов оптимизации, и их способности преодолевать локальные ловушки и достигать глобальных максимумов на разнообразных тестовых функциях. В предыдущей статье мы рассмотрели алгоритмы, занявшие скромные позиции в рейтинге, и теперь пришло время обратить внимание на те, которые показали отличную эффективность в данном исследовании.

Мы стремимся к тому, чтобы провести глубокий анализ каждого из этих алгоритмов, выявив их преимущества и уникальные особенности. Наша цель — понять, какие стратегии и подходы делают эти алгоритмы успешными в преодолении сложностей и достижении глобальных целей оптимизации.

Этот этап исследования позволит нам не только лучше понять устойчивость популяционных алгоритмов к застреванию в локальных ловушках, но и выявить ключевые факторы, способствующие их успеху в условиях разнообразных и сложных тестовых функций. Наша работа направлена на углубление понимания того, как можно оптимизировать и улучшить эти алгоритмы, а также на выявление возможностей их совместного использования и гибридизации для эффективного решения различных задач оптимизации в будущем.


1. Обсуждение алгоритмов

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

Далее будут приведены отчеты работы алгоритмов, которые нужно читать так:

  • C_AO_FSS:50;0.01;0.8             - название алгоритма и его внешние параметры
  • 5 Hilly's                                   - название тестовой функции и её количество в тесте
  •  Func runs: 10000                   - количество запусков
  • result: 0.32457068874346456  - полученный результат, где 0.0 - минимум тестовой функции, а 1.0 - максимум,  чем больше значение, тем лучше
  • All score: 1.33084                   - общее значение набранных баллов, чем больше значение, тем лучше

Эволюционные стратегии, (P+O)ES

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
5 Hilly's; Func runs: 10000; result: 0.45574011563217454
25 Hilly's; Func runs: 10000; result: 0.5979154724556998
500 Hilly's; Func runs: 10000; result: 0.3415203622112476
=============================
5 Forest's; Func runs: 10000; result: 0.18929181937830403
25 Forest's; Func runs: 10000; result: 0.1837517532554242
500 Forest's; Func runs: 10000; result: 0.15411134176683486
=============================
5 Megacity's; Func runs: 10000; result: 0.10153846153846155
25 Megacity's; Func runs: 10000; result: 0.12030769230769231
500 Megacity's; Func runs: 10000; result: 0.08793846153846216
=============================
All score: 2.23212

В отличие от своего младшего собрата (PO)ES, данный алгоритм (P+O)ES проявляет высокую активность в пространстве поиска, особенно это проявляется на гладкой функции Hilly, где популяция разделяется на несколько групп, каждая из которых исследует различные области. Однако на гладкой функции Forest его эффективность почему-то снижается, а на дискретной функции показывает себя плохо (достигается лишь ближайший холм). В целом, алгоритм очень интересен на гладких дифференцируемых функциях, но явно прослеживается склонность к застреванию и недостатку уточняющих результат способностей.

Оптимизация стаей серых волков, GWO

C_AO_GWO:50;10
=============================
5 Hilly's; Func runs: 10000; result: 0.5385541648909985
25 Hilly's; Func runs: 10000; result: 0.33060651191769963
500 Hilly's; Func runs: 10000; result: 0.25796885816873344
=============================
5 Forest's; Func runs: 10000; result: 0.33256641908450685
25 Forest's; Func runs: 10000; result: 0.2040563379483599
500 Forest's; Func runs: 10000; result: 0.15278428644972566
=============================
5 Megacity's; Func runs: 10000; result: 0.2784615384615384
25 Megacity's; Func runs: 10000; result: 0.1587692307692308
500 Megacity's; Func runs: 10000; result: 0.133153846153847
=============================
All score: 2.38692

По бескрайним просторам виртуального мира мчится стая волков алгоритма GWO, стремительно распространяясь во всех направлениях на различных тестовых функциях. Это свойство можно эффективно использовать на начальных итерациях, особенно если алгоритм работает в паре с другим методом, который может улучшить и дополнить найденные решения. Великолепные исследовательские способности стаи говорят об их потенциале, но, к сожалению, точность в определении областей остается их слабым местом. Интересно отметить, что алгоритм волчьей стаи продемонстрировал даже результат лучше, чем при обычном тестировании с равномерным распределением агентов.

Тасующий алгоритм прыгающих лягушек, SFL

C_AO_SFL:50;25;15;5;0.7
=============================
5 Hilly's; Func runs: 10000; result: 0.5009251084703008
25 Hilly's; Func runs: 10000; result: 0.3175649450809088
500 Hilly's; Func runs: 10000; result: 0.25514153268631673
=============================
5 Forest's; Func runs: 10000; result: 0.4165336325557746
25 Forest's; Func runs: 10000; result: 0.21617658684174407
500 Forest's; Func runs: 10000; result: 0.15782134182434096
=============================
5 Megacity's; Func runs: 10000; result: 0.2892307692307692
25 Megacity's; Func runs: 10000; result: 0.14892307692307696
500 Megacity's; Func runs: 10000; result: 0.10636923076923148
=============================
All score: 2.40869

Алгоритм SFL продемонстрировал еще более широкий спектр возможностей для распространения в различных направлениях пространства поиска, даже на дискретной функции Megacity, по сравнению с предыдущим алгоритмом в списке. SFL способен достичь даже областей глобального максимума в пределах заданного количества итераций. Однако точность уточнения найденных решений не является сильной стороной SFL. Этот алгоритм, аналогично GWO, продемонстрировал результаты, превосходящие чем в обычном тестировании.

Алгоритм со случайным поиском, RND

C_AO_RND:50
=============================
5 Hilly's; Func runs: 10000; result: 0.5024853724464499
25 Hilly's; Func runs: 10000; result: 0.3284469438564529
500 Hilly's; Func runs: 10000; result: 0.2600678718550755
=============================
5 Forest's; Func runs: 10000; result: 0.3989291459162246
25 Forest's; Func runs: 10000; result: 0.22913381881119183
500 Forest's; Func runs: 10000; result: 0.16727444696703453
=============================
5 Megacity's; Func runs: 10000; result: 0.2753846153846154
25 Megacity's; Func runs: 10000; result: 0.14861538461538465
500 Megacity's; Func runs: 10000; result: 0.09890769230769311
=============================
All score: 2.40925

Вот мы подошли к алгоритму RND. Этот простейший метод оптимизации опередил многих уважаемых и известных участников этого уникального соревнования. Напомню, стратегия алгоритма "RND" заключается в 50% вероятности: либо выбрать координату случайно выбранной особи из популяции, либо сгенерировать случайную координату с равномерным распределением. Тем не менее это позволило алгоритму подняться до середины списка участников. Это связано с его широкими возможностями исследования пространства, хотя говорить о точности в данном случае не приходится.

Эволюция социальных групп, ESG

C_AO_ESG:200:100:0.1:2.0:10.0
=============================
5 Hilly's; Func runs: 10000; result: 0.3695915822772909
25 Hilly's; Func runs: 10000; result: 0.3396716009249312
500 Hilly's; Func runs: 10000; result: 0.2727013729189837
=============================
5 Forest's; Func runs: 10000; result: 0.2956316169252261
25 Forest's; Func runs: 10000; result: 0.2875217303660672
500 Forest's; Func runs: 10000; result: 0.16124201361354124
=============================
5 Megacity's; Func runs: 10000; result: 0.30769230769230765
25 Megacity's; Func runs: 10000; result: 0.306153846153846
500 Megacity's; Func runs: 10000; result: 0.13183076923077003
=============================
All score: 2.47204

Алгоритм ESG проявляет неплохие возможности в исследовании пространства поиска, разделяясь на характерные группы. Однако следует отметить, что он оставляет без внимания дальние участки пространства, что может привести к проблемам при исследовании всего масштаба задачи. Также наблюдаются признаки застревания в значимых локальных экстремумах, что может затруднять достижение глобального оптимума. Несмотря на это, алгоритм демонстрирует значительные успехи при работе с дискретной функцией Megacity, подчеркивая его потенциал в определенных условиях и задачах.

Алгоритм интеллектуальных капель воды, IWDm

C_AO_IWDm:50;10;3.0
=============================
5 Hilly's; Func runs: 10000; result: 0.4883273901756646
25 Hilly's; Func runs: 10000; result: 0.34290016593207995
500 Hilly's; Func runs: 10000; result: 0.2581256124908963
=============================
5 Forest's; Func runs: 10000; result: 0.5119191969436073
25 Forest's; Func runs: 10000; result: 0.2564038040639046
500 Forest's; Func runs: 10000; result: 0.1675925588605327
=============================
5 Megacity's; Func runs: 10000; result: 0.34153846153846157
25 Megacity's; Func runs: 10000; result: 0.15784615384615389
500 Megacity's; Func runs: 10000; result: 0.09889230769230851
=============================
All score: 2.62355

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

В обычной рейтинговой таблице этот алгоритм не входит в число лучших, однако в данном конкретном испытании он проявил впечатляющие успехи по сравнению с другими алгоритмами. IWDm может быть рекомендован для использования на начальных этапах оптимизации, чтобы затем перейти к более точным алгоритмам, обогащая и улучшая процесс оптимизации в целом.

Рой частиц, PSO

C_AO_PSO:50;0.8;0.4;0.4
=============================
5 Hilly's; Func runs: 10000; result: 0.5548169875802522
25 Hilly's; Func runs: 10000; result: 0.3407594364160912
500 Hilly's; Func runs: 10000; result: 0.2525297014321252
=============================
5 Forest's; Func runs: 10000; result: 0.4573903259815636
25 Forest's; Func runs: 10000; result: 0.27561812346057046
500 Forest's; Func runs: 10000; result: 0.19079124396445962
=============================
5 Megacity's; Func runs: 10000; result: 0.3092307692307693
25 Megacity's; Func runs: 10000; result: 0.14923076923076928
500 Megacity's; Func runs: 10000; result: 0.09553846153846236
=============================
All score: 2.62591

Алгоритм PSO поразил своими внезапно высокими результатами в данном эксперименте, продемонстрировав ещё более высокую скорость перемещения в неизведанные территории по сравнению с предшествующим алгоритмом IWDm. Этот внезапный успех можно объяснить тем, что частицы в PSO обладают начальной скоростью, выбранной случайным образом на первой итерации, что позволяет им быстро покинуть исходное положение. Начальные шаги алгоритма напоминают танец частиц по всему пространству, пока они не находят свою особую гармонию. К сожалению, эта гармония не всегда приводит к глобальному оптимуму, отсутствие уточняющих качеств замедляет достижение идеального решения.

PSO, подобно IWDm, может быть рекомендован для использования на начальных этапах оптимизации, где его способность быстро исследовать пространство поиска может быть ключом к обнаружению перспективных решений.

Алгоритм летучих мышей, BA

C_AO_BA:50;0.0;1.0;0.0;1.5;0.0;1.0;0.3;0.3
=============================
5 Hilly's; Func runs: 10000; result: 0.5127608047854995
25 Hilly's; Func runs: 10000; result: 0.4239882910506281
500 Hilly's; Func runs: 10000; result: 0.3127353914885268
=============================
5 Forest's; Func runs: 10000; result: 0.4355521825589907
25 Forest's; Func runs: 10000; result: 0.29303187383086005
500 Forest's; Func runs: 10000; result: 0.19433130092541523
=============================
5 Megacity's; Func runs: 10000; result: 0.28769230769230764
25 Megacity's; Func runs: 10000; result: 0.16030769230769232
500 Megacity's; Func runs: 10000; result: 0.10907692307692407
=============================
All score: 2.72948

Летучие мыши в алгоритме BA имеют удивительное свойство быстро находить область глобального экстремума, моментально перемещаясь на самых первый итерациях. Но формула звуковых импульсов в этом поисковом методе имеет такое свойство, что перемещения рукокрылых быстро затухают, хотя визуально видна очевидная необходимость продолжать поиск. В обычном рейтинге BA имеет невысокое положение, но в этом испытании занимает строку в верхней части таблицы.

 Оптимизация инвазивных сорняков, IWO

C_AO_IWO:50;12;5;2;0.2;0.01
=============================
5 Hilly's; Func runs: 10000; result: 0.4570149872637351
25 Hilly's; Func runs: 10000; result: 0.4252105325836707
500 Hilly's; Func runs: 10000; result: 0.28299287471456525
=============================
5 Forest's; Func runs: 10000; result: 0.43322917175445896
25 Forest's; Func runs: 10000; result: 0.33438950288190694
500 Forest's; Func runs: 10000; result: 0.18632383795879612
=============================
5 Megacity's; Func runs: 10000; result: 0.3061538461538461
25 Megacity's; Func runs: 10000; result: 0.24369230769230765
500 Megacity's; Func runs: 10000; result: 0.12887692307692397
=============================
All score: 2.79788

Алгоритм инвазивных сорняков также подчиняется зависимости скорости распространения от текущей итерации, как и алгоритм летучих мышей (Bat Algorithm, BA). Однако в данном случае агенты способны исследовать пространство более эффективно и полно, что позволяет им быстрее и точнее находить оптимальные решения, учитывая ключевые особенности функции и области глобального максимума, по сравнению с BA. Но, если расстояние от точки старта до цели велико, то сорняки не достигают области глобального максимума, особенно это заметно на функции Megacity, то есть, агенты застревают в ближайшем значимом экстремуме.

Искусственная пчелиная колония, ABC

C_AO_ABC:50;45;10;0.1;0.4
=============================
5 Hilly's; Func runs: 10000; result: 0.5969246550857782
25 Hilly's; Func runs: 10000; result: 0.3899058056869557
500 Hilly's; Func runs: 10000; result: 0.26574506946962373
=============================
5 Forest's; Func runs: 10000; result: 0.536535405336652
25 Forest's; Func runs: 10000; result: 0.29048311417293887
500 Forest's; Func runs: 10000; result: 0.17322987568991322
=============================
5 Megacity's; Func runs: 10000; result: 0.3307692307692308
25 Megacity's; Func runs: 10000; result: 0.18492307692307694
500 Megacity's; Func runs: 10000; result: 0.11512307692307773
=============================
All score: 2.88364

Интересное поведение алгоритма ABC проявляется в его способности разбивать популяцию на отдельные рои, которые активно исследуют локальные экстремумы. Однако возможно, у алгоритма недостаточно уточняющих качеств, что отражается на его позиции в стандартной рейтинговой таблице. Тем не менее существует потенциал для улучшения и использования его поисковых способностей в гибридных алгоритмах. Путем интеграции с другими методами оптимизации можно значительно улучшить его способность находить глобальные оптимумы и повысить общую эффективность в различных задачах оптимизации.

Алгоритм эволюции разума, MEC

C_AO_MEC:50;10;0.4
=============================
5 Hilly's; Func runs: 10000; result: 0.5566946043237988
25 Hilly's; Func runs: 10000; result: 0.430203412538813
500 Hilly's; Func runs: 10000; result: 0.2724348221662864
=============================
5 Forest's; Func runs: 10000; result: 0.4548936450507163
25 Forest's; Func runs: 10000; result: 0.3156014530351309
500 Forest's; Func runs: 10000; result: 0.17625852850331755
=============================
5 Megacity's; Func runs: 10000; result: 0.3415384615384615
25 Megacity's; Func runs: 10000; result: 0.23107692307692304
500 Megacity's; Func runs: 10000; result: 0.1186615384615393
=============================
All score: 2.89736

Алгоритм MEC поражает своей скоростью, мгновенно обнаруживая практически все значимые локальные экстремумы и успешно выявляя область глобального максимума. Несмотря на небольшое отставание от результатов обычного тестирования, MEC продолжает демонстрировать высокую стабильность и эффективность в поиске оптимальных решений.

Алгоритм оптимизации с кукушкой, COAm

C_AO_COAm:100;40;0.6;0.6;0.63
=============================
5 Hilly's; Func runs: 10000; result: 0.600998666320958
25 Hilly's; Func runs: 10000; result: 0.42709404776275245
500 Hilly's; Func runs: 10000; result: 0.26571090745735276
=============================
5 Forest's; Func runs: 10000; result: 0.5533129896276743
25 Forest's; Func runs: 10000; result: 0.30413063297063025
500 Forest's; Func runs: 10000; result: 0.1703031415266755
=============================
5 Megacity's; Func runs: 10000; result: 0.3261538461538461
25 Megacity's; Func runs: 10000; result: 0.2046153846153847
500 Megacity's; Func runs: 10000; result: 0.1112615384615393
=============================
All score: 2.96358

Наш "середнячок" в обычной рейтинговой таблице COAm проявляет удивительную скорость перемещения в пространстве поиска, легко выбираясь из глобального минимума. Однако у него возникают определенные сложности с застреванием в значимых локальных экстремумах, не позволяя ему достичь глобального максимума.

Алгоритмы искусственной микро-иммунной системы, Micro-AIS

C_AO_Micro_AIS:50:1:2:0.3
=============================
5 Hilly's; Func runs: 10000; result: 0.6193671060348247
25 Hilly's; Func runs: 10000; result: 0.4656896752001433
500 Hilly's; Func runs: 10000; result: 0.24995620778886124
=============================
5 Forest's; Func runs: 10000; result: 0.7121901446084455
25 Forest's; Func runs: 10000; result: 0.4254191301238518
500 Forest's; Func runs: 10000; result: 0.211517515004865
=============================
5 Megacity's; Func runs: 10000; result: 0.2676923076923077
25 Megacity's; Func runs: 10000; result: 0.16461538461538466
500 Megacity's; Func runs: 10000; result: 0.10927692307692398
=============================
All score: 3.22572

В алгоритме Micro-AIS можно выделить очень равномерное облако, создаваемое антигенами, что придает процессу определенный порядок, напоминающий гармонию, а не хаос. Несмотря на это, его уточняющие свойства требуют некоторого улучшения, хотя алгоритм обладает хорошими поисковыми способностями. Однако он также подвержен застреванию в локальных ловушках.

Гармонический поиск, HS

C_AO_HS:50;0.9;0.1;0.2
=============================
5 Hilly's; Func runs: 10000; result: 0.602082991833691
25 Hilly's; Func runs: 10000; result: 0.5533985889779909
500 Hilly's; Func runs: 10000; result: 0.2820448101527182
=============================
5 Forest's; Func runs: 10000; result: 0.6503798132320532
25 Forest's; Func runs: 10000; result: 0.5104503170911219
500 Forest's; Func runs: 10000; result: 0.19337757947865844
=============================
5 Megacity's; Func runs: 10000; result: 0.30769230769230765
25 Megacity's; Func runs: 10000; result: 0.29538461538461525
500 Megacity's; Func runs: 10000; result: 0.12826153846153937
=============================
All score: 3.52307

В данной постановке задачи HS проявляет впечатляющие поисковые способности и высокую скорость перемещения по пространству в поисках глобального максимума. Однако при столкновении с первым значительным локальным экстремумом он замедляется из-за зависимости от номера текущей эпохи. Тем не менее этот недостаток проявляется лишь на дискретной функции Megacity, в то время как на гладких функциях Hilly и Forest его поисковые возможности остаются впечатляющими. В рейтинговой таблице Гармонический поиск занимает верхние позиции, продемонстрировав свою эффективность так же и в данном тестировании.

Алгоритм оптимизации спиральной динамики, SDOm

C_AO_SDOm:100;0.5;4.0;10000.0
=============================
5 Hilly's; Func runs: 10000; result: 0.7132463872323508
25 Hilly's; Func runs: 10000; result: 0.43264564401427485
500 Hilly's; Func runs: 10000; result: 0.25506574720969816
=============================
5 Forest's; Func runs: 10000; result: 0.804287574819851
25 Forest's; Func runs: 10000; result: 0.4249161540200845
500 Forest's; Func runs: 10000; result: 0.2193817986301354
=============================
5 Megacity's; Func runs: 10000; result: 0.4938461538461539
25 Megacity's; Func runs: 10000; result: 0.22030769230769232
500 Megacity's; Func runs: 10000; result: 0.11410769230769328
=============================
All score: 3.67780

В топ списка тестирования внезапно входит алгоритм SDOm. Этот алгоритм, опирающийся на гармонические колебания, проявляет себя весьма необычно и уникально в рамках данного эксперимента, оставляя за собой загадку, которую сложно разгадать. Шарик маятника, подвешенный на верёвке, может внезапно оторваться и отправиться в свободный полёт. Поведение алгоритма обладает множеством аспектов, делающих его особенным, и предсказать условия, приводящие к такому неожиданному поведению, практически невозможно. Именно поэтому сложно рекомендовать его для широкого спектра задач в его текущем виде. Однако в сочетании с другими алгоритмами, например, передача части агентов из общей популяции в управление SDOm может помочь выявить циклические закономерности в поставленной задаче.

Гибридный алгоритм оптимизации бактериального поиска с генетическим алгоритмом, BFO-GA

C_AO_BFO_GA:50;0.01;0.8;50;10.0
=============================
5 Hilly's; Func runs: 10000; result: 0.8233662999080027
25 Hilly's; Func runs: 10000; result: 0.5031148772790799
500 Hilly's; Func runs: 10000; result: 0.27434497581097494
=============================
5 Forest's; Func runs: 10000; result: 0.8611314745481611
25 Forest's; Func runs: 10000; result: 0.45038118646429437
500 Forest's; Func runs: 10000; result: 0.1806538222176609
=============================
5 Megacity's; Func runs: 10000; result: 0.3907692307692308
25 Megacity's; Func runs: 10000; result: 0.272
500 Megacity's; Func runs: 10000; result: 0.11061538461538559
=============================
All score: 3.86638

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

Стохастический диффузионный поиск, SDSm

C_AO_SDSm:100;100;0.05
=============================
5 Hilly's; Func runs: 10000; result: 0.6838494804548411
25 Hilly's; Func runs: 10000; result: 0.6796828568841194
500 Hilly's; Func runs: 10000; result: 0.32584905164208583
=============================
5 Forest's; Func runs: 10000; result: 0.6703019775594297
25 Forest's; Func runs: 10000; result: 0.6398441335988195
500 Forest's; Func runs: 10000; result: 0.24899123954861618
=============================
5 Megacity's; Func runs: 10000; result: 0.5307692307692308
25 Megacity's; Func runs: 10000; result: 0.49446153846153845
500 Megacity's; Func runs: 10000; result: 0.14973846153846293
=============================
All score: 4.42349

При обсуждении алгоритма SDSm не совсем уместно акцентировать внимание на скорости, с которой агенты распространяются по пространству поиска, поскольку их координаты задаются внутри случайно выбранных секторов среды. По сути, эти агенты мгновенно распределяются по всему полю поиска уже после первой итерации. Этот уникальный подход приводит к замечательным результатам, демонстрируя эффективность стратегии алгоритма.

Что отличает SDSm, так это его способность использовать силу случайности, повышая вероятность того, что ни один уголок пространства поиска не останется неисследованным. Принимая во внимание эту стохастическую природу, алгоритм может эффективно охватывать огромные территории и раскрывать ценную информацию о поверхности функции, что делает его действительно мощным инструментом для решения проблем.

Бинарный генетический алгоритм, BGA

C_AO_BGA:50:50:1.0:3:0.001:0.7:3
=============================
5 Hilly's; Func runs: 10000; result: 1.0
25 Hilly's; Func runs: 10000; result: 1.0
500 Hilly's; Func runs: 10000; result: 0.8703352617259978
=============================
5 Forest's; Func runs: 10000; result: 0.8872607468925364
25 Forest's; Func runs: 10000; result: 0.8177419261242314
500 Forest's; Func runs: 10000; result: 0.2603521654104144
=============================
5 Megacity's; Func runs: 10000; result: 0.7492307692307694
25 Megacity's; Func runs: 10000; result: 0.5833846153846155
500 Megacity's; Func runs: 10000; result: 0.24415384615384667
=============================
All score: 6.41246

Бинарный генетический алгоритм (BGA) извлекают выгоду из мутации генов, позволяя им мгновенно достигать любой области пространства поиска без дополнительных итераций. Однако в этом конкретном сценарии тестирования BGA выходит в лидеры несмотря на то, что иногда попадает в ловушку локального оптимума. В этом отношении SDSm представляется более предпочтительным, поскольку демонстрирует лучшую способность избегать подобных ситуаций.

Тем не менее следует отдать должное BGA за достижение в целом наилучших результатов, даже если принять во внимание его недостатки. Это достижение подчеркивает потенциал алгоритма и важность достижения баланса между исследованием и эксплуатацией в процессе поиска. Если мы углубимся в сравнение, станет очевидно, что каждый алгоритм имеет свои уникальные сильные и слабые стороны.

Подводя итог, можно сказать, что BGA демонстрирует впечатляющие результаты в данном тесте, закрепляя за собой позицию лидера.


2. Доработка агента для BGA

Чтобы осуществить это исследование понадобилось доработать код алгоритма BGA под эту определенную задачу для тестирования. Эта возможность - размещать агентов в произвольном месте пространства поиска может быть очень полезна при необходимости стартовать оптимизацию с определённых пользователем сетов.

В BGA решения задачи представлены в виде бинарного кода, поэтому для размещения агентов популяции в заданных координатах требуется преобразовать значения координат из вещественно представления в бинарный, в данном случае в бинарный код Грея.

Добавим в описания агента метод "DoubleToGene", который преобразует значение типа "double" в генетическое представление в массиве "genes". Основные действия в работе этого метода:

  • Если входное число меньше минимального допустимого значения, функция создает массив из нулей (вещественное число "0.0" в представлении по коду Грея), чтобы гарантировать, что значение остается в пределах допустимого диапазона.
  • Если входное число превышает максимальное допустимое значение, функция создает массив, который копирует значения из исходного массива, содержащего (максимально допустимое число в кодировке Грея, это число сохранено для подобных случаев, когда необходимо вернуться в диапазон, если произошёл выход за пределы диапазона в большую сторону).
  • В случае, если число находится в пределах допустимого диапазона, оно масштабируется и преобразуется в код Грея. Затем это значение сохраняется в массиве для использования в генетическом представлении.

Таким образом, метод "DoubleToGene" выполняет преобразование вещественного значения в генетическое представление и записывает его в соответствующий массив "генов". Функция обрабатывает случаи, когда входное значение выходит за пределы допустимого диапазона, инициализируя или копируя определенные массивы и досрочно прекращая выполнение. В противном случае функция масштабирует значение, преобразует целую и дробную части в код Грея и объединяет их в окончательное генетическое представление.

Поправленный код агента BGA:

//——————————————————————————————————————————————————————————————————————————————
struct S_Agent
{
  void Init (const int coords, const double &min [], const double &max [], int doubleDigitsInChromo)
  {
    ArrayResize(c, coords);
    f = -DBL_MAX;

    ArrayResize(genes, coords);
    ArrayResize(chromosome, 0, 1000);

    for(int i = 0; i < coords; i++)
    {
      genes [i].Init(min [i], max [i], doubleDigitsInChromo);
      ArrayCopy(chromosome, genes [i].gene, ArraySize(chromosome), 0, WHOLE_ARRAY);
    }
  }

  void ExtractGenes ()
  {
    uint pos = 0;

    for (int i = 0; i < ArraySize (genes); i++)
    {
      c [i] = genes [i].ToDouble (chromosome, pos);
      pos  += genes [i].length;

    }
  }

  void DoubleToGene (const double val, const int genePos)
  {
    double value = val;

    //--------------------------------------------------------------------------
    if (value < genes [genePos].rangeMin)
    {
      ArrayInitialize(genes [genePos].gene, 0);
      ArrayCopy (chromosome, genes [genePos].gene, genePos * genes [genePos].length, 0, WHOLE_ARRAY);
      return;
    }

    //--------------------------------------------------------------------------
    else
    {
      if (value > genes [genePos].rangeMax)
      {
        ArrayCopy (chromosome, genes [genePos].geneMax, genePos * genes [genePos].length, 0, WHOLE_ARRAY);
        return;
      }
    }

    //--------------------------------------------------------------------------
    value = Scale(value, genes [genePos].rangeMin, genes [genePos].rangeMax, 0.0, genes [genePos].maxCodedDistance);

    DecimalToGray ((ulong)value, genes [genePos].integPart);

    value = value - (int)value;

    value *= genes [genePos].digitsPowered;

    DecimalToGray ((ulong)value, genes [genePos].fractPart);

    ArrayInitialize(genes [genePos].gene, 0);

    uint   integGrayDigits = genes [genePos].integGrayDigits;
    uint   fractGrayDigits = genes [genePos].fractGrayDigits;
    uint   digits = ArraySize (genes [genePos].integPart);

    if (digits > 0) ArrayCopy (genes [genePos].gene, genes [genePos].integPart, integGrayDigits - digits, 0, WHOLE_ARRAY);

    digits = ArraySize (genes [genePos].fractPart);

    if (digits > 0) ArrayCopy (genes [genePos].gene, genes [genePos].fractPart, genes [genePos].length - digits, 0, WHOLE_ARRAY);

    ArrayCopy (chromosome, genes [genePos].gene, genePos * genes [genePos].length, 0, WHOLE_ARRAY);
  }

  void InjectGeneToChromosome ()
  {

  }

  //----------------------------------------------------------------------------
  double Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX)
  {
    if (OutMIN == OutMAX) return (OutMIN);
    if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0));
    else
    {
      if (In < InMIN) return OutMIN;
      if (In > InMAX) return OutMAX;

      return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);
    }
  }

  double c [];           //coordinates
  double f;              //fitness

  S_BinaryGene genes []; //there are as many genes as there are coordinates
  char chromosome    [];
};
//——————————————————————————————————————————————————————————————————————————————


3. Выводы

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

POES

(PO)ES на Megacity

SDOm

SDOm на Megacity

BFO_GA

BFO_GA на Megacity

SDSm

SDSm на Megacity

BGA

BGA на Megacity

Ниже представлена итоговая сравнительная таблица, на которой детально отображена работа каждого алгоритма на тестовых функциях.

Tab

Рисунок 1. Цветовая градация алгоритмов по соответствующим тестам. Белым цветом подсвечены результаты больше или равные 0.99.

Chart

Рисунок 2. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше,

где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы).

В завершении необходимо специально подчеркнуть, что все выводы и суждения по каждому алгоритму были сделаны исключительно в рамках проведённого эксперимента.

Из всего обсуждения и анализа поведения популяционных алгоритмов оптимизации вытекает важный вывод: успех работы алгоритмов сильно зависит от начальных условий их применения. Для некоторых методов, таких как DE, EM, GSA, ACOm, испытания с выходом из точки минимума тестовой функции могут оказаться настолько сложными, что приводят к затруднениям в начале работы. В то же время, для других, таких как (P+O)ES, ESG (которые изначально занимали верхние позиции в рейтинге, но стали аутсайдерами), эффективность резко снижается. Напротив, для алгоритмов типа PSO, GWO, SFL, BA, ABC специально выбранные начальные координаты могут значительно повысить результаты. Некоторые алгоритмы, BFO-GA, SDOm, даже продемонстрировали выдающуюся производительность при таком подходе, превосходя случайную равномерную инициализацию агентов.

Необходимо также отметить, что другие алгоритмы, такие как IWO, HS, SDSm, BGA, показали универсальную устойчивость, мало зависящую от стартового положения агентов. Этот специальный эксперимент подчеркнул, что хотя некоторые алгоритмы показывали слабые результаты в ходе тестирования, они все же демонстрировали впечатляющие способности в определенных моментах эксперимента. Некоторые из них успешно исследовали пространство в начале процесса, в то время как другие смогли значительно улучшить результаты в последующих этапах. Эти уникальные особенности каждого алгоритма можно успешно комбинировать и гибридизировать, усиливая их положительные стороны и уменьшая недостатки, что в конечном итоге может привести к созданию более эффективных методов оптимизации.

Прикрепленные файлы |
Загрузить ZIP
The_world_of_AO_Resistance.ZIP (1693.99 KB)
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.

Другие статьи автора

Перейти к обсуждению на форуме трейдеров
Шаблоны проектирования в MQL5 (Часть I): Порождающие шаблоны (Creational Patterns) Шаблоны проектирования в MQL5 (Часть I): Порождающие шаблоны (Creational Patterns)
Существуют методы, которые можно использовать для решения типовых задач. Поняв один раз, как использовать эти методы, можно затем эффективно писать программы и применять концепцию DRY ("Не повторяйся"). В этом контексте очень полезными оказываются шаблоны проектирования, которые могут давать решения хорошо описанных и повторяющихся проблем.
Нейросети — это просто (Часть 80): Генеративно-состязательная модель Трансформера графов (GTGAN) Нейросети — это просто (Часть 80): Генеративно-состязательная модель Трансформера графов (GTGAN)
В данной статье я предлагаю Вам познакомиться с алгоритмом GTGAN, который был представлен в январе 2024 года для решения сложных задач по созданию архитектурного макета с ограничениями на граф.
Гибридизация популяционных алгоритмов. Последовательная и параллельная схема Гибридизация популяционных алгоритмов. Последовательная и параллельная схема
В статье мы погрузимся в мир гибридизации алгоритмов оптимизации, рассмотрев три ключевых типа: смешивание стратегий, последовательную и параллельную гибридизации. Мы проведем серию экспериментов, сочетая и тестируя соответствующие алгоритмы оптимизации.
Разработка MQTT-клиента для MetaTrader 5: методология TDD (Часть 4) Разработка MQTT-клиента для MetaTrader 5: методология TDD (Часть 4)
Статья является четвертой частью серии, описывающей этапы разработки нативного MQL5-клиента для протокола MQTT. В этой части мы рассматриваем свойства MQTT v5.0, их семантику, то, как мы читаем некоторые из них, а также приводим краткий пример того, как свойства можно использовать для расширения протокола.