/HDUQLQJWR8QGHUVWDQG0XOWLPRGDO5HZDUGVIRU
+XPDQ5RERW,QWHUDFWLRQXVLQJ+LGGHQ0DUNRY0RGHOVDQG
&ODVVLFDO&RQGLWLRQLQJ$QMD$XVWHUPDQQ6HLML<DPDGD$EVWUDFW²:HDUHSURSRVLQJDQDSSURDFKWRHQDEOHDURERWWROHDUQ WKH VSHHFK JHVWXUH DQG WRXFK SDWWHUQV WKDW LWV XVHUHPSOR\V IRU JLYLQJ SRVLWLYH DQGQHJDWLYH UHZDUG 7KHOHDUQLQJ
SURFHGXUHXVHVDFRPELQDWLRQRI+LGGHQ0DUNRY0RGHOVDQGDPDWKHPDWLFDO PRGHO RI FODVVLFDO FRQGLWLRQLQJ 7R IDFLOLWDWHOHDUQLQJ WKH URERW DQG WKH XVHU JR WKURXJK D WUDLQLQJ WDVNZKHUH WKH JRDO LV NQRZQ VR WKDW WKH URERW FDQ DQWLFLSDWH LWV
XVHU¶V FRPPDQGV DQG UHZDUGV :H RXWOLQH WKH H[SHULPHQWDOIUDPHZRUN DQG WKH WUDLQLQJ WDVN DQG JLYH GHWDLOV RQ WKHSURSRVHG OHDUQLQJ PHWKRG HYDOXDWLQJ WKH DSSOLFDELOLW\ RI
FODVVLFDOFRQGLWLRQLQJIRUWKHWDVNRIOHDUQLQJXVHUUHZDUGVJLYHQ
LQ RQH RU PRUH PRGDOLWLHV VXFK DVVSHHFKJHVWXUH RUSK\VLFDOLQWHUDFWLRQ

7, ,1752'8&7,21

+,6 ZRUN GHVFULEHV D PHWKRG WR DGDSW D URERW WR LWV
XVHU WKURXJK D FRRSHUDWLYH WUDLQLQJ WDVN 'XULQJ WKHWUDLQLQJSKDVHWKHURERWOHDUQVWRXQGHUVWDQGLWVXVHU¶VZD\RIJLYLQJ SRVLWLYH DQG QHJDWLYH IHHGEDFN WR LW XVLQJ VSHHFKJHVWXUHV DQG WKH URERW V EXLOWLQ WRXFKVHQVRUV  7KH SDSHURXWOLQHVWKHWZRHVVHQWLDOHOHPHQWVRIRXUOHDUQLQJPHWKRG $ WZRVWDJHG OHDUQLQJ SURFHGXUH EDVHG RQ +LGGHQ0DUNRY PRGHOV DQG DQ LPSOHPHQWDWLRQ RI FODVVLFDOFRQGLWLRQLQJ,WLVHPSOR\HGWROHDUQWRUHFRJQL]HWKH
XVHU V PXOWLPRGDO EHKDYLRU SDWWHUQV DQG WR DVVRFLDWHWKHPZLWKSRVLWLYHDQGQHJDWLYHUHZDUGV $ PHWKRG WR JDWKHUWKHQHFHVVDU\ WUDLQLQJGDWD IURPWKHXVHULQDWUDLQLQJWDVNZLWKRXWVWUHVVLQJRUERULQJKLP DQG ZLWKRXW SXWWLQJ WKH XVHU LQWR D VLWXDWLRQZKHUHKHKDVWRSUHUHFRUGEHKDYLRUVWKDWKHZDQWVWR
XVH IRU FRPPXQLFDWLRQ LQ DQ DUWLILFLDO ³UHFRUGLQJ´VLWXDWLRQ
7KH SURSRVHG ZD\ RI OHDUQLQJ UHZDUG SDWWHUQV DQGPXOWLPRGDO LQVWUXFWLRQV WKURXJK D WUDLQLQJ WDVN KDV FHUWDLQDGYDQWDJHV RYHU WKH FXUUHQW SUDFWLFH RI XVLQJ KDUGZLUHG
FRPPDQGVIRUFRQWUROOLQJDURERWDQGJLYLQJIHHGEDFNWRLW,W
DOORZV WKH XVHU WR JLYH PXOWLPRGDO UHZDUG DQG FRPPDQGVQDWXUDOO\ LQ KLV RU KHU SUHIHUUHG ZD\ ZLWKRXW UHVWULFWLRQVFRQFHUQLQJ ZRUGV JUDPPDU RU HYHQ WKH ODQJXDJH XVHG
0RUHRYHU LW WUDQVIHUV WKH QHFHVVDU\ HIIRUW RI OHDUQLQJ DQGUHPHPEHULQJWKHFRUUHFWZD\RILQWHUDFWLQJIURPWKHXVHUWRWKHURERWZKLOHDWWKHVDPHWLPHDYRLGLQJWKHSLWIDOOVRIIXOO\0DQXVFULSWUHFHLYHG0DUFKWK
$QMD $XVWHUPDQQ LV ZLWK WKH *UDGXDWH 8QLYHUVLW\ IRU $GYDQFHG 6WXGLHV
62.(1'$, 7RN\R-DSDQ HPDLODQMD#QLLDFMS 
6HLML<DPDGDLVZLWKWKH1DWLRQDO,QVWLWXWHRI,QIRUPDWLFVDQGWKH*UDGXDWH
8QLYHUVLW\ IRU $GYDQFHG 6WXGLHV 62.(1'$,   7RN\R -DSDQHPDLOVHLML#QLLDFMS 

QDWXUDOODQJXDJHSURFHVVLQJ,QFRQWUDVWWRRWKHUVWXGLHVWKH
SURSRVHG DSSURDFK GRHV QRW DLP DW HQDEOLQJ URERWV WR
XQGHUVWDQGHYHU\GD\FRQYHUVDWLRQEXWDWPDNLQJDURERWOHDUQWR GHDO ZLWK VWULFWO\ WDVNUHODWHG FRPPXQLFDWLRQ OLNHFRPPDQGV DQG UHZDUGV 7KH SURSRVHG PHWKRG IRU XVHUDGDSWDWLRQUHVHPEOHVWKHZD\KXPDQVWHDFKFRPPDQGVWRSHWGRJV ,W LV GHVLJQHG WR EH LQWHJUDWHG LQWR D SHUVRQDOVHUYLFHURERWRUSHWURERWWRHQDEOHLWWRDGDSWWRWKHZD\LWV
XVHUZDQWVWRDFFHVVLWVVHUYLFHRUHQWHUWDLQPHQWIXQFWLRQVE\QDWXUDOPXOWLPRGDOFRPPDQGVRUUHZDUG
,Q RXU OHDUQLQJ PHWKRG WKH URERW DQG WKH XVHU KDYH WR
FRPSOHWHDFRRSHUDWLYHWUDLQLQJWDVNWRDGDSWWRHDFKRWKHU
7KH WUDLQLQJ SKDVH KDV WR EH FRPSOHWHG EHIRUH DFWXDOO\SXWWLQJ WKH URERW LQWR VHUYLFH :KLOH WKH PDLQ JRDO RI WKHWUDLQLQJWDVNLVWRHQDEOHWKHURERWWROHDUQWKHZD\LWVXVHULQWHUDFWVZLWKLWLWDOVRSURYLGHVDQHQYLURQPHQWIRUWKHXVHUWR OHDUQ KRZ WKH URERW H[SUHVVHV LWVHOI LQ D VLPSOH
HDV\WRXQGHUVWDQGVFHQDULRZKHUHPLVXQGHUVWDQGLQJVGRQRW
KDYHDQ\QHJDWLYHFRQVHTXHQFHV,QWKLVSDSHUZHDUHIRFXVLQJRQOHDUQLQJSDWWHUQVWKDWWKH
XVHU DSSOLHV IRU JLYLQJ SRVLWLYH DQG QHJDWLYH UHZDUG WR WKHURERW¶V EHKDYLRU DV D ILUVW VWHS WRZDUGV OHDUQLQJ PRUHFRPSOLFDWHG PXOWLPRGDO LQWHUDFWLRQ SDWWHUQV )XUWKHU
H[SODQDWLRQVIRUWKLVGHFLVLRQDUHJLYHQLQVHFWLRQ,,,%
,QILUVWH[SHULPHQWVZHHYDOXDWHGWKHVHFRQGFRQGLWLRQLQJEDVHG VWDJH RI RXU OHDUQLQJ PHWKRG DQG LQYHVWLJDWHG RQ WKHHIIHFWVRIUHVWULFWLRQVLQDOORZHGUHZDUGEHKDYLRU
,, 5(/$7(':25.
7HFKQLTXHV WR DFTXLUH QHZ ZRUGV>@>@ RU JHVWXUHV>@
WKURXJKKXPDQURERWLQWHUDFWLRQKDYHEHHQUHVHDUFKHGXSRQLQUHFHQW\HDUVDVDSDUWRIWKHUHVHDUFKRQV\PEROJURXQGLQJ
IRUQDWXUDOODQJXDJHDFTXLVLWLRQ/HHHWDOGHVFULEHGDQDSSURDFK>@IRUWKHRQOLQHOHDUQLQJRIKXPDQJHVWXUHVLQ+XPDQ5RERW,QWHUDFWLRQ7KHLUV\VWHPLV EDVHG RQ WKH RQOLQHWUDLQLQJ RI +LGGHQ 0DUNRY 0RGHOVXVLQJ JHVWXUH LQIRUPDWLRQ UHFRUGHG E\ D GDWD JORYH 7KHV\VWHP ZDV DEOH WR UHFRJQL]H  JHVWXUHV IURP WKH VLJQODQJXDJHDOSKDEHWZLWKDQHUURUUDWHRIDIWHUREVHUYLQJWUDLQLQJLQVWDQFHVRIHDFKJHVWXUH,ZDKDVKL GHVFULEHG DQ DSSURDFK >@ WR WKH DFWLYH DQGXQVXSHUYLVHG DFTXLVLWLRQ RI QHZ ZRUGV IRU WKH PXOWLPRGDOLQWHUIDFH RI D URERW +H DSSOLHV +LGGHQ 0DUNRY 0RGHOV WR
OHDUQYHUEDOUHSUHVHQWDWLRQVRIREMHFWVSHUFHLYHGE\DVWHUHRFDPHUD7KHOHDUQLQJFRPSRQHQWXVHVSUHWUDLQHG+00VDVDEDVLVIRUOHDUQLQJDQGLQWHUDFWVZLWKLWVXVHULQRUGHUWRDYRLG

4097
c
978-1-4244-1823-7/08/$25.002008
IEEE



DQGUHVROYHPLVXQGHUVWDQGLQJV
.D\LNFLHWDO>@XVH+LGGHQ0DUNRY0RGHOVDQGDQHXUDODVVRFLDWLYH PHPRU\ IRU OHDUQLQJWR XQGHUVWDQG VKRUW VSHHFKFRPPDQGVLQDWKUHHVWDJHGUHFRJQLWLRQSURFHGXUH)LUVWWKH
V\VWHPUHFRJQL]HVDVSHHFKVLJQDODVDVHTXHQFHRIGLSKRQHV
RUWULSKRQHV,QWKHQH[WVWHSWKHVHTXHQFHVDUHWUDQVODWHGLQWRZRUGV XVLQJ D QHXUDO DVVRFLDWLYH PHPRU\ 7KH ODVW VWHSHPSOR\V D QHXUDO DVVRFLDWLYH PHPRU\ WR ILQDOO\ REWDLQ D
VHPDQWLFUHSUHVHQWDWLRQRIWKHXWWHUDQFH
,Q WKH VDPH ZD\ DV WKH DSSURDFKHV RXWOLQHG DERYH RXUOHDUQLQJ DOJRULWKP DWWHPSWV DW DVVLJQLQJ D PHDQLQJ WR DQ
REVHUYHG DXGLWRU\ RU YLVXDO SDWWHUQ +RZHYHU WKH V\VWHP LV
QRW WU\LQJ WR OHDUQ WKH PHDQLQJ RI LQGLYLGXDO ZRUGV RU
V\PEROV EXW IRFXVHV RQ OHDUQLQJ FKDUDFWHULVWLF EHKDYLRUSDWWHUQVH[SUHVVLQJFRPPDQGVRUUHZDUGVDVDZKROH7KRVH
H[SUHVVLRQVFDQEHZRUGVRUJHVWXUHVDVLQWKHVWXGLHVDERYH
EXWDOVRSURVRGLFSDWWHUQVRUXWWHUDQFHVFRQVLVWLQJRIPXOWLSOHZRUGV0RUHRYHURXUSURSRVHGDSSURDFKLVQRWOLPLWHGWRDVLQJOH PRGDOLW\ VXFK DV RQO\ ZRUGV RUJHVWXUHV EXW WULHV WR
LQWHJUDWHREVHUYDWLRQVIURPGLIIHUHQWPRGDOLWLHV,QWKLVZRUN+LGGHQ0DUNRY0RGHOVDUHHPSOR\HGIRUWKH
ORZOHYHO PRGHOLQJ RI VSHHFK SURVRG\ JHVWXUH DQG WRXFK
SDWWHUQV$VDVWDQGDUGDSSURDFKIRUWKHFODVVLILFDWLRQRIWLPH
VHULHV GDWD +LGGHQ 0DUNRY 0RGHOV DUH ZLGHO\ XVHG LQ
OLWHUDWXUH7KHXVHRI0HO)UHTXHQF\&HSVWUXP&RHIILFLHQWV0)&& IRU+00EDVHGVSHHFKUHFRJQLWLRQLVGHVFULEHGLQ>@$SSURSULDWHIHDWXUHVHWVIRUHPRWLRQDIIHFWLYHLQWHQWDQG
JHVWXUH UHFRJQLWLRQ DUH RXWOLQHG LQ >@>@>@ DQG >@
UHVSHFWLYHO\ 7KRVH WULHG DQG WHVWHG IHDWXUHVHWV DUH XVHG LQ
RXUZRUNDVDQLQSXWIRUWKH+00EDVHGORZOHYHOOHDUQLQJSKDVH
)RU WKH KLJKOHYHO OHDUQLQJ RI DVVRFLDWLRQV EHWZHHQ WKHPHDQLQJ RI FRPPDQGV DQG UHZDUGV DQG WKHLU DSSURSULDWH
+LGGHQ0DUNRY0RGHOUHSUHVHQWDWLRQVFODVVLFDOFRQGLWLRQLQJLVXVHG0DWKHPDWLFDOWKHRULHVRIFODVVLFDOFRQGLWLRQLQJZHUH
H[WHQVLYHO\ UHVHDUFKHG XSRQ LQ WKH ILHOG RI FRJQLWLYH
SV\FKRORJ\$QRYHUYLHZFDQEHIRXQGLQ>@
7KH UHODWLRQ RI FODVVLFDO FRQGLWLRQLQJ WR WKH SKDVH RI
OHDUQLQJ ZRUG PHDQLQJV LQ KXPDQ VSHHFK DFTXLVLWLRQ KDV
EHHQ SRVWXODWHG LQ WKH ERRN ³9HUEDO %HKDYLRXU´ E\ % )
6NLQQHU >@ DQG KDV EHHQ DGRSWHG DQG PRGLILHG E\
UHVHDUFKHUVLQWKHILHOGRI%HKDYLRU$QDO\VLV,Q>@6WDDWVHW
DO GHVFULEH DQ HDUO\ DSSURDFK WR H[SODLQKXPDQOHDUQLQJ RI
ZRUGPHDQLQJVE\FODVVLFDOFRQGLWLRQLQJ$QH[SODQDWLRQRI
PRUH FRPSOH[ SKHQRPHQD LQ OHDUQLQJ ZRUG PHDQLQJV E\
FRQGLWLRQLQJ LV GHVFULEHG E\ % /RZHQNURQ LQ >@ 2XUPHWKRGLVEDVHGRQWKHSV\FKRORJLFDOEDFNJURXQGH[SODLQHG
LQWKHVHZRUNV2XUUHTXLUHPHQWVIRUFKRRVLQJDQDSSURSULDWHFRQGLWLRQLQJ PRGHO WR OHDUQ PXOWLPRGDO FRPPDQGV DUHRXWOLQHGLQVHFWLRQ,9&RIWKLVSDSHU
5HFHQWO\ WKHUH KDYH EHHQ VHYHUDO VWXGLHV FRQFHUQLQJ WKHZD\ WKDW KXPDQV OLNH WR WHDFK URERWV RU RWKHU DUWLILFLDOFUHDWXUHV VXFK DV YLUWXDO FKDUDFWHUV  +RZHYHU DV IDU DV
VSHHFK RU JHVWXUH LV XVHG LQ WKHVH VWXGLHV LW LV W\SLFDOO\UHVWULFWHGWRIL[HGVHQWHQFHSDWWHUQVDQGDOLPLWHGYRFDEXODU\RISUHWUDLQHGJHVWXUHVRUZRUGV<DPDGDHWDOGHVFULEHGDQDSSURDFKWRPXWXDODGDSWDWLRQ
EHWZHHQDKXPDQDQGDQ$,%2W\SHURERWEDVHGRQFODVVLFDOFRQGLWLRQLQJ XVLQJWKH .ORSI QHXURQPRGHO >@ :KLOH WKHURERW OHDUQHG WR LQWHUSUHW WKH KXPDQ V FRPPDQGV JLYHQ E\
SUHVVLQJ RQH RI WKH EXWWRQV RQ WKH URERW V EDFN WKH KXPDQIRXQGRXWLQWKHFRXUVHRIWKHH[SHULPHQWVKRZWRFRUUHFWO\JLYHFRPPDQGVWRWKHURERW
7KH XVH RI SRVLWLYH DQG QHJDWLYH UHZDUG IURP D KXPDQLQVWUXFWRUWR WHDFKDURERW ZDV LQYHVWLJDWHG XSRQLQ VHYHUDOVWXGLHV/RFNHUGHWDOGHVFULEHGDQH[SHULPHQWDOVHWWLQJIRU
DVVHVVLQJ KXPDQ UHZDUG EHKDYLRU DQG LWV FRQWLQJHQF\ >@
7KH SDUWLFLSDQWV RI WKH VWXG\ FRXOG JLYH SRVLWLYH DV ZHOO DV
QHJDWLYHUHZDUGWRWHDFKWKHYLUWXDOFKDUDFWHU6RSKLHWREDNHD
FDNHLQWKH6RSKLH V:RUOGVFHQDULR5HZDUGFRXOGEHJLYHQ
E\ DQ LQWHUDFWLYH UHZDUG LQWHUIDFH WKDW DOORZHG WKH XVHU WR
DVVLJQDQ\UHZDUGRQDVFDOHIURPWRHLWKHUWRDFHUWDLQREMHFW RU WR WKH ZRUOG VWDWH 7KH FKDUDFWHU OHDUQHG IURP D
KXPDQ WHDFKHU E\ WKLV NLQG RI UHLQIRUFHPHQW ,Q WKHLU
H[SHULPHQWVWKH\IRXQGDVWURQJELDVWRZDUGVSRVLWLYHUHZDUG
DQG GLVFRYHUHG D SKHQRPHQRQ WKDW WKH\ GHVFULEHG DV
DQWLFLSDWRU\UHZDUGVSRVLWLYHUHZDUGVWKDWZHUHDVVLJQHGWRDQREMHFWWKDWWKHFKDUDFWHUKDVWRXVHLQDODWHUVWHS7KLVNLQG
RIUHZDUGFDQEHLQWHUSUHWHGDVJXLGDQFHIRUWKHFKDUDFWHU,,, 7+(75$,1,1*3+$6(
7KHWUDLQLQJSKDVHWKDWLVXVHGWRDGDSWWKHURERWWRLWVXVHUDQGYLFHYHUVDKDVWRIXOILOOFHUWDLQUHTXLUHPHQWV$VWKHURERWGRHVQRWKDYHDQ\SULRUNQRZOHGJHDERXWLWVXVHUDQGKLVZD\RI LQWHUDFWLQJ DW WKH EHJLQQLQJ RI WKH WUDLQLQJ SKDVH WKHWUDLQLQJ WDVN QHHGV WR EH VSHFLILFDOO\ GHVLJQHG WR DOORZ WKHURERW WR DQWLFLSDWH ZKDW LQVWUXFWLRQ DQG UHZDUG WKH XVHU LV
JRLQJWRJLYHDWDQ\JLYHQWLPHGXULQJWDVNH[HFXWLRQ$ 5HTXLUHPHQWV/HDUQLQJ WKH PHDQLQJ RI XVHU EHKDYLRU E\ RXU OHDQLQJPHWKRGLVRQO\SRVVLEOH ZLWKLQDWDVNWKDWKDVWKHIROORZLQJSURSHUWLHV 7KHURERWDVZHOODVWKHXVHUNQRZWKHWDUJHWVWDWHLQ
DGYDQFH
 7KHRUGHURIVWHSVOHDGLQJIURPWKHFXUUHQWVWDWHWRWKH
WDUJHWVWDWHLVGHWHUPLQHGXQDPELJXRXVO\E\JLYLQJDWDUJHWVWDWH
,Q D VFHQDULR OLNH WKDW WKHURERW FDQ DQWLFLSDWH WKHXVHU V)LJXUH6DPSOHWUDLQLQJWDVN

4098

2008 IEEE Congress on Evolutionary Computation (CEC 2008)


UHZDUGEDVHGRQLWVNQRZOHGJHDERXWWKHWDUJHWVWDWHDQGWKH
FXUUHQWVWDWHRIWKHWDVNH[HFXWLRQ,WFDQSURYRNHSRVLWLYHDQG
QHJDWLYH UHZDUG E\ FRUUHFWLQFRUUHFW EHKDYLRU WKDW LVEHKDYLRUWKDWGRHVRUGRHVQRWOHDGWRWDUJHWVWDWHDQGLWFDQ
SURPSW WKHXVHU IRUWKHQH[WLQVWUXFWLRQLI QR LQWHUDFWLRQ LV
REVHUYHG
7KHUHTXLUHPHQWWKDWWKHRUGHURIVWHSVIRUWDVNH[HFXWLRQ
PXVW EH IL[HG PD\ DSSHDU TXLWH VWURQJ +RZHYHU LQ D
VFHQDULRZKHUHWKHURERWGRHVQRWKDYHDQ\SULRUNQRZOHGJH
DERXW WKH XVHU DQG KLV ZD\ RI JLYLQJ FRPPDQGV WKLV LV
QHFHVVDU\ EHFDXVH RWKHUZLVH ILQHJUDLQHG LQVWUXFWLRQ IURPWKHXVHUPLJKWOHDGWRDVLWXDWLRQZKHUHDQDFWLRQRIWKHURERWGRHV QRW FRUUHVSRQG WR WKH XVHU¶V LQVWUXFWLRQV DOWKRXJK LW
OHDGVWRWKHGHVLUHGILQDOVWDWH)RUH[DPSOHLQDWDVNZLWKWKH
WDUJHWVWDWH7KHUHGDQGWKHEOXHODPSDUHVZLWFKHGRQWKH
XVHUPD\JLYHWKHGHWDLOHGLQVWUXFWLRQ)LUVWVZLWFKRQWKHUHGODPS 1RZ VZLWFKLQJ RQ WKH EOXH ODPS ILUVW EHFRPHVLQFRUUHFWDOWKRXJKLWOHDGVWRWKHFRUUHFWILQDOVWDWH:LWKRXWXQGHUVWDQGLQJWKHXVHU¶VLQVWUXFWLRQVWKHUHLVQRZD\IRUWKH
URERWWRFRUUHFWO\GHDOZLWKWKLVNLQGRIVLWXDWLRQ7KHUHIRUH
WKH URERW KDV WR EH DEOH WR LQIHU WKH RUGHU RI VWHSV IURPNQRZLQJWKHWDUJHWVWDWH
$ VLPSOH H[DPSOH IRU D WUDLQLQJ WDVN WKDW SRVVHVVHV WKHGHVLUHGSURSHUWLHVDQGWKDWZDVXVHGRXUILUVWH[SHULPHQWLVPRYLQJ D FRORUHG REMHFW WR D FRORUPDUNHG SODFH 7KHH[SHULPHQWDOVHWWLQJFDQEHVHHQLQ)LJXUH:KHQWKHREMHFWDQGWKHWDUJHWSODFHDUHNQRZQWRWKHXVHUDVZHOODVWKHURERWWKHVWHSVOHDGLQJWRWKHJRDODUHIL[HGDQGWKHLURUGHUFDQQRWEH LQWHUFKDQJHG :KLOH WKH XVHU LQVWUXFWV WKHURERW IHHO\ E\
PHDQVRIKLVQDWXUDOO\XVHGVSHHFKDQGJHVWXUHSDWWHUQVWKH
URERWDQWLFLSDWHVWKHXVHU VFRPPDQGVIURPLWVNQRZOHGJHRIWKHWDUJHWVWDWHDQGWKHFXUUHQWVWDWHRIWKHWDVNH[HFXWLRQDQG
VKRZV HLWKHU FRPSOLDQW EHKDYLRU DQG H[SHFWV DQG OHDUQVSRVLWLYHUHZDUGRUVKRZVQRQFRPSOLDQWEHKDYLRUH[SHFWLQJQHJDWLYHUHZDUG% 7DUJHWRI/HDUQLQJ
7KHJRDORIRXUUHVHDUFKLVWRGHYHORSDPHWKRGWROHDUQFRPPDQGVDVZHOODVSRVLWLYHDQGQHJDWLYHUHZDUGVWKDWFDQ
EH XVHG IRU FRQWUROOLQJ WKH VHUYLFH DQG HQWHUWDLQPHQW
IXQFWLRQV RI VHUYLFHURERWV DQG SHWURERWV WKURXJK WKHLQWHUDFWLRQZLWKDXVHU:HFKRVHWKHOHDUQLQJRISRVLWLYHDQG
QHJDWLYH UHZDUGV DVWKH VWDUWLQJ SRLQW RI RXU ZRUN EHFDXVH
WKH\DUHWKHVPDOOHVWXVHIXOVHWRIFRPPDQGVWKDWFDQEHXVHG
WRWHDFKDURERWIRUH[DPSOHE\UHLQIRUFHPHQWOHDUQLQJ
7KHUH DUH WZR PDLQ SRLQWV WKDW PDNH OHDUQLQJ UHZDUGVHDVLHUWKDQOHDUQLQJW\SLFDORWKHUFRPPDQGV5HZDUGVDUHW\SLFDOO\QRWSDUDPHWHUL]HG:KLOHFRPPDQGV
FDQ WDNH VHYHUDO SDUDPHWHUV VXFK DV LQ ³JR IRUZDUG! 
P!´RU³SXWWKHFRIIHHFXS!RQWKHGHVN!´ZKLFKQHHGWR
EH SURFHVVHG IRU XQGHUVWDQGLQJ WKH FRPPDQG FRUUHFWO\UHZDUGVFDQEHXQGHUVWRRGDVSRVLWLYHRUQHJDWLYHZLWKRXWWKH
QHHG IRU SURFHVVLQJ SDUDPHWHUL]DWLRQ 7KHUHIRUH D UHZDUG
FDQEHPRGHOHGDVDVLQJOH+LGGHQ0DUNRY0RGHOZKLOHWKH
SURFHVVLQJRIDUELWUDU\FRPPDQGVZKLFKLVWKHQH[WVWHSLQ
RXU ZRUN QHHGV WR SURYLGH D PHDQV IRU FRPELQLQJ +00V
PRGHOLQJ FRPPDQGV DQG WKHLU SDUDPHWHUV DQG VHJPHQWLQJFRPPDQGVDQGSDUDPHWHUVGXULQJWKHWUDLQLQJSKDVH$SDUW IURP WKDW UHZDUGV FDQ RQO\ KDYH WZR PHDQLQJVSUDLVH RU SXQLVKPHQW DQG ZKLOH YDU\LQJ VWURQJO\ EHWZHHQGLIIHUHQW SHRSOH WKH QXPEHU RI GLIIHUHQW SRVLWLYH DQGQHJDWLYH UHZDUG SDWWHUQV XVHG E\ DQ LQGLYLGXDO LV OLPLWHG
7KLVOHDGVWRDUHGXFWLRQRIWKHQHFHVVDU\DPRXQWRIWUDLQLQJGDWDFRPSDUHGWRWKHOHDUQLQJRIPRUHFRPSOH[DQGQXPHURXVLQVWUXFWLRQSDWWHUQV& $VVXPSWLRQV
7KLV UHVHDUFK UHOLHV RQ WKH DVVXPSWLRQ WKDW SDWWHUQV RI
LQWHUDFWLRQ EHWZHHQ KXPDQV DQG URERWV UDQJH IURP UDWKHUXQLYHUVDORQHVOLNHSRLQWLQJJHVWXUHVZKLFKDUHURXJKO\WKH
VDPH EHWZHHQ GLIIHUHQW LQGLYLGXDOV WR KLJKO\ LQGLYLGXDOSDWWHUQV OLNH JLYLQJ SRVLWLYHQHJDWLYH UHZDUG 3DWWHUQV WKDWDUHXQLYHUVDOFDQEHSUHWUDLQHGDQGDGDSWHGWRDFHUWDLQXVHUGXULQJ WDVN H[HFXWLRQ 2QO\ SDWWHUQV WKDW YDU\ VXEVWDQWLDOO\EHWZHHQ XVHUV QHHG WR EH WUDLQHG LQ D WUDLQLQJ SKDVH WKDWSUHFHGHVWKHDFWXDOXVHRIWKHURERW:HIXUWKHUDVVXPHWKDWHDFKXVHUKDVDOLPLWHGLQYHQWRU\RILQWHUDFWLRQSDWWHUQVWRH[SUHVVDFHUWDLQFRPPDQGRUUHZDUG
7KHLQWHUDFWLRQ SDWWHUQVWKDW DUH W\SLFDOO\ XVHG FDQ FKDQJHVORZO\RYHUWLPH0RUHRYHULQWHUDFWLRQSDWWHUQVXVHGE\RQH
XVHUIRUWKHVDPHLQVWUXFWLRQGRQRWYDU\H[FHVVLYHO\EHWZHHQGLIIHUHQWWDVNV7KHWHUP³PXOWLPRGDOUHZDUGSDWWHUQ´LVXVHG
LQWKLVSDSHUWRUHIHUWRDWLPHVHTXHQFHRIREVHUYDWLRQVWKDWSRVVHVVHVWKHIROORZLQJSURSHUWLHV ,WFRQVLVWVRISHUFHSWLRQVLQRQHRUPRUHPRGDOLWLHV ,W EHJLQV E\ DQ LQFUHDVH LQ DFWLYLW\ LQ RQH RI WKHPRGDOLWLHV HJYRLFHRQVHW  ,WHQGVE\DSHULRGRILQDFWLYLW\LQDOOPRGDOLWLHV $FWLRQV LQ GLIIHUHQW PRGDOLWLHV RFFXU LQ FORVH WLPHO\UHODWLRQ WKDW LV DW WKH VDPH WLPH RU LQ D VHTXHQFH
TXLFNO\IROORZLQJRQHDQRWKHU 7KHSHUFHSWLRQVIROORZDEHKDYLRURIWKHURERWWKDWFDQ
EHFOHDUO\DWWULEXWHGDSRVLWLYHRUQHJDWLYHYDOXH
,9 /($51,1*0(7+2'$ 2YHUYLHZ
7KHOHDUQLQJDOJRULWKPLVGLYLGHGLQWRWZRVWDJHVZKLFKDUH
H[HFXWHG DIWHU HDFK RI WKH XVHU¶V DFWLRQV GXULQJ WKH WUDLQLQJSKDVH ,Q WKH UHZDUG UHFRJQLWLRQ OHDUQLQJ VWDJH +LGGHQ0DUNRY 0RGHOV DUH WUDLQHG WR UHFRJQL]H JHVWXUHVWRXFKVHTXHQFHV XWWHUDQFHV DQG SURVRGLF SDWWHUQV ,Q WKHUHZDUG DVVRFLDWLRQ OHDUQLQJ VWDJH WKH WUDLQHG +LGGHQ0DUNRYPRGHOVDUHDVVRFLDWHGZLWKHLWKHUSRVLWLYHRUQHJDWLYHUHZDUGV XVLQJ D PDWKHPDWLFDO PRGHO RI FODVVLFDOFRQGLWLRQLQJ
([WHQGLQJ D +00EDVHG UHFRJQL]HU E\ D VHFRQG
FRQGLWLRQLQJEDVHGOHDUQLQJVWDJHKDVFHUWDLQDGYDQWDJHVDQG
DGGUHVVHV SUREOHPV WKDW FDQQRW EH VROYHG E\ +00V DORQH
:KLOH LW FDQ EHQHILW IURP WKH KLJK SHUIRUPDQFH RI +00VZKLFK DUH ZLGHO\ FRQVLGHUHG VWDWHRIWKHDUW IRU WKHFODVVLILFDWLRQRIWLPHVHULHVGDWDRXUPRGHOKDVWRGHDOZLWKWKHSUREOHPWKDWWKHUHLVQRRQHWRRQHUHODWLRQVKLSEHWZHHQPHDQLQJV ± LQ WKLV FDVH UHZDUGV ± DQG WKHLU H[SUHVVLRQ LQ

2008 IEEE Congress on Evolutionary Computation (CEC 2008)

4099



VSHHFKSURVRG\WRXFKRUJHVWXUH(YHQDVLQJOHXVHUHPSOR\VPXOWLSOH ZD\V RI H[SUHVVLQJ SRVLWLYH DQG QHJDWLYH UHZDUGV
DQGWKHUHDUHH[SUHVVLRQVWKDWFDQKDYHDSRVLWLYHRUQHJDWLYH
PHDQLQJ GHSHQGLQJ RQ WKH FRQWH[W VXFK DV IRU LQVWDQFH
FDOOLQJWKHURERW¶V QDPH $V DQ +00 FDQ RQO\ UHSUHVHQW D
GLUHFW UHODWLRQVKLS RI D VHTXHQFH RI REVHUYDWLRQV WR LWVXQGHUO\LQJPRVWSUREDEOHFRUUHVSRQGLQJXWWHUDQFHRUJHVWXUH
LWLVQHFHVVDU\WRKDYHDVHFRQGVWDJHRIOHDUQLQJZKHUHWKH
FRQQHFWLRQV EHWZHHQ WKH GLIIHUHQW XWWHUDQFHV JHVWXUHV DQGSURVRGLF SDWWHUQV UHSUHVHQWHG E\ +LGGHQ 0DUNRY 0RGHOV
DQGWKHLUPHDQLQJLQWKLVFDVHSRVLWLYHRUQHJDWLYHIHHGEDFNDUHOHDUQHG:HFKRVHFRQGLWLRQLQJDVDELRORJLFDOO\LQVSLUHG
DSSURDFKDV LWKDVDQXPEHU RI GHVLUDEOH SURSHUWLHV ZKLFKDUH RXWOLQHG LQ VHFWLRQ ,9& RI WKLV SDSHU 0RUHRYHU LW LV
DVVXPHG WKDW D VLPLODU IRUP RI OHDUQLQJ WDNHV SODFH ZKHQGRJVOHDUQWRXQGHUVWDQGFRPPDQGVIURPWKHLUFDUHJLYHU
$QRYHUYLHZRIWKHLPSOHPHQWHGV\VWHPLVJLYHQLQ)LJXUH
7KHVRIWZDUHLVVHSDUDWHGLQWRWKHURERWFRQWUROVRIWZDUHLWVHOIDQG D WUDLQHU SURJUDP ZKLFK LV WDLORUHG WRZDUGV D VSHFLILF
WUDLQLQJWDVN,WSRVVHVVHVDOOLQIRUPDWLRQQHHGHGWRVROYHWKH
WDVN DQG HYDOXDWHV WKH FXUUHQW VLWXDWLRQ WKDW WKH URERW LV LQ
%DVHGRQLWVNQRZOHGJHDERXWWKHWUDLQLQJWDVNDQGLWVGHVLUHG
RXWFRPHLWVHQGVFRPPDQGVDQGSURYLGHVUHZDUGVLJQDOVWRWKHURERW
,QDQDORJ\WRFRQGLWLRQLQJLQUHDODQLPDOVWKHUHZDUGIURPWKH WUDLQHU DSSOLFDWLRQ FDQ EH LQWHUSUHWHG DV VRPHLPPHGLDWHO\ SDLQIXO RU SOHDVDQW VLJQDO ZKLFK VHUYHV DV DQ
XQFRQGLWLRQHG VWLPXOXV 86  7KH URERW VRIWZDUH LV DEOH WR
OHDUQWKHDVVRFLDWLRQEHWZHHQWKHXVHU VEHKDYLRUUHSUHVHQWHG
E\DWUDLQHG+00ZKLFKEHFRPHVWKHFRQGLWLRQHGVWLPXOXV&6 DQGWKHUHZDUGIURPWKHWUDLQHUSURJUDP 86 ,Q)LJXUH SRVLWLYHQHJDWLYH UHZDUGV DUH GHQRWHG E\  7KHFRQGLWLRQHGDVVRFLDWLRQVEHWZHHQWKHUHZDUGVDQGWKH+00V
IRUUHZDUGUHFRJQLWLRQDUHVKRZQDVGDVKHGOLQHVFRQQHFWLQJUHZDUGV DQG +00V LQ WKH ULJKW SDUW RI WKH LPDJH $Q
RYHUYLHZ RI WKH OHDUQLQJ DOJRULWKP WKDW LV XVHG WR WUDLQ WKH
+00VDQGDVVRFLDWLRQVLVVKRZQLQ)LJ,WLVGHVFULEHGLQ
GHWDLOLQVHFWLRQV,9%DQG,9&% 5HZDUG5HFRJQLWLRQ/HDUQLQJ$VHWRISUHWUDLQHG+00VIRUHDFKRIWKHIRXUPRGDOLWLHV
VSHHFK VSHHFK SURVRG\ WRXFK DQG JHVWXUH LV FUHDWHG IURPSUHUHFRUGHG VHQVRU DXGLR DQG YLGHR GDWD LQ RUGHU WR
PLQLPL]HWKHQHHGIRUWUDLQLQJVDPSOHVIURPHDFKLQGLYLGXDOXVHU 7KH LQLWLDO +00VHW IRU VSHHFK UHFRJQLWLRQ FRQWDLQVPRQRSKRQH PRGHOV 7KH PRGHOV DUH EDVHG RQ VWDQGDUG
0)&& IHDWXUHYHFWRUV H[WUDFWHG IURP WKH UHFRUGHG VSHHFKGDWD
7KH+00VHWIRUSURVRG\UHFRJQLWLRQLVEDVHGRQIHDWXUHV
H[WUDFWHG IURP WKH SLWFK DQG HQHUJ\ FRQWRXUVDV ZHOODV WKHIUHTXHQF\ GLVWULEXWLRQ SUHVHQW LQ HDFK IUDPH RI WKH VSHHFKVLJQDO WKDW DUH W\SLFDOO\ XVHG IRU UHFRJQL]LQJ HPRWLRQ RU
DIIHFWLYH LQWHQW LQ VSHHFK >@>@ )LUVW WULDOV DUH GRQH ZLWKVWDQGDUG OHIWULJKW +00V EXW WKHUH LV VRPH HYLGHQFH LQ
OLWHUDWXUH >@ RQ HPRWLRQ UHFRJQLWLRQ IURP VSHHFKVXJJHVWLQJ WKDW HUJRGLF +00V PD\ EH EHWWHU VXLWHG IRUUHFRJQL]LQJSURVRG\4100)LJXUH2YHUYLHZRIWKHV\VWHP

7KH +00VHW IRU JHVWXUH UHFRJQLWLRQ EDVHV RQ IHDWXUHVGHVFULELQJWKHUHODWLYHSRVLWLRQVRIWKHKDQGVDQGWKHIDFHRIDSHUVRQ7KHSRVLWLRQVDUHH[WUDFWHGIURPWKHVWHUHRLPDJHRIWZR FDPHUDV DQG WUDFNHG RYHU PXOWLSOH IUDPHV LQ RUGHU WR
GHWHUPLQHWKHWUDMHFWRULHVRIWKHXVHU¶VIDFHDQGKDQGV
7KH+00VHWWKDWLVXVHGWROHDUQWRXFKLQJSDWWHUQVVXFKDVVWURNLQJSDWWLQJRUKLWWLQJWKHURERWXVHVIHDWXUHYHFWRUVFRQWDLQLQJ WKH YDOXHV UHWXUQHG E\ $,%2¶V WDFWLOH KHDG DQGEDFNWRXFKVHQVRUVDQGE\WKHSDZWRXFKVHQVRUV)RU HDFK RI WKH DERYH GHVFULEHG PRGDOLWLHV +LGGHQ0DUNRY0RGHOVDUHSUHWUDLQHGXVLQJDQLPSOHPHQWDWLRQRI
WKH %DXP:HOFKDOJRULWKP 7KH SUHWUDLQHG +00V DUHVWRUHGVHSDUDWHO\IRUHDFKPRGDOLW\LQDQ+00GDWDEDVH'XULQJ WKH WUDLQLQJ SKDVH ZLWK KXPDQ LQVWUXFWLRQREVHUYHG UHZDUG EHKDYLRU LQ HDFK RI WKH PRGDOLWLHV LV ILUVWSURFHVVHG E\ WKH 9LWHUEL DOJRULWKP LQ RUGHU WR PDWFK LW
DJDLQVWWKHSUHWUDLQHG+000RGHOVLQWKH+00GDWDEDVH,QWKLVVWDJHWKHPDWFKLQJLVGRQHRQLVRODWHGZRUGOHYHO
7KH IXOO XWWHUDQFH JHVWXUH RU WRXFKVHTXHQFH LV DVVXPHG WRFRUUHVSRQGWRRQH+00LQWKHGDWDEDVHDQGPDWFKHGDJDLQVW
HYHU\VLQJOH+00LQWKH+00GDWDEDVH7KHRXWSXWRIWKH
9LWHUEL DOJRULWKP LV WKH EHVWILWWLQJ +00 DORQJ ZLWK D
FRQILGHQFHYDOXH
,IWKHFRQILGHQFHYDOXHLVDERYHDWKUHVKROGWKH+00LVWUDLQHG ZLWKWKH REVHUYHG XWWHUDQFHSURVRG\JHVWXUH DQG WKHDSSOLFDWLRQSURFHHGVWRWKHUHZDUGDVVRFLDWLRQOHDUQLQJSKDVH
,I WKH FRQILGHQFH YDOXH RXWSXW E\ WKH 9LWHUEL DOJRULWKP LV
EHORZ WKH WKUHVKROG WKH UHFRJQL]HU LV H[HFXWHG DJDLQ 7KLVWLPH LW LV XVHG DV D FRQWLQXRXV UHFRJQLWLRQ EDVHG RQ DQ(%1)OLNH
JUDPPDU
GHVFULELQJWKH
SRVVLEOH
+00VHTXHQFHV IRU UHFRJQLWLRQ 7KH VHTXHQFH RI +00V
UHVXOWLQJ IURP WKLV H[HFXWLRQ RI WKH 9LWHUEL UHFRJQLWLRQ LV
PHUJHGLQWRDQHZ+007KHQHZ+00LVWUDLQHGZLWKWKH
XWWHUDQFHSURVRG\JHVWXUH DQG LQVHUWHG LQWR WKH +00GDWDEDVHIRUUHXVH
7KH FRQILGHQFH WKUHVKROG XVHG IRU GHFLGLQJ ZKHWKHU D
+00 ILWV WKH FXUUHQWO\ REVHUYHG XWWHUDQFH GHSHQGV RQ WKHQXPEHURILQVWDQFHVDOUHDG\XVHGWRWUDLQWKHPRGHODQGWDNHV
LQWR DFFRXQW WKH DVVRFLDWLYH VWUHQJWK SUHVHQW EHWZHHQ WKHFXUUHQWO\ H[SHFWHG UHZDUG DQG WKH FDQGLGDWH +00 %HIRUHFRPSDULQJWKHFRQILGHQFHYDOXHWRWKHWKUHVKROGWKHYDOXHLV
WLPHQRUPDOL]HGWRFRPSHQVDWHIRUGLIIHUHQWXWWHUDQFHOHQJWKV
7KH+00WKDWUHVXOWVIURPWKLVORZOHYHOFODVVLILFDWLRQDQG

2008 IEEE Congress on Evolutionary Computation (CEC 2008)


OHDUQLQJVWDJHWKDWLVWKH+00SURYLGLQJWKHPRVWDFFXUDWH
DYDLODEOH PRGHO RI WKH REVHUYHG XWWHUDQFHSURVRG\JHVWXUH
VHUYHVDVDQLQSXWIRUWKHUHZDUGDVVRFLDWLRQOHDUQLQJ& 5HZDUG$VVRFLDWLRQ/HDUQLQJThe reward association learning phase is based on thetheory of classical conditioning, which was first describedby I. Pavlov and originates from behavioral research inanimals. In classical conditioning, an association between anew, motivationally neutral stimulus, the so-called
conditioned stimulus (CS), and a motivationally meaningfulstimulus, the so-called unconditioned stimulus (US), islearned. The unconditioned stimulus produces anunconditioned reaction (UR) as a natural behavior. Aftercompleting training, which is done by repeatedly presenting
the conditioned stimulus just before the occurrence of theunconditioned stimulus, the conditioned stimulus is able toevoke the same reaction, when it is presented alone. This
reaction is called the conditioned reaction. Pavlov found thisrelationship while he was doing experiments investigating
the gastric function of dogs and measuring the amount of
their salivation in response to food. At first the dog did notshow any reaction to the tone of a bell (CS) but when the
dog was given food (US), it salivated (UR). After repeatedly
ringing the bell just before feeding the dog, the tone of thebell alone was able to make the dog salivate.
  5HOHYDQWIHDWXUHVRIFODVVLFDOFRQGLWLRQLQJFor our task of learning multimodal reward patterns,
certain properties of classical conditioning are of special
importance. The most important features of classicalconditioning for our application are blocking, extinction andsecond-order-conditioning
as
well
as
sensory
preconditioning:
The term blocking denotes the phenomenon that occurs,
when a CS1 is paired with a US, and then conditioning is
performed for a second CS2 to the same US. In this case, theexisting association between the CS1 and the US blocks thelearning of the association between the CS2 and the US. The
strength of the blocking is proportional to the strength of theexisting association between the CS1 and the US.
For the learning of multimodal interaction patterns,
blocking is helpful, as it allows the system to emphasize thestimuli that are most relevant. For instance, if a certain user

)LJXUH2YHUYLHZRIWKHWUDLQLQJDOJRULWKP

always touches the head of the robot for giving positive
reward, and sometimes provides different speech utterances
together with touching the robot, then learning an
association between positive reward and these speechutterances is blocked if there is already a strong association
between touching the head sensor and positive reward.
Extinction refers to the situation, where a CS that has
been associated with a US, is presented without the US. In
that case, the association between the CS and the US is
weakened. This capability is necessary to deal with changes
in user behavior and with mistakes, made during the training
phase, such as a misunderstanding of the situation by thehuman and a resulting incorrect reward.
Secondarypreconditioning
andsecond-orderconditioning describe the learning of an association between
a CS1 and a CS2, so that if the CS1 occurs together with theUS, the association of the CS2 towards the US is
strengthened, too. In sensory preconditioning, learning theassociation between CS1 and CS2 is established before
learning the association towards the US, in second-orderconditioning, the association between the US and CS1 islearned beforehand, and the association between CS1 andCS2 is learned later.
This property is important for our learning method, as itenables us, to learn connections between stimuli in different
modalities, as well as to continue learning associations
between stimuli given through different modalities even insituations, where no clear positive or negative feedback can
be given by the trainer function as long as new stimuli, suchas new gestures or commands are presented together withstimuli, that are already known and associated to a reward.
E.g. a new positive speech feedback is uttered with a typical,
known positive/negative prosody pattern.
  7KH5HVFRUOD:DJQHU0RGHO7KHUH DUH VHYHUDO PDWKHPDWLFDO WKHRULHV WU\LQJ WR PRGHOFODVVLFDOFRQGLWLRQLQJDVZHOODVWKHYDULRXVHIIHFWVWKDWFDQ
EH REVHUYHG ZKHQ WUDLQLQJ UHDO DQLPDOV XVLQJ WKHFRQGLWLRQLQJ SULQFLSOH  7KH PRGHOV GHVFULEH KRZ WKHDVVRFLDWLRQ EHWZHHQ DQ XQFRQGLWLRQHG VWLPXOXV DQG D
FRQGLWLRQHG VWLPXOXV LV DIIHFWHG E\ WKH RFFXUUHQFH DQGFRRFFXUUHQFHRIWKHVWLPXOL
,Q RXU ZRUN ZH HPSOR\ WKH 5HVFRUOD:DJQHUPRGHO >@ZKLFKZDVGHYHORSHGLQDQGKDVVHUYHGDVDIRXQGDWLRQ
IRU PRVW RI WKH PRUH VRSKLVWLFDWHG QHZHU WKHRULHV ,Q WKH5HVFRUOD:DJQHUPRGHOWKHFKDQJHRIDVVRFLDWLYHVWUHQJWKRI
WKH FRQGLWLRQHG VWLPXOXV $ WR WKH XQFRQGLWLRQHG VWLPXOXV86 Q LQWULDOQǻ9$ Q LVFDOFXODWHGDVLQ  
Ǎ9$ Q  Į$ȕ86 Q  Ȝ86 Q 9DOO Q    ǩ$ DQG ȕ86 Q  DUH WKH OHDUQLQJ UDWHV GHSHQGHQW RQ WKHFRQGLWLRQHG VWLPXOXV $ DQG WKH XQFRQGLWLRQHG VWLPXOXV86 Q  UHVSHFWLYHO\ Ȝ86 Q  LV WKH PD[LPXP SRVVLEOH
DVVRFLDWLYH VWUHQJWK RI WKH FXUUHQWO\ SURFHVVHG &6 WR WKH86 Q ,WLVDSRVLWLYHYDOXHLIWKH&6LVSUHVHQWZKHQWKH86
RFFXUV VR WKDW WKH DVVRFLDWLRQ EHWZHHQ 86 DQG &6 FDQ EH
OHDUQHG ,W LV ]HUR LI WKH 86 RFFXUV ZLWKRXW WKH &6 ,Q WKDW
FDVH ǻ9$ Q   EHFRPHV QHJDWLYH 7KXV WKH DVVRFLDWLYH
VWUHQJWKEHWZHHQWKH86DQGWKH&6GHFUHDVHV9DOO Q LVWKH

2008 IEEE Congress on Evolutionary Computation (CEC 2008)

4101



FRPELQHG DVVRFLDWLYH VWUHQJWK RI DOO FRQGLWLRQHG VWLPXOL ZLUHOHVVFRPPXQLFDWLRQWRZDUGVWKHFXUUHQWO\SURFHVVHGXQFRQGLWLRQHGVWLPXOXV7KH
)RU WKH DXGLR DQG YLGHR UHFRUGLQJ ZH XWLOL]H D SDLU RI
HTXDWLRQLVXSGDWHGRQHDFKRFFXUUHQFHRIWKHXQFRQGLWLRQHG /RJLWHFK )XVLRQ ZHEFDPV IRU VWHUHR YLVLRQ DV ZHOO DV D
VWLPXOXVIRUDOOFRQGLWLRQHGVWLPXOLWKDWDUHDVVRFLDWHGZLWKLW ZLUHOHVV ODYDOLHU PLFURSKRQH $,%2 LV FRQWUROOHG XVLQJ WKH
2QH DGYDQWDJH RI XVLQJ FRQGLWLRQLQJ DV DQ DOJRULWKP IRU 6RQ\ $,%2 5HPRWH )UDPHZRUN >@ 7KH VRIWZDUH XVHV WKHOHDUQLQJ WKH DVVRFLDWLRQV EHWZHHQ SRVLWLYHQHJDWLYH UHZDUG +7. >@ DV DQ LPSOHPHQWDWLRQ RI +LGGHQ 0DUNRY PRGHOV
DQG WKH XVHU V FRUUHVSRQGLQJ EHKDYLRUV LV LWV UDWKHU TXLFN DQG WKH UHOHYDQW DOJRULWKPV IRU UHFRJQLWLRQ DQG WUDLQLQJ DV
FRQYHUJHQFHGHSHQGLQJRQWKHOHDUQLQJUDWH
ZHOODVIXQFWLRQVIURPWKH2SHQ&9>@IRUYLGHRSURFHVVLQJ
,Q WKLV VWXG\ WKH OHDUQLQJ UDWHV IRU FRQGLWLRQHG DQG9, (;3(5,0(176XQFRQGLWLRQHGVWLPXOLDUHIL[HGYDOXHVIRUHDFKPRGDOLW\EXW
FDQ EH RSWLPL]HG IUHHO\ 7KH\ GHWHUPLQH KRZ TXLFNO\ WKH,Q DQ H[SHULPHQWDO VWXG\ WKH SDUWLFLSDQWV ZHUH DVNHG WR
DOJRULWKP FRQYHUJHV DQG KRZ TXLFNO\ WKH URERW DGDSWV WR D LQVWUXFW WKHURERW WR SHUIRUPWKHWDVN GHVFULEHG LQ VHFWLRQ 
FKDQJH LQ UHZDUG EHKDYLRU 7KH PD[LPXP DVVRFLDWLYH ZLWKGLIIHUHQWUHVWULFWLRQVSRVHGRQWKHUHZDUGEHKDYLRUVWKDWVWUHQJWKLVVHWWRRQHLQFDVHWKHFRUUHVSRQGLQJ&6LVSUHVHQW WKH\ZHUHDOORZHGWRXVH7KHJRDORIWKLVSUHOLPLQDU\VWXG\ZKHQ WKH 86 RFFXUV ]HUR RWKHUZLVH 7KH FRPELQHG ZDV WR JHW DQ LQVLJKW LQ W\SLFDO XVHU EHKDYLRU GXULQJ D
DVVRFLDWLYH VWUHQJWK RI DOO FRQGLWLRQHG VWLPXOL WRZDUGV WKH KXPDQURERW WHDFKLQJ WDVN DQG UHFRUG GDWD IRU D ILUVWXQFRQGLWLRQHG VWLPXOXV FDQ EH FDOFXODWHG HDVLO\ E\ HYDOXDWLRQ RI WKH FRQGLWLRQLQJEDVHG VHFRQG SKDVH RI RXUVXPPDUL]LQJWKHSUHFDOFXODWHGDVVRFLDWLRQYDOXHVRIDOOWKH OHDUQLQJ PHWKRG ZKLFK LV SUHVHQWHG LQ WKLV SDSHU :H DOVR
&6WRZDUGVWKH86
DLPHG DW ILQGLQJ RXW KRZ UHVWULFWLRQV LQ DOORZHG UHZDUG
7KHPDMRUGUDZEDFNRIWKH5HVFRUOD:DJQHU0RGHOLVWKDW PRGDOLWLHVDIIHFWWKHIUHTXHQF\RIUHZDUGJLYHQE\WKHXVHUV
LW LV QRW DEOH WR PRGHO WKH HIIHFWV RI DQGWRXQGHUVWDQGWKHYDULDELOLW\RIUHZDUGVJLYHQE\DVLQJOHVHFRQGRUGHUFRQGLWLRQLQJ DQG VHQVRU\ SUHFRQGLWLRQLQJ XVHU LQ UHVSRQVH WR GLIIHUHQW URERW EHKDYLRUV :H IXUWKHUGLUHFWO\ 7KHUHIRUH ZH XVH D VHFRQG SDVV RI WKH LQYHVWLJDWHGLQKRZIDUUHZDUGSDWWHUQVWKDWDXVHUVHOHFWVDQG
5HVFRUOD:DJQHUDOJRULWKP WR OHDUQ DVVRFLDWLRQV EHWZHHQ SUHUHFRUGV IRU LQWHUDFWLQJ ZLWK D URERW UHVHPEOH WKH RQHVVLPXOWDQHRXVO\ RFFXUULQJ &6 ,Q WKLV VHFRQG SDVV WKH &6 WKDWKHHPSOR\VLIQRUHVWULFWLRQVDUHJLYHQVHUYHV DVWKH 86 IRU WKH FRQGLWLRQLQJ RI WKH &6 ,QD WKLUG
,Q WKH H[SHULPHQW IRXU SDUWLFLSDQWV DOO RI ZKLFK PDOHSDVVRIWKHDOJRULWKPZHXSGDWHWKHUHODWLRQEHWZHHQWKH86 FRPSXWHUOLWHUDWHJUDGXDWHVWXGHQWVDJHGEHWZHHQDQG
DQGDOO&6WKDWKDYHDQDVVRFLDWLRQWRWKHDFWXDOO\RFFXUUHG ZLWKRXWDQ\SULRUH[SHULHQFHRILQWHUDFWLQJZLWKDSHWURERW
&6 XVLQJ D OHDUQLQJ UDWH ǩ$ WKDW LV WKH SURGXFW RI WKH ZHUHDVNHGWRWUDLQWKHURERWXVLQJWKHWUDLQLQJWDVNGHVFULEHG
RULJLQDO OHDUQLQJ UDWH ǩ $ DQG WKH DVVRFLDWLYH VWUHQJWK LQ VHFWLRQ  'XULQJ WKH VWXG\ WKH URERW ZDV IXOO\EHWZHHQWKH&6DQGWKHFRUUHVSRQGLQJ&6
UHPRWHFRQWUROOHG DQG DOO LQ DOO  PLQXWHV RI DXGLR DQGYLGHRGDWDZHUHFROOHFWHGFRQWDLQLQJUHZDUGLQVWDQFHV±' 3RVW3URFHVVLQJSRVLWLYHDQGQHJDWLYHRQHV)LJXUHVKRZVDVDPSOHRI,Q RUGHU WR DYRLG WKH QXPEHU RI LWHPV LQ WKH +00 WKHYLGHRWDNHQGXULQJWKHH[SHULPHQWGDWDEDVH WR JURZ WRR ODUJH DQG WR LPSURYH UHFRJQLWLRQ  ([SHULPHQWDO6HWWLQJDQGHYDOXDWLRQPHWKRGDFFXUDF\SRVWSURFHVVLQJVWHSVDUHDSSOLHGWRWKH+00VLQ
7KHSDUWLFLSDQWVZHUHSURYLGHGZLWKFDUGVVKRZLQJZKLFKWKH GDWDEDVH DIWHU WKH WUDLQLQJ SKDVH 'XULQJ WKH SRVW REMHFWZDVWREHPRYHGWRZKDWSODFHDQGZHUHWROGWRLQVWUXFWSURFHVVLQJ +00V ZKLFK DUH VLPLODU LQ WHUPV RI
PDWKHPDWLFDO GLVWDQFH >@ DV ZHOO DV LQ WHUPV RI WKHLU
DVVRFLDWLRQVWRWKHVDPHUHZDUGVDUHPHUJHG+00VWKDWGRQRW KDYH D VXIILFLHQWO\ VWURQJ DVVRFLDWLRQ ZLWK DQ\ RI WKHUHZDUGVDUHUHPRYHGIURPWKH+00GDWDEDVH
9 ,03/(0(17$7,21
7KHIRFXVRIWKHDFWXDOLPSOHPHQWDWLRQRIWKHV\VWHPZDV
WR GHYHORS D IUDPHZRUN IRU FRQGXFWLQJ H[SHULPHQWV WKDW LV
HDV\ WR H[WHQG DQG WR DGDSW WR QHZ WDVNV  7KH IUDPHZRUNXWLOL]HV DQ $,%2 (56 URERW $,%2 LV D GRJVKDSHG SHWURERW ZKLFK KDV URXJKO\ WKH VL]H RI D FDW ,W SRVVHVVHV 
GHJUHHV RI IUHHGRP DQG LV DEOH WR FRPPXQLFDWH WKURXJKVRXQGVDQ/('SDQHOLQLWVIDFHDVZHOODVERG\PRYHPHQWV,W SHUFHLYHV LWV HQYLURQPHQW WKURXJK YDULRXV VHQVRUVLQFOXGLQJ VWHUHR PLFURSKRQHV D [ FDPHUD WZRSUR[LPLW\ VHQVRUV  WDFWLOH WRXFK VHQVRUV  RQH RQ LWV KHDG
DQG WKUHH RQ LWV EDFN   WRXFK VHQVRUV LQ LWV SDZV DQG DQ
DFFHOHURPHWHU ,W VXSSRUWV WKH E :/$1 VWDQGDUG IRU

4102



)LJXUH,PDJHFDSWXUHGIURPRQHRIWKHYLGHRVRIWKHH[SHULPHQW2008 IEEE Congress on Evolutionary Computation (CEC 2008)


WKHURERW IUHHO\ DQG JLYHUHZDUGVDFFRUGLQJWR RQH RI WKUHH
VFHQDULRVDWDWLPH7KHRUGHURIVFHQDULRVZDVFKDQJHGIRU
HDFKSDUWLFLSDQWWRDYRLGVHTXHQFHHIIHFWV )UHH UHZDUG 7KH XVHU FRXOG FKRVH IUHHO\ LQ ZKLFKZD\WRJLYHUHZDUGWRWKHURERW
 5HFRUGHGUHZDUG7KHXVHUKDGWRUHFRUGKLVSUHIHUUHGZD\RIJLYLQJUHZDUGLQDGYDQFHDQGKDGWRVWLFNWRLW
WKURXJKRXWWKHH[SHULPHQW 7RXFKUHZDUG7KHXVHUKDGWRWRXFKWKHURERW VKHDG
VHQVRU IRU SRVLWLYH DQG WKH URERW V EDFN VHQVRU IRUQHJDWLYHUHZDUG'XULQJWKHH[SHULPHQWVWKHURERWZDVUHPRWHFRQWUROOHGWR
PDNH GLIIHUHQW NLQGV RI PLVWDNHV VLPXODWLQJ D WHFKQLFDOIDLOXUH WR SLFN XS DQ REMHFW VLPXODWLQJ D PLVXQGHUVWDQGLQJIURPWKHVSHHFKUHFRJQLWLRQDQGVRPHXQH[SHFWHGEHKDYLRUVVXFK DV GHOLEHUDWHO\ VLWWLQJ GRZQ WR SURYRNH QHJDWLYH
IHHGEDFN 7KH GLIIHUHQW W\SHV RI PLVWDNHV ZHUH EDODQFHGZLWKLQ HYHU\ SDVV RI WKH H[SHULPHQW 3RVLWLYH IHHGEDFN ZDVH[SHFWHGIRUSLFNLQJXSWKHFRUUHFWREMHFWGHOLYHULQJLWWRWKHULJKW SODFH DQG UHFRYHULQJ IURP DQ HUURU $IWHU WKHH[SHULPHQWDTXHVWLRQQDLUHZDVSURYLGHGWRHDFKSDUWLFLSDQW
WRHYDOXDWHKLVH[SHULHQFHWKURXJKRXWWKHLQWHUDFWLRQ
7KH GDWD IURP WKH H[SHULPHQWV LQ WKH ³)UHH 5HZDUG´
VHWWLQJ ZDV WUDQVFULEHG PDQXDOO\ DQG XVHG IRU WUDLQLQJ WKHDVVRFLDWLRQV EHWZHHQ DFWLRQV DQG WKHLU PHDQLQJV LQ WKH³UHZDUGDVVRFLDWLRQOHDUQLQJSKDVH´RIRXUOHDUQLQJPHWKRG
7UDQVFULELQJ WKH GDWD E\ KDQG UHSODFHV WKH WUDLQLQJ RI WKH
+00VZKLFKUHTXLUHVDODUJHUDPRXQWRIWUDLQLQJGDWDWKDQZH REWDLQHG GXULQJ RXU ILUVW H[SHULPHQWV 7KH GDWD IRUWUDLQLQJWKHDFWXDO+00VLVFXUUHQWO\EHLQJJDWKHUHGGXULQJDVHFRQGVHULHVRIH[SHULPHQWV(DFKRIWKHXVHU¶VDFWLRQVZDVWUDQVFULEHG E\ D VWDUWLQJ DQG DQ HQGLQJ WLPHVWDPSFRUUHVSRQGLQJ WR WKH RQVHW DQG WKH HQG RI WKHYRLFHJHVWXUHWRXFKEDVHGVWLPXOXVWKHQDPHRIWKHPRGDOLW\VSHHFKJHVWXUHWRXFK DQGWKHFRQWHQWVRIWKHVWLPXOXVWKDWLV ZKLFK ZRUGVHQWHQFH ZDV XWWHUHG ZKLFK W\SH RI JHVWXUHZDV SHUIRUPHG DQG ZKLFK VHQVRU ZDV WRXFKHG :H GLG QRWLQFOXGHLQIRUPDWLRQRQSURVRG\LQRXUWUDQVFULSWLRQV
7KHUHZDUG IURPWKH WUDLQHU IXQFWLRQ ZDV GHVFULEHG E\ D
VWDUWWLPHVWDPSHQGWLPHVWDPSDQGWKHNH\ZRUG³SRVLWLYH´
³QHJDWLYH´RU³QHXWUDO´5HZDUGIURPWKHWUDLQHUIXQFWLRQZDVLQVHUWHGDIWHUHDFKREVHUYHGUHZDUGSDWWHUQLQGHSHQGHQWIURPWKHREVHUYHGXVHUEHKDYLRUGHSHQGLQJRQO\RQWKHVWDWHRIWKH
WDVN H[HFXWLRQ DW WKDW WLPH 7KLV FRUUHVSRQGV WR WKHLQIRUPDWLRQWKDWWKHURERWFDQDFFHVVLQDUHDOWUDLQLQJWDVN
7KHNH\ZRUG³SRVLWLYH´ZDVDVVLJQHGWRWKHUHZDUGVJLYHQZLWKLQ WKH ILUVW  VHFRQGV DIWHU D VXEWDVN KDV EHHQ
VXFFHVVIXOO\ILQLVKHG7KHNH\ZRUG³QHJDWLYH´ZDVDVVLJQHG
WRHYHU\UHZDUGJLYHQZKLOHWKHURERWZDVLQDQHUURUVWDWHDQG
KDGQRW\HWVWDUWHGWRFRUUHFWLW,QDOORWKHUFDVHVWKHVWLPXOXVUHWXUQHGE\WKHWUDLQHUIXQFWLRQZDV³QHXWUDO´
)RUH[DPSOHDVLWXDWLRQZKHUHWKHXVHUVD\V³JRRG´DQG
WRXFKHV WKH KHDG VHQVRU RI WKH URERW ZLWKLQ WKH ILUVW 
VHFRQGVDIWHUVXFFHVVIXOO\ILQLVKLQJDWDVNRUVXEWDVNVXFKDVWKH VXFFHVVIXO GHOLYHU\ RI DQ REMHFW WR LWV WDUJHW SODFH LV
WUDQVFULEHGDVIROORZVVSHHFKJRRG
WRXFKKHDG
IHHGEDFNSRVLWLYH  5HVXOWV
7KHFRQGLWLRQLQJDOJRULWKPKDVEHHQWUDLQHGDQGHYDOXDWHG
VHSDUDWHO\ IRU HYHU\ XVHU XVLQJ ³OHDYHRQHRXW´FURVVHYDOXDWLRQ7KHWRWDOQXPEHURIVWLPXOLZKLFKLQFOXGHGDQ\NLQGV RI XWWHUDQFHV JHVWXUHV RU WRXFKDFWLRQV ZDV UDQJLQJIURPWREHWZHHQGLIIHUHQWXVHUV2XWRIWKHVH
VWLPXOLZHUHQHXWUDOZHUHQHJDWLYHDQGZHUHSRVLWLYH 7KHVH QXPEHUV GLIIHU IURP WKHQXPEHU RI SRVLWLYH
DQGQHJDWLYHUHZDUGVJLYHQDERYHDVRQHUHZDUGFDQFRQVLVWRI PXOWLSOH VWLPXOL 7KH DYHUDJH DFFXUDF\ IRU FODVVLI\LQJ
EHWZHHQ³SRVLWLYH´³QHJDWLYH´DQG³QHXWUDO´XWWHUDQFHVZDV7KH FRQIXVLRQ PDWUL[ FDQ EH VHHQ LQWDEOH  0RVWPLVFODVVLILFDWLRQV RFFXUUHG ZLWK QHXWUDO VWLPXOL ZKLFK ZHUH
PLVFODVVLILHGDVHLWKHUSRVLWLYHRUQHJDWLYHZKLOHFRQIXVLRQVEHWZHHQSRVLWLYHDQGQHJDWLYHVWLPXOLZHUHOHDVWIUHTXHQW
7$%/(&21)86,210$75,;)257+(&21',7,21,1*67$*( 
3RVLWLYH
1HJDWLYH
1HXWUDO

3RVLWLYH



1HJDWLYH



1HXWUDO



/HIWWRULJKWH[SHFWHGFODVVLILFDWLRQV7RSWRERWWRPDFWXDOFODVVLILFDWLRQV$VIRUWKHXVHU¶VUHZDUGEHKDYLRULQWKHGHVFULEHGWUDLQLQJWDVNVZHIRXQGIURPWKHH[SHULPHQWVWKDWWKHUHZDUGVZKLFKZHUHUHFRUGHGE\WKHXVHUVIRUEHLQJXVHGLQWKH³UHFRUGHG´
VFHQDULR GLG QRW FRUUHVSRQG DV PXFK DV H[SHFWHG WR WKHUHZDUGVJLYHQLQWKH³IUHH´VFHQDULR2QO\RISRVLWLYH
DQGRIQHJDWLYHUHZDUGVZHUHJLYHQLQWKHVDPHZD\DVWKHRQHWKDWWKHXVHUFRQVLGHUHGDVKLV³IDYRULWH´ZD\ ZKHQUHFRUGLQJUHZDUGVIRUWKH³UHFRUGHG´VFHQDULR
%XW HYHQ ZLWKLQ WKH WRXFK DQG UHFRUGHG VFHQDULRV WKHSDUWLFLSDQWVGLGQRWVWLFNWRWKHGHVLJQDWHGUHZDUGEHKDYLRU$OWKRXJK WKH\ ZHUH FOHDUO\ LQVWUXFWHG QRW WR XVH GLIIHUHQWUHZDUGV LQ WKH UHFRUGHG DQG WRXFK VFHQDULR DOOSDUWLFLSDQWV JDYH DGGLWLRQDO RU IXOO\ LQFRUUHFW SRVLWLYH DQGQHJDWLYH UHZDUG ,Q FDVH RI WKH ³WRXFK´ UHLQIRUFHPHQW
SULQFLSOH  UHZDUGV ZHUH JLYHQ E\ WKH SDUWLFLSDQWV  RI
WKHPFRUUHFWUHZDUGVUHZDUGVWKDWFRQWDLQHGDQDGGLWLRQDO
VSHHFKXWWHUDQFHRUJHVWXUHDQGUHZDUGVWKDWGLGQRWDWDOO
LQFOXGH WRXFKLQJ WKH KHDG RU EDFN VHQVRU PRVW RI WKHPSURYLGLQJ D VSHHFK XWWHUDQFH RQO\ 2XW RI WKH  UHZDUGVJLYHQ ZLWK WKH UHFRUGHG UHLQIRUFHPHQW SULQFLSOH  ZHUHFRUUHFWWKDWLVXVLQJWKHVDPHZRUGVDQGURXJKO\WKHVDPH
JHVWXUHVDVUHFRUGHGUHZDUGVFRQWDLQHGDGGLWLRQDOVSHHFKXWWHUDQFHV RU JHVWXUHV DQG  UHZDUGV ZHUH FRPSOHWHO\GLIIHUHQWIURPWKHUHFRUGHGRQHV
7KH DPRXQW RI UHZDUG JLYHQ YDULHG ZLWK WKH DOORZHGUHZDUGPRGDOLWLHVDV FDQ EH VHHQLQ )LJXUH  0RVWUHZDUGZDVJLYHQLQWKHIUHHUHZDUGVFHQDULRZKHUHSHUFHQWRI
WKH SRVLWLYH VLWXDWLRQV DQG  SHUFHQW RI WKH QHJDWLYH
VLWXDWLRQVZHUHUHZDUGHGZKLOHOHDVWUHZDUGZDVJLYHQLQWKHWRXFK UHZDUG VFHQDULR ZKHUH D UHZDUG ZDV JLYHQ IRU 

2008 IEEE Congress on Evolutionary Computation (CEC 2008)

4103



VHWWLQJLV EDVHG RQ D JDPHWDVN WKDWDOORZV WKH XVHU WR JLYH
PRUH SRVLWLYH DQG QHJDWLYH UHZDUGV LQ D VKRUW WLPH E\
PLQLPL]LQJWKHLQWHUDFWLRQIUHHWDVNH[HFXWLRQWLPHZKLFKLV
PDLQO\FDXVHGE\WKHVORZZDONLQJPRYHPHQWVRIWKH$,%2
SHWURERW
5()(5(1&(6)LJXUH3HUFHQWDJHRISRVLWLYHDQGQHJDWLYHEHKDYLRUVRIWKHURERWWKDWUHVXOWLQSRVLWLYHQHJDWLYHUHZDUG

SHUFHQW RI WKH SRVLWLYH DQG  SHUFHQW RI WKH QHJDWLYH
VLWXDWLRQV 7KH UHDVRQ IRU WKH DSSDUHQW QHJDWLYH ELDV LQ
UHZDUGV LV WKDW PRVW RI WKH WLPH SRVLWLYH UHZDUG ZDV RQO\JLYHQ IRU UHDFKLQJ WKH ILQDO JRDO EXW QRW IRU UHDFKLQJVXEJRDOVOLNHDSSURDFKLQJWKHFRUUHFWREMHFWRUFRUUHFWLQJDPLVWDNH7KHURERWGLGQRWVWRSDQGZDLWRUSURPSWWKHXVHUIRU UHZDUG LQ WKHVH VLWXDWLRQV 2Q WKH RWKHU KDQG LQFRUUHFWSHUIRUPDQFH RI WKH URERW ZDV TXLWH REYLRXV DQG WKHUHIRUH
W\SLFDOO\UHVXOWHGLQDQHJDWLYHUHZDUG
,Q D TXHVWLRQQDLUH WKH SDUWLFLSDQWV FRXOG UDWH WKHLU
DJUHHPHQW ZLWK GLIIHUHQW VWDWHPHQWV FRQFHUQLQJ WKHLU
LQWHUDFWLRQ ZLWK WKH URERW RQ D VFDOH IURP  FRPSOHWHO\
DJUHH  WR  FRPSOHWHO\ GLVDJUHH  )RU WKH VWDWHPHQW ³, ZDVDEOH WR LQVWUXFWWKHURERW LQ DQDWXUDO ZD\´WKH IUHHUHZDUG
UHFHLYHGDUDWLQJRI 6'  UHFRUGHGUHZDUGZDVUDWHG
 6'  DQGWRXFKUHZDUGZDVUDWHG 6'  )RU
WKHVWDWHPHQW³,ZRXOGOLNHWRLQWHUDFWZLWKDUHDOVHUYLFHURERWLQ WKH VDPH ZD\´ WKH UDWLQJV ZHUH  6'   IRU IUHHUHZDUG 6'  IRUUHFRUGHGUHZDUGDQG 6'  IRUWRXFKUHZDUG
9,, ',6&866,21
$OWKRXJKWKHVPDOOQXPEHURISDUWLFLSDQWVGRHVQRWDOORZ
IRUDVRXQGVWDWLVWLFDODQDO\VLVWKHUHVXOWVVXJJHVWWKDWXVHUV
DUH TXLWH VHQVLWLYH WR UHVWULFWLRQV LQ DSSOLFDEOH UHZDUGEHKDYLRUV 7KHUHIRUH WHFKQLTXHV WKDW DOORZ UHZDUG DQGLQVWUXFWLRQVWREHJLYHQWRDURERWDVIUHHO\DVSRVVLEOHZRXOG
EHGHVLUDEOH
0RUHRYHU RXU GDWD VKRZV WKDW SUHUHFRUGLQJ IL[HG
SDWWHUQVIRUJLYLQJUHZDUGGRHVQRWVXIILFHWRHQDEOHDXVHUWRSURYLGHUHZDUGWRDURERWLQKLVRUKHUSUHIHUUHGZD\$VUHVXOWVIURPWKH+00EDVHGILUVWVWDJHRIRXUOHDUQLQJPHWKRG DUH VWLOO PLVVLQJ WKH UHVXOWV IURP WKH FRQGLWLRQLQJSKDVH FDQ RQO\ EH VHHQ DV DQ XSSHU ERXQGDU\ IRU WKHSHUIRUPDQFHRIWKHZKROHOHDUQLQJPHWKRG7KHPDLQFDXVH
RI PLVFODVVLILFDWLRQV RI WKH FRQGLWLRQLQJ SKDVH ZHUHXWWHUDQFHV WKDW ZHUH XVHG RQO\ RQFH ZLWKLQ RXU GDWD 7KLVSUREOHPZDVFDXVHGE\WKHVPDOODPRXQWRIWUDLQLQJGDWDZH
KDGJDWKHUHGZLWKLQRXUILUVWH[SHULPHQW,WLVEHLQJDGGUHVVHG
E\ FXUUHQWO\ RQJRLQJ H[SHULPHQWV ZLWK D ODUJHU QXPEHU RI
SDUWLFLSDQWV DQG D FKDQJHG H[SHULPHQWDO VHWWLQJ 7KH QHZ

4104

>@ $,%25HPRWH)UDPHZRUNKWWSRSHQUDLERFRP>@ & %DONHQLXV - 0RUQ ³&RPSXWDWLRQDO PRGHOV RI FODVVLFDOFRQGLWLRQLQJ D FRPSDUDWLYH VWXG\´  3URFHHGLQJV RI WKH )LIWK,QWHUQDWLRQDO&RQIHUHQFHRQ6LPXODWLRQRI$GDSWLYH%HKDYLRU
>@ ' + %DOODUG & <X ³$ PXOWLPRGDO OHDUQLQJ LQWHUIDFH IRU ZRUGDFTXLVLWLRQ´3URFHHGLQJVRIWKH,(((,QWHUQDWLRQDO&RQIHUHQFH
RQ$FRXVWLFV6SHHFKDQG6LJQDO3URFHVVLQJ
>@ & %UHD]HDO 5HFRJQLWLRQ RI $IIHFWLYH &RPPXQLFDWLYH ,QWHQW LQ
5RERW'LUHFWHG 6SHHFK $XWRQRPRXV 5RERWV 9ROXPH    ,VVXH -DQXDU\
>@ 0 )DONKDXVHQ + 5HLQLQJHU ' :ROI ³&DOFXODWLRQ RI 'LVWDQFH
0HDVXUHV EHWZHHQ +LGGHQ 0DUNRY 0RGHOV´ ,Q 3URF (XURVSHHFKSDJHV
>@ 1 ,ZDKDVKL ³$FWLYH DQG 8QVXSHUYLVHG /HDUQLQJ IRU 6SRNHQ :RUG
$FTXLVLWLRQ 7KURXJK D 0XOWLPRGDO ,QWHUIDFH´ 520$1   WK,((( LQWHUQDWLRQDO ZRUNVKRS RQ URERW DQG KXPDQ LQWHUDFWLYH
FRPPXQLFDWLRQ>@ & /HH < ;X ³2QOLQH ,QWHUDFWLYH /HDUQLQJ RI *HVWXUHV IRU+XPDQ5RERW LQWHUIDFHV´ ,((( ,QW &RQI RQ 5RERWLFV DQG$XWRPDWLRQSS>@ %/RZHQNURQ³:RUG PHDQLQJ $YHUEDO EHKDYLRUDFFRXQW´ $QQXDOFRQYHQWLRQRIWKH$VVRFLDWLRQIRU%HKDYLRU$QDO\VLV:DVKLQJWRQ'&
0D\
>@ =..D\LNFL+0DUNHUW*3DOP³1HXUDO$VVRFLDWLYH0HPRULHVDQG
+LGGHQ0DUNRY0RGHOVIRU6SHHFK5HFRJQLWLRQ´3URFHHGLQJVRIWKH
,-&11
>@ $ 1RJXHLUDV $ 0RUHQR $ %RQDIRQWH -RVp % 0DULQR ³6SHHFK(PRWLRQ5HFRJQLWLRQ8VLQJ+LGGHQ0DUNRY0RGHOV´3URFHHGLQJVRI(XURVSHHFK
>@ 7/1ZH6)RR6:HL/'H6LOYD³6SHHFKHPRWLRQUHFRJQLWLRQXVLQJKLGGHQ0DUNRYPRGHOV´6SHHFKFRPPXQLFDWLRQ
>@ %)6NLQQHU³9HUEDO%HKDYLRU´&RSOH\3XEOLVKLQJ*URXS
>@ & . 6WDDWV $: 6WDDWV ³0HDQLQJ HVWDEOLVKHG E\ FODVVLFDOFRQGLWLRQLQJ´-RXUQDORI([SHULPHQWDO3V\FKRORJ\
>@ $ / 7KRPD] & %UHD]HDO 5HLQIRUFHPHQW /HDUQLQJ ZLWK +XPDQ7HDFKHUV (YLGHQFH RI IHHGEDFN DQG JXLGDQFH ZLWK LPSOLFDWLRQV IRUOHDUQLQJSHUIRUPDQFH,Q3URFHHGLQJVRIWKHVW1DWLRQDO&RQIHUHQFH
RQ$UWLILFLDO,QWHOOLJHQFH $$$, 
>@ 7KH 2SHQ &RPSXWHU 9LVLRQ /LEUDU\
2SHQ&9   
KWWSRSHQFYOLEUDU\VRXUFHIRUJHQHW
>@ 6<DPDGD7<DPDJXFKL³7UDLQLQJ $,%2 OLNHD GRJ  SUHOLPLQDU\UHVXOWV´ 3URFHHGLQJV RI WKH ,((( :RUNVKRS RQ 5RERW DQG +XPDQ,QWHUDFWLYH&RPPXQLFDWLRQ520$1
>@ 6 <RXQJ HW DO ³7KH +7. %RRN´ +7. 9HUVLRQ  
KWWSKWNHQJFDPDFXN

2008 IEEE Congress on Evolutionary Computation (CEC 2008)