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