Genetic algorithm Darwin's theory of evolution.pptx

Genetic algorithm developed by Goldberg (1960’s) was inspired by Darwin's theory of evolution which states that the survival of an organism is affected by rule "the strongest species that survives".

1. M a the m a t i c a l Model: Gene t i c A l go r i thm By: Elias

2. Definition G e n e t i c a l g o r i t hm d e v e l op e d b y Goldb e r g ( 1960’s) w a s insp i r e d b y D a r w i n ' s t h e o r y of e volu t ion whi c h stat e s that the su r vival of a n o r g a nism is a f f e c ted b y rule " the st r on g e st s p ec ies t h a t surviv e s " . Genetic algorithms (GAS) are numerical optimization algorithms inspired by both natural selection and natural genetics. They are being used to help solve practical problems on a daily basis. A genetic algorithm (or GA) is a search technique used in computing to find true or approximate’ solutions to optimization and search problems.

3. A solu t ion g e n e r a t e d b y g e n e t i c a l g o r i t h m is ca l l e d a c h r omosome, while c ol l ec t i on of c h r omosomes is r e f e r r e d a s a population. A c h r omosome is c ompos e d f r om g e n e s a nd i t s v a lue ca n be e i t h e r nume r i c a l, bin a r y , s y mbo l s o r c h a ra c te r s . Th e se chromosomes will undergo a process called fitness fun c t i on to me a sure the sui t a bi l i t y of solu t ion g e n e r a ted b y GA wi t h p r oblem. S ome c h r omosomes in popula t ion will mate thro u g h p r o ce ss c a l l e d c rossov e r t h us p r odu c i n g n e w c h r omosomes n a med o f fsp r ing. I n a g e n e r a t i on, a f e w c h r omosomes will a lso mu t a t i on in their g e n e . The number of c h r omosomes whi c h will und e rgo c rossov e r a nd mu t a t i on is c ontroll e d b y c rossov e r r a te a nd mu t a t i on r a te v a lue.

4. Key terms individual - Any possible solution Population - Group of all individuals Search Space - All possible solutions to the problem Chromosome - Blueprint for an individual Trait - Possible aspect ( features) of an individual

5. Flowchart for a general genetic algorithm ( Bashi and Banimelhem ,2012)

6. Numerical Example S uppose the r e is e qu a l i t y a + 2 b + 3 c + 4 d = 30, g e n e t i c a l g o rithm used to find the v a lue o f a , b , c , a nd d that s a t i s f y t h e a bove e q u a t i on. the obje c t i ve fun c t i on, f o r th i s p r oblem t h e obj e c t i ve is m i ni m i z ing the v a lue of fun c t i on f ( x ) wh e re f ( x ) = ( ( a + 2 b + 3 c + 4 d ) - 30). T h e re a r e four v a ri a bles in t h e e qu a t i on, n a me l y a , b , c , a nd d , t he v a lu e s of v a ri a bles a , b , c , a nd d a r e in te g e rs b e tw ee n 0 a nd 30.

7. S t e p 1. In itializa t ion t he number o f c h r omos o mes in population a re 6, then we g e n e r a te r a ndom value of g e ne a , b , c , d for 6 c h r omosom e s. Chr o m os o m e [ 1] = [ a ; b ; c ; d ] = [ 12;0 5 ;23 ; 8 ] Chr o m os o m e [ 2] = [ a ; b ; c ; d ] = [ 02;2 1 ;18 ; 3 ] Chr o m os o m e [ 3] = [ a ; b ; c ; d ] = [ 10;0 4 ;13 ; 1 4 ] Chr o m os o m e [ 4] = [ a ; b ; c ; d ] = [ 20;0 1 ;10 ; 6 ] Chr o m os o m e [ 5] = [ a ; b ; c ; d ] = [ 01;0 4 ;13 ; 1 9 ] Chr o m os o m e [ 6] = [ a ; b ; c ; d ] = [ 20;0 5 ;17 ; 1 ]

