Популяционные алгоритмы оптимизации: Искусственные мультисоциальные поисковые объекты (artificial Multi-Social search Objects, MSO)
527
7
Содержание:
1. Введение
2. Описание алгоритма
3. Результаты тестов
1. Введение
В предыдущей статье мы обсудили эволюцию социальных групп, где они перемещались свободно в пространстве поиска. Однако в данной статье мы предлагаем изменить эту концепцию и предположить, что группы перемещаются между секторами, перепрыгивая из одного в другой. Все группы имеют свои центры, которые обновляются на каждой итерации алгоритма. Кроме того, мы вводим понятие памяти как для группы в целом, так и для каждой отдельной частицы в ней. Используя эти изменения, наш алгоритм теперь позволяет группам перемещаться из сектора в сектор, основываясь на информации о лучших решениях.
Эта новая модификация открывает новые возможности для исследования эволюции социальных групп. Переход к секторам позволяет группам обмениваться информацией и опытом внутри каждого сектора, что может привести к более эффективному поиску и адаптации. Введение памяти позволяет группам сохранять информацию о предыдущих перемещениях и использовать ее для принятия решений о будущих перемещениях.
В данной статье мы проведем серию экспериментов, чтобы исследовать, как эти новые концепции влияют на поисковые качества алгоритма. Мы будем анализировать взаимодействие между группами, их способность к сотрудничеству и координации, а также их способность к обучению и адаптации. Наши результаты могут пролить свет на эволюцию социальных систем и помочь лучше понять, как группы формируются, развиваются и приспосабливаются к изменяющейся среде.
В заключение, мы обсудим возможности дальнейшего улучшения модифицированного алгоритма и его применение в различных областях. Модификации, введенные в данной работе, позволяют более эффективно исследовать пространство решений и находить оптимальные значения. Это может быть полезно для исследователей и практиков, работающих в области оптимизации и поиска решений.
2. Описание алгоритма
Конечная цель алгоритма, интегрирующего принципы социальных групп, состоит в том, чтобы создать эффективную систему координации и сотрудничества между участниками группы. Вот общие принципы, которые могут быть интегрированы внутрь такого алгоритма:
- Алгоритм перемещения: позволяет группе перемещаться между различными секторами или областями. Это позволит группе исследовать разнообразные ресурсы и опыт, а также обмениваться не просто информацией об отдельных координатах, а метаданными в виде секторов с другими группами.
- Разделение ролей и специализация: предоставляет возможность участникам группы выбирать и специализироваться в определенных областях. Это позволит группе эффективно использовать свои ресурсы и навыки для достижения общих целей. Особенно это может быть полезно при решении задач с многомерными пространствами, где присутствуют одновременно различные по своим свойствам поверхности функций (как гладкие, так и дискретные).
- Кооперация и взаимодействие: позволяют участникам группы сотрудничать и взаимодействовать друг с другом. Это может включать обмен информацией, обсуждение идей, а также интерполяцию и экстраполяцию в неизвестные области.
- Конфликт и разрешение конфликтов: механизмы разрешения конфликтов внутри группы. Это может включать установление правил и процедур, посредничество и диалог для разрешения разногласий и споров. Например, чтобы предотвратить конкуренцию частиц за одни и те же участки и позволить им экономить драгоценные итерации алгоритма.
- Лидерство и организация: возможность наличия лидеров в группе, которые обеспечивают организацию, координацию и принятие решений. Лидеры должны быть способны мотивировать и вести группу к достижению целей.
- Обмен знаниями и опытом: позволяют группе активно обмениваться знаниями и опытом между участниками. Это поможет группе учиться на примере других, адаптироваться к новым ситуациям и принимать более информированные решения. Возможность построения сложных логических связей между координатами, а не только использование стохастического исследования пространства.
- Учет памяти группы: позволяющие группе сохранять информацию о предыдущих перемещениях, ролях, специализациях, сотрудничестве и решении конфликтов. Это позволит группе использовать накопленный опыт для принятия более обоснованных решений о будущих перемещениях и взаимодействии.
Интеграция этих общих принципов в алгоритм позволит создать более эффективную социальную систему, способную к сотрудничеству, координации, обмену информацией и адаптации к изменяющейся среде.
Для лучшего понимания в контексте алгоритма поясним значение сектора. Сектор - это часть области определения оптимизируемого параметра (осей координат многомерного пространства). Разбивка осей по секторам одинакова для всех групп, две группы G0 и G1 могут располагаться на секторах соответствующих координат, например, так:
G0 (X) |---V---|-------|-------|-------|-------|
G0 (Y) |-------|---V---|-------|-------|-------|
G0 (Z) |-------|-------|-------|-------|---V---|
-----------------------------------------------------
G1 (X) |-------|-------|---V---|-------|-------|
G1 (Y) |---V---|-------|-------|-------|-------|
G1 (Z) |-------|-------|-------|---V---|-------|
Одной из основных идей алгоритма - дать возможность группам обмениваться знанием об удачных секторах, сохраняя при этом некоторую долю стохастичности в свободе выбора секторов.
Теперь переходим к описанию первой концепции нашего алгоритма. Сначала рассмотрим алгоритм со случайным перемещением групп по секторам, без учета памяти о лучших решениях.
Псевдокод алгоритма следующий:
1. Случайно выбрать сектора для групп
2. Создать точки равномерно по секторам
3. Вычислить фитнес-функцию
4. Обновить глобальное решение (лучшая частица популяции)
5. Получить значение лучшей частицы в группе на текущей итерации
6. Обновить память лучших решений на секторах для каждой группы
7. Обновить память лучших решений на секторах для каждой частицы
8. Обновить лучшее решение по группе
9. Для группы спрашиваем для каждой координаты отдельно другую группу, лучше ли его решение:
9. a) если да : то берем его сектор
9. b) если нет: с вероятностью выбрать другой сектор
10. Создать частицы по вероятностям:
10. a) если да : равномерно по сектору
10. b) если нет: уточнить решение группы
11. Повторить с п.4.
Внутреннюю архитектуру группы и разметку координат по секторам можем представить следующим образом:
Group [groups]|
|-----------------------------------------
|fB
|-----------------------------------------
|fBLast
|-----------------------------------------
|cB [coords]
|-----------------------------------------
|cLast [coords]
|-----------------------------------------
|centre [coords]
|-----------------------------------------
|secInd [coords]
|-----------------------------------------
|secIndLast [coords]
|-----------------------------------------
|p [groupSize]|
| |-------------------
| |c [coords]
| |f
m [coords]|
|--------------
|min [sectNumb]
|max [sectNumb]
Переходим к описанию кода.
Для разметки пространства поиска по секторам нам понадобится задание границ секторов, для этого напишем структуру "S_Min_Max". Давайте разберем ее по частям:
Структура "S_Min_Max" имеет два поля данных: "min" и "max", которые представляют границу сектора слева, а "max" - границу сектора справа. Размер обоих массивов равен количеству секторов, которое задается параметром "sectNumb".
Также в структуре определена функция "Init", которая инициализирует массивы "min" и "max". Она принимает один параметр "sectNumb", который указывает количество секторов. Внутри функции "Init" изменяется размер массивов "min" и "max" в соответствии с переданным параметром "sectNumb". Таким образом, данная структура предоставляет способ хранения границ секторов и их инициализации с помощью функции "Init".
//—————————————————————————————————————————————————————————————————————————————— struct S_Min_Max { void Init (int sectNumb) { ArrayResize (min, sectNumb); ArrayResize (max, sectNumb); } double min []; //sector border on the left, size - number of sectors double max []; //sector border on the right, size - number of sectors }; //——————————————————————————————————————————————————————————————————————————————
Для описания частицы - члена группы, напишем структуру "S_Particle", которая содержит два поля: "c" и "f".
- "c" - массив для хранения координат частицы. Размер массива определяется параметром "coords", переданным в функцию "Init".
- "f" - значение фитнес-функции частицы, инициализированное числом "-DBL_MAX" в функции "Init".
Таким образом, данная структура предоставляет контейнер для хранения координат частицы и связанного с ней значения функции.
//—————————————————————————————————————————————————————————————————————————————— struct S_Particle { void Init (int coords, int sectNumb) { ArrayResize (c, coords); f = -DBL_MAX; } double c []; double f; }; //——————————————————————————————————————————————————————————————————————————————
Группу частиц объединим в структуру данных "S_Group". Структура "S_Group" содержит несколько полей данных:
- "p" представляет массив структур "S_Particle", который служит для хранения частиц группы. Размер массива "p" определяется параметром "groupSize", переданным в функцию "Init". Внутри цикла "for" происходит инициализация каждой частицы с помощью функции "Init" из структуры "S_Particle".
- "secInd" и "secIndLast" - массивы хранят индексы секторов на каждой координате. Размер массивов "secInd" и "secIndLast" определяется параметром "coords".
- "cB" и "cBLast" - массивы хранят лучшие координаты в группе и предыдущие лучшие координаты соответственно. Размер массивов "cB" и "cBLast" также определяется параметром "coords".
- "fB" и "fBLast" - переменные хранят лучший результат и предыдущий лучший результат в группе соответственно.
- "centre" - массив хранит центр. Размер массива "centre" также определяется параметром "coords" и служит для определения лучших координат по сектору для всей группы.
Функция "Init" инициализирует все массивы и переменные в структуре "S_Group". Она принимает три параметра: "coords" - количество координат, "groupSize" - размер группы, "sectNumb" - количество секторов.
Таким образом, данная структура предоставляет контейнер для хранения информации о группе частиц. Частицы подчиняются групповым правилам и не взаимодействуют с частицами других групп, взаимодействие происходит путем косвенной передачи информации посредством секторов на уровне групп.
//—————————————————————————————————————————————————————————————————————————————— struct S_Group { void Init (int coords, int groupSize, int sectNumb) { ArrayResize (p, groupSize); ArrayResize (secInd, coords); ArrayResize (cB, coords); ArrayResize (cBLast, coords); ArrayResize (secIndLast, coords); ArrayResize (centre, coords); for (int i = 0; i < groupSize; i++) p [i].Init (coords, sectNumb); fB = -DBL_MAX; fBLast = -DBL_MAX; } S_Particle p []; int secInd []; //sector index on the coordinate, size is the number of coordinates int secIndLast []; //previous index of the sector on the coordinate, the size is the number of coordinates double cB []; //the best coord's in the group double cBLast []; //the previous best coord's in the group double fB; //the best result in the group double fBLast; //the previous best result in the group double centre []; }; //——————————————————————————————————————————————————————————————————————————————
Опишем агента оптимизации структурой "S_Agent", посредством неё будет происходить передача информации от частиц групп к рассчету фитнес-функции. Структура "S_Agent" содержит два поля:
- "c" - массив хранит координаты агента.
- "f" - хранит фитнес-функцию агента.
Функция "Init" инициализирует массив "c" и переменную "f" в структуре "S_Agent". Она принимает один параметр "coords", который определяет размер массива "c".
//—————————————————————————————————————————————————————————————————————————————— struct S_Agent { void Init (const int coords) { ArrayResize (c, coords); f = -DBL_MAX; } double c []; //coordinates double f; //fitness }; //——————————————————————————————————————————————————————————————————————————————
Опишем мультисоциальный алгоритм классом "C_AO_MSO". Класс содержит несколько полей данных и методов:
- "cB" - массив хранит лучшие координаты.
- "fB" - переменная хранит фитнес лучших координат.
- "a" - массив структур "S_Agent", который хранит агентов.
- "rangeMax", "rangeMin" и "rangeStep" - массивы хранят максимальный и минимальный диапазоны поиска и шаг соответственно.
Класс также содержит несколько методов:
- "Init" инициализирует все члены данных класса. Он принимает параметры: количество координат "coordinatesNumberP", размер популяции "populationSizeP", количество групп "groupsP", количество секторов "sectorsNumberP" на координате, вероятность случайного сектора "probRNSsectorP", вероятность равномерного распределения "probUniformSectorP" для частицы, вероятность уточнения результата группы "probClgroupP" и степень "powerP" для функции степенного закона распределения.
- "Moving" и "Revision" - методы для выполнения основных операций с группами и частицами групп.
В целом, класс "C_AO_MSO" представляет собой реализацию алгоритма оптимизации с использованием множественного поиска с оптимальным распределением агентов. Он содержит данные и методы для управления агентами, группами, секторами и выполнения операций поиска и уточнения результата.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_MSO { //---------------------------------------------------------------------------- public: double cB []; //best coordinates public: double fB; //FF of the best coordinates public: S_Agent a []; //agents public: double rangeMax []; //maximum search range public: double rangeMin []; //manimum search range public: double rangeStep []; //step search public: void Init (const int coordinatesNumberP, //coordinates number const int populationSizeP, //population size const int groupsP, //number of groups const int sectorsNumberP, //sectors number const double probRNSsectorP, //probability random sector const double probUniformSectorP, //probability uniform distribution const double probClgroupP, //probability of clarifying the group's result const double powerP); //power public: void Moving (); public: void Revision (); //---------------------------------------------------------------------------- private: int coords; //coordinates number private: int popSize; //population size private: int sectNumb; //sectors number private: double sectorSpace []; //sector space private: S_Group gr []; //groups private: S_Min_Max min_max_Sector []; //sector boundary by coordinates private: int groups; //number of groups private: int sectorsNumber; //sectors number private: double probRNSsector; //probability random sector private: double probUniformSector; //probability uniform distribution private: double probClgroup; //probability of clarifying the group's result private: double power; //power private: bool revision; private: double SeInDiSp (double In, double InMin, double InMax, double Step); private: double RNDfromCI (double min, double max); private: double Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool revers); private: double PowerDistribution (const double In, const double outMin, const double outMax, const double power); }; //——————————————————————————————————————————————————————————————————————————————
Метод "Init" инициализирует объект класса "C_AO_MSO" с заданными параметрами. Давайте разберем этот код по частям:
В начале функции происходит инициализация переменных и членов данных класса. Генератор случайных чисел сбрасывается с использованием текущего времени в микросекундах. Затем переменная "fB" устанавливается на минимально возможное значение типа double "-DBL_MAX", а переменная "revision" устанавливается в "false".
Затем параметры, переданные в функцию, присваиваются соответствующим полям класса.
Для распределения частиц популяции по группам создается массив "partInSwarms", который будет хранить количество частиц в каждой группе. Размер массива устанавливается равным количеству групп. Затем переменная "particles" вычисляет количество частиц в каждой группе путем деления общего размера популяции "popSize" на количество групп "groups".
Если есть остаток "lost", то он распределяется по группам. Цикл будет выполняться, пока остаток не будет равен 0.
Далее происходит изменение размеров массивов и инициализация объектов.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_MSO::Init (const int coordinatesNumberP, //coordinates number const int populationSizeP, //population size const int groupsP, //number of groups const int sectorsNumberP, //sectors number const double probRNSsectorP, //probability random sector const double probUniformSectorP, //probability uniform distribution const double probClgroupP, //probability of clarifying the group's result const double powerP) //power { MathSrand ((int)GetMicrosecondCount ()); // reset of the generator fB = -DBL_MAX; revision = false; coords = coordinatesNumberP; popSize = populationSizeP; groups = groupsP; sectNumb = sectorsNumberP; probRNSsector = probRNSsectorP; probUniformSector = probUniformSectorP; probUniformSector = probClgroupP; power = powerP; //---------------------------------------------------------------------------- int partInSwarms []; ArrayResize (partInSwarms, groups); int particles = popSize / groups; ArrayInitialize (partInSwarms, particles); int lost = popSize - particles * groups; if (lost > 0) { int pos = 0; while (true) { partInSwarms [pos]++; lost--; pos++; if (pos >= groups) pos = 0; if (lost == 0) break; } } //---------------------------------------------------------------------------- ArrayResize (rangeMax, coords); ArrayResize (rangeMin, coords); ArrayResize (rangeStep, coords); ArrayResize (cB, coords); ArrayResize (gr, groups); for (int s = 0; s < groups; s++) gr [s].Init (coords, partInSwarms [s], sectNumb); ArrayResize (sectorSpace, coords); ArrayResize (a, popSize); for (int i = 0; i < popSize; i++) a [i].Init (coords); } //——————————————————————————————————————————————————————————————————————————————
Метод "Moving" отвечает за перемещение частиц на первой итерации и выполняет функцию инициализации групп и их частиц первоначальным положением.
В начале функции проверяется значение переменной "revision", для обеспечения только однократного выполнения, и если оно равно "false".
Первая часть кода отвечает за разделение пространства на сектора и инициализацию массива "min_max_Sector". Для каждой координаты "c" вычисляется размер сектора "sectorSpace[c]" как разница между "rangeMax[c]" и "rangeMin[c]", деленная на количество секторов "sectNumb". Затем для каждой координаты и каждого сектора инициализируются значения "min" и "max" в массиве "min_max_Sector".
Далее происходит расстановка частиц в пространстве поиска. Для каждой группы "s" выбираются случайные секторы для каждой координаты. Значения индексов секторов сохраняются в массиве "secInd" для каждой группы. Затем происходит случайное распределение частиц группы внутри выбранных секторов. Для каждой частицы "p" и каждой координаты "c" выбирается случайное значение "cd" в пределах минимального и максимального значения сектора, и это значение сохраняется в координатах частиц.
Последний блок кода отвечает за отправку частиц агентам. Создается счетчик "cnt", который будет использоваться для перебора агентов. Затем для каждой группы "s" и каждой частицы "p" значения координат частицы копируются в массив "a[cnt].c", где "cnt" увеличивается после каждой копии.
Итак, метод отвечает за случайное первоначальное размещение частиц в алгоритме оптимизации, разделяет пространство на секторы, случайным образом выбирает секторы для каждой группы и распределяет частицы внутри выбранных секторов. Затем частицы отправляются агентам для дальнейшей обработки.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_MSO::Moving () { if (!revision) { //marking up sectors-------------------------------------------------------- ArrayResize (min_max_Sector, coords); for (int c = 0; c < coords; c++) { sectorSpace [c] = (rangeMax [c] - rangeMin [c]) / sectNumb; min_max_Sector [c].Init (sectNumb); for (int sec = 0; sec < sectNumb; sec++) { min_max_Sector [c].min [sec] = rangeMin [c] + sectorSpace [c] * sec; min_max_Sector [c].max [sec] = min_max_Sector [c].min [sec] + sectorSpace [c]; } } //-------------------------------------------------------------------------- int sect = 0; //sector double sectMin = 0.0; //sector's min double sectMax = 0.0; //sector's max int ind = 0; //index double cd = 0.0; //coordinate for (int s = 0; s < groups; s++) { //select random sectors for the group------------------------------------- for (int c = 0; c < coords; c++) { ind = (int)(RNDfromCI (0, sectNumb)); if (ind >= sectNumb) ind = sectNumb - 1; gr [s].secInd [c] = ind; gr [s].secIndLast [c] = ind; } //random distribute the particles of the group within the sectors--------- for (int p = 0; p < ArraySize (gr [s].p); p++) { for (int c = 0; c < coords; c++) { sect = gr [s].secInd [c]; cd = RNDfromCI (min_max_Sector [c].min [sect], min_max_Sector [c].max [sect]); gr [s].p [p].c [c] = SeInDiSp (cd, rangeMin [c], rangeMax [c], rangeStep [c]); } } } //-------------------------------------------------------------------------- //send particles to agents int cnt = 0; for (int s = 0; s < groups; s++) { for (int p = 0; p < ArraySize (gr [s].p); p++) { ArrayCopy (a [cnt].c, gr [s].p [p].c, 0, 0, WHOLE_ARRAY); cnt++; } } revision = true; } } //——————————————————————————————————————————————————————————————————————————————
Основные операции по перемещению групп и их частиц по пространству поиска выполняет метод "Revision":
- Обновление лучшего глобального решения путем сравнения значений фитнес-функции для каждой частицы с текущим лучшим значением. Если значение функции цели для текущей частицы превышает текущее лучшее значение, оно становится новым лучшим значением, и ее координаты копируются в переменную "cB".
- Перенос результатов с агентов на частицы и определение лучшей частицы в каждой группе. Значение фитнес-функции каждой частицы устанавливается равным значению функции цели агента, соответствующего этой частице. Если значение фитнес-функции частицы превышает текущее лучшее значение в группе, оно становится новым лучшим значением, и ее координаты копируются в переменную "cB" группы.
- Обновление лучшего решения для каждой группы. Если новое лучшее значение в группе превышает предыдущее, оно становится текущим лучшим значением, и его координаты копируются в переменные "cBLast" и "secIndLast" группы.
- Для каждой координаты каждой группы проверяется, есть ли другая группа с лучшим решением. Если такая группа существует, сектор и центр текущей группы обновляются значениями сектора и центра группы с лучшим решением. В противном случае сектор и центр остаются неизменными.
- Создание новых частиц на основе вероятностей. Для каждой группы и каждой частицы в группе генерируются новые значения координат на основе вероятностей. Вероятность выбора равномерного распределения или распределения с использованием функции "PowerDistribution" определяется параметрами "probUniformSector" и "power".
- Перенос созданных частиц на агентов для дальнейшего использования в следующей итерации алгоритма оптимизации.
Метод выполняет обновление решений в каждой итерации, используя информацию о лучших решениях в группах и вероятностях для создания новых частиц.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_MSO::Revision () { //---------------------------------------------------------------------------- //Update the best global solution for (int i = 0; i < popSize; i++) { if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY); } } //---------------------------------------------------------------------------- //Transfer the results from the agents to the particles //and get the value of the best particle in the group at the current iteration int cnt = 0; for (int s = 0; s < groups; s++) { gr [s].fB = -DBL_MAX; for (int p = 0; p < ArraySize (gr [s].p); p++) { gr [s].p [p].f = a [cnt].f; if (a [cnt].f > gr [s].fB) { gr [s].fB = a [cnt].f; ArrayCopy (gr [s].cB, a [cnt].c, 0, 0, WHOLE_ARRAY); } cnt++; } } int sector = 0; //---------------------------------------------------------------------------- //Update the best solution for the group for (int s = 0; s < groups; s++) { if (gr [s].fB > gr [s].fBLast) { gr [s].fBLast = gr [s].fB; ArrayCopy (gr [s].cBLast, gr [s].cB, 0, 0, WHOLE_ARRAY); ArrayCopy (gr [s].secIndLast, gr [s].secInd, 0, 0, WHOLE_ARRAY); } ArrayCopy (gr [s].centre, gr [s].cBLast); } //---------------------------------------------------------------------------- int sect = 0; //sector double sectMin = 0.0; //sector's min double sectMax = 0.0; //sector's max int ind = 0; //index double cd = 0.0; //coordinate for (int s = 0; s < groups; s++) { for (int c = 0; c < coords; c++) { if (RNDfromCI (0.0, 1.0) < 0.6) { ind = (int)(RNDfromCI (0, groups)); if (ind >= groups) ind = groups - 1; if (ind == s) ind++; if (ind > groups - 1) ind = 0; if (gr [ind].fBLast > gr [s].fBLast) { gr [s].secInd [c] = gr [ind].secIndLast [c]; gr [s].centre [c] = gr [ind].cBLast [c]; } } else { if (RNDfromCI (0.0, 1.0) < probRNSsector) { ind = (int)(RNDfromCI (0, sectNumb)); if (ind >= sectNumb) ind = sectNumb - 1; gr [s].secInd [c] = ind; sect = gr [s].secInd [c]; cd = RNDfromCI (min_max_Sector [c].min [sect], min_max_Sector [c].max [sect]); gr [s].centre [c] = SeInDiSp (cd, rangeMin [c], rangeMax [c], rangeStep [c]); } else gr [s].secInd [c] = gr [s].secIndLast [c]; } } } //---------------------------------------------------------------------------- for (int s = 0; s < groups; s++) { for (int p = 0; p < ArraySize (gr [s].p); p++) { for (int c = 0; c < coords; c++) { sect = gr [s].secInd [c]; if (RNDfromCI (0.0, 1.0) < probUniformSector) { cd = RNDfromCI (min_max_Sector [c].min [sect], min_max_Sector [c].max [sect]); } else { cd = PowerDistribution (gr [s].centre [c], min_max_Sector [c].min [sect], min_max_Sector [c].max [sect], power); } gr [s].p [p].c [c] = SeInDiSp (cd, rangeMin [c], rangeMax [c], rangeStep [c]); } } } //---------------------------------------------------------------------------- cnt = 0; for (int s = 0; s < groups; s++) { for (int p = 0; p < ArraySize (gr [s].p); p++) { ArrayCopy (a [cnt].c, gr [s].p [p].c, 0, 0, WHOLE_ARRAY); cnt++; } } } //——————————————————————————————————————————————————————————————————————————————
Далее рассмотрим тот же алгоритм, но с добавлением памяти для группы и ее частиц и некоторыми другими изменениями в логике поисковой стратегии.
Псевдокод алгоритма изменим, с учётом наличия памяти у групп и частиц:
- 1. Случайно выбрать сектора для групп
- 2. Создать точки равномерно по секторам
- 4. Вычислить ФФ
- 5. Обновить глобальное решение (лучшая частица популяции)
- 6. Получить значение лучшей частицы в группе на текущей итерации
- 7. Обновить память лучших решений на секторах для каждой группы
- 8. Обновить память лучших решений на секторах для каждой частицы
- 9. Обновить лучшее решение по группе
- 10. Для группы спрашиваем для каждой координаты отдельно другую группу, лучше ли его решение:
- 10. a) если да : то берем его сектор
- 10. b) если нет: с вероятностью выбрать другой сектор
- 11. Создать частицы по вероятностям:
- 11. a) если да : равномерно по сектору
- 11. b) если нет: (вероятность ? (уточнить решение группы) : (уточнить своё решение))
- 12. Повторить с п.4.
Добавление памяти теоретически позволит группе сохранять информацию о предыдущих перемещениях и использовать ее для принятия решений о будущих. Это может помочь группам лучше адаптироваться к изменяющейся среде и эффективнее исследовать пространство решений.
Внесём изменения во внутреннюю архитектуру группы следующим образом:
|-----------------------------------------
|fB
|-----------------------------------------
|fBLast
|-----------------------------------------
|cB [coords]
|-----------------------------------------
|cBLast [coords]
|-----------------------------------------
|secInd [coords]
|-----------------------------------------
|secIndLast [coords]
|-----------------------------------------
|sMemory [coords]|
| |---------------
| |cB [sectNumb]
| |fB [sectNumb]
|-----------------------------------------
|p [groupSize] |
| |-------------------
| |c [coords]
| |f
| |pMemory [coords]|
| |--------
| |cB [sectNumb]
| |fB [sectNumb]
Добавим структуру "S_Memory", описывающую память. Для групп и частиц память будет выглядеть одинаково и содержать два массива "cB" и "fB" для хранения информации о лучших координатах и фитнес-функции для этих координат.
//—————————————————————————————————————————————————————————————————————————————— struct S_Memory { void Init (int sectNumb) { ArrayResize (cB, sectNumb); ArrayResize (fB, sectNumb); ArrayInitialize (fB, -DBL_MAX); } double cB []; //the best sector coordinate, size is the number of sectors double fB []; //FF is the best coordinate on a sector, size is the number of sectors }; //——————————————————————————————————————————————————————————————————————————————
Соответственно, в структуры частиц и групп добавим объявления памяти:
//—————————————————————————————————————————————————————————————————————————————— struct S_Particle { <..............code is hidden.................> S_Memory pMemory []; //particle memory, size - the number of coordinates }; //—————————————————————————————————————————————————————————————————————————————— //—————————————————————————————————————————————————————————————————————————————— struct S_Group { <..............code is hidden.................> S_Memory sMemory []; //group memory, size - number of coordinates }; //——————————————————————————————————————————————————————————————————————————————
Изменения коснулись и метода "Revision":
- Обновление лучших координат секторов в памяти роя. Для каждой группы и каждой координаты перебираются все секторы. Если значение "fB" группы на секторе больше, чем значение "fB" в памяти о секторе, то "fB" и "cB" обновляются в памяти.
- Обновление лучших позиций в памяти частиц. Если значение фитнес-функции частицы больше, чем значение в памяти частицы, то "fB" и "cB" обновляются в памяти.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_MSO::Revision () { //---------------------------------------------------------------------------- //Update the best global solution for (int i = 0; i < popSize; i++) { if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY); } } //---------------------------------------------------------------------------- //Transfer the results from the agents to the particles //and get the value of the best particle in the group at the current iteration int cnt = 0; for (int s = 0; s < groups; s++) { gr [s].fB = -DBL_MAX; for (int p = 0; p < ArraySize (gr [s].p); p++) { gr [s].p [p].f = a [cnt].f; if (a [cnt].f > gr [s].fB) { gr [s].fB = a [cnt].f; ArrayCopy (gr [s].cB, a [cnt].c, 0, 0, WHOLE_ARRAY); } cnt++; } } //---------------------------------------------------------------------------- //Update the best sector coordinates in the swarm's memory int sector = 0; for (int s = 0; s < groups; s++) { for (int c = 0; c < coords; c++) { sector = gr [s].secInd [c]; if (gr [s].fB > gr [s].sMemory [c].fB [sector]) { gr [s].sMemory [c].fB [sector] = gr [s].fB; gr [s].sMemory [c].cB [sector] = gr [s].cB [c]; } } } //---------------------------------------------------------------------------- //Update in the memory of the particles their best positions by sector sector = 0; for (int s = 0; s < groups; s++) { for (int p = 0; p < ArraySize (gr [s].p); p++) { for (int c = 0; c < coords; c++) { sector = gr [s].secInd [c]; if (gr [s].p [p].f > gr [s].p [p].pMemory [c].fB [sector]) { gr [s].p [p].pMemory [c].fB [sector] = gr [s].p [p].f; gr [s].p [p].pMemory [c].cB [sector] = gr [s].p [p].c [c]; } } } } //---------------------------------------------------------------------------- //Update the best solution for the group for (int s = 0; s < groups; s++) { if (gr [s].fB > gr [s].fBLast) { gr [s].fBLast = gr [s].fB; ArrayCopy (gr [s].cBLast, gr [s].cB, 0, 0, WHOLE_ARRAY); ArrayCopy (gr [s].secIndLast, gr [s].secInd, 0, 0, WHOLE_ARRAY); } } //---------------------------------------------------------------------------- int sect = 0; //sector double sectMin = 0.0; //sector's min double sectMax = 0.0; //sector's max int ind = 0; //index double cd = 0.0; //coordinate for (int s = 0; s < groups; s++) { for (int c = 0; c < coords; c++) { ind = (int)(RNDfromCI (0, groups)); if (ind >= groups) ind = groups - 1; if (ind == s) ind++; if (ind > groups - 1) ind = 0; if (RNDfromCI (0.0, 1.0) < 0.6) { if (gr [ind].fBLast > gr [s].fBLast) { gr [s].secInd [c] = gr [ind].secIndLast [c]; } } else { if (RNDfromCI (0.0, 1.0) < probRNSsector) { ind = (int)(RNDfromCI (0, sectNumb)); if (ind >= sectNumb) ind = sectNumb - 1; gr [s].secInd [c] = ind; sect = gr [s].secInd [c]; if (gr [s].sMemory [c].fB [sect] == -DBL_MAX) { cd = RNDfromCI (min_max_Sector [c].min [sect], min_max_Sector [c].max [sect]); gr [s].sMemory [c].cB [sect] = SeInDiSp (cd, rangeMin [c], rangeMax [c], rangeStep [c]); } } else gr [s].secInd [c] = gr [s].secIndLast [c]; } } } //---------------------------------------------------------------------------- for (int s = 0; s < groups; s++) { for (int p = 0; p < ArraySize (gr [s].p); p++) { for (int c = 0; c < coords; c++) { sect = gr [s].secInd [c]; if (RNDfromCI (0.0, 1.0) < probUniformSector) { cd = RNDfromCI (min_max_Sector [c].min [sect], min_max_Sector [c].max [sect]); } else { if (RNDfromCI (0.0, 1.0) < probClgroup) { cd = PowerDistribution (gr [s].sMemory [c].cB [sect], min_max_Sector [c].min [sect], min_max_Sector [c].max [sect], power); } else { cd = PowerDistribution (gr [s].p [p].pMemory [c].cB [sect], min_max_Sector [c].min [sect], min_max_Sector [c].max [sect], power); } } gr [s].p [p].c [c] = SeInDiSp (cd, rangeMin [c], rangeMax [c], rangeStep [c]); } } } //---------------------------------------------------------------------------- //send the particles to the agents cnt = 0; for (int s = 0; s < groups; s++) { for (int p = 0; p < ArraySize (gr [s].p); p++) { ArrayCopy (a [cnt].c, gr [s].p [p].c, 0, 0, WHOLE_ARRAY); cnt++; } } } //——————————————————————————————————————————————————————————————————————————————
3. Результаты тестов
Проанализированы результаты тестов алгоритма без учета памяти по частицам и можно заметить, что он демонстрирует достаточно хорошие результаты. Алгоритм занимает положение в числе первой десятки лучших в рейтинговой таблице. Важно отметить, что этот алгоритм служит всего лишь примером логики, и если бы он продемонстрировал выдающиеся результаты, я бы включил его в таблицу. Так же остается множество возможностей для дальнейшей реализации и модификации данного алгоритма.
Хотя результаты не являются выдающимися, однако алгоритм показал хорошие поисковые способности в исследовании различных областей пространства поиска.
C_AO_MSO|60|30|9|0.05|0.05|10.0
=============================
5 Hilly's; Func runs: 10000; result: 0.9313358190790157
25 Hilly's; Func runs: 10000; result: 0.6649184286250989
500 Hilly's; Func runs: 10000; result: 0.3282041522365852
=============================
5 Forest's; Func runs: 10000; result: 0.9522099605531393
25 Forest's; Func runs: 10000; result: 0.5542256622730999
500 Forest's; Func runs: 10000; result: 0.08984352753493675
=============================
5 Megacity's; Func runs: 10000; result: 0.7899999999999998
25 Megacity's; Func runs: 10000; result: 0.33533333333333326
500 Megacity's; Func runs: 10000; result: 0.042983333333333325
=============================
All score: 4.68905 (52.1%)
Следующие результаты относятся к варианту социальных групп с памятью, ухудшение общих результатов алгоритма является небольшим. Тем не менее данный алгоритм занимает достойное место в верхней части рейтинговой таблицы. Это указывает на потенциал алгоритма и его способность достигать удовлетворительных результатов. Мысль о рассмотрении концепции обмена памятью не только между группами, но и между их частицами, является логичным шагом для улучшения алгоритма. Введение такого дополнительного взаимодействия может привести к появлению новых идей и стратегий. Как уже было упомянуто выше в статье, описаны различные сценарии взаимодействия между социальными группами, и я включил только часть из них. Это означает, что есть обширные возможности для модификации и улучшения алгоритма.
C_AO_MSOm|60|30|9|0.1|0.9|0.1|10.0
=============================
5 Hilly's; Func runs: 10000; result: 0.9468984351872132
25 Hilly's; Func runs: 10000; result: 0.5865441453580522
500 Hilly's; Func runs: 10000; result: 0.3186653673403949
=============================
5 Forest's; Func runs: 10000; result: 0.9064162754293653
25 Forest's; Func runs: 10000; result: 0.43175851113448455
500 Forest's; Func runs: 10000; result: 0.06865408175918558
=============================
5 Megacity's; Func runs: 10000; result: 0.6783333333333333
25 Megacity's; Func runs: 10000; result: 0.213
500 Megacity's; Func runs: 10000; result: 0.03310000000000002
=============================
All score: 4.18337 (46.4%)
MSO на тестовой функции Hilly.
MSO на тестовой функции Forest.
MSO на тестовой функции Megacity.
Выводы
С учетом предыдущих рассуждений и результатов, можно добавить следующее:В ходе экспериментов было обнаружено, что алгоритм с памятью показал несколько ниже результаты по сравнению с алгоритмом без памяти. Однако это не означает, что алгоритм с памятью является менее перспективным. Скорее всего, необходимо модифицировать концепцию обмена памятью между группами и частицами, чтобы улучшить его результаты.
Кроме того, стоит отметить, что включение других принципов взаимодействия между социальными группами может значительно повысить эффективность алгоритма с памятью. Введение механизмов сотрудничества, координации и обучения между группами может привести к значительному улучшению показателей и занять алгоритму одну из лидирующих позиций в нашей рейтинговой таблице.
В заключение, исследование предлагает новую концепцию эволюции социальных групп, основанную на перемещении между секторами и использовании памяти. Эти концепции открывают новые возможности для изучения социальных систем и их способности к сотрудничеству, координации и адаптации. Надеюсь, что результаты помогут лучше понять, как социальные группы функционируют и эволюционируют в сложных социальных средах и это даст возможность для продолжения дальнейших исследований в этой области.
Разрабатываем мультивалютный советник (Часть 2): Переход к виртуальным позициям торговых стратегий
Оцениваем будущую производительность с помощью доверительных интервалов
Теория категорий в MQL5 (Часть 22): Другой взгляд на скользящие средние
Нейросети — это просто (Часть 75): Повышение производительности моделей прогнозирования траекторий
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования
На тему сложности ФФ в виде ТС.
Штатный ГА закончил оптимизацию в зеленой рамке.
Повторный запуска ГА первыми же нащупываниями вышел на значительно лучший результат (красная рамка).
Для штатного ГА многократный запуск является рекомендуемым приемом (не знаю, хорошо это или плохо - есть доводы и за, и против).
Теоретический вопрос (можно на практике проверить).
Если добавить в набор фейковый (не участвует в расчетах ФФ) параметр с диапазоном, например, пять значений, будет ли улучшение/ухудшение результатов алгоритма?
Ухудшатся, однозначно. Запуски фф будут тратиться на бесполезные попытки найти "хорошие" фейковые параметры.
Чем больший процент возможных вариантов фейковых параметров от всего количества возможных вариантов параметров, тем влияние будет сильнее - в пределе стремиться к рандомным результатам.
Для штатного ГА многократный запуск является рекомендуемым приемом (не знаю, хорошо это или плохо - есть доводы и за, и против).
Спасибо, это встроил.
Ухудшатся, однозначно. Запуски фф будут тратиться на бесполезные попытки найти "хорошие" фейковые параметры.
Чем больший процент возможных вариантов фейковых параметров от всего количества возможных вариантов параметров, тем влияние будет сильнее - в пределе стремиться к рандомным результатам.
Надо будет проверить.
Надо будет проверить.
Я бы сказал вернее так, фейковые параметры затрудняют поиск. Но при прочих равных результаты будут хуже. Скажем, делать 1мио прогонов фф, результат будет одинаковым, но если делать 1к запусков, то разница уже будет заметна.