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 I REMHFWLYHIXQFWLRQ ) ( ) [ = J I ( ( ) [ ) J WUDQVIRUPDWLRQ ) 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 D IRUPLQLPL]LQJ 2IIVHW EHQVXUHVQRQQHJDWLYHILWQHVVYDOXHV 3RZHUODZVFDOLQJ () () N ) [ = I [ N H[SRQHQW SRZHU 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