多目标優化模型求解方案
文章目錄
- (1) 概念引入
-
- 1.多目标優化模型
- 2.支配
- (2) 多目标優化的傳統解法
- (3) 智能優化算法
- (3) matlab的智能優化算法
-
- 1. 基本的兩個函數
- 2. 例子
- 3. 如果有三個目标
(1) 概念引入
1.多目标優化模型
- 數學模型(一般都轉化成最小問題) min F ( x ) = ( f 1 ( x ) , f 2 ( x ) , … , f m ( x ) ) s . t . x ∈ Ω \min{F(x)}=(f_1(x),f_2(x),\dots,f_m(x))\\ ~~\\ s.t. x\in\Omega minF(x)=(f1(x),f2(x),…,fm(x)) s.t.x∈Ω
- 決策空間： x = ( x 1 , x 2 , … , x n ) x=(x_1,x_2,\dots,x_n) x=(x1,x2,…,xn)所在的空間 Ω \Omega Ω，其中 Ω = { x ∈ R n ∣ g i ( x ) ≤ 0 , i = 1 , 2 , … , p } \Omega=\{x\in R^n|g_i(x)\le0,i=1,2,\dots,p \} Ω={x∈Rn∣gi(x)≤0,i=1,2,…,p}。
- 目标空間： m m m維向量 F ( x ) F(x) F(x)所在的空間。
2.支配
- 定義1：對最小化問題，一個向量 u = ( u 1 , u 2 , … , u w ) u=(u_1,u_2,\dots,u_w) u=(u1,u2,…,uw) 稱為支配(優于)另一個向量 v = ( v 1 , v 2 , … , v w ) v=(v_1,v_2,\dots,v_w) v=(v1,v2,…,vw)，當且僅當 u i ≤ v i i = 1 ， 2 ， ⋯ ， m u_i\le v_i i=1，2，\dotsb，m ui≤vii=1，2，⋯，m 且 ∃ j ∈ { 1 ， 2 , ⋯ , m } ， u j < v j 。 \exist j\in\{1，2,\dotsb,m\}，u_j<v_j。 ∃j∈{1，2,⋯,m}，uj<vj。
- 定義2：對于任意兩個自變量向量 x 1 ， x 2 ∃ Ω x_1，x_2\exist\Omega x1，x2∃Ω,如果下列條件成立： f i ( x 1 ) ≤ f i ( x 2 ) , ∀ i ∈ { 1 , 2 , ⋯ , m } f j ( x 1 ) ≤ f j ( x 2 ) , ∀ j ∈ { 1 , 2 , ⋯ , m } f_i(x_1)\le f_i(x_2),\forall i\in\{1,2,\dotsb,m\}\\ f_j(x_1)\le f_j(x_2),\forall j\in\{1,2,\dotsb,m\} fi(x1)≤fi(x2),∀i∈{1,2,⋯,m}fj(x1)≤fj(x2),∀j∈{1,2,⋯,m}則稱 x 1 x_1 x1 支配 x 2 x_2 x2。
- 定義3：
- 如果 Q Q Q 中沒有支配（優于） x x x 的解，則稱 x x x 是問題的一個Pareto最優解。
- Pareto最優解的全體被稱作Pareto最優解集；Pareto最優解集在目标函數空間的像集稱為Pareto Front（Pareto前沿，陣（界）面）。
(2) 多目标優化的傳統解法
- 權重法
- 理想點法(TOPSIS)
- 分層序列法(就是每次先求出一個最優值，然後把這個最優值當作不等式限制)
- 把 m m m 個目标篇按重要程度排序。假定 f 1 ( x ) f_1(x) f1(x) 最重要， f m ( x ) f_m(x) fm(x) 最不重要。
- 先求問題 min f 1 ( x ) s . t . x ∈ Ω \min{f_1(x)}\\s.t. x\in\Omega minf1(x)s.t.x∈Ω 的最優解 x ( 1 ) x^{(1)} x(1) 及最優值 f 1 ∗ f_1^* f1∗。
- 再求問題 min f 2 ( x ) s . t . x ∈ Ω 1 = Ω ∩ { x ∣ f 1 ( x ) ≤ f 1 ∗ } \min{f_2(x)}\\s.t. x\in\Omega_1=\Omega\cap\{x|f_1(x)\le f_1^*\} minf2(x)s.t.x∈Ω1=Ω∩{x∣f1(x)≤f1∗} 的最優解 x ( 1 ) x^{(1)} x(1) 及最優值 f 1 ∗ f_1^* f1∗。
- 重複上面的步驟。
(3) 智能優化算法
- 這裡選取 NSGA-II 方法
- 算法簡介
- 首先随機産生種群規模為 N N N 的初始種群 P t P_t Pt，進化代數 t = 0 t=0 t=0。
- 開始循環，對 P t P_t Pt 進行交叉變異操作生成新種群 Q t Q_t Qt。
- 取 R t = P t ∪ Q t R_t=P_t\cup Q_t Rt=Pt∪Qt。
- 對 R t R_t Rt 進行非劣分類。
- 按非劣等級從低到高選出 N N N 個個體填充到 P t + 1 P_{t+1} Pt+1 中。
- 擷取 R t R_t Rt 中的第一非劣等級個體集，判斷并決定該非劣等級能否全被新種群容納。如果能，将該非劣等級的所有個體填充到新種群中，繼續判斷下一非劣等級能否全被新種群容納。
- 如此反複，直到不能容納該非劣等級的所有個體,假設為第 i + 1 i+1 i+1 級。對最後不能被完全容納的非劣組中的個體求其擁擠距離,并選擇分布最廣的個體填充滿新種群。
- 重複
- 快速非支配排序方法
- 首先不被任何點支配的點選出來，成為 F 1 F_1 F1。
- 把選出來的點支配的點的支配關系全部删除，然後再看現在有哪些點不被任何點支配，成為 F 2 F_2 F2.
- 擁擠距離 d i = ∑ m = 1 M ∣ f m i + 1 − f m i − 1 ∣ d_i=\sum_{m=1}^{M}|f_m^{i+1}-f_m^{i-1}| di=m=1∑M∣fmi+1−fmi−1∣
- d i d_i di 表示第 i i i 個個體的擁擠距離。
- i − 1 i-1 i−1 和 i + 1 i+1 i+1 是個體 i i i 沿着 i i i 所在的Pareto Front Line 的兩邊鄰近的兩個個體。
- f m i + 1 f_m^{i+1} fmi+1 和 f m i − 1 f_m^{i-1} fmi−1 分别表示 i − 1 i-1 i−1 和 i + 1 i+1 i+1 個個體第 m m m 個目标函數值。(下面的圖 m = 1 , 2 m=1,2 m=1,2)
(3) matlab的智能優化算法
1. 基本的兩個函數
- 參數設定
-
options=gaoptimset('paretoFraction',0.3,'populationsize',100'generations',200,'stallGenLimit',200,'TolFun',1e-10,'PlotFcns',@gaplotpareto);
-
paretoFraction
-
populationsize
-
generations
-
stallGenLimit
-
TolFun
-
gaplotpareto
-
- 函數引用
-
[X,FVAL]=gamultiobj(fitnessfcn,nvars,A,b, Aeq,beq,lb,ub,nonlcon,options))
-
fitnessfcn
-
nvars
-
ub,lb
-
A,b
-
Aeq,beq
-
2. 例子
- 函數定義
%%這裡定義該函數
function y=Fun(x)
y(1)=x(1);
y(2)=(1+x(2))/x(1);
- 進行計算
%%這裡賦初值并且進行多目标優化的計算
fitnessfcn=@Fun;
nvars=2;
lb=[0.1,0];
ub=[1,5];
A=[-9,-1;-9,1];
b=[-6;-1];
Aeq=[];
beq=[];
options=gaoptimset('paretoFraction',0.4,'populationsize',200,'generations',300,'stallGenLimit',300,'TolFun',1e-10,'PlotFcns',@gaplotpareto);
[x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)
- 結果
3. 如果有三個目标
- 可以先優化出來，得到
fval
scatter3
- 對上面的問題增加條件 m i n x 1 + x 2 min~{x_1+x_2} min x1+x2
- 增加
scatter3(fval(:,1),fval(:,2),fval(:,3))
- 得到結果