Drift theory и Drift theorem - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:05:40Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:25, 1 сентября 2022

2022-09-01T06:25:28Z

Anton.bannykh в 08:20, 20 июня 2012

2012-06-20T08:20:03Z

194.85.160.130 в 14:41, 19 июня 2012

2012-06-19T14:41:34Z

194.85.160.130 в 09:08, 19 июня 2012

2012-06-19T09:08:20Z

Внесённые изменения

Anton.bannykh в 12:51, 18 июня 2012

2012-06-18T12:51:49Z

178.67.58.50: /* Примеры использования */

2012-06-18T08:49:02Z

‎Примеры использования

Anton.bannykh в 05:43, 18 июня 2012

2012-06-18T05:43:45Z

Anton.bannykh в 20:41, 17 июня 2012

2012-06-17T20:41:41Z

Anton.bannykh в 20:39, 17 июня 2012

2012-06-17T20:39:10Z

← Предыдущая		Версия 16:05, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	Теория дрифта была впервые представленная в работах <ref>He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)</ref><ref>He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)</ref>. Ее центральный результат, ''аддитивная теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов <ref>Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)</ref><ref>Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of GECCO 2006, pp. 651–658. ACM, New York (2006)</ref><ref>Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitnessproportional selection for optimizing linear functions. In: Proceedings of GECCO 2008, pp. 953–960. ACM, New York (2008)</ref><ref>Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82–91. Springer, Heidelberg (2008)</ref><ref>Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835–842. ACM, New York (2009)</ref>. Тем не менее, многие исследователи критикуют ее использование. Основные причины – сложность доказательства самой теоремы и ее использования.		Теория дрифта была впервые представленная в работах <ref>He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)</ref><ref>He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)</ref>. Ее центральный результат, ''аддитивная теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов <ref>Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)</ref><ref>Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of GECCO 2006, pp. 651–658. ACM, New York (2006)</ref><ref>Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitnessproportional selection for optimizing linear functions. In: Proceedings of GECCO 2008, pp. 953–960. ACM, New York (2008)</ref><ref>Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82–91. Springer, Heidelberg (2008)</ref><ref>Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835–842. ACM, New York (2009)</ref>. Тем не менее, многие исследователи критикуют ее использование. Основные причины – сложность доказательства самой теоремы и ее использования.

← Предыдущая		Версия 06:25, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	Теория дрифта была впервые представленная в работах <ref>He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)</ref><ref>He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)</ref>. Ее центральный результат, ''аддитивная теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов <ref>Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)</ref><ref>Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of GECCO 2006, pp. 651–658. ACM, New York (2006)</ref><ref>Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitnessproportional selection for optimizing linear functions. In: Proceedings of GECCO 2008, pp. 953–960. ACM, New York (2008)</ref><ref>Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82–91. Springer, Heidelberg (2008)</ref><ref>Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835–842. ACM, New York (2009)</ref>. Тем не менее, многие исследователи критикуют ее использование. Основные причины – сложность доказательства самой теоремы и ее использования.		Теория дрифта была впервые представленная в работах <ref>He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)</ref><ref>He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)</ref>. Ее центральный результат, ''аддитивная теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов <ref>Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)</ref><ref>Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of GECCO 2006, pp. 651–658. ACM, New York (2006)</ref><ref>Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitnessproportional selection for optimizing linear functions. In: Proceedings of GECCO 2008, pp. 953–960. ACM, New York (2008)</ref><ref>Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82–91. Springer, Heidelberg (2008)</ref><ref>Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835–842. ACM, New York (2009)</ref>. Тем не менее, многие исследователи критикуют ее использование. Основные причины – сложность доказательства самой теоремы и ее использования.

← Предыдущая		Версия 08:20, 20 июня 2012
Строка 1:		Строка 1:
−	Теория дрифта была впервые представленная в работах <ref>He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)</ref><ref>He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)</ref>. Ее центральный результат, ''теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов <ref>Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)</ref><ref>Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of GECCO 2006, pp. 651–658. ACM, New York (2006)</ref><ref>Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitnessproportional selection for optimizing linear functions. In: Proceedings of GECCO 2008, pp. 953–960. ACM, New York (2008)</ref><ref>Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82–91. Springer, Heidelberg (2008)</ref><ref>Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835–842. ACM, New York (2009)</ref>. Тем не менее, многие исследователи критикуют ее использование. Основные причины – сложность доказательства самой теоремы и ее использования.	+	Теория дрифта была впервые представленная в работах <ref>He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)</ref><ref>He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)</ref>. Ее центральный результат, ''аддитивная теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов <ref>Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)</ref><ref>Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of GECCO 2006, pp. 651–658. ACM, New York (2006)</ref><ref>Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitnessproportional selection for optimizing linear functions. In: Proceedings of GECCO 2008, pp. 953–960. ACM, New York (2008)</ref><ref>Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82–91. Springer, Heidelberg (2008)</ref><ref>Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835–842. ACM, New York (2009)</ref>. Тем не менее, многие исследователи критикуют ее использование. Основные причины – сложность доказательства самой теоремы и ее использования.

	В результате в работах <ref>Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010. IEEE, Los Alamitos (to appear, 2010)</ref><ref>Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. ACM, New York (to appear, 2010)</ref> была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе <ref>B. Doerr, L.A. Goldberg, Drift analysis with tail bounds, Proceedings of the 11th international conference on Parallel problem solving from nature: Part I, September 11-15, 2010, Kraków, Poland</ref> была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.		В результате в работах <ref>Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010. IEEE, Los Alamitos (to appear, 2010)</ref><ref>Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. ACM, New York (to appear, 2010)</ref> была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе <ref>B. Doerr, L.A. Goldberg, Drift analysis with tail bounds, Proceedings of the 11th international conference on Parallel problem solving from nature: Part I, September 11-15, 2010, Kraków, Poland</ref> была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.

