[發明專利]一種針對大規模復雜優化問題的樣本點快速轉化算法

在審

• 申請號: 201910276509.1
• 申請日: 2019-04-08
• 公開（公告）號: CN109992905A
• 公開（公告）日: 2019-07-09
• 發明（設計）人: 周才華;王博;趙海心;宋志博;李桐;徐勝利;郝鵬;畢祥軍;杜凱繁;明世朝
• 申請（專利權）人: 大連理工大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 隋秀文;溫福雪

1.一種針對大規模復雜優化問題的樣本點快速轉化算法，其特征在于，步驟如下：

步驟1：將大規模復雜優化問題T，按照需求分組為t₁、t₂、t₃…多組子問題

其中，假設原優化問題T中的設計變量為x_m、x_n、x_p、x_q、x_a、x_b…，假設變量分組后子問題t_i中的設計變量為x_m、x_n、x_p、x_q，則原優化問題T中其余的設計變量x_a、x_b…在t_i中為常數項；

步驟2：依據不同組子問題設計變量間的耦合屬性，將每個子問題中設計變量分解為耦合項與非耦合項

假設兩組子問題t_i、t_j，每個子問題包含不少于一個設計變量；

原優化問題T中存在不同子問題間的耦合關系：即子問題t_i中的一個設計變量或多個設計變量與子問題t_j中的一個設計變量或多個設計變量之間存在耦合關系；則對于子問題t_i設計變量分解為耦合項與非耦合項，耦合項即為與耦合設計變量相關的項，非耦合項即為與耦合設計變量無關的項，與非耦合設計變量相關項；

步驟3：建立任一組子問題的代理模型并進行優化，得到每組子問題的最優解，若任一組子問題t_i中設計變量的最優解與其余子問題t_j、t_k…的常數項的差值在一定誤差限內，則整個優化問題收斂，最優解為每組子問題最優解的集合，若不收斂則進行步驟4；

步驟4：運用SPTA算法更新樣本集并進行優化迭代至收斂，包括以下子步驟：

所述的樣本集為構建代理模型所需要的樣本點的集合；

步驟401：少量樣本點的重新計算

進行少量樣本點的重新計算，以求解相鄰迭代步間的迭代差值，總結出迭代差值與耦合項間的數學關系，需重新計算的樣本點個數如下式所示：

u＝v(g/h)

其中，u為需計算的樣本點個數，v為總樣本點個數，g為耦合變量個數，h為總設計變量個數；

步驟402：更新每組子問題常數項值

對于子問題t_i中的設計變量，在其余子問題中為常數項；若原優化問題T未收斂時，將本次迭代的設計變量的最優解值作為下一次迭代中其余子問題的初始常數項值，對其余子問題進行相同操作；

步驟403：每組子問題構建代理模型前進行樣本集轉化

構建代理模型前，需要采集樣本點，在傳統迭代優化流程中，每一次迭代過程中，子問題常數項發生變化，故需重新采集樣本點，本發明中通過少量計算下一迭代步的樣本點值，將上一次迭代中構建代理模型的樣本集進行轉化，構建子問題耦合項與樣本集迭代差值間的內嵌代理模型進行樣本集轉化，具體轉化步驟如下：

依據步驟2所述，任一組子問題t_i分解為耦合項與非耦合項，假設子問題t_i的設計變量為x_m、x_n，子問題t_j的設計變量為x_p、x_q，x_n與x_p存在耦合關系，則原問題寫為：

f(t_i，t_j)＝f_mn(x_m，x_n)+f_np(x_n，x_p)+f_pq(x_p，x_q)

其中，f_mn為子問題t_i對應的非耦合項，f_pq為子問題t_j對應的非耦合項，f_np為兩組子問題間的耦合項；

同理，當分組后存在大于兩個以上的子問題時，針對任一問題t_i進行樣本點轉化時，都可將原優化問題T按設計變量間的耦合關系拆分為三大項：優化子問題t_i對應的非耦合項，其它子問題對應的非耦合項，及優化子問題t_i和其它子問題之間的耦合項；

假設對子問題t_i的樣本點進行轉化，子問題t_j中的設計變量為t_i的常數項，相鄰兩次迭代常數項的值發生改變，則樣本點差值為：

Δ＝f(t_i，t_jb)-f(t_i，t_ja)

＝f(x_m，x_n，x_pb，x_qb)-f(x_m，x_n，x_pa，x_qa)

＝[f_mn(x_m，x_n)+f_np(x_m，x_pb)+f_pq(x_pb，x_qb)]

-[f_mn(x_m，x_n)+f_np(x_m，x_pa)+f_pq(x_pa，x_qa)]

＝f_np(x_n，x_pb)-f_np(x_n，x_pa)

+f_pq(x_pb，x_qb)-f_pq(x_pa，x_qa)

＝Δ(x_n)

構建子問題耦合項與樣本集迭代差值間的內嵌代理模型進行樣本集轉化。