AlegsaOnline.com

Holanda shēmu teorēma: definīcija, nozīme un kritika ģenētiskajos algoritmos

Holanda shēmas teorēma: definīcija, nozīme un kritika ģenētiskajos algoritmos — skaidrojums, vēsture, piemēri un diskusijas par tās ierobežojumiem un pielietojumu.

Autors: Leandro Alegsa Izveides datums: 2022. gada 5. aprīlis Pēdējā atjaunināšana: 2025. gada 16. oktobris

simple.wikipedia.org · Public domain

Holanda shēmas teorēma, ko dēvē arī par ģenētisko algoritmu fundamentālo teorēmu, ir nevienlīdzība, kas izriet no evolūcijas dinamikas vienādojuma rupjās struktūras. Shēmas teorēma apgalvo, ka īsas, zemas kārtas shēmas, kuru piemērotība ir virs vidējās, var palielināties ģenētiskā algoritma populācijā vairāku paaudžu gaitā. Teorēmu pagājušā gadsimta 70. gados ierosināja Džons Holands. Sākotnēji to plaši uzskatīja par pamatu ģenētisko algoritmu darbības un jaudas skaidrojumiem. Vēlākā literatūrā tomēr tika norādīts, ka šī interpretācija ir pārāk vienkāršota: shēmas teorēma dod tikai zemāko robežu sagaidāmajai shēmu skaita izmaiņai un ir iegūta zem vairākiem idealizētiem pieņēmumiem. Dažās publikācijās parādīts arī, ka shēmas teorēma ir īpašs gadījums plašākam cenas (Price) vienādojumam, kurā shēmas indikatora funkcija darbojas kā makroskopisks mērījums.

Shēma ir veidne, kas identificē virkņu apakškopu ar līdzībām noteiktās virkņu pozīcijās. Piemēram, binārajā alfabētā shēma 1*0* apzīmē visas virknes, kurās pirmajā pozīcijā ir 1, trešajā — 0, bet otrā un ceturtā pozīcija var būt jebkura (atsevišķi simboli aizstāti ar vietturētāju “*”). Shēmas ir cilindrisko kopu īpašs gadījums, tāpēc tās var traktēt kā elementus attiecīgā topoloģiskā telpā (cilindriskās kopas ģeneratori).

Definīcija un intuīcija

Vienkāršā valodā shēma (H) ir paraugs vai maska, kas nosaka noteiktas pozīcijas virkņu garumā, savukārt pārējās pozīcijas ir "neizšķirtas" (wildcards). Shēmas teorēma aplūko, kā šo shēmu skaits populācijā mainās, ja darbojas reprodukcijas mehānismi: atlase, krustošana (crossover) un mutācija. Ja shēma ir īsa (t. i., specifiskās pozīcijas ir tuvu viena otrai) un zemas kārtas (t. i., maz nerazlietoto, fiksēto pozīciju), un ja to vidējā piemērotība ir lielāka par populācijas vidējo piemērotību, tad šīs shēmas īpatsvars var pieaugt nākamajās paaudzēs.

Formālā izteiksme

Holanda klasiskā nevienlīdzība bieži tiek uzrakstīta šādi (gaidāmā vērtība vai sagaidāmais skaits m shēmām H nākamajā paaudzē):

E[m(H,t+1)] ≥ m(H,t) * (f(H) / f̄) * [1 - p_c * (δ(H)/(l-1)) - o(H) * p_m]

Kur:

m(H,t) — shēmas H gadījumu skaits laikposmā t;
f(H) — vidējā piemērotība tiem individuāliem stringiem, kas pieder shēmai H;
f̄ — populācijas vidējā piemērotība;
p_c — krustošanas (crossover) varbūtība (parasti viena-šķēršļu gadījums formulu atvasinājumos);
p_m — mutācijas varbūtība uz vienu simbolu;
o(H) — shēmas kārta (order): fiksēto (nespecifisko) pozīciju skaits shēmā;
δ(H) — definējošā garuma (defining length): attālums starp pirmo un pēdējo fiksēto pozīciju;
l — ģenotipa (stringa) kopējais garums.