@@ Строка 1: / Строка 1: @@
-Теория дрифта была впервые представленная в работах [1,2]. Ее центральный результат, ''теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов [3-7]. Тем не менее, многие исследователи критикуют ее использование. Основные причины &ndash; сложность доказательства самой теоремы и ее использования.
+Теория дрифта была впервые представленная в работах <ref>He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)</ref><ref>He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)</ref>. Ее центральный результат, ''теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов <ref>Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)</ref><ref>Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of GECCO 2006, pp. 651–658. ACM, New York (2006)</ref><ref>Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitnessproportional selection for optimizing linear functions. In: Proceedings of GECCO 2008, pp. 953–960. ACM, New York (2008)</ref><ref>Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82–91. Springer, Heidelberg (2008)</ref><ref>Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835–842. ACM, New York (2009)</ref>. Тем не менее, многие исследователи критикуют ее использование. Основные причины &ndash; сложность доказательства самой теоремы и ее использования.
-В результате в работах [8,9] была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе [10] была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.
+В результате в работах <ref>Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010. IEEE, Los Alamitos (to appear, 2010)</ref><ref>Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. ACM, New York (to appear, 2010)</ref> была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе  <ref>B. Doerr, L.A. Goldberg, Drift analysis with tail bounds, Proceedings of the 11th international conference on Parallel problem solving from nature: Part I, September 11-15, 2010, Kraków, Poland</ref> была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.
 = Мультипликативная теорема о дрифте =
@@ Строка 129: / Строка 129: @@
 = Источники =
-# He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)
+<references />

@@ Строка 29: / Строка 29: @@
 |id=statement2
 |about=2
-|statement=<tex>E(T) = \sum\limits_{i = 0}^{\infty} P(T >= i)</tex>
+|statement=<tex>E(T) = \sum\limits_{i = 0}^{\infty} P(T \ge i)</tex>
 |proof=
 Это утверждение достаточно известно в теории вероятностей.
-<tex>E(T) = \sum\limits_{i = 0}^{\infty}iP(T = i) = \sum\limits_{i = 1}^{\infty}\sum\limits_{j = 1}^{i}P(T = i) = \sum\limits_{j = 1}^{\infty}\sum\limits_{i = j}^{\infty}P(T = i) = \sum\limits_{i = 0}^{\infty} P(T >= i)</tex>
+<tex>E(T) = \sum\limits_{i = 0}^{\infty}iP(T = i) = \sum\limits_{i = 1}^{\infty}\sum\limits_{j = 1}^{i}P(T = i) = \sum\limits_{j = 1}^{\infty}\sum\limits_{i = j}^{\infty}P(T = i) = \sum\limits_{i = 0}^{\infty} P(T \ge i)</tex>
 }}
@@ Строка 42: / Строка 42: @@
 Так как из <tex>X_i = 0</tex> следует <tex>T \le i</tex>, то <tex>P(T \ge i) \le P(X_i > 0)</tex>.
