[發明專利]一種混合模擬退火和粒子群的最優化算法

在審

• 申請號: 201811221492.1
• 申請日: 2018-10-19
• 公開（公告）號: CN109345023A
• 公開（公告）日: 2019-02-15
• 發明（設計）人: 周登極;張會生;馬世喜;韋婷婷;肖旺;關睿;徐明;沈登海
• 申請（專利權）人: 上海交通大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00
• 代理公司: 上海旭誠知識產權代理有限公司 31220
• 代理人: 鄭立

本發明公開了一種混合模擬退火和粒子群的最優化算法，涉及最優化算法技術領域，包括步驟1、利用模擬退火算法進行M次迭代尋優，實施M次模擬退火過程，得到M個解；步驟2、針對從所述步驟1中獲得的所述M個解，實施精英粒子挑選策略，從所述M個解中選出N個精英粒子，將N個所述精英粒子的位置作為下一階段算法的初始解；步驟3、以N個所述精英粒子作為初始粒子，通過粒子群算法進行精確搜索；步驟4、判斷所述步驟3中的所述粒子群算法是否收斂，是否符合迭代終止條件，若符合所述迭代終止條件，迭代結束，并輸出全局最優粒子的相關參數。該算法分階段的對優化問題進行求解，兼顧全局搜索和局部精確搜索兩方面的問題，使優化過程更加快速，結果更加準確。

技術領域

本發明涉及最優化算法技術領域，尤其涉及一種混合模擬退火和粒子群的最優化算法。

背景技術

近幾年來，現實最優化問題越來越向著高維度、強非線性、非凸的方向的發展，面對越來越復雜的優化問題，傳統計算方法的局限性愈加凸顯，催生了智能算法特別是啟發式算法的快速發展。啟發式算法常用來解決難以獲得準確數值解的優化問題，其在處理復雜優化問題時雖然不一定能夠保證獲得精確解，但常常能在合理時間內得到可接受精度的解。啟發式算法的關鍵在于綜合求解時間和解的質量，常見的啟發式算法有模擬退火算法(SA)、遺傳算法(GA)、蟻群算法(ACA)等。眾多的啟發式算法常常難以兼顧搜索效率和搜索質量，容易過早或過晚收斂，從而陷入局部最優點或影響求解速度。為了克服以上缺點，各領域的研究人員相繼提出了各種改良措施。例如，專利CN201410166021.0公開了一種基于優勝劣汰、步步選擇的粒子群優化方法，專利CN201310269649.9公開了一種自適應的直接搜索模擬退火算法。這些技術方案對粒子群算法和模擬退火算法進行了一定程度的改進，但沒有考慮算法在不同階段的不同需求，改進程度有限。

因此，本領域的技術人員致力于開發一種混合模擬退火和粒子群的最優化算法，以兼顧全局搜索和局部精確搜索兩方面的問題，實現在較短時間內針對線性和非線性最優化問題進行求解，使優化過程更加快速，結果更加準確。

發明內容

有鑒于現有技術的上述缺陷，本發明所要解決的技術問題是如何兼顧全局搜索和局部精確搜索，如何克服在求解非線性優化過程中的早熟和陷入局部最優點。

為實現上述目的，本發明提供了一種混合模擬退火和粒子群的最優化算法，包括以下步驟：

步驟1、利用模擬退火算法進行M次迭代尋優，實施M次模擬退火過程，得到M個解；

步驟2、針對從所述步驟1中獲得的所述M個解，實施精英粒子挑選策略，從所述M個解中選出N個精英粒子，將N個所述精英粒子的位置作為下一階段算法的初始解；

步驟3、以N個所述精英粒子作為初始粒子，通過粒子群算法進行精確搜索；

步驟4、判斷所述步驟3中的所述粒子群算法是否收斂，是否符合迭代終止條件，若符合所述迭代終止條件，迭代結束，并輸出全局最優粒子的相關參數。

進一步地，所述步驟1中所采用的所述模擬退火算法的粒子更新方式為：在每次循環過程中在原來的解的基礎上產生擾動Δx，計算得到新點x'＝x+Δx，計算所述新點的函數值并同上一步進行比較，計算差值Δf＝f(x'-x)，如果所述差值小于零則接受所述新點作為新解，并作為下次循環的初始點，如果所述差值大于零，則計算概率P(Δf)；生成一個0～1的隨機數，若所述隨機數小于所述概率P(Δf)，則接受新解，否則放棄。

進一步地，所述概率P(Δf)根據Boltzmann–Gibbs來確定，具體計算公式為：

其中，T為每次循環的溫度，K是Boltzmann常數，f是目標函數。