Наиболее известные модификации алгоритма искусственного кооперативного поиска (Artificial Cooperative Search, ACSm)
563
0
Содержание:
1. Введение
В предыдущей статье мы познакомились с интересным и перспективным алгоритмом оптимизации, известным как алгоритм искусственного кооперативного поиска (ACS). Этот алгоритм вдохновлен наблюдениями за взаимодействием и кооперацией живых организмов в природе, где они объединяются для достижения общих целей и получения взаимной выгоды. Основная идея ACS состоит в моделировании таких мутуалистических отношений между "хищниками" и "жертвами" с целью оптимизации сложных многомерных задач.
Теперь, после знакомства с базовой версией ACS, мы попробуем расширить его возможности с помощью модифицированных вариантов алгоритма. Эти усовершенствованные версии ACS будут использовать дополнительные механизмы, вдохновленные наблюдениями за природными экосистемами, чтобы повысить эффективность поиска оптимальных решений.
Исследование известных модифицированных версий ACS позволит нам глубже понять, как принципы кооперации и взаимовыгодного сосуществования живых организмов могут быть успешно адаптированы для решения сложных оптимизационных задач, и поможет раскрыть новые перспективы в области искусственного интеллекта и вдохновить дальнейшие разработки в этом увлекательном направлении.
2.Реализация алгоритма
Первая и незначительная модификация алгоритма ACS (Modified Artificial Cooperative Search Algorithms) включает в себя два основных изменения:
1. Использование аугментированных форм матриц (популяций) "A" и "B":
- В этой модификации матрицы "A" и "B" имеют дополнительные столбцы. Каждая строка матрицы содержит N переменных и дополнительный столбец, в котором хранится значение функции, вычисленное на основе первых N переменных. Это позволяет легче отслеживать значения функций и улучшает точность решений.
2. Изменение способа создания бинарной матрицы "M":
- В оригинальном алгоритме матрица "M" заполняется значениями "0", а затем некоторые элементы выбираются и устанавливаются в "1". Это изменение приводит к небольшому улучшению точности решений, по крайней мере, для тестовых функций, на которых проводились эксперименты.
Таким образом, эти изменения в первой и незначительной модификации алгоритма ACS направлены на улучшение точности решений и эффективности работы алгоритма при решении оптимизационных задач. Вместо добавления дополнительного столбца для хранения значений приспособленности особей, как предлагают авторы, мы будем использовать уже привычное нам поле "f" в структуре агентов, которые описывают особи в популяции.
Вторая и значительная модификация алгоритма ACS включает в себя следующие изменения, которые отличаются от оригинальной версии:
1. Изменение подхода к заполнению матриц "Predator" и "Prey":
- В этой модификации каждая строка в аугментированных матрицах "A" и "B" сортируется по значению функции приспособленности. Затем строки из отсортированных матриц "A" и "B" сравниваются, и на основе этого сравнения определяется, какие строки попадут в матрицы "Predator" и "Prey". Этот подход позволяет выбирать кандидатов для обновления на основе их заслуг (значения функции), а не случайного выбора.
2. Случайные сравнения для обновления матриц "A" и "B":
- В конце каждой итерации основного цикла в этой модификации обновление матриц "A" и "B" происходит через случайные сравнения. Это означает, что обе матрицы имеют одинаковую вероятность быть обновленными. Такой подход позволяет равномерно обновлять обе популяции и улучшает разнообразие в поиске оптимального решения.
Таким образом, вторая модификация алгоритма ACS улучшает процесс выбора кандидатов и обновления популяций "A" и "B", делая их более эффективными и разнообразными в поиске оптимального решения. Она отличается от оригинальной версии алгоритма в способе формирования популяций "Predator" и "Prey" и в использовании случайных сравнений для обновления матриц.
Третья и значительная модификация алгоритма ACS представляет собой совершенно другой подход к формированию матриц "Predator" и "Prey". Подробное описание изменений, внесенных в третью модификацию:
1. Популяция "Pop":
- В этой модификации создается новая матрица "Pop", объединяющая аугментированные матрицы "A" и "B". "Pop" содержит все строки из матриц "A" и "B", а затем сортируется по значениям фитнес-функции. Первые "popSize" строк в "Pop" становятся популяцией "Predator", а последние "popSize" строк - популяцией "Prey".
2. Обновление "Predator" и "Prey":
- После формирования популяций "Predator" и "Prey", алгоритм продолжает обновление на основе приспособленности особей. Предпочтение отдается лучшим решениям, которые были отобраны в качестве "Predator", что способствует улучшению точности и скорости сходимости алгоритма.
3. Использование случайных сравнений:
- Аналогично второй модификации, в конце каждой итерации основного цикла обновление матриц "A" и "B" происходит через случайные сравнения. Этот подход обеспечивает равные шансы для обновления обеих популяций и способствует разнообразию в поиске оптимального решения.
Таким образом, третья модификация алгоритма ACS сосредотачивается на использовании приспособленности для формирования популяций "Predator" и "Prey". Она представляет собой более продвинутый и эффективный подход к выбору кандидатов и обновлению популяций в процессе поиска оптимального решения.
Ознакомившись с возможными вариантами модификации базовой версии алгоритма (ACS), мы теперь готовы перейти к реализации первой усовершенствованной версии этого перспективного оптимизационного метода. Наша цель - повысить эффективность поиска оптимальных решений. Шаг за шагом мы будем внедрять новые элементы в базовую структуру ACS, тщательно анализируя их влияние на производительность и сходимость алгоритма.
Приступим к реализации первой модифицированной версии алгоритма и исследуем ее потенциал. В каждой последующей версии алгоритма зелёным цветом в коде указаны участки, которые отличаются от предыдущей версии.
Описание кода класса C_AO_ACSm1:
1. C_AO_ACSm1 - это класс, который наследуется от базового класса "C_AO".
2. Класс имеет публичный конструктор и деструктор.
3. В конструкторе инициализируются следующие члены данных:
- ao_name, ao_desc, ao_link - описательные строки об алгоритме
- popSize - размер популяции
- bioProbab - вероятность биологического взаимодействия
- params - массив параметров алгоритма, в данном случае два параметра: "popSize" и "bioProbab"
4. SetParams() - метод устанавливает значения "popSize" и "bioProbab" на основе параметров из массива "params".
5. Init() - метод принимает на вход диапазоны и шаги поиска, а также количество эпох, и возвращает логическое значение, указывающее на успешность инициализации.
6. Moving() и Revision() - методы содержат основную логику работы алгоритма по перемещению агентов и их ревизии.
7. Приватные члены данных включают в себя массивы структур типов "S_AO_Agent" и "S_C", а также переменные "Key" и "phase", которые используются в алгоритме.
8. ArrayShuffle() - приватный метод перемешивает элементы массива.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_ACSm1 : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_ACSm1 () { } C_AO_ACSm1 () { ao_name = "ACS"; ao_desc = "Artificial Cooperative Search m1"; ao_link = "https://www.mql5.com/ru/articles/15014"; popSize = 1; //population size bioProbab = 0.9; //biological interaction probability ArrayResize (params, 2); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "bioProbab"; params [1].val = bioProbab; } void SetParams () { popSize = (int)params [0].val; bioProbab = params [1].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 (); //---------------------------------------------------------------------------- double bioProbab; //biological interaction probability private: //------------------------------------------------------------------- S_AO_Agent A []; S_AO_Agent B []; S_AO_Agent Predator []; S_AO_Agent Prey []; S_C M []; int Key; int phase; void ArrayShuffle (double &arr []); }; //——————————————————————————————————————————————————————————————————————————————
Метод "Init" класса "C_AO_ACSm1" выполняет инициализацию объекта:
1. Init() - объявление метода. Он принимает четыре аргумента: минимальный диапазон поиска "rangeMinP", максимальный диапазон поиска "rangeMaxP", шаг поиска "rangeStepP" и количество эпох "epochsP", которое по умолчанию равно "0".
2. if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false - вызов функции "StandardInit", которая выполняет стандартную инициализацию базового класса. Если "StandardInit" возвращает "false", то метод "Init" немедленно завершается и возвращает "false".
3. В цикле "for (int i = 0; i < popSize; i++)" каждый элемент массивов "A", "B", "Predator", "Prey" и "M" инициализируется с помощью метода "Init".
4. "ArrayResize (A, popSize)" и подобные строки изменяют размер массивов "A", "B", "Predator", "Prey" и "M" до размера "popSize".
5. Во вложенном цикле "for (int j = 0; j < coords; j++)" каждый элемент "c" (координаты особей) каждого объекта в массивах "A" и "B" инициализируется случайным значением в заданном диапазоне.
6. "phase = 0" устанавливает значение переменной "phase" равным 0.
7. Метод возвращает "true" в случае успешной инициализации.
Этот код отвечает за начальную настройку и подготовку данных, необходимых для дальнейшей работы алгоритма. Он создает массивы объектов, инициализирует их значения и устанавливает начальное состояние алгоритма.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_ACSm1::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 (A, popSize); ArrayResize (B, popSize); ArrayResize (Predator, popSize); ArrayResize (Prey, popSize); ArrayResize (M, popSize); for (int i = 0; i < popSize; i++) { A [i].Init (coords); B [i].Init (coords); Predator [i].Init (coords); Prey [i].Init (coords); M [i].Init (coords); } // Initialization for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { A [i].c [j] = rangeMin [j] + (rangeMax [j] - rangeMin [j]) * u.RNDprobab (); B [i].c [j] = rangeMin [j] + (rangeMax [j] - rangeMin [j]) * u.RNDprobab (); } } phase = 0; return true; } //——————————————————————————————————————————————————————————————————————————————
Метод "Moving" класса "C_AO_ACSm1" реализует основную логику перемещения особей в алгоритме:
1. "if (phase == 0)" - на этой фазе происходит копирование особей из популяции "A" в массив "a" (массив "а" используется для передачи особей на расчет фитнес-функции).
- Для каждого элемента в цикле "for (int i = 0; i < popSize; i++)" выполняется копирование координат особей из массива "A" в массив "a".
- Затем увеличивается значение переменной "phase" на 1 и метод возвращается.
2. "if (phase == 1)" - на этой фазе присваиваются приспособленности особям популяции "A" и копируются особи из популяции "B".
- Для каждого элемента в цикле "for (int i = 0; i < popSize; i++)" значение приспособленности "a [i].f" копируется в "A [i].f" .
- Затем для каждого элемента в цикле "for (int i = 0; i < popSize; i++)" выполняется копирование координат особей из массива "B" в массив "a" для дальнейшего расчета приспособленности особей.
- Значение "phase" увеличивается на 1 и метод возвращается.
3. "if (phase == 2)" - на этой фазе возвращается приспособленность особям популяции "B".
- Для каждого элемента в цикле "for (int i = 0; i < popSize; i++)" значение приспособленности "a [i].f" копируется в "B [i].f".
- Значение "phase" увеличивается на 1, и выполняется дальнейшая логика алгоритма.
4. "Selection" - в этом блоке выполняется операция селекции.
- Если случайное число "u.RNDprobab()" меньше 0.5, то для каждого элемента в цикле "for (int i = 0; i < popSize; i++)" особь "A [i]" копируется в "Predator [i]" и "Key" устанавливается в 1.
- Иначе для каждого элемента в цикле "for (int i = 0; i < popSize; i++)" особь "B [i]" копируется в "Predator [i]" и "Key" устанавливается в 2.
- Аналогичным образом выполняется селекция для массива "Prey".
5. "Permutation of Prey" - в этом блоке выполняется операция случайной перестановки координат в каждой особи популяции "Prey".
- Для каждой особи в цикле "for (int i = 0; i < popSize; i++)" выполняется "ArrayShuffle (Prey [i].c)", перемешивая координаты особей (перемешиваются координаты у каждой особи в отдельности, а между особями координаты не перемешиваются).
6. "Mutation" и "Crossover" - в этих блоках выполняются операции мутации и скрещивания.
- Вычисляется значение "R" в зависимости от случайного числа.
- Заполняется двоичная матрица "M" единицами.
- Выполняются дополнительные операции с матрицей "M", изменяя некоторые ее элементы на 0 или 1, в зависимости от вероятности биологического взаимодействия "bioProbab".
- Для каждой особи в цикле "for (int i = 0; i < popSize; i++)" выполняется мутация и скрещивание, обновляя значения в массиве популяции "a".
7. "Boundary control" - в этом блоке выполняется контроль выхода за границы, при котором координаты особей популяции "a", выходящие за пределы заданного диапазона оптимизируемых параметров, заменяются случайными значениями в этом диапазоне.
Этот метод реализует основные операции алгоритма, такие как селекция, мутация, скрещивание и контроль границ, которые применяются к популяции особей для поиска оптимального решения.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ACSm1::Moving () { //---------------------------------------------------------------------------- if (phase == 0) { for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, A [i].c); phase++; return; } //---------------------------------------------------------------------------- if (phase == 1) { for (int i = 0; i < popSize; i++) A [i].f = a [i].f; for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, B [i].c); phase++; return; } //---------------------------------------------------------------------------- if (phase == 2) { for (int i = 0; i < popSize; i++) B [i].f = a [i].f; phase++; } //---------------------------------------------------------------------------- // Selection if (u.RNDprobab () < 0.5) { for (int i = 0; i < popSize; i++) { Predator [i] = A [i]; } Key = 1; } else { for (int i = 0; i < popSize; i++) { Predator [i] = B [i]; } Key = 2; } if (u.RNDprobab () < 0.5) { for (int i = 0; i < popSize; i++) { Prey [i] = A [i]; } } else { for (int i = 0; i < popSize; i++) { Prey [i] = B [i]; } } // Permutation of Prey for (int i = 0; i < popSize; i++) { ArrayShuffle (Prey [i].c); } double R; if (u.RNDprobab () < 0.5) { R = 4 * u.RNDprobab () * u.RNDfromCI (-1.0, 1.0); } else R = 1 / MathExp (4 * MathRand () / 32767.0); // Fill binary matrix M with 0s for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { M [i].c [j] = 0; } } // Additional operations with matrix M for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { if (u.RNDprobab () < bioProbab) { M [i].c [j] = 1; } } } for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { if (u.RNDprobab () < bioProbab) { M [i].c [j] = 1; } } } for (int i = 0; i < popSize; i++) { int sum = 0; for (int c = 0; c < coords; c++) sum += M [i].c [c]; if (sum == coords) { int j = MathRand () % coords; M [i].c [j] = 0; } } // Mutation for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = Predator [i].c [j] + R * (Prey [i].c [j] - Predator [i].c [j]); // Crossover if (M [i].c [j] > 0) { a [i].c [j] = Predator [i].c [j]; } // Boundary control if (a [i].c [j] < rangeMin [j] || a [i].c [j] > rangeMax [j]) { a [i].c [j] = rangeMin [j] + (rangeMax [j] - rangeMin [j]) * u.RNDprobab (); } } } //---------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } } //——————————————————————————————————————————————————————————————————————————————
Далее рассмотрим код метода "Revision" класса "C_AO_ACSm1". Он выполняет следующие операции:
1. Проверяет, что фаза подготовки популяций "phase" уже завершена "phase >= 3". Если это условие не выполнено, метод возвращается без выполнения дальнейших действий.
2. Обновляет выбор особей "Selection update":
- Для каждой особи в популяции "a" проверяется, превышает ли ее значение приспособленности "f" соответствующее значение в массиве "Predator". Если да, то значение в "Predator" обновляется.
- В зависимости от значения переменной "Key", особи популяции "Predator" копируются в популяцию "A" или "B".
3. Определяет лучшее значение приспособленности "Ybest" и его индекс "Ibest" в массиве "Predator":
- Проходит по массиву "Predator", находит максимальное значение приспособленности и его индекс.
4. Обновляет лучшее глобальное решение "fB":
- Если "Ybest" превышает текущее лучшее значение "fB", то "fB" обновляется, а соответствующие элементы массивов "a" и "cB" копируются из массива "Predator".
Этот метод выполняет обновление выбора особей, определение лучшего решения и обновление глобального лучшего решения в рамках алгоритма оптимизации.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ACSm1::Revision () { if (phase < 3) return; // Selection update for (int i = 0; i < popSize; i++) { double d = a [i].f; if (d > Predator [i].f) { Predator [i] = a [i]; } } if (Key == 1) { for (int i = 0; i < popSize; i++) { A [i] = Predator [i]; } } else { for (int i = 0; i < popSize; i++) { B [i] = Predator [i]; } } double Ybest = -DBL_MAX; int Ibest = -1; for (int i = 0; i < popSize; i++) { if (Predator [i].f > Ybest) { Ybest = Predator [i].f; Ibest = i; } } if (Ybest > fB) { fB = Ybest; ArrayCopy (a [Ibest].c, Predator [Ibest].c); ArrayCopy (cB, Predator [Ibest].c); } } //——————————————————————————————————————————————————————————————————————————————
Метод "ArrayShuffle" класса "C_AO_ACS", применяется во всех трёх модификациях, выполняет случайную перетасовку элементов в массиве:
1. Определяет размер массива "arr" с помощью функции "ArraySize".
2. Проходит по массиву "arr" в обратном порядке, начиная с последнего элемента.
3. Для каждого элемента "i" генерирует случайный индекс "j" от 0 до "i".
4. Меняет местами элементы "arr[i]" и "arr[j]", используя временную переменную "tmp".
В результате этого метода элементы массива "arr" перемешиваются в случайном порядке.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ACSm1::ArrayShuffle (double &arr []) { int n = ArraySize (arr); for (int i = n - 1; i > 0; i--) { int j = MathRand () % (i + 1); double tmp = arr [i]; arr [i] = arr [j]; arr [j] = tmp; } } //——————————————————————————————————————————————————————————————————————————————
Теперь настала очередь разобрать код второй модификации алгоритма ACS. Код метода "Moving" класса "C_AO_ACSm2" в соответствии с изменениями:
1. "Фаза 0":
- Если фаза равна "0", то для каждой особи в популяции "a" копируются значения из популяции "A".
- Увеличивается значение фазы, и метод возвращается.
2. "Фаза 1":
- Если фаза равна "1", то для каждой особи в популяции "a" копируются значения приспособленности "f" в популяцию "A".
- Для каждой особи в популяции "a" копируются значения из популяции "B".
- Увеличивается значение фазы, и метод возвращается.
3. "Фаза 2":
- Если фаза равна "2", то для каждой особи в популяции "B" копируются значения приспособленности "f" из популяции "a".
- Увеличивается значение фазы, и дальнейшая логика алгоритма продолжается.
4. "Selection":
- Для каждой особи в популяциях "A" и "B" сравниваются значения приспособленности "f".
- Если значение "f" в "A" больше, чем в "B", то особь из "A" копируется в "Predator", а особь из "B" - в "Prey". В противном случае, наоборот (фактически наиболее приспособленные особи назначаются "хищниками", а наименее приспособленные - "добычей").
5. "Permutation of Prey":
- Для каждой особи в популяции "Prey" выполняется перемешивание её (особи) координат с помощью функции "ArrayShuffle".
6. "Mutation" и "Crossover":
- Определяется значение "R", в зависимости от случайного числа.
- Заполняется двоичная матрица "M" нулями.
- Выполняются дополнительные операции с матрицей "M", где некоторые элементы устанавливаются в "1" в зависимости от вероятности "bioProbab".
Для каждой особи в популяции "a":
- Выполняется мутация: элемент "a[i].c[j]" вычисляется как сумма элемента "Predator[i].c[j]" и произведения "R" на разность между "Prey[i].c[j]" и "Predator[i].c[j]".
- Выполняется скрещивание: если элемент "M[i].c[j]" равен "1", то элемент "a[i].c[j]" заменяется на элемент "Predator[i].c[j]".
- Выполняется контроль границ: если элемент "a[i].c[j]" выходит за пределы диапазона "rangeMin[j]" и "rangeMax[j]", то он заменяется случайным значением в этом диапазоне.
7. "Проверка координат":
- Для каждой особи в популяции "a" выполняется проверка координат с помощью функции "SeInDiSp".
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ACSm2::Moving () { //---------------------------------------------------------------------------- if (phase == 0) { for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, A [i].c); phase++; return; } //---------------------------------------------------------------------------- if (phase == 1) { for (int i = 0; i < popSize; i++) A [i].f = a [i].f; for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, B [i].c); phase++; return; } //---------------------------------------------------------------------------- if (phase == 2) { for (int i = 0; i < popSize; i++) B [i].f = a [i].f; phase++; } //---------------------------------------------------------------------------- // Selection for (int i = 0; i < popSize; i++) { if (A [i].f > B [i].f) { Predator [i] = A [i]; Prey [i] = B [i]; } else { Predator [i] = B [i]; Prey [i] = A [i]; } } // Permutation of Prey for (int i = 0; i < popSize; i++) { ArrayShuffle (Prey [i].c); } double R; if (u.RNDprobab () < 0.5) { R = 4 * u.RNDprobab () * u.RNDfromCI (-1.0, 1.0); } else R = 1 / MathExp (4 * MathRand () / 32767.0); // Fill binary matrix M with 0s for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { M [i].c [j] = 0; } } // Additional operations with matrix M for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { if (u.RNDprobab () < bioProbab) { M [i].c [j] = 1; } } } for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { if (u.RNDprobab () < bioProbab) { M [i].c [j] = 1; } } } for (int i = 0; i < popSize; i++) { int sum = 0; for (int c = 0; c < coords; c++) sum += M [i].c [c]; if (sum == coords) { int j = MathRand () % coords; M [i].c [j] = 0; } } // Mutation for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = Predator [i].c [j] + R * (Prey [i].c [j] - Predator [i].c [j]); // Crossover if (M [i].c [j] > 0) { a [i].c [j] = Predator [i].c [j]; } // Boundary control if (a [i].c [j] < rangeMin [j] || a [i].c [j] > rangeMax [j]) { a [i].c [j] = rangeMin [j] + (rangeMax [j] - rangeMin [j]) * u.RNDprobab (); } } } //---------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } } //——————————————————————————————————————————————————————————————————————————————
Метод "Revision" второй модификации алгоритма рассматривать не будем, потому что он не претерпел изменений.
Со второй модификацией мы разобрались, перейдем к третьей. В определении класса третьей модификации "C_AO_ACSm3", который является производным от базового класса "C_AO", появились следующие изменения:
Изменился список членов данных:
- "bioProbab" - вероятность биологического взаимодействия.
- "A[]", "B[]", "Predator[]", "Prey[]", "Pop[]", "pTemp[]" - массивы, хранящие различные популяции особей.
- "M[]" - массив, хранящий дополнительные данные, связанные с особями.
- "phase" - текущая фаза алгоритма.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_ACSm3 : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_ACSm3 () { } C_AO_ACSm3 () { ao_name = "ACS"; ao_desc = "Artificial Cooperative Search m3"; ao_link = "https://www.mql5.com/ru/articles/15014"; popSize = 10; //population size bioProbab = 0.9; //biological interaction probability ArrayResize (params, 2); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "bioProbab"; params [1].val = bioProbab; } void SetParams () { popSize = (int)params [0].val; bioProbab = params [1].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 (); //---------------------------------------------------------------------------- double bioProbab; //biological interaction probability private: //------------------------------------------------------------------- S_AO_Agent A []; S_AO_Agent B []; S_AO_Agent Predator []; S_AO_Agent Prey []; S_AO_Agent Pop []; S_AO_Agent pTemp []; S_C M []; int phase; void ArrayShuffle (double &arr []); }; //——————————————————————————————————————————————————————————————————————————————
В методе инициализации "Init" класса "C_AO_ACSm3" появились следующие изменения:
1. Выделяется память для массивов "A", "B", "Predator", "Prey", "Pop", "pTemp" и "M" размером "popSize" или "popSize * 2".
2. Каждый элемент массивов "A", "B", "Predator", "Prey", "Pop" и "M" инициализируется с помощью метода "Init".
Отметим, что авторы оригинальной версии алгоритма не имеет разделения логики на фазы. Для реализации алгоритма в стиле, принятом нами для всех популяционных алгоритмов, было добавлено разделение на фазы. Это было необходимо, поскольку в ACS используется предварительный расчет приспособленности агентов для двух популяций "А" и "B", и эти операции необходимо выполнять последовательно в методах.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_ACSm3::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 (A, popSize); ArrayResize (B, popSize); ArrayResize (Predator, popSize); ArrayResize (Prey, popSize); ArrayResize (Pop, popSize * 2); ArrayResize (pTemp, popSize * 2); ArrayResize (M, popSize); for (int i = 0; i < popSize; i++) { A [i].Init (coords); B [i].Init (coords); Predator [i].Init (coords); Prey [i].Init (coords); M [i].Init (coords); } for (int i = 0; i < popSize * 2; i++) Pop [i].Init (coords); // Initialization for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { A [i].c [j] = rangeMin [j] + (rangeMax [j] - rangeMin [j]) * u.RNDprobab (); B [i].c [j] = rangeMin [j] + (rangeMax [j] - rangeMin [j]) * u.RNDprobab (); } } phase = 0; return true; } //——————————————————————————————————————————————————————————————————————————————
Теперь, давайте посмотрим на код метода "Moving" класса "C_AO_ACSm3" третьей модификации. Изменения коснулись следующих мест кода:
- Объединение популяций "A" и "B" в одну популяцию "Pop".
- Сортировка популяции "Pop" по значениям приспособленности особей.
- Заполнение популяций "Predator" и "Prey" из отсортированного массива "Pop", где лучшая половина популяции становится "хищниками", а вторая половина "добычей" соответственно.
- Заполнение двоичной матрицы "M" единицами.
- Дополнительные операции с матрицей "M", в которых некоторые элементы меняются на "0" или "1", в зависимости от случайного числа и вероятности биологического взаимодействия "bioProbab".
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ACSm3::Moving () { //---------------------------------------------------------------------------- if (phase == 0) { for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, A [i].c); phase++; return; } //---------------------------------------------------------------------------- if (phase == 1) { for (int i = 0; i < popSize; i++) A [i].f = a [i].f; for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, B [i].c); phase++; return; } //---------------------------------------------------------------------------- if (phase == 2) { for (int i = 0; i < popSize; i++) B [i].f = a [i].f; phase++; } //---------------------------------------------------------------------------- // Merge matrices A and B to create matrix Pop for (int i = 0; i < popSize; i++) { Pop [i] = A [i]; Pop [i + popSize] = B [i]; } // Sort matrix Pop using column N as sort key values u.Sorting (Pop, pTemp, popSize * 2); // Populate Predator and Prey matrices for (int i = 0; i < popSize; i++) { Predator [i] = Pop [i]; Prey [i] = Pop [i + popSize]; } // Permutation of Prey for (int i = 0; i < popSize; i++) { ArrayShuffle (Prey [i].c); } double R; if (u.RNDprobab () < 0.5) { R = 4 * u.RNDprobab () * u.RNDfromCI (-1.0, 1.0); } else R = 1 / MathExp (4 * MathRand () / 32767.0); // Fill binary matrix M with 1s for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { M [i].c [j] = 1; } } // Additional operations with matrix M for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { if (u.RNDprobab () < bioProbab) { M [i].c [j] = 0; } } } for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { if (u.RNDprobab () < bioProbab) { if (u.RNDprobab() < bioProbab) { M[i].c[j] = 1; } else { M[i].c[j] = 0; } } } } for (int i = 0; i < popSize; i++) { int sum = 0; for (int c = 0; c < coords; c++) sum += M [i].c [c]; if (sum == coords) { int j = MathRand () % coords; M [i].c [j] = 0; } } // Mutation for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = Predator [i].c [j] + R * (Prey [i].c [j] - Predator [i].c [j]); // Crossover if (M [i].c [j] > 0) { a [i].c [j] = Predator [i].c [j]; } // Boundary control if (a [i].c [j] < rangeMin [j] || a [i].c [j] > rangeMax [j]) { a [i].c [j] = rangeMin [j] + (rangeMax [j] - rangeMin [j]) * u.RNDprobab (); } } } //---------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } } //——————————————————————————————————————————————————————————————————————————————
3. Результаты тестов
Мы тщательно рассмотрели и проанализировали все известные версии этого алгоритма. Теперь пришло время сосредоточиться на их практических результатах и выводах, которые мы можем сделать. Предлагаю подробно остановиться, как каждая из модификаций повлияла на производительность, точность и эффективность. Это позволит нам лучше понять, какие именно изменения оказались наиболее успешными, и в каком направлении стоит двигаться дальше.
Итак, первая версия модификации показала примерно сопоставимые результаты в общем балле, однако результаты значительно улучшились на функции Hilly c 1000 переменными и на функции Forest с 50 и 1000 переменными.
ACS|Artificial Cooperative Search m1|1.0|0.7|
=============================
5 Hilly's; Func runs: 10000; result: 0.7130880902279995
25 Hilly's; Func runs: 10000; result: 0.7565145335137569
500 Hilly's; Func runs: 10000; result: 0.31899537529427235
=============================
5 Forest's; Func runs: 10000; result: 0.9999999999866176
25 Forest's; Func runs: 10000; result: 0.9555551824899264
500 Forest's; Func runs: 10000; result: 0.24186829565864398
=============================
5 Megacity's; Func runs: 10000; result: 0.6607692307692307
25 Megacity's; Func runs: 10000; result: 0.5038461538461539
500 Megacity's; Func runs: 10000; result: 0.13922307692307825
=============================
All score: 5.28986 (58.78%)
Вторая версия алгоритма показала заметное улучшение результатов на всех тестовых функциях с 50 и 1000 переменных, но при этом результаты стали значительно хуже на Megacity c 10 переменными (чрезвычайно большой разброс результатов) по сравнению с базовой версией. Это указывает на то, что движение в данном направлении является перспективным (хотя есть спорные моменты), и стоит продолжить работу над дальнейшими модификациями.
ACS|Artificial Cooperative Search m2|2.0|0.7|
=============================
5 Hilly's; Func runs: 10000; result: 0.7682797921658492
25 Hilly's; Func runs: 10000; result: 0.7664893907210706
500 Hilly's; Func runs: 10000; result: 0.31831672493319296
=============================
5 Forest's; Func runs: 10000; result: 0.9999997349437437
25 Forest's; Func runs: 10000; result: 0.9534110489423269
500 Forest's; Func runs: 10000; result: 0.24425762117784502
=============================
5 Megacity's; Func runs: 10000; result: 0.6176923076923077
25 Megacity's; Func runs: 10000; result: 0.5384615384615385
500 Megacity's; Func runs: 10000; result: 0.14057692307692446
=============================
All score: 5.34749 (59.42%)
К сожалению, самая казалось бы перспективная третья модификация, не оправдала надежд и показала общий результат несколько хуже, чем базовая версия алгоритма. Хотя стоит отметить, что значительно улучшились результаты на гладкой функции Hilly с 10 переменными, алгоритм демонстрирует более высокую точность сходимости именно на гладких функциях с небольшим количеством переменных.
ACS|Artificial Cooperative Search m3|10.0|0.9|
=============================
5 Hilly's; Func runs: 10000; result: 0.8836798635515516
25 Hilly's; Func runs: 10000; result: 0.715438105666966
500 Hilly's; Func runs: 10000; result: 0.3011611038405591
=============================
5 Forest's; Func runs: 10000; result: 0.9893902762645717
25 Forest's; Func runs: 10000; result: 0.7954795408759185
500 Forest's; Func runs: 10000; result: 0.21910399769909533
=============================
5 Megacity's; Func runs: 10000; result: 0.6315384615384615
25 Megacity's; Func runs: 10000; result: 0.49876923076923074
500 Megacity's; Func runs: 10000; result: 0.12683076923077044
=============================
All score: 5.16139 (57.35%)
Визуализация второй модификации алгоритма. При небольшом количестве переменных, есть достаточно большой разброс в результатах на функциях Hilly и Megacity, при этом алгоритм чувствует себя превосходно на остроконечной гладкой функции Forest.
ACSm2 на тестовой функции Hilly.
ACSm2 на тестовой функции Forest.
ACSm2 на тестовой функции Megacity.
Выводы
В целом, можно сделать следующие выводы:
1. Первая модификация алгоритма ACS, с добавлением аугментированных форм матриц "A" и "B", улучшила точность решений, особенно на функциях Hilly c 1000 переменными и Forest с 50 и 1000 переменными.
2. Вторая модификация, изменяющая подход к заполнению матриц "Predator" и "Prey" и использование случайных сравнений для обновления матриц, показала заметное улучшение результатов на всех тестовых функциях с 50 и 1000 переменными, но привела к большему разбросу результатов на функции Megacity c 10 переменными.
3. Третья модификация, с фокусом на использовании приспособленности для формирования популяций "Predator" и "Prey", не оправдала надежд, показав общий результат несколько хуже, чем базовая версия алгоритма, хотя и улучшила точность сходимости на гладких функциях с небольшим количеством переменных.
Таким образом, каждая модификация имеет свои сильные и слабые стороны, и для дальнейшего развития алгоритма необходимо учитывать эти особенности, чтобы создать более эффективную и универсальную версию алгоритма ACS.
Возможные направления для улучшения:
1. Модификация механизмов поиска:
- Проанализировать текущие механизмы поиска, используемые в алгоритме, и рассмотреть возможность их дальнейшей оптимизации.
- Изучить, можно ли ввести дополнительные механизмы, такие как адаптивные шаги поиска, чтобы повысить эффективность поиска.
2. Исследование гибридных подходов:
- Рассмотреть возможность комбинирования текущего алгоритма с другими оптимизационными методами, чтобы воспользоваться преимуществами различных подходов. Например, можно попробовать интегрировать элементы эволюционных алгоритмов или методов роевого интеллекта для повышения разнообразия и скорости сходимости.
3. Анализ и улучшение механизма взаимодействия между популяциями:
- Изучить, как можно усовершенствовать способ взаимодействия между популяциями "A" и "B", чтобы они более эффективно дополняли друг друга в процессе поиска. Возможно, стоит рассмотреть более сложные схемы обмена информацией или совместного обучения между популяциями.
Рисунок 1. Цветовая градация модификаций алгоритма по соответствующим тестам для сравнения с базовой версией. Белым цветом подсвечены результаты больше или равные 0.99
Рисунок 2. Гистограмма результатов модификаций алгоритма (по шкале от 0 до 100, чем больше, тем лучше,
где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Общие плюсы и минусы модифицированных версий алгоритма искусственного кооперативного поиска (ACS):
Плюсы:
- Малое количество внешних параметров (всего лишь 1).
- Хорошая сходимость на различных типах функций.
Минусы:
- Разброс результатов на функциях с малой размерностью.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Элементы корреляционного анализа в MQL5: Критерий независимости хи-квадрат Пирсона и корреляционное отношение
Введение в MQL5 (Часть 3): Изучаем основные элементы MQL5
Машинное обучение и Data Science (Часть 19): Совершенствуем AI-модели с помощью AdaBoost
Разработка и тестирование торговых систем на основе Канала Кельтнера
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования