Теорема за схемата на Холанд

Схематичната теорема на Холанд, наричана още фундаментална теорема на генетичните алгоритми, е неравенство, което е резултат от грубото структуриране на уравнение за еволюционна динамика. Теоремата за схемите гласи, че кратките схеми от нисък порядък с пригодност над средната се увеличават експоненциално по честота в последователните поколения. Теоремата е предложена от Джон Холанд през 70-те години на миналия век. Първоначално тя е широко възприемана като основа за обяснения на силата на генетичните алгоритми. Това тълкуване на нейните последици обаче е критикувано в няколко публикации, разгледани в , където е показано, че Теоремата за схемата е частен случай на уравнението на Прайс с индикаторната функция на схемата като макроскопична мярка.

Схемата е шаблон, който идентифицира подмножество от низове със сходства в определени позиции на низовете. Схемите са специален случай на цилиндрични множества и следователно образуват топологично пространство.

Описание

Разглеждаме двоични низове с дължина 6. Схемата 1*10*1 описва множеството от всички низове с дължина 6 с 1 на позиции 1, 3 и 6 и 0 на позиция 4. Символът * е заместващ символ, което означава, че позиции 2 и 5 могат да имат стойност 1 или 0. Редът на една схема o ( H ) {\displaystyle o(H)} $o(H)$ се определя като броя на фиксираните позиции в шаблона, докато определящата дължина δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ е разстоянието между първата и последната специфична позиция. Редът на 1*10*1 е 4, а определящата му дължина е 5. Пригодността на дадена схема е средната пригодност на всички низове, съответстващи на схемата. Фитнесът на даден низ е мярка за стойността на кодираното решение на проблема, изчислена чрез специфична за проблема функция за оценка. Като се използват утвърдените методи и генетични оператори на генетичните алгоритми, теоремата за схемата гласи, че кратките схеми от нисък ред с фитнес над средния се увеличават експоненциално в последователните поколения. Изразено като уравнение:

E ( m ( H , t + 1 ) ) ≥ m ( H , t ) f ( H ) a t [ 1 - p ] . {\displaystyle \operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p]. } $\operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p].$

Тук m ( H , t ) {\displaystyle m(H,t)} $m(H,t)$ е броят на низовете, принадлежащи към схема H {\displaystyle H} $H$ в поколение t {\displaystyle t} $t$ , f ( H ) {\displaystyle f(H)} $f(H)$ е наблюдаваната средна пригодност на схема H {\displaystyle H} $H$ , а a t {\displaystyle a_{t}} $a_{t}$ е наблюдаваната средна пригодност в поколение t {\displaystyle t} $t$ . Вероятността за разрушаване p {\displaystyle p} $p$ е вероятността кръстосването или мутацията да разрушат схемата H {\displaystyle H} $H$ . Тя може да бъде изразена по следния начин:

p = δ ( H ) l - 1 p c + o ( H ) p m {\displaystyle p={\delta (H) \over l-1}p_{c}+o(H)p_{m}} $p={\delta (H) \over l-1}p_{c}+o(H)p_{m}$

където o ( H ) {\displaystyle o(H)} $o(H)$ е редът на схемата, l {\displaystyle l} $l$ е дължината на кода, p m {\displaystyle p_{m}} $p_{m}$ е вероятността за мутация, а p c {\displaystyle p_{c}} $p_{c}$ е вероятността за кръстосване. Така че схема с по-малка дефиниционна дължина δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ е по-малко вероятно да бъде нарушена.
Често неразбираем момент е защо Теоремата за схемата е неравенство, а не равенство. Отговорът всъщност е прост: Теоремата пренебрегва малката, но ненулева вероятност низ, принадлежащ към схемата H {\displaystyle H} $H$ , да бъде създаден "от нулата" чрез мутация на един низ (или рекомбинация на два низа), който не е принадлежал към H {\displaystyle H} $H$ в предишното поколение.

Ограничение

Теоремата за схемите е валидна при предположението за генетичен алгоритъм, който поддържа безкрайно голяма популация, но невинаги се пренася в (крайната) практика: поради грешка при вземането на проби в началната популация генетичните алгоритми могат да се слягат със схеми, които нямат селективно предимство. Това се случва по-специално в мултимодалната оптимизация, където функцията може да има множество върхове: популацията може да се отклони, за да предпочете един от върховете, игнорирайки останалите.

Причината, поради която теоремата за схемата не може да обясни силата на генетичните алгоритми, е, че тя важи за всички случаи на проблеми и не може да направи разлика между проблеми, при които генетичните алгоритми се справят слабо, и проблеми, при които генетичните алгоритми се справят добре.

Построяване на мултимодална функция в две променливи.

Въпроси и отговори

Въпрос: Какво представлява теоремата на Холанд за схемите?

О: Теоремата за схемата на Холанд е теорема за генетичните алгоритми, която гласи, че индивидите с фитнес, който е по-висок от средния, е по-вероятно да надделеят.

В: Кой и кога е предложил теоремата за схемата на Холанд?

О: Джон Холанд предлага теоремата за схемата на Холанд през 70-те години на миналия век.

В: Какво е схема в контекста на генетичните алгоритми?

О.: В контекста на генетичните алгоритми схемата е шаблон, който идентифицира подмножество от низове със сходства в определени позиции на низовете.

В: Каква е интерпретацията на теоремата за схемата на Холанд, която се използва като основа за обяснения на силата на генетичните алгоритми?

О: Интерпретацията на теоремата за схемата на Холанд, която е използвана като основа за обяснение на силата на генетичните алгоритми, е, че индивидите с фитнес, който е по-висок от средния, е по-вероятно да надделеят.

Въпрос: Какво показаха критиките към теоремата за схемата на Холанд?

О: Критиката на теоремата за схемата на Холанд показа, че тя е специален случай на уравнението на Прайс, в което функцията на индикатора на схемата е макроскопичното измерване.

В: Кой е специалният случай на цилиндричните множества?

О: Схемите са специален случай на цилиндричните множества.

В: Какъв вид пространство образуват схемите?

О: Схемите образуват топологично пространство.