|
3.8.
Строительные блоки (Building blocks)
Строительный блок (СБ) (
building block (BB)
) - это одно из ключевых
понятий в теории генетических алгоритмов, наряду со схемой и
теоремой схем. К строительным блокам (как правило) принято
относить схемы с малой определяющей длиной, малым порядком и
высокой приспособленностью. Приспособленность СБ чаще всего
А.Е. Кононюк Дискретно-непрерывная математика
143
определяется как средняя приспособленность особей, хромосомы
которых содержат данный строительный блок.
В гипотезе о строительных блоках (
building blocks hypothesis
)
считается, что в процессе работы генетического алгоритма, по мере
приближения к глобальному оптимуму, порядок и приспособленность
строительного блока увеличиваются. Т.е. в начале эволюции
относительно высокой приспособленностью обладают строительные
блоки малой определяющей длины, затем, в результате отбора и
рекомбинации, появляются более приспособленные и "длинные"
строительные блоки. Таким образом, говорят об обработке
строительных блоков (
building blocks processing
) в результате работы
генетического алгоритма.
Выделяют следующие проблемы в обработке строительных блоков:
1. Идентификация.
2. Смешивание.
Под идентификацией понимается проблема нахождения (локализации)
строительного блока. Иными словами, какой именно участок
хромосомы можно считать строительным блоком. Очевидно, что
минимальный по размерам СБ представляет один разряд, а
максимальный - всю хромосому. Но это в простейшем варианте, а в
случае "не граничных условий" количество "претендентов" на звание
строительного блока очень велико. В частности, для хромосомы длины
n
может существовать
С(n, 2)
различных позиций для строительных
блоков 2-го порядка,
С(n, 3)
различных позиций для строительных
блоков третьего порядка и т.д., где
C(n, m)
- количество сочетаний из
n
по
m
(вычисляется как
n!/(m!(n-m)!)
, где "
!
" - факториал, т.е.
n! = 1*2*...*(n-1)*n
, где "*" - обозначает операцию умножения).
Проблема смешивания заключается в том, что, даже если строительные
блоки найдены, трудно определить, какие из них стоит смешивать
(грубо говоря, помещать в одну хромосому), а какие – нет, т.к. высокая
приспособленность различных строительных блоков не гарантирует
высокой приспособленности хромосом, полученных в результате их
комбинации. В силу обозначенных проблем уделяется довольно много
внимания разработке операторов и подходов, которые позволили бы
обеспечить эффективную (
BB-wise
) обработку строительных блоков.
Также существует мнение, что эффективная идентификация и
А.Е. Кононюк Дискретно-непрерывная математика
144
смешивание являются критическими условиями для обеспечения
успешной работы генетического алгоритма.
Помимо идентификации и смешивания существует проблема
неопределенности приспособленности строительного блока (
building
block fitness noise
). Поскольку один и тот же строительный блок может
входить как в хорошие (с точки зрения решаемой задачи) хромосомы,
так и в не очень, то приспособленность этого строительного блока
практически всегда определяется с некоторым "шумом". Это
осложняет задачу выбора между двумя строительными блоками, т.к.
даже если приспособленность одного из них выше, чем
приспособленность другого, всегда есть вероятность сделать
неправильный выбор. Говоря по-другому, в результате селекции может
быть выбрана особь с менее приспособленным строительным блоком.
Графически это можно представить следующим образом (рис.1)
Рис.1.
Пусть
H1
и
H2
два строительных блока, приспособленности которых
распределены
по
нормальному
закону,
причем
1
H
f
и
2
H
f
соответственно средние приспособленности блоков 1 и 2. Пусть
также приспособленность
H
1
больше, чем приспособленность
Н
2
. Если
имеется небольшое число хромосом, содержащих рассматриваемые
блоки, то их приспособленности определены с достаточно большой
погрешностью, иными словами, дисперсия распределений велика.
Таким образом, площадь взаимного "наложения" распределений также
значительна, и, следовательно, значительна вероятность выбрать в
результате селекции менее приспособленный строительный блок. В
случае, представленном на рис.1, вероятность выбрать хромосому с
приспособленностью больше
f'
и содержащую схему
Н
2
, равна
площади закрашенной части распределения приспособленности 2-й
схемы.
А.Е. Кононюк Дискретно-непрерывная математика
145
Рис.2.
Если увеличить количество хромосом содержащих рассматриваемые
строительные блоки (например, увеличив размер популяции), то тогда
распределения приспособленностей обоих блоков "сжимаются", т.к.
значения приспособленностей определяются более точно (рис.2). Тем
самым уменьшается вероятность выбора менее приспособленного
строительного блока.
Несмотря на то, что изначально строительные блоки определялись как
схемы с определенными свойствами, т.е. применительно к ГА с
бинарным кодированием, аналоги схем, а следовательно и
строительных блоков, можно найти и в других видах эволюционных
вычислений (не только в генетических алгоритмах). Видимо,
концепция строительных блоков давно уже живет "своей жизнью",
отдельно от теоремы схем, т.к. за СБ можно считать любой участок
хромосомы определенного вида вне зависимости от того, возможно ли
описание хромосом, содержащих этот блок, одной схемой или нельзя.
Do'stlaringiz bilan baham: |
