量子進化算法用于求解約束多目標優化問題的探析

　　大四了，現在該考慮一下自己畢業論文怎么寫了。本科生畢業論文過不了是很丟臉的事情，所以必須要重視起來。下面文書幫小編給大家帶來一篇論文范文，歡迎閱讀！

        摘 要：本文提出了一種用于解決約束多目標優化問題的方法。本算法在進化算法的基礎上加入了鄰里競爭與鄰里合作算子，并通過引入agent-based模型的設計理念，更加注重個體變化對整個群體的影響。本算法首先使用約束偏離值的方法將約束多目標優化問題簡化為多目標優化問題;然后使用自我更新算子，當新產生的個體優于原先的個體時予以替換;之后通過鄰里競爭與鄰里合作加快種群內部的信息交流;最后加入量子加速算子，通過使用量子旋轉門來擴大計算搜尋范圍提高程序計算速度。本文最后與兩種已有算法進行對比，實驗結果表明，本算法完成了設計目標。在運行時間和輸出結果精度方面都有不錯的表現。

　　關鍵詞：約束多目標優化 約束偏離值 鄰里競爭 量子計算

　　一、引言

　　進化算法是以達爾文的進化論思想為基礎，通過模擬生物進化過程與機制的求解問題的自組織、自適應的人工智能技術。與傳統的優化算法相比，進化計算是一種成熟的具有高魯棒性和廣泛適用性的全局優化方法，具有自組織、自適應、自學習的特性。尤其是在處理多目標優化問題時，進化算法表現出很好的效果。

　　近年來，出現了很多優秀的算法用于解決約束多目標優化問題，其中Deb提出的NSGA-II算法是最為經典的一個算法。NSGA-II成功的將進化算法應用在約束多目標優化問題上，在進化算法的基礎上引入了約束偏離值。Hongguang Li提出了基于agent的進化算法用于求解約束多目標優化問題。算法利用agent概念認為每個個體與其種群內其他個體都有相互的作用和影響，雖然算法精度不是很高但是計算速度很快。本文受到基于agent概念的啟發，希望設計出一個計算速度快，精度高的算法。

　　二、量子進化算法

　　2.1 鄰里競爭與鄰里合作

　　agent-based模型是一種從底層到高層的數學模型，模型更加注重的是每個個體對整個群體的影響，通過改變個體的某些特征和表現從而影響整個整體。本算法在此基礎上，通過模仿自然界種群內部個體之間既有競爭又有合作的關系，設計出了鄰里競爭與鄰里合作算子。鄰里競爭算子采用的是吞并算子，算子表示如下：

　　設對于一個種群共有k個個體X1，X2，…，Xi，每個個體的目標函數值分別為，則：

　　(1)

　　其中表示的是新產生的個體。公式表達的意義是：每個個體與其排名靠后一位的個體進行競爭，將兩者目標函數值進行對比，目標函數值較小的個體成為這一位置上的新個體。

　　鄰里合作算子如下：

　　(2)

　　(3)

　　其中，是個體i、j的第k個決策變量，且。r，u是分布在[0，1]之間的隨機數。

　　2.2 量子計算

　　加入量子算子是為了加快計算速度，希望通過更少的進化代數進化出更加優秀的種群。本算法通過設計出一個對周圍區域具有自適應調整搜索步長的量子旋轉門，從而提升量子計算運行效率。量子計算首先需要將個體的基因編碼從實數編碼形式轉換為量子編碼形式，之后通過量子旋轉門的計算快速搜索周圍空間尋找更加優秀的個體進行輸出。

　　個體在完成量子旋轉門的計算后，個體的基因編碼需要映射回實數域，完成其他計算過程。量子算子的本質也就是通過將個體基因編碼轉換為量子域，通過利用量子計算在量子域具有指數級加速和指數級存儲的能力，快速的尋找最優解的過程。

　　2.3 算法的主要流程

