Обсуждение статьи "Популяционные алгоритмы оптимизации: Тасующий алгоритм прыгающих лягушек (Shuffled Frog-Leaping, SFL)"

 

Опубликована статья Популяционные алгоритмы оптимизации: Тасующий алгоритм прыгающих лягушек (Shuffled Frog-Leaping, SFL):

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

Тасующий алгоритм прыгающих лягушек (Shuffled Frog Leaping Algorithm, SFL) был предложен Юсуфом (М. Eusuff) и другими авторами в 2003 году. Этот алгоритм объединяет принципы меметического алгоритма и алгоритма роя частиц, и его разработка была вдохновлена поведением группы лягушек в процессе поиска пищи.

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

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

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

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

Автор: Andrey Dik

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

Спасибо автору за проделанную огромную работу и безвозмездную возможность использовать ее!


enum EFunc
{
  Skin,
  Forest,
  Megacity,
  Rastrigin,
  Universe
};
C_Function *SelectFunction (EFunc f)
{
  C_Function *func;
  switch (f)
  {
    case  Skin:
      func = new C_Skin (); return (GetPointer (func));
    case  Forest:
      func = new C_Forest (); return (GetPointer (func));
    case  Megacity:
      func = new C_Megacity (); return (GetPointer (func));
    case  Rastrigin:
      func = new C_Rastrigin (); return (GetPointer (func));
    case  Universe:
      func = new C_Universe (); return (GetPointer (func));
    
    default:
      func = new C_Skin (); return (GetPointer (func));
  }
}

Немного смотрю код. И вот эту красоту заменил у себя на такой ужас.

#property script_show_inputs

#include <Math\Functions.mqh> // https://www.mql5.com/ru/articles/13366

template <typename T>
C_Function* New( const string &ClassName ) { return((typename(T) == ClassName) ? new T : NULL); }

C_Function* New2( string ClassName )
{  
  typedef C_Function* (*TNew)( const string& );
  static const TNew FuncNew[] = {New<C_Skin>, New<C_Forest>, New<C_Megacity>, New<C_Rastrigin>, New<C_Universe>};

  C_Function* Res = NULL;
  
  ClassName = "class " + ClassName;
  
  for (uint i = ArraySize(FuncNew); (Res == NULL) && (bool)i--;)
    Res = FuncNew[i](ClassName);  
    
  return(Res);
}

C_Function* SelectFunction2( const EFunc f )
{
  return(New2("C_" + EnumToString(f)));
}

input EFunc inFunc = Skin;

void OnStart()
{
  C_Function* Func = SelectFunction2(inFunc);
  
  if (Func != NULL)
  {
    Print(Func.GetNamFun());
    
    delete Func;
  }
}
 
fxsaber #:

Немного смотрю код.

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

  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search

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

 
fxsaber #:

Спасибо автору за проделанную огромную работу и безвозмездную возможность использовать ее!

Спасибо, рад, что моя работа полезна))

fxsaber #:

Немного смотрю код. И вот эту красоту заменил у себя на такой ужас.

интересно

fxsaber #:

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

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

1. да, я пошёл по простому пути и сделал граничные условия алгоритмов в виде открытых членов - массивов.

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

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

4. однако, действительно, все алгоритмы могут быть унифицированы и приведены к единообразию благодаря проведённой работе в п.2. 


граничные условия rangeMax и остальные, по хорошему, должны быть аргументами в методе Init.

 
fxsaber #:


Немного смотрю код. И вот эту красоту заменил у себя на такой ужас.

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

Файл Functions.mqh:

class C_Function; // forward declaration for use in FunctionInstance base class

class FunctionInstance // common parent for all fabrics to be used in unified manner, for example listed in an array
{
  protected:
    C_Function *instance;
  public:
    FunctionInstance(): instance(NULL) { }
    ~FunctionInstance()                    // destructor provides garbage collection
    {
      if(CheckPointer(instance) == POINTER_DYNAMIC) delete instance;
    }
    virtual C_Function *create() = 0;
};

