МЕТОД НАПРАВЛЕННОЙ ЭВОЛЮЦИИ

 

ИСХОДНЫЕ ДАНЫЕ И ОПРЕДЕЛЕНИЯ

 

 

·        S – множество допустимых решений образующих пространство поиска

·        R – множество всех рациональных чисел

·        F(x) – функция оптимальности решения. xÎS, F:SÞR

·        M(x) – оператор мутации. Оператор мутации путем случайной модификации базового решения xÎS порождает новое решение. M:SÞS.

·        P – популяция решений

·        DIM(P) – объем популяции P

·        P₀ – стартовая популяция и P₀¹Æ

·        limit – максимальный допустимый размер популяции

·        PAR(x) – решение, в ходе мутации которого было порождено решение xÎS. PAR:SÞS.

·        , где xÎS

·        dF(x, d) = F(x) – PAR_F(x) + d, где xÎS, dF:SÞR, dÎR, d ³ 0

·        BEST(P) – функция возвращающая решение xÎP, где PÍS и P¹Æ, при котором значение F(x) больше либо равно чем при любом другом yÎP.

·        ROUND(x) – функция округления до ближайшего целого, где xÎR.

 

АЛГОРИТМ

 

1.      k := 0; d₁ := 0; d₂ := 0;

2.      b := BEST(P₀)

3.      L := SUM{dF(x, |d₁|) | xÎP_k}

4.      P_k+1 := Æ

5.      для всех xÎP_k выполнять

5.1.   i := ROUND((dF(x, |d₁|) / L) * limit)

5.2.   если i = 0 то GOTO 6

5.3.   mutant := M(x)

5.4.   P_k+1 := P_k+1 È {mutant}; если d₂ > F(mutant) – F(x) < 0 то d₂ := F(mutant) – F(x);

5.5.   i := i –1

5.6.   GOTO 5.2

6.      если DIM(P_k+1) > 0 то

6.1.   d₁ := d₂; d₂ := 0;

6.2.   new_b := BEST(P_k+1)

6.3.   если F(new_b) > F(b) то b := new_b

7.      если DIM(P_k+1) = 0 то

7.1.   result := b

7.2.   СТОП

8.      k := k +1

9.      GOTO 3

 

КОММЕНТАРИИ

 

1.      Результат работы алгоритма хранится в переменной result.

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

3.      Пункт 5 позволяет подвергать мутации каждый xÎP_k в параллельном режиме.

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