麻省理工学院：《Multidisciplinary System》Lecture 1 1 Olivier de Weck

M 16888 E077 Multidisciplinary System Design Optimization Genetic Algorithms() Tabu search 10 March 2004 Lecture 11 Olivier de weck C Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

0XOWLGLVFLSOLQDU\6\VWHP'HVLJQ2SWLPL]DWLRQ *HQHWLF$OJRULWKPV,, 7DEX6HDUFK 0DUFK /HFWXUH 2OLYLHUGH:HFN  ‹0DVVDFKXVHWWV,QVWLWXWHRI7HFKQRORJ\3URIGH:HFNDQG3URI:LOOFR[ (QJLQHHULQJ6\VWHPV'LYLVLRQDQG'HSWRI$HURQDXWLFVDQG$VWURQDXWLFV

M Today' s Topics 16888 E077 More on Fitness Function assignment Mutation Constraint implementation in Gas Multiobjective optimization with gas Tabu search Selection of Optimization algorithms C Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

7RGD\¶V7RSLFV ‡ 0RUHRQ)LWQHVV)XQFWLRQ$VVLJQPHQW ‡ 0XWDWLRQ ‡ &RQVWUDLQWLPSOHPHQWDWLRQLQ*$V ‡ 0XOWLREMHFWLYHRSWLPL]DWLRQZLWK*$V ‡ 7DEX6HDUFK ‡ 6HOHFWLRQRI2SWLPL]DWLRQ$OJRULWKPV  ‹0DVVDFKXVHWWV,QVWLWXWHRI7HFKQRORJ\3URIGH:HFNDQG3URI:LOOFR[ (QJLQHHULQJ6\VWHPV'LYLVLRQDQG'HSWRI$HURQDXWLFVDQG$VWURQDXWLFV

M Fitness Function Mapping () 16888 E077 Objective Function measures how individuals perform in the problem domain Raw measure of fitness usually only used as intermediate stage in determining relative performance of individuals in a ga Transform objective function value into a measure of relative fitness f: objective function g: transformation F(x)=g((x) F: relative Fitness =0) C Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

)LWQHVV)XQFWLRQ0DSSLQJ, ‡ 2EMHFWLYH)XQFWLRQPHDVXUHVKRZLQGLYLGXDOV SHUIRUPLQWKHSUREOHPGRPDLQ ‡ 5DZPHDVXUHRIILWQHVVXVXDOO\RQO\XVHGDV LQWHUPHGLDWHVWDJHLQGHWHUPLQLQJUHODWLYH SHUIRUPDQFHRILQGLYLGXDOVLQD*$ 7UDQVIRUPREMHFWLYHIXQFWLRQYDOXHLQWRDPHDVXUH RIUHODWLYHILWQHVV IREMHFWLYHIXQFWLRQ ) ( ) [ = J I ( ( ) [ ) JWUDQVIRUPDWLRQ )UHODWLYH)LWQHVV!   ‹0DVVDFKXVHWWV,QVWLWXWHRI7HFKQRORJ\3URIGH:HFNDQG3URI:LOOFR[ (QJLQHHULQJ6\VWHPV'LYLVLRQDQG'HSWRI$HURQDXWLFVDQG$VWURQDXWLFV

esd Fitness Function Mapping( 16888 ESD.77 f Mapping always necessary for minimization (smaller objective value= higher fitness Often fitness function value corresponds to the number of offspring which an individual will likely produce E.g. Proportional fitness assignment F() Fitness of i-th individual ∑f(x) individuals raw performance relative to the whole population Nind Population size x Phenotypic value of i C Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

)LWQHVV)XQFWLRQ0DSSLQJ,, I ) 6 0DSSLQJDOZD\VQHFHVVDU\IRUPLQLPL]DWLRQ VPDOOHUREMHFWLYHYDOXH KLJKHUILWQHVV 2IWHQILWQHVVIXQFWLRQYDOXHFRUUHVSRQGVWRWKHQXPEHU RIRIIVSULQJZKLFKDQLQGLYLGXDOZLOOOLNHO\SURGXFH (J3URSRUWLRQDOILWQHVVDVVLJQPHQW L ( ) = ( ) ) [L 1LQG I [ )LWQHVVRILWKLQGLYLGXDO ¦ I ( ) [L LQGLYLGXDOVUDZSHUIRUPDQFHUHODWLYH L= WRWKHZKROHSRSXODWLRQ 1LQG 3RSXODWLRQVL]H [L 3KHQRW\SLFYDOXHRI³L´  ‹0DVVDFKXVHWWV,QVWLWXWHRI7HFKQRORJ\3URIGH:HFNDQG3URI:LOOFR[ (QJLQHHULQJ6\VWHPV'LYLVLRQDQG'HSWRI$HURQDXWLFVDQG$VWURQDXWLFV

Mlesd Fitness Function Mapping(l) 16888 ESD.77 How to account for negative objective function values Linear transformation with offset: F(x)=af (x)+b Scale factor: a>0 for maximizing, a<0 for minimizing Offset b ensures non-negative fitness values Power law scaling: F(x)=f( k: exponent(power) can be changed during execution Tuning knob:“SP”- selective pressure degree of bias towardstowards fittest xX X;=position of i-th (x)=2-SP+2(SP-1) individual in ordered ind population C Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

)LWQHVV)XQFWLRQ0DSSLQJ,,, +RZWRDFFRXQWIRUQHJDWLYHREMHFWLYHIXQFWLRQYDOXHV" /LQHDUWUDQVIRUPDWLRQZLWKRIIVHW )[ D () () = + I[ E 6FDOHIDFWRU D!IRUPD[LPL]LQJ DIRUPLQLPL]LQJ 2IIVHW EHQVXUHVQRQQHJDWLYHILWQHVVYDOXHV 3RZHUODZVFDOLQJ () () N ) [ = I [ NH[SRQHQWSRZHUFDQEHFKDQJHGGXULQJH[HFXWLRQ 7XQLQJ.QRE³63´VHOHFWLYHSUHVVXUH GHJUHHRIELDVWRZDUGVWRZDUGVILWWHVW [ L SRVLWLRQRILWK L ) [( ) = − 63 +  (63 −  ) 1 [ LQG − −   L LQGLYLGXDOLQRUGHUHG SRSXODWLRQ  ‹0DVVDFKXVHWWV,QVWLWXWHRI7HFKQRORJ\3URIGH:HFNDQG3URI:LOOFR[ (QJLQHHULQJ6\VWHPV'LYLVLRQDQG'HSWRI$HURQDXWLFVDQG$VWURQDXWLFV

M Mutation() 16888 E077 (no ) too little mutation leads to an impoverished genetic pool with increasing number of generations dilemma Too much mutation decreases convergence rate and undermines fitness-based selection bias What is mutation?. a genetic operator Modifies chromosomes to restore diversity Permit random changes in a member of a population Examples with probability 1 20 randomly flip a single bit of a solution from o to 1 or 1 to o probability of mutation often called"mutation rate expressing the probability Pm that a bit is changed C Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

0XWDWLRQ, QRWRROLWWOHPXWDWLRQOHDGVWRDQLPSRYHULVKHG JHQHWLFSRROZLWKLQFUHDVLQJQXPEHURIJHQHUDWLRQV GLOHPPD 7RRPXFKPXWDWLRQGHFUHDVHVFRQYHUJHQFHUDWH DQGXQGHUPLQHVILWQHVVEDVHGVHOHFWLRQELDV :KDWLVPXWDWLRQ"«DJHQHWLFRSHUDWRU ‡0RGLILHVFKURPRVRPHVWRUHVWRUHGLYHUVLW\ ‡3HUPLWUDQGRPFKDQJHVLQDPHPEHURIDSRSXODWLRQ ([DPSOHV ZLWKSUREDELOLW\UDQGRPO\IOLSDVLQJOHELWRI DVROXWLRQIURPWRRUWR SUREDELOLW\RIPXWDWLRQRIWHQFDOOHG³PXWDWLRQUDWH´ H[SUHVVLQJWKHSUREDELOLW\3PWKDWDELWLVFKDQJHG  ‹0DVVDFKXVHWWV,QVWLWXWHRI7HFKQRORJ\3URIGH:HFNDQG3URI:LOOFR[ (QJLQHHULQJ6\VWHPV'LYLVLRQDQG'HSWRI$HURQDXWLFVDQG$VWURQDXWLFV

M Example with Mutation 16888 ESD.77 Improved population fitness with 1% mutation rate Original gen 5th gen 10th gen 10011 11011 11111 01000 10111 11111 00001 11111 11011 00000 01110 11111 11011 11111 Avg Fitness Avg Fitness Avg. Fitness 2.6 4.8 49 C Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

([DPSOHZLWK0XWDWLRQ ,PSURYHGSRSXODWLRQILWQHVVZLWKPXWDWLRQUDWH 2ULJLQDOJHQ WKJHQ WKJHQ          « « «       $YJ)LWQHVV $YJ)LWQHVV $YJ)LWQHVV     ‹0DVVDFKXVHWWV,QVWLWXWHRI7HFKQRORJ\3URIGH:HFNDQG3URI:LOOFR[ (QJLQHHULQJ6\VWHPV'LYLVLRQDQG'HSWRI$HURQDXWLFVDQG$VWURQDXWLFV

M Example without Mutation 16888 E077 Stagnant population with 0% mutation rate Original gen 5th gen 10th gen No“1 1001 11011 11011 01000 10011 11011 00001 11011 11011 Cal 00000 01010 1101 Never 110h1 11011 1 Achieve 11111 Avg Fitness Avg Fitness Avg. Fitness 2.6 3.2 4.0 C Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

([DPSOHZLWKRXW0XWDWLRQ 6WDJQDQWSRSXODWLRQZLWKPXWDWLRQUDWH 2ULJLQDOJHQ WKJHQ WKJHQ 1R³´          « « « &DQ    1HYHU    $FKLHYH  $YJ)LWQHVV $YJ)LWQHVV $YJ)LWQHVV     ‹0DVVDFKXVHWWV,QVWLWXWHRI7HFKQRORJ\3URIGH:HFNDQG3URI:LOOFR[ (QJLQHHULQJ6\VWHPV'LYLVLRQDQG'HSWRI$HURQDXWLFVDQG$VWURQDXWLFV

Mutation( 16888 ESD.77 EXample: eneration: 20 Before mutation 010111000 After mutation 010101000 Mutation rate can be variable usually gradually decreasing with increasing number of generations) 21 Mutation rate is an important tuning knob"for a GA Generation C Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

0XWDWLRQ,, ([DPSOH %HIRUHPXWDWLRQ $IWHUPXWDWLRQ ‡ 0XWDWLRQUDWHFDQEH YDULDEOHXVXDOO\JUDGXDOO\ GHFUHDVLQJZLWKLQFUHDVLQJ QXPEHURIJHQHUDWLRQV ‡ 0XWDWLRQUDWHLVDQLPSRUWDQW 0XWDWLRQUDWH  ³WXQLQJNQRE´IRUD*$ «WRRKLJK  ‹0DVVDFKXVHWWV,QVWLWXWHRI7HFKQRORJ\3URIGH:HFNDQG3URI:LOOFR[ (QJLQHHULQJ6\VWHPV'LYLVLRQDQG'HSWRI$HURQDXWLFVDQG$VWURQDXWLFV

GA Convergence 16888 E077 global ypIcal Results optimum Average (unknown) Fitness Converged too fast(mutation rate too small? generation Average performance of individuals in a population is expected to increase, as good individuals are preserved and bred and less fit individuals die out C Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

*$&RQYHUJHQFH JOREDO 7\SLFDO5HVXOWV RSWLPXP JHQHUDWLRQ XQNQRZQ $YHUDJH )LWQHVV &RQYHUJHGWRR IDVWPXWDWLRQUDWH WRRVPDOO" $YHUDJHSHUIRUPDQFHRILQGLYLGXDOVLQD SRSXODWLRQLVH[SHFWHGWRLQFUHDVHDVJRRGLQGLYLGXDOV DUHSUHVHUYHGDQGEUHGDQGOHVVILWLQGLYLGXDOVGLHRXW  ‹0DVVDFKXVHWWV,QVWLWXWHRI7HFKQRORJ\3URIGH:HFNDQG3URI:LOOFR[ (QJLQHHULQJ6\VWHPV'LYLVLRQDQG'HSWRI$HURQDXWLFVDQG$VWURQDXWLFV