Local Search with P Systems

.H\ZRUGV &/,36/RFDO6HDUFK0HPEUDQH&RPSXWLQJ14XHHQV36\VWHPV3UREOHP ,1752'8&7,21 6HDUFKLQJLVWKHEDVLVRIPDQ\SURFHVVHVLQ$U WLILFLDO,QWHOOLJHQFH7KHNH\SRLQWLVWKDWPDQ\ UHDOOLIHSUREOHPVFDQEHVWDWHGDVDVSDFHRI VWDWHVDVWDWHLVWKHGHVFULSWLRQRIWKHZRUOGDW DJLYHQLQVWDQWH[SUHVVHGLQVRPHODQJXDJH DQGWZRVWDWHVDUHOLQNHGE\DWUDQVLWLRQLIWKH VHFRQGVWDWHFDQEHUHDFKHGIURPWKHSUHYLRXV RQHE\DSSO\LQJRQHHOHPHQWDU\RSHUDWLRQ%\ XVLQJWKHVHFRQFHSWVDVHDUFKLQJWUHHZKHUH WKHQRGHVDUHWKHVWDWHVWKHURRWLVWKHVWDUWLQJ VWDWHDQGWKHHGJHVDUHWKHDFWLRQVFRQVLGHUHG *LYHQDQLQLWLDOVWDWHDVHTXHQFHRIWUDQVLWLRQV WRRQHRIWKHILQDOVWDWHVLVVHDUFKHG %\XVLQJWKLVDEVWUDFWLRQVHDUFKLQJPHWK RGVKDYHEHHQGHHSO\VWXGLHGE\WKHPVHOYHV IRUJHWWLQJWKHUHDOZRUOGSUREOHPZKLFKWKH\ILW 7KHVWXGLHVFRQVLGHUDVSHFWVDVWKHFRPSOHWHQHVV LIWKHVHDUFKLQJPHWKRGLVFDSDEOHRIILQGLQJ DVROXWLRQLILWH[LVWVFRPSOH[LW\LQWLPHDQG VSDFHDQGRSWLPDOLW\LIWKHIRXQGVROXWLRQLV RSWLPDO LQ VRPH VHQVH %\ FRQVLGHULQJ WKH VHDUFKLQJ WUHH FODVVLFDO VHDUFK KDV IRFXVHG RQWKHRUGHULQZKLFKWKHQRGHVVKRXOGEHH[ SORUHG,QWKLVFODVVLFDOVHDUFKWZRDSSURDFKHV DUHSRVVLEOHWKHIRUPHULVEOLQGVHDUFKZKHUH WKHVHDUFKLVJXLGHGRQO\E\WKHWRSRORJ\RI WKHWUHHDQGQRLQIRUPDWLRQLVDYDLODEOHIURP WKHVWDWHVWKHODWWHULVFDOOHGLQIRUPHGVHDUFK DQGVRPHLQIRUPDWLRQDERXWWKHIHDWXUHVRIWKH QRGHVLVXVHGWRGHILQHDKHXULVWLFVWRGHFLGH WKHQH[WQRGHWRH[SORUH 6HDUFKLQJSUREOHPVKDYHEHHQSUHYLRXVO\ VWXGLHGLQWKHIUDPHZRUNRI0HPEUDQH&RPSXW LQJ,Q*XWLpUUH]1DUDQMRDQG3pUH]-LPpQH] /RFDO6HDUFKZLWK36\VWHPV $&DVH6WXG\ 0LJXHO$*XWLpUUH]1DUDQMR8QLYHUVLW\RI6HYLOOD6SDLQ 0DULR-3pUH]-LPpQH]8QLYHUVLW\RI6HYLOOD6SDLQ $%675$&7 /RFDOVHDUFKLVFXUUHQWO\RQHRIWKHPRVWXVHGPHWKRGVIRU¿QGLQJVROXWLRQVLQUHDOOLIHSUREOHPV,WLVXVXDOO\ FRQVLGHUHGZKHQWKHUHVHDUFKLVLQWHUHVWHGLQWKH¿QDOVROXWLRQRIWKHSUREOHPLQVWHDGRIWKHKRZWKHVROXWLRQ LVUHDFKHG,QWKLVSDSHUWKHDXWKRUVSUHVHQWDQLPSOHPHQWDWLRQRIORFDOVHDUFKZLWK0HPEUDQH&RPSXWLQJ WHFKQLTXHVDSSOLHGWRWKH1TXHHQVSUREOHPDVDFDVHVWXG\$&/,36SURJUDPLQVSLUHGLQWKH0HPEUDQH &RPSXWLQJGHVLJQKDVEHHQLPSOHPHQWHGDQGVHYHUDOH[SHULPHQWVKDYHEHHQSHUIRUPHG7KHREWDLQHGUHVXOWV VKRZEHWWHUDYHUDJHWLPHVWKDQWKRVHREWDLQHGZLWKRWKHU0HPEUDQH&RPSXWLQJLPSOHPHQWDWLRQVWKDWVROYH WKH1TXHHQVSUREOHP '2,MQFU DILUVWVWXG\RQGHSWKILUVWVHDUFKLQ WKHIUDPHZRUNRI0HPEUDQH&RPSXWLQJZDV SUHVHQWHG,QWKLVSDSHUZHJRIXUWKHUZLWKWKH VWXG\RIVHDUFKLQJPHWKRGVLQ0HPEUDQH&RP SXWLQJE\H[SORULQJORFDOVHDUFK:HFRQVLGHU WKH1TXHHQVSUREOHPDVDFDVHVWXG\DQGZH SUHVHQWDIDPLO\RI3V\VWHPVZKLFKVROYHVLW E\LPSOHPHQWLQJORFDOVHDUFKLGHDV 7KHSDSHULVRUJDQL]HGDVIROORZV)LUVW ZHUHFDOOVRPHEDVLFGHILQLWLRQVUHODWHGWROR FDOVHDUFK7KHQZHUHFDOOWKHSUREOHPXVHG DVDFDVHVWXG\WKH1TXHHQVSUREOHPSUHYL RXVO\VWXGLHGLQWKHIUDPHZRUNRI0HPEUDQH &RPSXWLQJ LQ *XWLpUUH]1DUDQMR 0DUWtQH] GHO$PRU3pUH]+XUWDGRDQG3pUH]-LPpQH] 1H[WZHSURYLGHVRPHJXLGHOLQHVRI WKHLPSOHPHQWDWLRQRIORFDOVHDUFKLQRXUFDVH VWXG\DQGVKRZVRPHH[SHULPHQWDOUHVXOWV7KH SDSHUILQLVKHVZLWKVRPHILQDOUHPDUNV /2&$/6($5&+ &ODVVLFDOVHDUFKDOJRULWKPVH[SORUHWKHVSDFHRI VWDWHVV\VWHPDWLFDOO\7KLVH[SORUDWLRQLVPDGH E\NHHSLQJRQHRUPRUHSDWKVLQPHPRU\DQGE\ UHFRUGLQJWKHDOWHUQDWLYHVLQHDFKFKRLFHSRLQW :KHQDILQDOVWDWHLVIRXQGWKHSDWKWKDWLV WKHVHTXHQFHRIWUDQVLWLRQVLVFRQVLGHUHGDVWKH VROXWLRQRIWKHSUREOHP1RQHWKHOHVVLQPDQ\ SUREOHPVZHDUHRQO\LQWHUHVWHGLQWKHIRXQG VWDWHQRWSURSHUO\LQWKHSDWKRIWUDQVLWLRQV)RU H[DPSOHLQMREVKRSVFKHGXOLQJYHKLFOHURXW LQJRUWHOHFRPPXQLFDWLRQVQHWZRUNRSWLPL]D WLRQZHDUHRQO\LQWHUHVWHGLQWKHILQDOVWDWHD FRQFUHWHGLVSRVLWLRQRIWKHREMHFWVLQWKHZRUOG QRWLQWKHZD\LQZKLFKWKLVVWDWHLVDFKLHYHG ,IWKHVHTXHQFHRIHOHPHQWDU\WUDQVLWLRQV LVQRWLPSRUWDQWDJRRGDOWHUQDWLYHWRFODVVLFDO VHDUFKLQJDOJRULWKPVLVORFDOVHDUFK7KLVW\SH RIVHDUFKRSHUDWHVXVLQJDVLQJOHVWDWHDQGLWV VHWRIQHLJKERUV,WLVQRWQHFHVVDU\WRNHHSLQ PHPRU\KRZWKHFXUUHQWVWDWHKDVEHHQREWDLQHG 6LQFHWKHVHDOJRULWKPVGRQRWV\VWHPDWL FDOO\H[SORUHWKHVWDWHVWKH\GRQRWJXDUDQWHH WKDWDILQDOVWDWHFDQEHIRXQGLHWKH\DUH QRWFRPSOHWH1RQHWKHOHVVWKH\KDYHWZRDG YDQWDJHVWKDWPDNHWKHPLQWHUHVWLQJLQPDQ\ VLWXDWLRQV  2QO\DOLWWOHSLHFHRILQIRUPDWLRQLVVWRUHG VRYHU\OLWWOHPHPRU\XVXDOO\FRQVWDQW LVXVHG  7KHVHDOJRULWKPVFDQRIWHQILQGDUHDVRQ DEOHVROXWLRQLQDQH[WUHPHO\ODUJHVSDFH RI VWDWHV ZKHUH FODVVLFDO DOJRULWKPV DUH XQVXLWDEOH 7KHEDVLFVWUDWHJ\LQORFDOVHDUFKLVFRQ VLGHULQJDFXUUHQWVWDWHDQGLILWLVQRWDILQDO RQHWKHQLWPRYHVWRRQHRILWVQHLJKERUV7KLV PRYHPHQWLVQRWPDGHUDQGRPO\,QRUGHUWR GHFLGH ZKHUH WR PRYH D PHDVXUH RI JRRG QHVVLVLQWURGXFHGLQORFDOVHDUFK,QWKLVZD\ WKHPRYHPHQWLVSHUIRUPHGWRZDUGVWKHEHVW QHLJKERURUDWOHDVWDQHLJKERUZKRLPSURYHV WKHFXUUHQWPHDVXUHRIJRRGQHVV,WLVXVXDOWR YLVXDOL]HWKHJRRGQHVVRIDVWDWHDVLWVKHLJKW LQVRPHJHRPHWULFDOVSDFH,QWKLVZD\ZHFDQ FRQVLGHUDODQGVFDSHRIVWDWHVDQGWKHWDUJHWRI WKHVHDUFKLQJPHWKRGLVWRDUULYHWRWKHJOREDO PD[LPXP7KLVPHWDSKRULVXVHIXOWRXQGHU VWDQGVRPHRIWKHGUDZEDFNVRIWKLVPHWKRG IODWUHJLRQVZKHUHWKHQHLJKERUVDUHDVJRRG DVWKHFXUUHQWVWDWHRUORFDOPD[LPXPZKHUH WKHQHLJKERUVDUHZRUVHWKDQWKHFXUUHQWVWDWH EXWLWLVQRWDJOREDOPD[LPXP$GHHSVWXG\ RIORFDOVHDUFKLVRXWRIWKHVFRSHRIWKLVSDSHU )XUWKHULQIRUPDWLRQFDQEHIRXQGLQ5XVVHOO DQG1RUYLJ ,QWKLVSDSHUZHZLOORQO\FRQVLGHUWKH EDVLFDOJRULWKPRIORFDOVHDUFK*LYHQDVHWRI VWDWHVDPRYHPHQWRSHUDWRUDQGDPHDVXUHWR FRPSDUHVWDWHV  :HVWDUWZLWKDVWDWHUDQGRPO\FKRVHQ  :HFKHFNLIWKHFXUUHQWVWDWHLVDILQDORQH ,IVRZHILQLVK7KHV\VWHPRXWSXWVWKH FXUUHQWVWDWH ,I QRW ZH ORRN IRU D PRYHPHQW ZKLFK UHDFKHVDEHWWHUVWDWH ,ILWH[LVWVZHUDQGRPO\FKRRVHRQHRI WKHSRVVLEOHPRYHPHQWV  7KHUHDFKHGVWDWHEHFRPHVWKHFXUUHQWVWDWH DQGZHJREDFNWR ,ILWGRHVQRWH[LVWZHJREDFNWR 7+(148((16352%/(0 7KURXJKWKLVSDSHUZHZLOO FRQVLGHUWKH1 TXHHQVSUREOHPDVDFDVHVWXG\,WLVDJHQHUDOL]D WLRQRIDFODVVLFSX]]OHNQRZQDVWKHTXHHQV SX]]OH7KHRULJLQDORQHLVDWWULEXWHGWRWKHFKHVV SOD\HU0D[%H]]HODQGLWFRQVLVWVRISXWWLQJHLJKW TXHHQVRQDQîFKHVVERDUGLQVXFKZD\WKDW QRQHRIWKHPLVDEOHWRFDSWXUHDQ\RWKHUXVLQJ WKHVWDQGDUGPRYHPHQWRIWKHTXHHQVLQFKHVV LHRQO\RQHTXHHQFDQEHSODFHGRQHDFKURZ FROXPQDQGGLDJRQDOOLQH+RIIPDQ/RHVVL 0RRUH%HUQKDUGVVRQ ,Q*XWLpUUH]1DUDQMRHWDODILUVW VROXWLRQWRWKH1TXHHQVSUREOHPLQWKHIUDPH ZRUNRI0HPEUDQH&RPSXWLQJZDVVKRZQ)RU WKDWDLPDIDPLO\RIGHWHUPLQLVWLF3V\VWHPV ZLWKDFWLYHPHPEUDQHVZDVSUHVHQWHG,QWKLV IDPLO\WKH1WKHOHPHQWRIWKHIDPLO\VROYHV WKH1TXHHQVSUREOHPDQGWKHODVWFRQILJXUD WLRQHQFRGHVDOOWKHVROXWLRQVRIWKHSUREOHP ,QRUGHUWRVROYHWKHSUREOHPDWUXWKDV VLJQPHQWWKDWVDWLVILHVDIRUPXODLQFRQMXQFWLYH QRUPDOIRUP&1)LVVHDUFKHG7KLVSUREOHP LVH[DFWO\6$7VRWKHVROXWLRQ SUHVHQWHGLQ *XWLpUUH]1DUDQMRHWDOXVHVDPRGLILHG VROXWLRQIRU6$7IURP3pUH]-LPpQH]5RPHUR -LPpQH]DQG6DQFKR&DSDUULQL6RPH H[SHULPHQWVZHUHSUHVHQWHGE\UXQQLQJWKH3 V\VWHPVZLWKDQXSGDWHGYHUVLRQRIWKH3OLQJXD VLPXODWRU *DUFtD4XLVPRQGR *XWLpUUH] (VFXGHUR 3pUH]+XUWDGR 3pUH]-LPpQH]  5LVFRV1~xH]7KHH[SHULPHQWVZHUH SHUIRUPHGRQ D V\VWHP ZLWK DQ ,QWHO&RUH 4XDG&38DVLQJOHSURFHVVRUZLWKFRUHV DW*K]*%RI5$0DQGXVLQJD& VLPXODWRUXQGHUWKHRSHUDWLQJV\VWHP8EXQWX 6HUYHU$FFRUGLQJWRWKHUHSUHVHQWDWLRQLQ *XWLpUUH]1DUDQMRHWDOWKHTXHHQV SUREOHPLVH[SUHVVHGE\DIRUPXODLQ&1)ZLWK YDULDEOHVDQGFODXVHV7KHLQSXWPXOWLVHW KDVHOHPHQWVDQGWKH3V\VWHPKDVUXOHV $ORQJ WKH FRPSXWDWLRQ   HOHPHQWDU\ PHPEUDQHV QHHG WR EH FRQVLGHUHG LQ SDUDO OHO6LQFHWKHVLPXODWLRQZDVFDUULHGRXWRQD XQLSURFHVVRUV\VWHPWKHVHPHPEUDQHVZHUH HYDOXDWHGVHTXHQWLDOO\7KHWKFRQILJXUDWLRQ ZDVDKDOWLQJRQH,WWRRNVHFRQGVWRUHDFK LWDQGLWKDVDQREMHFW1RLQWKHHQYLURQPHQW $VH[SHFWHGWKLVPHDQVWKDWWKUHHTXHHQVFDQ QRWEHSODFHGRQDîFKHVVERDUGVDWLVI\LQJ WKHUHVWULFWLRQV,QWKHTXHHQVSUREOHPIRXU QRQDWWDFNLQJTXHHQVDUHVHDUFKHGRQDî FKHVVERDUG$FFRUGLQJWRWKHUHSUHVHQWDWLRQ WKHSUREOHPFDQEHH[SUHVVHGE\DIRUPXODLQ &1)ZLWKYDULDEOHVDQGFODXVHV$ORQJWKH FRPSXWDWLRQ HOHPHQWDU\PHPEUDQHV ZHUHFRQVLGHUHGLQWKHVDPHFRQILJXUDWLRQDQG WKH3V\VWHPKDVUXOHV7KHVLPXODWLRQ WDNHVVHFRQGV!KRXUVWRUHDFKWKH KDOWLQJFRQILJXUDWLRQ,WLVWKHWKFRQILJX UDWLRQDQGLQWKLVFRQILJXUDWLRQRQHREMHFW<HV DSSHDUVLQWKHHQYLURQPHQW7KLVFRQILJXUDWLRQ KDVWZRHOHPHQWDU\PHPEUDQHVHQFRGLQJWKH WZRVROXWLRQVRIWKHSUREOHP*XWLpUUH]1DUDQMR HWDO ,Q*XWLpUUH]1DUDQMRDQG3pUH]-LPpQH]  D VWXG\ RI GHSWKILUVW VHDUFK LQ WKH IUDPHZRUNRI0HPEUDQH&RPSXWLQJZDVSUH VHQWHG7KHFDVHVWXG\ZDVDOVRWKH1TXHHQV SUREOHP$QDGKRF&/,36SURJUDPZDVZULWWHQ EDVHGRQD0HPEUDQH&RPSXWLQJGHVLJQ6RPH H[SHULPHQWVZHUHSHUIRUPHGRQDV\VWHPZLWK DQ,QWHO3HQWLXP'XDO&38(DW*+] *%RI5$0DQGXVLQJ&/,369XQGHU WKHRSHUDWLQJV\VWHP:LQGRZV9LVWD)LQGLQJ RQHVROXWLRQWRRNVHFRQGVIRUDîERDUG DQGVHFRQGVIRUDîERDUG $36<67(0)$0,/< )25/2&$/6($5&+ ,QWKLVVHFWLRQZHJLYHDVNHWFKRIWKHGHVLJQRI D3V\VWHPIDPLO\ZKLFKVROYHVWKH1TXHHQV SUREOHPE\XVLQJORFDOVHDUFK ^1`11 (DFK3V\VWHPȆ1VROYHVWKH1TXHHQVSURE OHPLQDQRQGHWHUPLQLVWLFZD\DFFRUGLQJWR WKHVHDUFKLQJPHWKRG7KHPHPEUDQHVWUXFWXUH GRHVQRWFKDQJHDORQJWKHFRPSXWDWLRQDQGZH XVHHOHFWULFDOFKDUJHVRQWKHPHPEUDQHVDVLQ WKHPRGHORIDFWLYHPHPEUDQHV 2QHVWDWHLVUHSUHVHQWHGE\DQ1î1FKHVV ERDUGZKHUH1TXHHQVKDYHEHHQSODFHG,Q RUGHUWROLPLWWKHQXPEHURISRVVLEOHVWDWHVZH FRQVLGHUDQLPSRUWDQWUHVWULFWLRQZHFRQVLGHU WKDWWKHUHLVRQO\RQHTXHHQLQHDFKFROXPQDQG LQHDFKURZ%\XVLQJWKLVUHVWULFWLRQZHRQO\ QHHGWRFKHFNWKHGLDJRQDOVLQRUGHUWRNQRZ ZKHWKHUDERDUGLVDVROXWLRQWRWKHSUREOHP RUQRW 7KHVH ERDUGV FDQ EH HDVLO\ UHSUHVHQWHG LQ 0HPEUDQH &RPSXWLQJ )RU WKH 3 V\VWHP Ȇ1ZHFRQVLGHUDPHPEUDQHVWUXFWXUHZKLFK FRQWDLQV 1 HOHPHQWDU\ PHPEUDQHV ODEHOOHG ZLWK «1 DQG 1 REMHFWV \LL∈^«1` LQ WKHVNLQ%\XVLQJUXOHVRIW\SH\L>@Mo>\L@MWKH REMHFWV\LDUHQRQGHWHUPLQLVWLFDOO\VHQWLQWRWKH PHPEUDQHVDQGWKHREMHFW\LLQVLGHDPHPEUDQH ZLWKODEHOMLVLQWHUSUHWHGDVDTXHHQSODFHGRQ WKHURZLRIWKHFROXPQM)RUH[DPSOHWKH SDUWLDOFRQILJXUDWLRQ>>\@>\@>\@>\@>\@ LVDPHPEUDQHUHSUHVHQWDWLRQRIWKHERDUGLQ )LJXUH ,QRUGHUWRNQRZLIRQHVWDWHLVEHWWHUWKDQ DQRWKHUZHQHHGWRFRQVLGHUDPHDVXUH7KH QDWXUDOPHDVXUHLVWRDVVRFLDWHWRDQ\ERDUGWKH QXPEHURIFROOLVLRQV6RVLF*X7KH QXPEHURIFROOLVLRQVRQDGLDJRQDOOLQHLVRQH OHVVWKDQWKHQXPEHURITXHHQVRQWKHOLQHLI WKH OLQH LV QRW HPSW\ DQG ]HUR LI WKH OLQH LV HPSW\7KHVXPRIFROOLVLRQVRQDOOGLDJRQDO OLQHVLVWKHWRWDOQXPEHURIFROOLVLRQVEHWZHHQ TXHHQV)RUH[DPSOHLIZHGHQRWHE\GSWKH GHVFHQGDQW GLDJRQDO IRU VTXDUHV LM ZKHUH LM S DQG E\ XT WKH DVFHQGDQW GLDJRQDO IRU VTXDUHVLMZKHUHLíM TWKHQWKHERDUGVKRZQ LQ)LJXUHKDVFROOLVLRQVLQXDQGLQG 7KLVEDVLFGHILQLWLRQRIFROOLVLRQVRIDVWDWHFDQ EHUHILQHGLQD0HPEUDQH&RPSXWLQJDOJRULWKP $VZHZLOOVHHEHORZLQRUGHUWRFRPSDUHWZR ERDUGVLWLVQRWLPSRUWDQWWKHH[DFWDPRXQWRI FROOLVLRQVZKHQWKH\DUHJUHDWHUWKDQ 2WKHUNH\GHILQLWLRQVLQWKHDOJRULWKPDUH WKH FRQFHSWV RI QHLJKERU DQG PRYHPHQW ,Q WKLVSDSHUDPRYHPHQWLVWKHLQWHUFKDQJHRI FROXPQVRIWZRTXHHQVE\NHHSLQJWKHURZV ,QRWKHUZRUGVLIZHKDYHRQHTXHHQDWLM DQGDQRWKHUDWNVDIWHUWKHPRYHPHQWWKHVH TXHHQVDUHSODFHGDWLVDQGNM,WLVWULYLDOWR FKHFNWKDWIRUHDFKPRYHPHQWLIWKHRULJLQDO ERDUGGRHVQRWKDYHWZRTXHHQVRQWKHVDPH FROXPQDQGURZWKHQWKHILQDORQHGRHVQRW KDYH LW7KH GHILQLWLRQ RI QHLJKERU GHSHQGV RQWKHGHILQLWLRQRIPRYHPHQWWKHVWDWHVLVD QHLJKERURIVWDWHVLILWFDQEHUHDFKHGIURPV ZLWKRQHPRYHPHQW $FFRUGLQJWRWKHVHGHILQLWLRQVWKHORFDO VHDUFKDOJRULWKPIRUWKH1TXHHQVSUREOHPFDQ EHZULWWHQDVIROORZV  :HVWDUWZLWKDUDQGRPO\FKRVHQVWDWH  :HFKHFNLIWKHQXPEHURIFROOLVLRQVRI WKHFXUUHQWVWDWHLV]HUR ,IVRZHILQLVK7KHKDOWLQJFRQILJXUDWLRQ FRGLILHVWKHVROXWLRQERDUG ,IQRWZHORRNIRUPRYHPHQWVZKLFKUHDFK DVWDWHZLWKDORZHUQXPEHURIFROOLVLRQV ,IWKH\H[LVWZHUDQGRPO\FKRRVHRQHRI WKHSRVVLEOHPRYHPHQWV  7KHUHDFKHGVWDWHEHFRPHVWKHFXUUHQWVWDWH DQGZHJREDFNWR ,IWKH\GRQRWH[LVWZHJREDFNWR )LJXUH)LYHTXHHQVRQDERDUG:HFRQVLGHUWKHRULJLQRIFRRUGLQDWHVDWERWWRPOHIW $WWKLVSRLQWWKUHHEDVLFTXHVWLRQVDULVH IURP WKH GHVLJQ RI 0HPEUDQH &RPSXWLQJ KRZWKHQXPEHURIFROOLVLRQVRIDERDUGLV FRPSXWHG"KRZDEHWWHUVWDWHLVVHDUFKHG" DQGKRZDPRYHPHQWLVSHUIRUPHG" &RPSXWLQJ&ROOLVLRQV 7KHUHSUHVHQWDWLRQRIDQ1î1ERDUGLVPDGH E\XVLQJ1HOHPHQWDU\PHPEUDQHVZKHUHWKH REMHFWV\«\1DUHSODFHG7KHVH1HOHPHQWDU\ PHPEUDQHV ZLWK ODEHOV «1 DUH QRW WKH XQLTXH HOHPHQWDU\ PHPEUDQHV LQ WKH PHP EUDQHVWUXFWXUH7KHUHDUH1íDVFHQGDQWDQG 1íGHVFHQGDQWGLDJRQDOVLQDQ1î1ERDUG $V SRLQWHG DERYH ZH GHQRWH WKH DVFHQGDQW GLDJRQDOVDVX1«X1ZKHUHWKHLQGH[S LQXSGHQRWHVWKDWWKHGLDJRQDOFRUUHVSRQGVWR WKHVTXDUHVLMZLWKLíM S$QDORJRXVO\WKH GHVFHQGDQWGLDJRQDOVDUHGHQRWHGE\G«G11 ZKHUHWKHLQGH[TLQGTGHQRWHVWKDWWKHGLDJRQDO FRUUHVSRQGVWRWKHVTXDUHVLMZLWKLM T %HVLGHV WKH 1 HOHPHQWDU\ PHPEUDQHV ZLWKODEHOV«1IRUHQFRGLQJWKHERDUGZH DOVRSODFH1íHOHPHQWDU\PHPEUDQHVLQWKH VWUXFWXUHZLWKODEHOVX1«X1G«G11 7KHVHPHPEUDQHVZLOOEHXVHGWRFRPSXWHWKH FROOLVLRQV %HDULQJLQPLQGWKHFXUUHQWERDUGHQFRGHG E\PHPEUDQHVZLWKDQREMHFW>\L@MZHFDQXVH UXOHV RI W\SH >\L@M ĺGLM XLM 7KHVH UXOHV DUH WULJJHUHGLQSDUDOOHODQGWKH\SURGXFHDVPDQ\ REMHFWVGTUHVSXSDVTXHHQVZKLFKDUHSODFHG RQWKHGLDJRQDOGTUHVSXS 2EMHFWVGTDQGXSDUHVHTXHQWLDOO\VHQWLQWR WKHHOHPHQWDU\PHPEUDQHVODEHOOHGE\GTDQGXS ,QDILUVWDSSURDFKRQHFDQFRQVLGHUDFRXQWHU ]LZKLFKHYROYHVWR]LLQVLGHHDFKHOHPHQWDU\ PHPEUDQHZKHQDQREMHFWGTRUXSLVVHQWLQ %\XVLQJWKLVVWUDWHJ\WKHLQGH[LRI]LGHQRWHV KRZPDQ\REMHFWVKDYHFURVVHGWKHPHPEUDQH RULQRWKHUZRUGVKRZPDQ\TXHHQVDUHSODFHG RQWKHFRUUHVSRQGLQJGLDJRQDO 7KLVVWUDWHJ\KDVDQLPSRUWDQWGUDZEDFN ,QWKHZRUVWFDVHLIDOOWKHTXHHQVDUHSODFHG RQWKHVDPHGLDJRQDODWOHDVW1VWHSVDUHQHF HVVDU\LQRUGHUWRFRXQWWKHP,QRXUGHVLJQ WKLVLVQRWQHFHVVDU\$VZHZLOOVHHZHRQO\ QHHGWRNQRZLIWKHQXPEHURITXHHQVLQHDFK GLDJRQDOLVRUPRUHWKDQ'XHWRWKH SDUDOOHOLVPRIWKH3V\VWHPVWKLVFDQEHFKHFNHG LQDFRQVWDQWQXPEHURIVWHSVUHJDUGOHVVRIWKH QXPEHURITXHHQV 7HFKQLFDOO\DIWHUXVLQJDFRPSOH[VHWRI UXOHVZKHUHWKHHOHFWULFDOFKDUJHVDUHXVHGWR FRQWUROWKHIORZRI REMHFWV HDFKPHPEUDQH GTVHQGVWRWKHVNLQDFRPSOH[REMHFWRIW\SH GT'$T'%T'&T''TZKHUH'$T'%T'&T ''T∈^`FRGLI\WKHQXPEHURITXHHQVRQWKH GLDJRQDOIRUXSWKHGHYHORSPHQWLVDQDORJRXV ZLWKWKHQRWDWLRQXS8$S8%S8&S8'S:H FRQVLGHUIRXUSRVVLELOLWLHV  GT7KHLQWKHILUVWFRRUGLQDWH GHQRWHVWKDWWKHUHLVQRTXHHQSODFHGRQ WKHGLDJRQDODQGWKHGLDJRQDOLVUHDG\WR UHFHLYHRQHTXHHQDIWHUDPRYHPHQW  GT7KHLQWKHVHFRQGFRRUGLQDWH GHQRWHV WKDW WKHUH LV RQH TXHHQ SODFHG RQWKHGLDJRQDO7KLVGLDJRQDOGRHVQRW FRQWDLQFROOLVLRQVEXWLWVKRXOGQRWUHFHLYH PRUHTXHHQV  GT7KHLQWKHWKLUGFRRUGLQDWH GHQRWHVWKDWWKHUHDUHWZRTXHHQVSODFHG RQ WKH GLDJRQDO7KLV GLDJRQDO KDV RQH FROOLVLRQZKLFKFDQEHVROYHGE\DXQLTXH DSSURSULDWHPRYHPHQW  GT7KHLQWKHIRXUWKGLDJRQDO GHQRWHVWKDWWKHUHDUHPRUHWKDQWZRTXHHQV SODFHGRQWKHGLDJRQDO7KLVGLDJRQDOKDV VHYHUDOFROOLVLRQVDQGLWZLOOKDYHDWOHDVW RQH FROOLVLRQ HYHQ LI RQH PRYHPHQW LV SHUIRUPHG %HDULQJLQPLQGWKDWDGLDJRQDOLVUHDG\WR UHFHLYHTXHHQVTXHHQVRULWQHHGVWRVHQG TXHHQVWRDQRWKHUGLDJRQDORUPRUHTXHHQV ZH FDQ SUHYHQW LI D PRYHPHQW SURGXFHV DQ LPSURYHPHQWLQWKHZKROHQXPEHURIFROOLVLRQV EHIRUHSHUIRUPLQJWKHPRYHPHQW:HGRQRW QHHGWRSHUIRUPWKHPRYHPHQWDQGWKHQWRFRXQW WKHQXPEHURIFROOLVLRQVLQRUGHUWRNQRZLIWKH PRYHPHQWGHFUHDVHVWKHQXPEHURIFROOLVLRQV ,QRUGHUWRGRWKDWZHGLVWLQJXLVKLIWKHSDLU RITXHHQVWREHPRYHGDUHSODFHGRQWKHVDPH GLDJRQDORUQRW )LUVWO\OHWXVFRQVLGHUWZRTXHHQVSODFHG LQWKHVTXDUHVLMDQGNVRIWKHVDPHDVFHQ GDQWGLDJRQDOLHLíM NíV:HZRQGHULIWKH PRYHPHQWRILQWHUFKDQJLQJWKHFROXPQVRIWZR TXHHQVE\NHHSLQJWKHURZVZLOOLPSURYHWKH WRWDOQXPEHURIFROOLVLRQV,QRWKHUZRUGVZH ZRQGHULIUHPRYLQJWKHTXHHQVIURPLMDQG NVSXWWLQJWKHPDWLVDQGNMLPSURYHV WKHERDUG ,QRUGHUWRDQVZHUWKLVTXHVWLRQZHFRQVLGHU WKHIROORZLQJREMHFWV  XLM8&LM8'LM7KHDVFHQGDQWGLDJRQDO XLMKDVDWOHDVWTXHHQVVRWKHILUVWWZRFR RUGLQDWHVDUH7KHSDUDPHWHUV8&LM8'LM FDQEHRUEXWH[DFWO\RQHRIWKHPLV  GLM'%LM'&LM''LM DQG GNV'%NV'&NV''NV7KHGHVFHQGHQW GLDJRQDOVDQGGNVKDYHDWOHDVWTXHHQVR WKHILUVWFRRUGLQDWHLV7KHUHPDLQLQJRQHV FDQEHRUEXWH[DFWO\RQHRIWKHPLV ,WLVHDV\WRFKHFNWKDWWKHUHGXFWLRQLQ WKHZKROHDPRXQWRIFROOLVLRQVSURGXFHGE\ WKHUHPRYDORIWKHTXHHQVIURPWKHVTXDUHV LMDQGNVLV 8&LM8'LM'%LM'&LM ''LM'%NV'&NV''NV $QDORJRXVO\ LQ RUGHU WR FRPSXWH WKH FKDQJHLQWKHQXPEHURIFROOLVLRQVSURGXFHGE\ WKHSODFHPHQWRIWZRTXHHQVLQWKHVTXDUHVLV NMZHFRQVLGHUGLV'$LV'%LV'&LV''LV XLV8$LV8%LV8FLV8'LV DQG XNM8$NM8%NM8&NM8'NM %\XVLQJWKLVQRWDWLRQLWLVHDV\WRFKHFN WKDWWKHDXJPHQWDWLRQLQWKHQXPEHURIFROOL VLRQVLV'$LV8$LV8$NM 7KHPRYHPHQWUHSUHVHQWVDQLPSURYHPHQW LQWKHJHQHUDOVLWXDWLRQRIWKHERDUGLIWKHUHGXF WLRQLQWKHQXPEHURIFROOLVLRQVLVJUHDWHUWKDQWKH DXJPHQWDWLRQ7KLVFDQEHHDVLO\H[SUHVVHGZLWK DVLPSOHIRUPXODGHSHQGLQJRQWKHSDUDPHWHUV 7KLVLVWKHNH\SRLQWLQRXU0HPEUDQH &RPSXWLQJDOJRULWKPVLQFHZHGRQRWQHHG WRSHUIRUPWKHPRYHPHQWDQGWKHQWRFKHFNLI ZHKDYHDQLPSURYHPHQWEXWZHFDQHYDOXDWH LWDSULRULE\H[SORULQJWKHREMHFWVSODFHGLQ WKHVNLQ2EYLRXVO\LIWKHVTXDUHVVKDUHDGH VFHQGDQWGLDJRQDOWKHVLWXDWLRQLVV\PPHWULF ,IWKHTXHHQVGRQRWVKDUHDGLDJRQDOWKH VWXG\LVDQDORJRXVEXWWKHREWDLQHGIRUPXODE\ FRQVLGHULQJWKDWZHJHWDIHDVLEOHPRYHPHQWLI WKHUHGXFWLRQLVJUHDWHUWKDQWKHDXJPHQWDWLRQ LVVOLJKWO\GLIIHUHQW )URPDWHFKQLFDOSRLQWRIYLHZZHFRQVLGHU DILQLWHVHWRIUXOHVZLWKWKHIROORZLQJLQWHUSUHWD WLRQ,IWKHFRUUHVSRQGLQJVHWRIREMHFWV XLM8$LM8%LM8&LM8'LM  GLM'$LM'%LM'&LM''LM XNV8$NV8%NV8&NV8'NV GNV'$NV'%NV'&NV''NV XLV8$LV8%LV8&LV8'LV GLV'$LV'%LV'&LV''LV XNM8$NM8%NM8&NM8'NM GNM'$NM'%NM'&NM''NM LVSODFHGLQWKHVNLQWKHQWKHPRYHPHQWRITXHHQ IURPLMDQGNVWRLVDQGNMLPSURYHV WKHQXPEHURIFROOLVLRQV ,QWKHJHQHUDOFDVHWKHUHZLOOEHPDQ\ SRVVLEOH DSSOLFDWLRQV RI UXOHV RI WKLV W\SH 7KH3V\VWHPFKRRVHVRQHRIWKHPLQDQRQ GHWHUPLQLVWLFZD\7KHDSSOLFDWLRQRIWKHUXOH LQWURGXFHVDQREMHFWFKDQJHLNVLQWKHVNLQ$IWHU DFRPSOH[VHWRIUXOHVWKLVREMHFWSURGXFHVD QHZFRQILJXUDWLRQDQGWKHF\FOHVWDUWVDJDLQ 7KHGHVLJQRIWKH3V\VWHPGHSHQGVRQ1 WKHQXPEHURITXHHQVDQGLWLVUDWKHUFRPSOH[ IURPDWHFKQLFDOSRLQWRIYLHZ,WXVHVFRRSHUD WLRQLQKLELWRUVDQGHOHFWULFDOFKDUJHVLQRUGHU WRFRQWUROWKHIORZRIREMHFWV,QSDUWLFXODUD VHWRIUXOHVKDOWVWKH3V\VWHPLIDERDUGZLWK ]HURFROOLVLRQVLVUHDFKHGDQGDQRWKHUVHWRI UXOHVUHVWDUWVWKH3V\VWHPLHLWSURGXFHVD FRQILJXUDWLRQHTXLYDOHQWWRWKHLQLWLDORQHLI QRPRUHLPSURYHPHQWVFDQEHDFKLHYHGIURP WKHFXUUHQWFRQILJXUDWLRQ )LJXUHVKRZVDVROXWLRQIRXQGZLWKWKH FRUUHVSRQGLQJ3V\VWHPIRUWKHTXHHQVSURE OHP:HVWDUWZLWKDERDUGZLWKDOOWKHTXHHQV LQWKHPDLQDVFHQGDQWGLDJRQDOXSSHUOHIW7KH QXPEHURIFROOLVLRQVLQWKLVGLDJRQDODQGLQWKH ZKROHERDUGLV%\FKDQJLQJTXHHQVIURPWKH FROXPQVDQGZHREWDLQWKHERDUGVKRZQLQ )LJXUHZLWKFROOLVLRQVXSSHUULJKWLQ)LJXUH ,QWKHQH[WVWHSWKHTXHHQVIURPFROXPQV DQGDUHFKDQJHGDQGZHJHWDERDUGZLWK FROOLVLRQVSURGXFHGEHFDXVHWKHWZRPDLQ GLDJRQDOVKDYHWZRTXHHQVHDFKERWWRPOHIW )LQDOO\E\FKDQJLQJTXHHQVLVWKHFROXPQV DQGZHJHWDERDUGZLWKQRFROOLVLRQVWKDW UHSUHVHQWVDVROXWLRQWRWKHTXHHQVSUREOHP ERWWRPULJKW (;3(5,0(17$/5(68/76 $QDGKRF&/,36SURJUDPZDVZULWWHQLQVSLUHG RQWKLV0HPEUDQH&RPSXWLQJGHVLJQ6RPH H[SHULPHQWVZHUHSHUIRUPHGRQDV\VWHPZLWK DQ,QWHO3HQWLXP'XDO&38(DW*+] *%RI5$0DQGXVLQJ&/,369XQGHU WKHRSHUDWLQJV\VWHP:LQGRZV9LVWD 'XHWRWKHUDQGRPFKRRVLQJRIWKHLQLWLDO FRQILJXUDWLRQDQGWKHQRQGHWHUPLQLVPRIWKH3 V\VWHPIRUFKRRVLQJWKHPRYHPHQWH[SHUL PHQWVKDYHEHHQSHUIRUPHGIRUHDFKQXPEHU1RI TXHHQVIRU1∈^«`LQRUGHUWRJHWDQ LQIRUPDWLYHSDUDPHWHU:HKDYHFRQVLGHUHGWKH DYHUDJHRIWKHVHH[SHULPHQWVRQWKHQXPEHU RI3V\VWHPVWHSVDQGWKHQXPEHURIVHFRQGV 7DEOHVKRZVWKHUHVXOWRIWKHH[SHULPHQWV 1RWLFHIRUH[DPSOHWKDWLQWKHVROXWLRQ SUHVHQWHGLQ*XWLpUUH]1DUDQMRDQG3pUH]-L PpQH]WKHVROXWLRQIRUTXHHQVZDV REWDLQHG DIWHU  VHFRQGV 7KH DYHUDJH WLPHREWDLQHGZLWKWKLVDSSURDFKLV VHFRQGV )LJXUH6WDUWLQJIURPDFRQILJXUDWLRQ&ZLWKFROOLVLRQVXSOHIWZHFDQUHDFK&ZLWK FROOLVLRQVXSULJKWWKHQ&ZLWKFROOLVLRQVERWWRPOHIWDQGILQDOO\&ZLWKFROOLVLRQV ERWWRPULJKWZKLFKLVDVROXWLRQWRWKHTXHHQVSUREOHP &21&/86,21 'XHWRWKHKLJKFRPSXWDWLRQDOFRVWRIFODVVLFDO PHWKRGVORFDOVHDUFKKDVEHFRPHDQDOWHUQDWLYH IRUVHDUFKLQJVROXWLRQWRUHDOOLIHKDUGSUREOHPV +RRV6WW]OH%LMDUERRQHK)OHQHU 3HDUVRQ ,QWKLVSDSHUZHSUHVHQWDILUVWDSSURDFK WRWKHSUREOHPRIORFDOVHDUFKE\XVLQJ0HP EUDQH&RPSXWLQJDQGZHKDYHDSSOLHGLWWRWKH 1TXHHQVSUREOHPDVDFDVHVWXG\$VDIXWXUH ZRUNVHYHUDOSRVVLELOLWLHVDULVH2QHRIWKHP LVWRLPSURYHWKHGHVLJQIURPD3V\VWHPSRLQW RIYLHZPD\EHFRQVLGHULQJQHZLQJUHGLHQWV DVHFRQGRQHLVWRFRQVLGHUQHZFDVHVWXGLHV FORVHUWRUHDOOLIHSUREOHPVDWKLUGRQHLVWR LPSOHPHQWWKHGHVLJQLQSDUDOOHODUFKLWHFWXUHV DQGFRPSDUHWKHUHVXOWVZLWKWKHRQHVREWDLQHG ZLWKDRQHSURFHVVRUFRPSXWHU $&.12:/('*0(176 7KHDXWKRUVDFNQRZOHGJHWKHVXSSRUWRIWKH SURMHFWV7,1RIWKH0LQLVWHULRGH &LHQFLDH,QQRYDFLyQRI6SDLQDQGWKHVXSSRUW RIWKH3URMHFWRI([FHOOHQFHRIWKH-XQWDGH $QGDOXFtDJUDQW37,& 5()(5(1&(6 %HUQKDUGVVRQ%([SOLFLWVROXWLRQVWRWKH 1TXHHQVSUREOHPIRUDOO$&06,*$57%XOOHWLQ GRL 7DEOH([SHULPHQWDOUHVXOWV 1XPEHURITXHHQV $YHUDJHQXPEHURIVWHSV $YHUDJHQXPEHURIVHFV                                                             %LMDUERRQHK)+)OHQHU33HDUVRQ- '\QDPLFGHPDQGFDSDFLW\EDODQFLQJIRUDLUWUDIILF PDQDJHPHQW XVLQJ FRQVWUDLQWEDVHG ORFDO VHDUFK )LUVWUHVXOWV,Q3URFHHGLQJVRIWKHWK,QWHUQDWLRQDO :RUNVKRSRQ/RFDO6HDUFK7HFKQLTXHVLQ&RQVWUDLQW 6DWLVIDFWLRQ9ROSS *DUFtD4XLVPRQGR 0 *XWLpUUH](VFXGHUR 5 3pUH]+XUWDGR,3pUH]-LPpQH]0-5LVFRV 1~xH]$$QRYHUYLHZRI3OLQJXD,Q *3ăXQ 0- 3pUH]-LPpQH]$5LVFRV1~xH] *5R]HQEHUJ$6DORPDD(GV3URFHHGLQJV RIWKHWK ,QWHUQDWLRQDO:RUNVKRS RQ 0HPEUDQH &RPSXWLQJ/1&6SS *XWLpUUH]1DUDQMR 0 $ 0DUWtQH]GHO$PRU 0$3pUH]+XUWDGR,3pUH]-LPpQH]0- 6ROYLQJWKH1TXHHQVSX]]OHZLWK3V\VWHPV ,Q3URFHHGLQJVRIWKH6HYHQWK%UDLQVWRUPLQJ:HHN RQ0HPEUDQH&RPSXWLQJ6HYLOOH6SDLQ9RO SS *XWLpUUH]1DUDQMR0$3pUH]-LPpQH]0- 'HSWKILUVWVHDUFKZLWK3V\VWHPV,Q0 *KHRUJKH 7 +LQ]H * 3ăXQ * 5R]HQEHUJ  $ 6DORPDD (GV 3URFHHGLQJV RI WKH (OHYHQWK ,QWHUQDWLRQDO&RQIHUHQFHRQ0HPEUDQH&RPSXWLQJ /1&6SS +RIIPDQ(/RHVVL-0RRUH5&RQ VWUXFWLRQVIRUWKHVROXWLRQRIWKH1TXHHQVSUREOHP 1DWLRQDO0DWKHPDWLFV0DJD]LQH± +RRV++6WW]OH76WRFKDVWLFORFDO VHDUFK)RXQGDWLRQVDSSOLFDWLRQVVWHG6DQ )UDQFLVFR&$0RUJDQ.DXIPDQQ 3ăXQ*0HPEUDQHFRPSXWLQJ$QLQWURGXF WLRQ%HUOLQ*HUPDQ\6SULQJHU9HUODJ 3ăXQ * 5R]HQEHUJ *  6DORPDD$ (GV 7KH2[IRUGKDQGERRNRIPHPEUDQHFRPSXW LQJ2[IRUG8.2[IRUG8QLYHUVLW\3UHVV 3pUH]-LPpQH] 0 - 5RPHUR-LPpQH] È  6DQFKR&DSDUULQL )  &RPSOH[LW\ FODVVHV LQ PRGHOV RI FHOOXODU FRPSXWLQJ ZLWK PHPEUDQHV 1DWXUDO &RPSXWLQJ  ± GRL$ 5XVVHOO6-1RUYLJ3$UWLILFLDOLQWHO OLJHQFH$PRGHUQDSSURDFKQGHG8SSHU6DGGOH 5LYHU1-3UHQWLFH+DOO 6RVLF5*X-(IILFLHQWORFDOVHDUFKZLWK FRQIOLFWPLQLPL]DWLRQ$FDVHVWXG\RIWKH1TXHHQV SUREOHP,(((7UDQVDFWLRQVRQ.QRZOHGJHDQG'DWD (QJLQHHULQJ±GRL (1'127(6  :HDVVXPHWKDWWKHUHDGHULVIDPLOLDUZLWKWKH FRQFHSWVRI0HPEUDQH&RPSXWLQJ:HUHIHU WR3ăXQIRUEDVLFLQIRUPDWLRQLQWKLV DUHDDQGWR3ăXQ5R]HQEHUJDQG6DORPDD IRUDFRPSUHKHQVLYHSUHVHQWDWLRQDQG WKHZHEVLWHKWWSSSDJHSV\VWHPVHXIRUXS WRGDWHLQIRUPDWLRQ  &/,36 LV DQ H[SHUW V\VWHP WRRO RULJLQDOO\ GHYHORSHGE\WKH6RIWZDUH7HFKQRORJ\%UDQFK 67% 1$6$/\QGRQ % -RKQVRQ 6SDFH &HQWHUVHHKWWSFOLSVUXOHVVRXUFHIRUJHQHW  $YDLODEOHIURPWKHDXWKRUV 0LJXHO$*XWLpUUH]1DUDQMRREWDLQHGKLV3K'LQ0DWKHPDWLFVLQ&XUUHQWO\KHLVDSURIHV VRULQWKH&RPSXWHU6FLHQFHDQG$UWLILFLDO,QWHOOLJHQFH'HSDUWPHQWDWWKH8QLYHUVLW\RI6HYLOOH 6SDLQ+HLVDOVRDPHPEHURIWKH5HVHDUFK*URXSRQ1DWXUDO&RPSXWLQJRIWKH8QLYHUVLW\RI 6HYLOOH+LVUHVHDUFKLQWHUHVWLQFOXGHVWRSLFVUHODWHGWR$UWLILFLDO,QWHOOLJHQFHDQG1DWXUDO&RP SXWLQJ+HKDVFRDXWKRUHGPRUHWKDQVFLHQWLILFSDSHUVLQWKHVHDUHDV