Sisteme de programe pentru timp real

Universitatea Politehnica din Bucuresti 2007-2008 Suport de curs

Curs Nr. 7 & 8

Programare genetica Generarea imaginilor cu sistemul GAIA

1 Programare genetica
Aplicarea algoritmilor genetici asupra unei populatii de programe Indivizii = nu gene cu dim fixe ci programe Op genetici:
crossover (2 parinti) reproducere (1 parinte) mutatie duplicare gene stergere gene
3

Programare genetica
Programele = arbori sintactici max(x * x, x + 3 * y) Noduri interne = functii Frunze = terminale Programe = compuse din rutine Set de arbori (rutine) grupate intr-o radacina Nr, tip, structura rutine = arhitectura Arborii notatie prefixata (S-expression) (max (* x x) (+ x (* 3 y)))
4

Pasi pregatitori
1. 2. 3. 4. 5. Ex: Descriere de nivel inalt Set de terminale (vars, funct cu 0 args, const) Set de functii (aritmetice, conditionale) Fitness (explicit sau implicit) Parametrii de control al AG Conditia de terminare si metoda de alegere a rez Tragerea la tinta Aspersoare Robot care se deplaseaza
5

Algoritmul genetic
1. Populatie generata aleator cu programe compuse din functii si terminale 2. Repeta pentru mai multe generatii Executa fiecare program si determina fitness Selectioneaza cf schemei de selectie Creaza noi indivizi prin aplicarea op gen:
Reproductie: copiaza individ Crossover: creeaza 2 descendenti din 2 parinti sau 1 parinte Mutatie: asupra unui individ existent in populatie Operatii de alterare a arhitecturii asupra unui individ
6

3. Testeaza cond de terminare

Algoritmul genetic

Metoda de initializare
Populatie generata aleator cu programe compuse din functii si terminale Construieste aleator arborele pana la o adancime maxima 1. Metoda Full numai functii pana la nivelul frunzelor 2. Metoda Grow functii si terminale pe orice nivel

Cum se genereaza
gen_rnd_expr(func_set, term_set, max_d, method) if max_d = 0 or method = Grow and random_digit = 1 then expr = choose_random_element(term_set) else func = choose_random_element(func_set) for i=1 to arity(func) do arg_i = gen_rnd_expr(func_set, term_set, max_d-1, method) expr=(fun, arg_1, arg_2,..) return expr end
9

Full si Grow

10

Operatori genetici
Crossover 2 parinti = parinti diferiti Crossover 1 parinte = parinti identici (reproducere) Crossover point = 90% nodui interne, 10% frunze Mutatie = crossover intre un program existent si unul generat aleator Toate programele obtinute sunt valide din punct de vedere sintactic
11

Crossover

12

Crossover

13

Mutatie

14

Evaluare
Compilare separata Interpretare cod pe masina virtuala eval(expr) if expr este lista then proc=expr(1) value = proc(eval(expr(2)), eval(expr(3)),..) else if exp este var sau const then value =expr else value = expr(0) return value end
15

Evaluare
Fitness eroarea intre iesirea actuala si iesirea dorita cat de bine recunoaste anumite sabloane castig in jocuri, etc. Valori calculate si efecte laterale Executat pe seturi de valori fitness cases

16

Exemplu
Program genetic pt calculul radacinilor ecuatiei x2 + x + 1 T (terminal set)={x,R}, R = (-5, 5) F (function set) = {+, -, *, /} , cu / modif pt 0 Fitness = (-1,+1)|(x2 + x + 1)- (v2 + v + 1)| In practica se aproximeaza mai multe valori pt x Selectie: turneu, proportionala cu fitness Crossover 90 % din populatie Reproductie - 8% Mutatie - 2% Fitness < 0.01 Grow
17

Exemplu
(a) x+1
+ 0 1

(b) x2+1
+

(c) 2

(d) x
*

+ * 2 0
-1 -2

0.67

1.0

1.67

2.67
18

(a) x+1, 0.67

+ 0

(b) x2+1, 1.0

+

(c) 2, 1.67
+

(d) x, 2.67
*

1 x 1 x

-1

-2

Reprod
+ 0

Mutatie
+

Crossover
1

/ x 1 x x

(c) x, 2.67 (b) 1, 1.0 (d) x2+x+1, 0

x

x
1
19

(a) x+1, 0.67

2 GA pentru generare de imagini

Programul Gaia generarea de noi imagini Fiecare imagine este generata prin evaluarea unei formule matematice Sa se gaseasca formule care prin evaluare sa produca imagini interesante. GA pt a produce astfel de formule Se genereaza aleator o formula si se genereaza variatii ale acesteia Utilizatorul selecteaza cele mai interesante imagini Formulele selectate devin noi generatii; procesul se repeta Conceptul de evolutie este utilizat pentru a genera noi formule din cele existente
20

