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

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

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

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

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

5、的競爭性。
　　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)搜索到潛在的、能夠被識別的更好的解。但是，每一代的子問題獲得的解并不是最好的解。并

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