基于量子進(jìn)化算法的機(jī)器人聯(lián)盟編組優(yōu)化研究.pdf

1、機(jī)器人聯(lián)盟問(wèn)題屬于NP完全的復(fù)雜的組合優(yōu)化問(wèn)題。基于量子衍生機(jī)制的量子信息表達(dá)方式與量子門(mén)干涉推理方法是一種潛在的可行解決辦法。量子概率編碼的表達(dá)多樣性和量子進(jìn)化算法的并行搜索能力，使得量子進(jìn)化算法很適合于求解組合優(yōu)化問(wèn)題。量子進(jìn)化算法在求解典型的組合優(yōu)化問(wèn)題上的成功，啟發(fā)了我們將其應(yīng)用到機(jī)器人聯(lián)盟問(wèn)題。 本文分析了機(jī)器人單個(gè)聯(lián)盟以及聯(lián)盟結(jié)構(gòu)生成問(wèn)題的特點(diǎn)，對(duì)當(dāng)前機(jī)器人聯(lián)盟生成算法進(jìn)行了總結(jié)和分類(lèi)，并分析各自算法的優(yōu)點(diǎn)和不足，指

2、出啟發(fā)式算法與進(jìn)化算法的結(jié)合是解決機(jī)器人聯(lián)盟生成問(wèn)題的有效途徑。并將量子進(jìn)化算法應(yīng)用到機(jī)器人單個(gè)聯(lián)盟以及聯(lián)盟結(jié)構(gòu)生成問(wèn)題，運(yùn)用編碼的映射將資源配置和任務(wù)分配合并為一個(gè)過(guò)程，降低了問(wèn)題的復(fù)雜性。實(shí)驗(yàn)結(jié)果表明了本文算法對(duì)解決單個(gè)聯(lián)盟問(wèn)題以及聯(lián)盟結(jié)構(gòu)生成問(wèn)題的有效性與先進(jìn)性。 本文的主要的研究?jī)?nèi)容和成果如下： （1）對(duì)機(jī)器人聯(lián)盟及其相關(guān)問(wèn)題進(jìn)行了探討，包括聯(lián)盟問(wèn)題的提出，機(jī)器人聯(lián)盟問(wèn)題和聯(lián)盟環(huán)境的形式化描述，單個(gè)聯(lián)盟問(wèn)題以及聯(lián)

3、盟結(jié)構(gòu)問(wèn)題的數(shù)學(xué)模型以及聯(lián)盟問(wèn)題解空間復(fù)雜性的分析。 （2）針對(duì)單個(gè)聯(lián)盟問(wèn)題，提出了基于量子進(jìn)化算法的單個(gè)聯(lián)盟算法。并針對(duì)基本的量子進(jìn)化算法引入“基于信息正反饋的島嶼模型”對(duì)其改進(jìn)，采用進(jìn)化方程對(duì)量子門(mén)進(jìn)行更新，使其具有更快的收斂速度和不再易于陷入局部極值。對(duì)比實(shí)驗(yàn)結(jié)果表明，算法不但保持了量子進(jìn)化算法并行性、魯棒性強(qiáng)等優(yōu)點(diǎn)，而且提高了解的質(zhì)量，加快了收斂速度，不易陷入局部極值，收斂穩(wěn)定性較高。同時(shí)算法基于島嶼模型的信息反饋機(jī)制和

4、采用進(jìn)化方程對(duì)量子門(mén)進(jìn)行更新比基本的量子進(jìn)化算法機(jī)制更靈活、更有效、有更高的魯棒性，可以有效減少聯(lián)盟生成的搜索時(shí)間和計(jì)算量，可實(shí)現(xiàn)性較好。 （3）針對(duì)聯(lián)盟結(jié)構(gòu)問(wèn)題，提出了基于量子進(jìn)化算法的聯(lián)盟結(jié)構(gòu)生成算法。運(yùn)用編碼的映射，將資源組合和任務(wù)分配合并為一個(gè)過(guò)程，降低了問(wèn)題的復(fù)雜性，根據(jù)聯(lián)盟結(jié)構(gòu)生成問(wèn)題的特點(diǎn)，在采用量子進(jìn)化算法求解的時(shí)候，對(duì)量子進(jìn)化算法中的相關(guān)部分（量子編碼、適應(yīng)度函數(shù)等）重新進(jìn)行了設(shè)計(jì)。對(duì)比實(shí)驗(yàn)結(jié)果表明，算法在聯(lián)盟