Holanda shēmas teorēma

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)} ir definēta kā fiksēto pozīciju skaits šablonā, bet definējošais garums δ ( H ) {\displaystyle \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]. }

Šeit m ( H , t ) {\displaystyle m(H,t)} ir to virkņu skaits, kas pieder shēmai H {\displaystyle H} paaudzē t {\displaystyle t}. , f ( H ) {\displaystyle f(H)} ir shēmas H {\displaystyle H} vidējā novērotā piemērotība un a t {\displaystyle a_{t}} ir vidējā piemērotība paaudzē t {\displaystyle t} . Izjaukšanas varbūtība p {\displaystyle p} ir varbūtība, ka krustošana vai mutācija iznīcinās shēmu H {\displaystyle 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}}}

kur o ( H ) {\displaystyle o(H)} ir shēmas secība, l {\displaystyle l} ir koda garums, p m {\displaystyle p_{m}} ir mutācijas varbūtība un p c {\displaystyle p_{c}} ir krustojuma varbūtība. Tātad shēmai ar īsāku definējošo garumu δ ( H ) {\displaystyle \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} , tiks izveidota "no nulles", mutējot vienu virkni (vai rekombinējot divas virknes), kas iepriekšējā paaudzē nepiederēja H {\displaystyle 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.