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

在審

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

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

2.根據權利要求1所述的混合整數非線性規劃問題的群智能與線性規劃協同方法，其特征在于，所述群智能算法為粒子群算法。

3.根據權利要求1所述的混合整數非線性規劃問題的群智能與線性規劃協同方法，其特征在于，所述線性規劃算法為單純形算法。

4.根據權利要求1至3中任意一項所述的混合整數非線性規劃問題的群智能與線性規劃協同方法，其特征在于，在粒子群算法中引入速度擾動概率函數，速度擾動概率函數與求解所得最優值沒有明顯更新的代數正相關，隨著速度擾動概率函數的增大，種群中的粒子位置與速度發生變異以增加搜索全局最優的能力。

5.根據權利要求1至3中任意一項所述的混合整數非線性規劃問題的群智能與線性規劃協同方法，其特征在于，在粒子群算法中引入雙重適應度函數和系統容忍度函數，一個適應度函數為改進的目標函數，另一個適應度函數為定義的約束懲罰函數，兩個適應度函數根據規則來進行最優值的選取；規則為若約束懲罰函數值不大于系統容忍度函數值，比較改進的目標函數值大小進行最優值的選取，若約束懲罰函數值大于系統容忍度函數值，選取約束懲罰函數值較小的作為最優值；其中改進的目標函數中，考慮解的魯棒性，計算時在參數的不確定性集中隨機選取幾組求得的函數均值作為改進的目標函數值。

6.根據權利要求1至3中任意一項所述的混合整數非線性規劃問題的群智能與線性規劃協同方法，其特征在于，在粒子群算法中引入速度擾動概率函數，速度擾動概率函數與求解所得最優值沒有明顯更新的代數正相關，隨著速度擾動概率函數的增大，種群中的粒子位置與速度發生變異以增加搜索全局最優的能力；在粒子群算法中引入雙重適應度函數和系統容忍度函數，一個適應度函數為改進的目標函數，另一個適應度函數為定義的約束懲罰函數，兩個適應度函數根據規則來進行最優值的選取；規則為若約束懲罰函數值不大于系統容忍度函數值，比較改進的目標函數值大小進行最優值的選取，若約束懲罰函數值大于系統容忍度函數值，選取約束懲罰函數值較小的作為最優值；其中改進的目標函數中，考慮解的魯棒性，計算時在參數的不確定性集中隨機選取幾組求得的函數均值作為改進的目標函數值。

7.根據權利要求1至6中任意一項所述的混合整數非線性規劃問題的群智能與線性規劃協同方法，其特征在于，具體包括如下步驟：

步驟(1)：混合整數非線性規劃問題的一般模型為：

minf(x₁,x₂,x₃,y)

s.t.g(x₁,x₂,x₃,y)≤0

h(x₁,x₂,x₃,y)＝0

x₁∈X₁,x₂∈X₂,x₃∈X₃,y∈Y

其中x₁表示強非線性連續變量，l₁為維數(l₁為大于或等于0的整數)；x₂表示線性連續變量，l₂為維數(l₂為大于或等于0的整數)；x₃表示弱非線性連續變量，l₃為維數(l₃為大于或等于0的整數)；y表示整數變量，l₄為維數(l₄為大于0的整數)；g(x₁,x₂,x₃,y)≤0和h(x₁,x₂,x₃,y)＝0分別是不等式和等式約束方程組，維數分別為p和q；

將混合整數非線性規劃問題中的變量分為L₁和L₂兩部分，分別對應外層簡化的混合整數非線性問題和內層線性規劃問題；首先將整數變量y、強非線性連續變量x₁分到L₁中，將線性連續變量x₂分到L₂中；然后將余下的多個弱非線性連續變量x₃逐個分到L₁中，并觀察余下x₃，若余下的x₃存在變量變為線性變量，則將其分到L₂中，并使得x₃盡可能多的分到L₂中，設x₃分到L₂中變量為且變量個數為分到L₁中的變量為且變量個數為分組后有：

其中設L₁變量個數為m₁，L₂變量個數為m₂，則有

步驟(2)：外層改進的粒子群算法首先進行初始化：給定初始種群個數為N；迭代總次數為M；確定速度邊界[V_min,V_max]和位置邊界[L_1min,L_1max]；N個粒子在m₁維中均勻生成初始位置隨機生成初始速度其中l＝1,…,N；

步驟(3)：此時L₁參數固定，問題轉化為線性規劃問題，進入內層采用內層問題求解模塊的線性規劃算法求解參數L₂，參數L₂的解記為其中m為當前迭代次數，初始解記為

步驟(4)：外層改進的粒子群算法引入雙重適應度函數和系統容忍度g，為改進的目標函數，為定義的約束懲罰函數：

其中m為當前迭代次數，g(L₁)≤0為包含L₁變量的不等式約束方程組，方程組個數為p₁，k_g,i為不等式約束方程組懲罰系數，h(L₁)＝0為包含L₁變量的等式約束方程組，方程組個數為q₁，k_h,i為等式約束方程組懲罰系數；

兩個適應度函數根據如下的規則來進行最優值的選取：

當滿足并且時，取與中較小的粒子；否則，取與中較小的粒子；其中g的迭代公式為：

其中mn為的粒子數目，pset為設定值；考慮解的魯棒性，確定的不確定集合：

其中是標稱值，e₁和e₂是不確定度；計算第m次迭代粒子的改進的目標函數時，在x_l的不確定集合中隨機選取參數C次，求均值作為每個粒子的改進的目標函數值：

其中為不確定集合中的隨機值；

根據計算和更新粒子自身最優位置pBest[l]和群體最優位置gBest；

步驟(5)：外層改進的粒子群算法引入速度擾動概率函數：

P＝μ+Re·σ

其中μ和σ是擾動率調節參數，Re為粒子群最優值沒有明顯優化的代數，設第m-1代粒子群最優值為O(m-1)，第m代粒子群最優值為O(m)，其中m>1，若|O(m)-O(m-1)|≤ε，其中ε為最優值明顯變化閾值變量且為正數，則表示第m代粒子群最優值沒有明顯優化，令Re＝Re+1；若|O(m)-O(m-1)|>ε，表示第m代粒子群最優值明顯優化，令Re＝0；

改進的粒子群算法每次更新完粒子的自身最優位置pBest[l]和群體最優位置gBest，將P與(0,1)內的隨機值Pr進行比較，當Re不斷增大時，P大于隨機值Pr的概率將會增大；

當P大于或等于隨機值Pr時，保存當前的gBest，并進行如下的速度擾動：

其中為第l個粒子的速度，m為當前迭代次數，M為迭代總次數，θ為服從標準正態分布N(0,1)的隨機數；

速度擾動后，也將進行更新，問題轉化為線性規劃問題，進入內層采用內層問題求解模塊的線性規劃算法求解參數然后重新計算粒子群的適應度，更新粒子自身最優位置pBest[l]和群體最優位置gBest，并將適應度最差的粒子由備份的gBest代替，Re重置為0；設Re_p為速度擾動后粒子群最優值沒有明顯優化的代數，設第m-1代粒子群最優值為O(m-1)，第m代粒子群發生速度擾動后，最優值為O(m)，若|O(m)-O(m-1)|≤ε，表示粒子群發生速度擾動后最優值沒有明顯優化，令Re_p＝Re_p+1；若|O(m)-O(m-1)|>ε，表示粒子群發生速度擾動后最優值明顯優化，令Re_p＝0；然后進入步驟(6)；

當P小于隨機值Pr時，直接進入步驟(6)；

步驟(6)：判斷是否滿足終止條件m>M或者Re_p>M_p，其中M_p為速度擾動后最優值沒有明顯優化的閾值次數，2≤M_p≤M。若終止條件都不滿足，則令m＝m+1，根據粒子自身最優位置pBest[l]和群體最優位置gBest，按照標準粒子群算法更新速度和位置并返回步驟(2)，若滿足任意一個終止條件，算法結束。