時間：2023-06-20 18:03:17
序論：速發表網結合其深厚的文秘經驗，特別為您篩選了11篇多目標優化概念范文。如果您需要更多原創資料，歡迎隨時與我們的客服老師聯系，希望您能從中汲取靈感和知識！
多目標規劃最優的思想起初由法國經濟學家V.帕雷托提出，他由政治經濟學的角度將不可比較的多個目標轉化為多個單目標的最優問題，涉及到了多目標規劃的概念。上世紀40年代末，J?馮?諾伊曼和O?莫根施特恩又基于對策論又提出了在多個決策人相互矛盾的前提下引入多目標問題。50年代初，T?C?庫普曼斯從生產和分配的活動中提出多目標最優化問題，引入有效解的概念，并得到一些基本結果。同時，H?W?庫恩和A?W?塔克爾從研究數學規劃的角度提出向量極值問題，引入庫恩-塔克爾有效解概念，并研究了它的必要和充分條件。自70年代以來，多目標規劃的研究越來越受到人們的重視。至今關于多目標最優解尚無一種完全令人滿意的定義，所以在理論上多目標規劃仍處于發展階段。
2、多目標規劃方法優化投資組合的應用分析
某生產車間計劃在10天內安排生產甲類和乙類兩種商品。已知生產甲類商品需要A號配件5組，B號配件3組；生產乙類商品需要A號配件2組，B號配件4組。在十天的計劃期內該生產車間僅提高A號配件180組，B號配件135組。同時，我們還知道該生產車間沒生產一個甲類商品可獲取利潤為20元，生產一個乙類商品可獲取利潤15元。那么，通過以上條件甲乙兩類商品分別生產多少可實現利潤最大呢？下面我們將各項數據列表如下表1所示：
表1
我們假設，X1和X2分別為甲乙兩類商品的生產數量，Z為總利潤，以此可以線性規劃描述此問題，建立數學模型應該是：
（1）
（2）
其中，X1和X2均為整數。理想狀態下，可以利用圖解法即可得出公式（1）的最優解為Z=775，X1=32，X2=9。但是，站在車間生產計劃人員的角度上將，問題往往比較復雜。
首先，這是一種單一目標優化問題。但通常來講，一個規劃問題需要滿足多個條件。例如，例如財務部門的利潤目標：利潤盡可能大；物資部門的節約資金：消耗盡可能?。讳N售部門的適銷對路：產品品種多樣；計劃部門的安排生產：產品批量盡可能大。規劃問題其本質上是多目標決策類問題，只是因為利用線性規劃模型處置，致使生產計劃人員不得已從諸多目標中硬性選擇其中的一種作為線性規劃的數學模型。這樣一來，由數學模型目標函數得到的結果可能會違背部分部門的根部意愿，從而導致生產過程受阻，又或者是從生產計劃開始階段就因為某些矛盾而不能從諸多目標中選取一個最優目標。
其次，線性規劃問題存在最優解的必要條件是可行解集合非空，也就是說各個約束條件之間彼此相容。但在優化投資組合等實際應用問題中有時候也未必能完全滿足這樣的條件。如因設備維修養護、消耗能源或其他產品自身原因導致生產計劃期內不能提供足夠的工時而無法滿足計劃生產的進度和產量，又或者因投資資本有限的束縛生產原材料的供應不能滿足計劃產品的需求等等。
第三，線性規劃問題的可行解和最優解具有非常明確的價值，這些可行解和最優解都依數學函數模型而定。在實際的投資組合應用當中，決策人發出決策后往往還需要對其決策進行某種修正，主要原因就在于數學函數模型與實際問題之間不盡相同，具有一種近似性，也就是建立數學模型時應對實際應用問題進行簡化且不考慮新情況的發生。
計劃人員為決策人提供的數學可行解并不是嚴格意義上的最優解，僅作為決策實現最優的一種參考性計劃方案。上世界六十年代初期，由查恩斯（A?Charnes）和庫柏（W?w?CooPer）提出的目標規劃（Goalprogramming）直接已得到了重視和推廣，該法在處置實際應用問題方面承認諸項決策條件存在的合理性，即便多個決策條件是相互沖突的、相互影響的都具有合理性，在做出最終決策中不會強調絕對的最優性。由此看來，多目標規劃問題可以認為是一種較之于線性規劃問題更切合于實際應用的決策手段。
3、多目標規劃方法優化投資組合的常見途徑
（1）加權法（或效用系數法）。
加權法（或效用系數法）將投資問題中所有的目標進行統一度量（例如以錢或效用系數度量）。本方法的的基本原理是將多目標模型轉化為多個單目標模型。多個目標，有主次不同和輕重緩急不同等區別，最重要的一個目標我們將之賦予為優先因子P1，次重要的目標依次賦予優先因子P2，P3，P4，…，同時約定PK>>PK+1（PK比PK+1擁有更好的優先權）。如果非要將擁有相同優先因子的目標加以區別，我們可以將其分別賦予不同的權系數wj。它的優點在于適用于計算機運算求解可行解和最優解（如線性函數模型可用單純形法求解），而缺點則在于難以找到合理的權系數（如某高速公路建設投資，在減少建設投資和保證施工質量降低交通傷亡事故率之間難以衡量人的生命價值）。
（2）序列法（或優先級法）。
序列法（或優先級法）并不是對每一個目標進行加權，它主要是按照目標的輕重緩急不同將其分為各個不同等級后再行求解。它的優點在于可規避權系數的困擾，適用范圍比較廣，各種決策活動幾乎都可使用。例如，某公司在決定提拔人員，很多單位主要根據該人員的工作積極性、工作能力和對單位的貢獻價值等幾個方面予以考慮，這幾個方面也會按照先后順序依次評定，等級不同參考評定的比重也會有所不同。它的缺點在于難以區分各個目標的輕重等級，難以排定優先順序無法保證最終的求解結果是最令人滿意的。
（3）有效解法（或非劣解法）。
中圖分類號：TP301.6文獻標識碼：A文章編號文章編號：1672-7800（2013）012-0067-04
作者簡介：馬春連（1988-），男，安徽理工大學理學院碩士研究生，研究方向為智能計算；許峰（1963-），男，安徽理工大學理學院教授，研究方向為波譜學和智能計算。
0引言
在科學研究和工程應用中，許多決策問題具有多目標的特點和性質，它們需要同時滿足幾個相互沖突的不同目標，即無法使各個目標同時達到最優，這類問題稱之為多目標優化問題（Multi-objective Optimization Problem， MOP）。多目標優化問題存在一個最優解集合，其中的元素稱為Pareto最優解。
由于多目標進化算法在優化控制、挖掘數據、設計機械、移動網絡規劃等領域的成功應用，使得學術界興起研究進化算法的熱潮。自上世紀80年代以來，人們已提出多種多目標進化算法，比如Srinivas的NSGA，Zitzler的SPEA，Knowles的PAES以及Deb的NSGA-Ⅱ等。
近年來，一些新的進化算法被用來求解多目標優化問題，如蟻群算法、粒子群算法、免疫算法、分布估計算法等。
上世紀90年代末，人工免疫算法開始興起，其思想源于生物的免疫系統，它借鑒了免疫系統的功能、原理和模型并用于進行尋優搜索。由于現在還不能充分認識免疫機理，所以有關免疫算法的研究基本集中在其它算法。我們用免疫原理來改進并構成新的算法，比如免疫神經網絡、免疫遺傳算法等。人工免疫系統算法的自身研究成果并不多，主要有基于克隆選擇原理的克隆選擇算法和基于陰性選擇原理的陰性選擇算法等。
多目標優化; Pareto優勝; Pareto前沿; 演化算法; 自適應
中圖分類號: TP18
文獻標志碼:A
Quick multi-objective evolutionary algorithm based on adaptive Pareto-ε dominance
WANG Jiang-qing1, YANG Xun2
(
1. College of Computer Science, South-Central University for Nationalities, Wuhan Hubei 430074, China;
2. Yan’an General Office, China Executive Leadership Academy,Yan’an Shaanxi 716000, China
)
Abstract:
For multi-objective optimization problems (MOP), it is very important to provide proper and feasible solutions rapidly for the decision makers. A method for MOP was given. First, a conception of Pareto-ε dominance was defined. Then, based on this conception, a new adaptive multi-objective evolutionary algorithm was proposed. The numerical results demonstrate that the new algorithm can improve the process of MOP optimization, and can meet the requirement of the high-speed, effectiveness in application.
For Multi-objective Optimization Problems (MOP), it is very important to provide proper and feasible solutions rapidly for the decision makers. A method for MOP was given. First, a concept of Pareto-ε dominance was defined. Then, based on this concept, a new adaptive multi-objective evolutionary algorithm was proposed. The simulation results demonstrate that the new algorithm can improve the process of MOP optimization, and can meet the requirements of high-speed and effectiveness in application.
Key words:
multi-objective optimization; Pareto dominance; Pareto front; evolutionary algorithm; adaptive
0 引言
科學研究和工程應用中的優化問題大多是多目標優化問題(Multi-objective Optimization Problem,MOP),如車輛路徑路徑問題、QoS路由等。這類問題通常包含若干個相互矛盾且沒有共同量綱的目標 [1-3]。如何在優化過程中既兼顧各目標利益又體現各目標的地位,是求解此類問題的關鍵[4-5]。
多目標優化的目的是使決策者最終能夠找到一個滿意的決策方案。目前在多目標優化算法中,基于Pareto優勝的算法非常流行[6-8]。這些算法主要集中于利用算法找到最大的Pareto最優解集,找到Pareto 前沿與已知全局前沿的最小距離,及找到解的最大寬度等[9-10]。然而,在實際的應用系統中,決策者通常期望算法能夠在較短的時間內提供一個或幾個可采納的解決方案。在算法的效率和解的質量不能同時滿足的情況下,如何快速地給決策者提供合理、易決策、可接受的解決方案,是算法走向實際應用的一個關鍵問題。
本文定義了一種Pareto-ε優勝的概念,并基于此概念提出了一種新的基于ε-優勝的多目標演化算法(Pareto-ε Multi-Objective Evolutionary Algorithm,PEMOEA)。該算法采用一種新的帶調節度的搜索策略以調節搜索的步長,加快算法的收斂,并采用ε的自適應調整策略改進解的質量。實驗結果顯示,新策略可以使搜索更加快速有效地到達Pareto前沿,為決策者提供可行的解決方案。
1 Pareto-ε的相關定義
圖1為Pareto比較搜索示意圖。圖中f1 和f2為兩個子目標,表示搜索空間中的隨機點,所組成的曲線表示最終的Pareto前沿。
圖片
圖1 Pareto比較搜索示意圖
如果從隨機點A出發進行搜索,那么A的附近有B、C、D優于它(極小化)。逐步推進搜索到E、F、G、H,然后搜索到N、O、…、S,最后才能搜索到Pareto前沿…。通過分析發現,從A搜索到最優解,做了許多無用功。如果采取一定的策略,適當調整搜索的步長,搜索速度將會大幅度提高。
定義1 Pareto-ε優勝。向量u=(u1,…,un)ε-優勝于向量v=(v1,…,vn)(表示為u┆華εv)當且僅當i∈{1,…,n},滿足ui≤vi±ε,ε≥0。
與以往文獻的區別在于,本文定義的ε-優勝可以加上ε也可以減去ε:如果加上ε,稱該調節度為帶寬容度的;如果減去ε,稱該調節度為帶苛刻度的。
定義2 Pareto-ε無差別。向量u=(u1,…,un)無差別于向量v=(u1,…,un)當且僅當i∈{1,…,n} 滿足|ui-vi|≤ε,ε≥0。
定義3 Pareto-ε最優解。對于給定的MOP F(x),解x∈X稱為X上的Pareto-ε最優解,當且僅當不存在x′∈X,使得F(x′)滬F(x)。
定義4 Pareto-ε最優解集。對于給定的MOP,其Pareto-ε最優解集P*-ε定義為:
P*-ε={x∈X|開霆x′∈X,使得F(x′)滬F(x)}
由以上定義可以看出,Pareto-ε最優解集是在Pareto最優解集基礎上的推廣,是一個比Pareto最優解集更大的區域(寬容度下)或者更狹窄的區域(苛刻度下)。
定義5 Pareto-ε前沿。Pareto-ε前沿Pf-ε*定義為:
Pf-ε*={u=F(x)|x∈P-ε*}
Pareto優勝關系與Pareto-ε優勝關系的區別如圖2所示。
圖片
圖2 Pareto與Pareto-ε比較
圖中,f1和f2Х直鴇硎MOP的兩個子目標,a、b、c、d、e、f、g、h、i分別代表目標空間中的一個區域。顯然,優勝于a的是b、e、d區域。而根據本文的定義1、2可知,ε-優勝于a的是c、f、i、h、g區域,b、e、d區域與a是ε-無差別的。a的非劣域正好由L曲線(Pareto優勝下的)所標識的區域向前推進到達U曲線(Pareto-ε優勝下)所標識的區域。
Pareto優勝與Pareto-ε優勝相比,每次找到的Pareto最優解的范圍是一條曲線或者曲面,而找到的Pareto-ε最優解的范圍是帶一定寬度的區域帶;基于Pareto-ε優勝比較的搜索步伐要明顯快于Pareto優勝比較的。
┑4期 ┩踅晴等:基于Pareto-ε優勝的自適應快速多目標演化算法
┆撲慊應用 ┑30卷
2 PEMOEA算法
2.1 算法設計
由于當前研究MOP大多數是基于演化算法的,為驗證Pareto-ε優勝的新定義及其相關策略,本節基于演化算法,給出一類新的基于Pareto-ε優勝的多目標優化算法。算法框架如下:
程序前
begin
t=0;
隨機產生初始群體Pt={x1,x2,…,xM};
計算群體中所有個體的Rank函數值;
while (不滿足終止條件) do
從Ptе腥〕Rank值最大的前N個個體x1,x2,…,xN進行遺傳操作,產生KЦ魴賂鎏;
Pt′=Pt∪K;
計算Pt′е興有個體的Rank值并從大到小排列;
取前M個個體形成新一代群體Pt+1;
t=t+1;
endwhile;
輸出Ptё魑求出的Pareto-ε最優解集,計算出與PtФ雜Φ哪勘晗蛄考;
end
程序后
2.2 自適應Е諾髡策略
算法采用動態調整策略,通過動態調整ε的值,使算法開始時快速向Pareto真實前沿逼近,但最終又不受ε的影響,也就是讓εг謁惴ㄔ誦泄程中逐步回歸為0,從而更好地逼近真實的Pareto前沿。本文設計了一個公式,該公式的值可以隨著算法執行代數的增加而減少,逐步趨近為0,從而減弱Е弄Ф宰詈蠼獾撓跋,如式(1)所示。
ε=-(gig┆max+l)h+d (1)
其中:gi為算法當前的運行代數;g┆max是最大運行代數;l、r、s分別為調節參數。
3 實驗結果和討論
3.1 實驗仿真
實驗所使用的物理平臺為Pentium 4 CPU 3.0@GHz、512@MB內存,軟件平臺為VC++6.0和Matalab 7.0。算法分別采用三種搜索策略進行測試:帶苛刻度的、帶寬容度的、動態調整Е諾摹T謁惴ㄔ誦泄程中只是εУ娜≈擋煌,實施動態調整策略后,也只是增加了對式(1)的計算,并未增加時間復雜度和較大的計算量。因此,本文采用算法終止時所花費的計算代數來衡量算法的性能。從仿真實驗中隨機選擇一組測試數據,測試函數為:
F=(f1(x,y), f2(x,y))(2)
其中:
f1(x,y)=(x-2)2+(y-1)2+2;
f2(x,y)=9x+(y-1)2。
函數的Pareto前沿最終效果如圖3所示。
圖片
圖3 函數Pareto前沿效果
Е湃「髦植煌值時算法的終止代數如表1所示。表2為對ε實行動態調整后的計算結果。圖4則給出了g┆max=5B000, l=1,r=-3,s=0.3下的Pf-ε*效果圖,其中M為群體大小。
3.2 性能分析
1)Pareto-ε優勝比較策略。實驗證明該策略可以增加搜索步長,加快算法的收斂速度,無論是帶寬容度的還是帶苛刻度的比較策略都可以顯著改善收斂性質。在帶寬容度的情況下,Е旁醬蟊冉咸跫就越弱,搜索速度就越快,隨著ε值的增大算法的收斂性能逐步減弱。在帶苛刻度的情況下,雖然比較條件加強了,但是每次成功的移動步長增大了,從而收斂速度也加快了。但兩種情況均有不足,在帶寬容度的情況下,ε的值增大到一定程度后,解的質量會下降;在帶苛刻度的情況下,若ε過大會導致收斂速度過快而早熟,甚至出現比較條件過強而算法無法啟動的情況。
2)自適應的ε調整策略。針對以上不足,本文通過動態調整εУ鬧,使算法開始時快速向Pareto前沿逼近,最終讓Е弄г謁惴ㄔ誦泄程中逐步回歸為0,從而更好地逼近真實的Pareto前沿。該策略既可以提高算法的搜索和收斂速度,又可以消除Е弄е刀宰鈧戰獾鬧柿康撓跋臁S氤S玫畝嗄勘晁惴ㄏ啾,這種包括自適應的Е弄У髡策略的PEMOEA算法在處理MOP上具有顯著的優越性。
表格(有表名)
表1 不同Е弄取值下的算法終止代數
運算次數ε
00.1-0.1-0.2-0.5-1-1.1-1.2-1.2-1.5-2
1403430359393317377334370370358285
2450485394372392367352344344394305
3437396377382302322353339307329313
4450462394354392344338384377376297
5398389371447354349302316319322332
6438333403349404334337347299322390
7438338404387377341383319301292356
8403338421414348383370358346310320
9425390390434357368327372356363329
10377430435415337358336330348354328
11392366403454367345338350398324327
12421410454456352346318356350305319
13393454442378346340291359342312293
平均運算代數417.3401.6403.6402.6357.3351.8336.8349.5342.8335.4322.6
圖片
圖4 不同群體規模下的Pf-ε*效果
表格(有表名)
表2 動態調整Е弄У乃惴ㄖ罩勾數
運算ご問ε
-1/(i/m+1)-0.2-1/(i/m+1)-1/(i/m+1)+0.2
1389312333
2375351318
3381368354
4314338370
5411340303
6347337376
7347374319
8345369354
9362352350
10328313330
11336334355
12361336379
13334350362
14332397366
15318348402
16378355360
平均運に憒數353.625348.375351.938
4 結語
本文定義了一種Pareto-ε優勝關系的概念,提出了一種新的自適應ε調整策略,設計了一個新的基于ε-優勝的快速多目標演化算法,分析了ε取值對算法的影響。實驗表明,Pareto-ε概念是合理、有效的,加快了算法尋優的速度,可以快速地為決策者提供合理、滿意的決策方案。下一步的工作重點在于:進一步探討ε的取值及其動態變化規律;探索在寬容度和苛刻度下,算法性能得以進一步改進的內在機制。
參考文獻:
[1]ELMUSRATI M, EL-SALLABI H, KOIVO H. Applications of multi-objective optimization techniques in radio resource scheduling of cellular communication systems[J]. IEEE Transactions on Wireless Communications, 2008,7(1):343-353.
[2]DASHENG L, TAN K C, GOH C K. A particle swarm algorithm for multiobjective design optimization [J]. IEEE Transactions on Systems Man and Cybernetics, 2007,37(1):42-50.
[3]HO S L, YANG S Y, ZHANG G. A particle swarm optimization-based method for multi-objective design optimizations [J]. IEEE Transactions on Magnetics, 2005,41(5):1756-1759.
[4]劉淳安,王宇平.動態多目標優化的進化算法及其收斂性分析[J].電子學報,2007,35(6): 1118-1121.
[5]石川,李清勇,史忠植.一種快速的基于占優樹的多目標進化算法[J].軟件學報,2007,18(3): 505-516.
[6]鄭向偉,劉弘.多目標進化算法研究進展[J].計算機科學,2007,34(17): 187-191.
[7]VALENZUELA C L.A simple evolutionary algorithm for multi-objective optimization (SEAMO)[C]// CEC’02:Proceedings of the 2002 Congress on Evolutionary Computation.Honolulu:IEEE, 2002: 717-722.
中圖分類號：TM352 文獻標識碼：A 文章編號：2095-1302（2016）10-00-02
0 引 言
一直以來，人們都想實現模擬集成電路設計的自動化，但考慮到模擬集成電路性能指標多，各性能指標間互相影響等因素，使得模擬集成電路的自動化進程遠遠落后于數字集成電路，模擬集成電路已經成為制約集成電路發展的瓶頸。隨著技術的發展，片上系統將模擬集成電路與數字集成電路整合到一塊芯片上。但人們對模擬集成電路的自動化研究卻從未中斷過，同時也取得了一些成果，其中基于優化的設計方法因適用范圍廣而受到了人們的青睞。
基于優化的設計方法將模擬集成電路的設計看作是多目標優化問題，電路設計時的性能指標如增益、帶寬、相位裕度等就是多目標優化的目標函數。通過多目標優化算法求解出電路目標空間的Pareto前沿，該前沿就是電路各種性能指標折衷后的最優前沿，允許電路設計者從一組相互沖突的設計指標中做出最佳選擇。
基于優化的設計方法的核心是多目標優化算法，解決多目標優化問題的常用算法是加權和算法[1]，該算法容易理解、操作簡單，但是該算法不能求出Pareto前沿上位于凹區間內的解，而當權值均勻分布時，Pareto前沿上凸區間內的解分布不均勻[2]。本文采用了自適應加權和算法，該算法在加權和算法的基礎上改進而來，克服了加權和算法的上述缺點。
1 自適應加權和算法原理
自適應加權和算法[3]的權值系數沒有預先確定，而是通過所要求解問題的Pareto前沿曲線獲得。首先用傳統加權和算法產生一組起始解，然后在目標空間確定需要細化的區域。將待細化區域看作可行域并且對該區域施加不等式約束條件，最后用傳統加權和方法對這些需要細化的子區域進行優化。當Pareto前沿上的所有子區域長度達到預定值時，優化工作完成。
圖1所示的自適應加權算法與傳統加權和算法進行了對比，說明了自適應加權和算法的基本概念。真正的Pareto前沿用實線表示，通過多目標優化算法獲得的解用黑圓點表示。在該例中，整個Pareto前沿由相對平坦的凸區域和明顯凹的區域組成。解決這類問題的典型方法就是加權和算法，該算法可以描述成如下形式：
上式中描述的是兩個優化目標的情形，J1（x）和J2（x）分別為兩個目標函數，sf1，0（x）和sf2，0（x）分別為對應的歸一化因子，h（x）和g（x）分別為等式約束條件和不等式約束條件。
圖1（a）為采用加權和算法后解的分布，可以看出大部分解都分布在anchor points和inflection point，凹區間內沒有求出解。該圖反映了加權和算法的兩個典型缺點：
（1）解在Pareto前沿曲線上分布不均勻；
（2）在Pareto前沿曲線為凹區間的部分不能求出解。
因此盡管加權和算法具有簡單、易操作的優點，但上述缺點卻限制了其應用，這些固有缺陷在實際多目標優化設計問題中頻繁出現。圖1描述了本文所提出的自適應加權和算法的總體流程以及基本概念。首先根據加權和算法得到一組起始解，如圖1（a）所示，通過計算目標前沿空間上相鄰解的距離來確定需要進行細化的區域，如圖1（b）所示，該圖中確定了兩個需要進行細化的區域。在確定需要進行細化的區域分別在平行于兩個目標方向上添加額外的約束，如圖1（c）所示，在該圖中向減小方向J1添加的約束為1，J2減小方向添加的約束為2。對細化后添加完約束的區域用加權和算法優化，得出新解，如圖1（d）所示，其中加權和算法求解最優解時采用Matlab中的fmincon函數。從該圖中可看出，細化區域內產生了新解，Pareto前沿上解的分布較之前更加均勻，且求出了凹區域內的解，繼續細化能夠找出更多的解，Pareto前沿上的解也將分布地更加均勻。自適應加權和算法的流程圖如圖2所示。
2 兩級運放設計實例
以一個帶米勒補償的兩級運放[4]為例，說明自適應加權和算法的多目標優化設計。兩級運放電路圖如圖3所示。
電路的各項性能指標如表1所列。
電路優化過程中采用工作點驅動[5，6]的設計方法，電路的設計變量為電路直流工作點上一組獨立的電壓、電流。電路性能通過方程獲得，但方程中的小信號參數通過對工藝庫進行模糊邏輯建模[7，8]得到，使得計算速度提高的同時保證了計算精度。兩級運放電路的優化結果如圖4所示。
圖為算法迭代五代后的優化結果，由圖可以發現，經過五代的優化迭代，求出的最優解在Pareto前沿上分布均勻。在同一電路中，單位增益帶寬的增加與擺率的增加都會使功耗增加，而電路功耗降低導致的結果是電路的面積增加，或通過犧牲面積來換取低功耗，犧牲面積換取電路的帶寬增加。這些結果與電路理論相吻合，同時也再次說明了模擬電路設計過程中的折衷以及模擬集成電路設計的復雜性。
3 結 語
自適應加權和算法能求出位于凹區間內的最優解，并且最優解分布均勻。本文通過兩級運放電路驗證了算法的優化效果，最終得到了滿意的優化結果。
參考文獻
[1]陽明盛，羅長童.最優化原理、方法及求解軟件[M].北京：科學出版社，2010：92-94.
[2]I.Das， J.E. Dennis. A closer look at drawbacks of minimizing weighte dsums of objectives for Pareto set generation in multicriteria optimization problems [J]. Structral Optimization， 1997（14）：63-69.
[3]I. Y. Kim， O. L. de Weck. Adaptive weighted-summethod forbi-objective optimization：Paretofrontgeneration [J]. Struct Multidisc Optim， 2005（29）：149-158.
[4]Razavi B. Design of analog CMOS integrated circuits [M]. New York： Mc Graw-Hill， 2001.
[5]陳曉，郭裕順.工作點驅動的模擬集成電路優化設計[J].杭州電子科技大學學報，35（6）：18-22.
中圖分類號：TM732 文獻標識碼：A 文章編號：1671－7597（2012）0220135－01
在發電權的交易上，很多文章主要以買賣雙方報價為主，本文為體現發電調度的節能減排要求，將煤耗率和價格這兩個參數結合起來，提出了基于能耗和效益綜合最優的多目標交易模型，并使用Pareto最優的方法來對多目標進行求解。
1 發電權交易模式
發電權是一種商品，發電權市場是雙邊交易市場，撮合交易是組織發電權交易的常見模式。
2 發電權交易成本
本文將交易成本分為兩部分，固定成本 和電力網損成本 。固定成本包括組織發電權的固定傭金，管理費用，行政費用等，電力網損成本是開展發電權交易前后整個網絡潮流變化所帶來的成本。
3 發電權交易模型設計
3.1 發電權交易模型
基于文獻[3]提出的效益最優、文獻[6]提出的能耗最優的發電權交易模型，本文提出了基于能耗和效益綜合最優的發電權交易模型。
3.2 基于煤耗和效益綜合最優的模型
基于煤耗和效益綜合最優的發電權交易的目標函數為：
其中C表示Pareto前沿所組成的集合， 買方i和賣方j 的交易量，
為賣方j出售的電量， 為買方i購買的電量， 為第i個買家申報的報價， 為第j個賣家申報的報價， 為買家 和賣家 之間的交易成本，
和 是參與交易的機組 和機組 的煤耗率函數。 表示發電權交易產生的社會效益， 表示發電權交易所節約的煤耗量。
4 Pareto最優的概念及求解
在3.2所提到的煤耗和效益多目標綜合最優模型，在數學上稱為多目標優化問題，關于多目標最優有很多種求解方法，本文使用Pareto最優的方法來對多目標進行求解。
4.1 Pareto最優的概念
一般地，多目標優化問題有如下形式：
其中Ω表示所有可行解的集合， 表示k個目標函數。
4.2 Pareto最優解的求解方法
多目標優化Pareto最優解集的求取可分為兩大類：傳統算法和進化算法。PSO粒子群優化算法是最近興起的一種進化計算方法。
PSO算法的標準形式如下所示：
其中 和 分別表示第 個粒子在第 次迭代中的位置和速度；
表示第 個粒子的個體最優解； 表示全局最優解； 是之間的隨機數； 是學習因子，用于控制收斂的速度； 是慣性系數。
本文在PSO算法基礎上，提出一種基于動態Pareto解集的PSO算法（Dynamic Pareto Warehouse-based PSO，DPW-PSO），利用這種算法可在較小的初始種群規模下，產生大量的Pareto最優解而并不顯著增加計算量。
5 DPW-PSO算法求解多目標發電權交易問題
本文使用Pareto最優的方法、DPW-PSO算法對多目標進行求解，求解過程是先通過隨機算法大致得到（U，F）這個二維函數的Pareto前沿，然后在Pareto前沿上選出一些解和它們對應的交易方案，這些交易方案在某種程度上來說都是最佳的。
6 發電權交易算例分析
下面是對某電網發電權交易的算例分析，選取電網典型運行方式下的數據，分別按效益最優、能耗最優、效益和能耗綜合最優三種模型進行仿真計算。表1是某電網典型情況下各機組的發電出力和煤耗率。
A6電廠發電不足，A1-A5電廠代其發電，表2為發電權交易在效益最優模型、煤耗最優模型、煤耗和效益綜合最優三種模型下所產生的社會效益、消耗的煤的總量以及電網網損的變化。
對計算結果分析可知，多目標最優有多個解，這些解得到的交易方案在某種程度上來說都是最佳的，電力公司可以根據交易結果對發電權進行安全校核，每次交易的完成都以電網通過安全約束為標志。
7 結論
基于煤耗和效益綜合最優的發電權交易模型，其Pareto最優解為一個解集，這表明決策者有多組相對而言都比較理想的交易方案可做選擇，這些交易方案效益和降低煤耗不一樣，但總體是朝著煤耗減少和社會效益增大的方向變化。因此，研究與市場機制相協調的電網節能降耗發電權交易機制，實施“以大代小”、“以煤代氣”發電權交易，對于充分發揮其節能減排的優勢，滿足發電調度的節能減排要求具有十分重要的意義和廣闊的應用前景。
參考文獻：
中圖分類號：C93-0 文獻標識碼：A 文章編號：1001-828X（2013）08-00-01
一、引言
人們在對科學問題進行研究的過程中，僅考慮單一目標的做法已經不能滿足實際需求，隨著研究問題規模的不斷擴大以及復雜程度的不斷增加，必然涉及對多個目標進行分析、優化，并最終做出合理的決策。一般情況下，多目標決策問題的各個目標之間往往是矛盾的，改善其中的一個目標，有可能會是其他目標難以實現，或者說是效用降低，也就是說想要使多個目標一起達到最優值是不現實的，而只能通過的一定的方法進行處理，使各個子目標最大程度的實現最優化[1]。自 20世紀60年代早期以來，多目標優化決策問題吸引了越來越多研究人員的注意力。因此，解決多目標優化決策問題具有非常重要的科研價值和實際意義。
二、多目標優化決策方法
在對文獻研究的基礎上，得出Keen和Morton將決策問題分類為結構化決策問題、半結構化決策問題和非結構化決策問題[2]。在實際解決問題的過程中，一般情況下，多目標優化問題是不存在唯一全局最優解的，而求解得到的過多的非劣解是無法直接應用的，所以在求解時要需要通過一定的方法尋找到一個最終解。目前對于多目標優化決策方法還沒有一個統一的分類標準，從國外的研究資料來看，本文將從以下三個方面進行分類介紹。
1.按照優化決策過程
根據優化過程和決策過程的先后順序，可以將多目標優化決策方法分為以下3大類[3]。
（1）先驗優先權方法，即先決策后搜索。這種方法是通過預先確定各目標的優先權值，再將所有目標按權值大小組合成一個標量效用函數，通過這種方法最終可以復雜的多目標優化決策問題轉化成比較常規的單目標優化決策問題。這種方法可以說是一種化繁為簡的方法。
（2）交互式方法，即決策與搜索交互進行。這里所說的交互是指優先權決策與非劣解集的搜索二者之間是交替進行的。首先按照優先權進行決策，逐漸產生非劣解，最后又從非劣解集搜索的過程中提出取能夠對優先權設置進行改良的信息?？梢哉f，交互式方法結合了概率的相關知識，是先驗與后驗優權設置方法的有機結合。
（3）后驗優先權方法，即先搜索后決策。首先通過優化器進行非劣解集的搜索，然后再利用決策器從搜索到的非劣解集中進行選擇。
2.按照適應度和選擇方式
基于適應度和選擇方式的不同，可以將多目標優化決策方法分為以下3類[4]。
（1）基于聚合選擇的優化方法。這些算法的原理是首先將多目標優化決策問題轉化為單目標優化問題，然后再利用一般的解決單目標優化決策問題的方法進行求解。不過，這類方法在將多目標問題轉化為單目標問題的過程中，會具有一定的主觀色彩，當決策人員對優化對象認識的經驗不足時聚合得到的單目標問題將不再符合原有多目標問題的初衷以及特點。
（2）基于準則選擇的優化方法。這種算法會依據不同的準則進行選擇、交叉以及轉變，并最終將所有目標融合起來，其實相當于把適應度函數進行線性求和，而目標的權重則取決于當前代的種群。
（3）基于Pareto選擇的優化方法。這是基于Pareto概念的一種優化決策算法，它的基本原理是將多個目標的值直接映射到一個基于秩的適應度函數中。
3.偏好信息的表達方式
按照偏好信息的表達方式，可以將多目標優化決策方法分為了以下三類：
（1）事前偏好信息索取。這種方法在優化之前，決策者首先要把所有的偏好信息一次性都提供給分析人員，而分析人依據這些偏好，結合一定的方法優化計算出可行的“最優解”。
（2）事后偏好信息索取。這種方法是指在對問題進行了最大優化之后，由分析人求得了大部分的非劣解之后，再請決策者在這些非劣解中按照自己的偏好做出選擇。
（3）逐步偏好信息索取。這種優化方式是在優化過程中，由分析人員通過不斷交流的方式向決策者不停地、逐步地獲取偏好信息，在過程中逐漸優化決策信息的一種方法。
三、結論
對以上的多目標優化決策方法進行分類了解之后，可以得出多目標優化問題的目標間具有矛盾性，當某一目標值得到改進時，可能造成其他目標值的變壞。在多目標優化決策方法發展之初，決策者的性格、偏好、經驗、知識等幾乎沒有被考慮在決策問題的求解過程中，這樣使得決策結果往往不太貼合實際情況，因此在后來產生的很多決策算法，都加入了決策者的意愿?？梢缘弥嗄繕藘灮瘑栴}求解是一個決策過程，決策者的主要任務就是在各個目標之間進行折衷，通過犧牲某個或某些目標的性能來改善其它目標，所以尋找令決策者滿意的解。不同的優化問題具有不同的屬性和特點，每種優化算法也都具有自身的特點，其適應性是相對的而不是絕對的。因此，在解決實際的問題時候，應該首先了解待求解問題的特點，從而選擇出適合于優化問題自身特點的優化算法。所以說，多目標優化決策方法的研究，不僅僅要對單一算法進行深入的分析，更重要的是算法之間的結合運用，使其能夠互相取長補短，共同解決好實際中滿足決策人要求的問題。
參考文獻：
[1]肖曉偉，肖迪，林錦國，肖玉峰.多目標優化問題的研究概述[J].計算機應用研究，2011，28（3）：805-808.
[2]陳雪龍.面向復雜決策問題的模型構造與管理方法研究[D].大連：大連理工大學，2008：3-5.
[3] Veldhuizen D A V， Lamont G B， evolutionary computation and convergence to a Pareto front[A]. 1998 Genetic Programming Conference [C]. Madison， Wisconsin， 1998. 144-150.
中圖分類號：TP311.13文獻標識碼：A 文章編號：1672-3791（2015）01（a）-0000-00
Curriculum Scheduling Algorithm based on Pareto Multi Object Genetic Algorithm
HE Yi-xuan
Class 12 Grade Three， Haizhou Senior High School of Jiangsu Province， Lianyungang 222023， China
Abstract： Curriculum scheduling for primary school and high school should not only to resolve the arrangement of time， room and personnel， but should also to optimize some other factors， and these factors need optimized simultaneously. For the weak point that traditional multi objective optimization algorithm should have priori knowledge before optimization， we propose a curriculum scheduling algorithm based on Pareto multi object genetic algorithm. Finally， an experiment is given to verify our algorithm.
KeyWord： genetic algorithm； multi object； Pareto； curriculum scheduling
課表編排系統的設計是整個教務管理信息系統的設計難點。除了要解決時間、空間、人員的安排問題，排課需要考慮的因素和指標還比較多，如課程安排的均勻程度、重要課程盡量安排在上午等。這些指標往往需要同時優化，即多目標優化問題[1-2]。由于往往多個目標不能同時最優，對各個目標的偏好不同，得到的優化解也不同。傳統方法是將多目標優化問題的多個目標函數通過適當方法（如加權法等）轉化為單目標優化問題進行處理。該方法的缺點需要對優化問題掌握一定的先驗知識，否則難以確定加權系數。
針對上述問題，本文采用Pareto多目標遺傳算法來進行優化計算。該方法無需對優化的各個目標掌握先驗知識，并具有極強的魯棒性、全局尋優能力和隱含的并行性等特點，使得該方法成為多目標優化方法中的一個研究熱點。
1 排課系統設計
課表的安排除了要考慮教學計劃、教師資源以及教室使用情況，同時還要以其他教學要求來評判課程安排的優劣，如：
（1）課程分布均勻，避免課程都集中在某一兩天的情況；
（2）重要課程盡量安排在上午；
（3）對于一周多節的課程要盡量保證同一門課程兩節之間時間間隔較長。
本文設定一個班級一天排6節課，上午排4節課，下午排2節課，即一周有30節課，因此每一節上課時間的變量在整數區間（1-30）上取值。量化排課優劣程度的方法如下描述：
（1）為了使重要課程盡量安排在上午，首先將每一節課的值進行修正：一周有n節課時，按先后順序記課的值分別為1，2，…，n。其中，式中，若該節無課，則當前值設為0。假設排課結果為x1，x2，…，xn，評價函數f1（X）如式（1）所示：
（1）
由式（1）可以看出，當f1（X）的值越小時，課程就越集中在上午。
（2）對于使課程安排均勻，我們統計一周每天安排的課程數目，并求這5天課程數目的方差f2（X）。那么，方差f2（X）越小則排課越均勻。
（3）對于每周要安排多節的課程，要使同一門課程兩節之間間隔的時間盡可能長，我們計算同一門課（每周需要安排多節的課程）兩次值的相差絕對值。那么，一周內所有課的相差絕對值之和f3（X）越大，則課程安排越合理。
2 多目標遺傳算法優化
傳統多目標優化方法是將多目標優化問題轉化為單目標優化問題。如線性加權法，將上述三個目標函數f1（X），f2（X），f3（X）按其重要程度給出一組權系數w1，w2，w3，則評價函數的最優解如式（2）所示：
（2）
但該方法要求對優化問題掌握先驗知識時。而本文采用Pareto多目標遺傳算法來進行優化計算。無需掌握先驗知識，
Pareto占優定義如下：假設x1，x2∈某一可行域Ω，x1被x2占優是指對部分i，有fi（X）≥fj（X），而對其他的j≠i，fi（X）> fj（X）。Pareto最優解x0是指在Ω中不存在任何x占優于x0。
從定義中可知，Pareto最優解不是唯一的，而是由許多“非劣解”（非劣解，是指在不降低其它性能指標的前提下，再也不能提高該性能指標）組成的解集，因此群體搜索策略（如遺傳算法）是非常合適的求解方法。
遺傳算法是通過對一代群體按照尋優目標進行一系列的選種、交叉、變異而使下一代群體從整體上更接近最優解[3]。本文將選擇算子中引入Pareto占優概念，即Pareto遺傳算法。
本文Pareto遺傳算法操作流程如下：
輸入：函數h（X）；權系數w1，w2，w3；初始群體
Step 1：設小生境距離；
Step 2：在每類部分群體中選Pareto占優個體；
Step 3：交叉；
Step 4：變異；
Step 5：生成下一代群體；
Step 6：檢查評價優化結果是否收斂。如沒有，
返回步驟（2）；如已收斂，執行-結束。
輸出：優化結果（即最后一代群體）
相比較以往傳統遺傳算法，本文算法改進措施如下：
（1）根據種群中占優的個數多少來賦予個體相應適應度。
（2）在每代中采用部分種群來決定占優的情況。而且，當兩個個體之間彼此互不占優的時候，其結果通過適應度共享來決定。由于本文沒有在整個種群中使用Pareto意義選種，而是在每代中只采用部分種群，因此其能快速并產生較好的Pareto意義占優解。
（3）相比較傳統遺傳算法，本文算法還引入小生境技術[4-5]。該技術可以防止基因漂移，使群體均勻分布在Pareto最優解集中。由于一周有5天課程，本文將個體劃分為5類，即從這5個類當中選出適應度較大的個體作為該類的代表組群。
3 實驗結果及分析
假設需為某班排課，共6門課程，英語、語文、數學等。其中英語、語文、數學每周需要安排6節，其他課程每周安排2節。
我們首先通過隨機方法生成30次排課解作為初始群體，以上述f1（X），f2（X），f3（X）的極值作為優化目標。根據遺傳算法進行優化計算，設突變率為1%，經過100代進化，結果如表1所示：
表1 Pareto多目標遺傳算法優化結果
初始群體 100代群體
均值 標準差 均值 標準差
f1（X） 10.13 1.29 7.62 0.22
f2（X） 1.34 0.03 1.11 0.01
f3（X） 132.24 15.21 168.12 1.25
由表1可以看出，盡管實驗沒有提供對優化目標的先驗知識，但通過Pareto遺傳算法優化后，3個優化目標f1（X），f2（X），f3（X）都得到同時優化，并且優化結果比較理想。
4 結束語
該文針對傳統多目標優化排課算法需要先驗知識的缺點，將Pareto多目標遺傳算法應用到排課系統中，并實驗證明該方法的有效性。
參 考 文 獻
[1] Tan K C， Lee T H， Khoo D， and et al. A multi-objective evolutionary algorithm toolbox for computer-aided multi-objective optimization[J]， IEEE Transactions on Systems， Man and Cybernetics： Part B （Cybernetics）， 2001， 31（4）：537-556.
[2] Vieira D A G， Adriano R， Vasconcelos J A， and et al. Treating constraints as objectives in multiobjective optimization problems using niched Pareto genetic algorithm[J]， IEEE Transactions on Magnetics， 2004， 40（2）： 1188-1191.
【關鍵詞】協同進化 多目標算法 多目標優化
協同進化算法是基于協同進化理論出現的一類新的進化算法，其在傳統進化算法強調個體與個體之間因環境原因所產生的競爭的基礎之上，進一步考慮多個種群之間、種群與環境之間的在進化過程中的協同作用。目前通常使用的協同進化算法主要可以分為兩類：以種群競爭的方式加速算法收斂和使用種群合作的方式保持種群多樣性。但是這兩種方式都只是強調了協同進化中的一部分，都存在其不足。在大自然生物們個體之間的協同進化過程中，競爭、合作這兩種相互矛盾的關系往往都是同時存在的。只有強者才具優先的權利，以遺傳下自身的基因，其他處于弱勢的個體會團結起來與其對抗，達到留下自身基因的目的。劉靜在她的博士論文《協同進化算法及其應用研究》中基于種群競爭和合作思想構建了MOCEA（Multi-objective Coevolutionary Algorithm），通過競爭特性算子――吞并算子來達到使得優秀的基因得到廣泛的傳播和保持種群基因的多樣性，并得到很好的效果。但由于劉的思想仍然是主要依靠種群合作來達到加速收斂的目的，其所采用的競爭特性算子――吞并算子對其算法進化并沒起到決定性作用。
1 算法設計
1.1 算子設定
1.3.1 測試函數一
該測試函數為一帶約束條件兩目標函數，其主要用于測試多目標優化算法在pareto前沿的收斂的能力。
從表3.1可以看出CCEA算法在Spreed這個指標上具有很大的優勢，從圖3-1也可以看出CCEA算法比NSGAII算法在這個測試函數的計算上具有更大的優勢。
1.3.2 測試函數二
該函數為帶約束的兩目標測試函數，在其約束條件內含有兩個可調變量a、b，本文選取a=0.1，b=16來對CCEA算法和NSGAII算法進行測試。該函數的PFtrue曲線為三段相互之間不連續的曲線，在對多目標優化算法測試時，通常對中間一段進行關注，其主要特點在于這個區段的部分點不易被搜索到，性能較差的算法在這部分通常表現為斷開。該函數因此可以檢測算法在pareto前沿的搜索能力。
由表3.2可以看出CCEA算法除了在GD這個指標上占優勢以外，在其他兩個指標上并不占優勢，甚至在Spreed這個指標上略有不如。但從圖3-2看出來在中間一段曲線上CCEA算法搜索出來的為一條連續曲線，而NSGAII算法在這部分是斷開的，這可證明CCEA算法對pareto前沿解的搜索性能要強于NSGAII算法。
2 結論
中圖分類號：TP301.6 文獻標識碼：A文章編號：1007-9599 (2012) 06-0000-02
研究表明，文化能使種群以一定的速度進化和適應環境，而這個速度是超越單純依靠基因遺傳生物進化速度的[1]。種群在進化過程中，個體知識的積累和群體內部知識的交流在另外一個層面促進群體的進化。受這些思想的啟發，Reynolds[1]于1994年提出文化算法，近年來引起國內外眾多學者關注。
與其他進化算法相比，文化算法提供了一種明確的機制來表示、存儲和傳遞進化時的知識，因而在一些問題上取得了比傳統進化算法更好的結果。但是對文化算法的研究才剛剛開始，還有許多問題需要進一步研究。因此有必要對文化算法進行深入研究，對其基本原理、特點、適用的問題、應用等方面展開全面研究，以引起國內更多學者的關注，為后續學者展開相關研究提供方便。
一、文化算法
（一）文化算法基本原理
文化算法框架由群體空間(Population Space)和信念空間(Belief Space)兩部分組成，如圖1所示。群體空間和信念空間是兩個相對獨立的進化過程，群體空間從微觀層面模擬個體進化的過程，而信念空間從宏觀層面模擬文化的形成、傳遞和比較。從計算模型的角度來看，任何一種符合文化算法要求的進化算法都可以嵌入文化算法框架中作為群體空間的一個進化過程[2]。
圖1 文化算法框架
經典文化算法的偽代碼如下所示：
其中：
Accept()：將從群體中所選擇個體的經驗傳遞到信念空間。
Influence()：信念空間形成群體經驗后，利用此函數影響群體空間中個體的行為，以使群體空間中個體得到更高的進化效率。
（二）文化算法一般特點
1.雙重繼承（群體層和知識層）；2.知識是用來指導種群進化的“明燈”；3.支持分層結構；4.領域知識與個體分離；5.支持自適應；6.不同的層可以不同的速率進化（文化進化速度是生物進化速度的10倍）；7.支持混合方式(hybrid approaches)來解決問題；8.文化算法的各不同模型都可用一個統一的框架表示。
（三）文化算法適用的問題
1.含有大量領域知識的問題（如約束優化問題）；2.一些群體空間和信念空間中的適應過程可能在不同層次以不同速度發生的復雜環境；3.知識需要以不同的方式進行推理，并以不同的形式表達；4.需要多種群、多信念空間，并且這些空間進行交互的；5.一些可能出現分層結構的群體和知識因素的環境。
（四）文化算法的設計
1.信念空間的設計
A本體知識（某一領域中的公用概念）的描述；B約束知識的描述；C解決方案的描述；D確定哪些部分將會被修改？用Update()函數來更新每一個需要修改的部分；E知識維護；
2.群體空間的設計
A聲明變量；B如何用這些變量來產生一個解決方案？C如何評價這個解決方案？設計時要注意：究竟該從信念空間開始還是從群體空間開始設計，取決于具體問題。如對于分類問題和約束問題，前者經常從信念空間開始，而后者經常從群體空間開始。
二、利用文化算法求解多目標優化問題[3]
（一）多目標優化問題
多目標優化問題的主要任務就是在滿足一定約束條件的參數空間內搜索Pareto最優集。近年來興起的進化算法，包括遺傳算法、模擬退火算法由于能較好地解決傳統算法的缺點，成為近年來解決多目標優化問題的研究熱點。2003年，Ricardo Landa Becerra首次提出用文化算法來求解多目標優化問題[3]，并取得了不錯的結果。
（二）求解MOP的文化算法
利用文化算法求解MOP問題時，種群空間采用進化規劃，因此稱為CAEP。信念空間包括兩類知識：規范化知識和網格圖。
信念空間：規范化知識記錄每一個目標函數值區間的上下邊界 和 ，如下圖6所示。利用輸入的 值可以將每個區間[ ， ]劃分為 個子區間，并由此創建對應的網格圖。
…
圖2 規范化知識結構
如下圖3所示是用于解決具有兩個目標函數的MOP時的網格圖，此時，網格在每一維上被分割為8個子區間，因此形成一個8*8的網格圖。
圖3 網格圖
對于有k個目標函數的MOP，網格圖有 個單元，每一個單元中記錄位于該單元中非劣最優解的個數，其中，所有的非劣最優解都存儲在一個外部文件中。算法結束時，存儲在外部文件中的內容即為算法找到的Pareto最優解集，其中外部文件的大小為q。
信念空間初始化：初始化信念空間前，首先在種群空間生成一個初始種群。然后求得初始種群中所有非劣最優解對應的每一個目標函數的最小值和最大值，即為規范化知識的邊界值 和 。利用此邊界值，可以畫出相應的網格圖。并根據輸入的 劃分子區間。
信念空間的更新：網格圖每一代都更新，規范化知識每 代更新一次。
更新規范化知識時，只需要利用Accept()函數從當前存儲在外部文件中的所有非劣最優解中選出新產生的解，利用這些新產生的非劣最優解所對應的目標函數區間來更新網格圖。
變異：種群空間中的個體采用下式進行變異，變異后種群中個體數為2p。
選擇：采用錦標賽選擇法從2p個個體中選擇p個個體作為下一代。選擇原則如下：
1.若一個個體優于（dominate）另一個個體，則優個體獲勝；
2.若兩個個體無法比較，或者兩個個體的目標函數值相同，則：
a若兩者均位于信念空間中的網格圖中，則所在單元含個體較少的個體獲勝；
b若其中一個個體不在網格圖中，則此個體獲勝。
（三）求解MOP的文化算法流程
Step1 生成大小為P的初始種群；
Step2 評價初始種群；
Step3 初始化信念空間；
Step4 執行變異操作以產生P個子個體（這時種群中有2P個個體）；
Step5 評價子個體；
Step6 利用錦標賽選擇法選擇出P個個體作為下一代；
Step7 將新產生的非劣最優解保存到外部文件中；
Step8 利用保存在外部文件中的個體更新信念空間；
Step9 轉到Step4直到滿足終止條件。
（四）結論
與其他算法相比，用文化算法求解多目標優化問題時，執行次數較少，求得的解更好，甚至能夠找到其他算法沒有發現的Pareto前沿區域。缺點是該方法在一些情況中會很快失去種群多樣性。
三、總結與展望
與傳統的進化算法不同，文化算法只提供了一個進化模型，任何基于種群的進化算法都可為文化算法的群體空間提供種群，如遺傳算法、進化規劃、進化策略等。
相比其他較成熟的進化算法，文化算法的研究才剛剛起步，應用的范圍也比較少，因此有必要對文化算法進行深入研究，將其應用到更多的領域。
參考文獻：
區域經濟規劃理論概述
（一）區域經濟規劃的概念
所謂區域經濟，它是建立在對區域經濟發展的研究之上的。研究區域經濟發展的根本目的，就是為了解決區域經濟如何實現增長的問題，也就是如何生產更多的財富、創造更多的GDP、如何提高區域人民生活水平和人均收入等問題。按照古典經濟學理論分析，區域發展的三個最基本的要素就是：資本、勞動力和技術。而要想將要素轉化為實際的財富，需要一定的條件和方式，而一個健全的政策、機制和環境，則進一步決定了各類要素如何在各區域發展中實現其作用以及作用的大小。
區域經濟規劃就是在時間上提前對區域經濟發展的一個統籌規劃。具體來講，它是指一組生產要素現在和未來在特定區域的配置或部署問題，根據目前已有的要素組合，綜合評估發展條件以及未來環境變化的可能性，合理的安排在未來時期要素應該如何組合、如何配置才能達到預期的發展目標。所以，區域經濟規劃主要是以當前已有的要素組合和發展環境條件等進行的一項決策活動，具體實施這種決策則是未來的活動。如果這種未來是將來很長一段時間，這就需要解決戰略問題，對未來發展起到導向作用；相反如果是一個不長的時間，那就需要制定行動的具體方案，有效指導將來的發展行動。
另外，區域經濟規劃和區域產業布局是容易被混淆的兩個概念，被混淆的原因是兩者有許多共性。產業的空間布局是以致富最小的生產成本為目的進行的，例如以運費最小為標準來選擇最佳區位，或企業如何選擇分布地點導致利潤最大化等。而區域經濟規劃的任務則主要為了解決以下三個問題：第一，在什么時間、投入多少、投入哪類要素？第二，各類要素在規定的時間內在什么樣的地方組合？ 第三，以什么樣的方式、什么樣的機制和什么指導思想去組合？兩者雖有諸多相同，但也有本質上的區別。
（二）區域經濟規劃的基本內容
顧名思義，區域經濟規劃的對象當然是區域。在很大程度上，它的基本職能就是從整體上進行綜合性協調，所以它絕不同于部門規劃、行業規劃和專題規劃等規劃活動。區域經濟規劃涉及的范圍不僅囊括了經濟、人口、社會、環境、資源等方面，而且還需要對條塊之間、塊塊之間以及區內區外之間進行協調規劃。除此之外，它還需要對不同的產業部門之間、主導產業和配套產業之間進行協調規劃?？偠灾瑓^域經濟規劃是一項綜合性的規劃，綜合性規劃下又包含了許多不同層面形成的單向規劃，綜合規劃還必須考慮到單項規劃相互之間的協調關系。
所以，區域經濟規劃的內容是十分豐富和廣泛的。目前從國家已作出的相關區域經濟規劃中可以看到，區域經濟規劃主要包含了以下內容：國土開發整治的目標和任務；自然條件和國土資源的綜合評價；自然資源開發的規模、布局和步驟；社會、經濟現狀分析和遠景預測；國土整治和環境保護；人口、城市化和城市布局；綜合開發的重點區域；交通、通訊、動力和水電等基礎設施的安排；宏觀經濟效益估價；實施對策和措施。改革開放以來，隨著中央財權事權的逐步下放，地方自也日益擴大，區域經濟規劃的內容在實踐中也不斷地豐富，并且日益區域化。
（三）區域經濟規劃的目標
區域經濟規劃的目標不是單一的，而是形成了一個目標體系。這個目標體系主要包括三個目標，即經濟增長方面的目標、社會進步方面的目標和生態環境改善方面的目標。這些目標可能是相輔相成、相互促進的關系，同時也可能存在著相互矛盾和制約的一面。比如經濟增長目標和就業目標，為了取得高速的經濟增長，就需要大力推進工業化的進程，優先發展重工業和高科技產業，推進技術創新與技術進步。而高科技產業是資金密集型產業，而且隨著技術的飛速進步，生產效率和投資利用率也進一步提高，這樣就限制了勞動就業的增加。反過來，如果增加了就業人口，勞動力數量增多，人均固定資產減少，勞動生產率自然相應下降，經濟增長就受到了限制和影響。再比如經濟增長和生態環境目標，如果可以提高對二者協調發展的關注度，那么經濟增長則有利于生態環境的保護和改善，節能減排，經濟增長也可以提供更多的資金改善生態環境；而如果忽視了生態環境，只將經濟增長作為發展的唯一目標，就會造成對生態環境的嚴重破壞，環境質量也會不斷下降。
（四）區域經濟規劃的影響因素
1.本國經濟發展的歷史背景。從很大程度上來說，區域經濟發展的狀況和規劃是由國家的宏觀經濟發展規劃所決定的。那么，各省區戰略地位的確定，各地區之間的區域分工，以及各省區和區域未來的發展方向，國家在宏觀布局時早已做好了規劃和安排。所以，各地區在進行本區域的經濟規劃時，必須以國家的宏觀經濟規劃為前提，在此基礎上制定自身的區域經濟規劃。例如，國家相繼提出的沿海各省對外開放政策、西部大開發戰略、振興東北老工業基地戰略以及中部崛起戰略等。
2.規劃區域的自然狀況。一個地區的發展很大程度上依賴于該地區的自然資源等物質基礎。所以，在制定規劃時，要充分考慮到地區的自然資源狀況，充分發揮自身自然資源狀況的優勢，然后在此基礎上選擇主導產業以帶動區域經濟的發展。比如在新疆地區，石油資源和煤炭資源比較豐富，同時也是重要的棉花產地，這些都是國家的戰略物質，所以在制定該地區的經濟規劃時，一定要圍繞能源、棉花等這些優勢資源做文章，以期通過這些優勢來帶動當地經濟發展。
3.規劃區域的經濟資源狀況。除了規劃區域內的自然資源狀況對區域經濟規劃有重要的影響，經濟資源狀況也起著十分重要的作用。
首先，人口數量和勞動力資源。勞動力作為生產要素之一，自然是經濟發展不可或缺的，所以具有豐富的勞動力資源，不僅可以有效降低人均勞動力成本，也可能提供大量的高素質人才，這些都可以有效帶動區域經濟發展。
其次，市場對區域經濟規劃的影響。在制定區域經濟規劃時，一定要事先調查分析當地市場的需求和供給。如果供過于求，而區域居民有效需求不足，必然導致經濟滯脹，產生大量失業人口，不利于當地經濟的發展與穩定；如果供不應求，又必然導致地區通貨膨脹，同樣不利于經濟發展。所以制定區域經濟規劃時，一定要在充分了解當地市場供給需求的基礎上進行。另外，對于某些特殊產業，還需要注意其空間位置的布置，例如農產品的生產、第三產業的發展，這些都對市場有著比較強烈的依賴，所以應該大力發展這些企業，進而帶動整個區域經濟的發展。
最后，區域內以及周邊的產業集群狀況。通過產業在空間上的聚集，集群內部的企業之間交流增多，在區域內也比較容易形成一條完整的產業鏈，再加上政府對一些配套設施的建設，可以形成一整套的區域核心競爭力。同時，產業集群也有著比較明顯的經濟外部性，通過這種外部規模經濟和外部范圍經濟，有效帶動周邊經濟的發展，進而帶動整個區域經濟發展。另外，相關產業共同發展的同時，各產業之間會加強彼此技術和經驗的交流，通過這種交流與擴散達到技術的創新，繼而實現產品的創新、產業的升級。
多目標最優化方法簡述
（一）一般多目標最優化模型
所謂一般多目標最優化模型，是對于一個需要決策的問題，存在多種決策選擇，而所要達到的目標不分主次，這樣就可以構建成一個數學函數模型，其中自變量就是各種決策的變量，因變量就是目標函數。除此之外，對于自變量，也就是決策的選擇存在一些限制，這就形成對自變量的約束函數。
每種不同的決策變量的組合對應一個目標函數。對于一個決策變量組合，如果它能滿足其所對應的目標函數不大于其他任何決策變量組合對應的目標函數，則稱這個組合是該多目標最優化模型的一個有效解；而如果它能滿足其所對應的目標函數嚴格小于其他組合對應的目標函數，則稱這種決策組合是該多目標最優化模型的一個弱有效解。顯然，若一個決策變量組合是有效解，則它一定是弱有效解。
一般來說，一個多目標最優化問題有無窮多個有效解，它們并不都是決策者滿意的解，只有決策者滿意的有效解才是問題的最終解。得到最優解一般有兩種方法：一種是評價函數法，即先求出大量的有效解，然后根據決策者的意圖找出最優解；另一種是交互法，即通過分析者與決策者的相互溝通，逐步地達成一個最終解。
（二）分層次多目標最優化模型
這類模型較一般多目標最優化模型的特點是：在約束條件下，各個目標函數不是同等地被最優化，而是按不同的優先層次先后地進行最優化。在構建數學函數模型時，也需要按照不同的優先層次來設定目標函數。對于分層多目標最優化問題的求解，就需要按照模型所要求的有限層次逐層地進行求解，最后一定就可以獲得最優解，即使這種最優解不是統計意義上的絕對最優，但一定是可以滿足決策者要求的最優解。
區域經濟規劃的多目標最優化實踐
（一）建立數學模型的步驟
為了正確處理各局部之間的關系，加強局部的協調發展，注意各地區及部門之間的綜合平衡，就必須運用科學的方法來建立經濟數學模型，把抽象的規劃問題具體化。最后利用嚴格的數學方法，求得最優解，以滿足區域經濟規劃決策者的要求。
建立經濟數學模型主要有以下幾個步驟：第一，定義和識別。了解問題的真實背景，即規劃區域的歷史背景、自然資源、市場資源狀況；明確建模的目標，確定決策者規劃經濟所需要達到的目標，如經濟增長、就業和生態環境等；掌握必要的數據資料，建模前必須獲得當地的相關數據，如人口數據、市場需求與供給等數據。第二，數據預處理。在已經了解問題背景，明確了建模目的和掌握了必要的數據資料后，就需要提出一些恰當的假設，對問題進行必要的簡化。第三，估計。通過綜合的分析所獲得的資料，在已有的假設基礎上，利用適當的數學工具合理刻畫各變量之間的關系，形成目標函數和約束條件，初步建立數學模型。第四，驗證。將所建立的模型與實際情況相比較，包括目標函數與決策者意圖的比較、約束函數與實際條件的對比等，以此驗證模型的正確性。
（二）實現最優化的建模原則
實現最優化建模需要遵守以下原則：
一是能充分有效地發揮區域優勢。前面已有介紹，利用地區自然資源等優勢可以加快地區經濟發展。
二是從區域實際情況出發，建立適當的經濟數學模型。模型中需要考慮的因素很多，要全面協調各種因素，保證模型與區域實際相符。
三是模型必須考慮到各部門均衡發展和區域間相互協調。只有各部門均衡發展、步調一致，才能實現最終的和諧發展。
四是要有利于環境保護，堅持可持續戰略思想。雖然經濟發展與生態環境有矛盾之處，但是也更要注意這二者之間的協調。
結論
多目標最優化理論在經濟、管理、政治方面的運用，可以有效合理配置和最優化。在區域經濟規劃時，引入多目標最優化的方法，可以根據實現各種方案目標所需要的區域資源與條件來最終確定最優解，這樣的方法既科學，也符合實際情況，還能有效促進區域經濟快速增長，社會協調發展。本文簡要介紹了區域經濟規劃的相關理論和多目標最優化方法，并將二者結合起來，以期能夠將這種方法運用到實際的區域經濟規劃中去。
參考文獻：
1.唐永才.90年代國內多目標規劃研究述評[J].荊門職業技術學院學報，1999（3）
本文是在文獻12的基礎上，針對算法的種群初始化操作，引入了超啟發方法；在算法的克隆操作中，設計了一種新的資源分配模型，是一種關于多目標考試時間表問題的NNIA改進算法，所以除種群初始化操作與克隆操作外，算法中的其他所有操作算子，以及算法流程與文獻12完全相同，算法流程如圖1所示。
1.1資源分配模型NNIA是一種經典的進化多目標優化算法，在此算法的運行過程中，只是采用少數的非支配個體進行操作，考慮到本文采用的多目標考試時間表的建模方式，在算法運行過程中，當出現非支配解數量不足的情況時，必然會對NNIA框架下的算法性能產生十分明顯的影響。顧本文在采用NNIA算法框架的基礎上，在個體克隆階段，設計了一種基于博弈論的資源分配模型，通過動態控制優勢個體的克隆數量手段，更加合理的分配計算資源。在資源分配模型中，根據非支配排序關系，待克隆的個體首先被劃分為不同的等級（R1,…,Rn）。其中，Ri代表了第i等級的個體的數量。通常情況下，R1中的個體優于其他個體。根據R1個體在所有待克隆個體中所占的比例r，將資源分配模型分解為早期模型、中期模型和后期模型。算法在運行過程中，根據不同的模型，采用相應的克隆策略。早期模型(r≤1/3)：在此階段只有很少的優秀個體（R1個體）。根據博弈論的相關概念，需要抑制R2中個體的克隆數量，以保證其無法影響到R1中的個體。如公式(5)所示，其中Si表示原始的克隆尺寸，Mi表示資源分配模型計算過后，克隆后第i級別的克隆規模。
1.2基于超啟發方法的種群初始化許多學者的研究及仿真實驗表明[1]，基于圖著色的超啟發方法十分適合處理單目標考試時間表問題。采用超啟發方法擁有更大幾率快速找到可行解或潛在的優勢個體。針對本文所面對的多目標考試時間表問題，若能快速得到可行解或潛在的優勢個體，在固定的算法迭代次數的條件下，則更加有利于得到更好的結果。因此，本文采用基于圖著色的超啟發方法生成初始種群。其中，初始種群是由一定數量的初始解(時間表)構成的。首先，隨機產生由不同圖啟發算法構成的啟發式鏈表，根據啟發式鏈表，產生初始解（考試時間表）。在產生初始解的過程中，每當產生一個新的考試時間表示，通過這些不同的啟發式算法，可以產生一個考試科目安排順序，在不違反硬約束的條件下，根據考試安排順序，每門考試隨機安排在時間段中。具體的超啟發方法請參看文獻[1]。另外，本文采用二進制編碼方式，其中每一列代表一個時間段，每一行代表一門考試，數字1表示在此時段安排某門考試，0表示在此時段未安排考試。
2仿真實驗
本文選取Carter標準數據集[14]進行測試。近幾十年來，幾乎所有關于考試時間表算法的研究都采用此數據集進行性能測試，但此數據仍是開放數據，理論最優解仍然未知。本文選取了該數據集中的十個具有代表性的數據，對提出的算法進行仿真實驗。以下仿真均為10次獨立運行實驗，運行環境為2.8GHzCorePersonalComputer。具體參數如表1所示：針對10個測試數據，算法經過10次獨立運行，隨機選取一組解集，其pareto前沿面如圖2所示。少數幾個測試集（car91,car92,ear83等）在個別區域沒有找到非支配解。除上述測試集，大部分的測試集基本上能夠完整勾勒出2目標優化的pareto前沿面，并且對于每一組數據的pareto解都可以較為均勻的分布在其前沿面上。表2記錄了現今這些測試集的最好的運行結果，需要注意的是，此結果均為在單目標優化(固定時間表長度，只優化考試間沖突關系)的環境下產生的。我們選取的運行結果則是根據單目標環境下的時間表長度(P),在我們的多目標算法運行的結果中，選取的對應結果。從對比結果來看，除數據集york83，我們的算法均能找到與單目標模型中相同的時間段。從具體結果上來說，我們的結果的確與其他幾種最優秀的單目標優化結果尚存一定差距，但差距并不明顯。重要的是采用本文提出的多目標優化算法，經過一次運行就可提供不同時間段的多個解，運行效率是單目標優化的數十倍。上述結果表明，將考試時間表問題按照多目標優化問題建模有效且可以極大地提高計算效率。本文在NNIA框架下，在克隆階段采用了資源分配模型，此模型對于整個算法的影響可由下列實驗得出結論。圖3為十組測試數據分別來自為采用資源分配模型的RA-NNIA和未采用此模型的原始NNIA進行十次獨立運行后，非支配解個數的統計盒圖。針對每一個測試數據，左邊采用RA-NNIA，右邊采用NNIA。我們可以明顯看出，采用資源分配模型的RA-NNIA的非支配個體數量明顯的好于未采用的NNIA。圖4為十組測試數據，分別采用RA-NNIA和NNIA，經過十次獨立實驗后，spacing指標的統計盒圖對比。由圖可知，除少數幾組數據(car92,ear83)，采用RA-NNIA算法的均勻性指標都要優于采用NNIA的運行結果。根據以上兩組實驗結果分析可知，對于如此建模的多目標考試時間表問題，非支配解的數量本身就十分的有限，傳統的NNIA僅采用當前的非支配個體進行克隆，而后進行進化操作，導致種群的多樣性難以保持，很有可能進一步導致最終的非支配解數目不足，而RA-NNIA克隆階段，在非支配個體數量不足時，還會利用少部分較好的支配個體，共同進行克隆操作，并且，資源分配模型還會根據當前非支配個體所占的比例，動態控制每一部分個體的克隆比例，此種策略在一定的情況下可以很好地改善傳統NNIA在這方面上的不足。所以，采用資源分配模型的NNIA是有利于非支配個體的產生與保留，有利于算法的多樣性的保持，此策略十分適合用于求解多目標考試時間表問題的多目標進化算法。