8. S t e p 2. Eval u a t ion c ompu t e the obje c t i ve fun c t i on v a lue for e a c h c h r omosome p r odu c e d in i n i t ial i z a t i on step: F _o b j [ 1] = Abs ( ( 12 + 2 *05 + 3*23 + 4*08 ) - 3 ) = Abs ( (12 + 10 + 69 + 32 ) - 30) = 93 F _o b j [ 2] = Abs ( (02 + 2 * 21 + 3*18 + 4*03) - 3 ) = Abs ( (02 + 42 + 54 + 12) - 30) = 80 F _o b j [ 3] = Abs ( (10 + 2 * 04 + 3*13 + 4*14) - 3 ) = Abs ( (10 + 08 + 39 + 56) - 30) = 83 F _o b j [ 4] = Abs ( (20 + 2 * 01 + 3*10 + 4*06) - 3 ) = Abs ( (20 + 02 + 30 + 24) - 30) = 46 F _o b j [ 5] = Abs ( (01 + 2 * 04 + 3*13 + 4*19) - 3 ) = Abs ( (01 + 08 + 39 + 76) - 30) = 94 F _o b j [ 6] = Abs ( (20 + 2 * 05 + 3*17 + 4*01) - 3 ) = Abs ( (20 + 10 + 51 + 04) - 30) = 55

