基于Memetic和量子免疫克隆的大規(guī)模限量弧路由問題研究.pdf

1、限量弧路由規(guī)劃問題(Capacitated Arc Routing Problem)是一個(gè)經(jīng)典的NP-Hard組合優(yōu)化問題，特別是大規(guī)模限量弧路由問題（LSCARP）在社會(huì)生活中有著廣泛的應(yīng)用，受到了眾多研究者的不斷研討。CARP問題隨著實(shí)例規(guī)模的增大其復(fù)雜性會(huì)增強(qiáng)，無法對(duì)其進(jìn)行精確求解。因此，本文基于路線距離分組的合作協(xié)同進(jìn)化算法（RDG-MAENS）提出了運(yùn)用各類搜索算法的搜索特性、量子免疫克隆算法的高度進(jìn)化的特點(diǎn)和協(xié)同進(jìn)化的并行進(jìn)

2、化選解特征來求解大規(guī)模限量弧路由問題。本文主要工作如下：
　　1)用于求解CARP問題的已有算法存在解的穩(wěn)定性差和易陷入局部最優(yōu)等問題，于是本文提出了基于擴(kuò)展步長(zhǎng)和統(tǒng)計(jì)濾波的memetic算法用于求解限量弧路由問題(ESMAENS)，該方法對(duì)MAENS算法的全局搜索策略和局部搜索策略兩方面進(jìn)行改進(jìn)。首先，ESMAENS算法采用路線距離分組方案（RDG分解方案）將大規(guī)模CARP問題分解為若干獨(dú)立的子問題。然后，利用演化算子將初始化種

3、群演化為一個(gè)新的群體，在種群的全局搜索策略中引入擴(kuò)展步長(zhǎng)的搜索策略對(duì)當(dāng)前解的鄰域進(jìn)行搜索。最后，在局部搜索策略中，采用統(tǒng)計(jì)過濾器濾掉對(duì)最佳解決方案沒有改進(jìn)的解，使得算法可以獲得更好的下界，并提高算法的穩(wěn)定性。通過對(duì)Beullen’C, D, E, F, egl和EGL-G測(cè)試集進(jìn)行測(cè)試，與RDG-MAENS算法進(jìn)行對(duì)比，結(jié)果表明ESMAENS算法用于求解CARP問題的優(yōu)越性明顯。
　　2)針對(duì)現(xiàn)有算法求解LSCARP問題的不足之處

4、提出量子免疫克隆算法用于求解大規(guī)模限量弧路由問題(QICA-CARP)。在本文中，將人工免疫系統(tǒng)的概念和量子計(jì)算的特點(diǎn)結(jié)合用于求解限量弧路由問題。針對(duì)這種用量子編碼表示抗體的方式，通過量子旋轉(zhuǎn)門變異策略，使用當(dāng)前最優(yōu)抗體的信息來增加抗體的多樣性。同時(shí)，采納量子交叉操作來加強(qiáng)鄰域之間信息的交流，從而增加解的多樣性，防止陷入局部最優(yōu)。并且，采用修正算子對(duì)不可行解進(jìn)行修正，保證解的多樣性，使其逼近最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，該算法得到的結(jié)果具有極大

5、的競(jìng)爭(zhēng)性。
　　3)研究了LSCARP問題中更加復(fù)雜的模型—多目標(biāo)大規(guī)模限量弧路由問題(MO-LSCARP)。在2014年，梅一等人提出了一種非常優(yōu)秀的基于路線距離分組的合作協(xié)同進(jìn)化算法（RDG-MAENS），該算法已被證明在用于求解大規(guī)模限量弧路由問題上優(yōu)于現(xiàn)有的其它算法，然而，該算法仍然有改進(jìn)的空間。首先，雖然RDG-MAENS算法可以在解空間內(nèi)搜索到潛在的、能夠被識(shí)別的更好的解。但是，每一代的子問題獲得的解并不是最好的解。并

6、且，搜索到的到目前為止最好的解并沒有馬上運(yùn)用于當(dāng)前子代的求解。同時(shí)，RDG分組方案只是單純根據(jù)路徑的接近程度來決定該個(gè)體所屬的子種群，這種分配方式在用于求解多目標(biāo)問題時(shí)有可能會(huì)導(dǎo)致各個(gè)子種群之間的個(gè)體數(shù)目和資源分配不均衡。其次，該算法僅運(yùn)用于求解大規(guī)模單目標(biāo)的限量弧問題。針對(duì)上述問題，本文對(duì)RDG-MAENS算法在求解子問題時(shí)解及時(shí)更替并立即通過鄰域共享運(yùn)用于當(dāng)前子代的求解，以及根據(jù)路徑方向向量的大小提出一種快速簡(jiǎn)單的分配方式判斷路由所