piatok 22. apríla 2011
utorok 5. apríla 2011
Evolučné algoritmy - Simulované žíhanie
Úloha:
Použite simulované žíhanie s gaussovskou mutáciou so sigmou 0,1 umiestnenia vrcholov na nájdenie rozmiestnenia vrcholov kompletného grafu pre n=4 až n=10 s čo najmenším počtom prekrížení. Počiatočné umiestnenia vrcholov by mali byť v štvorci o jednotkovej hrane, ale mutácie môžu vysunúť vrcholy mimo tohto štvorca. Použite verziu bez a s pokutovou funkciou, penalizujúcou vybočenie vrcholov ďaleko od stredu štvorca. Vypočítajte priemer a smerodajnú odchýlku na počet pokusov k dosiahnutiu cieľa pre každý z grafov.
Riešenie:
Parametre algoritmu:
Energia je počet prekrížení
Teplota klesá každých 250 pokusov
Mutácia je posunutie jedného vrcholu
Pokutová funkcia: čím väčšia vzdialenosť mutovaného vrcholu od stredu štvorca tým väčšia pravdepodobnosť, že túto mutáciu nepoužíjeme.
Výsledok algoritmu:
Celá prezentácia
Zdrojový kód v Scala-e
Použite simulované žíhanie s gaussovskou mutáciou so sigmou 0,1 umiestnenia vrcholov na nájdenie rozmiestnenia vrcholov kompletného grafu pre n=4 až n=10 s čo najmenším počtom prekrížení. Počiatočné umiestnenia vrcholov by mali byť v štvorci o jednotkovej hrane, ale mutácie môžu vysunúť vrcholy mimo tohto štvorca. Použite verziu bez a s pokutovou funkciou, penalizujúcou vybočenie vrcholov ďaleko od stredu štvorca. Vypočítajte priemer a smerodajnú odchýlku na počet pokusov k dosiahnutiu cieľa pre každý z grafov.
Riešenie:
Parametre algoritmu:
Energia je počet prekrížení
Teplota klesá každých 250 pokusov
Mutácia je posunutie jedného vrcholu
Pokutová funkcia: čím väčšia vzdialenosť mutovaného vrcholu od stredu štvorca tým väčšia pravdepodobnosť, že túto mutáciu nepoužíjeme.
Výsledok algoritmu:
Celá prezentácia
Zdrojový kód v Scala-e
Evolučné algoritmy
Úloha
1.a) Predpokladajte, že pracujete v prostredí genetického programovania, ktorého jazyk pozostáva z konštanty 1 a operácie +. Koľko uzlov má najmenší strom, ktorým vypočítate číslo n? Napríklad číslo 3 môže byť vyjadrené ako výraz ((1+1)+1), ktorého strom má 5 vrcholov, 3 koncové jednotky a dva operátory +.
2n + 1
1.b) Napíšte pseudokód, ktorý bude schopný zanalyzovať a zbehnúť kód v tvare výrazu (+(+ 1 1)1)
symbols <- read from right to left
foreach (symbol <- symbols)
{
if space
next
if opening_parenthesis
operator <- pop
operand1 = <- pop
operand2 = <- pop
pop //closing parenthesis
push operator.apply(operand1, operand2)
else
push symbol
}
pop
2.b) Predpokladajte, že pracujete v prostredí genetického programovania, ktorého jazyk pozostáva z konštanty 1, operácie +, SQR, STO, a RCL, kde SQR znamená druhú mocninu čísla v pamäti, STO znamená operáciu, ktorá zoberie jednu hodnotu,, dá ju do externej pamäti a vráti hodnotu v pamäti. RCL inštrukcia vráti hodnotu pamäti. Predpokladajte, že ľavý argument operácie + je vyhodnotený pred pravým. Nájdite najmenší strom, ktorý vypočíta čísla n=3,4,5,...12.
Celá prezentácia
1.a) Predpokladajte, že pracujete v prostredí genetického programovania, ktorého jazyk pozostáva z konštanty 1 a operácie +. Koľko uzlov má najmenší strom, ktorým vypočítate číslo n? Napríklad číslo 3 môže byť vyjadrené ako výraz ((1+1)+1), ktorého strom má 5 vrcholov, 3 koncové jednotky a dva operátory +.
2n + 1
1.b) Napíšte pseudokód, ktorý bude schopný zanalyzovať a zbehnúť kód v tvare výrazu (+(+ 1 1)1)
symbols <- read from right to left
foreach (symbol <- symbols)
{
if space
next
if opening_parenthesis
operator <- pop
operand1 = <- pop
operand2 = <- pop
pop //closing parenthesis
push operator.apply(operand1, operand2)
else
push symbol
}
pop
2.b) Predpokladajte, že pracujete v prostredí genetického programovania, ktorého jazyk pozostáva z konštanty 1, operácie +, SQR, STO, a RCL, kde SQR znamená druhú mocninu čísla v pamäti, STO znamená operáciu, ktorá zoberie jednu hodnotu,, dá ju do externej pamäti a vráti hodnotu v pamäti. RCL inštrukcia vráti hodnotu pamäti. Predpokladajte, že ľavý argument operácie + je vyhodnotený pred pravým. Nájdite najmenší strom, ktorý vypočíta čísla n=3,4,5,...12.
Celá prezentácia
Prihlásiť na odber:
Príspevky (Atom)
