Za jídlo, šaty a vzduch otročíme na programech z temných světů

Programujeme v BASICu: OROROK OREBUH

Kreacionisti ať raději dále vůbec nečtou…pokud tedy neprogramují rádi v BASICu.

Při příležitosti JHConu jsem zavzpomínal na biologii a to krátké šťastné období, v němž se nebylo třeba učit kdo má a kdo nemá ochmýřený sosáček, protože se probírala genetika. Když pominu věci, které mě na střední vysloveně bavily a stačilo mi je slyšet jen jednou (IT, historie, zeměpis, angličtina), měl jsem problém s tím se učit. Pravda, nejhorší známku na vysvědčení jsem měl trojku z matiky (párkrát i z jiných předmětů, ale z matiky asi pokaždé), protože nakonec jsem se nějak ty věci naládovat do hlavy přinutil, ale vždycky když šlo místo biflování v něčem vymyslet logický systém, byla to pro mě spása. A taková genetika na střední škole není nic jiného než kombinatorika, jen místo čísel se kombinuje s květy fazolí a barvou myší. Je to legrace a normální člověk těch pár principů pochopí asi tak za čtvrt hodiny.

Znovu jsem se k téhle oblasti dostal, když diZZy přinesl do práce odkaz na simulaci vývoje autíček prostřednictvím genetických algoritmů a přirozeného výběru. Vydržel jsem s tím blbnout tři dny prakticky v kuse a jen s velkým vnitřním vypětím jsem se dostal k psaní diplomky. Už po letmém přečtení jsem ale dospěl k názoru, že o JHConu si takovou jednoduchou genetiku i s výběrem naprogramuju na ZX Spectru v BASICu.

Pojal jsem celý problém opravdu velmi jednoduše a díky skvělé práci s vícerozměrnými poli a textovými řetězci v Sinclair BASICu celé programování trvalo ani ne půl hodiny. Než přistoupím k vysvětlení funkcionality, malá ukázka. Žijeme v 21. století a tří až pětiminutové video by mělo existovat naprosto ke všemu:


Co je vlastně třeba, aby to fungovalo?
Potřebujeme simulované jedince, kteří budou mít nějakou sadu vlastností a tyto vlastnosti je lépe či hůře předurčí k přežití. Pokud takové vlastnosti máme, není problém každého jedince ohodnotit a k těm lepším se chovat lépe než k těm horším, čímž nasimulujeme bezcitnou mrchu přírodu.

A jak že to tedy celé funguje?
Populace se skládá z deseti jedinců, každý má deset vlastností reprezentovaných písmeny A-Z. Jako nejlepší kombinace těchto vlastností byla stanovena taková, která tvoří text ZXSPECTRUM. První generace je sestavena čistě náhodně, každý jedinec je pak ohodnocen, za každé správné písmeno na správném místě je 100 bodů. Jedinci jsou seřazeni od nejúspěšnějšího k nejhoršímu. První dva postupují do další generace beze změny (elitářský výběr, zajišťuje, že další generace nebude mít maximum horší než ta předchozí). Následně prvních 9 jedinců vstupuje do křížení – první s druhým, druhý s třetím, třetí se čtvrtým atd. Nejhorší jedinec do křížení nevstupuje, nejlepší a předposlední jedinec se množí jen jednou (mírně to zpomaluje vývoj). Tím se získá celkem deset jedinců, kteří jsou ohodnoceni a celý proces se opakuje.

Jak probíhá křížení?
Pravil jednou jeden moudrý , že pokud něčemu nerozumíme a vypadá to náhodně, lze to nahradit generováním náhodných čísel. Děje se tak i zde. Dva vybraní křížící se jedinci se prochází znak po znaku. Konstantou je nastavena procentuální pravděpodobnost mutace, následně se generujeme číslo od 0 do 100 a pokud se trefí do rozsahu této pravděpodobnosti, je aktuální znak vygenerován zcela nový. Pokud k mutaci na základě vygenerovaného čísla nedochází, je výsledná vlastnost výsledkem křížení: zbývající část rozsahu, tj. 100-pravděpodobnost_mutace, vydělí dvěmi a podle toho kam generované číslo padlo, je vybrán znak jednoho z rodičů.


   1 CLS
   5 LET g=1
  10 LET m=10
  20 LET z$="ZXSPECTRUM"
  30 DIM a$(10,10)
  40 DIM b$(10,10)
  50 DIM r(10)
 100 REM ------------------- Prvni plneni
 110 FOR i=1 TO 10
 120 FOR x=1 TO 10
 130 LET a$(i,x)=CHR$ (65+INT (RND*26))
 135 BORDER INT (RND*7)
 140 NEXT x
 150 NEXT i
 200 REM ------------------- Hodnoceni
 210 FOR i=1 TO 10
 220 FOR x=1 TO 10
 230 IF a$(i,x)=z$(x) THEN LET r(i)=r(i)+100
 240 NEXT x
 260 NEXT i
 300 REM ------------------- Razeni
 310 LET o=0
 320 FOR i=1 TO 9
 330 IF r(i)< r(i+1) THEN LET t$=a$(i): LET a$(i)=a$(i+1): LET a$(i+1)=t$: 
 LET t=r(i): LET r(i)=r(i+1): LET r(i+1)=t: LET o=o+1
 335 BORDER INT (RND*7)
 340 NEXT i
 350 IF o>0 THEN GO TO 310
 400 REM ------------------- Vypis
 401 POKE 23692,0
 405 PRINT : PRINT "Generace:";g
 410 PRINT "-------------------"
 420 FOR i=1 TO 10
 430 PRINT a$(i),r(i)
 440 NEXT i
 500 REM ------------------- Krizeni
 510 FOR i=1 TO 8
 520 FOR x=1 TO 10
 530 LET n=RND*100
 540 IF n<=m THEN LET b$(i+2,x)=CHR$ (65+INT (RND*26))
 550 IF n>m AND n<=m+(100-m)/2 THEN LET b$(i+2,x)=a$(i,x)
 560 IF n> m+(100-m)/2 THEN LET b$(i+2,x)=a$(i+1,x)
 570 NEXT x
 575 BORDER INT (RND*7)
 580 NEXT i
 590 LET b$(1)=a$(1): LET b$(2)=a$(2)
 600 REM ------------------- Presun
 610 FOR i=1 TO 10
 620 LET a$(i)=b$(i): LET r(i)=0
 630 NEXT i
 700 REM ------------------- A znovu
 710 LET g=g+1
 720 GO TO 200

Jak vidno z videa, funguje to. Někdy rychleji, někdy pomaleji, ale vždy je výsledný řetězec sestaven rychleji, než kdybychom jej hádali metodou brute force. Byla to legrace programovat, je to legrace sledovat a ještě větší legrace bude, podaří-li se mi sestavit obdobný program v assembleru nad bitmapou. Jen jsem zvědav na rychlost, výše uvedené video je 10x zrychleno.