9. S t e p 3. S e le c tion The fittest c h r omosom e s h a ve h i g h e r p r ob a bi l it y to be s e le c ted f or t he n e x t g e n e r a t i on. T o a void d iv i de b y z e ro p r ob l e m, t he v a lue of F _o b j is ad d e d b y 1 . . F itnes s [ 1] = 1 / (1 + F _o b j [ 1 ] ) = 1 / 94 = 0.0106 F itnes s [ 2] = 1 / (1 + F _o b j [ 2 ] = 1 / 81 = 0.0123 F itnes s [ 3] = 1 / (1 + F _o b j [ 3 ] ) = 1 / 84 = 0.0119 F itnes s [ 4] = 1 / (1 + F _o b j [ 4 ] ) = 1 / 47 = 0.0213 F itnes s [ 5] = 1 / (1 + F _o b j [ 5 ] ) = 1 / 95 = 0.0105 F itnes s [ 6] = 1 / (1 + F _o b j [ 6 ] ) = 1 / 56 = 0.0179 To t al = 0.0106 + 0.0123 + 0.0119 + 0.0213 + 0.0 1 05 + 0.0179 = 0.0845

10. S t e p 3. S e le c tion The pro ba bi l i t y for e ac h c h r omosome is fo r mu l a t e d b y : P [ i ] = F itness [ i ] / To t al P [ 1] = 0.0106 / 0.0845 = 0.1254 P [ 2] = 0.0123 / 0.0845 = 0.1456 P [ 3] = 0.0119 / 0.0845 = 0.1408 P [ 4] = 0.0213 / 0.0845 = 0.2521 P [ 5] = 0.0105 / 0.0845 = 0.1243 P [ 6] = 0.0179 / 0.0845 = 0.2118 Ch r o mosome 4 that h a s the h i g h e st fitness  

11. S t e p 3. S e le c tion F or the se le c t i on process we use roulette wheel , for that we should compute the cumulative p r ob a bi l i t y v a lues: C [ 1] = 0.1254 C [ 2] = 0.1254 + 0.1456 = 0.2710 C [ 3] = 0.1254 + 0.1456 + 0.1408 = 0.4118 C [ 4] = 0.1254 + 0.1456 + 0.1408 + 0.2521 = 0.6639 C [ 5] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1 2 43 = 0.7882 C [ 6] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1 2 43 + 0.2118 = 1.0

12. r o ulett e - wh ee l H a ving c a lcul a ted the c u mu l a t i ve p r ob a bi l i t y of s e le c t i on p r o ce ss usi n g r o ulett e - wh ee l ca n be don e . The pr o ce ss i s to g e n e r a t e ra ndom nu m b e r R in t he ra n g e - 1 a s fol l ows. R [ 1] = 0.201 R [ 2] = 0.284 R [ 3] = 0.099 R [ 4] = 0.822 R [ 5] = 0.398 R [ 6] = 0.501

13. Step 4. cr ossov e r I f r a ndom num b e r R [ 1] is g r e a t e r than C [ 1] a nd small e r than C [ 2] then s e le c t Chr o m os o m e [ 2] a s a c h r omosome in the n e w popul a t i on f o r n e x t g e n e r a t i o n: N e w Chro m os o m e [ 1] = Chr o m os o m e [ 2] N e w Chro m os o m e [ 2] = Chr o m os o m e [ 3] N e w Chro m os o m e [ 3] = Chr o m os o m e [ 1] N e w Chro m os o m e [ 4] = Chr o m os o m e [ 6] N e w Chro m os o m e [ 5] = Chr o m os o m e [ 3] N e w Chro m os o m e [ 6] = Chr o m os o m e [ 4] Ch r omosomes in t he population t hus b eca me: Chr o m os o m e [ 1] = [ 02; 2 1;18 ; 03] Chr o m os o m e [ 2] = [ 10; 4;13 ; 14] Chr o m os o m e [ 3] = [ 12; 5;23 ; 08] Chr o m os o m e [ 4] = [ 20; 5;17 ; 01] Chr o m os o m e [ 5] = [ 10; 4;13 ; 14] Chr o m os o m e [ 6] = [ 20; 1;10 ; 06]

14. Step 4. cr ossov e r I n th i s e x a mp l e , we u se on e -c ut poin t , i.e. r a ndom l y s e l e c t a posi t ion in the p a r e nt c h r omosome then e x c h a n g i n g su b -c h romosom e . P a r e nt c h r omosome whi c h will mate i s r a ndom l y s e l e c ted a nd t h e number of m a te Ch r o m osom e s is c ontroll e d us i ng cr ossov e r _ r a te ( ρ c ) p a r a met e rs. Ps e ud o - c ode f or t h e c rosso v e r p r o ce ss i s as f ol l ows: b e g in k ← 0; while ( k < p o pu latio n ) do R [ k ] = r a nd o m ( - 1 ); if ( R [ k ] < ρ c ) th e n s e le c t Chr o m os o m e [ k ] a s pa re nt; e nd; k = k + 1; e nd; e nd;

15. Step 4. cr ossov e r S uppose we s e t th a t the c rossov e r r a te is 25%, then Ch r omosome number k will be s e l e c t e d for c rossov e r if r a nd o m g e n e r a ted v a lue for Ch r omosome k b e l o w 0.25. T he p roc e ss i s as f ol l ows: F irst w e g e n e r a t e a r a ndom nu m b e r R a s the number o f po p ulations. R [ 1] = 0.191 R [ 2] = 0.259 R [ 3] = 0.760 R [ 4] = 0.006 R [ 5] = 0.159 R [ 6] = 0.340   F or r a ndom number R a bov e , parents a re Chro m os o m e [ 1 ] , Chromosome [ 4] a nd Chr o m os o m e [ 5] will be sel ec ted f o r c rosso v e r. Chr o m os o m e [ 1] > < Chr o m os o m e [ 4] Chr o m os o m e [ 4] > < Chr o m os o m e [ 5] Chr o m os o m e [ 5] > < Chr o m os o m e [ 1]  

16. Step 4. cr ossov e r A f ter c h r omosome s e l e c t i on, the n e xt p r o ce ss is d e te r m i ning the posit i on of the c rossov e r poin t . This is done b y g e n e r a t i n g r a ndom numbe r s b e tw ee n 1 to (l e n g th of Ch r omosome – 1 ) . I n th i s ca s e , g e n e r a ted r a ndom numbe r s should be b e tw ee n 1 a nd 3. A f ter we g e t the c rossov e r poin t , p a r e nts Ch r omosome will be c ut a t c rossov e r point a n d i t s g e ns will be in t e r c h a n g e d. F or e x a mp l e we g e n e r a ted 3 r a nd o m nu m b e r a nd we g e t : C [ 1] = 1 C [ 2] = 1 C [ 3] = 2

17. Step 4. cr ossov e r Th e n for fi r st c rossov e r, s ec ond c rosso v e r a nd t hird c rossov e r, p a r e nt’s g e ns will be c ut a t g e n num b e r 1, g e n num b e r 1 a nd g e n n umber 3 re spe c t i v e l y , e . g . Chr o m os o m e [ 1] = Chro m os o me [ 1] > < Chr o m o som e [ 4] = [ 02;21 ; 18;0 3 ] >< [ 20;05 ; 17;01] = [ 02;05 ; 17;0 1 ] Chr o m os o m e [ 4] = Chro m os o me [ 4] > < Chr o m o som e [ 5] = [ 20;05 ; 17;0 1 ] > < [ 10;04 ; 13;14] = [ 20;04 ; 13;1 4 ] Chr o m os o m e [ 5] = Chro m os o me [ 5] > < Chr o m o som e [ 1] = [ 10;04 ; 13;1 4 ] > < [ 02;21 ; 18;03] = [ 10;04 ; 18;0 3 ]   Thus, Ch r om o some popul a t i on a ft e r e x p e ri e n c i n g a c rossov e r p ro c e ss: Chr o m os o m e [ 1] = [ 02; 5;17 ; 01] Chr o m os o m e [ 2] = [ 10; 4;13 ; 14] Chr o m os o m e [ 3] = [ 12; 5;23 ; 08] Chr o m os o m e [ 4] = [ 20; 4;13 ; 14] Chr o m os o m e [ 5] = [ 10; 4;18 ; 03] Chr o m os o m e [ 6] = [ 20; 1;10 ; 06]  

18. S t e p 5. M u ta t ion Mut a t i on p r o ce ss is done b y r e pl a c ing the g e n a t r a ndom posit i on with a n e w v a lue. F irst we must ca lcul a te the to t a l len g th of g e n in the population. to t al_gen = nu m b er _o f _g e n _i n _Chr o m os o m e * n u m b e r of p o pu lati o ns = 4 * 6 = 24   Mut a t i on p r o ce ss is done b y g e n e r a t i n g a r a ndom in t e g e r b e tw e e n 1 a nd t otal_ g e n (1 to 24). I f g e n e r a ted r a ndom n u mber is small e r than m utation_r a te ( ρm ) v a ri a b l e then ma r k e d the posit i on of g e n in c h r omosomes. S uppose we d e fine ρm 10%, it is e x p ec ted that 10% (0.1) of to t a l_ g e n in t he populat i on that will be mu t a ted: number of mutations = 0 . 1 * 24 = 2.4 ≈ 2

19. S t e p 5. M u ta t ion S uppose g e n e r a t i on of r a ndom number y i e ld 12 a nd 18 then the c h r omosome whi c h h a ve mu t a t i on a re Ch r omosome number 3 g e n num b e r 4 a nd Ch r omosome 5 g e n num b e r 2. The v a lue of mutated gene at mutation point is replaced by random number between 0- 30. S uppose g e n e r a t e d r a nd o m number a re 2 a nd 5 t h e n Ch r omosome c omposi t ion a ft e r mu t a t i on a r e : Chr o m os o m e [ 1] = [ 02; 5;17 ; 01] Chr o m os o m e [ 2] = [ 10; 4;13 ; 14] Chr o m os o m e [ 3] = [ 12; 5;23 ; 02 ] Chr o m os o m e [ 4] = [ 20; 4;13 ; 14] Chr o m os o m e [ 5] = [ 10 ; 5 ;18 ; 03] Chr o m os o m e [ 6] = [ 20; 1;10 ; 06]

20. S t e p 5. M u ta t ion e v a luate the obj ec t i ve fu n c t i on a ft e r o n e g e n e r a t i o n: chr o m os o m e [ 1] = [ 02; 5;17 ; 01] F _o b j [ 1] = Abs ( ( 02 + 2 *05 + 3*17 + 4*01 ) - 3 ) = 37 Chr o m os o m e [ 2] = [ 10; 4;13 ; 14] F _o b j [ 2] = Abs ( ( 10 + 2 *04 + 3*13 + 4*14 ) - 3 ) = 77 Chr o m os o m e [ 3] = [ 12; 5;23 ; 02] F _o b j [ 3] = Abs ( ( 12 + 2 *05 + 3*23 + 4*02 ) - 3 ) = 47 Chr o m os o m e [ 4] = [ 20; 4;13 ; 14] F _o b j [ 4] = Abs ( ( 20 + 2 *04 + 3*13 + 4*14 ) - 3 ) = 93 Chr o m os o m e [ 5] = [ 10; 5;18 ; 03] F _o b j [ 5] = Abs ( ( 10 + 2 *05 + 3*18 + 4*03 ) - 3 ) = 56 Chr o m os o m e [ 6] = [ 20; 1;10 ; 06] F _o b j [ 6] = Abs ( ( 20 + 2 *01 + 3*10 + 4*06 ) - 3 ) = 46

21. S t e p 5. M u ta t ion F rom the e v a luation o f n e w Ch r omosome, w e c a n s e e that the obje c t i ve fu n c t i on is d ec r ea si n g , th i s means that we have better Chromosome or solution compared with previous Ch r omosome g e n e r a t i on. N e w Chromosom e s for n e x t i te ra t i on a r e : Chr o m os o m e [ 1] = [ 02; 5;17 ; 01] Chr o m os o m e [ 2] = [ 10; 4;13 ; 14] Chr o m os o m e [ 3] = [ 12; 5;23 ; 02] Chr o m os o m e [ 4] = [ 20; 4;13 ; 14] Chr o m os o m e [ 5] = [ 10; 5;18 ; 03] Chr o m os o m e [ 6] = [ 20; 1;10 ; 06]     Th e se n e w Ch r omoso m e s will und e r g o the s a me p r o ce ss a s the p re v ious g e n e r a t i on of Ch r omosomes such a s e v a luation, s e le c t i on, c ros s ov e r a nd mu t a t i on a nd a t the e nd it p r odu c es n e w g e n e r a t i on of Ch r omosome for the n e x t i t e r a t i on.

22. S t e p 5. M u ta t ion This p r o ce ss will be r e p e a ted unt i l a pre d e t e rmin e d number o f g e n e r a t i ons. F o r th i s e x a mp l e , a ft e r runni n g 5 g e n e r a t i ons, b e st c h r omosome is obt a ined: Ch r omosome = [ 07; 05; 03; 01] This m ea ns th a t: a = 7, b = 5, c = 3, d = 1 I f we u s e the numb e r in t he pro b lem e qu a t i o n : a + 2 b + 3 c + 4 d = 30 7 + ( 2 * 5) + (3 * 3 ) + (4 * 1) = 30 W e ca n s e e that the v a l u e of v a ri a ble a , b , c a nd d g e n e r a ted b y g e n e t i c a l g o r i t hm ca n s a t i s f y that e qu a l i t y .

23. Design of energy Efficient Buildings The genetic algorithm allows a designer to select from a range of buildings, all of which have a predicted energy performance within, say, five percent of the achievable minimum, the design which best suits his/her other requirements. It relieves the designer of the need to work through the consequences of choosing individual features and of checking their compatibility with the rest of the building system. The energy performance of a building is determined by its response as a complete system to the external environment and the internal environmental demands of the occupants. The system response, in turn, depends upon the combination of individual attributes that have been assembled to produce the building.

24. In the work of Migowsky [MIG95], and subsequent extensions, EXCALIBUR is combined with a genetic algorithm to try and generate high-quality designs with architectural appeal. The population, P, is manipulated as follows: 1. create initial, random, population of attributes 2. reduce physical attributes to model parameters 3. calculate annual energy use of heating and cooling systems, 4. use GA to create new designs by recombination and mutation using as the selection factor; 5. repeat from 2 until termination criterion is met; and then 6. filter designs considering architectural appeal.

25. Al Bahar Towers The Abu Dhabi Investment Council’s Headquarters was the 150 meters high twin towers are located in Abu Dhabi, United Arab Emirates. Among the many performance-driven design features, the building stands out with its fluid form, honeycomb-inspired structure, and its automated dynamic solar screen. This system kinetically responds to the sun’s movement and offers the building its distinct identity. The country’s architectural heritage is comprised of adobe buildings from the 19th century. Buildings such as the Al-Jahili Fort in Al-Ain have protective external walls surrounding an internal vegetated courtyard with watchtowers at the corners. each unit comprises a series of stretched panels can prevent that direct sunlight strike the façade and limit direct solar gain to a maximum of 400 watts per linear meter.

26. Design Process

27. The target is to admit natural diffused light into the building and maintain a useful daylight threshold ranging from 250 to 2000 Lux throughout daily working hours (09:00 am to 17:00 pm). As soon as light sensors located at the perimeter of the ceiling near the curtain-wall read lower than 250 Lux, dimmers linked between the sensors and artificial lighting are activated to maintain the required comfort threshold.