Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

Строительные блоки 
Из полученного в теореме шаблонов выражения видно, что шаблоны с 
малым порядком и малой определяющей длиной менее подвержены 
разрушению в результате кроссовера или мутации, поэтому рост (или 
уменьшение) их доли в популяции происходит динамичнее. Шаблоны с 
высокой приспособленностью, малым порядком и малой определяющей 
длиной называются 
строительными блоками
(
building blocks
).
Холланд (1992) показал, что в то время, как ГА обрабатывает 
N
строк на 
каждом поколении, в то же время неявно обрабатываются порядка 
N
3
гиперплоскостей. Это доказывается с рассчетом на реально 
применимые размеры популяции и длины строки. Практически это 
означает, что большая популяция имеет возможность локализовать 
решение быстрее, чем маленькая. Для оценки рекомендуемого размера 
популяции в зависимости от длины строки можно вспомнить, что всего 
гиперплоскостей 3
L
.
Еще один аргумент в пользу больших популяций: в случае, если разброс 
приспособленностей представителей блока большой, то вероятность 
выбрать некоторое количество представителей блока с меньшей 
приспособленностью вместо представителей более хорошего 
достаточно велика, поскольку отдельные особи «слабого» блока могут 
оказаться лучше, чем многие особи «сильного». Увеличение размера 
популяции увеличит количество осуществляемых при генерации 
промежуточной популяции выборок, и вероятность сделать в итоге 
выбор неверного блока окажется достаточно малой.

---

А.Е. Кононюк Дискретно-непрерывная математика 
110 
В гипотезе о строительных блоках считается, что в процессе 
приближения популяции к глобальному оптимуму порядок и 
приспособленность строительных блоков увеличиваются. Это легко 
видно на простом примере:
Все локальные максимумы приведенной функции приходятся на блок 
**0*, а минимумы — на **1*, поэтому очевидно, что после отбора 
основная часть особей будут представителями первого блока. Левая 
половина графика в среднем ниже правой, поэтому доля блока 1*** 
будет преобладать над долей 0***. Получается, что основная масса 
особей окажутся представителями блока 1*** и в то же время **0*, 
значит, большое их количество будут представителями блока 1*0*. 
Теперь, выбирая между блоками 100* и 110*, получаем, что второй 
блок будет преобладать над первым. Таким образом, можно сказать, что 
хорошие строительные блоки малого порядка сложились в 
приспособленные блоки большего порядка, и в результате мы оказались 
в области глобального максимума, чем приблизились к решению 
задачи.