-Следовательно, по [[#statement2|утверждению(2)]], <tex>E(T) = \sum\limits_{i = 0}^{\infty} P(T >= i) \le \sum\limits_{t = 0}^{\infty} P(X_t > 0)</tex>.
+Следовательно, по [[#statement2|утверждению(2)]], <tex>E(T) = \sum\limits_{i = 0}^{\infty} P(T \ge i) \le \sum\limits_{t = 0}^{\infty} P(X_t > 0)</tex>.
 Для произвольного натурального <tex>K</tex>:
@@ Строка 48: / Строка 48: @@
 <tex>\parbox{0px}{\begin{align*}
 E(T) &\le \sum\limits_{t = 0}^{\infty} P(X_t > 0) \le K + \sum\limits_{t=K}^{\infty} P(X_t > 0) =\\
-&= K + \sum\limits_{t=K}^{\infty} P(X_t >= 1) \le K + \sum\limits_{t=K}^{\infty} E(X_t)
+&= K + \sum\limits_{t=K}^{\infty} P(X_t \ge 1) \le K + \sum\limits_{t=K}^{\infty} E(X_t)
 \end{align*}}</tex>.
-Здесь мы использовали то, что <tex>X_t > 0 \Leftrightarrow X_t >= 1</tex>, а также неравество Маркова: <tex>P(|X| \ge a) \le \frac{E(|X|)}{a}</tex>.
+Здесь мы использовали то, что <tex>X_t > 0 \Leftrightarrow X_t \ge 1</tex>, а также неравество Маркова: <tex>P(|X| \ge a) \le \frac{E(|X|)}{a}</tex>.
 }}
@@ Строка 98: / Строка 98: @@
 Теорема о дрифте достаточно естественно применяется для эволюционных алгоритмов, оперирующих одной особью. Продемонстрируем это.
-Пусть в эволюционном алгоритме проcтранство поиска <tex>S_n</tex>, а целевая функция &ndash; <tex>f: S_n \rightarrow \mathbb{N}</tex>.
+Пусть в эволюционном алгоритме протранство поиска <tex>S_n</tex>, а целевая функция &ndash; <tex>f: S_n \rightarrow \mathbb{N}</tex>.
 Пусть оптимальное значение целевой функции &ndash; <tex>f_{opt}</tex>
 Положим, что <tex>X_t = |f_{opt} - f(x_t)|</tex>, где <tex>x_t \in S_n</tex> &ndash; особь, полученная на шаге номер <tex>t</tex>. Почти все условия [[#theorem1| теоремы о дрифте]] выполнены, последнее условие (оценка на <tex>E(X_{i+1}|X_i)</tex>)доказывается для каждой задачи отдельно.

@@ Строка 102: / Строка 102: @@
 Положим, что <tex>X_t = |f_{opt} - f(x_t)|</tex>, где <tex>x_t \in S_n</tex> &ndash; особь, полученная на шаге номер <tex>t</tex>. Почти все условия [[#theorem1| теоремы о дрифте]] выполнены, последнее условие (оценка на <tex>E(X_{i+1}|X_i)</tex>)доказывается для каждой задачи отдельно.
-Продемострируем использование теоремы о дрифте для оценки времени нахождения оптимального решения задачи [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#OneMax|OneMax]] при использовании [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#RMHC_.28Random_Mutation_Hill_Climbing.29|RMHC]] и [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#ES_.28Evolution_Strategies.29|(1+1)-ES]] стратегий. Пространство поиска <tex>S_n</tex> &ndash; множество битовых строк длины <tex>n</tex>, целевая функция <tex>f(x_1, x_2, \dots , x_n) = OneMax(x_1, x_2, \dots , x_n) = x_1 + x_2, + \dots + x_n </tex>.
+Продемострируем использование теоремы о дрифте для оценки времени нахождения оптимального решения задачи [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#OneMax|OneMax]] при использовании [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#RMHC_.28Random_Mutation_Hill_Climbing.29|RMHC]] и [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#ES_.28Evolution_Strategies.29|(1+1)-ES]] стратегий. Пространство поиска <tex>S_n</tex> &ndash; множество битовых строк длины <tex>n</tex>, целевая функция <tex>f(x_1, x_2, \dots , x_n) = OneMax(x_1, x_2, \dots , x_n) = x_1 + x_2, + \dots + x_n </tex>. В качестве оценки сверху на <tex>X_0</tex> берем <tex>n</tex>.
 Ниже приведены примеры оценки ожидаемого значения следующего элемента в зависимости от предыдущего (<tex>E(X_{i+1}|X_i)</tex>).
@@ Строка 118: / Строка 118: @@
 Получаем, что <tex>\delta = \frac{1}{en}</tex>, следовательно <tex>E(T) \le en (\ln n + 1)</tex>.
-== Источники ==
+= Источники =
 # He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)
 # He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)

@@ Строка 1: / Строка 1: @@
 Теория дрифта была впервые представленная в работах [1,2]. Ее центральный результат, ''теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов [3-7]. Тем не менее, многие исследователи критикуют ее использование. Основные причины &ndash; сложность доказательства самой теоремы и ее использования.
@@ Строка 83: / Строка 82: @@
 <tex>\parbox{0px}{\begin{align*}
 P(T > T_c) &\le_{(1)} P(X_{T_c} > 0) \le_{(1)}\\
-&\le_{(1)} E(X_{T_c}) \le_{(2)} e^{-\delta T_c}X_0 \le_{(3)}\\
+&\le_{(1)} E(X_{T_c}) \le_{(2)}\\
 &\le_{(3)} e^{-\delta \left( \delta^{-1}(\ln X_0 + c)\right) } X_0 =_{(4)}\\
 &=_{(4)} e^{-c}

← Предыдущая		Версия 20:39, 17 июня 2012
Строка 1:		Строка 1:

−	Теория дрифта была впервые представленная в работах [1,2]. Ее центральный результат, ''теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов [3-7]. Тем не менее, многие исследователи критикуют ее использование. Основные причины ~~---~~ сложность доказательства самой теоремы и ее использования.	+	Теория дрифта была впервые представленная в работах [1,2]. Ее центральный результат, ''теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов [3-7]. Тем не менее, многие исследователи критикуют ее использование. Основные причины – сложность доказательства самой теоремы и ее использования.

	В результате в работах [8,9] была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе [10] была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.		В результате в работах [8,9] была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе [10] была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.