Популяционные алгоритмы оптимизации: Алгоритм эволюции разума (Mind Evolutionary Computation, MEC)

MetaTrader 5 — Примеры | 29 сентября 2023, 15:51

850

Andrey Dik

Содержание:

1. Введение
2. Описание алгоритма
3. Результаты тестов

1. Введение

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

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

Одним из интересных подходов в эволюционных вычислениях является алгоритм эволюции разума (Mind Evolutionary Computation, MEC), предложенный в 1998 году Ченгаем и его соавторами. В отличие от ожидаемой моделирования работы человеческого мозга, алгоритм MEC моделирует некоторые аспекты поведения человека в обществе. В этом алгоритме каждый индивид рассматривается как разумный агент, функционирующий в группе людей. При принятии решений индивид ощущает влияние как со стороны членов своей группы, так и со стороны членов других групп. Чтобы достичь высокого положения в обществе, индивиду приходится учиться у наиболее успешных индивидов в своей группе. В то же время, для того чтобы его группа стала более успешной по сравнению с другими группами, все индивиды должны руководствоваться тем же принципом в межгрупповой конкуренции. Важным аспектом алгоритма MEC является обмен информацией между индивидами внутри группы и между группами. Это отражает необходимость непрерывного и свободного обмена информацией для успешного развития общества разумных индивидов.

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

2. Описание алгоритма

Алгоритм MEC может быть интерпретирован как многопопуляционный алгоритм, состоящий из лидирующих и отстающих групп. Число агентов в каждой группе полагается одинаковым. Каждая группа имеет свою локальную доску объявлений, а также существует общая глобальная доска объявлений для всей мультипопуляции.

В оригинальной версии алгоритма MEC, известной как Simple MEC (SMEC), используются операции инициализации групп, локальных состязаний и диссимиляции.

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

Операция локальных состязаний реализует локальный поиск максимума фитнесс-функции каждой группы. Для каждой группы считывается информация о текущем агенте-победителе с ее доски объявлений. Затем определяются новые координаты остальных агентов группы, размещая их случайным образом вокруг победителя с использованием нормального закона распределения. Вычисляются новые счета агентов группы, и определяется новый победитель группы, который имеет максимальный текущий счет. Информация о новом победителе заносится на доску объявлений группы.

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

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

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

Выше сказано о том, что алгоритм моделирует человеческое общество и взаимодействие между его членами. Наиболее просто и понятно можно представить себе понятие "идея", это может быть научная идея, художественная, литературная или любая другая. В обществе всегда присутствуют доминирующие идеи и альтернативные. Мы не будем делить идеи на "лидирующие и отстающие", так как предлагают авторы по отношению к группам. Это, как мы увидим ниже, даст некоторое преимущество алгоритму по сравнению с его базовой версией. Так как каждая идея включает в себя по крайней мере один тезис (тезис - оптимизируемый параметр фитнес функции), то у идеи могут существовать идейные ответвления, так же, как в науке существуют различные научные теории и течения. На рисунке 1 схематично показаны идеи, обозначенные как i1, i2 и т.д. Каждая идея может давать ответвления в пределах, определённых силой мысли (внешний параметр алгоритма), чем дальше ответвление от идеи, тем менее оно вероятно (вероятность и границы идейных ответвлений показаны как расширяющиеся концентрические круги). Если идея показала себя более состоятельной (значение фитнес функции лучше) чем её идейный родитель, то это ответвление заменяет родительскую идею (новая идея как результат идейного ответвления показана на рисунке как i5). На рисунке можно видеть, что ограничений на пересечение идейных границ нет, а значит возможно появление идейных ответвлений с одинаковыми тезисами.

ideas

Рисунок 1. Идеи i1, i2, i3, i4, их границы, пересечения границ и появление новой идеи i5 как результат ветвления идеи i1.

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

Для обеспечения глобального поиска нужно обеспечивать появление новых идей за пределами текущих в популяции, иначе идеи будут "варится" сами в себе (застревание в локальных экстремумах) и не будет появления лучшего значения фитнес функции. Для этого предназначен процесс диссимиляции (разрушение). Мы будем использовать немного другую схему обмена идеями между доминирующей группы (зелёный цвет) идей и альтернативной группы (синий цвет), чем в оригинальном алгоритме. После раздельной сортировки идей в каждой группе, из доминирующей группы удаляем самую худшую, на место нее помещаем лучшую из альтернативной группы, обеспечивая тем самым идейный обмен. На освободившееся место в альтернативной группе помещаем новую идею, которая собирается из тезисов случайно выбранных идей из доминирующей группы (исключая последнюю). Для обеспечения вариативности к этому действию можно добавить случайную компоненту, что оставляю для возможных дальнейших экспериментов исследователям алгоритмов оптимизации. Забор тезисов из идей доминирующей группы повышает комбинаторные способности алгоритма. Ниже на рисунке 2 показана схема замены идеей из альтернативной группы и создание новой.

ideas 2

Рисунок 2. Схема замены идеей из альтернативной группы и создание новой.

Напишем псевдокод MEC для упрощения написания далее кода алгоритма:

1.1 Если первый запуск алгоритма
1.1.1 Создать случайно две группы идей по полю идей (доминирующая и альтернативная)

1.2 Если второй и последующие запуски алгоритма
1.2.1 Для доминирующей идеи создать ответвления по закону Леви*, одно из ответвлений будет результатом комбинации тезисов из доминирующих идей.
1.2.2 Для альтернативной идеи все ответвления создаются по закону Леви*

2 Рассчитать ценность идейных ответвлений

3.1 Если есть идейное ответвление лучше - заменить соответствующую идею
3.2 Отсортировать раздельно доминирующую и альтернативные группы
3.3 Заменить худшую идею доминирующей группы лучшей идеей из альтернативной группы
3.4 Вместо пустующей идеи в альтернативной группе создать новую идею на основе элементов доминирующей группы** (всех кроме последней заменённой)

* - вместо нормального распределения, как у автора
** - вместо создания случайных тезисов, как у автора

Можем заметить по псевдокоду, что оригинальный алгоритм претерпел изменения.

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

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

Переходим к описанию кода алгоритма.

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

//——————————————————————————————————————————————————————————————————————————————
struct S_Idea
{
  void Init (int size)
  {
    ArrayResize (c, size);
    f = -DBL_MAX;
  }
  double c []; //coordinates
  double f;    //fitness
};
//——————————————————————————————————————————————————————————————————————————————

В классе C_AO_MEC опишем алгоритм MEC. Он содержит ряд переменных и методов для работы с этими переменными.

Переменные класса:
- cB: массив, содержащий лучшие координаты
- fB: значение функции приспособленности для лучших координат
- idBr: массив, содержащий идеологические ветви

- rangeMax: массив, содержащий максимальные значения для поиска
- rangeMin: массив, содержащий минимальные значения для поиска
- rangeStep: массив, содержащий шаги для поиска

- leadIdeolGroup: массив, содержащий ведущую идеологическую группу
- alteIdeolGroup: массив, содержащий альтернативную идеологическую группу
- tempIdeolGroup: массив, содержащий временную идеологическую группу

- coordinatesNumber: количество координат
- populationSize: размер популяции
- ideasNumber: количество идей
- thoughtPower: сила мысли
- ideasBr: количество идеологических ветвей
- leadIdGroupSize: размер ведущей идеологической группы
- alteIdGroupSize: размер альтернативной идеологической группы

- vect: вектор для использования приращения координат
- ind: массив индексов
- val: массив значений
- revision: флаг ревизии

Методы класса:
- Init: инициализация класса с передачей параметров
- Moving: выполнение движения
- Revision: ревизия

- Sorting: сортировка идеологических групп
- SeInDiSp: вычисление интервала для поиска
- RNDfromCI: генерация случайного числа из заданного интервала