template<typename T>
class FunctionFabric: public FunctionInstance // specific fabric
{
  public:
    virtual T *create() override
    {
      if(instance == NULL) instance = new T; // here dynamic "singleton" pattern is implemeted for simplicity only (could be a collection of objects or no references at all)
      return instance;
    }
};

//——————————————————————————————————————————————————————————————————————————————
class C_Function
{
  public:
  template<typename T>
  static FunctionFabric<T> *fabric()
  {
    static FunctionFabric<T> singleton; // here static "singleton" is implemeted as most appropriate for fabric (no need to have more than 1 fabric per class)
    return &singleton;
  }
  ...
};
...

Использовать в скрипте так:

C_Function* NewX(const EFunc elem)
{
  // order of initialization corresponds to EFunc enumeration
  static FunctionInstance *pointers[] = {C_Function::fabric<C_Skin>(), C_Function::fabric<C_Forest>(), C_Function::fabric<C_Megacity>(), C_Function::fabric<C_Rastrigin>(), C_Function::fabric<C_Universe>()};
  return pointers[elem].create();
}

void OnStart()
{
  C_Function* Func = NewX(inFunc);
  
  if (Func != NULL)
  {
    Print(Func.GetNamFun());
    
    // delete Func; // not needed anymore, fabric will do itself
  }
}
 
Stanislav Korotky #:

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

Файл Functions.mqh:

Использовать в скрипте так:

Два аргумента против такого варианта.

  1. Отказ от задания функции строкой - отказ от задания настроек робота через ini-файл.
  2. Синглтон - отказ от параллельной работы нескольких одинаковых роботов с разными настройками.
 
fxsaber #:

Два аргумента против такого варианта.

  1. Отказ от задания функции строкой - отказ от задания настроек робота через ini-файл.
  2. Синглтон - отказ от параллельной работы нескольких одинаковых роботов с разными настройками.

Набросал его просто потому, что если уж ваять какие-то навороты, то без потенциальных проблем - "зацепило" использование цикла с перебором строк (!) - может быть супер неэффективно в программах побольше.

В ini-файле не только строковые параметры, но и других типов (хотя представлены текстом).

Синглтон у фабрики - это нормально. Синглтон у объекта функции - в данном случае просто для работоспособности примера - можно реализовать множественность.

 
Stanislav Korotky #:

Набросал его просто потому, что если уж ваять какие-то навороты, то без потенциальных проблем - "зацепило" использование цикла с перебором строк (!) - может быть супер неэффективно в программах побольше.

В ini-файле не только строковые параметры, но и других типов (хотя представлены текстом).

Синглтон у фабрики - это нормально. Синглтон у объекта функции - в данном случае просто для работоспособности примера - можно реализовать множественность.

Использую string-решение на этапе инициализации. Думаю, меньше миллисекунды занимает. Честно говоря, не прочувствовал потенциальных проблем. 

 
fxsaber #:

Спасибо автору за проделанную огромную работу и безвозмездную возможность использовать ее!



Немного смотрю код. И вот эту красоту заменил у себя на такой ужас.

А в чем выигрыш? Это же действительно ужас. Извините, если что))

 
Stanislav Korotky #:

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

Файл Functions.mqh:

Использовать в скрипте так:

Извините, но я конечно же ошибаюсь, вот в той строке кода:

static FunctionInstance *pointers[] = {C_Function::fabric<C_Skin>(), C_Function::fabric<C_Forest>(), C_Function::fabric<C_Megacity>(), C_Function::fabric<C_Rastrigin>(), C_Function::fabric<C_Universe>()};
 

не будут создаваться по объекту каждого типа?

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

 
Dmitry Fedoseev #:

А в чем выигрыш? Это же действительно ужас. Извините, если что))

Сложный вопрос. Не знаю.