Аннотация:
Исследуется последовательность цепей Маркова $Z_n(s)$ с $n+1$ состоянием у процессов с индексом $n$. Вероятности перехода определяются с помощью случайных процессов, являющихся двухшаговыми эволюциями популяции частиц. Частицам присвоены типы в терминах бинарных n-мерных векторов с нормой Хэмминга. Значение цепи Маркова $Z_n(s)$ задается типом некоторой частицы «x» и равно размерности бинарного вектора n минус норма Хэмминга типа этой частицы. Эти случайные процессы соответствуют циклу генетического алгоритма (1+(λ, λ))$\sim$GA с onemax весовой функцией, где на первом этапе частица «x» многократно мутирует и из мутантов выбирается частица «x’» с максимальной нормой, а на втором этапе «x» и «x’» многократно скрещиваются, и из этих потомков выбирается «y» с максимальной нормой.
Если |«y»|≥|«x»|, то значение $Z_n(s+1)$ задается типом частицы |«y»|, а иначе значение $Z_n(s+1)$ задается типом старой частицы «x» и $Z_n(s+1)=Z_n(s)$.
В работе на основе классических предельных теорем описаны асимптотические свойства случайных величин $Z_n(s)-Z_n(s+1)$ при $n$→∞ и оценено время вырождения цепи. В качестве приложения оценено среднее количество вычислений весовой функции в генетическом алгоритме (1+(λ, λ))$\sim$GA с onemax весовой функцией, равной норме типа частицы. Для генетических алгоритмов наши оценки уточняют наилучшие из полученных ранее. В них в явном виде выписаны постоянные при главных членах асимптотических представлений.
|