　　圖1為本算法流程圖。算法采用順序結構設計，結構簡單， 在進化計算的基礎上首先使用了約束偏離值的方法，將約束多目標問題進行簡化。其次借鑒了基于agent模型里種群中個體之間又相互的影響和作用，設計了鄰里競爭與鄰里合作算子。又利用了量子計算的加速性能，提升了算法的運行速度。

　　若為第一代種群，本算法通過之前修正好的目標函數向量進行選擇，首先在可行解里選取非支配解，形成種群FeaPop，并在全部種群中尋找非支配解，放入種群NonPop中;若不是第一代種群，則將上一代產生的父代FeaPop與當代的進化種群Pop合并形成NPop，在合并之后的種群里再去尋找可行非支配解形成當代的FeaPop種群，尋找非支配解形成當代的NonPop。變異算子對于防止種群陷入局部最優解起到了重要的作用，本算法采用文獻中非一致性變異算子。

　　三、仿真實驗與結果分析

　　本文的測試問題是Deb提出的六個經典的約束多目標最小化問題， 算法參數設計為：初始種群大小為100，合作概率為0.9， 合作指數為10，變異概率為0.5，非一致系數為2，自我更新指數為20。最大的可行非支配解集FeaPop大小為100，非支配解集NonPop大小為100。對比算法初始種群大小為100， 交叉概率為0.9， 交叉分布指數為15， 變異概率為0.1， 變異分布指數為20。

　　文中所有測試問題均獨立運行30次，我們采用的度量指標分別為GD和算法運行時間。世代距離指標(GD)，是度量算法所得Pareto前端與真實前端之間的距離。其數學表達式如下式所示：

　　(4)

　　其中，，n為個體數目，是中第個個體的目標函數向量與中最近個體間的歐氏距離。GD值越小，所求得的前端就越接近真實前端，解集的收斂性就越好。運行時間則是算法的跑完相同進化代數所需要的時間，時間越短說明算法運行速度越快，本文中涉及到的幾種算法運行代數均為1000代。

　　表1給出本文算法與兩種對比算法運行6測試問題的結果。

　　CTP2、CTP7是尋找離散的幾個線段，CTP3、CTP4兩個問題要尋找的Pareto前端都是離散的端點，CTP5是離散點和線段的組合，CTP6問題是尋找連續的直線。從表中我們可以看出幾種算法對于處理CTP2問題都有不錯的結果，都可以很好地找到幾個離散端點。對于CTP3和CTP4問題由于測試函數難度的加大，算法[3]已不能很好地找出真實Pareto前端所在位置，而NSGA-II、本算法還能找到真實Pareto前端所在區域，不過已經無法做到很精準的定位Pareto前端的位置。對于CTP5，幾種算法在找離散點的能力都很不錯。對于CTP6問題幾種算法都找到了Pareto前端，只是均勻性稍有差異。CTP7問題，除了算法[3]之外也都很好的找到了前端所在區域。

　　4 總結與展望

　　本文算法用于處理約束多目標優化問題，在設計上借鑒了agent-based模型，更加注意種群中個體對整個種群的影響，通過進行自我更新，鄰里協作與鄰里競爭等操作來改變個體的基因編碼，從而改變了整個種群的進化方向進化速度，共同朝著真實的Pareto前端進行進化。并且本算法融入了量子計算，使得程序可以更高效更快捷更準確的去尋找最優解。在和現有的幾種算法的對比上體現出了算法的優勢，在保證精度值的基礎上減少了大量的程序運行時間。不過提高算法的精度仍然是之后研究的重點。如何更好地處理種群中個體之間的關系是我們今后需要進一步做的工作。

【量子進化算法用于求解約束多目標優化問題的探析】相關文章：

優化營商環境問題整改報告05-11

幸福的約束作文02-15

排序算法的算法思想和使用場景總結01-29

進化論作文06-06

用于表白的情書06-13

用于表白的情書10-19

企業實行全面預算管理問題及優化途徑研究的論文（精選8篇）08-02

小學數學簡便算法08-19

幸福的約束作文15篇02-15

幸福的約束作文(15篇)02-15