//——————————————————————————————————————————————————————————————————————————————
class C_AO_MEC
{
  //----------------------------------------------------------------------------
  public: double cB   []; //best coordinates
  public: double fB;      //FF of the best coordinates
  public: S_Idea idBr []; //ideological branches


  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    ideasNumberP,         //ideas number
                     const double thoughtPowerP);       //thought power

  public: void Moving   ();
  public: void Revision ();

  //----------------------------------------------------------------------------
  private: S_Idea leadIdeolGroup []; //leading ideological group
  private: S_Idea alteIdeolGroup []; //alternative ideological group
  private: S_Idea tempIdeolGroup []; //temporal ideological group

  private: int    coordinatesNumber; //coordinates number
  private: int    populationSize;    //population size
  private: int    ideasNumber;       //ideas number
  private: double thoughtPower;      //thought power
  private: int    ideasBr;           //number of ideological branches
  private: int    leadIdGroupSize;   //leading ideological group size
  private: int    alteIdGroupSize;   //alternative ideological group size

  private: double vect    [];        //vector
  private: int    ind     [];
  private: double val     [];
  private: bool   revision;

  private: void   Sorting   (S_Idea &ideas []);
  private: double SeInDiSp  (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

Метод инициализации Init выполняет следующие действия:

- В начале кода устанавливается начальное значение генератора случайных чисел и переменная fB устанавливается на минимальное значение типа double.
- Затем переменные coordinatesNumber, populationSize, ideasNumber и thoughtPower устанавливаются равными значениям, переданным в функцию Init.
- Затем вычисляются значения переменных ideasBr, leadIdGroupSize и alteIdGroupSize на основе значений populationSize и ideasNumber.
- Затем происходит изменение размеров массивов rangeMax, rangeMin, rangeStep, vect, ind, val, tempIdeolGroup и cB с помощью функции ArrayResize.
- Затем создаются объекты класса Ideology в массивах leadIdeolGroup и alteIdeolGroup с помощью циклов for и функции Init.
- Затем создаются объекты класса Ideology в массиве idBr с помощью цикла for и функции Init.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_MEC::Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    ideasNumberP,         //ideas number
                     const double thoughtPowerP)        //thought power
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coordinatesNumber = coordinatesNumberP;
  populationSize    = populationSizeP;
  ideasNumber       = ideasNumberP;
  thoughtPower      = thoughtPowerP;

  ideasBr         = populationSize / ideasNumber;
  leadIdGroupSize = ideasNumber / 2;
  alteIdGroupSize = ideasNumber - leadIdGroupSize;

  ArrayResize (rangeMax,       coordinatesNumber);
  ArrayResize (rangeMin,       coordinatesNumber);
  ArrayResize (rangeStep,      coordinatesNumber);
  ArrayResize (vect,           coordinatesNumber);
  ArrayResize (ind,            alteIdGroupSize, alteIdGroupSize);
  ArrayResize (val,            alteIdGroupSize, alteIdGroupSize);
  ArrayResize (tempIdeolGroup, alteIdGroupSize, alteIdGroupSize);
  ArrayResize (cB,             coordinatesNumber);

  ArrayResize (leadIdeolGroup, leadIdGroupSize);
  for (int i = 0; i < leadIdGroupSize; i++) leadIdeolGroup [i].Init (coordinatesNumber);

  ArrayResize (alteIdeolGroup, alteIdGroupSize);
  for (int i = 0; i < alteIdGroupSize; i++) alteIdeolGroup [i].Init (coordinatesNumber);

  ArrayResize (idBr, populationSize);
  for (int i = 0; i < populationSize; i++) idBr [i].Init (coordinatesNumber);
}
//——————————————————————————————————————————————————————————————————————————————

Метод создания идейных ответвлений Moving выполняет основную логику стратегии поиска MEC. Часть кода выполняется только на первой итерации алгоритма а остальная часть кода выполняется на каждой итерации.

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

//============================================================================
if (!revision)
{
  fB = -DBL_MAX;
  int cnt = 0;

  for (int c = 0; c < coordinatesNumber; c++) vect [c] = (rangeMax [c] - rangeMin [c]) * thoughtPower;

  //--------------------------------------------------------------------------
  for (int i = 0; i < leadIdGroupSize; i++)
  {
    for (int c = 0; c < coordinatesNumber; c++)    
    {
      coord = RNDfromCI (rangeMin [c], rangeMax [c]);
      leadIdeolGroup [i].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
    }
    leadIdeolGroup [i].f = -DBL_MAX;
  }

  //--------------------------------------------------------------------------
  for (int i = 0; i < alteIdGroupSize; i++)
  {
    for (int c = 0; c < coordinatesNumber; c++)
    {
      coord = RNDfromCI (rangeMin [c], rangeMax [c]);
      alteIdeolGroup [i].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
    }
    alteIdeolGroup [i].f = -DBL_MAX;
  }

  revision = true;
}

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

Основная операция по созданию ответвления - задание перемещения к тезисам идей по закону полётов Леви с нормированием на коэффициент силы мысли, мы это будем делать для всех идей альтернативной группы и для всех кроме последней для доминирующей группы по формуле:

coord = leadIdeolGroup [i].c [c] + r1 * vect [c] * pow (r2, -2.0);

