70
правок
Изменения
Новая страница: «{{В разработке}} == Анализ RMHC и IGA == === Оценка для RMHC (Simple Hill-Climbing Algorithm) === Согласно [[Теоретич...»
{{В разработке}}
== Анализ RMHC и IGA ==
=== Оценка для RMHC (Simple Hill-Climbing Algorithm) ===
Согласно [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST|оценке времени работы алгоритмов RMHC]] ожидаемое время поиска всех требуемых блоков:
<tex>E_N \approx 2^K N (\log N + \gamma)</tex>
=== Оценка для IGA (Idealized Genetic Algorithm) ===
Вероятность нахождения требуемого блока <tex>s</tex> в случайной строке <tex>p=1/2^k</tex>, вероятность нахождения <tex>s</tex> за время <tex>t</tex> равна <tex>1-(1-p)^t</tex>
Вероятность нахождения всех требуемых <tex>N</tex> блоков за время <tex>t</tex> есть <tex>P_{N}(t)=(1-(1-p)^t)^N</tex>
Вероятность нахождения требуемых блоков точно в момент времени <tex>t</tex> есть <tex>P_{N}(t)=(1-(1-p)^t)^N - (1-(1-p)^{t-1})^N</tex>
Ожидаемое время поиска есть <tex>E_N=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(1-p)^{t-1})^N ]</tex>
Это значение можно аппроксимировать <tex>E_N \approx (1/p) \sum_{n=1}^N \frac{1}{N} \approx 2^K(\log N + \gamma)</tex>
==== IGA и Real GA ====
Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме:
# Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частоту мутаций должно быть достаточно, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции
# Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения
# Превосходство в скорости: Оценка скорости для RMHC: <tex>E_N \approx 2^K N (\log N + \gamma)</tex>, для IGA: <tex>E_N \approx (1/p) 2^K(\log N + \gamma)</tex>. Длина строки должна быть достаточно большой, чтобы фактор <tex>N</tex> давал превосходство в скорости
=== Результаты сравнения ===
В работе [http://www.santafe.edu/media/workingpapers/93-06-037.pdf. When Will a Genetic Algorithm Outperform Hill Climbing?] были получены следующие экспериментальные результаты:
==Источники==
* [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST]]
* [http://www.santafe.edu/media/workingpapers/93-06-037.pdf. When Will a Genetic Algorithm Outperform Hill Climbing?]
== Анализ RMHC и IGA ==
=== Оценка для RMHC (Simple Hill-Climbing Algorithm) ===
Согласно [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST|оценке времени работы алгоритмов RMHC]] ожидаемое время поиска всех требуемых блоков:
<tex>E_N \approx 2^K N (\log N + \gamma)</tex>
=== Оценка для IGA (Idealized Genetic Algorithm) ===
Вероятность нахождения требуемого блока <tex>s</tex> в случайной строке <tex>p=1/2^k</tex>, вероятность нахождения <tex>s</tex> за время <tex>t</tex> равна <tex>1-(1-p)^t</tex>
Вероятность нахождения всех требуемых <tex>N</tex> блоков за время <tex>t</tex> есть <tex>P_{N}(t)=(1-(1-p)^t)^N</tex>
Вероятность нахождения требуемых блоков точно в момент времени <tex>t</tex> есть <tex>P_{N}(t)=(1-(1-p)^t)^N - (1-(1-p)^{t-1})^N</tex>
Ожидаемое время поиска есть <tex>E_N=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(1-p)^{t-1})^N ]</tex>
Это значение можно аппроксимировать <tex>E_N \approx (1/p) \sum_{n=1}^N \frac{1}{N} \approx 2^K(\log N + \gamma)</tex>
==== IGA и Real GA ====
Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме:
# Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частоту мутаций должно быть достаточно, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции
# Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения
# Превосходство в скорости: Оценка скорости для RMHC: <tex>E_N \approx 2^K N (\log N + \gamma)</tex>, для IGA: <tex>E_N \approx (1/p) 2^K(\log N + \gamma)</tex>. Длина строки должна быть достаточно большой, чтобы фактор <tex>N</tex> давал превосходство в скорости
=== Результаты сравнения ===
В работе [http://www.santafe.edu/media/workingpapers/93-06-037.pdf. When Will a Genetic Algorithm Outperform Hill Climbing?] были получены следующие экспериментальные результаты:
==Источники==
* [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST]]
* [http://www.santafe.edu/media/workingpapers/93-06-037.pdf. When Will a Genetic Algorithm Outperform Hill Climbing?]
