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

文档信息

资源类别：文库
文档格式：PDF
文档页数：41
文件大小：502.13KB
团购合买：点击进入团购

内容简介

More on Fitness Function Assignment Mutation Constraint implementation in Gas Multiobjective optimization with Gas Tabu search Selection of Optimization algorithms o Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics

刷新页面文档预览

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[SRQHQWSRZHUFDQEHFKDQJHGGXULQJH[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, QRWRROLWWOHPXWDWLRQOHDGVWRDQLPSRYHULVKHG 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

共41页，可试读14页，点击继续阅读 ↓

刷新页面下载完整文档

VIP每日下载上限内不扣除下载券和下载次数；
按次数下载不扣除下载券；
注册用户24小时内重复下载只扣除一次；
顺序：VIP每日次数-->可用次数-->下载券；

点击下载完整版文档（PDF）