для последней идеи доминирующей группы мы будем выбирать случайным образом идею из этой группы и брать тезис соответствующего индекса:

r1 = RNDfromCI (0.0, leadIdGroupSize - 1);
idBr [cnt].c [c] = leadIdeolGroup [(int)r1].c [c];

а вот и весь код создания идейных ответвлений для обоих групп:

//----------------------------------------------------------------------------
for (int i = 0; i < leadIdGroupSize; i++)
{
  for (int b = 0; b < ideasBr; b++)
  {
    if (b < ideasBr -1)
    {
      for (int c = 0; c < coordinatesNumber; c++)
      {
        r1 = RNDfromCI (0.0, 1.0);
        r1 = r1 > 0.5 ? 1.0 : -1.0;
        r2 = RNDfromCI (1.0, 20.0);

        coord = leadIdeolGroup [i].c [c] + r1 * vect [c] * pow (r2, -2.0);
        idBr [cnt].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
    else
    {
      for (int c = 0; c < coordinatesNumber; c++)
      {
        r1 = RNDfromCI (0.0, leadIdGroupSize - 1);
        idBr [cnt].c [c] = leadIdeolGroup [(int)r1].c [c];
      }
    }

    cnt++;
  }
}

//----------------------------------------------------------------------------
for (int i = 0; i < alteIdGroupSize; i++)
{
  for (int b = 0; b < ideasBr; b++)
  {
    for (int c = 0; c < coordinatesNumber; c++)
    {
      r1 = RNDfromCI (0.0, 1.0);
      r1 = r1 > 0.5 ? 1.0 : -1.0;
      r2 = RNDfromCI (1.0, 20.0);

      coord = alteIdeolGroup [i].c [c] + r1 * vect [c] * pow (r2, -2.0);
      idBr [cnt].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
    }

    cnt++;
  }
}

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

1. Инициализируются переменные cnt и pos.

2. Замена лучших идей: В цикле по каждому лидеру в группе лидеров (leadIdeolGroup) происходит поиск лучшего идейного ответвления из глобального (idBr). Для каждого ответвления проверяется, если ее значение фитнес функции (f) больше, чем значение текущего лидера, то позиция (pos) устанавливается равной текущему индексу (cnt). Если найдена лучшая идея, то функциональное значение и координаты лидера обновляются значениями этой идеи. Если функциональное значение новой идеи также больше, чем текущее лучшее функциональное значение (fB), то fB и координаты лучшей идеи (cB) также обновляются.

3. Аналогично для группы альтернативных решений (alteIdeolGroup).

4. Сортировка групп идей: Группы лидеров и альтернативных идей сортируются в порядке убывания значения фитнес функции.

5. Замена худшей идеи: Худшая идея в группе лидеров (leadIdeolGroup) заменяется лучшей идеей из группы альтернативных решений (alteIdeolGroup).

6. Создание новой идеи: для каждой координаты (c) в группе альтернативных решений (alteIdeolGroup) создается новая идея, основанная на элементах доминирующей группы (leadIdeolGroup). Координата выбирается случайно из доминирующей группы лидеров.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_MEC::Revision ()
{
  int cnt = 0;
  int pos = -1;

  //----------------------------------------------------------------------------
  //4.Если есть идейное ответвление лучше - заменить соответствующую идею
  for (int i = 0; i < leadIdGroupSize; i++)
  {
    pos = -1;
    for (int b = 0; b < ideasBr; b++)
    {
      if (idBr [cnt].f > leadIdeolGroup [i].f) pos = cnt;

      cnt++;
    }

    if (pos != -1)
    {
      leadIdeolGroup [i].f = idBr [pos].f;
      ArrayCopy (leadIdeolGroup [i].c, idBr [pos].c, 0, 0, WHOLE_ARRAY);

      if (idBr [pos].f > fB)
      {
        fB = idBr [pos].f;
        ArrayCopy (cB, idBr [pos].c, 0, 0, WHOLE_ARRAY);
      }
    }
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < alteIdGroupSize; i++)
  {
    pos = -1;
    for (int b = 0; b < ideasBr; b++)
    {
      if (idBr [cnt].f > alteIdeolGroup [i].f) pos = cnt;

      cnt++;
    }

    if (pos != -1)
    {
      alteIdeolGroup [i].f = idBr [pos].f;
      ArrayCopy (alteIdeolGroup [i].c, idBr [pos].c, 0, 0, WHOLE_ARRAY);

      if (idBr [pos].f > fB)
      {
        fB = idBr [pos].f;
        ArrayCopy (cB, idBr [pos].c, 0, 0, WHOLE_ARRAY);
      }
    }
  }

  //----------------------------------------------------------------------------
  //5.Отсортировать две группы идей.
  Sorting (leadIdeolGroup);
  Sorting (alteIdeolGroup);

  //----------------------------------------------------------------------------
  //6.Заменить худшую идею первой группы лучшей идеей из второй группы
  leadIdeolGroup [leadIdGroupSize - 1] = alteIdeolGroup [0];

  //----------------------------------------------------------------------------
  //7.Вместо пустующей идеи создать новую идею на основе элементов доминирующей группы 
  double rnd   = 0.0;
  double coord = 0.0;
  for (int c = 0; c < coordinatesNumber; c++)
  {
    rnd = RNDfromCI (0.0, leadIdGroupSize - 2);
    alteIdeolGroup [0].c [c] = leadIdeolGroup [(int)rnd].c [c];
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Результаты тестов

Распечатка работы алгоритма эволюции разума на тестовом стенде:

C_AO_MEC:50;10;0.3
=============================
5 Rastrigin's; Func runs 10000 result: 78.73205273291103
Score: 0.97553
25 Rastrigin's; Func runs 10000 result: 58.554840607439516
Score: 0.72553
500 Rastrigin's; Func runs 10000 result: 42.32395504312925
Score: 0.52442
=============================
5 Forest's; Func runs 10000 result: 1.2024830541165685
Score: 0.68018
25 Forest's; Func runs 10000 result: 0.4588423143844061
Score: 0.25954
500 Forest's; Func runs 10000 result: 0.08756810826330522
Score: 0.04953
=============================
5 Megacity's; Func runs 10000 result: 5.279999999999999
Score: 0.44000
25 Megacity's; Func runs 10000 result: 2.048
Score: 0.17067
500 Megacity's; Func runs 10000 result: 0.4364
Score: 0.03637
=============================
All score: 3.86178

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

rastrigin

MEC на тестовой функции Rastrigin.

forest

MEC на тестовой функции Forest.

megacity

MEC на тестовой функции Megacity.

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

№	AO	Description	Rastrigin			Rastrigin final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result
№	AO	Description	10 p (5 F)	50 p (25 F)	1000 p (500 F)	Rastrigin final	10 p (5 F)	50 p (25 F)	1000 p (500 F)	Forest final	10 p (5 F)	50 p (25 F)	1000 p (500 F)	Megacity final	Final result
1	SSG	saplings sowing and growing	1,00000	1,00000	0,55665	2,55665	0,72740	0,94522	1,00000	2,67262	0,76364	0,85977	1,00000	2,62340	100,000
2	HS	harmony search	0,99676	0,95282	0,48178	2,43136	1,00000	0,98931	0,44806	2,43736	1,00000	1,00000	0,41537	2,41537	92,329
3	ACOm	ant colony optimization M	0,34611	0,17985	0,17044	0,69640	0,86888	1,00000	0,77362	2,64249	1,00000	0,88930	0,05606	1,94536	65,347
4	IWO	invasive weed optimization	0,95828	0,67083	0,29807	1,92719	0,70773	0,46349	0,31773	1,48896	0,80000	0,42067	0,33289	1,55356	61,104
5	MEC	mind evolutionary computation	0,99270	0,51040	0,22800	1,73110	0,60762	0,40658	0,25459	1,26880	0,93335	0,41328	0,26170	1,60833	56,227
6	COAm	cuckoo optimization algorithm M	0,92400	0,46794	0,26004	1,65199	0,58378	0,34034	0,16526	1,08939	0,72727	0,33025	0,17083	1,22835	47,612
7	FAm	firefly algorithm M	0,59825	0,33980	0,17135	1,10941	0,51073	0,42299	0,49790	1,43161	0,34545	0,28044	0,35258	0,97847	41,537
8	ABC	artificial bee colony	0,78170	0,32715	0,20822	1,31707	0,53837	0,21455	0,13344	0,88636	0,56364	0,26569	0,13926	0,96858	36,849
9	GSA	gravitational search algorithm	0,70167	0,45217	0,00000	1,15384	0,31660	0,36416	0,33204	1,01280	0,59395	0,35054	0,00000	0,94448	36,028
10	BA	bat algorithm	0,40526	0,63761	0,84451	1,88738	0,20841	0,17477	0,25989	0,64308	0,29698	0,09963	0,17371	0,57032	35,888
11	BFO	bacterial foraging optimization	0,67203	0,30963	0,11813	1,09979	0,39702	0,26623	0,20652	0,86976	0,52122	0,33211	0,18932	1,04264	34,693
12	EM	electroMagnetism-like algorithm	0,12235	0,46278	1,00000	1,58513	0,00000	0,03498	0,34880	0,38377	0,00000	0,00000	0,10924	0,10924	22,091
13	SFL	shuffled frog-leaping	0,40072	0,23739	0,26548	0,90360	0,20153	0,04147	0,02652	0,26952	0,27273	0,05535	0,06639	0,39446	15,203
14	MA	monkey algorithm	0,33192	0,33451	0,14644	0,81287	0,10012	0,07891	0,08932	0,26836	0,21818	0,04243	0,10720	0,36781	13,603
15	FSS	fish school search	0,46812	0,25337	0,11302	0,83451	0,12840	0,05013	0,06516	0,24369	0,16971	0,04796	0,08283	0,30050	12,655
16	PSO	particle swarm optimisation	0,20449	0,08200	0,07160	0,35809	0,18895	0,10486	0,21738	0,51119	0,23636	0,05903	0,01957	0,31496	10,031
17	RND	random	0,16826	0,09743	0,08019	0,34589	0,13496	0,04810	0,04715	0,23021	0,16971	0,03875	0,04922	0,25767	5,302
18	GWO	grey wolf optimizer	0,00000	0,00000	0,02256	0,02256	0,06570	0,00000	0,00000	0,06570	0,32727	0,07378	0,02557	0,42663	1,000

Выводы

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

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

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

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

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

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

Для более наглядного представления преимуществ и недостатков отдельных алгоритмов в сравнении между собой таблицу выше можно представить с помощью цветовой шкалы на рисунке 3.

rating table

Рисунок 3. Цветовая градация алгоритмов по соответствующим тестам.

Гистограмма результатов тестирования алгоритмов на рисунке 3 (по шкале от 0 до 100, чем больше тем лучше, в архиве скрипт для расчета рейтинговой таблицы по методике в этой статье):

chart

Рисунок 4. Гистограмма итоговых результатов тестирования алгоритмов.

Плюсы и минусы алгоритма эволюции разума (MEC):

Плюсы:
1. Минимальное количество внешних параметров.
2. Высокая эффективность при решении разнообразных задач.
3. Низкая нагрузка на вычислительные ресурсы.
4. Легкость в реализации алгоритма.

Минусы:
1. Застревание на функциях с ровными горизонтальными "площадками".

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

Прикрепленные файлы |

Загрузить ZIP

18_The_world_of_AO_MEC.ZIP (522.92 KB)

Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.

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

Перейти к обсуждению на форуме трейдеров

Разработка системы репликации - Моделирование рынка (Часть 15): Появление СИМУЛЯТОРА (V) - СЛУЧАЙНОЕ БЛУЖДАНИЕ

В этой статье мы завершим разработку симулятора для нашей системы. Основной целью здесь будет настройка алгоритма, рассмотренного в предыдущей статье. Этот алгоритм направлен на создание движения СЛУЧАЙНОГО БЛУЖДАНИЯ. Поэтому, для понимания сегодняшнего материала, необходимо понять содержание предыдущих статей. Если вы не следили за развитием симулятора, советую посмотреть эту последовательность с самого начала. В противном случае вы можете запутаться в том, что будет здесь объяснено.

Разработка пользовательского индикатора Heiken Ashi с помощью MQL5

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

Сделайте торговые графики лучше с интерактивным графическим интерфейсом на основе MQL5 (Часть II): Перемещаемый интерфейс (II)

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

Разработка системы репликации - Моделирование рынка (Часть 14): Появление СИМУЛЯТОРА (IV)

В этой статье мы продолжим этап разработки симулятора. Однако сейчас мы увидим, как эффективно создать движение типа «СЛУЧАЙНОЕ БЛУЖДАНИЕ». Этот тип движения весьма интригующий, поскольку служит основой всего, что происходит на рынке капитала. Кроме того, мы начнем понимать некоторые концепции, основополагающие для тех, кто проводит анализ рынка.