Intuitīvi: f(H)/f̄ nosaka, cik veiksmīga shēma ir salīdzinājumā ar vidējo, bet izteiksmes kreisās puses faktors [1 - ...] atspoguļo, cik lielā mērā šī shēma tiek iznīcināta vai bojāta krustojuma un mutācijas rezultātā. Ja iznīcināšanas termiņš ir mazs un f(H)/f̄ > 1, tad sagaidāms shēmas īpatsvara palielinājums, kas, atkārtojoties pa paaudzēm, var radīt eksponenciālu augšanu ideālos apstākļos.

Shēmu parametri

Kārta (o(H)) — cik daudz pozīciju shēmā ir konkrētas (nevis wildcards). Mazāka kārta nozīmē, ka mazāk bitu jāuztur vienā kopā, un tie mazāk riskē tikt izmainīti mutācijas laikā.
Definējošā garuma (δ(H)) — attālums starp pirmajiem un pēdējiem noteiktajiem simboliem. Jo mazāks δ(H), jo mazāka iespēja, ka krustojums to "sagriezīs".

Nozīme ģenētiskajos algoritmos

Holanda shēmas teorēma deva konceptuālu pamatu building block hypothesis — idejai, ka labas atrisinājuma daļas (mazi, spēcīgi kombinēti bitti) tiek apkopotas un pakāpeniski salikti kopā, lai veidotu arvien labākus risinājumus. Teorēma palīdz saprast, kā atlase un ģenētiskie operatori var saglabāt un pastiprināt šādas detaļas populācijā. Tā arī iedrošināja pētniekus izstrādāt reprezentācijas un operatorus, kas saglabā "labus" bitu blokus (piem., mazā definējošā garuma shēmas).

Kritika un ierobežojumi

Holanda teorēma dod tikai zemāko robežu sagaidāmajam shēmu skaitam — tā neparedz precīzas dinamikas vai ātrumu ilgtermiņā.
Teorēma balstās uz vairākiem idealizētiem pieņēmumiem: proporcionālā atlasei, viena-šķēršļa krustojumam un nelielām mutāciju varbūtībām. Reālos algoritmos bieži izmanto citas atlases metodes, daudzšķēršļu krustošanu, populācijas aprēķina nianses utml., kas maina uzvedību.
Shēmas var overlapot un veidot milzīgu skaitu to kombināciju; shēmu teorēma neatrisina, kā no šī milzīgā kopuma efektīvi izvēlēties vai modelēt atkarības starp bitiem (linkāžu problēma, epistāze).
Vairāki pētnieki (piem., izmantojot Price vienādojumu, Vose un citi) ir parādījuši precīzākus vai visaptverošākus aprakstus GA dinamikai. Daļa literatūras arī apstrīd "building block" kā universālu paskaidrojumu — praktiskie rezultāti rāda, ka GA darbība reizēm balstās uz citiem mehānismiem.
Teorija ir deterministiska sagaidāmajā vērtībā un neņem pilnībā vērā stohastiskumu (gala populāciju variāciju, ģimenes izmērus, nejaušu efektu, mazas populācijas izmaiņas).

Piemērs

Apsveriet bitu virknes garumu l = 4 un shēmu H = 1*0*. Ja populācijā ir m(H,t) = 10 piemēri, vidējā piemērotība šo piemēru vidū f(H) = 1.2 un populācijas vidējā piemērotība f̄ = 1.0, p_c = 0.7, p_m = 0.01, o(H) = 2 (divas konkrētas pozīcijas) un δ(H) = 2. Tad, pēc Holland izteiksmes, sagaidāmais šīs shēmas skaits nākamajā paaudzē būs vismaz:

