Редактирование: Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 98: Строка 98:
 
|id=proposal5
 
|id=proposal5
 
|about=Лемма об ожидании
 
|about=Лемма об ожидании
|statement=Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание времени наступления этого события <tex>E(t_A) = \frac{1}{p}</tex>.
+
|statement=Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание наступления этого события <tex>E(t_A) = \frac{1}{p}</tex>.
 
|proof=По определению математического ожидания:  
 
|proof=По определению математического ожидания:  
  
Строка 107: Строка 107:
 
Воспользовавшись этим фактом, получаем:
 
Воспользовавшись этим фактом, получаем:
  
<tex> (\frac{1}{1 - x})' = \frac{1}{(1 - x) ^ 2} = \sum_{i=0}^\infty  i x^{i - 1} </tex>.
+
<tex> \frac{1}{1 - x}' = \frac{1}{(1 - x) ^ 2} = \sum_{i=0}^\infty  i x^{i - 1} </tex>.
  
 
Отсюда видно, что: <tex> \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty  i (1 - p)^{i-1} = \frac{1}{p} </tex>.
 
Отсюда видно, что: <tex> \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty  i (1 - p)^{i-1} = \frac{1}{p} </tex>.
Строка 113: Строка 113:
 
=== Алгоритм RMHC ===
 
=== Алгоритм RMHC ===
  
Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равновероятно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> {{---}} количество единиц в векторе (то есть значение <tex> f </tex>) в начале фазы. При <tex> k + 1 = k' > k </tex> фаза заканчивается.
+
Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равномерно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> {{---}} количество единиц в векторе (то есть значение <tex> f </tex>) в начале фазы. При <tex> k + 1 = k' > k </tex> фаза заканчивается.
  
 
Оценим время работы алгоритма для данной задачи.
 
Оценим время работы алгоритма для данной задачи.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: