Алгоритм поиска в окрестности — Across Neighbourhood Search (ANS)
149
0
1. Введение
В современном мире разработка эффективных методов оптимизации играет важную роль в решении разнообразных задач, начиная от инженерных применений до научных исследований в области машинного обучения и искусственного интеллекта. В данном контексте метаэвристические эволюционные алгоритмы представляют собой мощные инструменты для решения сложных задач оптимизации. Однако, для дальнейшего улучшения их производительности и эффективности, необходимо постоянное развитие и модификация существующих методов, а также разработка новых алгоритмов.
В данной статье мы познакомимся с алгоритмом оптимизации, известным как Across Neighborhood Search (ANS), предложенным Guohua Wu в 2014 году и основанным на поиске по популяции для числовой оптимизации. Разработанный алгоритм ANS представляет собой значительный шаг вперед в области оптимизации, обещая решать разнообразные задачи в реальном мире с высокой эффективностью и точностью, так ли это, подтвердим или опровергнем - об этом ниже. Основная идея ANS состоит в моделировании поведения многоагентной системы, где каждый агент перемещается по пространству решений, взаимодействуя с соседями и обмениваясь информацией. Этот подход даёт возможность отлично исследовать пространство поиска, сочетая локальную и глобальную оптимизацию.
Мы познакомимся с подробным описанием структуры алгоритма ANS и принципами его работы, а так же проведем сравнительный анализ с уже существующими методами оптимизации. Разработанный алгоритм ANS открывает нам новую дверь в области оптимизации, позволяя решать широкий спектр задач с высокой производительностью. Кроме того, в контексте развития искусственного интеллекта важно отметить, что алгоритм ANS представляет собой важный шаг в направлении создания более гибких и интеллектуальных методов оптимизации, способных учитывать специфику задачи и динамику окружающей среды.
2. Реализация алгоритма
Алгоритм Across Neighborhood Search, ANS (поиск в окрестности) является методом оптимизации, использующим идеи из области эволюционных алгоритмов и метаэвристик, и предназначен для поиска оптимальных решений в пространстве параметров задачи.
Отметим основные особенности ANS:
- Поиск в окрестности: агенты исследуют окрестности текущих решений, что позволяет более эффективно находить локальные оптимумы.
- Использование нормального распределения: ANS использует нормальное распределение для генерации новых значений параметров.
- Коллекции решений: в ANS используются коллекции лучших решений, которые помогают ориентировать алгоритм сразу в нескольких перспективных направлениях.
В ANS группа индивидов совместно производит поиск в пространстве решений для оптимального выполнения рассматриваемой задачи оптимизации. Основная идея алгоритма заключается в поддержании и динамическом обновлении коллекции превосходных решений, найденных индивидами до сих пор. В каждом поколении индивид напрямую ищет по соседству несколько отличных решений в соответствии с нормальным распределением вероятностей. Таким образом эксплуатируется идея о наличии сразу нескольких потенциально хороших решений, так как заранее неизвестно какое из них будет наилучшим.
Ниже рассмотрим полное описание алгоритма ANS с формулами и этапами, согласно авторской концепции. ANS выполняет следующие шаги:
1. Инициализация параметров:
- Размер популяции m
- Коллекция множества лучших решений c
- Стандартное отклонение гауссовского распределения sigma
- Размерность пространства поиска D
- Максимальное количество поколений MaxG
2. Инициализация популяции. Случайная инициализация позиции каждой особи в популяции в пространстве поиска.
3. Обновление лучших решений. Каждая особь в популяции обновляет свою текущую позицию, исследуя окрестности лучших решений из коллекции с помощью нормального распределения.
4. Выбор координаты для поиска. Выбор случайного числа n (across-search degree) для определения текущей координаты положения индивида в пространстве решений.
5. Обновление позиции особи. Обновление позиции особи i в соответствии с предыдущим шагом.
Формулы и операции:
1. Обновление позиции pos_i особи i (исследование окрестности решения из коллекции):
- Позиция особи i обновляется с помощью распределения Гаусса: pos_i = r_g + G (r_g - pos_i), где:
- G - случайное значение из гауссовского распределения
- r_g - позиция лучшего решения из коллекции
2. Обновление позиции pos_i особи i (исследование окрестности собственного лучшего решения индивида):
- Позиция особи i обновляется с помощью распределения Гаусса: pos_i = r_i + G (r_i - pos_i), где:
- G - случайное значение из гауссовского распределения
- r_i - позиция лучшего решения индивида
3. Обновление множества лучших решений:
- Коллекция лучших решений обновляется на основе новых позиций особей.
Таким образом, формулы отражают механизм поиска особи i в окрестностях своего лучшего решения r_i, а также в окрестностях других лучших решений r_g из коллекции R. Эти шаги алгоритма представляют собой основную логику работы метода ANS (Across Neighbourhood Search) для решения задач оптимизации. Он включает в себя инициализацию параметров, случайную инициализацию позиций особей, обновление позиций особей с учетом окрестностей лучших решений и обновление коллекции лучших решений. Алгоритм продолжает работу до выполнения условия останова.
Поиск на основе лучших решений или индивидов - это общая и часто используемая техника поиска в алгоритмах на основе популяционных стратегий, хотя процессы, реализующие такой механизм поиска, могут отличаться для разных алгоритмов оптимизации. В данном случае, по сути, кроме основной популяции агентов, вводится дополнительная популяция - коллекция лучших решений (потенциальных направлений поиска). Размер коллекции определяется во внешних параметрах алгоритма и может быть задан как меньше размера основной популяции, так и больше.
Стратегия поиска в алгоритме ANS начинается с наполнения коллекции лучших решений и переходит к поиску в окрестности лучших решений коллекции и лучших индивидуальных решений каждого агента. Ключевую роль в алгоритме играет размер стандартного отклонения sigma. Малое значение sigma обеспечивает более широкое исследование пространства поиска, а более высокие значения обеспечивают уточнение решений, сужая их окрестности. Этот параметр алгоритма отвечает за баланс между интенсификацией и диверсификацией поиска. В некоторых алгоритмах этот баланс привязывают к номеру текущей эпохи, чтобы обеспечивать динамическое изменение баланса между исследованием и уточнением, но в данном случае авторы определили регулировку баланса в качестве внешнего параметра ANS.
Таким образом, алгоритм ANS сочетает в себе эксплуатацию лучших найденных решений (через поиск в их окрестностях) и исследование пространства решений (через поиск в окрестностях собственных лучших решений индивидов). Это теоретически должно обеспечивать хороший баланс между интенсификацией и диверсификацией поиска.
Теперь давайте перейдём к написанию и разбору кода алгоритма ANS. Определим структуру "S_ANS_Agent", которая будет использоваться для представления агентов в алгоритме ANS. Поля структуры:
- c: массив для хранения координат агента.
- cBest: массив для хранения лучших координат агента.
- f: значение приспособленности (fitness) агента.
- fBest: лучшее значение приспособленности агента.
- Init(int coords): метод инициализации, задает размеры массивов "c" и "cBest" и устанавливает начальные значения "f" и "fBest".
Эта часть кода представляет базовую структуру агента, массив которых (агентов) будет представлять основную популяцию в алгоритме ANS.
//—————————————————————————————————————————————————————————————————————————————— struct S_ANS_Agent { double c []; //coordinates double cBest []; //best coordinates double f; //fitness double fBest; //best fitness void Init (int coords) { ArrayResize (c, coords); ArrayResize (cBest, coords); f = -DBL_MAX; fBest = -DBL_MAX; } }; //—————————————————————————————————————————————————————————————————————————————
Для описания коллекции лучших решений, напишем структуру "S_Collection", которая будет использоваться для хранения информации о лучших координатах в пространстве поиска и соответствующем им значении приспособленности. Структура содержит следующие поля:
- c: массив для хранения координат.
- f: значение приспособленности (fitness) для данного решения задачи в коллекции.
- Init(int coords): метод инициализации, задает размер массива "c" и устанавливает начальное значение "f" на минимально возможное значение типа "double".
//—————————————————————————————————————————————————————————————————————————————— struct S_Collection { double c []; //coordinates double f; //fitness void Init (int coords) { ArrayResize (c, coords); f = -DBL_MAX; } }; //——————————————————————————————————————————————————————————————————————————————
Объявим класс "C_AO_ANS", который является наследником базового класса "C_AO" и представляет собой реализацию алгоритма Across Neighbourhood Search (ANS). Вот некоторые ключевые моменты:
- ao_name, ao_desc, ao_link: свойства, описывающие алгоритм ANS.
- popSize: размер популяции.
- collectionSize, sigma, range, collChoiceProbab: параметры алгоритма ANS.
- SetParams(): метод для установки параметров.
- Init(), Moving(), Revision(): методы для инициализации, перемещения агентов и обновления популяции и коллекции решений.
- S_ANS_Agent, S_Collection: структуры для хранения данных агентов и коллекции.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_ANS : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_ANS () { } C_AO_ANS () { ao_name = "ANS"; ao_desc = "Across Neighbourhood Search"; ao_link = "https://www.mql5.com/ru/articles/15049"; popSize = 50; //population size collectionSize = 20; //Best solutions collection sigma = 3.0; //Form of normal distribution range = 0.5; //Range of values dispersed collChoiceProbab = 0.8; //Collection choice probab ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "collectionSize"; params [1].val = collectionSize; params [2].name = "sigma"; params [2].val = sigma; params [3].name = "range"; params [3].val = range; params [4].name = "collChoiceProbab"; params [4].val = collChoiceProbab; } void SetParams () { popSize = (int)params [0].val; collectionSize = (int)params [1].val; sigma = params [2].val; range = params [3].val; } bool Init (const double &rangeMinP [], //minimum search range const double &rangeMaxP [], //maximum search range const double &rangeStepP [], //step search const int epochsP = 0); //number of epochs void Moving (); void Revision (); //---------------------------------------------------------------------------- int collectionSize; //Best solutions collection double sigma; //Form of normal distribution double range; //Range of values dispersed double collChoiceProbab; //Collection choice probab S_ANS_Agent agent []; private: //------------------------------------------------------------------- S_Collection coll []; S_Collection collTemp []; }; //——————————————————————————————————————————————————————————————————————————————
Метод "Init" инициализирует параметры алгоритма ANS (Across Neighbourhood Search).
- rangeMinP, rangeMaxP, rangeStepP: массивы, представляющие минимальный, максимальный и шаг диапазона поиска.
- epochsP: количество эпох (поколений).
Внутри метода:
- Проверяется успешная инициализация стандартных параметров с помощью "StandardInit".
- Создаются массивы агентов "agent" и коллекций "coll" (вторая популяция для хранения лучших решений) и "collTemp" (временный массив для сортировки коллекции).
- Для каждого агента и коллекции вызывается метод "Init", чтобы задать начальные значения.
Этот метод играет важную роль в подготовке алгоритма ANS к выполнению оптимизации. Важно отметить, что массивы "coll" и "collTemp" инициализируются с двойным размером по отношению к параметру "collectionSize". Это делается для того, чтобы новые агенты, добавляемые в коллекцию, попадали во вторую половину массива. Последующая сортировка происходит по всей коллекции, а для дальнейшей работы используется только первая половина, содержащая лучших агентов.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_ANS::Init (const double &rangeMinP [], //minimum search range const double &rangeMaxP [], //maximum search range const double &rangeStepP [], //step search const int epochsP = 0) //number of epochs { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- ArrayResize (agent, popSize); for (int i = 0; i < popSize; i++) agent [i].Init (coords); ArrayResize (coll, collectionSize * 2); ArrayResize (collTemp, collectionSize * 2); for (int i = 0; i < collectionSize * 2; i++) { coll [i].Init (coords); collTemp [i].Init (coords); } return true; } //——————————————————————————————————————————————————————————————————————————————
Метод "Moving" выполняет движение (перемещение) агентов в алгоритме ANS. Давайте подробно разберем этот код:
1. Инициализация (если "revision" равно "false"):
- Если это первый шаг (первая эпоха), то для каждого агента:
- Генерируется случайное значение "val" в диапазоне от "rangeMin[c]" до "rangeMax[c]".
- Применяется оператор "SeInDiSp" для учета шага "rangeStep[c]".
- Значение "val" присваивается координатам агента "agent[i].c[c]".
- Значение "val" также присваивается лучшим координатам агента "agent[i].cBest[c]" (на данном этапе значения приспособленности агентов неизвестны, поэтому лучшие координаты равны текущим начальным).
- Значение "val" присваивается массиву агентов "a[i].c[c]".
2. Перемещение агентов (если "revision" равно "true"):
- Для каждого агента и каждой координаты:
- Если случайное число меньше "collChoiceProbab", выбирается случайное решение из коллекции:
- Выбирается случайный индекс "ind" из коллекции (пока не найдется непустое решение).
- Значение "p" берется из текущих координат агента.
- Значение "r" берется из выбранного решения из коллекции.
- В противном случае, используются лучшие координаты агента:
- Значение "p" берется из текущих координат агента.
- Значение "r" берется из лучших координат агента.
- Рассчитывается дистанция "dist" и диапазон ("min" и "max") для перемещения.
- Ограничиваются значения "min" и "max" диапазонами "rangeMin[c]" и "rangeMax[c]".
- Применяется нормальное распределение с параметрами "r", "min", "max" и "sigma".
- Значение "val" присваивается координатам агента "agent[i].c[c]".
- Значение "val" также присваивается массиву агентов "a[i].c[c]".
Этот код обновляет координаты агентов в алгоритме ANS, учитывая лучшие собственные координаты агентов и решения в коллекции.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ANS::Moving () { double val = 0.0; //---------------------------------------------------------------------------- if (!revision) { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { val = u.RNDfromCI (rangeMin [c], rangeMax [c]); val = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); agent [i].c [c] = val; agent [i].cBest [c] = val; a [i].c [c] = val; } } revision = true; return; } //---------------------------------------------------------------------------- double min = 0.0; double max = 0.0; double dist = 0.0; int ind = 0; double r = 0.0; double p = 0.0; for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { if (u.RNDprobab () < collChoiceProbab) { do ind = u.RNDminusOne (collectionSize); while (coll [ind].f == -DBL_MAX); p = agent [i].c [c]; r = coll [ind].c [c]; } else { p = agent [i].c [c]; r = agent [i].cBest [c]; } dist = fabs (p - r) * range; min = r - dist; max = r + dist; if (min < rangeMin [c]) min = rangeMin [c]; if (max > rangeMax [c]) max = rangeMax [c]; val = u.GaussDistribution (r, min, max, sigma); val = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); agent [i].c [c] = val; a [i].c [c] = val; } } } //——————————————————————————————————————————————————————————————————————————————
Метод "Revision" выполняет ревизию (обновление) агентов и коллекции в алгоритме ANS. Вот основные моменты:
- Первая часть метода: ищет агента, приспособленность которого лучше глобального решения с приспособленностью "fB" и сохраняет его координаты в массив "cB".
- Вторая часть метода: обновляет лучшие координаты агентов "agent[i].cBest" на основе их текущей приспособленности "a[i].f".
- Третья часть метода: обновляет коллекцию "coll" на основе лучших координат агентов.
- Сортирует коллекцию.
Этот метод играет важную роль в обновлении агентов и коллекции решений во время выполнения алгоритма. Популяция агентов помещается во вторую часть коллекции, производится сортировка коллекции и в дальнейшем используется первая половина коллекции, содержащая лучшие решения.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ANS::Revision () { //---------------------------------------------------------------------------- int ind = -1; for (int i = 0; i < popSize; i++) { if (a [i].f > fB) { fB = a [i].f; ind = i; } } if (ind != -1) ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY); //---------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { if (a [i].f > agent [i].fBest) { agent [i].fBest = a [i].f; ArrayCopy (agent [i].cBest, a [i].c, 0, 0, WHOLE_ARRAY); } } //---------------------------------------------------------------------------- int cnt = 0; for (int i = collectionSize; i < collectionSize * 2; i++) { if (cnt < popSize) { coll [i].f = agent [cnt].fBest; ArrayCopy (coll [i].c, agent [cnt].cBest, 0, 0, WHOLE_ARRAY); cnt++; } else break; } u.Sorting (coll, collTemp, collectionSize * 2); } //——————————————————————————————————————————————————————————————————————————————
3. Результаты тестов
Распечатка работы алгоритма ANS на стенде с тестовыми функциями:
ANS|Across Neighbourhood Search|50.0|100.0|8.0|1.0|0.6|
=============================
5 Hilly's; Func runs: 10000; result: 0.9494753644543816
25 Hilly's; Func runs: 10000; result: 0.8477633752716718
500 Hilly's; Func runs: 10000; result: 0.43857039929159747
=============================
5 Forest's; Func runs: 10000; result: 0.9999999999988883
25 Forest's; Func runs: 10000; result: 0.9233446583489741
500 Forest's; Func runs: 10000; result: 0.3998822848099108
=============================
5 Megacity's; Func runs: 10000; result: 0.709230769230769
25 Megacity's; Func runs: 10000; result: 0.6347692307692309
500 Megacity's; Func runs: 10000; result: 0.2309076923076936
=============================
All score: 6.13394 (68.15%)
ANS показывает впечатляющие результаты на всех тестовых функциях. Ну что же, давайте полюбуемся на визуализацию работы этого алгоритма на тестовом стенде. Результаты работы ANS действительно потрясающие, но при визуализации появляются некоторые вопросы. В частности, обращает на себя внимание поведение популяции - она как будто исчезает из поля зрения. Видно, что пространство решений очищается, и ландшафт функции остаётся без агентов. Это может означать только одно - несмотря на превосходные результаты работы алгоритма, популяция склонна к вырождению. Коллекция превосходных решений забивается очень похожими решениями, и новые решения просто не могут быть созданы, поскольку все решения являются производными от тех, что уже существуют.
Такая динамика популяции может свидетельствовать о необходимости доработки механизмов поддержания разнообразия в популяции. Возможно, стоит рассмотреть добавление оператора мутации или введение других механизмов, которые будут способствовать сохранению большего разнообразия решений в процессе оптимизации. Это поможет избежать вырождения популяции и обеспечить более стабильную работу алгоритма.
ANS на тестовой функции Hilly.
ANS на тестовой функции Forest.
ANS на тестовой функции Megacity.
Рассмотренный в этой статье алгоритм уверенно разместился на второй строчке рейтинговой таблицы. Комментарии излишни, но можно выделить основные моменты: алгоритм демонстрирует впечатляющую масштабируемость, сохраняя способность к поиску даже на задачах больших размерностей.
| № | AO | Description | Hilly | Hilly final | Forest | Forest final | Megacity (discrete) | Megacity final | Final result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | BGA | binary genetic algorithm | 0,99989 | 0,99518 | 0,42835 | 2,42341 | 0,96153 | 0,96181 | 0,32027 | 2,24360 | 0,91385 | 0,95908 | 0,24220 | 2,11512 | 6,782 | 75,36 |
| 2 | ANS | across neighbourhood search | 0,94948 | 0,84776 | 0,43857 | 2,23581 | 1,00000 | 0,92334 | 0,39988 | 2,32323 | 0,70923 | 0,63477 | 0,23091 | 1,57491 | 6,134 | 68,15 |
| 3 | CLA | code lock algorithm | 0,95345 | 0,87107 | 0,37590 | 2,20042 | 0,98942 | 0,91709 | 0,31642 | 2,22294 | 0,79692 | 0,69385 | 0,19303 | 1,68380 | 6,107 | 67,86 |
| 4 | (P+O)ES | (P+O) evolution strategies | 0,92256 | 0,88101 | 0,40021 | 2,20379 | 0,97750 | 0,87490 | 0,31945 | 2,17185 | 0,67385 | 0,62985 | 0,18634 | 1,49003 | 5,866 | 65,17 |
| 5 | CTA | comet tail algorithm | 0,95346 | 0,86319 | 0,27770 | 2,09435 | 0,99794 | 0,85740 | 0,33949 | 2,19484 | 0,88769 | 0,56431 | 0,10512 | 1,55712 | 5,846 | 64,96 |
| 6 | SDSm | stochastic diffusion search M | 0,93066 | 0,85445 | 0,39476 | 2,17988 | 0,99983 | 0,89244 | 0,19619 | 2,08846 | 0,72333 | 0,61100 | 0,10670 | 1,44103 | 5,709 | 63,44 |
| 7 | ESG | evolution of social groups | 0,99906 | 0,79654 | 0,35056 | 2,14616 | 1,00000 | 0,82863 | 0,13102 | 1,95965 | 0,82333 | 0,55300 | 0,04725 | 1,42358 | 5,529 | 61,44 |
| 8 | SIA | simulated isotropic annealing | 0,95784 | 0,84264 | 0,41465 | 2,21513 | 0,98239 | 0,79586 | 0,20507 | 1,98332 | 0,68667 | 0,49300 | 0,09053 | 1,27020 | 5,469 | 60,76 |
| 9 | ACS | artificial cooperative search | 0,75547 | 0,74744 | 0,30407 | 1,80698 | 1,00000 | 0,88861 | 0,22413 | 2,11274 | 0,69077 | 0,48185 | 0,13322 | 1,30583 | 5,226 | 58,06 |
| 10 | TSEA | turtle shell evolution algorithm | 0,96798 | 0,64480 | 0,29672 | 1,90949 | 0,99449 | 0,61981 | 0,22708 | 1,84139 | 0,69077 | 0,42646 | 0,13598 | 1,25322 | 5,004 | 55,60 |
| 11 | DE | differential evolution | 0,95044 | 0,61674 | 0,30308 | 1,87026 | 0,95317 | 0,78896 | 0,16652 | 1,90865 | 0,78667 | 0,36033 | 0,02953 | 1,17653 | 4,955 | 55,06 |
| 12 | CRO | chemical reaction optimisation | 0,94629 | 0,66112 | 0,29853 | 1,90593 | 0,87906 | 0,58422 | 0,21146 | 1,67473 | 0,75846 | 0,42646 | 0,12686 | 1,31178 | 4,892 | 54,36 |
| 13 | BSA | bird swarm algorithm | 0,89306 | 0,64900 | 0,26250 | 1,80455 | 0,92420 | 0,71121 | 0,24939 | 1,88479 | 0,69385 | 0,32615 | 0,10012 | 1,12012 | 4,809 | 53,44 |
| 14 | HS | harmony search | 0,86509 | 0,68782 | 0,32527 | 1,87818 | 0,99999 | 0,68002 | 0,09590 | 1,77592 | 0,62000 | 0,42267 | 0,05458 | 1,09725 | 4,751 | 52,79 |
| 15 | SSG | saplings sowing and growing | 0,77839 | 0,64925 | 0,39543 | 1,82308 | 0,85973 | 0,62467 | 0,17429 | 1,65869 | 0,64667 | 0,44133 | 0,10598 | 1,19398 | 4,676 | 51,95 |
| 16 | (PO)ES | (PO) evolution strategies | 0,79025 | 0,62647 | 0,42935 | 1,84606 | 0,87616 | 0,60943 | 0,19591 | 1,68151 | 0,59000 | 0,37933 | 0,11322 | 1,08255 | 4,610 | 51,22 |
| 17 | BSO | brain storm optimization | 0,93736 | 0,57616 | 0,29688 | 1,81041 | 0,93131 | 0,55866 | 0,23537 | 1,72534 | 0,55231 | 0,29077 | 0,11914 | 0,96222 | 4,498 | 49,98 |
| 18 | WOAm | wale optimization algorithm M | 0,84521 | 0,56298 | 0,26263 | 1,67081 | 0,93100 | 0,52278 | 0,16365 | 1,61743 | 0,66308 | 0,41138 | 0,11357 | 1,18803 | 4,476 | 49,74 |
| 19 | ACOm | ant colony optimization M | 0,88190 | 0,66127 | 0,30377 | 1,84693 | 0,85873 | 0,58680 | 0,15051 | 1,59604 | 0,59667 | 0,37333 | 0,02472 | 0,99472 | 4,438 | 49,31 |
| 20 | BFO-GA | bacterial foraging optimization - ga | 0,89150 | 0,55111 | 0,31529 | 1,75790 | 0,96982 | 0,39612 | 0,06305 | 1,42899 | 0,72667 | 0,27500 | 0,03525 | 1,03692 | 4,224 | 46,93 |
| 21 | MEC | mind evolutionary computation | 0,69533 | 0,53376 | 0,32661 | 1,55569 | 0,72464 | 0,33036 | 0,07198 | 1,12698 | 0,52500 | 0,22000 | 0,04198 | 0,78698 | 3,470 | 38,55 |
| 22 | IWO | invasive weed optimization | 0,72679 | 0,52256 | 0,33123 | 1,58058 | 0,70756 | 0,33955 | 0,07484 | 1,12196 | 0,42333 | 0,23067 | 0,04617 | 0,70017 | 3,403 | 37,81 |
| 23 | Micro-AIS | micro artificial immune system | 0,79547 | 0,51922 | 0,30861 | 1,62330 | 0,72956 | 0,36879 | 0,09398 | 1,19233 | 0,37667 | 0,15867 | 0,02802 | 0,56335 | 3,379 | 37,54 |
| 24 | COAm | cuckoo optimization algorithm M | 0,75820 | 0,48652 | 0,31369 | 1,55841 | 0,74054 | 0,28051 | 0,05599 | 1,07704 | 0,50500 | 0,17467 | 0,03380 | 0,71347 | 3,349 | 37,21 |
| 25 | SDOm | spiral dynamics optimization M | 0,74601 | 0,44623 | 0,29687 | 1,48912 | 0,70204 | 0,34678 | 0,10944 | 1,15826 | 0,42833 | 0,16767 | 0,03663 | 0,63263 | 3,280 | 36,44 |
| 26 | NMm | Nelder-Mead method M | 0,73807 | 0,50598 | 0,31342 | 1,55747 | 0,63674 | 0,28302 | 0,08221 | 1,00197 | 0,44667 | 0,18667 | 0,04028 | 0,67362 | 3,233 | 35,92 |
| 27 | FAm | firefly algorithm M | 0,58634 | 0,47228 | 0,32276 | 1,38138 | 0,68467 | 0,37439 | 0,10908 | 1,16814 | 0,28667 | 0,16467 | 0,04722 | 0,49855 | 3,048 | 33,87 |
| 28 | GSA | gravitational search algorithm | 0,64757 | 0,49197 | 0,30062 | 1,44016 | 0,53962 | 0,36353 | 0,09945 | 1,00260 | 0,32667 | 0,12200 | 0,01917 | 0,46783 | 2,911 | 32,34 |
| 29 | BFO | bacterial foraging optimization | 0,61171 | 0,43270 | 0,31318 | 1,35759 | 0,54410 | 0,21511 | 0,05676 | 0,81597 | 0,42167 | 0,13800 | 0,03195 | 0,59162 | 2,765 | 30,72 |
| 30 | ABC | artificial bee colony | 0,63377 | 0,42402 | 0,30892 | 1,36671 | 0,55103 | 0,21874 | 0,05623 | 0,82600 | 0,34000 | 0,14200 | 0,03102 | 0,51302 | 2,706 | 30,06 |
| 31 | BA | bat algorithm | 0,59761 | 0,45911 | 0,35242 | 1,40915 | 0,40321 | 0,19313 | 0,07175 | 0,66810 | 0,21000 | 0,10100 | 0,03517 | 0,34617 | 2,423 | 26,93 |
| 32 | SA | simulated annealing | 0,55787 | 0,42177 | 0,31549 | 1,29513 | 0,34998 | 0,15259 | 0,05023 | 0,55280 | 0,31167 | 0,10033 | 0,02883 | 0,44083 | 2,289 | 25,43 |
| 33 | IWDm | intelligent water drops M | 0,54501 | 0,37897 | 0,30124 | 1,22522 | 0,46104 | 0,14704 | 0,04369 | 0,65177 | 0,25833 | 0,09700 | 0,02308 | 0,37842 | 2,255 | 25,06 |
| 34 | PSO | particle swarm optimisation | 0,59726 | 0,36923 | 0,29928 | 1,26577 | 0,37237 | 0,16324 | 0,07010 | 0,60572 | 0,25667 | 0,08000 | 0,02157 | 0,35823 | 2,230 | 24,77 |
| 35 | Boids | boids algorithm | 0,43340 | 0,30581 | 0,25425 | 0,99346 | 0,35718 | 0,20160 | 0,15708 | 0,71586 | 0,27846 | 0,14277 | 0,09834 | 0,51957 | 2,229 | 24,77 |
| 36 | MA | monkey algorithm | 0,59107 | 0,42681 | 0,31816 | 1,33604 | 0,31138 | 0,14069 | 0,06612 | 0,51819 | 0,22833 | 0,08567 | 0,02790 | 0,34190 | 2,196 | 24,40 |
| 37 | SFL | shuffled frog-leaping | 0,53925 | 0,35816 | 0,29809 | 1,19551 | 0,37141 | 0,11427 | 0,04051 | 0,52618 | 0,27167 | 0,08667 | 0,02402 | 0,38235 | 2,104 | 23,38 |
| 38 | FSS | fish school search | 0,55669 | 0,39992 | 0,31172 | 1,26833 | 0,31009 | 0,11889 | 0,04569 | 0,47467 | 0,21167 | 0,07633 | 0,02488 | 0,31288 | 2,056 | 22,84 |
| 39 | RND | random | 0,52033 | 0,36068 | 0,30133 | 1,18234 | 0,31335 | 0,11787 | 0,04354 | 0,47476 | 0,25333 | 0,07933 | 0,02382 | 0,35648 | 2,014 | 22,37 |
| 40 | GWO | grey wolf optimizer | 0,59169 | 0,36561 | 0,29595 | 1,25326 | 0,24499 | 0,09047 | 0,03612 | 0,37158 | 0,27667 | 0,08567 | 0,02170 | 0,38403 | 2,009 | 22,32 |
| 41 | CSS | charged system search | 0,44252 | 0,35454 | 0,35201 | 1,14907 | 0,24140 | 0,11345 | 0,06814 | 0,42299 | 0,18333 | 0,06300 | 0,02322 | 0,26955 | 1,842 | 20,46 |
| 42 | EM | electroMagnetism-like algorithm | 0,46250 | 0,34594 | 0,32285 | 1,13129 | 0,21245 | 0,09783 | 0,10057 | 0,41085 | 0,15667 | 0,06033 | 0,02712 | 0,24412 | 1,786 | 19,85 |
Рисунок 1. Цветовая градация алгоритмов по соответствующим тестам. Белым цветом подсвечены результаты больше или равные 0.99
Рисунок 2. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше,
где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Выше в статье мы отметили склонность популяции алгоритма ANS к вырождению. Для устранения этого существенного недостатка, я решил внести изменения в алгоритм путем добавления оператора мутации. В данном случае мутация будет представлять собой гауссову вероятность получения новой координаты в окрестностях лучшего решения агента, но в диапазоне от минимально допустимого значения до максимального для соответствующей координаты. Для этого нам потребуется внести некоторые изменения в метод "Moving".
Давайте посмотрим, какие изменения были внесены в код, и кратко опишем логику метода:
- Если случайное число меньше 0.005, происходит мутация с использованием нормального распределения.
- В противном случае выбирается случайное решение из коллекции, или используются лучшие координаты агента.
- Рассчитывается дистанция и диапазон для нормально распределения.
- Применяется нормальное распределение для получения новых значений координат.
//---------------------------------------------------------------------------- double min = 0.0; double max = 0.0; double dist = 0.0; int ind = 0; double r = 0.0; double p = 0.0; for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { if (u.RNDprobab () < 0.005) { val = u.GaussDistribution (agent [i].cBest [c], rangeMin [c], rangeMax [c], sigma); val = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); } else { if (u.RNDprobab () < collChoiceProbab) { do ind = u.RNDminusOne (collectionSize); while (coll [ind].f == -DBL_MAX); p = agent [i].c [c]; r = coll [ind].c [c]; } else { p = agent [i].c [c]; r = agent [i].cBest [c]; } dist = fabs (p - r) * range; min = r - dist; max = r + dist; if (min < rangeMin [c]) min = rangeMin [c]; if (max > rangeMax [c]) max = rangeMax [c]; val = u.GaussDistribution (r, min, max, sigma); val = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); } agent [i].c [c] = val; a [i].c [c] = val; } }
После добавления оператора мутации, алгоритм продолжает исследовать пространство поиска при любом количестве эпох, что продемонстрировано на рисунке 3 (скриншот визуализации работы алгоритма).
Рисунок 3. Остались агенты, популяция не вырождается (параметр mut = 0.005)
- Оператор мутации с параметром "mut 0.1" оказывает негативное влияние на общий результат. При таком большом коэффициенте мутации (10% от общего количества операций над каждой координатой) наблюдается ухудшение результатов работы алгоритма. Поэтому было принято решение последовательно уменьшать этот параметр. Уменьшение значения параметра привело к улучшению результатов, и я остановился на значении 0.005. Этот коэффициент оказался достаточным, чтобы предотвратить вырождение популяции и при этом обеспечить улучшение результатов работы алгоритма, что отражено на распечатках ниже.
Результаты работы алгоритма с вероятностью мутации mut = 0.1:
=============================
All score: 6.05103 (67.23%)
ANS|Across Neighbourhood Search|50.0|100.0|8.0|1.0|0.6|
=============================
5 Hilly's; Func runs: 10000; result: 0.9534829314854332
25 Hilly's; Func runs: 10000; result: 0.8136803288623282
500 Hilly's; Func runs: 10000; result: 0.31144979106165716
=============================
5 Forest's; Func runs: 10000; result: 0.9996561274415626
25 Forest's; Func runs: 10000; result: 0.81670393859872
500 Forest's; Func runs: 10000; result: 0.25620559379918284
=============================
5 Megacity's; Func runs: 10000; result: 0.8753846153846153
25 Megacity's; Func runs: 10000; result: 0.5778461538461539
500 Megacity's; Func runs: 10000; result: 0.13375384615384744
=============================
All score: 5.73816 (63.76%)
Результаты работы алгоритма с вероятностью мутации mut = 0.01:
=============================
5 Hilly's; Func runs: 10000; result: 0.9073657389037575
25 Hilly's; Func runs: 10000; result: 0.871278233418226
500 Hilly's; Func runs: 10000; result: 0.3960769225373809
=============================
5 Forest's; Func runs: 10000; result: 0.989394440004635
25 Forest's; Func runs: 10000; result: 0.9513150500729907
500 Forest's; Func runs: 10000; result: 0.35407610928209116
=============================
5 Megacity's; Func runs: 10000; result: 0.7492307692307691
25 Megacity's; Func runs: 10000; result: 0.6387692307692309
500 Megacity's; Func runs: 10000; result: 0.19352307692307838
=============================
All score: 6.05103 (67.23%)
Результаты работы алгоритма с вероятностью мутации mut = 0.005:
ANS|Across Neighbourhood Search|50.0|100.0|8.0|1.0|0.6|
=============================
5 Hilly's; Func runs: 10000; result: 0.949632264944664
25 Hilly's; Func runs: 10000; result: 0.871206955779846
500 Hilly's; Func runs: 10000; result: 0.40738389742274217
=============================
5 Forest's; Func runs: 10000; result: 0.9924803131691761
25 Forest's; Func runs: 10000; result: 0.9493489251290264
500 Forest's; Func runs: 10000; result: 0.3666276564633121
=============================
5 Megacity's; Func runs: 10000; result: 0.8061538461538461
25 Megacity's; Func runs: 10000; result: 0.6732307692307691
500 Megacity's; Func runs: 10000; result: 0.20844615384615534
=============================
All score: 6.22451 (69.16%)
Выводы
Теперь, когда мы рассмотрели результаты работы совместно с оператором мутации, мы можем сделать следующие выводы:
1. Простота и удобство реализации.
2. Сбалансированность исследования и эксплуатации.
3. Эффективность в решении различных типов задач.
4. Адаптивность к различным задачам.
5. Потенциал для дальнейшего улучшения.
Таким образом, ANS представляет собой простой, но эффективный алгоритм оптимизации, который демонстрирует конкурентоспособные результаты на широком спектре задач и имеет потенциал для дальнейшего развития.
Общие плюсы и минусы алгоритма поиска в окрестности (ANS):
Плюсы:
- Хорошая сходимость на различных типах функций.
- Очень быстрый.
- Простая реализация.
- Отличная масштабируемость.
Минусы:
- Иногда застревает в локальных экстремумах.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Разработка торгового робота на Python (Часть 3): Реализация торгового алгоритма на основе модели
Введение в MQL5 (Часть 4): Структуры, классы и функции времени
Машинное обучение и Data Science (Часть 20): Выбор между LDA и PCA в задачах алготрейдинга на MQL5
Нейросети это просто (Часть 96): Многоуровневое извлечение признаков (MSFformer)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования