[發明專利]混合整數非線性規劃問題的群智能與線性規劃協同方法

在審

• 申請號: 201711363333.0
• 申請日: 2017-12-18
• 公開（公告）號: CN108334973A
• 公開（公告）日: 2018-07-27
• 發明（設計）人: 盧建剛;韓金厚
• 申請（專利權）人: 浙江大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00
• 代理公司: 浙江杭州金通專利事務所有限公司 33100
• 代理人: 劉曉春

本發明公開了一種混合整數非線性規劃問題的群智能與線性規劃協同方法，包括求解外層問題的改進粒子群算法與求解內層問題的線性規劃算法；算法具有啟發式算法的全局尋優能力，并且比單純啟發式算法有更快的收斂速度與更少的計算時間；算法引入速度擾動概率函數，提高算法避免陷入局部最優的能力，并備份最優粒子，防止速度擾動后收斂速度變慢的問題；算法考慮到解的魯棒性，通過改進粒子群的適應度函數，有效排除解空間中的尖銳值；算法進一步引入雙重適應度函數和系統容忍度，根據更合理的規則來進行粒子的選取。本發明作為一種通用的混合整數非線性規劃問題的求解策略，可在混合整數非線性規劃問題中廣泛應用，求解效率高，結果可靠，魯棒性好。

技術領域

本發明屬于系統工程領域，尤其是涉及混合整數非線性規劃問題的群智能與線性規劃協同方法。

背景技術

混合整數非線性規劃問題(Mixed Integer Non-Linear Programming，簡稱MINLP)是一類包含連續變量與離散變量的非線性規劃問題。MINLP的應用涵蓋科學、工程、生活等諸多領域：化工生產的計劃和調度問題，電力市場機組組合問題，物流基地布局優化問題，設計、組合及控制相互作用問題，在不定條件下的過程組合和設計應用問題，水資源管理和共享問題等。

過去幾十年來，MINLP問題一直是國際研究的前沿。然而，由于MINLP問題的復雜性，如何有效求解MINLP問題的算法，一直是科技界與企業界所面臨的重大挑戰，迄今為止尚未很好地解決。求解MINLP的確定性算法諸如分支定界法、廣義分解法、擴展割平面法，對于規模不大的凸模型，這些方法求解是可行的，但當目標函數呈現出強非線性、優化變量維數很大、可行區域非凸時，確定性算法存在著難以保證全局最優解甚至無法求解等諸多問題；因此啟發式算法得到越來越廣泛的應用，算法通過模仿自然界的生物行為方式或者物質的運動形態來求解優化問題，諸如遺傳算法、蟻群算法、粒子群算法，理論上具有全局尋優的能力，然而啟發式算法在可行區域非凸時，容易陷入局部最優值，并且在變量維數很大時，收斂的速度慢，計算時間長，從而限制了它們的推廣應用。

發明內容

為了解決背景技術中存在問題，本發明的目的在于，提供混合整數非線性規劃問題的群智能與線性規劃協同方法。

為此，本發明的上述目的通過以下技術方案來實現：

混合整數非線性規劃問題的群智能與線性規劃協同方法，其特征在于，將混合整數非線性規劃問題劃分為外層問題與內層問題，內層問題為線性規劃問題或弱非線性規劃問題，外層問題為混合整數非線性規劃問題去除內層問題后留下的問題；外層問題采用外層問題求解模塊進行求解，外層問題求解模塊采用群智能算法；內層問題采用內層問題求解模塊進行求解，內層問題求解模塊采用線性規劃算法；在外層問題采用外層問題求解模塊進行求解后，混合整數非線性規劃問題簡化更新為內層問題；在內層問題采用內層問題求解模塊進行求解后，混合整數非線性規劃問題又簡化更新為外層問題，再次求解；外層問題與內層問題如此不斷循環求解與簡化更新，直到混合整數非線性規劃問題得到收斂的解。

在采用上述技術方案的同時，本發明還可以采用或者組合采用以下進一步的技術方案：

優選地，所述群智能算法為粒子群算法。

優選地，所述線性規劃算法為單純形算法。

優選地，在粒子群算法中引入速度擾動概率函數，速度擾動概率函數與求解所得最優值沒有明顯更新的代數正相關，隨著速度擾動概率函數的增大，種群中的粒子位置與速度發生變異以增加搜索全局最優的能力。