10 * (1.2/1.0) * [1 - 0.7*(2/(4-1)) - 2*0.01] ≈ 12 * [1 - 0.4667 - 0.02] ≈ 12 * 0.5133 ≈ 6.16

Tas parāda: lai gan shēma ir labāka par vidējo (f(H)/f̄ > 1), krustojuma un mutācijas iznīcināšanas efekti var samazināt tās sagaidāmo skaitu nākamajā paaudzē. Ja aizsardzības faktors [1 - ...] būtu > 1/f(H)*f̄, ilgtermiņā šī shēma varētu augt eksponenciāli.

Praktiski secinājumi

Holanda shēmas teorēma ir vērtīgs rīks, lai iegūtu intuitīvu izpratni par to, kā atlase un ģenētiskie operatori ietekmē "mazas" struktūras populācijā.
Tas nav pilnīgs vai vienīgais paskaidrojums ģenētisko algoritmu sekmēm; praktiskai izmantošanai jāņem vērā shēmu savstarpējās atkarības (linkāža), atlases veids, operatoru īpatnības un stohastiskās ietekmes.
Izstrādājot reprezentāciju un operatorus, praktiski jāmērķē uz to, lai svarīgās problēmas daļas būtu koncentrētas īsos, stabilos blokos (samazināts definējošais garums), vienlaikus izmēģinot adaptīvākas metodes (linkāžas mācīšanās, selekcijas modifikācijas u. c.).

Secinot — Holanda shēmas teorēma ir nozīmīgs teorētisks pamats ģenētisko algoritmu pētījumam, taču to jālieto kā viens no instrumentiem kombinācijā ar plašāku analīzi un empīriskām pārbaudēm.

Apraksts

Aplūkojiet 6 garas bināro virknes. 1*10*1 shēma apraksta visu 6 garu virkņu kopu ar 1 1, 3 un 6 pozīcijā un 0 4 pozīcijā. * ir aizstājējzīmīte, kas nozīmē, ka 2. un 5. pozīcijai var būt vērtība 1 vai 0. Shēmas kārtība o ( H ) {\displaystyle o(H)} $o(H)$ ir definēta kā fiksēto pozīciju skaits šablonā, bet definējošais garums δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ ir attālums starp pirmo un pēdējo konkrēto pozīciju. Šablona 1*10*1 kārtība ir 4, un tā definējošais garums ir 5. Shēmas piemērotība ir visu shēmai atbilstošo virkņu vidējā piemērotība. Virknes piemērotība ir kodētā problēmas risinājuma vērtības mērs, ko aprēķina ar konkrētai problēmai specifisku novērtēšanas funkciju. Izmantojot ģenētisko algoritmu iedibinātās metodes un ģenētiskos operatorus, shēmas teorēma nosaka, ka īsas, zemas kārtas shēmas, kuru fitness ir virs vidējā, secīgās paaudzēs eksponenciāli palielinās. Izteikta kā vienādojums:

E ( m ( H , t + 1 ) ) ≥ m ( H , t ) f ( H ) a t [ 1 - p ] . {\displaystyle \operatora nosaukums {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].$

Šeit m ( H , t ) {\displaystyle m(H,t)} $m(H,t)$ ir to virkņu skaits, kas pieder shēmai H {\displaystyle H} $H$ paaudzē t {\displaystyle t}. $t$ , f ( H ) {\displaystyle f(H)} $f(H)$ ir shēmas H {\displaystyle H} $H$ vidējā novērotā piemērotība un a t {\displaystyle a_{t}} $a_{t}$ ir vidējā piemērotība paaudzē t {\displaystyle t} $t$ . Izjaukšanas varbūtība p {\displaystyle p} $p$ ir varbūtība, ka krustošana vai mutācija iznīcinās shēmu H {\displaystyle H} $H$ . To var izteikt kā:

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}$

