[發明專利]一種用于0-1規劃的AB-DPSO優化算法

在審

• 申請號: 201711312663.7
• 申請日: 2017-12-08
• 公開（公告）號: CN108021976A
• 公開（公告）日: 2018-05-11
• 發明（設計）人: 田慧欣;帥民偉
• 申請（專利權）人: 天津工業大學
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明是一種基于AB?DPSO(改進的具有自適應性、適應于二進制編碼或0?1變量的差分進化(DE)?粒子群(PSO)混合算法)的優化算法。包括下列步驟：(1)參數初始化(包括PSO算法和DE算法的部分參數)。(2)初始化種群，獲取最優個體和最優適應度值，并將種群劃分為P種群和D種群兩部分。(3)進化開始，分別對PSO算法的P種群進行速度、位置自適應更新；DE算法對D種群進行變異、交叉、選擇操作的自適應性更新。(4)記錄每一代中P種群的最優個體和相應的適應度值；D種群中的最優個體和相應的適應度值。(5)比較兩個種群的個體，判斷是否滿足論壇式交互學習條件，如果滿足，則進行優勢互補，更新兩種群的個體；否則轉(7)。(6)優勢互補，篩選P種群和D種群中的較好個體組成新的種群，并更新P種群和D種群為篩選后的種群。(7)記錄歷史最優解，判斷是否到達最大迭代次數，或者滿足精度要求，滿足則輸出最優個體和最佳適應度值，否則轉(3)。算法結束。AB?DPSO算法使PSO算法、DE算法應用于二進制編碼或0?1變量的優化需求中，并且能夠有效的改善算法的性能，避免陷入局部最優。

技術領域

本發明——一種用于0-1規劃的AB-DPSO(改進的DE與PSO的混合優化算法)優化算法，是針對優化問題中決策變量為0-1變量，或者使用二進制編碼的特殊性提出的，本發明屬于優化算法領域。

背景技術

截止2016年末，我國高速運營里程已經達到2.2萬公里，高速鐵路逐步成為人們出行的重要交通工具，高速鐵路占整個鐵路客運比重達到38％。隨著高速鐵路規模的日益擴大，高速鐵路的安全、高效運營面臨著嚴峻的挑戰。高速列車運營的組織和優化是高速鐵路安全平穩運行的同時滿足旅客出行需求、確保我國鐵路運營的經濟效益和市場效益雙贏的重要保證。一個高效的列車開行方案能夠合理編排動車組、安排各站點的?？浚岣哞F路運輸的經營策略和服務質量。

高速鐵路開行方案優化問題通常轉化為一個給定客流OD情況下的最優列車停站組合問題。停站方案的優化一直以來是旅客列車開行優化方案中的一個重要的優化問題。列車停站方案是在列車徑路、類別、編組數量、開行頻率確定后，根據客流需求和列車協調配合情況確定各列車的停站序列。合理的停站方案能夠方便旅客的出行和換乘，滿足旅客多元化需求，吸引節點客流，能夠降低鐵路企業運營成本，增加鐵路企業的下效益，提升鐵路在多種運輸方式中的競爭力。

粒子群算法(Particle Swarm Optimization，PSO)是模仿鳥類在空間覓食過程的仿生學算法，優化的最優解是鳥群尋找到的“食物”。它是參照群體中當前處于最優位置的個體和個體自身到達過的最優位置來調整粒子下一步的搜尋方向和大小，由于算法收斂速度快，設置參數少，易于實現，在諸多領域得到了廣泛的應用。但也存在著易于陷入局部最優的不足；差分進化算法(Differential Evolution，DE)是一種基于群體差異的啟發式隨機搜索算法，其特有的競爭生存策略可以動態跟蹤當前的搜索情況，降低了遺傳算法的復雜性，具有結構簡單、容易實現、收斂快速、魯棒性強等特點。但是如果控制參數和進化策略選擇不當，在進化過程中容易造成種群多樣性降低，個體間差異的減小會導致個體集中于某一局部最優點，而使種群整體過早收斂。兩種算法都是基于種群的啟發式全局搜索算法，對于實值參數的優化具有較強的魯棒性。由于更新操作的性質，使得上述算法在0-1規劃中未展現很好的性能。

針對上述問題和算法應用的特殊性，同時考慮到單純使用一種優化算法面對較大解空間時可能陷入局部最優的不足，本文在改進PSO算法和DE算法尋優性能，并將其應用于0-1規劃的同時，將兩種算法混合。這樣既保證了算法的優化質量，防止單一算法陷入局部最優解，又使該算法能夠成功的應用于 0-1規劃當中，延伸算法的應用范圍。

發明內容

本發明的基于AB-DPSO混合優化算法具體步驟如下：