首頁 > 優(yōu)秀范文 > 多目標(biāo)優(yōu)化概念
時(shí)間：2023-06-20 18:03:17
序論：速發(fā)表網(wǎng)結(jié)合其深厚的文秘經(jīng)驗(yàn)，特別為您篩選了11篇多目標(biāo)優(yōu)化概念范文。如果您需要更多原創(chuàng)資料，歡迎隨時(shí)與我們的客服老師聯(lián)系，希望您能從中汲取靈感和知識(shí)！
多目標(biāo)規(guī)劃最優(yōu)的思想起初由法國(guó)經(jīng)濟(jì)學(xué)家V.帕雷托提出，他由政治經(jīng)濟(jì)學(xué)的角度將不可比較的多個(gè)目標(biāo)轉(zhuǎn)化為多個(gè)單目標(biāo)的最優(yōu)問題，涉及到了多目標(biāo)規(guī)劃的概念。上世紀(jì)40年代末，J?馮?諾伊曼和O?莫根施特恩又基于對(duì)策論又提出了在多個(gè)決策人相互矛盾的前提下引入多目標(biāo)問題。50年代初，T?C?庫(kù)普曼斯從生產(chǎn)和分配的活動(dòng)中提出多目標(biāo)最優(yōu)化問題，引入有效解的概念，并得到一些基本結(jié)果。同時(shí)，H?W?庫(kù)恩和A?W?塔克爾從研究數(shù)學(xué)規(guī)劃的角度提出向量極值問題，引入庫(kù)恩-塔克爾有效解概念，并研究了它的必要和充分條件。自70年代以來，多目標(biāo)規(guī)劃的研究越來越受到人們的重視。至今關(guān)于多目標(biāo)最優(yōu)解尚無一種完全令人滿意的定義，所以在理論上多目標(biāo)規(guī)劃仍處于發(fā)展階段。
2、多目標(biāo)規(guī)劃方法優(yōu)化投資組合的應(yīng)用分析
某生產(chǎn)車間計(jì)劃在10天內(nèi)安排生產(chǎn)甲類和乙類兩種商品。已知生產(chǎn)甲類商品需要A號(hào)配件5組，B號(hào)配件3組；生產(chǎn)乙類商品需要A號(hào)配件2組，B號(hào)配件4組。在十天的計(jì)劃期內(nèi)該生產(chǎn)車間僅提高A號(hào)配件180組，B號(hào)配件135組。同時(shí)，我們還知道該生產(chǎn)車間沒生產(chǎn)一個(gè)甲類商品可獲取利潤(rùn)為20元，生產(chǎn)一個(gè)乙類商品可獲取利潤(rùn)15元。那么，通過以上條件甲乙兩類商品分別生產(chǎn)多少可實(shí)現(xiàn)利潤(rùn)最大呢？下面我們將各項(xiàng)數(shù)據(jù)列表如下表1所示：
表1
我們假設(shè)，X1和X2分別為甲乙兩類商品的生產(chǎn)數(shù)量，Z為總利潤(rùn)，以此可以線性規(guī)劃描述此問題，建立數(shù)學(xué)模型應(yīng)該是：
（1）
（2）
其中，X1和X2均為整數(shù)。理想狀態(tài)下，可以利用圖解法即可得出公式（1）的最優(yōu)解為Z=775，X1=32，X2=9。但是，站在車間生產(chǎn)計(jì)劃人員的角度上將，問題往往比較復(fù)雜。
首先，這是一種單一目標(biāo)優(yōu)化問題。但通常來講，一個(gè)規(guī)劃問題需要滿足多個(gè)條件。例如，例如財(cái)務(wù)部門的利潤(rùn)目標(biāo)：利潤(rùn)盡可能大；物資部門的節(jié)約資金：消耗盡可能小；銷售部門的適銷對(duì)路：產(chǎn)品品種多樣；計(jì)劃部門的安排生產(chǎn)：產(chǎn)品批量盡可能大。規(guī)劃問題其本質(zhì)上是多目標(biāo)決策類問題，只是因?yàn)槔镁€性規(guī)劃模型處置，致使生產(chǎn)計(jì)劃人員不得已從諸多目標(biāo)中硬性選擇其中的一種作為線性規(guī)劃的數(shù)學(xué)模型。這樣一來，由數(shù)學(xué)模型目標(biāo)函數(shù)得到的結(jié)果可能會(huì)違背部分部門的根部意愿，從而導(dǎo)致生產(chǎn)過程受阻，又或者是從生產(chǎn)計(jì)劃開始階段就因?yàn)槟承┟芏荒軓闹T多目標(biāo)中選取一個(gè)最優(yōu)目標(biāo)。
其次，線性規(guī)劃問題存在最優(yōu)解的必要條件是可行解集合非空，也就是說各個(gè)約束條件之間彼此相容。但在優(yōu)化投資組合等實(shí)際應(yīng)用問題中有時(shí)候也未必能完全滿足這樣的條件。如因設(shè)備維修養(yǎng)護(hù)、消耗能源或其他產(chǎn)品自身原因?qū)е律a(chǎn)計(jì)劃期內(nèi)不能提供足夠的工時(shí)而無法滿足計(jì)劃生產(chǎn)的進(jìn)度和產(chǎn)量，又或者因投資資本有限的束縛生產(chǎn)原材料的供應(yīng)不能滿足計(jì)劃產(chǎn)品的需求等等。
第三，線性規(guī)劃問題的可行解和最優(yōu)解具有非常明確的價(jià)值，這些可行解和最優(yōu)解都依數(shù)學(xué)函數(shù)模型而定。在實(shí)際的投資組合應(yīng)用當(dāng)中，決策人發(fā)出決策后往往還需要對(duì)其決策進(jìn)行某種修正，主要原因就在于數(shù)學(xué)函數(shù)模型與實(shí)際問題之間不盡相同，具有一種近似性，也就是建立數(shù)學(xué)模型時(shí)應(yīng)對(duì)實(shí)際應(yīng)用問題進(jìn)行簡(jiǎn)化且不考慮新情況的發(fā)生。
計(jì)劃人員為決策人提供的數(shù)學(xué)可行解并不是嚴(yán)格意義上的最優(yōu)解，僅作為決策實(shí)現(xiàn)最優(yōu)的一種參考性計(jì)劃方案。上世界六十年代初期，由查恩斯（A?Charnes）和庫(kù)柏（W?w?CooPer）提出的目標(biāo)規(guī)劃（Goalprogramming）直接已得到了重視和推廣，該法在處置實(shí)際應(yīng)用問題方面承認(rèn)諸項(xiàng)決策條件存在的合理性，即便多個(gè)決策條件是相互沖突的、相互影響的都具有合理性，在做出最終決策中不會(huì)強(qiáng)調(diào)絕對(duì)的最優(yōu)性。由此看來，多目標(biāo)規(guī)劃問題可以認(rèn)為是一種較之于線性規(guī)劃問題更切合于實(shí)際應(yīng)用的決策手段。
3、多目標(biāo)規(guī)劃方法優(yōu)化投資組合的常見途徑
（1）加權(quán)法（或效用系數(shù)法）。
加權(quán)法（或效用系數(shù)法）將投資問題中所有的目標(biāo)進(jìn)行統(tǒng)一度量（例如以錢或效用系數(shù)度量）。本方法的的基本原理是將多目標(biāo)模型轉(zhuǎn)化為多個(gè)單目標(biāo)模型。多個(gè)目標(biāo)，有主次不同和輕重緩急不同等區(qū)別，最重要的一個(gè)目標(biāo)我們將之賦予為優(yōu)先因子P1，次重要的目標(biāo)依次賦予優(yōu)先因子P2，P3，P4，…，同時(shí)約定PK>>PK+1（PK比PK+1擁有更好的優(yōu)先權(quán)）。如果非要將擁有相同優(yōu)先因子的目標(biāo)加以區(qū)別，我們可以將其分別賦予不同的權(quán)系數(shù)wj。它的優(yōu)點(diǎn)在于適用于計(jì)算機(jī)運(yùn)算求解可行解和最優(yōu)解（如線性函數(shù)模型可用單純形法求解），而缺點(diǎn)則在于難以找到合理的權(quán)系數(shù)（如某高速公路建設(shè)投資，在減少建設(shè)投資和保證施工質(zhì)量降低交通傷亡事故率之間難以衡量人的生命價(jià)值）。
（2）序列法（或優(yōu)先級(jí)法）。
序列法（或優(yōu)先級(jí)法）并不是對(duì)每一個(gè)目標(biāo)進(jìn)行加權(quán)，它主要是按照目標(biāo)的輕重緩急不同將其分為各個(gè)不同等級(jí)后再行求解。它的優(yōu)點(diǎn)在于可規(guī)避權(quán)系數(shù)的困擾，適用范圍比較廣，各種決策活動(dòng)幾乎都可使用。例如，某公司在決定提拔人員，很多單位主要根據(jù)該人員的工作積極性、工作能力和對(duì)單位的貢獻(xiàn)價(jià)值等幾個(gè)方面予以考慮，這幾個(gè)方面也會(huì)按照先后順序依次評(píng)定，等級(jí)不同參考評(píng)定的比重也會(huì)有所不同。它的缺點(diǎn)在于難以區(qū)分各個(gè)目標(biāo)的輕重等級(jí)，難以排定優(yōu)先順序無法保證最終的求解結(jié)果是最令人滿意的。
（3）有效解法（或非劣解法）。
中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：1672-7800（2013）012-0067-04
作者簡(jiǎn)介：馬春連（1988-），男，安徽理工大學(xué)理學(xué)院碩士研究生，研究方向?yàn)橹悄苡?jì)算；許峰（1963-），男，安徽理工大學(xué)理學(xué)院教授，研究方向?yàn)椴ㄗV學(xué)和智能計(jì)算。
0引言
在科學(xué)研究和工程應(yīng)用中，許多決策問題具有多目標(biāo)的特點(diǎn)和性質(zhì)，它們需要同時(shí)滿足幾個(gè)相互沖突的不同目標(biāo)，即無法使各個(gè)目標(biāo)同時(shí)達(dá)到最優(yōu)，這類問題稱之為多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problem， MOP）。多目標(biāo)優(yōu)化問題存在一個(gè)最優(yōu)解集合，其中的元素稱為Pareto最優(yōu)解。
由于多目標(biāo)進(jìn)化算法在優(yōu)化控制、挖掘數(shù)據(jù)、設(shè)計(jì)機(jī)械、移動(dòng)網(wǎng)絡(luò)規(guī)劃等領(lǐng)域的成功應(yīng)用，使得學(xué)術(shù)界興起研究進(jìn)化算法的熱潮。自上世紀(jì)80年代以來，人們已提出多種多目標(biāo)進(jìn)化算法，比如Srinivas的NSGA，Zitzler的SPEA，Knowles的PAES以及Deb的NSGA-Ⅱ等。
近年來，一些新的進(jìn)化算法被用來求解多目標(biāo)優(yōu)化問題，如蟻群算法、粒子群算法、免疫算法、分布估計(jì)算法等。
上世紀(jì)90年代末，人工免疫算法開始興起，其思想源于生物的免疫系統(tǒng)，它借鑒了免疫系統(tǒng)的功能、原理和模型并用于進(jìn)行尋優(yōu)搜索。由于現(xiàn)在還不能充分認(rèn)識(shí)免疫機(jī)理，所以有關(guān)免疫算法的研究基本集中在其它算法。我們用免疫原理來改進(jìn)并構(gòu)成新的算法，比如免疫神經(jīng)網(wǎng)絡(luò)、免疫遺傳算法等。人工免疫系統(tǒng)算法的自身研究成果并不多，主要有基于克隆選擇原理的克隆選擇算法和基于陰性選擇原理的陰性選擇算法等。
多目標(biāo)優(yōu)化; Pareto優(yōu)勝; Pareto前沿; 演化算法; 自適應(yīng)
中圖分類號(hào): TP18
文獻(xiàn)標(biāo)志碼: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 引言
科學(xué)研究和工程應(yīng)用中的優(yōu)化問題大多是多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem,MOP),如車輛路徑路徑問題、QoS路由等。這類問題通常包含若干個(gè)相互矛盾且沒有共同量綱的目標(biāo) [1-3]。如何在優(yōu)化過程中既兼顧各目標(biāo)利益又體現(xiàn)各目標(biāo)的地位,是求解此類問題的關(guān)鍵[4-5]。
多目標(biāo)優(yōu)化的目的是使決策者最終能夠找到一個(gè)滿意的決策方案。目前在多目標(biāo)優(yōu)化算法中,基于Pareto優(yōu)勝的算法非常流行[6-8]。這些算法主要集中于利用算法找到最大的Pareto最優(yōu)解集,找到Pareto 前沿與已知全局前沿的最小距離,及找到解的最大寬度等[9-10]。然而,在實(shí)際的應(yīng)用系統(tǒng)中,決策者通常期望算法能夠在較短的時(shí)間內(nèi)提供一個(gè)或幾個(gè)可采納的解決方案。在算法的效率和解的質(zhì)量不能同時(shí)滿足的情況下,如何快速地給決策者提供合理、易決策、可接受的解決方案,是算法走向?qū)嶋H應(yīng)用的一個(gè)關(guān)鍵問題。
本文定義了一種Pareto-ε優(yōu)勝的概念,并基于此概念提出了一種新的基于ε-優(yōu)勝的多目標(biāo)演化算法(Pareto-ε Multi-Objective Evolutionary Algorithm,PEMOEA)。該算法采用一種新的帶調(diào)節(jié)度的搜索策略以調(diào)節(jié)搜索的步長(zhǎng),加快算法的收斂,并采用ε的自適應(yīng)調(diào)整策略改進(jìn)解的質(zhì)量。實(shí)驗(yàn)結(jié)果顯示,新策略可以使搜索更加快速有效地到達(dá)Pareto前沿,為決策者提供可行的解決方案。
1 Pareto-ε的相關(guān)定義
圖1為Pareto比較搜索示意圖。圖中f1 和f2為兩個(gè)子目標(biāo),表示搜索空間中的隨機(jī)點(diǎn),所組成的曲線表示最終的Pareto前沿。
圖片
圖1 Pareto比較搜索示意圖
如果從隨機(jī)點(diǎn)A出發(fā)進(jìn)行搜索,那么A的附近有B、C、D優(yōu)于它(極小化)。逐步推進(jìn)搜索到E、F、G、H,然后搜索到N、O、…、S,最后才能搜索到Pareto前沿…。通過分析發(fā)現(xiàn),從A搜索到最優(yōu)解,做了許多無用功。如果采取一定的策略,適當(dāng)調(diào)整搜索的步長(zhǎng),搜索速度將會(huì)大幅度提高。
定義1 Pareto-ε優(yōu)勝。向量u=(u1,…,un)ε-優(yōu)勝于向量v=(v1,…,vn)(表示為u┆華εv)當(dāng)且僅當(dāng)i∈{1,…,n},滿足ui≤vi±ε,ε≥0。
與以往文獻(xiàn)的區(qū)別在于,本文定義的ε-優(yōu)勝可以加上ε也可以減去ε:如果加上ε,稱該調(diào)節(jié)度為帶寬容度的;如果減去ε,稱該調(diào)節(jié)度為帶苛刻度的。
定義2 Pareto-ε無差別。向量u=(u1,…,un)無差別于向量v=(u1,…,un)當(dāng)且僅當(dāng)i∈{1,…,n} 滿足|ui-vi|≤ε,ε≥0。
定義3 Pareto-ε最優(yōu)解。對(duì)于給定的MOP F(x),解x∈X稱為X上的Pareto-ε最優(yōu)解,當(dāng)且僅當(dāng)不存在x′∈X,使得F(x′)滬F(x)。
定義4 Pareto-ε最優(yōu)解集。對(duì)于給定的MOP,其Pareto-ε最優(yōu)解集P*-ε定義為:
P*-ε={x∈X|開霆x′∈X,使得F(x′)滬F(x)}
由以上定義可以看出,Pareto-ε最優(yōu)解集是在Pareto最優(yōu)解集基礎(chǔ)上的推廣,是一個(gè)比Pareto最優(yōu)解集更大的區(qū)域(寬容度下)或者更狹窄的區(qū)域(苛刻度下)。
定義5 Pareto-ε前沿。Pareto-ε前沿Pf-ε*定義為:
Pf-ε*={u=F(x)|x∈P-ε*}
Pareto優(yōu)勝關(guān)系與Pareto-ε優(yōu)勝關(guān)系的區(qū)別如圖2所示。
圖片
圖2 Pareto與Pareto-ε比較
圖中,f1和f2Х直鴇硎MOP的兩個(gè)子目標(biāo),a、b、c、d、e、f、g、h、i分別代表目標(biāo)空間中的一個(gè)區(qū)域。顯然,優(yōu)勝于a的是b、e、d區(qū)域。而根據(jù)本文的定義1、2可知,ε-優(yōu)勝于a的是c、f、i、h、g區(qū)域,b、e、d區(qū)域與a是ε-無差別的。a的非劣域正好由L曲線(Pareto優(yōu)勝下的)所標(biāo)識(shí)的區(qū)域向前推進(jìn)到達(dá)U曲線(Pareto-ε優(yōu)勝下)所標(biāo)識(shí)的區(qū)域。
Pareto優(yōu)勝與Pareto-ε優(yōu)勝相比,每次找到的Pareto最優(yōu)解的范圍是一條曲線或者曲面,而找到的Pareto-ε最優(yōu)解的范圍是帶一定寬度的區(qū)域帶;基于Pareto-ε優(yōu)勝比較的搜索步伐要明顯快于Pareto優(yōu)勝比較的。
┑4期 ┩踅晴等:基于Pareto-ε優(yōu)勝的自適應(yīng)快速多目標(biāo)演化算法
┆撲慊應(yīng)用 ┑30卷
2 PEMOEA算法
2.1 算法設(shè)計(jì)
由于當(dāng)前研究MOP大多數(shù)是基于演化算法的,為驗(yàn)證Pareto-ε優(yōu)勝的新定義及其相關(guān)策略,本節(jié)基于演化算法,給出一類新的基于Pareto-ε優(yōu)勝的多目標(biāo)優(yōu)化算法。算法框架如下:
程序前
begin
t=0;
隨機(jī)產(chǎn)生初始群體Pt={x1,x2,…,xM};
計(jì)算群體中所有個(gè)體的Rank函數(shù)值;
while (不滿足終止條件) do
從Ptе腥〕Rank值最大的前N個(gè)個(gè)體x1,x2,…,xN進(jìn)行遺傳操作,產(chǎn)生KЦ魴賂鎏;
Pt′=Pt∪K;
計(jì)算Pt′е興有個(gè)體的Rank值并從大到小排列;
取前M個(gè)個(gè)體形成新一代群體Pt+1;
t=t+1;
endwhile;
輸出Ptё魑求出的Pareto-ε最優(yōu)解集,計(jì)算出與PtФ雜Φ哪勘晗蛄考;
end
程序后
2.2 自適應(yīng)Е諾髡策略
算法采用動(dòng)態(tài)調(diào)整策略,通過動(dòng)態(tài)調(diào)整ε的值,使算法開始時(shí)快速向Pareto真實(shí)前沿逼近,但最終又不受ε的影響,也就是讓?duì)脓灾]惴ㄔ誦泄程中逐步回歸為0,從而更好地逼近真實(shí)的Pareto前沿。本文設(shè)計(jì)了一個(gè)公式,該公式的值可以隨著算法執(zhí)行代數(shù)的增加而減少,逐步趨近為0,從而減弱Е弄Ф宰詈蠼獾撓跋,如式(1)所示。
ε=-(gig┆max+l)h+d (1)
其中:gi為算法當(dāng)前的運(yùn)行代數(shù);g┆max是最大運(yùn)行代數(shù);l、r、s分別為調(diào)節(jié)參數(shù)。
3 實(shí)驗(yàn)結(jié)果和討論
3.1 實(shí)驗(yàn)仿真
實(shí)驗(yàn)所使用的物理平臺(tái)為Pentium 4 CPU 3.0@GHz、512@MB內(nèi)存,軟件平臺(tái)為VC++6.0和Matalab 7.0。算法分別采用三種搜索策略進(jìn)行測(cè)試:帶苛刻度的、帶寬容度的、動(dòng)態(tài)調(diào)整Е諾摹T謁惴ㄔ誦泄程中只是εУ娜≈擋煌,實(shí)施動(dòng)態(tài)調(diào)整策略后,也只是增加了對(duì)式(1)的計(jì)算,并未增加時(shí)間復(fù)雜度和較大的計(jì)算量。因此,本文采用算法終止時(shí)所花費(fèi)的計(jì)算代數(shù)來衡量算法的性能。從仿真實(shí)驗(yàn)中隨機(jī)選擇一組測(cè)試數(shù)據(jù),測(cè)試函數(shù)為:
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。
函數(shù)的Pareto前沿最終效果如圖3所示。
圖片
圖3 函數(shù)Pareto前沿效果
Е湃「髦植煌值時(shí)算法的終止代數(shù)如表1所示。表2為對(duì)ε實(shí)行動(dòng)態(tài)調(diào)整后的計(jì)算結(jié)果。圖4則給出了g┆max=5B000, l=1,r=-3,s=0.3下的Pf-ε*效果圖,其中M為群體大小。
3.2 性能分析
1)Pareto-ε優(yōu)勝比較策略。實(shí)驗(yàn)證明該策略可以增加搜索步長(zhǎng),加快算法的收斂速度,無論是帶寬容度的還是帶苛刻度的比較策略都可以顯著改善收斂性質(zhì)。在帶寬容度的情況下,Е旁醬蟊冉咸跫就越弱,搜索速度就越快,隨著ε值的增大算法的收斂性能逐步減弱。在帶苛刻度的情況下,雖然比較條件加強(qiáng)了,但是每次成功的移動(dòng)步長(zhǎng)增大了,從而收斂速度也加快了。但兩種情況均有不足,在帶寬容度的情況下,ε的值增大到一定程度后,解的質(zhì)量會(huì)下降;在帶苛刻度的情況下,若ε過大會(huì)導(dǎo)致收斂速度過快而早熟,甚至出現(xiàn)比較條件過強(qiáng)而算法無法啟動(dòng)的情況。
2)自適應(yīng)的ε調(diào)整策略。針對(duì)以上不足,本文通過動(dòng)態(tài)調(diào)整εУ鬧,使算法開始時(shí)快速向Pareto前沿逼近,最終讓?dǎo)ε灾]惴ㄔ誦泄程中逐步回歸為0,從而更好地逼近真實(shí)的Pareto前沿。該策略既可以提高算法的搜索和收斂速度,又可以消除Е弄е刀宰鈧戰(zhàn)獾鬧柿康撓跋臁S氤S玫畝嗄勘晁惴ㄏ啾,這種包括自適應(yīng)的Е弄У髡策略的PEMOEA算法在處理MOP上具有顯著的優(yōu)越性。
表格(有表名)
表1 不同Е弄取值下的算法終止代數(shù)
運(yùn)算次數(shù)ε
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
平均運(yùn)算代數(shù)417.3401.6403.6402.6357.3351.8336.8349.5342.8335.4322.6
圖片
圖4 不同群體規(guī)模下的Pf-ε*效果
表格(有表名)
表2 動(dòng)態(tài)調(diào)整Е弄У乃惴ㄖ罩勾數(shù)
運(yùn)算ご問ε
-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
平均運(yùn)に憒數(shù)353.625348.375351.938
4 結(jié)語
本文定義了一種Pareto-ε優(yōu)勝關(guān)系的概念,提出了一種新的自適應(yīng)ε調(diào)整策略,設(shè)計(jì)了一個(gè)新的基于ε-優(yōu)勝的快速多目標(biāo)演化算法,分析了ε取值對(duì)算法的影響。實(shí)驗(yàn)表明,Pareto-ε概念是合理、有效的,加快了算法尋優(yōu)的速度,可以快速地為決策者提供合理、滿意的決策方案。下一步的工作重點(diǎn)在于:進(jìn)一步探討ε的取值及其動(dòng)態(tài)變化規(guī)律;探索在寬容度和苛刻度下,算法性能得以進(jìn)一步改進(jìn)的內(nèi)在機(jī)制。
參考文獻(xiàn):
[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]劉淳安,王宇平.動(dòng)態(tài)多目標(biāo)優(yōu)化的進(jìn)化算法及其收斂性分析[J].電子學(xué)報(bào),2007,35(6): 1118-1121.
[5]石川,李清勇,史忠植.一種快速的基于占優(yōu)樹的多目標(biāo)進(jìn)化算法[J].軟件學(xué)報(bào),2007,18(3): 505-516.
[6]鄭向偉,劉弘.多目標(biāo)進(jìn)化算法研究進(jìn)展[J].計(jì)算機(jī)科學(xué),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.
中圖分類號(hào)：TM352 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2016）10-00-02
0 引 言
一直以來，人們都想實(shí)現(xiàn)模擬集成電路設(shè)計(jì)的自動(dòng)化，但考慮到模擬集成電路性能指標(biāo)多，各性能指標(biāo)間互相影響等因素，使得模擬集成電路的自動(dòng)化進(jìn)程遠(yuǎn)遠(yuǎn)落后于數(shù)字集成電路，模擬集成電路已經(jīng)成為制約集成電路發(fā)展的瓶頸。隨著技術(shù)的發(fā)展，片上系統(tǒng)將模擬集成電路與數(shù)字集成電路整合到一塊芯片上。但人們對(duì)模擬集成電路的自動(dòng)化研究卻從未中斷過，同時(shí)也取得了一些成果，其中基于優(yōu)化的設(shè)計(jì)方法因適用范圍廣而受到了人們的青睞。
基于優(yōu)化的設(shè)計(jì)方法將模擬集成電路的設(shè)計(jì)看作是多目標(biāo)優(yōu)化問題，電路設(shè)計(jì)時(shí)的性能指標(biāo)如增益、帶寬、相位裕度等就是多目標(biāo)優(yōu)化的目標(biāo)函數(shù)。通過多目標(biāo)優(yōu)化算法求解出電路目標(biāo)空間的Pareto前沿，該前沿就是電路各種性能指標(biāo)折衷后的最優(yōu)前沿，允許電路設(shè)計(jì)者從一組相互沖突的設(shè)計(jì)指標(biāo)中做出最佳選擇。
基于優(yōu)化的設(shè)計(jì)方法的核心是多目標(biāo)優(yōu)化算法，解決多目標(biāo)優(yōu)化問題的常用算法是加權(quán)和算法[1]，該算法容易理解、操作簡(jiǎn)單，但是該算法不能求出Pareto前沿上位于凹區(qū)間內(nèi)的解，而當(dāng)權(quán)值均勻分布時(shí)，Pareto前沿上凸區(qū)間內(nèi)的解分布不均勻[2]。本文采用了自適應(yīng)加權(quán)和算法，該算法在加權(quán)和算法的基礎(chǔ)上改進(jìn)而來，克服了加權(quán)和算法的上述缺點(diǎn)。
1 自適應(yīng)加權(quán)和算法原理
自適應(yīng)加權(quán)和算法[3]的權(quán)值系數(shù)沒有預(yù)先確定，而是通過所要求解問題的Pareto前沿曲線獲得。首先用傳統(tǒng)加權(quán)和算法產(chǎn)生一組起始解，然后在目標(biāo)空間確定需要細(xì)化的區(qū)域。將待細(xì)化區(qū)域看作可行域并且對(duì)該區(qū)域施加不等式約束條件，最后用傳統(tǒng)加權(quán)和方法對(duì)這些需要細(xì)化的子區(qū)域進(jìn)行優(yōu)化。當(dāng)Pareto前沿上的所有子區(qū)域長(zhǎng)度達(dá)到預(yù)定值時(shí)，優(yōu)化工作完成。
圖1所示的自適應(yīng)加權(quán)算法與傳統(tǒng)加權(quán)和算法進(jìn)行了對(duì)比，說明了自適應(yīng)加權(quán)和算法的基本概念。真正的Pareto前沿用實(shí)線表示，通過多目標(biāo)優(yōu)化算法獲得的解用黑圓點(diǎn)表示。在該例中，整個(gè)Pareto前沿由相對(duì)平坦的凸區(qū)域和明顯凹的區(qū)域組成。解決這類問題的典型方法就是加權(quán)和算法，該算法可以描述成如下形式：
上式中描述的是兩個(gè)優(yōu)化目標(biāo)的情形，J1（x）和J2（x）分別為兩個(gè)目標(biāo)函數(shù)，sf1，0（x）和sf2，0（x）分別為對(duì)應(yīng)的歸一化因子，h（x）和g（x）分別為等式約束條件和不等式約束條件。
圖1（a）為采用加權(quán)和算法后解的分布，可以看出大部分解都分布在anchor points和inflection point，凹區(qū)間內(nèi)沒有求出解。該圖反映了加權(quán)和算法的兩個(gè)典型缺點(diǎn)：
（1）解在Pareto前沿曲線上分布不均勻；
（2）在Pareto前沿曲線為凹區(qū)間的部分不能求出解。
因此盡管加權(quán)和算法具有簡(jiǎn)單、易操作的優(yōu)點(diǎn)，但上述缺點(diǎn)卻限制了其應(yīng)用，這些固有缺陷在實(shí)際多目標(biāo)優(yōu)化設(shè)計(jì)問題中頻繁出現(xiàn)。圖1描述了本文所提出的自適應(yīng)加權(quán)和算法的總體流程以及基本概念。首先根據(jù)加權(quán)和算法得到一組起始解，如圖1（a）所示，通過計(jì)算目標(biāo)前沿空間上相鄰解的距離來確定需要進(jìn)行細(xì)化的區(qū)域，如圖1（b）所示，該圖中確定了兩個(gè)需要進(jìn)行細(xì)化的區(qū)域。在確定需要進(jìn)行細(xì)化的區(qū)域分別在平行于兩個(gè)目標(biāo)方向上添加額外的約束，如圖1（c）所示，在該圖中向減小方向J1添加的約束為1，J2減小方向添加的約束為2。對(duì)細(xì)化后添加完約束的區(qū)域用加權(quán)和算法優(yōu)化，得出新解，如圖1（d）所示，其中加權(quán)和算法求解最優(yōu)解時(shí)采用Matlab中的fmincon函數(shù)。從該圖中可看出，細(xì)化區(qū)域內(nèi)產(chǎn)生了新解，Pareto前沿上解的分布較之前更加均勻，且求出了凹區(qū)域內(nèi)的解，繼續(xù)細(xì)化能夠找出更多的解，Pareto前沿上的解也將分布地更加均勻。自適應(yīng)加權(quán)和算法的流程圖如圖2所示。
2 兩級(jí)運(yùn)放設(shè)計(jì)實(shí)例
以一個(gè)帶米勒補(bǔ)償?shù)膬杉?jí)運(yùn)放[4]為例，說明自適應(yīng)加權(quán)和算法的多目標(biāo)優(yōu)化設(shè)計(jì)。兩級(jí)運(yùn)放電路圖如圖3所示。
電路的各項(xiàng)性能指標(biāo)如表1所列。
電路優(yōu)化過程中采用工作點(diǎn)驅(qū)動(dòng)[5，6]的設(shè)計(jì)方法，電路的設(shè)計(jì)變量為電路直流工作點(diǎn)上一組獨(dú)立的電壓、電流。電路性能通過方程獲得，但方程中的小信號(hào)參數(shù)通過對(duì)工藝庫(kù)進(jìn)行模糊邏輯建模[7，8]得到，使得計(jì)算速度提高的同時(shí)保證了計(jì)算精度。兩級(jí)運(yùn)放電路的優(yōu)化結(jié)果如圖4所示。
圖為算法迭代五代后的優(yōu)化結(jié)果，由圖可以發(fā)現(xiàn)，經(jīng)過五代的優(yōu)化迭代，求出的最優(yōu)解在Pareto前沿上分布均勻。在同一電路中，單位增益帶寬的增加與擺率的增加都會(huì)使功耗增加，而電路功耗降低導(dǎo)致的結(jié)果是電路的面積增加，或通過犧牲面積來換取低功耗，犧牲面積換取電路的帶寬增加。這些結(jié)果與電路理論相吻合，同時(shí)也再次說明了模擬電路設(shè)計(jì)過程中的折衷以及模擬集成電路設(shè)計(jì)的復(fù)雜性。
3 結(jié) 語
自適應(yīng)加權(quán)和算法能求出位于凹區(qū)間內(nèi)的最優(yōu)解，并且最優(yōu)解分布均勻。本文通過兩級(jí)運(yùn)放電路驗(yàn)證了算法的優(yōu)化效果，最終得到了滿意的優(yōu)化結(jié)果。
參考文獻(xiàn)
[1]陽明盛，羅長(zhǎng)童.最優(yōu)化原理、方法及求解軟件[M].北京：科學(xué)出版社，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]陳曉，郭裕順.工作點(diǎn)驅(qū)動(dòng)的模擬集成電路優(yōu)化設(shè)計(jì)[J].杭州電子科技大學(xué)學(xué)報(bào)，35（6）：18-22.
中圖分類號(hào)：TM732 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671－7597（2012）0220135－01
在發(fā)電權(quán)的交易上，很多文章主要以買賣雙方報(bào)價(jià)為主，本文為體現(xiàn)發(fā)電調(diào)度的節(jié)能減排要求，將煤耗率和價(jià)格這兩個(gè)參數(shù)結(jié)合起來，提出了基于能耗和效益綜合最優(yōu)的多目標(biāo)交易模型，并使用Pareto最優(yōu)的方法來對(duì)多目標(biāo)進(jìn)行求解。
1 發(fā)電權(quán)交易模式
發(fā)電權(quán)是一種商品，發(fā)電權(quán)市場(chǎng)是雙邊交易市場(chǎng)，撮合交易是組織發(fā)電權(quán)交易的常見模式。
2 發(fā)電權(quán)交易成本
本文將交易成本分為兩部分，固定成本 和電力網(wǎng)損成本 。固定成本包括組織發(fā)電權(quán)的固定傭金，管理費(fèi)用，行政費(fèi)用等，電力網(wǎng)損成本是開展發(fā)電權(quán)交易前后整個(gè)網(wǎng)絡(luò)潮流變化所帶來的成本。
3 發(fā)電權(quán)交易模型設(shè)計(jì)
3.1 發(fā)電權(quán)交易模型
基于文獻(xiàn)[3]提出的效益最優(yōu)、文獻(xiàn)[6]提出的能耗最優(yōu)的發(fā)電權(quán)交易模型，本文提出了基于能耗和效益綜合最優(yōu)的發(fā)電權(quán)交易模型。
3.2 基于煤耗和效益綜合最優(yōu)的模型
基于煤耗和效益綜合最優(yōu)的發(fā)電權(quán)交易的目標(biāo)函數(shù)為：
其中C表示Pareto前沿所組成的集合， 買方i和賣方j(luò) 的交易量，
為賣方j(luò)出售的電量， 為買方i購(gòu)買的電量， 為第i個(gè)買家申報(bào)的報(bào)價(jià)， 為第j個(gè)賣家申報(bào)的報(bào)價(jià)， 為買家 和賣家 之間的交易成本，
和 是參與交易的機(jī)組 和機(jī)組 的煤耗率函數(shù)。 表示發(fā)電權(quán)交易產(chǎn)生的社會(huì)效益， 表示發(fā)電權(quán)交易所節(jié)約的煤耗量。
4 Pareto最優(yōu)的概念及求解
在3.2所提到的煤耗和效益多目標(biāo)綜合最優(yōu)模型，在數(shù)學(xué)上稱為多目標(biāo)優(yōu)化問題，關(guān)于多目標(biāo)最優(yōu)有很多種求解方法，本文使用Pareto最優(yōu)的方法來對(duì)多目標(biāo)進(jìn)行求解。
4.1 Pareto最優(yōu)的概念
一般地，多目標(biāo)優(yōu)化問題有如下形式：
其中Ω表示所有可行解的集合， 表示k個(gè)目標(biāo)函數(shù)。
4.2 Pareto最優(yōu)解的求解方法
多目標(biāo)優(yōu)化Pareto最優(yōu)解集的求取可分為兩大類：傳統(tǒng)算法和進(jìn)化算法。PSO粒子群優(yōu)化算法是最近興起的一種進(jìn)化計(jì)算方法。
PSO算法的標(biāo)準(zhǔn)形式如下所示：
其中 和 分別表示第 個(gè)粒子在第 次迭代中的位置和速度；
表示第 個(gè)粒子的個(gè)體最優(yōu)解； 表示全局最優(yōu)解； 是之間的隨機(jī)數(shù)； 是學(xué)習(xí)因子，用于控制收斂的速度； 是慣性系數(shù)。
本文在PSO算法基礎(chǔ)上，提出一種基于動(dòng)態(tài)Pareto解集的PSO算法（Dynamic Pareto Warehouse-based PSO，DPW-PSO），利用這種算法可在較小的初始種群規(guī)模下，產(chǎn)生大量的Pareto最優(yōu)解而并不顯著增加計(jì)算量。
5 DPW-PSO算法求解多目標(biāo)發(fā)電權(quán)交易問題
本文使用Pareto最優(yōu)的方法、DPW-PSO算法對(duì)多目標(biāo)進(jìn)行求解，求解過程是先通過隨機(jī)算法大致得到（U，F(xiàn)）這個(gè)二維函數(shù)的Pareto前沿，然后在Pareto前沿上選出一些解和它們對(duì)應(yīng)的交易方案，這些交易方案在某種程度上來說都是最佳的。
6 發(fā)電權(quán)交易算例分析
下面是對(duì)某電網(wǎng)發(fā)電權(quán)交易的算例分析，選取電網(wǎng)典型運(yùn)行方式下的數(shù)據(jù)，分別按效益最優(yōu)、能耗最優(yōu)、效益和能耗綜合最優(yōu)三種模型進(jìn)行仿真計(jì)算。表1是某電網(wǎng)典型情況下各機(jī)組的發(fā)電出力和煤耗率。
A6電廠發(fā)電不足，A1-A5電廠代其發(fā)電，表2為發(fā)電權(quán)交易在效益最優(yōu)模型、煤耗最優(yōu)模型、煤耗和效益綜合最優(yōu)三種模型下所產(chǎn)生的社會(huì)效益、消耗的煤的總量以及電網(wǎng)網(wǎng)損的變化。
對(duì)計(jì)算結(jié)果分析可知，多目標(biāo)最優(yōu)有多個(gè)解，這些解得到的交易方案在某種程度上來說都是最佳的，電力公司可以根據(jù)交易結(jié)果對(duì)發(fā)電權(quán)進(jìn)行安全校核，每次交易的完成都以電網(wǎng)通過安全約束為標(biāo)志。
7 結(jié)論
基于煤耗和效益綜合最優(yōu)的發(fā)電權(quán)交易模型，其Pareto最優(yōu)解為一個(gè)解集，這表明決策者有多組相對(duì)而言都比較理想的交易方案可做選擇，這些交易方案效益和降低煤耗不一樣，但總體是朝著煤耗減少和社會(huì)效益增大的方向變化。因此，研究與市場(chǎng)機(jī)制相協(xié)調(diào)的電網(wǎng)節(jié)能降耗發(fā)電權(quán)交易機(jī)制，實(shí)施“以大代小”、“以煤代氣”發(fā)電權(quán)交易，對(duì)于充分發(fā)揮其節(jié)能減排的優(yōu)勢(shì)，滿足發(fā)電調(diào)度的節(jié)能減排要求具有十分重要的意義和廣闊的應(yīng)用前景。
參考文獻(xiàn)：
中圖分類號(hào)：C93-0 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1001-828X（2013）08-00-01
一、引言
人們?cè)趯?duì)科學(xué)問題進(jìn)行研究的過程中，僅考慮單一目標(biāo)的做法已經(jīng)不能滿足實(shí)際需求，隨著研究問題規(guī)模的不斷擴(kuò)大以及復(fù)雜程度的不斷增加，必然涉及對(duì)多個(gè)目標(biāo)進(jìn)行分析、優(yōu)化，并最終做出合理的決策。一般情況下，多目標(biāo)決策問題的各個(gè)目標(biāo)之間往往是矛盾的，改善其中的一個(gè)目標(biāo)，有可能會(huì)是其他目標(biāo)難以實(shí)現(xiàn)，或者說是效用降低，也就是說想要使多個(gè)目標(biāo)一起達(dá)到最優(yōu)值是不現(xiàn)實(shí)的，而只能通過的一定的方法進(jìn)行處理，使各個(gè)子目標(biāo)最大程度的實(shí)現(xiàn)最優(yōu)化[1]。自 20世紀(jì)60年代早期以來，多目標(biāo)優(yōu)化決策問題吸引了越來越多研究人員的注意力。因此，解決多目標(biāo)優(yōu)化決策問題具有非常重要的科研價(jià)值和實(shí)際意義。
二、多目標(biāo)優(yōu)化決策方法
在對(duì)文獻(xiàn)研究的基礎(chǔ)上，得出Keen和Morton將決策問題分類為結(jié)構(gòu)化決策問題、半結(jié)構(gòu)化決策問題和非結(jié)構(gòu)化決策問題[2]。在實(shí)際解決問題的過程中，一般情況下，多目標(biāo)優(yōu)化問題是不存在唯一全局最優(yōu)解的，而求解得到的過多的非劣解是無法直接應(yīng)用的，所以在求解時(shí)要需要通過一定的方法尋找到一個(gè)最終解。目前對(duì)于多目標(biāo)優(yōu)化決策方法還沒有一個(gè)統(tǒng)一的分類標(biāo)準(zhǔn)，從國(guó)外的研究資料來看，本文將從以下三個(gè)方面進(jìn)行分類介紹。
1.按照優(yōu)化決策過程
根據(jù)優(yōu)化過程和決策過程的先后順序，可以將多目標(biāo)優(yōu)化決策方法分為以下3大類[3]。
（1）先驗(yàn)優(yōu)先權(quán)方法，即先決策后搜索。這種方法是通過預(yù)先確定各目標(biāo)的優(yōu)先權(quán)值，再將所有目標(biāo)按權(quán)值大小組合成一個(gè)標(biāo)量效用函數(shù)，通過這種方法最終可以復(fù)雜的多目標(biāo)優(yōu)化決策問題轉(zhuǎn)化成比較常規(guī)的單目標(biāo)優(yōu)化決策問題。這種方法可以說是一種化繁為簡(jiǎn)的方法。
（2）交互式方法，即決策與搜索交互進(jìn)行。這里所說的交互是指優(yōu)先權(quán)決策與非劣解集的搜索二者之間是交替進(jìn)行的。首先按照優(yōu)先權(quán)進(jìn)行決策，逐漸產(chǎn)生非劣解，最后又從非劣解集搜索的過程中提出取能夠?qū)?yōu)先權(quán)設(shè)置進(jìn)行改良的信息?？梢哉f，交互式方法結(jié)合了概率的相關(guān)知識(shí)，是先驗(yàn)與后驗(yàn)優(yōu)權(quán)設(shè)置方法的有機(jī)結(jié)合。
（3）后驗(yàn)優(yōu)先權(quán)方法，即先搜索后決策。首先通過優(yōu)化器進(jìn)行非劣解集的搜索，然后再利用決策器從搜索到的非劣解集中進(jìn)行選擇。
2.按照適應(yīng)度和選擇方式
基于適應(yīng)度和選擇方式的不同，可以將多目標(biāo)優(yōu)化決策方法分為以下3類[4]。
（1）基于聚合選擇的優(yōu)化方法。這些算法的原理是首先將多目標(biāo)優(yōu)化決策問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，然后再利用一般的解決單目標(biāo)優(yōu)化決策問題的方法進(jìn)行求解。不過，這類方法在將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題的過程中，會(huì)具有一定的主觀色彩，當(dāng)決策人員對(duì)優(yōu)化對(duì)象認(rèn)識(shí)的經(jīng)驗(yàn)不足時(shí)聚合得到的單目標(biāo)問題將不再符合原有多目標(biāo)問題的初衷以及特點(diǎn)。
（2）基于準(zhǔn)則選擇的優(yōu)化方法。這種算法會(huì)依據(jù)不同的準(zhǔn)則進(jìn)行選擇、交叉以及轉(zhuǎn)變，并最終將所有目標(biāo)融合起來，其實(shí)相當(dāng)于把適應(yīng)度函數(shù)進(jìn)行線性求和，而目標(biāo)的權(quán)重則取決于當(dāng)前代的種群。
（3）基于Pareto選擇的優(yōu)化方法。這是基于Pareto概念的一種優(yōu)化決策算法，它的基本原理是將多個(gè)目標(biāo)的值直接映射到一個(gè)基于秩的適應(yīng)度函數(shù)中。
3.偏好信息的表達(dá)方式
按照偏好信息的表達(dá)方式，可以將多目標(biāo)優(yōu)化決策方法分為了以下三類：
（1）事前偏好信息索取。這種方法在優(yōu)化之前，決策者首先要把所有的偏好信息一次性都提供給分析人員，而分析人依據(jù)這些偏好，結(jié)合一定的方法優(yōu)化計(jì)算出可行的“最優(yōu)解”。
（2）事后偏好信息索取。這種方法是指在對(duì)問題進(jìn)行了最大優(yōu)化之后，由分析人求得了大部分的非劣解之后，再請(qǐng)決策者在這些非劣解中按照自己的偏好做出選擇。
（3）逐步偏好信息索取。這種優(yōu)化方式是在優(yōu)化過程中，由分析人員通過不斷交流的方式向決策者不停地、逐步地獲取偏好信息，在過程中逐漸優(yōu)化決策信息的一種方法。
三、結(jié)論
對(duì)以上的多目標(biāo)優(yōu)化決策方法進(jìn)行分類了解之后，可以得出多目標(biāo)優(yōu)化問題的目標(biāo)間具有矛盾性，當(dāng)某一目標(biāo)值得到改進(jìn)時(shí)，可能造成其他目標(biāo)值的變壞。在多目標(biāo)優(yōu)化決策方法發(fā)展之初，決策者的性格、偏好、經(jīng)驗(yàn)、知識(shí)等幾乎沒有被考慮在決策問題的求解過程中，這樣使得決策結(jié)果往往不太貼合實(shí)際情況，因此在后來產(chǎn)生的很多決策算法，都加入了決策者的意愿?？梢缘弥嗄繕?biāo)優(yōu)化問題求解是一個(gè)決策過程，決策者的主要任務(wù)就是在各個(gè)目標(biāo)之間進(jìn)行折衷，通過犧牲某個(gè)或某些目標(biāo)的性能來改善其它目標(biāo)，所以尋找令決策者滿意的解。不同的優(yōu)化問題具有不同的屬性和特點(diǎn)，每種優(yōu)化算法也都具有自身的特點(diǎn)，其適應(yīng)性是相對(duì)的而不是絕對(duì)的。因此，在解決實(shí)際的問題時(shí)候，應(yīng)該首先了解待求解問題的特點(diǎn)，從而選擇出適合于優(yōu)化問題自身特點(diǎn)的優(yōu)化算法。所以說，多目標(biāo)優(yōu)化決策方法的研究，不僅僅要對(duì)單一算法進(jìn)行深入的分析，更重要的是算法之間的結(jié)合運(yùn)用，使其能夠互相取長(zhǎng)補(bǔ)短，共同解決好實(shí)際中滿足決策人要求的問題。
參考文獻(xiàn)：
[1]肖曉偉，肖迪，林錦國(guó)，肖玉峰.多目標(biāo)優(yōu)化問題的研究概述[J].計(jì)算機(jī)應(yīng)用研究，2011，28（3）：805-808.
[2]陳雪龍.面向復(fù)雜決策問題的模型構(gòu)造與管理方法研究[D].大連：大連理工大學(xué)，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.
中圖分類號(hào)：TP311.13文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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
課表編排系統(tǒng)的設(shè)計(jì)是整個(gè)教務(wù)管理信息系統(tǒng)的設(shè)計(jì)難點(diǎn)。除了要解決時(shí)間、空間、人員的安排問題，排課需要考慮的因素和指標(biāo)還比較多，如課程安排的均勻程度、重要課程盡量安排在上午等。這些指標(biāo)往往需要同時(shí)優(yōu)化，即多目標(biāo)優(yōu)化問題[1-2]。由于往往多個(gè)目標(biāo)不能同時(shí)最優(yōu)，對(duì)各個(gè)目標(biāo)的偏好不同，得到的優(yōu)化解也不同。傳統(tǒng)方法是將多目標(biāo)優(yōu)化問題的多個(gè)目標(biāo)函數(shù)通過適當(dāng)方法（如加權(quán)法等）轉(zhuǎn)化為單目標(biāo)優(yōu)化問題進(jìn)行處理。該方法的缺點(diǎn)需要對(duì)優(yōu)化問題掌握一定的先驗(yàn)知識(shí)，否則難以確定加權(quán)系數(shù)。
針對(duì)上述問題，本文采用Pareto多目標(biāo)遺傳算法來進(jìn)行優(yōu)化計(jì)算。該方法無需對(duì)優(yōu)化的各個(gè)目標(biāo)掌握先驗(yàn)知識(shí)，并具有極強(qiáng)的魯棒性、全局尋優(yōu)能力和隱含的并行性等特點(diǎn)，使得該方法成為多目標(biāo)優(yōu)化方法中的一個(gè)研究熱點(diǎn)。
1 排課系統(tǒng)設(shè)計(jì)
課表的安排除了要考慮教學(xué)計(jì)劃、教師資源以及教室使用情況，同時(shí)還要以其他教學(xué)要求來評(píng)判課程安排的優(yōu)劣，如：
（1）課程分布均勻，避免課程都集中在某一兩天的情況；
（2）重要課程盡量安排在上午；
（3）對(duì)于一周多節(jié)的課程要盡量保證同一門課程兩節(jié)之間時(shí)間間隔較長(zhǎng)。
本文設(shè)定一個(gè)班級(jí)一天排6節(jié)課，上午排4節(jié)課，下午排2節(jié)課，即一周有30節(jié)課，因此每一節(jié)上課時(shí)間的變量在整數(shù)區(qū)間（1-30）上取值。量化排課優(yōu)劣程度的方法如下描述：
（1）為了使重要課程盡量安排在上午，首先將每一節(jié)課的值進(jìn)行修正：一周有n節(jié)課時(shí)，按先后順序記課的值分別為1，2，…，n。其中，式中，若該節(jié)無課，則當(dāng)前值設(shè)為0。假設(shè)排課結(jié)果為x1，x2，…，xn，評(píng)價(jià)函數(shù)f1（X）如式（1）所示：
（1）
由式（1）可以看出，當(dāng)f1（X）的值越小時(shí)，課程就越集中在上午。
（2）對(duì)于使課程安排均勻，我們統(tǒng)計(jì)一周每天安排的課程數(shù)目，并求這5天課程數(shù)目的方差f2（X）。那么，方差f2（X）越小則排課越均勻。
（3）對(duì)于每周要安排多節(jié)的課程，要使同一門課程兩節(jié)之間間隔的時(shí)間盡可能長(zhǎng)，我們計(jì)算同一門課（每周需要安排多節(jié)的課程）兩次值的相差絕對(duì)值。那么，一周內(nèi)所有課的相差絕對(duì)值之和f3（X）越大，則課程安排越合理。
2 多目標(biāo)遺傳算法優(yōu)化
傳統(tǒng)多目標(biāo)優(yōu)化方法是將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。如線性加權(quán)法，將上述三個(gè)目標(biāo)函數(shù)f1（X），f2（X），f3（X）按其重要程度給出一組權(quán)系數(shù)w1，w2，w3，則評(píng)價(jià)函數(shù)的最優(yōu)解如式（2）所示：
（2）
但該方法要求對(duì)優(yōu)化問題掌握先驗(yàn)知識(shí)時(shí)。而本文采用Pareto多目標(biāo)遺傳算法來進(jìn)行優(yōu)化計(jì)算。無需掌握先驗(yàn)知識(shí)，
Pareto占優(yōu)定義如下：假設(shè)x1，x2∈某一可行域Ω，x1被x2占優(yōu)是指對(duì)部分i，有fi（X）≥fj（X），而對(duì)其他的j≠i，fi（X）> fj（X）。Pareto最優(yōu)解x0是指在Ω中不存在任何x占優(yōu)于x0。
從定義中可知，Pareto最優(yōu)解不是唯一的，而是由許多“非劣解”（非劣解，是指在不降低其它性能指標(biāo)的前提下，再也不能提高該性能指標(biāo)）組成的解集，因此群體搜索策略（如遺傳算法）是非常合適的求解方法。
遺傳算法是通過對(duì)一代群體按照尋優(yōu)目標(biāo)進(jìn)行一系列的選種、交叉、變異而使下一代群體從整體上更接近最優(yōu)解[3]。本文將選擇算子中引入Pareto占優(yōu)概念，即Pareto遺傳算法。
本文Pareto遺傳算法操作流程如下：
輸入：函數(shù)h（X）；權(quán)系數(shù)w1，w2，w3；初始群體
Step 1：設(shè)小生境距離；
Step 2：在每類部分群體中選Pareto占優(yōu)個(gè)體；
Step 3：交叉；
Step 4：變異；
Step 5：生成下一代群體；
Step 6：檢查評(píng)價(jià)優(yōu)化結(jié)果是否收斂。如沒有，
返回步驟（2）；如已收斂，執(zhí)行-結(jié)束。
輸出：優(yōu)化結(jié)果（即最后一代群體）
相比較以往傳統(tǒng)遺傳算法，本文算法改進(jìn)措施如下：
（1）根據(jù)種群中占優(yōu)的個(gè)數(shù)多少來賦予個(gè)體相應(yīng)適應(yīng)度。
（2）在每代中采用部分種群來決定占優(yōu)的情況。而且，當(dāng)兩個(gè)個(gè)體之間彼此互不占優(yōu)的時(shí)候，其結(jié)果通過適應(yīng)度共享來決定。由于本文沒有在整個(gè)種群中使用Pareto意義選種，而是在每代中只采用部分種群，因此其能快速并產(chǎn)生較好的Pareto意義占優(yōu)解。
（3）相比較傳統(tǒng)遺傳算法，本文算法還引入小生境技術(shù)[4-5]。該技術(shù)可以防止基因漂移，使群體均勻分布在Pareto最優(yōu)解集中。由于一周有5天課程，本文將個(gè)體劃分為5類，即從這5個(gè)類當(dāng)中選出適應(yīng)度較大的個(gè)體作為該類的代表組群。
3 實(shí)驗(yàn)結(jié)果及分析
假設(shè)需為某班排課，共6門課程，英語、語文、數(shù)學(xué)等。其中英語、語文、數(shù)學(xué)每周需要安排6節(jié)，其他課程每周安排2節(jié)。
我們首先通過隨機(jī)方法生成30次排課解作為初始群體，以上述f1（X），f2（X），f3（X）的極值作為優(yōu)化目標(biāo)。根據(jù)遺傳算法進(jìn)行優(yōu)化計(jì)算，設(shè)突變率為1%，經(jīng)過100代進(jìn)化，結(jié)果如表1所示：
表1 Pareto多目標(biāo)遺傳算法優(yōu)化結(jié)果
初始群體 100代群體
均值 標(biāo)準(zhǔn)差 均值 標(biāo)準(zhǔn)差
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可以看出，盡管實(shí)驗(yàn)沒有提供對(duì)優(yōu)化目標(biāo)的先驗(yàn)知識(shí)，但通過Pareto遺傳算法優(yōu)化后，3個(gè)優(yōu)化目標(biāo)f1（X），f2（X），f3（X）都得到同時(shí)優(yōu)化，并且優(yōu)化結(jié)果比較理想。
4 結(jié)束語
該文針對(duì)傳統(tǒng)多目標(biāo)優(yōu)化排課算法需要先驗(yàn)知識(shí)的缺點(diǎn)，將Pareto多目標(biāo)遺傳算法應(yīng)用到排課系統(tǒng)中，并實(shí)驗(yàn)證明該方法的有效性。
參 考 文 獻(xiàn)
[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.
【關(guān)鍵詞】協(xié)同進(jìn)化 多目標(biāo)算法 多目標(biāo)優(yōu)化
協(xié)同進(jìn)化算法是基于協(xié)同進(jìn)化理論出現(xiàn)的一類新的進(jìn)化算法，其在傳統(tǒng)進(jìn)化算法強(qiáng)調(diào)個(gè)體與個(gè)體之間因環(huán)境原因所產(chǎn)生的競(jìng)爭(zhēng)的基礎(chǔ)之上，進(jìn)一步考慮多個(gè)種群之間、種群與環(huán)境之間的在進(jìn)化過程中的協(xié)同作用。目前通常使用的協(xié)同進(jìn)化算法主要可以分為兩類：以種群競(jìng)爭(zhēng)的方式加速算法收斂和使用種群合作的方式保持種群多樣性。但是這兩種方式都只是強(qiáng)調(diào)了協(xié)同進(jìn)化中的一部分，都存在其不足。在大自然生物們個(gè)體之間的協(xié)同進(jìn)化過程中，競(jìng)爭(zhēng)、合作這兩種相互矛盾的關(guān)系往往都是同時(shí)存在的。只有強(qiáng)者才具優(yōu)先的權(quán)利，以遺傳下自身的基因，其他處于弱勢(shì)的個(gè)體會(huì)團(tuán)結(jié)起來與其對(duì)抗，達(dá)到留下自身基因的目的。劉靜在她的博士論文《協(xié)同進(jìn)化算法及其應(yīng)用研究》中基于種群競(jìng)爭(zhēng)和合作思想構(gòu)建了MOCEA（Multi-objective Coevolutionary Algorithm），通過競(jìng)爭(zhēng)特性算子――吞并算子來達(dá)到使得優(yōu)秀的基因得到廣泛的傳播和保持種群基因的多樣性，并得到很好的效果。但由于劉的思想仍然是主要依靠種群合作來達(dá)到加速收斂的目的，其所采用的競(jìng)爭(zhēng)特性算子――吞并算子對(duì)其算法進(jìn)化并沒起到?jīng)Q定性作用。
1 算法設(shè)計(jì)
1.1 算子設(shè)定
1.3.1 測(cè)試函數(shù)一
該測(cè)試函數(shù)為一帶約束條件兩目標(biāo)函數(shù)，其主要用于測(cè)試多目標(biāo)優(yōu)化算法在pareto前沿的收斂的能力。
從表3.1可以看出CCEA算法在Spreed這個(gè)指標(biāo)上具有很大的優(yōu)勢(shì)，從圖3-1也可以看出CCEA算法比NSGAII算法在這個(gè)測(cè)試函數(shù)的計(jì)算上具有更大的優(yōu)勢(shì)。
1.3.2 測(cè)試函數(shù)二
該函數(shù)為帶約束的兩目標(biāo)測(cè)試函數(shù)，在其約束條件內(nèi)含有兩個(gè)可調(diào)變量a、b，本文選取a=0.1，b=16來對(duì)CCEA算法和NSGAII算法進(jìn)行測(cè)試。該函數(shù)的PFtrue曲線為三段相互之間不連續(xù)的曲線，在對(duì)多目標(biāo)優(yōu)化算法測(cè)試時(shí)，通常對(duì)中間一段進(jìn)行關(guān)注，其主要特點(diǎn)在于這個(gè)區(qū)段的部分點(diǎn)不易被搜索到，性能較差的算法在這部分通常表現(xiàn)為斷開。該函數(shù)因此可以檢測(cè)算法在pareto前沿的搜索能力。
由表3.2可以看出CCEA算法除了在GD這個(gè)指標(biāo)上占優(yōu)勢(shì)以外，在其他兩個(gè)指標(biāo)上并不占優(yōu)勢(shì)，甚至在Spreed這個(gè)指標(biāo)上略有不如。但從圖3-2看出來在中間一段曲線上CCEA算法搜索出來的為一條連續(xù)曲線，而NSGAII算法在這部分是斷開的，這可證明CCEA算法對(duì)pareto前沿解的搜索性能要強(qiáng)于NSGAII算法。
2 結(jié)論
中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1007-9599 (2012) 06-0000-02
研究表明，文化能使種群以一定的速度進(jìn)化和適應(yīng)環(huán)境，而這個(gè)速度是超越單純依靠基因遺傳生物進(jìn)化速度的[1]。種群在進(jìn)化過程中，個(gè)體知識(shí)的積累和群體內(nèi)部知識(shí)的交流在另外一個(gè)層面促進(jìn)群體的進(jìn)化。受這些思想的啟發(fā)，Reynolds[1]于1994年提出文化算法，近年來引起國(guó)內(nèi)外眾多學(xué)者關(guān)注。
與其他進(jìn)化算法相比，文化算法提供了一種明確的機(jī)制來表示、存儲(chǔ)和傳遞進(jìn)化時(shí)的知識(shí)，因而在一些問題上取得了比傳統(tǒng)進(jìn)化算法更好的結(jié)果。但是對(duì)文化算法的研究才剛剛開始，還有許多問題需要進(jìn)一步研究。因此有必要對(duì)文化算法進(jìn)行深入研究，對(duì)其基本原理、特點(diǎn)、適用的問題、應(yīng)用等方面展開全面研究，以引起國(guó)內(nèi)更多學(xué)者的關(guān)注，為后續(xù)學(xué)者展開相關(guān)研究提供方便。
一、文化算法
（一）文化算法基本原理
文化算法框架由群體空間(Population Space)和信念空間(Belief Space)兩部分組成，如圖1所示。群體空間和信念空間是兩個(gè)相對(duì)獨(dú)立的進(jìn)化過程，群體空間從微觀層面模擬個(gè)體進(jìn)化的過程，而信念空間從宏觀層面模擬文化的形成、傳遞和比較。從計(jì)算模型的角度來看，任何一種符合文化算法要求的進(jìn)化算法都可以嵌入文化算法框架中作為群體空間的一個(gè)進(jìn)化過程[2]。
圖1 文化算法框架
經(jīng)典文化算法的偽代碼如下所示：
其中：
Accept()：將從群體中所選擇個(gè)體的經(jīng)驗(yàn)傳遞到信念空間。
Influence()：信念空間形成群體經(jīng)驗(yàn)后，利用此函數(shù)影響群體空間中個(gè)體的行為，以使群體空間中個(gè)體得到更高的進(jìn)化效率。
（二）文化算法一般特點(diǎn)
1.雙重繼承（群體層和知識(shí)層）；2.知識(shí)是用來指導(dǎo)種群進(jìn)化的“明燈”；3.支持分層結(jié)構(gòu)；4.領(lǐng)域知識(shí)與個(gè)體分離；5.支持自適應(yīng)；6.不同的層可以不同的速率進(jìn)化（文化進(jìn)化速度是生物進(jìn)化速度的10倍）；7.支持混合方式(hybrid approaches)來解決問題；8.文化算法的各不同模型都可用一個(gè)統(tǒng)一的框架表示。
（三）文化算法適用的問題
1.含有大量領(lǐng)域知識(shí)的問題（如約束優(yōu)化問題）；2.一些群體空間和信念空間中的適應(yīng)過程可能在不同層次以不同速度發(fā)生的復(fù)雜環(huán)境；3.知識(shí)需要以不同的方式進(jìn)行推理，并以不同的形式表達(dá)；4.需要多種群、多信念空間，并且這些空間進(jìn)行交互的；5.一些可能出現(xiàn)分層結(jié)構(gòu)的群體和知識(shí)因素的環(huán)境。
（四）文化算法的設(shè)計(jì)
1.信念空間的設(shè)計(jì)
A本體知識(shí)（某一領(lǐng)域中的公用概念）的描述；B約束知識(shí)的描述；C解決方案的描述；D確定哪些部分將會(huì)被修改？用Update()函數(shù)來更新每一個(gè)需要修改的部分；E知識(shí)維護(hù)；
2.群體空間的設(shè)計(jì)
A聲明變量；B如何用這些變量來產(chǎn)生一個(gè)解決方案？C如何評(píng)價(jià)這個(gè)解決方案？設(shè)計(jì)時(shí)要注意：究竟該從信念空間開始還是從群體空間開始設(shè)計(jì)，取決于具體問題。如對(duì)于分類問題和約束問題，前者經(jīng)常從信念空間開始，而后者經(jīng)常從群體空間開始。
二、利用文化算法求解多目標(biāo)優(yōu)化問題[3]
（一）多目標(biāo)優(yōu)化問題
多目標(biāo)優(yōu)化問題的主要任務(wù)就是在滿足一定約束條件的參數(shù)空間內(nèi)搜索Pareto最優(yōu)集。近年來興起的進(jìn)化算法，包括遺傳算法、模擬退火算法由于能較好地解決傳統(tǒng)算法的缺點(diǎn)，成為近年來解決多目標(biāo)優(yōu)化問題的研究熱點(diǎn)。2003年，Ricardo Landa Becerra首次提出用文化算法來求解多目標(biāo)優(yōu)化問題[3]，并取得了不錯(cuò)的結(jié)果。
（二）求解MOP的文化算法
利用文化算法求解MOP問題時(shí)，種群空間采用進(jìn)化規(guī)劃，因此稱為CAEP。信念空間包括兩類知識(shí)：規(guī)范化知識(shí)和網(wǎng)格圖。
信念空間：規(guī)范化知識(shí)記錄每一個(gè)目標(biāo)函數(shù)值區(qū)間的上下邊界 和 ，如下圖6所示。利用輸入的 值可以將每個(gè)區(qū)間[ ， ]劃分為 個(gè)子區(qū)間，并由此創(chuàng)建對(duì)應(yīng)的網(wǎng)格圖。
…
圖2 規(guī)范化知識(shí)結(jié)構(gòu)
如下圖3所示是用于解決具有兩個(gè)目標(biāo)函數(shù)的MOP時(shí)的網(wǎng)格圖，此時(shí)，網(wǎng)格在每一維上被分割為8個(gè)子區(qū)間，因此形成一個(gè)8*8的網(wǎng)格圖。
圖3 網(wǎng)格圖
對(duì)于有k個(gè)目標(biāo)函數(shù)的MOP，網(wǎng)格圖有 個(gè)單元，每一個(gè)單元中記錄位于該單元中非劣最優(yōu)解的個(gè)數(shù)，其中，所有的非劣最優(yōu)解都存儲(chǔ)在一個(gè)外部文件中。算法結(jié)束時(shí)，存儲(chǔ)在外部文件中的內(nèi)容即為算法找到的Pareto最優(yōu)解集，其中外部文件的大小為q。
信念空間初始化：初始化信念空間前，首先在種群空間生成一個(gè)初始種群。然后求得初始種群中所有非劣最優(yōu)解對(duì)應(yīng)的每一個(gè)目標(biāo)函數(shù)的最小值和最大值，即為規(guī)范化知識(shí)的邊界值 和 。利用此邊界值，可以畫出相應(yīng)的網(wǎng)格圖。并根據(jù)輸入的 劃分子區(qū)間。
信念空間的更新：網(wǎng)格圖每一代都更新，規(guī)范化知識(shí)每 代更新一次。
更新規(guī)范化知識(shí)時(shí)，只需要利用Accept()函數(shù)從當(dāng)前存儲(chǔ)在外部文件中的所有非劣最優(yōu)解中選出新產(chǎn)生的解，利用這些新產(chǎn)生的非劣最優(yōu)解所對(duì)應(yīng)的目標(biāo)函數(shù)區(qū)間來更新網(wǎng)格圖。
變異：種群空間中的個(gè)體采用下式進(jìn)行變異，變異后種群中個(gè)體數(shù)為2p。
選擇：采用錦標(biāo)賽選擇法從2p個(gè)個(gè)體中選擇p個(gè)個(gè)體作為下一代。選擇原則如下：
1.若一個(gè)個(gè)體優(yōu)于（dominate）另一個(gè)個(gè)體，則優(yōu)個(gè)體獲勝；
2.若兩個(gè)個(gè)體無法比較，或者兩個(gè)個(gè)體的目標(biāo)函數(shù)值相同，則：
a若兩者均位于信念空間中的網(wǎng)格圖中，則所在單元含個(gè)體較少的個(gè)體獲勝；
b若其中一個(gè)個(gè)體不在網(wǎng)格圖中，則此個(gè)體獲勝。
（三）求解MOP的文化算法流程
Step1 生成大小為P的初始種群；
Step2 評(píng)價(jià)初始種群；
Step3 初始化信念空間；
Step4 執(zhí)行變異操作以產(chǎn)生P個(gè)子個(gè)體（這時(shí)種群中有2P個(gè)個(gè)體）；
Step5 評(píng)價(jià)子個(gè)體；
Step6 利用錦標(biāo)賽選擇法選擇出P個(gè)個(gè)體作為下一代；
Step7 將新產(chǎn)生的非劣最優(yōu)解保存到外部文件中；
Step8 利用保存在外部文件中的個(gè)體更新信念空間；
Step9 轉(zhuǎn)到Step4直到滿足終止條件。
（四）結(jié)論
與其他算法相比，用文化算法求解多目標(biāo)優(yōu)化問題時(shí)，執(zhí)行次數(shù)較少，求得的解更好，甚至能夠找到其他算法沒有發(fā)現(xiàn)的Pareto前沿區(qū)域。缺點(diǎn)是該方法在一些情況中會(huì)很快失去種群多樣性。
三、總結(jié)與展望
與傳統(tǒng)的進(jìn)化算法不同，文化算法只提供了一個(gè)進(jìn)化模型，任何基于種群的進(jìn)化算法都可為文化算法的群體空間提供種群，如遺傳算法、進(jìn)化規(guī)劃、進(jìn)化策略等。
相比其他較成熟的進(jìn)化算法，文化算法的研究才剛剛起步，應(yīng)用的范圍也比較少，因此有必要對(duì)文化算法進(jìn)行深入研究，將其應(yīng)用到更多的領(lǐng)域。
參考文獻(xiàn)：
區(qū)域經(jīng)濟(jì)規(guī)劃理論概述
（一）區(qū)域經(jīng)濟(jì)規(guī)劃的概念
所謂區(qū)域經(jīng)濟(jì)，它是建立在對(duì)區(qū)域經(jīng)濟(jì)發(fā)展的研究之上的。研究區(qū)域經(jīng)濟(jì)發(fā)展的根本目的，就是為了解決區(qū)域經(jīng)濟(jì)如何實(shí)現(xiàn)增長(zhǎng)的問題，也就是如何生產(chǎn)更多的財(cái)富、創(chuàng)造更多的GDP、如何提高區(qū)域人民生活水平和人均收入等問題。按照古典經(jīng)濟(jì)學(xué)理論分析，區(qū)域發(fā)展的三個(gè)最基本的要素就是：資本、勞動(dòng)力和技術(shù)。而要想將要素轉(zhuǎn)化為實(shí)際的財(cái)富，需要一定的條件和方式，而一個(gè)健全的政策、機(jī)制和環(huán)境，則進(jìn)一步?jīng)Q定了各類要素如何在各區(qū)域發(fā)展中實(shí)現(xiàn)其作用以及作用的大小。
區(qū)域經(jīng)濟(jì)規(guī)劃就是在時(shí)間上提前對(duì)區(qū)域經(jīng)濟(jì)發(fā)展的一個(gè)統(tǒng)籌規(guī)劃。具體來講，它是指一組生產(chǎn)要素現(xiàn)在和未來在特定區(qū)域的配置或部署問題，根據(jù)目前已有的要素組合，綜合評(píng)估發(fā)展條件以及未來環(huán)境變化的可能性，合理的安排在未來時(shí)期要素應(yīng)該如何組合、如何配置才能達(dá)到預(yù)期的發(fā)展目標(biāo)。所以，區(qū)域經(jīng)濟(jì)規(guī)劃主要是以當(dāng)前已有的要素組合和發(fā)展環(huán)境條件等進(jìn)行的一項(xiàng)決策活動(dòng)，具體實(shí)施這種決策則是未來的活動(dòng)。如果這種未來是將來很長(zhǎng)一段時(shí)間，這就需要解決戰(zhàn)略問題，對(duì)未來發(fā)展起到導(dǎo)向作用；相反如果是一個(gè)不長(zhǎng)的時(shí)間，那就需要制定行動(dòng)的具體方案，有效指導(dǎo)將來的發(fā)展行動(dòng)。
另外，區(qū)域經(jīng)濟(jì)規(guī)劃和區(qū)域產(chǎn)業(yè)布局是容易被混淆的兩個(gè)概念，被混淆的原因是兩者有許多共性。產(chǎn)業(yè)的空間布局是以致富最小的生產(chǎn)成本為目的進(jìn)行的，例如以運(yùn)費(fèi)最小為標(biāo)準(zhǔn)來選擇最佳區(qū)位，或企業(yè)如何選擇分布地點(diǎn)導(dǎo)致利潤(rùn)最大化等。而區(qū)域經(jīng)濟(jì)規(guī)劃的任務(wù)則主要為了解決以下三個(gè)問題：第一，在什么時(shí)間、投入多少、投入哪類要素？第二，各類要素在規(guī)定的時(shí)間內(nèi)在什么樣的地方組合？ 第三，以什么樣的方式、什么樣的機(jī)制和什么指導(dǎo)思想去組合？?jī)烧唠m有諸多相同，但也有本質(zhì)上的區(qū)別。
（二）區(qū)域經(jīng)濟(jì)規(guī)劃的基本內(nèi)容
顧名思義，區(qū)域經(jīng)濟(jì)規(guī)劃的對(duì)象當(dāng)然是區(qū)域。在很大程度上，它的基本職能就是從整體上進(jìn)行綜合性協(xié)調(diào)，所以它絕不同于部門規(guī)劃、行業(yè)規(guī)劃和專題規(guī)劃等規(guī)劃活動(dòng)。區(qū)域經(jīng)濟(jì)規(guī)劃涉及的范圍不僅囊括了經(jīng)濟(jì)、人口、社會(huì)、環(huán)境、資源等方面，而且還需要對(duì)條塊之間、塊塊之間以及區(qū)內(nèi)區(qū)外之間進(jìn)行協(xié)調(diào)規(guī)劃。除此之外，它還需要對(duì)不同的產(chǎn)業(yè)部門之間、主導(dǎo)產(chǎn)業(yè)和配套產(chǎn)業(yè)之間進(jìn)行協(xié)調(diào)規(guī)劃。總而言之，區(qū)域經(jīng)濟(jì)規(guī)劃是一項(xiàng)綜合性的規(guī)劃，綜合性規(guī)劃下又包含了許多不同層面形成的單向規(guī)劃，綜合規(guī)劃還必須考慮到單項(xiàng)規(guī)劃相互之間的協(xié)調(diào)關(guān)系。
所以，區(qū)域經(jīng)濟(jì)規(guī)劃的內(nèi)容是十分豐富和廣泛的。目前從國(guó)家已作出的相關(guān)區(qū)域經(jīng)濟(jì)規(guī)劃中可以看到，區(qū)域經(jīng)濟(jì)規(guī)劃主要包含了以下內(nèi)容：國(guó)土開發(fā)整治的目標(biāo)和任務(wù)；自然條件和國(guó)土資源的綜合評(píng)價(jià)；自然資源開發(fā)的規(guī)模、布局和步驟；社會(huì)、經(jīng)濟(jì)現(xiàn)狀分析和遠(yuǎn)景預(yù)測(cè)；國(guó)土整治和環(huán)境保護(hù)；人口、城市化和城市布局；綜合開發(fā)的重點(diǎn)區(qū)域；交通、通訊、動(dòng)力和水電等基礎(chǔ)設(shè)施的安排；宏觀經(jīng)濟(jì)效益估價(jià)；實(shí)施對(duì)策和措施。改革開放以來，隨著中央財(cái)權(quán)事權(quán)的逐步下放，地方自也日益擴(kuò)大，區(qū)域經(jīng)濟(jì)規(guī)劃的內(nèi)容在實(shí)踐中也不斷地豐富，并且日益區(qū)域化。
（三）區(qū)域經(jīng)濟(jì)規(guī)劃的目標(biāo)
區(qū)域經(jīng)濟(jì)規(guī)劃的目標(biāo)不是單一的，而是形成了一個(gè)目標(biāo)體系。這個(gè)目標(biāo)體系主要包括三個(gè)目標(biāo)，即經(jīng)濟(jì)增長(zhǎng)方面的目標(biāo)、社會(huì)進(jìn)步方面的目標(biāo)和生態(tài)環(huán)境改善方面的目標(biāo)。這些目標(biāo)可能是相輔相成、相互促進(jìn)的關(guān)系，同時(shí)也可能存在著相互矛盾和制約的一面。比如經(jīng)濟(jì)增長(zhǎng)目標(biāo)和就業(yè)目標(biāo)，為了取得高速的經(jīng)濟(jì)增長(zhǎng)，就需要大力推進(jìn)工業(yè)化的進(jìn)程，優(yōu)先發(fā)展重工業(yè)和高科技產(chǎn)業(yè)，推進(jìn)技術(shù)創(chuàng)新與技術(shù)進(jìn)步。而高科技產(chǎn)業(yè)是資金密集型產(chǎn)業(yè)，而且隨著技術(shù)的飛速進(jìn)步，生產(chǎn)效率和投資利用率也進(jìn)一步提高，這樣就限制了勞動(dòng)就業(yè)的增加。反過來，如果增加了就業(yè)人口，勞動(dòng)力數(shù)量增多，人均固定資產(chǎn)減少，勞動(dòng)生產(chǎn)率自然相應(yīng)下降，經(jīng)濟(jì)增長(zhǎng)就受到了限制和影響。再比如經(jīng)濟(jì)增長(zhǎng)和生態(tài)環(huán)境目標(biāo)，如果可以提高對(duì)二者協(xié)調(diào)發(fā)展的關(guān)注度，那么經(jīng)濟(jì)增長(zhǎng)則有利于生態(tài)環(huán)境的保護(hù)和改善，節(jié)能減排，經(jīng)濟(jì)增長(zhǎng)也可以提供更多的資金改善生態(tài)環(huán)境；而如果忽視了生態(tài)環(huán)境，只將經(jīng)濟(jì)增長(zhǎng)作為發(fā)展的唯一目標(biāo)，就會(huì)造成對(duì)生態(tài)環(huán)境的嚴(yán)重破壞，環(huán)境質(zhì)量也會(huì)不斷下降。
（四）區(qū)域經(jīng)濟(jì)規(guī)劃的影響因素
1.本國(guó)經(jīng)濟(jì)發(fā)展的歷史背景。從很大程度上來說，區(qū)域經(jīng)濟(jì)發(fā)展的狀況和規(guī)劃是由國(guó)家的宏觀經(jīng)濟(jì)發(fā)展規(guī)劃所決定的。那么，各省區(qū)戰(zhàn)略地位的確定，各地區(qū)之間的區(qū)域分工，以及各省區(qū)和區(qū)域未來的發(fā)展方向，國(guó)家在宏觀布局時(shí)早已做好了規(guī)劃和安排。所以，各地區(qū)在進(jìn)行本區(qū)域的經(jīng)濟(jì)規(guī)劃時(shí)，必須以國(guó)家的宏觀經(jīng)濟(jì)規(guī)劃為前提，在此基礎(chǔ)上制定自身的區(qū)域經(jīng)濟(jì)規(guī)劃。例如，國(guó)家相繼提出的沿海各省對(duì)外開放政策、西部大開發(fā)戰(zhàn)略、振興東北老工業(yè)基地戰(zhàn)略以及中部崛起戰(zhàn)略等。
2.規(guī)劃區(qū)域的自然狀況。一個(gè)地區(qū)的發(fā)展很大程度上依賴于該地區(qū)的自然資源等物質(zhì)基礎(chǔ)。所以，在制定規(guī)劃時(shí)，要充分考慮到地區(qū)的自然資源狀況，充分發(fā)揮自身自然資源狀況的優(yōu)勢(shì)，然后在此基礎(chǔ)上選擇主導(dǎo)產(chǎn)業(yè)以帶動(dòng)區(qū)域經(jīng)濟(jì)的發(fā)展。比如在新疆地區(qū)，石油資源和煤炭資源比較豐富，同時(shí)也是重要的棉花產(chǎn)地，這些都是國(guó)家的戰(zhàn)略物質(zhì)，所以在制定該地區(qū)的經(jīng)濟(jì)規(guī)劃時(shí)，一定要圍繞能源、棉花等這些優(yōu)勢(shì)資源做文章，以期通過這些優(yōu)勢(shì)來帶動(dòng)當(dāng)?shù)亟?jīng)濟(jì)發(fā)展。
3.規(guī)劃區(qū)域的經(jīng)濟(jì)資源狀況。除了規(guī)劃區(qū)域內(nèi)的自然資源狀況對(duì)區(qū)域經(jīng)濟(jì)規(guī)劃有重要的影響，經(jīng)濟(jì)資源狀況也起著十分重要的作用。
首先，人口數(shù)量和勞動(dòng)力資源。勞動(dòng)力作為生產(chǎn)要素之一，自然是經(jīng)濟(jì)發(fā)展不可或缺的，所以具有豐富的勞動(dòng)力資源，不僅可以有效降低人均勞動(dòng)力成本，也可能提供大量的高素質(zhì)人才，這些都可以有效帶動(dòng)區(qū)域經(jīng)濟(jì)發(fā)展。
其次，市場(chǎng)對(duì)區(qū)域經(jīng)濟(jì)規(guī)劃的影響。在制定區(qū)域經(jīng)濟(jì)規(guī)劃時(shí)，一定要事先調(diào)查分析當(dāng)?shù)厥袌?chǎng)的需求和供給。如果供過于求，而區(qū)域居民有效需求不足，必然導(dǎo)致經(jīng)濟(jì)滯脹，產(chǎn)生大量失業(yè)人口，不利于當(dāng)?shù)亟?jīng)濟(jì)的發(fā)展與穩(wěn)定；如果供不應(yīng)求，又必然導(dǎo)致地區(qū)通貨膨脹，同樣不利于經(jīng)濟(jì)發(fā)展。所以制定區(qū)域經(jīng)濟(jì)規(guī)劃時(shí)，一定要在充分了解當(dāng)?shù)厥袌?chǎng)供給需求的基礎(chǔ)上進(jìn)行。另外，對(duì)于某些特殊產(chǎn)業(yè)，還需要注意其空間位置的布置，例如農(nóng)產(chǎn)品的生產(chǎn)、第三產(chǎn)業(yè)的發(fā)展，這些都對(duì)市場(chǎng)有著比較強(qiáng)烈的依賴，所以應(yīng)該大力發(fā)展這些企業(yè)，進(jìn)而帶動(dòng)整個(gè)區(qū)域經(jīng)濟(jì)的發(fā)展。
最后，區(qū)域內(nèi)以及周邊的產(chǎn)業(yè)集群狀況。通過產(chǎn)業(yè)在空間上的聚集，集群內(nèi)部的企業(yè)之間交流增多，在區(qū)域內(nèi)也比較容易形成一條完整的產(chǎn)業(yè)鏈，再加上政府對(duì)一些配套設(shè)施的建設(shè)，可以形成一整套的區(qū)域核心競(jìng)爭(zhēng)力。同時(shí)，產(chǎn)業(yè)集群也有著比較明顯的經(jīng)濟(jì)外部性，通過這種外部規(guī)模經(jīng)濟(jì)和外部范圍經(jīng)濟(jì)，有效帶動(dòng)周邊經(jīng)濟(jì)的發(fā)展，進(jìn)而帶動(dòng)整個(gè)區(qū)域經(jīng)濟(jì)發(fā)展。另外，相關(guān)產(chǎn)業(yè)共同發(fā)展的同時(shí)，各產(chǎn)業(yè)之間會(huì)加強(qiáng)彼此技術(shù)和經(jīng)驗(yàn)的交流，通過這種交流與擴(kuò)散達(dá)到技術(shù)的創(chuàng)新，繼而實(shí)現(xiàn)產(chǎn)品的創(chuàng)新、產(chǎn)業(yè)的升級(jí)。
多目標(biāo)最優(yōu)化方法簡(jiǎn)述
（一）一般多目標(biāo)最優(yōu)化模型
所謂一般多目標(biāo)最優(yōu)化模型，是對(duì)于一個(gè)需要決策的問題，存在多種決策選擇，而所要達(dá)到的目標(biāo)不分主次，這樣就可以構(gòu)建成一個(gè)數(shù)學(xué)函數(shù)模型，其中自變量就是各種決策的變量，因變量就是目標(biāo)函數(shù)。除此之外，對(duì)于自變量，也就是決策的選擇存在一些限制，這就形成對(duì)自變量的約束函數(shù)。
每種不同的決策變量的組合對(duì)應(yīng)一個(gè)目標(biāo)函數(shù)。對(duì)于一個(gè)決策變量組合，如果它能滿足其所對(duì)應(yīng)的目標(biāo)函數(shù)不大于其他任何決策變量組合對(duì)應(yīng)的目標(biāo)函數(shù)，則稱這個(gè)組合是該多目標(biāo)最優(yōu)化模型的一個(gè)有效解；而如果它能滿足其所對(duì)應(yīng)的目標(biāo)函數(shù)嚴(yán)格小于其他組合對(duì)應(yīng)的目標(biāo)函數(shù)，則稱這種決策組合是該多目標(biāo)最優(yōu)化模型的一個(gè)弱有效解。顯然，若一個(gè)決策變量組合是有效解，則它一定是弱有效解。
一般來說，一個(gè)多目標(biāo)最優(yōu)化問題有無窮多個(gè)有效解，它們并不都是決策者滿意的解，只有決策者滿意的有效解才是問題的最終解。得到最優(yōu)解一般有兩種方法：一種是評(píng)價(jià)函數(shù)法，即先求出大量的有效解，然后根據(jù)決策者的意圖找出最優(yōu)解；另一種是交互法，即通過分析者與決策者的相互溝通，逐步地達(dá)成一個(gè)最終解。
（二）分層次多目標(biāo)最優(yōu)化模型
這類模型較一般多目標(biāo)最優(yōu)化模型的特點(diǎn)是：在約束條件下，各個(gè)目標(biāo)函數(shù)不是同等地被最優(yōu)化，而是按不同的優(yōu)先層次先后地進(jìn)行最優(yōu)化。在構(gòu)建數(shù)學(xué)函數(shù)模型時(shí)，也需要按照不同的優(yōu)先層次來設(shè)定目標(biāo)函數(shù)。對(duì)于分層多目標(biāo)最優(yōu)化問題的求解，就需要按照模型所要求的有限層次逐層地進(jìn)行求解，最后一定就可以獲得最優(yōu)解，即使這種最優(yōu)解不是統(tǒng)計(jì)意義上的絕對(duì)最優(yōu)，但一定是可以滿足決策者要求的最優(yōu)解。
區(qū)域經(jīng)濟(jì)規(guī)劃的多目標(biāo)最優(yōu)化實(shí)踐
（一）建立數(shù)學(xué)模型的步驟
為了正確處理各局部之間的關(guān)系，加強(qiáng)局部的協(xié)調(diào)發(fā)展，注意各地區(qū)及部門之間的綜合平衡，就必須運(yùn)用科學(xué)的方法來建立經(jīng)濟(jì)數(shù)學(xué)模型，把抽象的規(guī)劃問題具體化。最后利用嚴(yán)格的數(shù)學(xué)方法，求得最優(yōu)解，以滿足區(qū)域經(jīng)濟(jì)規(guī)劃決策者的要求。
建立經(jīng)濟(jì)數(shù)學(xué)模型主要有以下幾個(gè)步驟：第一，定義和識(shí)別。了解問題的真實(shí)背景，即規(guī)劃區(qū)域的歷史背景、自然資源、市場(chǎng)資源狀況；明確建模的目標(biāo)，確定決策者規(guī)劃經(jīng)濟(jì)所需要達(dá)到的目標(biāo)，如經(jīng)濟(jì)增長(zhǎng)、就業(yè)和生態(tài)環(huán)境等；掌握必要的數(shù)據(jù)資料，建模前必須獲得當(dāng)?shù)氐南嚓P(guān)數(shù)據(jù)，如人口數(shù)據(jù)、市場(chǎng)需求與供給等數(shù)據(jù)。第二，數(shù)據(jù)預(yù)處理。在已經(jīng)了解問題背景，明確了建模目的和掌握了必要的數(shù)據(jù)資料后，就需要提出一些恰當(dāng)?shù)募僭O(shè)，對(duì)問題進(jìn)行必要的簡(jiǎn)化。第三，估計(jì)。通過綜合的分析所獲得的資料，在已有的假設(shè)基礎(chǔ)上，利用適當(dāng)?shù)臄?shù)學(xué)工具合理刻畫各變量之間的關(guān)系，形成目標(biāo)函數(shù)和約束條件，初步建立數(shù)學(xué)模型。第四，驗(yàn)證。將所建立的模型與實(shí)際情況相比較，包括目標(biāo)函數(shù)與決策者意圖的比較、約束函數(shù)與實(shí)際條件的對(duì)比等，以此驗(yàn)證模型的正確性。
（二）實(shí)現(xiàn)最優(yōu)化的建模原則
實(shí)現(xiàn)最優(yōu)化建模需要遵守以下原則：
一是能充分有效地發(fā)揮區(qū)域優(yōu)勢(shì)。前面已有介紹，利用地區(qū)自然資源等優(yōu)勢(shì)可以加快地區(qū)經(jīng)濟(jì)發(fā)展。
二是從區(qū)域?qū)嶋H情況出發(fā)，建立適當(dāng)?shù)慕?jīng)濟(jì)數(shù)學(xué)模型。模型中需要考慮的因素很多，要全面協(xié)調(diào)各種因素，保證模型與區(qū)域?qū)嶋H相符。
三是模型必須考慮到各部門均衡發(fā)展和區(qū)域間相互協(xié)調(diào)。只有各部門均衡發(fā)展、步調(diào)一致，才能實(shí)現(xiàn)最終的和諧發(fā)展。
四是要有利于環(huán)境保護(hù)，堅(jiān)持可持續(xù)戰(zhàn)略思想。雖然經(jīng)濟(jì)發(fā)展與生態(tài)環(huán)境有矛盾之處，但是也更要注意這二者之間的協(xié)調(diào)。
結(jié)論
多目標(biāo)最優(yōu)化理論在經(jīng)濟(jì)、管理、政治方面的運(yùn)用，可以有效合理配置和最優(yōu)化。在區(qū)域經(jīng)濟(jì)規(guī)劃時(shí)，引入多目標(biāo)最優(yōu)化的方法，可以根據(jù)實(shí)現(xiàn)各種方案目標(biāo)所需要的區(qū)域資源與條件來最終確定最優(yōu)解，這樣的方法既科學(xué)，也符合實(shí)際情況，還能有效促進(jìn)區(qū)域經(jīng)濟(jì)快速增長(zhǎng)，社會(huì)協(xié)調(diào)發(fā)展。本文簡(jiǎn)要介紹了區(qū)域經(jīng)濟(jì)規(guī)劃的相關(guān)理論和多目標(biāo)最優(yōu)化方法，并將二者結(jié)合起來，以期能夠?qū)⑦@種方法運(yùn)用到實(shí)際的區(qū)域經(jīng)濟(jì)規(guī)劃中去。
參考文獻(xiàn)：
1.唐永才.90年代國(guó)內(nèi)多目標(biāo)規(guī)劃研究述評(píng)[J].荊門職業(yè)技術(shù)學(xué)院學(xué)報(bào)，1999（3）
本文是在文獻(xiàn)12的基礎(chǔ)上，針對(duì)算法的種群初始化操作，引入了超啟發(fā)方法；在算法的克隆操作中，設(shè)計(jì)了一種新的資源分配模型，是一種關(guān)于多目標(biāo)考試時(shí)間表問題的NNIA改進(jìn)算法，所以除種群初始化操作與克隆操作外，算法中的其他所有操作算子，以及算法流程與文獻(xiàn)12完全相同，算法流程如圖1所示。
1.1資源分配模型NNIA是一種經(jīng)典的進(jìn)化多目標(biāo)優(yōu)化算法，在此算法的運(yùn)行過程中，只是采用少數(shù)的非支配個(gè)體進(jìn)行操作，考慮到本文采用的多目標(biāo)考試時(shí)間表的建模方式，在算法運(yùn)行過程中，當(dāng)出現(xiàn)非支配解數(shù)量不足的情況時(shí)，必然會(huì)對(duì)NNIA框架下的算法性能產(chǎn)生十分明顯的影響。顧本文在采用NNIA算法框架的基礎(chǔ)上，在個(gè)體克隆階段，設(shè)計(jì)了一種基于博弈論的資源分配模型，通過動(dòng)態(tài)控制優(yōu)勢(shì)個(gè)體的克隆數(shù)量手段，更加合理的分配計(jì)算資源。在資源分配模型中，根據(jù)非支配排序關(guān)系，待克隆的個(gè)體首先被劃分為不同的等級(jí)（R1,…,Rn）。其中，Ri代表了第i等級(jí)的個(gè)體的數(shù)量。通常情況下，R1中的個(gè)體優(yōu)于其他個(gè)體。根據(jù)R1個(gè)體在所有待克隆個(gè)體中所占的比例r，將資源分配模型分解為早期模型、中期模型和后期模型。算法在運(yùn)行過程中，根據(jù)不同的模型，采用相應(yīng)的克隆策略。早期模型(r≤1/3)：在此階段只有很少的優(yōu)秀個(gè)體（R1個(gè)體）。根據(jù)博弈論的相關(guān)概念，需要抑制R2中個(gè)體的克隆數(shù)量，以保證其無法影響到R1中的個(gè)體。如公式(5)所示，其中Si表示原始的克隆尺寸，Mi表示資源分配模型計(jì)算過后，克隆后第i級(jí)別的克隆規(guī)模。
1.2基于超啟發(fā)方法的種群初始化許多學(xué)者的研究及仿真實(shí)驗(yàn)表明[1]，基于圖著色的超啟發(fā)方法十分適合處理單目標(biāo)考試時(shí)間表問題。采用超啟發(fā)方法擁有更大幾率快速找到可行解或潛在的優(yōu)勢(shì)個(gè)體。針對(duì)本文所面對(duì)的多目標(biāo)考試時(shí)間表問題，若能快速得到可行解或潛在的優(yōu)勢(shì)個(gè)體，在固定的算法迭代次數(shù)的條件下，則更加有利于得到更好的結(jié)果。因此，本文采用基于圖著色的超啟發(fā)方法生成初始種群。其中，初始種群是由一定數(shù)量的初始解(時(shí)間表)構(gòu)成的。首先，隨機(jī)產(chǎn)生由不同圖啟發(fā)算法構(gòu)成的啟發(fā)式鏈表，根據(jù)啟發(fā)式鏈表，產(chǎn)生初始解（考試時(shí)間表）。在產(chǎn)生初始解的過程中，每當(dāng)產(chǎn)生一個(gè)新的考試時(shí)間表示，通過這些不同的啟發(fā)式算法，可以產(chǎn)生一個(gè)考試科目安排順序，在不違反硬約束的條件下，根據(jù)考試安排順序，每門考試隨機(jī)安排在時(shí)間段中。具體的超啟發(fā)方法請(qǐng)參看文獻(xiàn)[1]。另外，本文采用二進(jìn)制編碼方式，其中每一列代表一個(gè)時(shí)間段，每一行代表一門考試，數(shù)字1表示在此時(shí)段安排某門考試，0表示在此時(shí)段未安排考試。
2仿真實(shí)驗(yàn)
本文選取Carter標(biāo)準(zhǔn)數(shù)據(jù)集[14]進(jìn)行測(cè)試。近幾十年來，幾乎所有關(guān)于考試時(shí)間表算法的研究都采用此數(shù)據(jù)集進(jìn)行性能測(cè)試，但此數(shù)據(jù)仍是開放數(shù)據(jù)，理論最優(yōu)解仍然未知。本文選取了該數(shù)據(jù)集中的十個(gè)具有代表性的數(shù)據(jù)，對(duì)提出的算法進(jìn)行仿真實(shí)驗(yàn)。以下仿真均為10次獨(dú)立運(yùn)行實(shí)驗(yàn)，運(yùn)行環(huán)境為2.8GHzCorePersonalComputer。具體參數(shù)如表1所示：針對(duì)10個(gè)測(cè)試數(shù)據(jù)，算法經(jīng)過10次獨(dú)立運(yùn)行，隨機(jī)選取一組解集，其pareto前沿面如圖2所示。少數(shù)幾個(gè)測(cè)試集（car91,car92,ear83等）在個(gè)別區(qū)域沒有找到非支配解。除上述測(cè)試集，大部分的測(cè)試集基本上能夠完整勾勒出2目標(biāo)優(yōu)化的pareto前沿面，并且對(duì)于每一組數(shù)據(jù)的pareto解都可以較為均勻的分布在其前沿面上。表2記錄了現(xiàn)今這些測(cè)試集的最好的運(yùn)行結(jié)果，需要注意的是，此結(jié)果均為在單目標(biāo)優(yōu)化(固定時(shí)間表長(zhǎng)度，只優(yōu)化考試間沖突關(guān)系)的環(huán)境下產(chǎn)生的。我們選取的運(yùn)行結(jié)果則是根據(jù)單目標(biāo)環(huán)境下的時(shí)間表長(zhǎng)度(P),在我們的多目標(biāo)算法運(yùn)行的結(jié)果中，選取的對(duì)應(yīng)結(jié)果。從對(duì)比結(jié)果來看，除數(shù)據(jù)集york83，我們的算法均能找到與單目標(biāo)模型中相同的時(shí)間段。從具體結(jié)果上來說，我們的結(jié)果的確與其他幾種最優(yōu)秀的單目標(biāo)優(yōu)化結(jié)果尚存一定差距，但差距并不明顯。重要的是采用本文提出的多目標(biāo)優(yōu)化算法，經(jīng)過一次運(yùn)行就可提供不同時(shí)間段的多個(gè)解，運(yùn)行效率是單目標(biāo)優(yōu)化的數(shù)十倍。上述結(jié)果表明，將考試時(shí)間表問題按照多目標(biāo)優(yōu)化問題建模有效且可以極大地提高計(jì)算效率。本文在NNIA框架下，在克隆階段采用了資源分配模型，此模型對(duì)于整個(gè)算法的影響可由下列實(shí)驗(yàn)得出結(jié)論。圖3為十組測(cè)試數(shù)據(jù)分別來自為采用資源分配模型的RA-NNIA和未采用此模型的原始NNIA進(jìn)行十次獨(dú)立運(yùn)行后，非支配解個(gè)數(shù)的統(tǒng)計(jì)盒圖。針對(duì)每一個(gè)測(cè)試數(shù)據(jù)，左邊采用RA-NNIA，右邊采用NNIA。我們可以明顯看出，采用資源分配模型的RA-NNIA的非支配個(gè)體數(shù)量明顯的好于未采用的NNIA。圖4為十組測(cè)試數(shù)據(jù)，分別采用RA-NNIA和NNIA，經(jīng)過十次獨(dú)立實(shí)驗(yàn)后，spacing指標(biāo)的統(tǒng)計(jì)盒圖對(duì)比。由圖可知，除少數(shù)幾組數(shù)據(jù)(car92,ear83)，采用RA-NNIA算法的均勻性指標(biāo)都要優(yōu)于采用NNIA的運(yùn)行結(jié)果。根據(jù)以上兩組實(shí)驗(yàn)結(jié)果分析可知，對(duì)于如此建模的多目標(biāo)考試時(shí)間表問題，非支配解的數(shù)量本身就十分的有限，傳統(tǒng)的NNIA僅采用當(dāng)前的非支配個(gè)體進(jìn)行克隆，而后進(jìn)行進(jìn)化操作，導(dǎo)致種群的多樣性難以保持，很有可能進(jìn)一步導(dǎo)致最終的非支配解數(shù)目不足，而RA-NNIA克隆階段，在非支配個(gè)體數(shù)量不足時(shí)，還會(huì)利用少部分較好的支配個(gè)體，共同進(jìn)行克隆操作，并且，資源分配模型還會(huì)根據(jù)當(dāng)前非支配個(gè)體所占的比例，動(dòng)態(tài)控制每一部分個(gè)體的克隆比例，此種策略在一定的情況下可以很好地改善傳統(tǒng)NNIA在這方面上的不足。所以，采用資源分配模型的NNIA是有利于非支配個(gè)體的產(chǎn)生與保留，有利于算法的多樣性的保持，此策略十分適合用于求解多目標(biāo)考試時(shí)間表問題的多目標(biāo)進(jìn)化算法。
