2009 Third International Conference on Genetic and Evolutionary Computing
$Q DGYDQFHG *HQHWLF $OJRULWKP IRU 7UDYHOLQJ 6DOHVPDQ 3UREOHP
:DQJ <RXSLQJ /L OLDQJ &KHQ /LQ
ǃ &ROOHJH RI &RPSXWHU 6FLHQFH <DQJW]H 8QLYHUVLW\ -LQJ]KRX +XEHL &KLQD
HPDLO UTD]G#FRPˈFKDQB#VRKXFRP
&ROOHJH RI ,QIRUPDWLRQ DQG 0DWKHPDWLFV <DQJW]H 8QLYHUVLW\ -LQJ]KRX +XEHL &KLQD
HPDLO ED\#VLQDFRP
$EVWUDFW%\ DQDO\]LQJ WKH GHILFLHQF\ RI WUDGLWLRQDO FRQYHUJH WR WKH ORFDO RSWLPX P 7R RYHUFRPH
JHQHWLF DOJRULWKP LQ VROYLQJ WKH 7UDYHOLQJ 6DOHVPDQ WKHVH VKRUWFRPLQJV KHXULVWLF NQRZOHGJH DQG D
3UREOHP DQ LPSURYHG JHQHWLF DOJRULWKP LV SURSRVHG VHOIOHDUQLQJ LV HPSOR\HG IRU PXWDWLRQ )LQDOO\
IRU 763 ,Q WKLV SDSHU WKH RUGLQDO UHDOQXPEHU HQFRGHU H[SHULPHQWDO VLPX ODWLRQV DUH VKRZQ WR YHULI\ WKH
LV XVHG IRU FKURPRVRPH HQFRGLQJ DQG RUGHUHG IHDVLELOLW\ DQG YDOLGLW\ RI WKLV DOJRULWKP
FURVVRYHU RSHUDWRUV LV DGYDQFHG WKDW XWLOL]HV ORFDO DQG
,, 3UREOHP GHVFULSWLRQ
JOREDO LQIRUPDWLRQ WR FRQVWUXFW RIIVSULQJ ,Q RUGHU WR
763 LV GHVFULEHG XVLQJ ZHLJKWHG JUDSK WKHRU\ DV
JXDUDQWHH JOREDO FRQYHUJHQFH KHXULVWLF NQRZOHGJH DQG
IROORZV * 9 $ : GHQRWHV D JLYHQ FLW\
VHOIOHDUQLQJ LV HPSOR\HG IRU PXWDWLRQ 7KHQ D FLW\
QHWZRUN ZKHUH 9 ^Y Y Y Q ` LV D ILQLWH VHW
QHWZRUN ZKLFK FRQWDLQV FLW\ QRGHV LV HPSOR\HG WR
WHVW WKH DOJRULWKP 7KH VLPXODWLRQ UHVXOW RI 0$7/$% ZKRVH HOHPHQ WV DUH FDOOHG QRGHV LH FLW\ _ 9 _ Q
VKRZV WKDW WKH SURSRVHG PHWKRG FDQ JHW IHDVLEOH UHVXOW LV WKH QXPEHU RI QRGHV LQ WKH FLW\ QHWZRUN
ZLWK D KLJKHU FRQYHUJHQW UDWH DQG VXFFHVV UDWH WKDQ DQG $ ^DLM _ d L M d Q` LV D ILQ LWH VHW ZKRVH
H[LVWLQJ KHXULVWLFV HOHPHQ WV DUH FDOOHG DUFV $Q DUF DL M OLQ NV WZR
QRGHV Y L DQG Y M LQ WKH QHWZRUN (DFK DUF DL M KDV
.H\ZRUG *HQHWLF DOJRULWKP FURVVRYHU KHXULVWLF DVVRFLDWHG D QRQQHJDWLYH ZHLJKW YDOXH ZL M ZKLFK
NQRZOHGJH PXWDWLRQ
LQGLFDWHV WKH GLVWDQFH EHWZHHQ YL DQG Y M XVH D
, ,QWURGXFWLRQ ILQ LWH VHW : ^ ZL M _ d L M d Q ` WR GHQRWH WKH
7UDYHOOLQJ 6DOHVPDQ 3UREOHP VKRUW IRU 763 ZHLJKW PDWUL[ RI WKH QHWZRUN LW LV GHILQHG DV
KDV WKH ZLGHVSUHDG DSSOLFDWLRQ EDFNJURXQG DQG IROORZLQJ
WKH LPSRUWDQW WKHRU\ YDOXH LQ FRPELQDWLRQ ª Z Z Z Q º
«Z Z Z Q »
RSWLPL]HV 7KH LGHD RI 763 LV WR ILQG D FORVHG : « » ˄˅
VKRUWHVW WRXU SDWK EHWZHHQ D JLYHQ QXPEHU RI « »
« »
FLWLHV DQG HDFK FLW\ FDQ EH YLVLWHG RQO\ RQH WLPH ¬ Z Q Z Q Z Q Q ¼
7KH SUREOHP LV HTXLYDOHQW WR WKH +DPLOWRQ FLUFOH LI L z M ZL M ZML LI L M WKHQ ZL M
SUREOHP 0RVW RI UHVHDUFKHUV WHQG WR DGRSW 7KH 763 LV WR ILQG WKH VKRUWHVW WUDYHOOLQJ URXWH LQ
LQWHOOLJHQFH FRPSXWDWLRQ WR DFKLHYH DSSUR[LPDWH WKH FLW\ QHWZRUN7KH RSWLPX P URXWH PRGHO FDQ
RSWLPL]HG VROXWLRQ IRU WKH SUREOHP EH GHVFULEHG DV
*HQHW LF $OJRULWKP *$ LV D SRZHUIXO JOREDO Q
UDQGRPL]HG VHDUFK DQG UREXVW LQWHOOLJHQW
= PLQ ¦
M
ZL M ZQ
Lz M
RSWLPL]DWLRQ WHFKQLTXH +RZHYHU WKHUH DUH VRPH
VKRUWFRPLQJV H[LVWHG LQ JHQHWLF DOJRULWKPV VXFK (TXDWLRQ LV XVHG WR JXDUDQWHH WKH OHQJWK RI D
DV WKH ORZ HIILFLHQF\ FRQYHUJHQFH DQG DSW WR URXWH UHDFKHG PLQLPX P
978-0-7695-3899-0/09 $29.00 © 2009 IEEE 101
DOI 10.1109/WGEC.2009.127
,,, $OJRULWKPV GHVFULSWLRQ DQG GHVLJQLQJ URXOHWWH ZKHHO VHOHFWLRQ LV DGRSWHG LQ RXU
*HQHW LF $OJRULWKP LV D IDPLOLDU LQWHOOLJHQW DOJRULWK P
VHDUFK PHWKRG LQVSLUHG E\ WKH HYROXWLRQDU\
'ˊ&URVVRYHU RSHUDWRUV
SURFHVVHV LQ QDWXUDO V\VWHPV DQG FRQVLGHUHG WR EH
,Q WKLV SDSHU 2; >@ FURVVRYHU RSHUDWRU LV
D JOREDO UDQGRP VHDUFK RSWLPL]DWLRQ PHWKRG DQG
HPSOR\HG IRU WKH DOJRULWKP 7KH DGYDQWDJH RI WKLV
LW RIWHQ SHUIRUPV ZLWK UHPDUNDEOH HIILFLHQF\
PHWKRG LV WKDW 2; FDQ QRW RQO\ UHWDLQ VRPH
)ROORZLQJ LV WKH PDLQ SURFHVVHG RI *$
H[FHO OHQFH JHQH DUUDQJHPHQW RI SDUHQW LQGLYLGXDO
$ &KURPRVRPDO UHSUHVHQWDWLRQ EXW DOVR FDQ FRPELQH DOO NLQGV RI RUGHUHG
7KHUH DUH PX OWLSOH FRGHV LQ WKH FKURPRVRPH VWUXFWXUH XQLW VR WKDW LW LV HDV\ WR JHW D EHWWHU
FRGH VXFK DV ELQDU\ FRGH *UD\ FRGH DQG WKH UHDO LQGLYLGXDO DIWHU FURVVRYHU RSHUDWLRQ 7KH 2;
QXPEHU FRGH ,Q WKLV SDSHU WKH JHQHV DUH WKH FLW\ FURVVRYHU RSHUDWRU LV SURFHHGHG DFFRUG WR WKH
QHWZRUN QRGHV WKH SURFHVV RI ILQGLQJ WKH IROORZLQJ VWHSV
RSWLPX P URXWH LV WKH SURFHVV RI UHRUGHULQJ WKHVH 5DQGRPO\ JHQHUDWH WZR QDWXUDO QXPEHUV
QRGHV DQG DQ RUGLQDO UHDOQX PEHU HQFRGHU LV XVHG DQG XVH WKHP WR GHWHUPLQH WZR FURVVRYHU SRLQWV
)RU H[D PSOH VXSSRVH WKDW WKHUH LV D URXWH ³_´ )RU H[DPSOH WKH WZR UDQGRP QXPEHUV DUH
H[LVWLQJ LQ WKH IROORZ ZHLJKWHG UHVSHFWLYHO\ DQG WKHQ WKH FURVVRYHU SRLQW RI
JUDSK DQG WKHQ WKH LQLWLDO SRSXODWLRQ LV WZR SDUHQWDO LQGLYLGXDO FDQ EH GHFRGHG DV IROOR ZV
3
% )LWQHVV IXQFWLRQ 3
%DVHG RQ WKH VKRUWFRPLQJ RI WKH *$ LW LV )LJ &KURPRVRPH FRGLQJ GLDJUDP
QHHGHG WR YRLG WKH VXSHU FKURPRVRPH WKDW ˅.HHS WKH JHQH IUDJPHQW EHWZHHQ WKH WZR
SUHYHQWV SUHPDWXUH FRQYHUJHQFH E\ DGGLQJ D FURVVRYHU LQYDULDQW DQG XVH WKH V\PERO ³[´ WR
KHXULVWLF UXOH $FFRUGLQJ WR WKH SUREOHP GHVFULEHG UHSODFH RWKHU SDUWV DQG WKHQ JHW WZR LQGLYLGXDO DV
DERYH ZH FDQ GHILQH WKH ILWQHVV IXQFWLRQV DV IROORZV
2 [ [ [ [ [ [
IROORZ
2 [ [ [ [ [ [
= = PLQ
PD[) ZL M P ˄˅ ˅ 5HFRUG D JHQH VHTXHQFH DUUDQJHPHQW RI
= PD[ =PLQ U 3 IURP WKH VHFRQG FURVVRYHU SRLQW WR WKH HQG
:KHUH U >@ P LV HOLPLQDWLRQ LQGH[ ZKLFK LV DQG FRQWLQXH WR OLQ N WKH JHQH IUDJPHQWV IURP WKH
XVHG WR FRQWURO WKH VHDUFKLQJ VSHHG RI WKH KHDG WR WKH VHFRQG FURVVRYHU SRLQW DQG WKHQ JHW
DOJRULWKP VR WKDW DFFHOHUDWH WKH FRQYHUJHQFH 7KH DQ H[FKDQJHG SDUHQW 3
DV IROOR Z
H[SHULPHQWDO VLPX ODWLRQ VKRZV KDW P LV 3¶
VXLWDEOH $V WR SDUHQWDO 3 D SDUW JHQH IUDJ PHQW 5
DOUHDG\ H[LVWHG
& 6HOHFWLRQ RSHUDWRUV
5
7KH SDUHQWDO QRGHV ZKLFK XVHG WR FURVVRYHU LV
7R DYRLG WKH UHSHDW JHQH KDSSHQHG 5 PXVW
GHFLGHG E\ WKH ILWQHVV IXQFWLRQ YDOXH RI SUHFHGLQJ
EH JRW ULG RI IURP WKH SDUHQWDO LQGLYLGXDO 3
DQG
JHQHUDWLRQ FKURPRVRPH WKH JRRG TXDOLW\
WKH UHPDLQ LQJ JHQH IUDJPHQW LV DV IROORZ
LQGLYLGXDO QDPHO\ WKH LQGLYLGXDO ZKRVH OLQ N
5
EHWZHHQ WKH RULJLQ QRGH DQG WKH GHVWLQDWLRQ QRGH
7KHQ VWDUW WR FRS\ 5 WR WKH SDUHQW 3 IURP
LV VKRUWHU LV PRUH SRVVLEOH WR EH VHOHFW 7KH
102
WKH VHFRQG FURVVRYHU SRLQW DQG UHSODFH WKH JHQH 6WDUW
³[´ RI 2 ZLWK 5 LQ VHTXHQFH WKH RIIVSULQJ 3
LV
DV IROORZ WKH RWKHU RIIVSULQJ 3
LV WKH VDPH W\SH *HQHUDWH LQLWLDO SRS
ZLWK VDPH UHDVRQLQJ
(YDOXDWH )LWQHVV
3 ¶¶
3¶¶ <
&RXQWHUı/LPLW 5HVXOW
( 0XWDWLRQ RSHUDWRUV
1
7ZR 3RLQW ([FKDQJH PHWKRG LV HPSOR\HG IRU
0XWDWLRQ RSHUDWRU 6XSSRVH WKDW D SDUHQWDO 6HOHFW RSHUDWLRQ
FKURPRVRPH S LV DV IROOR Z
&URVVRYHU RSHUDWLRQ
3
)LUVW UDQGRPO\ JHQHUDWH WZR H[FKDQJH SRLQW
0XWDWH RSHUDWLRQ
DUUD\ DQG DUUD\˄˅ˈDQG WKHQ H[FKDQJH WKH WZR
JHQHV DW VXFK WZR SRLQWV 6XSSRVH WKDW DUUD\ )LJ )ORDW FKDUW RI *$
DQG DUUD\ WKH RIIVSULQJ S
IURP WKH
7DEOH &RRUGLQDWH GDWD RI FLWLHV
FURVVRYHU PXVW EH DV IROORZ /KDVD /DQ]K RX
3 ¶ %HLMLQJ <LQFKXDQ
7KH PHDQ LQJ RI PXWDWLRQ RSHUDWRU LV WR PDNH WKH 6KDQJKDL ;LQLQJ
JURXS GLYHUVLW\ %XW LW LV DSW WR GHVWUR\ WKH JRRG 7LDQMLQ 8UXPFKL
LQGLYLGXDO DQG WKHQ VORZGRZQ WKH VSHHG WR REWDLQ 6KLMLD]K XDQJ -L QDQ
WKH RSWLPX P VROXWLRQV ,Q RUGHU WR RYHUFRPH WKH 7DL\ XDQ 1DQMLQJ
VKRUWFRPLQJV ZH QHHG WR DGG D VHOIOHDUQLQJ +RKKRW +DQJ]K RX
SURFHVV ZKHQ PXWDWLRQ RSHUDWRU KDSSHQHG 7KH 6KHQ\ DQJ +HIHL
PHWKRG RI VHOIOHDUQLQJ HPSOR\HG LV WR UHDSSUDLVH &KDQJFKXQ 1DQFKDQJ
WKH ILWQHVV IXQFWLRQ YDOXH ) S :KHQ VRPH JLYHQ +DUELQ )X]K RX
JHQH RI LQGLYLGXDO S ZDV PXWDWHG ZH QHHG WR =KHQJ]K RX :XKDQ
UHFDOFXODWH WKH ILWQHVV IXQFWLRQ YDOXH ) S
DQG &KDQJVKD *XDQJ]K RX
FRPSDUHG LW ZLW K ) S ,I ) S
! ) S WKHQ 1DQQLQJ +DLNRX
NHHS S
RWKHUZLVH NHHS S &KHQJGRX *XL\ DQJ
) $OJRULWKPV GHVLJQLQJ .XPLQJ ;L DQ
$FFRUGLQJ WR WKH DERYH GHVFULEHG WKH JHQHWLF 7DLSHL
DOJRULWKP IORDW FKDUW LV DV )LJ 7DEOH %HVW VROXWLRQ FKDQJHV DORQJ ZLWK SRSXODWLRQ
VFDOH 3& 3P (OLPLQDWLRQ LQGH[ P
,9 ([SHULPHQWDO GDWD DQG DQDO\VLV ,WHUDWLRQ WLPHV 3RSXODWLRQ VFDOH %HVW URXWH OHQJWK 5XQ WLPH
$ QHWZRUN ZKLFK FRQWDLQV FLWLHV VKRZQ LQ
H V
7DEOH LV HPSOR\HG WR EH WKH H[SHULPHQW GDWD
H V
7KH UHVXOWV ZHUH VKRZQ LQ WKH 7DEOH 7DEOH
H V
)LJ DQG )LJ E\ VLPX ODWLRQ RI 0$7/$%
103
7DEOH %HVW VROXWLRQ FKDQJHV DORQJ ZLWK LWHUDWLRQ WLPHV KHXULVWLF UXOH WR SUHYHQW WKH SUHPDWXUH
3& 3P (OLPLQDWLRQ LQGH[ P FRQYHUJHQFH DQG D VHOIOHDUQLQJ PXWDWLRQ LV XVHG
3RSXODWLRQ VFDOH ,WHUDWLRQ WLPHV %HVW URXWH OHQJWK 5XQ WLPH WR VSHHG XS WKH RSWLPX P URXWH VROXWLRQ 7KH
H V H[SHULPHQWDO VLPX ODWLRQ VKRZV WKLV DOJRULWKP FDQ
H V ILQG WKH RSWLPX P URXWH PRUH HIILFLHQWO\ +RZHYHU
H V VRPH SDUDPHWHUV DUH FRQWUROOHG DUWLILFLDOO\ WKDW
7KH VLPX ODWH UHVXOW LQ WDEOH VKRZV WKDW WKH %HVW PD\EH FDXVH DQ LQHIIHFWLYH VROXWLRQ 6XFK DV WKH
URXWH OHQJWK GHFOLQH ZKLOH SRSXODWLRQ VFDOH DOJRULWKP FDQ VSHHG XS UHVHDUFK UDWH E\ DVVLJQLQJ
LQFUHDVH DQG WDEOH VKRZV WKDW WKH %HVW URXWH D ELJ YDOXH IRU WKH HOLPLQDWLRQ LQGH[ P EXW PD\EH
OHQJWK GHFOLQHV ZKLOH LWHUDWLRQ WLPHV LQFUHDVH ZLWKRXW DQ RSWLPX P VROXWLRQ WKXV FDXVLQJ
)URP WKH WDEOH DERYH WKH %HVW URXWH OHQJWK LV XQVWDEOH FRQYHUJHQFH )RU WKHVH VKRUWFRPLQJV
H ZKLFK LV YHU\ FORVH WR WKH EHVW VHOIDGDSWLYH FRQWUROOLQJ LV UHVHDUFK HPSKDVLV LQ
LQWHUQDWLRQDO RSWLPX P VROXWLRQ ZKLFK ZLWK D WKH QHVW VWHS ZRUN
YDOXH H 7KH %HVW UHF\FOH URXWH LV
5HIHUHQFHV
VKRZHG LQ )LJ >@ :DQJ /LQJ ,QWHOOLJHQW 2SWLPL]DWLRQ $OJRULWKPV
ZLWK $SSOLFDWLRQV %HLMLQJ 7VLQJKXD 8QLYHUVLW\
SUHVV a
>@ 0 0XQHPRWR < 7DNDL< 6DWR $ PLJUDWLRQ VFKHPH
IRU WKH JHQHWLF DGDSWLYH URXWLQJ DOJRULWKP >&@ Ġ
86$ ,((( ,QWHUQDWLRQDO &RQIHUHQFH RQ 6\VWHPV
0DQ DQG &\EHUQHWLFV
>@ *UHIHQVWHWWH - -*RSDO 5 5RVPDLWD % HW DO *HQHWLF
DOJRULWKP IRU 7 63 ,Q *UHIHQVWHWWH - - HGV
3URFHHGLQJV RI WKH )LUVW ,QWHUQDWLRQDO &RQIHUHQFH
)LJ %HVW UHF\FOH URXWH RI SRSXODWLRQ VFDOH RQ *HQHWLF $OJRULWKPV DQG 7KHLU $SSOLFDWLRQV
3LWWVEXUJK 3LWWVEXUJK 3 $ &DUQHJLH0 HOORQ
8QLYHUVLW\ a
>@ 2OLYHU / 0 6PLWK ' - +ROODQG - 5 &$ 6WXG\ RI
3HUPXWDWLRQ &URVVRYHU 2SHUDWRUV RQ WKH 7UDYHOLQJ
6DOHVPDQ 3UREOHP ,Q 3URFHHGLQJV RI WKH 6HFRQG
,QWHUQDWLRQDO &RQIHUHQFH RQ *HQHWLF $OJRULWKPV
/DZUHQFH (UOEDXP $VVRFLDWHV a
>@ :DQJ ;LDRSLQJ &DR /LPLQJ *HQHWLF $OJRULWKP
7KHRU\ 8WLOL]DWLRQ DQG 5HDOL]DWLRQ ;LDQ
)LJ (YROXWLRQ JHQHUDWLRQV SRSXODWLRQ VFDOH ;LDQ-LDRWRQJ 8QLYHUVLW\ 3UHVV
)URP WKH VLPX ODWLRQ UHVXOWV RI WKH DERYH JUDSK >@ *ROGEHUJ ' ( $OOHOHV ORFL DQG WKH WUDYHOLQJ
WKH FRQFOXVLRQ FDQ EH GUDZQ WKDW WKH DGYDQFHG VDOHVPDQ SUREOHP ,Q *UHIHQVWHWWH - - HGV
JHQHWLF DOJRULWKP FDQ FRQYHUJH WR RSWLPDO 3URFHHGLQJV RI WKH )LUVW ,QWHUQDWLRQDO &RQIHUHQFH
VROXWLRQ DQG JHW WKH IHDVLEOH UHVXOW IRU WKH 763 RQ *HQHWLF $OJRULWKPV DQG 7KHLU $SSOLFDWLRQV
9 &RQFOXVLRQV 3LWWVEXUJK 3LWWVEXUJK 3 $ &DUQHJLH0 HOORQ
7KH DOJRULWKP LV LPSURYHG E\ DGGLQJ D 8QLYHUVLW\ a
104
