Filetype PDF | Posted on 19 Aug 2022 | 4 years ago
Authentication
digital resources
202x Filetype PDF File size 0.31 MB Source: research.utwente.nl
&RQWH[W$ZDUH7DVN$VVLJQPHQWLQ8ELTXLWRXV&RPSXWLQJ
(QYLURQPHQW$*HQHWLF$OJRULWKP%DVHG$SSURDFK
3UDYLQ3DZDU+DLOLDQJ0HL,QJ:LG\D%HUW-DQYDQ%HLMQXP$DUWYDQ+DOWHUHQ
DGGLWLRQDOO\ UHTXLUHV WKH UHVRXUFHV ZKLFK DUH FDSDEOH RI
$EVWUDFW²:LWKWKHDGYHQWRIXELTXLWRXVFRPSXWLQJDXVHU
LV VXUURXQGHG E\ D YDULHW\ RI GHYLFHV LQFOXGLQJ WLQ\ VHQVRU H[HFXWLQJWKLVWDVN7KHUHIRUHWKHUHVHDUFKLQWKLVDUHDKDV
QRGHV KDQGKHOG PRELOH GHYLFHV DQG SRZHUIXO FRPSXWHUV DV IRFXVHG RQ SHUIRUPLQJ WKH RSWLPDO DVVLJQPHQW RI WKH
ZHOO DV GLYHUVH FRPPXQLFDWLRQ QHWZRUNV ,Q WKLV QHWZRUNHG SURFHVVLQJWDVNVRQWRWKHDYDLODEOHUHVRXUFHVVXFKWKDWWKH
VRFLHW\ WKH UROH RI D KXPDQ EHLQJLVHYROYLQJIURPWKHGDWD GDWD WKURXJKSXW LV PD[LPL]HG >@ RU WKH HQGWRHQG
FRQVXPHU WR WKH GDWD SURGXFHU ,Q WKHVH FKDQJLQJ SURFHVVLQJWLPHLVPLQLPL]HG>@
FLUFXPVWDQFHV SLSHOLQHG SURFHVVLQJ ILQGV DSSOLFDWLRQV ZKHUH 7KH PRUH JHQHUDO SUREOHP RI PXOWLSURFHVVRU VFKHGXOLQJ
WKH GDWD REWDLQHG IURP WKH KXPDQ SURGXFHU QHHGV WR EH
SURFHVVHGDQGLQWHUSUHWHGLQUHDOWLPH)RUH[DPSOHLQDQ0 ZKLFKLQYROYHVREWDLQLQJDVFKHGXOHIRUDJHQHUDOWDVNJUDSK
+HDOWKV\VWHPWKHYLWDOVLJQV DFTXLUHG IURP WKH SDWLHQW DUH WREHH[HFXWHGRQDPXOWLSURFHVVRUV\VWHPWRPLQLPL]HWKH
SURFHVVHGLQWKHSLSHOLQHGIDVKLRQ VFKHGXOHOHQJWKLV 13KDUG>@6HYHUDOVXEFODVVHVRIWKH
7KLV SDSHU SURSRVHV D JHQHWLF DOJRULWKP *$ EDVHG SUREOHPDUHNQRZQWREHLQ3DQGVHYHUDODOJRULWKPVWKDW
DSSURDFKIRUWKHRSWLPDODVVLJQPHQWRISLSHOLQHGSURFHVVLQJ VROYHWKHVHLQSRO\QRPLDOWLPHKDYHEHHQUHSRUWHG>@
WDVNVRQWRDFKDLQRIQHWZRUNHGGHYLFHVWKDWPLQLPL]HVWRWDO
HQGWRHQGSURFHVVLQJGHOD\FRQVLGHULQJNQRZOHGJHDERXWWKH $ 7DVN$VVLJQPHQWLQWKH0+HDOWK'RPDLQ
FRPPXQLFDWLRQ DQG FRPSXWDWLRQ UHVRXUFHV DV WKH FRQWH[W ,QWRGD\¶VZRUOGRIXELTXLWRXVFRPSXWLQJLQWHUPVRIWKH
LQIRUPDWLRQ $OWKRXJK VRPH H[LVWLQJ JUDSKEDVHG DOJRULWKPV GDWDSURFHVVLQJUHVRXUFHVDKXPDQXVHULVVXUURXQGHGE\D
FDQVROYHWKLVSUREOHPLQSRO\QRPLDOWLPHZHH[SHFWWKDW*$
FDQ WDNH OHVV FRPSXWDWLRQDO WLPH DQG UHTXLUHV OHVV PHPRU\ YDULHW\RIGHYLFHVUDQJLQJIURPWKHWLQ\VHQVRUVKDQGKHOG
ZKLOH SURYLGLQJ D UHDVRQDEO\ JRRG DVVLJQPHQW :H FRPSDUH PRELOHJDGJHWVDQGSRZHUIXOFRPSXWHUV HDFKFRQVLVWLQJRI
WKH SHUIRUPDQFH RI *$ DSSURDFK ZLWK WKH JUDSKEDVHG LWVRZQSURFHVVLQJSRZHUVRIWZDUHDQGKDUGZDUHSODWIRUPV
DSSURDFKHV,WLVREVHUYHGWKDWZKHQWKHQXPEHURIGHYLFHVDQG 6LPLODUO\ WKH FRPPXQLFDWLRQ WHFKQRORJ\ LQFOXGHV VKRUW
WKH QXPEHU RI SURFHVVLQJ WDVNV DUH ODUJH WKH *$ DSSURDFK UDQJHORZEDQGZLGWKQHWZRUNV HJ%OXHWRRWK ORQJUDQJH
SHUIRUPV EHWWHU LQ WHUPV RI WKH VDWLVIDFWRU\ TXDOLW\ RI WKH ORZEDQGZLGWKQHWZRUNV HJ*356 DVZHOODVVKRUWUDQJH
REWDLQHG VXERSWLPDO VROXWLRQ FRQVLGHULQJ WKH DGYDQWDJH RI
UHGXFHGFRPSXWDWLRQDOWLPH KLJK EDQGZLGWK QHWZRUNV HJ :/$1 DQG 8:%
FRH[LVWLQJZLWKWKHFRQYHQWLRQDOZLUHOLQHQHWZRUNV2ZLQJ
, ,1752'8&7,21 WR WKHVH DGYDQFHV DQG WKH QHHG WR SURYLGH XVHUFHQWULF
1 D VHTXHQWLDO GDWD SURFHVVLQJ V\VWHP D SLSHOLQHG DSSOLFDWLRQVWKHUROHRIDKXPDQEHLQJLVDOVRHYROYLQJIURP
, WKHGDWDFRQVXPHU HJGRZQORDGLQJULQJWRQHVDQGQHZV
SURFHVVLQJ MRE FRQVLVWV RI D FKDLQ RI SURFHVVLQJ WDVNV
ZKHUHHYHU\SURFHVVLQJWDVNH[FHSWWKHILUVWRQH WDNHVDV WR WKH GDWD SURGXFHU HJ XVHU FRQWH[W VXFK DV DJHQGD
LQSXW WKH RXWSXW RI WKH SUHYLRXV WDVN $ QXPEHU RI FXUUHQW DFWLYLW\ $ UHSUHVHQWDWLYH H[DPSOH RI WKHVH
DSSOLFDWLRQV ZKLFK LQYROYH SLSHOLQHG SURFHVVLQJ H[LVW E\ FKDQJLQJWUHQGVLVWKHUHPRWHSDWLHQWWHOHPRQLWRULQJV\VWHP
DSSO\LQJDVHULHVRIVLJQDOSURFHVVLQJWDVNVHJWRFDSWXUH LQ WKH 0RELOH KHDOWKFDUH 0KHDOWK GRPDLQ 7KH
VWRUDJHPDQLSXODWHDQGWUDQVPLWPXOWLPHGLDREMHFWVLQWKH DSSOLFDWLRQVLQWKH0+HDOWKGRPDLQDUHUHFHLYLQJPRUHDQG
PHGLD SURFHVVLQJ V\VWHP >@ DQG WKH IORZVKRS PRUHDWWHQWLRQVGXHWRLWVDELOLW\WRUHVKDSHWKHKHDOWKFDUH
SURGXFWLRQ SODQW DPRQJ RWKHUV $ FKDUDFWHULVWLF RI WKH GHOLYHU\ SURFHVV WR VDWLVI\ WRGD\¶V VRFLHW\ GHPDQGV OLNH
SLSHOLQHGSURFHVVLQJV\VWHPLVWKDWHYHU\WDVNLQYROYHGLQ SDWLHQW VHOIPDQDJHPHQW FRQWLQXRXV DQG DQ\ZKHUH WHOH
WKH SURFHVVLQJ FKDLQ QHHGV FHUWDLQ DPRXQW RI WLPH DQG PRQLWRULQJDQGWHOHWUHDWPHQW> @
7KHSXUSRVHRIWKHUHPRWHSDWLHQWWHOHPRQLWRULQJV\VWHP
0DQXVFULSWUHFHLYHG0DUFK7KLVZRUNLVSDUWRIWKH)UHHEDQG LV WR JDWKHU WKH SDWLHQW¶V ELRVLJQDOV HJ (&* R[\JHQ
$:$5(1(663URMHFW)UHHEDQGLVVSRQVRUHGE\WKH'XWFKJRYHUQPHQW VDWXUDWLRQOHYHOKHDUWUDWH FROOHFWHGIURPPHGLFDOVHQVRUV
XQGHUFRQWUDFW%6,. KWWS DZDUHQHVVIUHHEDQGQO DWWDFKHGWRWKHSDWLHQW¶VERG\SURFHVVDQGWUDQVIHUWKLVGDWD
3UDYLQ3DZDU+DLOLDQJ0HL,QJ:LG\DDQG%HUW-DQYDQ%HLMQXPDUH LQDQHDUUHDOWLPHIDVKLRQWRWKHVHUYHULQKHDOWKFDUHFHQWHUV
ZLWKWKH$UFKLWHFWXUHVDQG6HUYLFHVRIWKH1HWZRUNHG$SSOLFDWLRQV*URXS
'HSDUWPHQWRI(OHFWULFDO(QJLQHHULQJ0DWKHPDWLFVDQG&RPSXWHU6FLHQFH ORFDWHGLQWKHIL[HGQHWZRUNYLDVHYHUDOFRPSXWLQJGHYLFHV
8QLYHUVLW\RI7ZHQWH$((QVFKHGH7KH1HWKHUODQGV LQWKHVLJQDOGHOLYHU\SDWK$ELRVLJQDOSURFHVVLQJMRERIWHQ
3K ±± )D[ ±± FRQVLVWV RI FDVFDGHG SURFHVVLQJ WDVNV ZKLFK KDYH WR EH
(PDLO ^33DZDU+0HL,:LG\D%-YDQ%HLMQXP`#XWZHQWHQO
$DUWYDQ+DOWHUHQLVZLWK3KLOLSV5HVHDUFK(LQGKRYHQ7KH1HWKHUODQGV FRQILJXUHGRQWRWKHGHYLFHVLQWKHVLJQDOGHOLYHU\SDWK7KLV
(PDLO $DUWYDQ+DOWHUHQ#SKLOLSVFRP MRE IDOOV LQ WKH FDWHJRU\ RI WKH SLSHOLQHG MREV PHQWLRQHG
HDUOLHULQWKLVVHFWLRQ
2695
c
1-4244-1340-0/07$25.002007IEEE
0HGLFDO SURWRFROV DQG SUDFWLFHV SUHVFULEH VWULFW :H SHUIRUP D VHULHV RI H[SHULPHQWV XVLQJ JHQHWLF
UHTXLUHPHQWV RQ WKH SURFHVVLQJ TXDOLW\ RI WKH ELRVLJQDO DOJRULWKP WR FRPSDUH LWV SHUIRUPDQFH ZLWK %RNKDUL DQG
GDWD ZKLFK QHFHVVLWDWHV WKH QHHG RI DOORFDWLQJ WKH 0HL¶VDOJRULWKPVIRUWKHVLPLODUSUREOHPV$OWKRXJKERWKRI
LQWHUPHGLDWH SURFHVVLQJ WDVNV RQ WKH GHYLFHV SURYLGLQJ WKHP VROYH WKH SLSHOLQHG WDVN DVVLJQPHQW SUREOHP LQ
VXLWDEOH FRPSXWDWLRQ UHVRXUFHV )XUWKHUPRUH GXULQJ WKH SRO\QRPLDO WLPH ZH H[SHFW WKDW *$ WDNHV OHVV
HPHUJHQF\FRQGLWLRQVWKHFDUHJLYHURUSDUDPHGLFVQHHGWR FRPSXWDWLRQDO WLPH DQG UHTXLUHV OHVV PHPRU\ ZKLOH
EHLQIRUPHGDERXWWKHFULWLFDOFRQGLWLRQRIDSDWLHQWZLWKLQD SURYLGLQJ D UHDVRQDEO\ JRRG VROXWLRQ ,Q WKLV SDSHU ZH
VSHFLILHG WLPH WR UHDFW ZKLFK QHFHVVLWDWHV WKH QHHG RI HYDOXDWHWKHSHUIRUPDQFHRI*$WRYHULI\RXUDVVXPSWLRQ
PLQLPL]LQJ WKH ELRVLJQDO SURFHVVLQJ WLPH +HQFH D ZLWKWKHIROORZLQJWZRDVSHFWV WKHFRPSXWDWLRQWLPHDQG
FKDOOHQJHLQWKHUHPRWHSDWLHQWWHOHPRQLWRULQJV\VWHPLVWR TXDOLW\RIWKHREWDLQHGVXERSWLPDOVROXWLRQDVFRPSDUHG
RSWLPDOO\DVVLJQWKHELRVLJQDOSURFHVVLQJWDVNVWRDYDLODEOH WRWKHRSWLPDOVROXWLRQ:HDOVRVWXG\WKHHIIHFWRIWKHLQLWLDO
GHYLFHV VXFK WKDW WKH HQGWRHQG SURFHVVLQJ GHOD\ LV SRSXODWLRQJHQHUDWLRQVWUDWHJ\DQGWKHSRSXODWLRQVL]HRQWKH
PLQLPL]HG DQG VXEMHFW WR WKH FRQVWUDLQWV RQ WKH TXDOLW\RIWKHREWDLQHGVXERSWLPDOVROXWLRQ
FRPPXQLFDWLRQDQGFRPSXWDWLRQUHVRXUFHV:HUHIHUWRWKH ' 3DSHU2XWOLQH
LQIRUPDWLRQ SURYLGLQJ WKH NQRZOHGJH DERXW WKH 7KLVSDSHULVRUJDQL]HGDVIROORZV 6HFWLRQGHVFULEHVD
FRPPXQLFDWLRQ DQG FRPSXWDWLRQ UHVRXUFHV DV WKH FRQWH[W FRQWH[WDZDUH0KHDOWKDSSOLFDWLRQVFHQDULRIRUSUHGLFWLQJ
LQIRUPDWLRQ$FRQWH[WDZDUHV\VWHPDGDSWVDFFRUGLQJWRWKH HSLOHSWLF VHL]XUHV IURP VHQVHG ELRVLJQDOV 6HFWLRQ
FRQWH[W LQIRUPDWLRQ HJ XVHU FRQWH[W VHUYLFH FRQWH[W DQG IRUPXODWHV WKH PLQLPL]DWLRQ SUREOHP 6HFWLRQ EULHIO\
FRPPXQLFDWLRQ DQG FRPSXWDWLRQ HQYLURQPHQW FRQWH[W DV GHVFULEHV 0HL¶V DOJRULWKP 6HFWLRQ SUHVHQWV WKH JHQHWLF
ZHOODVWRFKDQJHVWRWKHFRQWH[WLQIRUPDWLRQRYHUWLPH>@ DOJRULWKP IUDPHZRUN 6HFWLRQ GLVFXVVHV WKH UHVXOWV RI
% *UDSKEDVHGDOJRULWKP DSSO\LQJ WKH *$ DOJRULWKP DQG FRPSDUHV WKHVH ZLWK
7KH SUREOHP RI WKH DVVLJQPHQW RI WKH ELRVLJQDO %RNKDUL¶V DQG 0HL¶V DOJRULWKP 6HFWLRQ FRQFOXGHV WKLV
SURFHVVLQJ WDVNV WR WKH DYDLODEOH GHYLFHV LV IRXQG WR EH SDSHUDQGGLVFXVVHVWKHIXWXUHZRUN
VLPLODUWRDQLQGXVWULDOFDVHVWXGLHGHDUOLHUE\%RNKDULLQWKH
,, &
DUHDRISDUDOOHODQGSLSHOLQHGFRPSXWLQJ>@7RVROYHWKLV 217(;7$:$5(0+($/7+$33/,&$7,216&(1$5,2
SUREOHP %RNKDUL SUHVHQWHG D JUDSKEDVHG VROXWLRQ E\ $QHSLOHSV\SUHGLFWLRQMREGHYHORSHGLQ>@FRQVLVWVRI
FRQVWUXFWLQJDOD\HUHGDVVLJQPHQWJUDSK,QWKLVDVVLJQPHQW VL[ELRVLJQDOSURFHVVLQJWDVNV )LJXUH :HQDPHWKHVH
JUDSK DQ\ SDWK FRQQHFWLQJ WZR GLVWLQJXLVKHG QRGHV WDVNV DV %LR6LJQDO 3URFHVVLQJ 8QLWV %638V )LUVW WKH
UHSUHVHQWVDSRVVLEOHDVVLJQPHQW7KHUHIRUHWKHDVVLJQPHQW SDWLHQW¶VVHQVHG(OHFWUR&DUGLR*UDP (&* GDWDLVILOWHUHG
SUREOHPLVWUDQVODWHGLQWRDSDWKVHDUFKSUREOHPZKLFKFDQ WRUHPRYHVLJQDODUWLIDFWVDQGHQYLURQPHQWQRLVH7KHUHDIWHU
EH VROYHG LQ SRO\QRPLDO WLPH 6RPH LPSURYHGDOJRULWKPV EHDWWREHDW KHDUW UDWH +5 LV GHULYHG DQG KHDUW UDWH
DUHIXUWKHUUHSRUWHGLQ>@0HL >@ VWXGLHGDVLPLODU YDULDELOLW\ +59 LQWKHIUHTXHQF\GRPDLQLVFDOFXODWHG7KH
SUREOHP E\ UHOD[LQJ WKH FRQWLJXLW\ FRQVWUDLQW >@ DQG IUHTXHQF\VSHFWUXPRIWKH+59LVWKHQXVHGWRFDOFXODWHWKH
SURSRVHGDQHZJUDSKEDVHGPHWKRGWRFRPSXWHWKHRSWLPDO SUREDELOLW\RIDQXSFRPLQJRURFFXUULQJVHL]XUH7RUHGXFH
DVVLJQPHQW,WKDVEHHQIRXQGWKDWWKLVVROXWLRQFDQDOVREH WKHFKDQFHRIIDOVHDODUPVWKHSDWLHQW¶VDFWLYLW\LQIRUPDWLRQ
H[WHQGHGWRVROYHWKHSUREOHPZLWKWKHFRQWLJXLW\FRQVWUDLQW LV PRQLWRUHG DV ZHOO DQG FRUUHODWHG ZLWK WKH DQDO\]HG
DQGLWPRUHRYHUUHGXFHVERWKWKHWLPHFRPSOH[LW\DQGVSDFH VSHFWUXPLQWKHILQDOVWDJH
FRPSOH[LW\FRPSDUHGWR%RNKDUL¶VRULJLQDODOJRULWKP
& *HQHWLF$OJRULWKP
6LQFH WKH WDVN DVVLJQPHQW SUREOHP LQ WKH JHQHUDO
PXOWLSURFHVVRUVFKHGXOLQJLV13KDUGKHXULVWLFPHWKRGVDQG )LJXUH(SLOHSV\SUHGLFWLRQWDVNFRQVLVWLQJRIVL[%638V
LQ SDUWLFXODU JHQHWLF DOJRULWKP DUH GHYHORSHG > @ $Q0KHDOWKSODWIRUP>@ZKLFKIDFLOLWDWHVWKHVHQVLQJ
+RZHYHU WKH VROXWLRQV SURSRVHG LQ > @ FDQ QRW EH SURFHVVLQJDQGWUDQVSRUWLQJRIWKHELRVLJQDOVFRQVLVWVRI
DSSOLHGWRRXUWDVNDVVLJQPHQWSUREOHPLQWKHLURULJLQDOIRUP WKHIROORZLQJGHYLFHV DVHWRIERG\ZRUQVHQVRUER[HVD
EHFDXVH ZH FRQVLGHU D FKDLQ RI SURFHVVLQJ GHYLFHV KDQGKHOG0RELOH%DVH8QLW 0%8 DEDFNHQGVHUYHUDQG
FRPPXQLFDWLRQDQGFRPSXWDWLRQFRQVWUDLQWVLQDGGLWLRQWR DQHQGWHUPLQDO )LJXUH 7KHVHQVRUER[HVFROOHFWWKHELR
WKHRUGHULQJFRQVWUDLQW WREHH[SODLQHGLQWKH6HFWLRQ,,, VLJQDOV RI WKH SDWLHQW VHQVH RWKHU GDWD OLNH ORFDWLRQ RU
+RZHYHUZHFRQVLGHUVRPHVSHFLDOWHFKQLTXHVSURSRVHGLQ DFWLYLW\DQGVHQGWKHGDWDWRWKH0%8RYHUZLUHOHVVVKRUW
WKHVH DSSURDFKHV HJ NQRZOHGJH DXJPHQWHG JHQHWLF UDQJHFRQQHFWLRQVHJ%OXHWRRWK$VDJDWHZD\WKH0%8
DOJRULWKPLQ>@ $VFRPSDUHGWR>@RXUDSSURDFK VHQGVWKHGDWDWRWKHEDFNHQGVHUYHURYHUD:L)L*356RU
EHQHILWV IURP WKH VLPSOHU FKURPRVRPH VWUXFWXUH DQG OHVV 8076FRQQHFWLRQ7KHUHDIWHUWKHGDWDFDQEHVWUHDPHGWR
SURFHVVLQJ LQWHQVLYH FURVVRYHU DQG PXWDWLRQ RSHUDWLRQV RU DFFHVVHG E\ D KHDOWKFDUH SURIHVVLRQDO XVLQJ KLV HQG
FRQVHTXHQWO\UHVXOWLQJLQDORZHUWLPHVSDQWRDFKLHYHWKH V\VWHP HJ KLV ODSWRS RU GHVNWRS 3& '\QDPLFDOO\
VXERSWLPDOVROXWLRQ UHDVVLJQLQJWKHSURFHVVLQJWDVNVWRWKHDYDLODEOHGHYLFHVLQ
2696 2007IEEECongressonEvolutionaryComputation(CEC2007)
UXQWLPHKDVDSRWHQWLDOWRHQKDQFHWKHV\VWHPDGDSWLYLW\WR %638LVDVVLJQHGWRGHYLFH%DVHGRQRXUGHILQLWLRQVLWV
WKHHQYLURQPHQWDOFRQWH[WFKDQJHV7RDFKLHYHWKLVGHVLUHG HQGWRHQGSURFHVVLQJGHOD\FDQEHFDOFXODWHGDV
DGDSWDWLRQWKHILUVWWRSLFWREHDGGUHVVHGLVKRZWRILQGWKH τ SSSSSSFFF
EHVWGHYLFHIRUHDFK%638:HIRUPXODWHWKLVDVVLJQPHQW
SUREOHPLQWKHQH[WVHFWLRQ
)LJXUH$QH[DPSOHRIDVVLJQLQJDGLUHFWHG%638FKDLQ P RQWRD
GLUHFWHGGHYLFHFKDLQ Q
)RUDQP%638QGHYLFHPRGHOWKHQXPEHURISRVVLEOH
DVVLJQPHQWVZLWKRXWFRQVLGHULQJWKHORFDOFRQVWUDLQWVLV
P+Q−
§ ·
¨ ¸
¨ Q− ¸
© ¹
)RU D ODUJHU QXPEHU RI P DQG Q WKLV SUREOHP LV
)LJXUH0KHDOWKSODWIRUP XQVROYDEOH LI DQ H[KDXVWLYH VHDUFK LV FRQGXFWHG (J IRU
P DQG Q WKHUH DUH LQ WRWDO [ SRVVLEOH
,,, %,26,*1$/352&(66,1*7$6.$66,*10(17352%/(0 DVVLJQPHQWVWREHFKHFNHG
:HIRUPXODWHWKHSUREOHPRIRSWLPDODVVLJQPHQWRID%638 ,9 *5$3+%$6('$/*25,7+0)257+(237,0$/
FKDLQRQWRDGHYLFHFKDLQDV $66,*10(172)3,3(/,1('352&(66,1*7$6.6
• *LYHQ D GLUHFWHG %638 FKDLQ FRQWDLQLQJ P %638V
LQFUHDVLQJO\LQGH[HGE\L∈^«P`DGLUHFWHGGHYLFH $ JUDSKEDVHG PHWKRG WR FRPSXWH WKH RSWLPDO
FKDLQ FRQWDLQLQJ Q GHYLFHV LQFUHDVLQJO\ LQGH[HG E\ DVVLJQPHQWRID%638FKDLQRQWRDGHYLFHFKDLQLVSURSRVHG
M∈^«Q`DQGDQREMHFWLYHIXQFWLRQτZKHUHτGHQRWHV LQ >@ LW ILUVW FRQVWUXFWV D OD\HUHG DVVLJQPHQW JUDSK WKDW
WKH HQGWRHQG SURFHVVLQJ GHOD\ IRU D SDUWLFXODU FRQWDLQVDOOWKHSRVVLEOHVXEDVVLJQPHQWRI%638WRGHYLFH
FRQILJXUDWLRQRI%638VDFURVVGHYLFHV $IWHUDVRXUFHQRGHDQGDVLQNQRGHDUHDGGHGDOOQRGHVLQ
• *RDO 7R ILQG DQ DVVLJQPHQW IXQFWLRQ Ȍ DPRQJ DOO WKH DVVLJQPHQW JUDSK DUH FRQQHFWHG DFFRUGLQJ WR WKH
RSW
SRVVLEOHȌ ^L`ĺ^M`VXFKWKDWτ Ȍ LVWKHPLQLPDORQH RUGHULQJFRQVWUDLQW )LJXUH :KHQWKHFRQVWUXFWLRQRIWKH
RSW JUDSKLVFRPSOHWHHYHU\SDWKFRQQHFWLQJWKHVRXUFHQRGH
DPRQJDOOτ Ȍ
• 6XEMHFWWR WKHIROORZLQJRUGHULQJDQGORFDOFRQVWUDLQWV DQGWKHVLQNQRGHFRUUHVSRQGVWRRQHSRVVLEOHDVVLJQPHQW
7KHRUGHULQJFRQVWUDLQWLVWKDWIRUHYHU\SDLURI%638L 7KHUHIRUHWKHSUREOHPRIILQGLQJWKHRSWLPDODVVLJQPHQWLV
DQG %638 L¶ LI L L¶ WKHQ Ȍ L Ȍ L¶ 7KLV FRQVWUDLQW WUDQVODWHGLQWRDSDWKVHDUFKSUREOHPWKDWFDQEHVROYHGZLWK
WKHUHIRUH UHIOHFWV WKH DOLJQPHQW RI GLUHFWLRQV RI WKH WZR DQ\ VKRUWHVW SDWK DOJRULWKP 7KH VSDFH FRPSOH[LW\ LV
FKDLQV ,W LV D PRUH UHOD[HG FRQVWUDLQW FRPSDUHG WR WKH 2 P
Q DQGWKHWLPHFRPSOH[LW\IRUWKHVHDUFKLV2 P Q LID
FRQWLJXLW\ FRQVWUDLQW GLVFXVVHG LQ > @ 7KH ORFDO VSHFLILFODEHOLQJSURFHGXUHLVDSSOLHG
FRQVWUDLQWLVWKDWIRUHYHU\%638LLWVKRVWLQJGHYLFHȌ L
VKRXOGVDWLVI\WKH%638L¶VV\VWHPUHTXLUHPHQW HJ&38
VSHHG DQG OLEUDU\ VXSSRUW DQG XVHU SUHIHUHQFH HJ WKLV
%638LKDVWREHDVVLJQHGRQGHYLFHȌ L
:HGHILQHWKHFRPSXWDWLRQWLPHIRU%638LWRSURFHVV
RQH IUDPH RI ELRVLJQDO GDWD DW GHYLFH MDVSLM DQG WKH
FRPPXQLFDWLRQWLPHIRUWUDQVIHUULQJRQHIUDPHRI%638L¶V
RXWSXWELRVLJQDOGDWDRYHUWKHOLQNEHWZHHQGHYLFHMDQG
MDVF 7KHYDULDEOHF GHQRWHVWKHFRPPXQLFDWLRQWLPH
LM M
IRUWUDQVIHUULQJRQHIUDPHRIVHQVHGGDWD WKHLQSXWWR%638
RYHUWKHOLQNEHWZHHQGHYLFHMDQGM:HQHJOHFWLQWUD
GHYLFHFRPPXQLFDWLRQWLPHHJLIERWK%638LDQGLDUH
ORFDWHGRQWKHVDPHGHYLFH:HIXUWKHUDVVXPHWKHUHLVQR
DGGLWLRQDOFRPSXWDWLRQWLPHRYHUKHDGIRUH[HFXWLQJVHYHUDO )LJXUH7KH%638GHYLFHDVVLJQPHQWJUDSKZLWKRXWWKHFRQWLJXLW\
%638VRQWKHVDPHGHYLFH6LQFHWKHYDOXHVRISLMDQGFLM FRQVWUDLQW
FRXOG EH NQRZQ D SULRU HJ EDVHG RQ DQDO\WLFDO 7KH H[SHULPHQW VWXG\ SURYHV WKH HIILFLHQF\ RI WKLV
EHQFKPDUNLQJRUWDVNSURILOLQJ>@WKHHQGWRHQGGHOD\τ JUDSKEDVHG PHWKRG 6LQFH WKLV WHFKQLTXH DOVR ILQGV LWV
RIDSDUWLFXODUFRQILJXUDWLRQRI%638VDFURVVGHYLFHVFDQEH DSSOLFDWLRQV LQ WKH G\QDPLF UXQWLPH UH DVVLJQPHQW RI
FDOFXODWHG ,Q )LJXUH ZH LOOXVWUDWH D %638GHYLFH %638V WR WKH SURFHVVLQJ GHYLFHV WKH SURFHVVLQJ WLPH
DVVLJQPHQWRIWKHHSLOHSV\SUHGLFWLRQWDVNRQWKH0KHDOWK UHTXLUHG WR FDOFXODWH WKH UH DVVLJQPHQW LV DOVR FULWLFDO $
SODWIRUP,QWKLVH[DPSOH%638DQGDUHDVVLJQHGWR VXERSWLPDO VROXWLRQ FDOFXODWHG XVLQJ WKH KHXULVWLF
GHYLFH%638DQGDUHDVVLJQHGWRGHYLFHDQG DOJRULWKPVVXFKDV*$PD\VDYHRQWKHSURFHVVLQJWLPHDW
2007IEEECongressonEvolutionaryComputation(CEC2007) 2697
WKHH[SHQVHRIDOLWWOHGLIIHUHQFHEHWZHHQWKHRSWLPDODQG FXUUHQW SRSXODWLRQ DQG VRPH RI WKHLU FRUUHVSRQGLQJ
VXERSWLPDOVROXWLRQV,QWKLVSDSHUZHZDQWWRHYDOXDWHWKH FRPSRQHQWV DUH H[FKDQJHG DW WKH UDQGRPO\ FKRVHQ
SHUIRUPDQFHRI*$IURPWKHIROORZLQJWZRDVSHFWV WKH FURVVRYHUSRLQW V WRIRUPWZRQHZFKURPRVRPHV UHIHUUHG
FRPSXWDWLRQWLPHDQG TXDOLW\RIWKHREWDLQHGVXERSWLPDO WRDVFKLOGUHQFKURPRVRPHV 7KHUHDUHDOVRYDULRXVW\SHVRI
VROXWLRQDVFRPSDUHGWRWKHRSWLPDOVROXWLRQ WKH FURVVRYHU LQYROYLQJ VLQJOH SRLQW FURVVRYHU DQG PXOWL
9 *(1(7,&$/*25,7+0)257+(237,0$/$66,*10(172) SRLQWFURVVRYHU:HFKRRVHWKHVLQJOHSRLQWFURVVRYHUIRU
3,3(/,1('352&(66,1*7$6.6 RXU SXUSRVH 7KH FURVVRYHU RSHUDWRU HYHQWXDOO\ OHDGV WR
FRPELQLQJWKHEHVWQXPHULFVHTXHQFHRIRQHFKURPRVRPH
*HQHWLF$OJRULWKP *$ LVDSURYHQKHXULVWLFWHFKQLTXH ZLWKWKDWRIWKHRWKHUFKURPRVRPHWRHYROYHDEHWWHUQHZ
EDVHGRQWKH'DUZLQ¶VWKHRU\RIWKHµVXUYLYDORIWKHILWWHVW¶ FKURPRVRPH V
WRILQGWKHVXERSWLPDOVROXWLRQLQWKHODUJHVHDUFKVSDFHV $IWHUDSSO\LQJWKHFURVVRYHURSHUDWRUHDFKHOHPHQWRIWKH
> @+HUHZLWKZHSURYLGHDEULHIRYHUYLHZRIWKHVWHSV FKURPRVRPH LQ WKH SRSXODWLRQ LV DSSOLHG D PXWDWLRQ
DSSOLHGLQRXU*$ RSHUDWRU ZLWK VRPH SUREDELOLW\ UHIHUUHG WR DV PXWDWLRQ
7KH ILUVW VWHS LV DQ HQFRGLQJ RI WKH SRVVLEOH VROXWLRQ SUREDELOLW\ 7KH PXWDWLRQ RSHUDWRU WUDQVIRUPV D
ZKLFKLVUHSUHVHQWHGE\DFKURPRVRPH7KHUHH[LVWVHYHUDO FKURPRVRPH LQWR DQRWKHU FKURPRVRPH ZKLFK FRXOG
HQFRGLQJ WHFKQLTXHV VXFK DV ELQDU\ HQFRGLQJ QXPEHU HYHQWXDOO\OHDGWRDEHWWHUFKURPRVRPHZKLFKFRXOGQRWEH
HQFRGLQJFKDUDFWHUHQFRGLQJDQGWUHHHQFRGLQJ>@(DFK REWDLQHGMXVWE\DSSO\LQJWKHFURVVRYHURSHUDWRU
FKURPRVRPHUHSUHVHQWVRQHVROXWLRQWRWKHSUREOHP$VHWRI /DWHUWKHVHTXHQFHRIVWHSV UHIHUUHGWRDVRQHLWHUDWLRQ
FKURPRVRPHV LV UHIHUUHG WR DV D SRSXODWLRQ )RU RXU LQYROYLQJ VHOHFWLRQ FURVVRYHU DQG PXWDWLRQ RSHUDWRUV LV
SUREOHPZHFKRRVHDQXPEHUHQFRGLQJRIWKHFKURPRVRPH UHSHDWHGXQWLODFHUWDLQVWRSSLQJFULWHULRQLVPHW$VWRSSLQJ
7KHVHFRQGVWHSLVWKHJHQHUDWLRQRIDQLQLWLDOSRSXODWLRQ FULWHULRQPD\LQYROYHYDULRXVIRUPVVXFKDVUXQQLQJWKH*$
8VXDOO\ WKH FKURPRVRPHV ZKLFK FRQVWLWXWH DQ LQLWLDO IRUDFHUWDLQQXPEHURILWHUDWLRQVRUZKHQQRLPSURYHPHQW
SRSXODWLRQDUHJHQHUDWHGSXUHO\UDQGRPO\+RZHYHUWRWDNH LQWKHPD[LPXPILWQHVVFRXOGEHREWDLQHGDIWHUDSUHGHILQHG
FDUH RI WKH RUGHULQJ FRQVWUDLQW ZH LQWURGXFH FHUWDLQ QXPEHU RI LWHUDWLRQV :H DGRSW WKH ODWHU FULWHULRQ LQ RXU
RUGHULQJLQWKHJHQHUDWLRQRIWKHLQLWLDOSRSXODWLRQ)RUWKH H[SHULPHQWV
VHFRQG VWHS WKH LQLWLDO SRSXODWLRQ UHSUHVHQWV WKH FXUUHQW $ (QFRGLQJRIDVROXWLRQ
JHQHUDWLRQ 7KH QXPEHU RI FKURPRVRPHV FRQVWLWXWLQJ WKH :HHQFRGHDFKURPRVRPHDVDVHTXHQFHRIQXPEHUV7KH
FXUUHQW JHQHUDWLRQ LV NQRZQ DV WKH SRSXODWLRQ VL]H 7KH OHQJWKRIWKHFKURPRVRPHLVVDPHDVWKHQXPEHURI%638V
SRSXODWLRQ VL]H DIIHFWV WKH TXDOLW\ RI WKH VXERSWLPDO 7KHILUVWQXPEHURIWKHFKURPRVRPHUHSUHVHQWVWKHLQGH[RI
VROXWLRQREWDLQHG GHYLFH LHȌ RQZKLFKWKHILUVW%638ZLOOH[HFXWH WKH
7KH WKLUG VWHS LV WR HYDOXDWH WKH ILWQHVV RI HYHU\ VHFRQGQXPEHUUHSUHVHQWVWKHLQGH[RIGHYLFH LHȌ
FKURPRVRPHLQWKHFXUUHQWJHQHUDWLRQ$VSHFLILFREMHFWLYH RQZKLFKWKHVHFRQG%638ZLOOH[HFXWHDQGVRRQ7KXV
IXQFWLRQ UHSUHVHQWLQJ WKH XWLOLW\ RI WKH FKURPRVRPH HYHU\ FKURPRVRPH UHSUHVHQWV D GLIIHUHQW DVVLJQPHQW $Q
GHWHUPLQHVWKHILWQHVVRIWKHFKURPRVRPH,QRXUFDVHWKH H[DPSOH RI WKH FKURPRVRPH FRUUHVSRQGLQJ WR WKH
REMHFWLYH IXQFWLRQ HYDOXDWHV WKH HQGWRHQG GHOD\ LQ WKH DVVLJQPHQWLOOXVWUDWHGLQ)LJXUHLVJLYHQLQ)LJXUH
%638SURFHVVLQJFKDLQDVDVVLJQHGE\WKHFKURPRVRPHWR
WKHGHYLFHV6LQFHRXUSUREOHPLVWKHPLQLPL]DWLRQSUREOHP
DVPDOOHUGHOD\UHSUHVHQWVKLJKHUILWQHVV
7KHIRXUWKVWHSLVDSSO\LQJWKHVHOHFWLRQRSHUDWRUWRIRUP
WKHQH[WJHQHUDWLRQ7KHVHOHFWLRQRSHUDWRUDOORZVWKH*$WR )LJXUH $SRVVLEOHFKURPRVRPHUHSUHVHQWLQJWKHSODFHPHQWRI%638VWR
WDNH ELDVHG GHFLVLRQV IDYRULQJ WKH FKURPRVRPHV KDYLQJ WKHGHYLFHVZKHUHP DQGQ
KLJKHUILWQHVVYDOXHRYHUWKHFKURPRVRPHVKDYLQJWKHORZHU % ,QLWLDOSRSXODWLRQJHQHUDWLRQ
ILWQHVVYDOXH7KHUHH[LVWVHYHUDOVHOHFWLRQWHFKQLTXHVVXFK 6LQFH LW LV UHTXLUHG WKDW WKH DVVLJQPHQW RI %638V WR
DV URXOHWWH ZKHHO VHOHFWLRQ :HFKRRVHWKH URXOHWWHZKHHO GHYLFHVVKRXOGIROORZWKHRUGHULQJFRQVWUDLQWDFFRUGLQJWR
VHOHFWLRQ WHFKQLTXH IRU RXU H[SHULPHQWDWLRQ ,Q WKLV WKH HQFRGLQJ WHFKQLTXH FKRVHQ LQ WKH 6HFWLRQ 9$ WKH
WHFKQLTXHWKHSUREDELOLW\RIWKHVHOHFWLRQRIDFKURPRVRPH VHDUFKVSDFHFRQVLVWVRIDOOWKH%638WRGHYLFHPDSSLQJV
LQWKHQH[WLVGLUHFWO\SURSRUWLRQDOWRLWVILWQHVVYDOXH7KH IROORZLQJ WKH RUGHULQJ FRQVWUDLQW DQG FORVHG E\ WKH
SRSXODWLRQVL]HRIWKHQH[WJHQHUDWLRQW\SLFDOO\UHPDLQVWKH FKURPRVRPHDVVLJQLQJHDFK%638WRWKHVWGHYLFHDQGWKH
VDPH DV WKH LQLWLDO JHQHUDWLRQ $IWHU VHOHFWLQJ WKH QH[W FKURPRVRPH DVVLJQLQJ HDFK %638 WR WKH QWK GHYLFH DV
JHQHUDWLRQWKHFXUUHQWJHQHUDWLRQLVUHSODFHGE\WKHLQLWLDO VKRZQLQWKH)LJXUH
JHQHUDWLRQ :KHQFUHDWLQJWKHFKURPRVRPHVLQWKHLQLWLDOSRSXODWLRQ
6HOHFWLRQLVIROORZHGE\DSSO\LQJWKHFURVVRYHURSHUDWRU LQLWLDOO\ ZH KDG FKRVHQ WR XVH D UDQGRP DVVLJQPHQW RI
RYHUWKHFXUUHQWJHQHUDWLRQ:LWKVRPHSUREDELOLW\ UHIHUUHG %638VWRGHYLFHV+RZHYHUGXULQJWKHH[SHULPHQWDWLRQZH
WR DV FURVVRYHU SUREDELOLW\ VRPH SDLUV RI FKURPRVRPHV IRXQGWKDWXQOHVVWKHQXPEHURI%638VLVYHU\VPDOOWKH
UHIHUUHGWRDVSDUHQWFKURPRVRPHV DUHVHOHFWHGIURPWKH PHPEHUVRIWKHLQLWLDOSRSXODWLRQKDUGO\IROORZRXURUGHULQJ
2698 2007IEEECongressonEvolutionaryComputation(CEC2007)
no reviews yet
Please Login to review.
