- 相關(guān)推薦
量子進(jìn)化算法用于求解約束多目標(biāo)優(yōu)化問題的探析
大四了，現(xiàn)在該考慮一下自己畢業(yè)論文怎么寫了。本科生畢業(yè)論文過不了是很丟臉的事情，所以必須要重視起來。下面文書幫小編給大家?guī)硪黄撐姆段�，歡迎閱讀！
摘 要：本文提出了一種用于解決約束多目標(biāo)優(yōu)化問題的方法。本算法在進(jìn)化算法的基礎(chǔ)上加入了鄰里競爭與鄰里合作算子，并通過引入agent-based模型的設(shè)計理念，更加注重個體變化對整個群體的影響。本算法首先使用約束偏離值的方法將約束多目標(biāo)優(yōu)化問題簡化為多目標(biāo)優(yōu)化問題;然后使用自我更新算子，當(dāng)新產(chǎn)生的個體優(yōu)于原先的個體時予以替換;之后通過鄰里競爭與鄰里合作加快種群內(nèi)部的信息交流;最后加入量子加速算子，通過使用量子旋轉(zhuǎn)門來擴(kuò)大計算搜尋范圍提高程序計算速度。本文最后與兩種已有算法進(jìn)行對比，實驗結(jié)果表明，本算法完成了設(shè)計目標(biāo)。在運行時間和輸出結(jié)果精度方面都有不錯的表現(xiàn)。
關(guān)鍵詞：約束多目標(biāo)優(yōu)化 約束偏離值 鄰里競爭 量子計算
一、引言
進(jìn)化算法是以達(dá)爾文的進(jìn)化論思想為基礎(chǔ)，通過模擬生物進(jìn)化過程與機(jī)制的求解問題的自組織、自適應(yīng)的人工智能技術(shù)。與傳統(tǒng)的優(yōu)化算法相比，進(jìn)化計算是一種成熟的具有高魯棒性和廣泛適用性的全局優(yōu)化方法，具有自組織、自適應(yīng)、自學(xué)習(xí)的特性。尤其是在處理多目標(biāo)優(yōu)化問題時，進(jìn)化算法表現(xiàn)出很好的效果。
近年來，出現(xiàn)了很多優(yōu)秀的算法用于解決約束多目標(biāo)優(yōu)化問題，其中Deb提出的NSGA-II算法是最為經(jīng)典的一個算法。NSGA-II成功的將進(jìn)化算法應(yīng)用在約束多目標(biāo)優(yōu)化問題上，在進(jìn)化算法的基礎(chǔ)上引入了約束偏離值。Hongguang Li提出了基于agent的進(jìn)化算法用于求解約束多目標(biāo)優(yōu)化問題。算法利用agent概念認(rèn)為每個個體與其種群內(nèi)其他個體都有相互的作用和影響，雖然算法精度不是很高但是計算速度很快。本文受到基于agent概念的啟發(fā)，希望設(shè)計出一個計算速度快，精度高的算法。
二、量子進(jìn)化算法
2.1 鄰里競爭與鄰里合作
agent-based模型是一種從底層到高層的數(shù)學(xué)模型，模型更加注重的是每個個體對整個群體的影響，通過改變個體的某些特征和表現(xiàn)從而影響整個整體。本算法在此基礎(chǔ)上，通過模仿自然界種群內(nèi)部個體之間既有競爭又有合作的關(guān)系，設(shè)計出了鄰里競爭與鄰里合作算子。鄰里競爭算子采用的是吞并算子，算子表示如下：
設(shè)對于一個種群共有k個個體X1，X2，…，Xi，每個個體的目標(biāo)函數(shù)值分別為，則：
(1)
其中表示的是新產(chǎn)生的個體。公式表達(dá)的意義是：每個個體與其排名靠后一位的個體進(jìn)行競爭，將兩者目標(biāo)函數(shù)值進(jìn)行對比，目標(biāo)函數(shù)值較小的個體成為這一位置上的新個體。
鄰里合作算子如下：
(2)
(3)
其中，是個體i、j的第k個決策變量，且。r，u是分布在[0，1]之間的隨機(jī)數(shù)。
2.2 量子計算
加入量子算子是為了加快計算速度，希望通過更少的進(jìn)化代數(shù)進(jìn)化出更加優(yōu)秀的種群。本算法通過設(shè)計出一個對周圍區(qū)域具有自適應(yīng)調(diào)整搜索步長的量子旋轉(zhuǎn)門，從而提升量子計算運行效率。量子計算首先需要將個體的基因編碼從實數(shù)編碼形式轉(zhuǎn)換為量子編碼形式，之后通過量子旋轉(zhuǎn)門的計算快速搜索周圍空間尋找更加優(yōu)秀的個體進(jìn)行輸出。
個體在完成量子旋轉(zhuǎn)門的計算后，個體的基因編碼需要映射回實數(shù)域，完成其他計算過程。量子算子的本質(zhì)也就是通過將個體基因編碼轉(zhuǎn)換為量子域，通過利用量子計算在量子域具有指數(shù)級加速和指數(shù)級存儲的能力，快速的尋找最優(yōu)解的過程。
2.3 算法的主要流程
圖1為本算法流程圖。算法采用順序結(jié)構(gòu)設(shè)計，結(jié)構(gòu)簡單， 在進(jìn)化計算的基礎(chǔ)上首先使用了約束偏離值的方法，將約束多目標(biāo)問題進(jìn)行簡化。其次借鑒了基于agent模型里種群中個體之間又相互的影響和作用，設(shè)計了鄰里競爭與鄰里合作算子。又利用了量子計算的加速性能，提升了算法的運行速度。
若為第一代種群，本算法通過之前修正好的目標(biāo)函數(shù)向量進(jìn)行選擇，首先在可行解里選取非支配解，形成種群FeaPop，并在全部種群中尋找非支配解，放入種群NonPop中;若不是第一代種群，則將上一代產(chǎn)生的父代FeaPop與當(dāng)代的進(jìn)化種群Pop合并形成NPop，在合并之后的種群里再去尋找可行非支配解形成當(dāng)代的FeaPop種群，尋找非支配解形成當(dāng)代的NonPop。變異算子對于防止種群陷入局部最優(yōu)解起到了重要的作用，本算法采用文獻(xiàn)中非一致性變異算子。
三、仿真實驗與結(jié)果分析
本文的測試問題是Deb提出的六個經(jīng)典的約束多目標(biāo)最小化問題， 算法參數(shù)設(shè)計為：初始種群大小為100，合作概率為0.9， 合作指數(shù)為10，變異概率為0.5，非一致系數(shù)為2，自我更新指數(shù)為20。最大的可行非支配解集FeaPop大小為100，非支配解集NonPop大小為100。對比算法初始種群大小為100， 交叉概率為0.9， 交叉分布指數(shù)為15， 變異概率為0.1， 變異分布指數(shù)為20。
文中所有測試問題均獨立運行30次，我們采用的度量指標(biāo)分別為GD和算法運行時間。世代距離指標(biāo)(GD)，是度量算法所得Pareto前端與真實前端之間的距離。其數(shù)學(xué)表達(dá)式如下式所示：
(4)
其中，，n為個體數(shù)目，是中第個個體的目標(biāo)函數(shù)向量與中最近個體間的歐氏距離。GD值越小，所求得的前端就越接近真實前端，解集的收斂性就越好。運行時間則是算法的跑完相同進(jìn)化代數(shù)所需要的時間，時間越短說明算法運行速度越快，本文中涉及到的幾種算法運行代數(shù)均為1000代。
表1給出本文算法與兩種對比算法運行6測試問題的結(jié)果。
CTP2、CTP7是尋找離散的幾個線段，CTP3、CTP4兩個問題要尋找的Pareto前端都是離散的端點，CTP5是離散點和線段的組合，CTP6問題是尋找連續(xù)的直線。從表中我們可以看出幾種算法對于處理CTP2問題都有不錯的結(jié)果，都可以很好地找到幾個離散端點。對于CTP3和CTP4問題由于測試函數(shù)難度的加大，算法[3]已不能很好地找出真實Pareto前端所在位置，而NSGA-II、本算法還能找到真實Pareto前端所在區(qū)域，不過已經(jīng)無法做到很精準(zhǔn)的定位Pareto前端的位置。對于CTP5，幾種算法在找離散點的能力都很不錯。對于CTP6問題幾種算法都找到了Pareto前端，只是均勻性稍有差異。CTP7問題，除了算法[3]之外也都很好的找到了前端所在區(qū)域。
4 總結(jié)與展望
本文算法用于處理約束多目標(biāo)優(yōu)化問題，在設(shè)計上借鑒了agent-based模型，更加注意種群中個體對整個種群的影響，通過進(jìn)行自我更新，鄰里協(xié)作與鄰里競爭等操作來改變個體的基因編碼，從而改變了整個種群的進(jìn)化方向進(jìn)化速度，共同朝著真實的Pareto前端進(jìn)行進(jìn)化。并且本算法融入了量子計算，使得程序可以更高效更快捷更準(zhǔn)確的去尋找最優(yōu)解。在和現(xiàn)有的幾種算法的對比上體現(xiàn)出了算法的優(yōu)勢，在保證精度值的基礎(chǔ)上減少了大量的程序運行時間。不過提高算法的精度仍然是之后研究的重點。如何更好地處理種群中個體之間的關(guān)系是我們今后需要進(jìn)一步做的工作。
【量子進(jìn)化算法用于求解約束多目標(biāo)優(yōu)化問題的探析】相關(guān)文章：
幸福的約束作文02-15
進(jìn)化論作文06-06
用于表白的情書06-13
用于表白的情書10-19
企業(yè)實行全面預(yù)算管理問題及優(yōu)化途徑研究的論文（精選8篇）08-02
幸福的約束作文15篇02-15
幸福的約束作文(15篇)02-15