kur o ( H ) {\displaystyle o(H)} $o(H)$ ir shēmas secība, l {\displaystyle l} $l$ ir koda garums, p m {\displaystyle p_{m}} $p_{m}$ ir mutācijas varbūtība un p c {\displaystyle p_{c}} $p_{c}$ ir krustojuma varbūtība. Tātad shēmai ar īsāku definējošo garumu δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ ir mazāka varbūtība, ka tā tiks izjaukta.
Bieži vien tiek pārprasts, kāpēc shēmas teorēma ir nevienādība, nevis vienlīdzība. Atbilde patiesībā ir vienkārša: teorēma neņem vērā mazo, tomēr nenulles varbūtību, ka virkne, kas pieder shēmai H {\displaystyle H} $H$ , tiks izveidota "no nulles", mutējot vienu virkni (vai rekombinējot divas virknes), kas iepriekšējā paaudzē nepiederēja H {\displaystyle H} $H$ .

Ierobežojums

Shēmas teorēma ir spēkā, pieņemot, ka ģenētiskais algoritms uztur bezgalīgi lielu populāciju, bet ne vienmēr tiek pārnesta uz (galīgo) praksi: paraugu ņemšanas kļūdas dēļ sākotnējā populācijā ģenētiskie algoritmi var konverģēt uz shēmām, kurām nav selektīvo priekšrocību. Tas jo īpaši notiek multimodālā optimizācijā, kur funkcijai var būt vairāki maksimumi: populācija var dreifēt, dodot priekšroku vienam no maksimumiem, ignorējot pārējos.

Iemesls, kāpēc ar shēmas teorēmu nevar izskaidrot ģenētisko algoritmu jaudu, ir tas, ka tā attiecas uz visiem problēmu gadījumiem un nevar atšķirt problēmas, kurās ģenētiskie algoritmi darbojas vāji, no problēmām, kurās ģenētiskie algoritmi darbojas labi.

Divu mainīgo multimodālas funkcijas grafiks.

Jautājumi un atbildes

J: Kas ir Holanda shēmas teorēma?

A: Holanda shēmas teorēma ir teorēma par ģenētiskajiem algoritmiem, kas saka, ka indivīdi, kuru piemērotība ir augstāka par vidējo, ar lielākām izredzēm gūst pārsvaru.

J: Kas un kad ierosināja Holanda shēmas teorēmu?

A: Džons Holands ierosināja Holanda shēmas teorēmu pagājušā gadsimta 70. gados.

J: Kas ir shēma ģenētisko algoritmu kontekstā?

A: Ģenētisko algoritmu kontekstā shēma ir veidne, kas identificē virkņu apakškopu ar līdzībām noteiktās virkņu pozīcijās.

J: Kāda ir Holanda shēmas teorēmas interpretācija, kas tika izmantota par pamatu ģenētisko algoritmu jaudas skaidrojumiem?

A: Holanda shēmas teorēmas interpretācija, kas tika izmantota par pamatu ģenētisko algoritmu spēka skaidrojumiem, ir tāda, ka indivīdi, kuru fitness ir augstāks par vidējo, ar lielāku varbūtību gūst pārsvaru.

J: Kāda ir Holanda shēmas teorēmas kritika?

A: Holanda shēmas teorēmas kritika ir parādījusi, ka tā ir īpašs gadījums cenas vienādojumam, kurā shēmas indikatora funkcija ir makroskopiskais mērījums.

J: Kas ir īpašs cilindrisko kopu gadījums?

A: Shēmas ir cilindrisko kopu īpašais gadījums.

J: Kāda veida telpu veido shēmas?

A: Shēmas veido topoloģisku telpu.

Autors

AlegsaOnline.com - Holanda shēmas teorēma - Leandro Alegsa

Izveides datums: 2022. gada 5. aprīlis
Pēdējā atjaunināšana: 2025. gada 16. oktobris

URL: https://lv.alegsaonline.com/art/44753