GA pentru generare de imagini

21

GA pentru generare de imagini

(lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (PHY)) (color_grad "earth" (gradient (log (+ (&& (lerp (PHY) #(-0.080 0.408 0.254) (RAD)) (RAD)) #(-0.098 -0.277 0.840))))) (color_noise (mod (warped_color_noise (X) -0.003 -0.296 #(-0.359 0.020 0.790)) (Y)) (color_noise (X) (invert (Y))))
22

GA pentru generare de imagini

23

GA pentru generare de imagini

(lerp (* (vector -0.422 (warped_bw_noise (RAD) #(-0.468 0.375 -0.624) (Y) (RAD)) (RAD)) (X)) (RAD) (bw_noise (PHY) (log 0.529)))

(triwave (- (^ (& (RAD) (PHY)) (PHY)) #(-0.176 0.738 -0.928)))

(mynoise (triwave (|| (RAD) (PHY))) (RAD))

24

GA pentru generare de imagini

25

GA pentru generare de imagini

(lerp (* (X) (X)) (/ (/ #(0.204 0.166 0.711) (RAD)) (RAD)) (bw_noise (RAD) (RAD))) (triwave (lerp (min (lerp (PHY) (lerp (PHY) 0.033 (RAD)) #(0.050 0.137 0.586)) (PHY)) (IRAD) (RAD)))

(color_noise (cos (+ (bw_noise (mod (X) (Y)) #(-0.419 -0.415 0.673)) (Y))) 0.296)
26

GA pentru tranzitii de imagini

Programul poate genera de asemenea tranzitii intre imagini generate Utilizatoruls electeaza sursa si desinatia si programul gaseste secventa de imagini care face tranzitia Daca formulele nu au nimic in comun, tranzitiile sunt pure amestecuri ale imaginilor Daca formulele au similaritati se obtin tranzitii interesante

27

GA pentru tranzitii de imagini

Source: (triwave (abs (RAD))) Target: (triwave (abs (X)))

28

GA pentru tranzitii de imagini

Source: (triwave (abs (X))) Target: (triwave (&& (PHY) (PHY)))

29

GA pentru tranzitii de imagini

Source: (/ (& (Y) (X)) (RAD)) Target: (/ (& (Y) (RAD)) (RAD))

30

2.1 Genotip
Gaia codifica o imagine printr-o formula si un domeniu Ambele elemente sunt genotipul solutiei Formulele = set de operatori, variabile si constante Formula S-expression Domeniul indica unde se evalueaza formula Domeniul este o regiune in planul real specificata de limite Domeniul implicit este [-1..1] x [-1..1].
31

Genotip
Formulele pot fi oricat de lungi Operatorii cu argumente noduri interne Operatorii fara argumente frunze S-Expression (+ (+ (X) (Y)) (Y)) (gradient (invert (- (0.5) (RAD)))) Domeniu [0..1] x [0..1] [-1..1] x [-1..1]

(abs (lerp (mynoise (/ (triwave (mod (PHY) -0.190)) (RAD)) (min (RAD) -0.873)) (Y) (X))) [-1..1] x [-1..1]
32

2.2 Formule si operatori

5 clase de operatori: 1. Operatori de domeniu: X,Y,RAD,PHY depind de domeniul pe care se evalueaza formula. X, Y Returns an image which is the values of the domain in the Xaxis or Y-axis directions. The resulting images are horizontal and vertical ramps of luminance. Images obtained with the domain [0..1] x [0..1]

33

Formule si operatori
RAD The resulting image depends directly on the domain where it is evaluated. The luminance of each pixel in the image is the distance from the coordinates of the pixel in the domain to the origin, typically at the center.

IRAD Similar to the operador RAD, the luminance of each pixel is the distance measured to the nearest odd integer in the domain. The black corners represents the four integer coords (-1,-1) (1,1) (1,1) (1,-1) of the domain where the image was rendered.

34

Formule si operatori
PHY The luminance of the resulting image represents the angular coordinate of the pixel, with the zero heading [Link] where the value is greater than 1 a white pixel is used.

35

Formule si operatori
2. One argument functions: From a single image, returns a new image after applying some function to the pixels values of the argument. Some examples of functions are cos, sin, normalize, gradient, abs, round, triwave, ... TRIWAVE This operator is bounded in the interval 0..1 for all the source values. This means that we can feed this operator with any image with any pixel values, that the resulting image will be limited between 0 and 1.

36

Formule si operatori
3. Simple operators: Combines two images to return the result of the operator. The combination operator can be as easy as add the images, substract, multitply, or combine logically at pixel level. 4. Complex operators: Need more than two images as arguments and returns a more complex combination of them. They usually use some of them as parameters of the combination. Examples: LERP, noise functions, color grad, ... 5. Misc operators: The operators which uses external images imported from other programs or those which use the templates of the program
37

Formule si operatori
LERP It takes three images as arguments: A,B,C and computes the resulting image as A+(B-A)*Triwave(C). It makes a linear interpolation from A to B, using C as weight of the interpolation. The operator Triwave is included to limit C in the interval 0..1.

38

2.3 Mutatie Evolution is achived by two methods: Mutation and Combination. Mutations If we are using a long formula to obtain an image, and make some little changes in the formula, the final image will be in general quite similar but different. Mutations are normally applied on a single node, and affects this node and maybe nodes in lower levels. The node is chosen randomly in the tree.
39

Mutation
New Node: The selected node is substituted by a new simply random node. This type of mutation can achieve important changes when the original tree is big, and the node is near the root of the tree. Adjust Node: The node is modified by another one with the same number of parameters. The tree maintains the same structure, but instead of computing the cos (maybe) we will compute the sin, or maybe we will change a constant with value 0.7 by a new one with value 0.5. This type of mutation makes light changes. Node as arg: The selected node becomes the argument of a new random node which is placed in his previous location in the tree, and the old node hanging from it. If the new node needs more arguments they are generated randomly.
40

Mutation
Arg as node: The inverse operation. One of the arguments of the node substitutes the node itself. The new tree is simpler than the original. If the original node got more arguments, they are discarded. Node as uncle: The node is substituted by a copy of a node in upper levels of the tree. Reorder arguments: This operator changes the order of the arguments of the selected node (assuming it has more than two). It can be very different to compute X / RAD or RAD / X. The default number of mutations applied is one, but when formulas become bigger, it is preferable to use two or three. In Gaia, there is only one parent. Children are obtained by performing different types of mutations in different nodes of the same parent.
41

Mutation examples
Parent expression: (triwave (mod (triwave (PHY)) (RAD))) Domain: [-1..1] x [-1..1]

42

Mutation examples
(triwave (mod (triwave (PHY)) (RAD)))

(triwave (mod (lerp (PHY) (Y) (Y)) (RAD)))

43

Mutation examples
1. 2. 3. 4. 5. 6. 7. 8. 9. (triwave (mod (lerp (PHY) (Y) (Y)) (RAD))) (mod (triwave (PHY)) (RAD)) (triwave (mod (^ (triwave (PHY)) (X)) (RAD))) (triwave (mod (PHY) (RAD))) (triwave (lerp (mod (triwave (PHY)) (RAD)) (Y) (RAD))) (triwave (mod (max (triwave (PHY)) (RAD)) (RAD))) (triwave (sin (triwave (PHY)))) (triwave (mod (+ (triwave (PHY)) (RAD)) (RAD))) (triwave (mod (triwave (PHY)) (warped_color_noise (RAD) #(0.653 0.865 -0.369) #(0.683 0.337 -0.625) (X)))) 10.(mod (mod (triwave (PHY)) (RAD)) (PHY)) 11.(triwave (mod (RAD) (triwave (PHY)))) 12.(triwave (rotate (mod (triwave (PHY)) (RAD)) (RAD))) 13.(triwave (mod (gradient (triwave (PHY))) (RAD))) 14.(invert (triwave (mod (triwave (PHY)) (RAD)))) 15.(triwave (* (mod (triwave (PHY)) (RAD)) (X))) 16.(triwave (mod (abs (PHY)) (RAD)))
44

2.4 Combination
We want to find a method to generate images that share characteristics of two previously generated images. To accomplish this we will rely on the fact that the relation between formulas and images is basically associated to the sequences of operators used in the genotypes, rather than the individual operators used. Try to maintain sequences of nodes of the parent and mother in the new genotypes. Combination may be applied several times

45

Combination
Parent Mother

Child 1

Child 2

46

Combination examples
Parent expression: (lerp (* (vector -0.422 (warped_bw_noise (RAD) #(-0.468 -0.375 0.624) (Y) (RAD)) (RAD)) (X)) (RAD) (bw_noise (PHY) (log 0.529))) Domain: [-1..1] x [-1..1] Mother expression: (lerp (triwave (PHY)) (* (lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (PHY)) (triwave (mod (triwave (PHY)) (RAD)))) (RAD)) Domain: [-1..1] x [-1..1]

47

Combination examples

48

Combination examples
(lerp (triwave (RAD)) (* (lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (PHY)) (triwave (mod (triwave (PHY)) (RAD)))) (RAD)) (lerp (triwave (PHY)) (* (lerp #(0.524 0.389 -0.394) (bw_noise (PHY) (log 0.529)) (PHY)) (triwave (mod (triwave (PHY)) (RAD)))) (RAD)) (lerp (triwave (PHY)) (* (lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (PHY)) (triwave (mod #(-0.468 -0.375 -0.624) (RAD)))) (RAD)) (* (lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (PHY)) (triwave (mod (triwave (PHY)) (RAD)))) (lerp (triwave (PHY)) (* (lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (X)) (triwave (mod (triwave (PHY)) (RAD)))) (RAD)) (lerp (* (vector -0.422 (warped_bw_noise (RAD) #(-0.468 -0.375 -0.624) (Y) (RAD)) (RAD)) (- (triwave (RAD)) 0.590)) (RAD) (bw_noise (PHY) (log 0.529))) (lerp (triwave (PHY)) (* (lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (PHY)) (triwave (mod (triwave (PHY)) (RAD)))) (bw_noise (PHY) (log 0.529))) (lerp (* (vector -0.422 (warped_bw_noise (RAD) #(-0.468 -0.375 -0.624) (Y) (lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (PHY))) (RAD)) (X)) (RAD) (bw_noise (PHY) (log 0.529)))
49

Combination examples
(lerp (triwave (PHY)) (* (lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (PHY)) (triwave (mod (triwave (PHY)) (RAD)))) (RAD)) (lerp (triwave (PHY)) (* (lerp #(0.524 0.389 -0.394) (RAD) (PHY)) (triwave (mod (triwave (PHY)) (RAD)))) (RAD)) (lerp (* (vector (PHY) (warped_bw_noise (RAD) #(-0.468 -0.375 -0.624) (Y) (RAD)) (RAD)) (X)) (RAD) (bw_noise (PHY) (log 0.529))) (lerp (* (vector -0.422 (warped_bw_noise (RAD) #(-0.468 -0.375 -0.624) (Y) (RAD)) (RAD)) (X)) (RAD) (bw_noise (PHY) (log (RAD)))) (lerp (triwave (PHY)) (log 0.529) (RAD)) (lerp (* (vector -0.422 (warped_bw_noise (RAD) #(-0.468 -0.375 -0.624) (Y) (RAD)) (RAD)) (X)) (* (lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (PHY)) (triwave (mod (triwave (PHY)) (RAD)))) (RAD)) (lerp (triwave (PHY)) (* (lerp #(0.524 0.389 -0.394) (- (triwave (RAD)) 0.590) (PHY)) (triwave (bw_noise (PHY) (log 0.529)))) (RAD)) (lerp (triwave #(-0.468 -0.375 -0.624)) (* (lerp #(0.524 0.389 -0.394) ((triwave (RAD)) 0.590) (PHY)) (triwave (mod (triwave (PHY)) (RAD)))) (RAD))
50

2.5 Image transitions

The software is able to make smooth transitions between images The user selects one image as the source, and another as the target, and Gaia will make automatically a smooth transition between both images. Depending on the semblance of both source and target, the transition will be a simple melt if the genotypes have nothing in common, but it can be an interesting transition if there are some similarities in the genotypes. We say that two genotypes are similar if they share the upper nodes of the genotypes (the nodes near the root node). The more nodes they share, the more similar they are. If both expressions have different root nodes, the expressions have nothing in common.

51

Image transitions
To obtain the animation, Gaia generates a new genotype parametrized in time. This new genotype has the common nodes of source and target images, and interpolates in time the nodes which are different. This means that when the parameter t = 0, the genotype is equivalent to the source genotype, while when t = 1, the genotype match the target. Between, the genotype is a proportional mix of both genotypes. Important here: making a simply melt of the different nodes, but when apply the operators, the melt is visualized as a transformation of forms in the image, and not just as an interpolation of colors.

52

Image transitions
Source genotype Target genotype New genotype

The blue nodes are common to both source and target genotypes, while the red and green nodes are different. The gray nodes are inserted to interpolate in time the different nodes. The program inserts this special join node every time the nodes of source and target differs. (1-t)*Y+t*(COS(2*PHI))
53

Image transitions
Source genotype Target genotype New genotype

Source genotype: (+ (X) (* (RAD) (Y))) = X + RAD*Y Target genotype: (+ (X) (* (RAD) (Cos (* (2) (PHY))))) = X + RAD*(Cos(2*PHY)) New genotype: (+ (X) (* (RAD) (+ (* (1-t) (Y)) (* (t) (Cos (* (2) (PHY))))))) = X + RAD* ((1-t)*(Y) + (t)*(Cos(2*PHY)))
54

Image transitions
Source: (triwave (abs (X))) Target: (triwave (&& (PHY) (PHY)))

55

Image transitions
Source:(triwave (abs (RAD))) Target:(triwave (abs (X)))

56

Image transitions
Source: (lerp (/ (gradient (& (PHY) (RAD))) (RAD)) (Y) #(0.545 0.495 0.981)) Target: (lerp (Y) #(0.545 0.495 0.981) (/ (gradient (& (PHY) (RAD))) (RAD)))

57