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

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

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