3
правки
Изменения
Нет описания правки
== Рассмотренные методы решения ==
==='''HC'''(Hill Climbing)===
В русскоязычном варианте этот метод называется методом спуска. Общая схема данного алгоритма выглядит следующим образом:
x <tex>\leftarrow</tex> random
==='''ES''' (Evolution Strategies)===
Это широкий класс алгоритмов поиска, основанных на идеях приспособления и эволюции<ref>Droste S., Jansen T., Wegener I.: [http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CEcQFjAA&url=http%3A%2F%2Fwww.mpi-inf.mpg.de%2F~tfried%2Fteaching%2FSS08%2Fseminar%2Fpaper%2F7-DorsteJansenWegener.pdf&ei=92DfT6vnDMX6mAWz1fmtDA&usg=AFQjCNErEUu9L8x4PWFPofp3Y80hjE2_Ow&sig2=G9rsT_PDarYfL7LL4tLPvg On the analysis of the (1 + 1) evolutionary algorithm.] Theoretical Computer Science 276, 51–81 (2002) </ref>. Существуют различные вариации ES:
1) (1+1)-ES {{---}} на каждой итерации существует одно исходное решение <tex> x</tex> и одно промежуточное решение <tex>x'</tex>. После внесения случайного изменения в каждый из компонентов <tex> x</tex>, <tex>x'</tex> может оказаться любым элементом <tex>S</tex>, но, чем он ближе к <tex>x</tex>, тем выше вероятность его выбора.
== Оценка времени работы для OneMax ==
Содержание данного раздела основано на работе <ref>Witt C.: [http://massivedatasets.files.wordpress.com/2010/03/slides-02283-20102.pdf Randomized Search Heuristics.] Algorithms for Massive Data Sets, DTU Informatik,Danmarks Tekniske Universitet (2010)</ref>.
Чтобы оценить время работы вышеописанных алгоритмов на задаче OneMax необходимо доказать несколько утверждений.
==Оценка времени работы с использованием Drift Analysis==
[[Теорема о дрифте | Теорема о дрифте]] с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Рассмотрим несколько примеровПримеры можно найти в работе<ref>Doerr B.: [http://dl.acm.org/citation.cfm?id=2002138 Tutorial: Drift Analysis.] GECCO '11 Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, 1311-1320 (2011)</ref>.
===RMHC для OneMax===
<tex>E(X_t | X_{t-1} = D) \leq D - \sum_{i} (1/e m^2) (w(e_i) - w(e'_i))= (1 - 1/e m^2) D </tex>
Используем [[Теорема о дрифте|теорему о дрифте]], учитывая, что
<tex>X_0 \leq \sum_{e \in E} w(e) \leq m w_{max}</tex>, и получаем требуемый результат.
}}
==Источники==
