引論：我們?yōu)槟砹?3篇多目標(biāo)優(yōu)化概念范文，供您借鑒以豐富您的創(chuàng)作。它們是您寫作時(shí)的寶貴資源，期望它們能夠激發(fā)您的創(chuàng)作靈感，讓您的文章更具深度。

篇1

Evolutiaon Algorithm for Multi-Objective Optimization Problems

MO Hai-fang

(Computer and Experiment Center, South-Center University For Nationality, Wuhan 430074, China)

Abstract: Evolut ionary algorithm is especially suitable to solve multi-object ive optimization problems. The basic principle of multi-object ive evolution algorithm is introduced, and the Pareto optimial-based evolutionary approach is discussed.

Key words: multi-objective optimization; Pareto optimal solutions; evolution algorithm

1 引言

多目標(biāo)問(wèn)題的求解是近年來(lái)優(yōu)化計(jì)算的一個(gè)熱點(diǎn)問(wèn)題。與單目標(biāo)問(wèn)題不同，多目標(biāo)問(wèn)題的解不是單一的解，而是一組相互之間不可比較，甚至是相互沖突的解。因此求解多目標(biāo)問(wèn)題比求解單目標(biāo)問(wèn)題要困難得多。

求解多目標(biāo)問(wèn)題的傳統(tǒng)方法主要有加權(quán)法、層次優(yōu)化法、目標(biāo)規(guī)劃法等，這些方法的主要思想是對(duì)多目標(biāo)進(jìn)行權(quán)重分配，轉(zhuǎn)化為單目標(biāo)問(wèn)題，然后運(yùn)用單目標(biāo)優(yōu)化技術(shù)進(jìn)行求解。這類方法需要較多的先驗(yàn)知識(shí)，而且計(jì)算效率低。

演化算法（EA）是一類模擬自然界生物進(jìn)化的全局性概率優(yōu)化搜索方法，因?yàn)槠鋬?nèi)在的并行性，特別適合于求解復(fù)雜的多目標(biāo)優(yōu)化問(wèn)題。

基于向量評(píng)估的VEGA算法是Schaffer于1985年提出的，這是第一個(gè)多目標(biāo)演化算法。該算法的主要思想是在每一代中根據(jù)各目標(biāo)函數(shù)，用適應(yīng)度比例法產(chǎn)生一定數(shù)目的子種群，然后把它們合并成新的一代，繼續(xù)執(zhí)行交叉和變異等遺傳操作。VEGA算法在本質(zhì)上仍然是加權(quán)和的方法。隨后有許多成功的多目標(biāo)演化算法被提出。1993年，F(xiàn)onseca和Fleming提出MOGA算法，Horn和Nafploitis提出NPGA算法，Srinivas和Deb提出NSGA算法。其中MOGA最著名，這是基于Pareto最優(yōu)概念的算法，它統(tǒng)計(jì)出群體中優(yōu)于某個(gè)體的個(gè)體數(shù)量，并依此計(jì)算該個(gè)體的適應(yīng)值。同時(shí)采用自適應(yīng)的小生境技術(shù)和受限雜交技術(shù)來(lái)提高種群多樣性。1999年，Zitzler和Thiele提出了SPEA算法，該算法采用精英保留策略來(lái)提高多目標(biāo)進(jìn)化算法的性能。這些算法都能成功求解多目標(biāo)問(wèn)題，它們的實(shí)現(xiàn)基于以下基本的策略：Pareto最優(yōu)策略和保持種群多樣性的策略。

2 多目標(biāo)優(yōu)化問(wèn)題中的一些概念

一般地，一個(gè)多目標(biāo)優(yōu)化問(wèn)題可以歸結(jié)為多個(gè)目標(biāo)的極小化模型：

定義1：多目標(biāo)優(yōu)化問(wèn)題

v-min f(x)=[(f1(x), f2(x), …,fm(x))]T

subject to x ∈X

X?哿Rm

其中的v-min表示向量極小化，即向量目標(biāo)函數(shù)f(x)=[(f1(x),f2(x),…,fm(x))]T中的各子目標(biāo)函數(shù)都盡可能地極小化。

然而在很多情況下，多目標(biāo)優(yōu)化問(wèn)題中的各個(gè)子目標(biāo)是相互沖突的，一個(gè)子目標(biāo)性能的改善可能會(huì)引起另一個(gè)子目標(biāo)性能的降低，也就是說(shuō)，一個(gè)能夠同時(shí)使所有目標(biāo)函數(shù)達(dá)到最優(yōu)的解很可能是不存在的，只能在它們之間進(jìn)行協(xié)調(diào)和折衷處理，使各個(gè)子目標(biāo)函數(shù)都盡可能地達(dá)到最優(yōu)。為了對(duì)多目標(biāo)問(wèn)題的解進(jìn)行比較, 先給出Pareto最優(yōu)解的定義。

定義2：Pareto占優(yōu)

任何兩個(gè)決策向量a∈X和b∈X，如果f(a)

定義3：Pareto最優(yōu)解

如果不存在y∈X，使fi(y)≤fi(x), i=1,2,…,m，且至少有一個(gè)嚴(yán)格不等式成立，則稱x∈X是多目標(biāo)優(yōu)化問(wèn)題的Pareto最優(yōu)解，或稱為非劣解。

通常的多目標(biāo)問(wèn)題的Pareto最優(yōu)解都有很多，把Pareto最優(yōu)解的集合稱為Pareto前沿。由定義3可知，Pareto最優(yōu)解集中的解是彼此不可比較的，解集中的解數(shù)量越多，分布越廣泛, 決策者的選擇空間越大，越能對(duì)實(shí)際多目標(biāo)問(wèn)題進(jìn)行合理求解。

3 多目標(biāo)演化算法

多目標(biāo)演化算法的大致流程如下：

1) 初始化：產(chǎn)生初始群體P(0)；

2) 計(jì)算個(gè)體的適應(yīng)值；

3) 在群體P(t)中執(zhí)行選擇、交叉和變異等進(jìn)化操作產(chǎn)生下一代種群P(t+1)；

4) 若滿足結(jié)束條件則將退出，否則轉(zhuǎn)到步驟3)。

3.1 基于Pareto非劣概念的排名

用Pareto非劣解的概念計(jì)算個(gè)體適應(yīng)值的方法首先是由Goldberg于1989年提出的。他提出排序方法（Ranking）和基于序的適應(yīng)度函數(shù)形式。先將多目標(biāo)函數(shù)值組成一個(gè)向量代表一個(gè)個(gè)體，假設(shè)個(gè)體xi在t代群體中有n個(gè)個(gè)體優(yōu)于它，則它在群體中的序?yàn)椋簉ank(xi)=1+n。如圖1所示，當(dāng)前群體中所有非劣最優(yōu)解的序都為1。

圖1 群體中個(gè)體的Pareto序

排序僅僅體現(xiàn)了各個(gè)個(gè)體之間的優(yōu)越次序，沒(méi)有體現(xiàn)各個(gè)個(gè)體的分散程度，所以容易導(dǎo)致最終得到很多個(gè)相似的Pareto最優(yōu)解，而難于獲得分布均勻的Pareto最優(yōu)解。

3.2 群體多樣性

為了逼近Pareto最優(yōu)解集，就要得到多個(gè)不同的解，因此，群體多樣性極其重要。為了提高群體多樣性，多目標(biāo)演化算法已經(jīng)提出了多種小生境與共享技術(shù)，以求獲得均勻分布得Pareto最優(yōu)解集。已有的保持群體多樣性的方法有：適應(yīng)值共享、受限雜交、孤島模型、重新初始化、擁擠機(jī)制等。比較適合多目標(biāo)演化算法的是適應(yīng)值共享。

適應(yīng)值共享的思路是：同一個(gè)小生境中（Niche）的個(gè)體必須共享資源。一個(gè)個(gè)體有越多的鄰居（neighborhood），那么該個(gè)體的適應(yīng)值越小。

兩個(gè)個(gè)體之間的空間距離小于某個(gè)伐值（Niche radius）時(shí)，就成為鄰居（neighborhood），一個(gè)個(gè)體的鄰居數(shù)量稱為小生境數(shù)（Niche Count）。某個(gè)個(gè)體的適應(yīng)值除以它的小生境數(shù)就得到它調(diào)整后的適應(yīng)值，從而使有多個(gè)相似的個(gè)體降低了適應(yīng)值，減少了它們遺傳到下一代群體的機(jī)會(huì)。

3.3 精英策略

SPEA算法采用精英保留策略來(lái)提高多目標(biāo)進(jìn)化算法的性能。精英是指一代群體中適應(yīng)值較高的個(gè)體。在多目標(biāo)演化算法中，在每一代群體中都有多個(gè)精英，把這些精英保存到一個(gè)精英集合中，然后按照概率從這個(gè)集合中再選擇優(yōu)秀個(gè)體進(jìn)入下一代群體，從而加快了算法的收斂速度，提高算法的性能。

4 測(cè)試函數(shù)

minimize T(x)=(f1(x1),f2(x2)

subject to f2(x)=g(x2,…, xm)h(f1(x1),g(x2,…,xm))

where x=(x1,x2,…,xm)

測(cè)試函數(shù)1：

f1(x1)=x1

(m=30并且xi∈[0,1]。當(dāng)達(dá)到Pareto前沿時(shí)g(x)=1)

5 結(jié)束語(yǔ)

多目標(biāo)演化算法具有廣泛的應(yīng)用前景，目前已經(jīng)被成功應(yīng)用到自動(dòng)控制、機(jī)械設(shè)計(jì)、航空航天、網(wǎng)絡(luò)通信、作業(yè)調(diào)度、圖像處理、生命科學(xué)等多個(gè)領(lǐng)域。隨著多目標(biāo)演化算法在理論上的深入探索，必將在更多領(lǐng)域得到應(yīng)用。

多目標(biāo)演化算法的研究在近年來(lái)取得了許多成果，進(jìn)一步值得研究的問(wèn)題包括：加強(qiáng)多目標(biāo)演化算法的基礎(chǔ)理論研究，從理論上證明算法的收斂性，設(shè)計(jì)能反映多目標(biāo)演化算法基本特征的測(cè)試函數(shù)；對(duì)于高維多目標(biāo)優(yōu)化問(wèn)題，研究新的非基于Pareto 最優(yōu)概念的群體排序方法；結(jié)合領(lǐng)域知識(shí)，設(shè)計(jì)專門的多目標(biāo)演化算法。

參考文獻(xiàn)：

[1] 謝濤, 陳火旺, 康立山. 多目標(biāo)優(yōu)化的演化算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2003,26(8):997-1007.

[2] 馬清亮, 胡昌華. 多目標(biāo)進(jìn)化算法及其在控制領(lǐng)域中的應(yīng)用綜述[J].控制與決策, 2006,21(5):481-486.

[3] 祁榮賓, 錢鋒, 杜文莉, 等. 基于精英選擇和個(gè)體遷移的多目標(biāo)遺傳算法[J]. 控制與決策, 2007,22(2):164-168.

篇2

作者簡(jiǎn)介：馬春連（1988-），男，安徽理工大學(xué)理學(xué)院碩士研究生，研究方向?yàn)橹悄苡?jì)算；許峰（1963-），男，安徽理工大學(xué)理學(xué)院教授，研究方向?yàn)椴ㄗV學(xué)和智能計(jì)算。

0引言

在科學(xué)研究和工程應(yīng)用中，許多決策問(wèn)題具有多目標(biāo)的特點(diǎn)和性質(zhì)，它們需要同時(shí)滿足幾個(gè)相互沖突的不同目標(biāo)，即無(wú)法使各個(gè)目標(biāo)同時(shí)達(dá)到最優(yōu)，這類問(wèn)題稱之為多目標(biāo)優(yōu)化問(wèn)題（Multi-objective Optimization Problem， MOP）。多目標(biāo)優(yōu)化問(wèn)題存在一個(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年代以來(lái)，人們已提出多種多目標(biāo)進(jìn)化算法，比如Srinivas的NSGA，Zitzler的SPEA，Knowles的PAES以及Deb的NSGA-Ⅱ等。

近年來(lái)，一些新的進(jìn)化算法被用來(lái)求解多目標(biāo)優(yōu)化問(wèn)題，如蟻群算法、粒子群算法、免疫算法、分布估計(jì)算法等。

上世紀(jì)90年代末，人工免疫算法開始興起，其思想源于生物的免疫系統(tǒng)，它借鑒了免疫系統(tǒng)的功能、原理和模型并用于進(jìn)行尋優(yōu)搜索。由于現(xiàn)在還不能充分認(rèn)識(shí)免疫機(jī)理，所以有關(guān)免疫算法的研究基本集中在其它算法。我們用免疫原理來(lái)改進(jìn)并構(gòu)成新的算法，比如免疫神經(jīng)網(wǎng)絡(luò)、免疫遺傳算法等。人工免疫系統(tǒng)算法的自身研究成果并不多，主要有基于克隆選擇原理的克隆選擇算法和基于陰性選擇原理的陰性選擇算法等。

篇3

人類通過(guò)了社會(huì)自然的漫長(zhǎng)的考驗(yàn)最終開始進(jìn)化，于是在解決生活中復(fù)雜問(wèn)題的的同時(shí)，合理對(duì)問(wèn)題進(jìn)行優(yōu)化安排成為了人們的首要研究問(wèn)題。于是，各種各樣的算法就產(chǎn)生于求解問(wèn)題的方法。進(jìn)化算法中包含了重要的差分進(jìn)化算法，這是一種智能型的優(yōu)化方法，特點(diǎn)在于可調(diào)節(jié)參數(shù)不多、內(nèi)容簡(jiǎn)單、持續(xù)性強(qiáng)、結(jié)構(gòu)單一。在日常生活中多目標(biāo)優(yōu)化對(duì)人們發(fā)展具有相當(dāng)重要的意義。對(duì)人們生活的影響方面涵括了如下表1所示。

表1 多目標(biāo)優(yōu)的發(fā)展

二、差分進(jìn)化

（一）差分進(jìn)化算法構(gòu)理

差分進(jìn)化法是新興的一種計(jì)算的算法，它最基本的特點(diǎn)就是擁有集體共享的特點(diǎn)，可以這么說(shuō)，差分進(jìn)化法可以在自然種群的個(gè)體通過(guò)競(jìng)爭(zhēng)與合作的關(guān)系來(lái)實(shí)現(xiàn)對(duì)復(fù)雜問(wèn)題的優(yōu)化以及提供必要的解決方法。這種算法與遺傳算法的最大一個(gè)區(qū)別就在于他們對(duì)變異的操作不同之上，例如，差分進(jìn)化算法中的變異操作屬于變量中向量的一種，是在個(gè)體的染色體差異之間進(jìn)行的。算法的實(shí)現(xiàn)是建立在兩個(gè)正在變異的個(gè)體之間的染色體差異之上的。接著，在選擇變異個(gè)體之前，對(duì)另外一個(gè)隨機(jī)抽取的目標(biāo)進(jìn)行整合，提取必要的參數(shù)的數(shù)據(jù)，對(duì)合適的目標(biāo)開始研究，繼續(xù)產(chǎn)生一個(gè)新的個(gè)體進(jìn)行下一個(gè)類似的實(shí)驗(yàn)。

（二）差分進(jìn)化算法模型流程

從差分進(jìn)化算法的基本數(shù)據(jù)結(jié)構(gòu)與方法來(lái)看，差分進(jìn)化算法已經(jīng)廣泛開始應(yīng)用于自動(dòng)化控制、規(guī)劃、設(shè)置、組合、優(yōu)化、機(jī)器人、人工生命等重要的領(lǐng)域當(dāng)中去。對(duì)于差分進(jìn)化算法模型流程可由如下圖1所示

三、多目標(biāo)優(yōu)化

（一）多目標(biāo)優(yōu)化的研究現(xiàn)狀

多目標(biāo)進(jìn)化算法是為了解決現(xiàn)實(shí)生活中存在的難以用單一的目標(biāo)來(lái)解決的難題。畢竟在生活瑣事中總能遇到不同的多目標(biāo)優(yōu)化問(wèn)題，放任不理之后，久而久之就會(huì)越來(lái)越難處理這些問(wèn)題。于是為了找到新穎簡(jiǎn)便的法子，會(huì)讓學(xué)術(shù)家們花很多的精力。在歷史當(dāng)中，多目標(biāo)最優(yōu)決策的方法最先是由英國(guó)的一名數(shù)學(xué)家Pate指出，隨后他圈概出了最優(yōu)解的概念。在那個(gè)時(shí)候確實(shí)有很好的影響目的。距現(xiàn)在一百多年前，在尋求多目標(biāo)優(yōu)化的問(wèn)題之上學(xué)術(shù)家們發(fā)表了無(wú)數(shù)不完美的優(yōu)化方法，傳統(tǒng)上有加權(quán)和法、目標(biāo)規(guī)劃法的方法。所以一百多年前進(jìn)化算法就已經(jīng)開始了興起。為此，學(xué)術(shù)家們貢獻(xiàn)了大量的精力去進(jìn)行計(jì)算數(shù)值來(lái)尋求解決進(jìn)化算法的難題。

（二）多目標(biāo)優(yōu)化方法

在上一世紀(jì)的三四十年代，對(duì)多目標(biāo)問(wèn)題的優(yōu)化問(wèn)題探究就引起了普遍的科學(xué)家們的重視。發(fā)展至今，優(yōu)化的方法就從很多不同的的角度對(duì)問(wèn)題進(jìn)行了歸納和總結(jié)，并且提出了解決的k法，順帶著給出了多目標(biāo)問(wèn)題最優(yōu)解的原始概念。在那個(gè)世紀(jì)，學(xué)術(shù)科學(xué)家們會(huì)把注意力放在簡(jiǎn)單的單一優(yōu)化方法中，用傳統(tǒng)的辦法對(duì)問(wèn)題進(jìn)行簡(jiǎn)單的優(yōu)化。于是在那時(shí)候就提出了很多關(guān)于求解多目標(biāo)優(yōu)化問(wèn)題的方法，例如，目的計(jì)劃法、平均和法。從那時(shí)候開始，更簡(jiǎn)便的進(jìn)化算法開始在學(xué)術(shù)家們當(dāng)中以迅雷不及掩耳之勢(shì)發(fā)展開來(lái)，至此，科學(xué)家們又將自己的主要興趣放在求解多優(yōu)化的問(wèn)題發(fā)展中去。下面多目標(biāo)優(yōu)化方法如圖2所示。

四、結(jié)語(yǔ)

在現(xiàn)代生活中，技術(shù)人員對(duì)于實(shí)現(xiàn)人工智能已經(jīng)不是難題，把人工智能與運(yùn)籌學(xué)以及控制理論等方面的方法進(jìn)行融合，將靜態(tài)與動(dòng)態(tài)的優(yōu)化等方法進(jìn)行結(jié)合。差分進(jìn)化算法的缺點(diǎn)類似于遺傳學(xué)的算法，都有過(guò)早對(duì)數(shù)據(jù)進(jìn)行收斂的過(guò)失。所以對(duì)差分進(jìn)化算法的優(yōu)化，讓算法深入到人們遇上的工作難題當(dāng)中去，是大家探究這個(gè)算法的意義所在。通常來(lái)說(shuō)，多目標(biāo)之間存在著矛盾的關(guān)系，在解決有多目標(biāo)的問(wèn)題之上，算法通常存在傳統(tǒng)方法中的計(jì)算難，與難操作的問(wèn)題。在多優(yōu)化目標(biāo)的問(wèn)題當(dāng)中，如果運(yùn)用到了工作當(dāng)?shù)母鞔箢I(lǐng)域當(dāng)中去，可以在更廣的范圍內(nèi)運(yùn)用到算法的結(jié)構(gòu)。根據(jù)已出意義的算法能大幅度提高人們的生活質(zhì)量。在我們生活的軌跡當(dāng)中，難免碰“瓷”，有時(shí)候會(huì)很難得到想要的解決方法，于是需要解決的越來(lái)越多，這更突出了多優(yōu)化目標(biāo)實(shí)現(xiàn)對(duì)人們生活有很大的意義。

參考文獻(xiàn)：

篇4

1引言

大多數(shù)多目標(biāo)優(yōu)化問(wèn)題，每個(gè)目標(biāo)函數(shù)之間可能是競(jìng)爭(zhēng)的關(guān)系，優(yōu)化某一個(gè)函數(shù)的同時(shí)，往往以犧牲另一個(gè)優(yōu)化目標(biāo)為代價(jià)，如果將多目標(biāo)轉(zhuǎn)化為單目標(biāo)函數(shù)優(yōu)化時(shí)，各優(yōu)化目標(biāo)加權(quán)值的分配帶有很大的主觀性，必然造成優(yōu)化結(jié)果的單一性，沒(méi)有考慮全局優(yōu)化。而如果將多目標(biāo)函數(shù)利用評(píng)價(jià)函數(shù)法轉(zhuǎn)化為單目標(biāo)函數(shù)求解，得到的僅僅是一個(gè)有效解，所以我們可以考慮直接采用多目標(biāo)函數(shù)的優(yōu)化方法對(duì)多目標(biāo)進(jìn)行優(yōu)化[1-2]。

2多目標(biāo)優(yōu)化的發(fā)展現(xiàn)狀

在多目標(biāo)優(yōu)化問(wèn)題中，各分目標(biāo)函數(shù)的最優(yōu)解往往是互相獨(dú)立的，很難同時(shí)實(shí)現(xiàn)最優(yōu)。在分目標(biāo)函數(shù)之間甚至還會(huì)出現(xiàn)完全對(duì)立的情況，即某一個(gè)分目標(biāo)函數(shù)的最優(yōu)解卻是另一個(gè)分目標(biāo)函數(shù)的劣解。求解多目標(biāo)優(yōu)化問(wèn)題的關(guān)鍵，是要在決策空間中尋求一個(gè)最優(yōu)解的集合，需要在各分目標(biāo)函數(shù)的最優(yōu)解之間進(jìn)行協(xié)調(diào)和權(quán)衡，以使各分目標(biāo)函數(shù)盡可能達(dá)到近似最優(yōu)。多目標(biāo)優(yōu)化問(wèn)題不存在唯一的全局最優(yōu)解，而是要尋找一個(gè)最終解。得到最終解需要通過(guò)各種算法來(lái)實(shí)現(xiàn)，如進(jìn)化算法、模擬退火算法、蟻群算法、粒子群算法和遺傳算法等[3-4]。由于各種算法存在應(yīng)用領(lǐng)域的差異和自身缺陷，人們也提出了一些改進(jìn)算法和組合算法。

2.1進(jìn)化算法

進(jìn)化算法 （Evolutionary Algorithms，EA）是一種仿生優(yōu)化算法，主要包括遺傳算法、進(jìn)化規(guī)劃、遺傳規(guī)劃和進(jìn)化策略等。根據(jù)達(dá)爾文的“優(yōu)勝劣汰、適者生存”的進(jìn)化原理及盂德爾等人的遺傳變異理論，在優(yōu)化過(guò)程中模擬自然界的生物進(jìn)化過(guò)程與機(jī)制，求解優(yōu)化與搜索問(wèn)題。進(jìn)化算法具有自組織、自適應(yīng)、人工智能、高度的非線性、可并行性等優(yōu)點(diǎn)[5]。

進(jìn)化算法在求解多目標(biāo)優(yōu)化問(wèn)題上優(yōu)勢(shì)在于：一是搜索的多向性和全局性，通過(guò)重組操作充分利用解之間的相似性，能夠在一次運(yùn)行中獲取多個(gè)Pareto最優(yōu)解，構(gòu)成近似問(wèn)題的Pareto最優(yōu)解集；二是可以處理所有類型的目標(biāo)函數(shù)和約束。三是采用基于種群的方式組織搜索、遺傳操作和優(yōu)勝劣汰的選擇機(jī)制，不受其搜索空間條件的限制。

雖然基于Pareto最優(yōu)解的多目標(biāo)進(jìn)化算法可以得到較好分布的最優(yōu)解集，但如何保證算法具有良好的收斂性仍是一個(gè)熱點(diǎn)問(wèn)題。

2.2模擬退火算法

模擬退火（Simulated Annealing，SA）算法是根據(jù)物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性，基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法。SA在初始溫度下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。SA具有以下優(yōu)點(diǎn)：通用性強(qiáng)，對(duì)問(wèn)題信息依賴較少，可有效避免陷入局部極小并最終趨于全局最優(yōu)。因此在諸多工程和學(xué)術(shù)領(lǐng)域得到了研究與應(yīng)用[6-7]。遺憾的是它在多目標(biāo)優(yōu)化領(lǐng)域的研究與應(yīng)用尚少。

2.3蟻群算法

蟻群算法（Ant Colony Optimization， ACO）是一種用來(lái)在圖中尋找優(yōu)化路徑的正反口的新型模擬進(jìn)化算法。。蟻群算法具有并行性、分布性、正反饋性、自組織性、較強(qiáng)的魯棒性和全局搜索能力等特點(diǎn)。目前運(yùn)用這種方法已成功地解決了旅行商（TSP）問(wèn)題、Job-shop調(diào)度問(wèn)題、二次指派問(wèn)題等組合優(yōu)化問(wèn)題。

由于蟻群算法需要的參數(shù)數(shù)目少，設(shè)置簡(jiǎn)單，在求解多目標(biāo)優(yōu)化問(wèn)題時(shí)存在一些困難。首先，多目標(biāo)函數(shù)優(yōu)化問(wèn)題是在連續(xù)空間中進(jìn)行尋優(yōu)，解空間以區(qū)域表示，螞蟻在每一階段可選的路徑不再是有限的，螞蟻在信息索的駐留和基于信息素的尋優(yōu)上存在困難。文獻(xiàn)[8]提出先使用遺傳算法對(duì)解空間進(jìn)行全局搜索，再運(yùn)用蟻群算法對(duì)得到的結(jié)果進(jìn)行局部?jī)?yōu)化；文獻(xiàn)[9]修改了螞蟻信息素的留存方式和行走規(guī)則，運(yùn)用信息素交流和直接通訊兩種方式來(lái)指導(dǎo)螞蟻尋優(yōu)；文獻(xiàn)[10]將搜索空間劃分為若干子域，根據(jù)信息量確定解所在的子域，在該子域內(nèi)尋找解，也取得了滿意的結(jié)果。

其次，螞蟻算法需要較長(zhǎng)的搜索時(shí)間、容易出現(xiàn)早熟停滯現(xiàn)象。文獻(xiàn)[11]提出了具有免疫能力的螞蟻算法和蟻群遺傳算法，提高算法的尋優(yōu)能力和尋優(yōu)效率。

最后，多目標(biāo)優(yōu)化問(wèn)題由于解的多樣性，不僅要求所得的解能夠收斂到Pareto前沿，而且要有效地保持群體的多樣性。螞蟻之間的這種信息素交流方式，會(huì)使所求得的解集中在解空間的某一區(qū)域內(nèi)，不利于群體多樣性的保持。

2.4粒子群算法

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是在1995年由美國(guó)社會(huì)心理學(xué)家Kennedy和電氣工程師Eberhart共同提出的，源于對(duì)鳥群覓食過(guò)程中的遷徙和聚集的模擬。它收斂速度快、易于實(shí)現(xiàn)且僅有少量參數(shù)需要調(diào)整，目前已經(jīng)被廣泛應(yīng)用于目標(biāo)函數(shù)優(yōu)化、動(dòng)態(tài)環(huán)境優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練等許多領(lǐng)域。

由于直接用粒子群算法處理多目標(biāo)優(yōu)化問(wèn)題，很容易收斂于非劣最優(yōu)域的局部區(qū)域，以及如何保證算法的分布性等問(wèn)題，Coello等人提出了基于Pareto的多目標(biāo)粒子群算法（MOPS0），強(qiáng)調(diào)了粒子和種群之間作用的重要性[12]。

多目標(biāo)粒子群優(yōu)化算法作為一種新興的多目標(biāo)優(yōu)化算法具有以下優(yōu)點(diǎn)：（1）在編碼方式上PSO算法比較簡(jiǎn)單，可以直接根據(jù)被優(yōu)化問(wèn)題進(jìn)行實(shí)數(shù)編碼；（2）對(duì)種群的初始化不敏感，可達(dá)到較快的收斂速度；（3）算法適用于絕大多數(shù)的多目標(biāo)優(yōu)化問(wèn)題；（4）優(yōu)化過(guò)程中，每個(gè)粒子通過(guò)自身經(jīng)驗(yàn)與群體經(jīng)驗(yàn)進(jìn)行更新，具有學(xué)習(xí)和記憶的功能；（5）該算法在收斂性、解的分布性以及計(jì)算效率方面具有很大改善。

2.5遺傳算法

遺傳算法（Genetic Algorithm，GA）是進(jìn)化算法的一種，是美國(guó)密執(zhí)安大學(xué)的John Holland教授于七十年代中期首先提出來(lái)的，從生物進(jìn)化的過(guò)程中得到靈感與啟迪，模擬人自然“物竟天擇，適者生存”的自然選擇的法則創(chuàng)立的。

與其他優(yōu)化算法相比，遺傳算法求解多目標(biāo)優(yōu)化問(wèn)題的主要優(yōu)點(diǎn)：一是保證算法的收斂性，即在目標(biāo)空間內(nèi)，所求得的Pareto最優(yōu)解集與實(shí)際Pareto盡可能的接近。二是多樣性的維護(hù)，即希望找到的Pareto最優(yōu)解集具有較好的分布特性（如均勻分布），且分布范圍盡可能的寬闊。三是具有很好的魯棒性，是一種高度并行、隨機(jī)、自適應(yīng)能力很強(qiáng)的智能搜索算法，因此特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜非線性問(wèn)題。四是新的遺傳算法引入精英概念，使進(jìn)化的每一代的Pareto最優(yōu)解總是直接保留到下一代的群體中，提高了Pareto最優(yōu)解的搜索效率。五是引入用戶的偏好信息，以交互的方式表達(dá)偏好，使用決策者的偏好信息來(lái)指導(dǎo)算法的搜索過(guò)程和范圍[13-14]。

3多目標(biāo)優(yōu)化研究的熱點(diǎn)問(wèn)題

多目標(biāo)優(yōu)化問(wèn)題中，各個(gè)目標(biāo)之間通過(guò)決策變量相互制約，對(duì)其中一個(gè)目標(biāo)優(yōu)化必須以其他目標(biāo)作為代價(jià)，而且各目標(biāo)的單位又往往不一致，因此很難客觀地評(píng)價(jià)多目標(biāo)問(wèn)題解的優(yōu)劣性。傳統(tǒng)優(yōu)化方法往往強(qiáng)調(diào)最優(yōu)化，在解決因多種復(fù)雜因素難以建模，或根本不存在傳統(tǒng)意義上的最優(yōu)解或獲得最優(yōu)解的代價(jià)太大的優(yōu)化問(wèn)題時(shí)。由此，采用滿意優(yōu)化方法解決這類問(wèn)題是較好的策略。滿意優(yōu)化本質(zhì)上是一個(gè)多目標(biāo)優(yōu)化方法，它摒棄了傳統(tǒng)的最優(yōu)概念，它將優(yōu)化問(wèn)題的約束和目標(biāo)融為一體，將性能指標(biāo)要求的滿意設(shè)計(jì)與參數(shù)優(yōu)化融為一體，強(qiáng)調(diào)的是“滿意”而不“最優(yōu)”。所以，近年來(lái)，滿意優(yōu)化也逐漸成為各領(lǐng)域關(guān)心的問(wèn)題。

4結(jié)束語(yǔ)

多目標(biāo)優(yōu)化問(wèn)題是近年來(lái)人們?cè)絹?lái)越需要面對(duì)和解決的問(wèn)題。除了以上單一優(yōu)化算法外，很多學(xué)者已經(jīng)在單一優(yōu)化算法的基礎(chǔ)上，結(jié)合多種優(yōu)化算法解決了一些多目標(biāo)優(yōu)化問(wèn)題，如NSGA-Ⅱ與MOPSP的結(jié)合算法[15]，模擬退火算法與遺傳算法的結(jié)合算法[16]。然而，由于各種多目標(biāo)優(yōu)化算法的不同特點(diǎn)和缺陷，如何使這些優(yōu)化算法能夠更好地?zé)o縫對(duì)接，對(duì)解決多目標(biāo)滿意優(yōu)化問(wèn)題具有非常重要的意義。

參考文獻(xiàn)

[1]玄光男，程潤(rùn)偉著.周根貴譯.遺傳算法與工程優(yōu)化，清華大學(xué)出版社，2004.

[2] Liu Zhen Yu .Multi-objective optimization design analysis of primary surface recuperator for microturbines[J].Applied Thermal Engineering 28（2008）：601～610.

[3]肖曉偉等.多目標(biāo)優(yōu)化問(wèn)題的研究概述.計(jì)算機(jī)應(yīng)用研究，2011（03）

[4] Kalyanmoy Deb，Amrit Pratap，T Meyarivan.A fast and elitist multi-objective genetic 2002.6（2）：182～197.algorithm： NSGA-II [J].IEEE Transactions on Evolutionary Computation.

[5]楊海清.進(jìn)化算法的改進(jìn)及其應(yīng)用研究.浙江工業(yè)大學(xué)碩士論文，2004.

[6]鄧俊等.基于神經(jīng)網(wǎng)絡(luò)和模擬退火算法的配煤智能優(yōu)化方法[J].冶金自動(dòng)化，2007（3）.

[7]韓強(qiáng).多目標(biāo)應(yīng)急設(shè)施選址問(wèn)題的模擬退火算法[J].計(jì)算機(jī)工程與應(yīng)用 ，2007（30）.

[8]陳峻等.蟻群算法求解連續(xù)空間優(yōu)化問(wèn)題的一種方法[J].軟件學(xué)報(bào) 2002，13（12）.

[9]Dorigo M，Gambardella L M. Ant colony system： a cooperative learning approach to the traveling salesman problem[J].IEEE Trans. Evolutionary Computation，1997，1（1）：53-56.

[10]張德勇，黃莎白.多目標(biāo)優(yōu)化問(wèn)題的蟻群算法研究[J].控制與決策 2005，20（2）

[11]毛寧.具有免疫能力的螞蟻算法研究（碩士學(xué)位論文） 河北工業(yè)大學(xué).2006

[12]張慧敏.改進(jìn)的粒子群計(jì)算智能算法及其多目標(biāo)優(yōu)化的應(yīng)用研究（碩士學(xué)位論文）.

杭州大學(xué).2005.

[13]李金娟.遺傳算法及應(yīng)用的研究[J].電腦與信息技術(shù)，2013（02）.

[14]洪朝飛等.面向機(jī)械設(shè)計(jì)的一種改進(jìn)的遺傳算法.太原科技大學(xué)學(xué)報(bào)，2013（02）.

篇5

在發(fā)電權(quán)的交易上，很多文章主要以買賣雙方報(bào)價(jià)為主，本文為體現(xiàn)發(fā)電調(diào)度的節(jié)能減排要求，將煤耗率和價(jià)格這兩個(gè)參數(shù)結(jié)合起來(lái)，提出了基于能耗和效益綜合最優(yōu)的多目標(biāo)交易模型，并使用Pareto最優(yōu)的方法來(lái)對(duì)多目標(biāo)進(jìn)行求解。

1 發(fā)電權(quán)交易模式

發(fā)電權(quán)是一種商品，發(fā)電權(quán)市場(chǎng)是雙邊交易市場(chǎng)，撮合交易是組織發(fā)電權(quán)交易的常見(jiàn)模式。

2 發(fā)電權(quán)交易成本

本文將交易成本分為兩部分，固定成本 和電力網(wǎng)損成本 。固定成本包括組織發(fā)電權(quán)的固定傭金，管理費(fèi)用，行政費(fèi)用等，電力網(wǎng)損成本是開展發(fā)電權(quán)交易前后整個(gè)網(wǎng)絡(luò)潮流變化所帶來(lái)的成本。

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)化問(wèn)題，關(guān)于多目標(biāo)最優(yōu)有很多種求解方法，本文使用Pareto最優(yōu)的方法來(lái)對(duì)多目標(biāo)進(jìn)行求解。

4.1 Pareto最優(yōu)的概念

一般地，多目標(biāo)優(yōu)化問(wèn)題有如下形式：

其中Ω表示所有可行解的集合， 表示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)交易問(wèn)題

本文使用Pareto最優(yōu)的方法、DPW-PSO算法對(duì)多目標(biāo)進(jìn)行求解，求解過(guò)程是先通過(guò)隨機(jī)算法大致得到（U，F(xiàn)）這個(gè)二維函數(shù)的Pareto前沿，然后在Pareto前沿上選出一些解和它們對(duì)應(yīng)的交易方案，這些交易方案在某種程度上來(lái)說(shuō)都是最佳的。

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è)解，這些解得到的交易方案在某種程度上來(lái)說(shuō)都是最佳的，電力公司可以根據(jù)交易結(jié)果對(duì)發(fā)電權(quán)進(jìn)行安全校核，每次交易的完成都以電網(wǎng)通過(guò)安全約束為標(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)：

篇6

近年來(lái)，多目標(biāo)優(yōu)化問(wèn)題的研究成果已廣泛應(yīng)用于自動(dòng)控制、生產(chǎn)調(diào)度、網(wǎng)絡(luò)交通、集成電路設(shè)計(jì)、化學(xué)工程和環(huán)境工程、數(shù)據(jù)庫(kù)和芯片設(shè)計(jì)、核能和機(jī)械設(shè)計(jì)等眾多領(lǐng)域。隨著研究問(wèn)題的復(fù)雜度越來(lái)越高，優(yōu)化目標(biāo)的個(gè)數(shù)也不僅僅局限于2到3個(gè)，有時(shí)往往會(huì)達(dá)到4個(gè)或者甚至更多[1]。一般意義上，當(dāng)多目標(biāo)優(yōu)化問(wèn)題的優(yōu)化目標(biāo)個(gè)數(shù)達(dá)到3個(gè)以上時(shí)，我們將此類多目標(biāo)優(yōu)化問(wèn)題稱為高維多目標(biāo)優(yōu)化問(wèn)題[2]（Many-Objective Optimization，簡(jiǎn)稱MAP）。

進(jìn)化算法作為一種基于種群的智能搜索方法，目前已經(jīng)能夠成功地求解具有2、3個(gè)目標(biāo)的多目標(biāo)優(yōu)化問(wèn)題。然而，當(dāng)遇到目標(biāo)數(shù)目增至4個(gè)或4個(gè)以上的高維多目標(biāo)優(yōu)化問(wèn)題時(shí)，基于Pareto支配排序的多目標(biāo)進(jìn)化算法在搜索能力、計(jì)算成本和可視化方面都遇到了很大的挑戰(zhàn)。因此，高維多目標(biāo)優(yōu)化問(wèn)題的進(jìn)化算法研究成為進(jìn)化算法領(lǐng)域的一個(gè)難點(diǎn)和熱點(diǎn)問(wèn)題。

由于高維多目標(biāo)優(yōu)化問(wèn)題的復(fù)雜性，目前對(duì)于此類問(wèn)題的算法研究尚處于起步階段，首先分析高維多目標(biāo)優(yōu)化問(wèn)題研究存在的困難，然后對(duì)當(dāng)前所提出的高維多目標(biāo)進(jìn)化算法進(jìn)行分類概述，接下來(lái)重點(diǎn)總結(jié)了可降維的高維多目標(biāo)優(yōu)化問(wèn)題的幾類目標(biāo)縮減進(jìn)化算法，最后給出了未來(lái)研究的方向。

1 高維多目標(biāo)優(yōu)化問(wèn)題的基本概念

定義1 （多目標(biāo)優(yōu)化問(wèn)題和高維多目標(biāo)優(yōu)化問(wèn)題）

通常，對(duì)于單目標(biāo)優(yōu)化問(wèn)題，其全局最優(yōu)解就是目標(biāo)函數(shù)達(dá)到最優(yōu)值的解，但是對(duì)于多目標(biāo)優(yōu)化問(wèn)題來(lái)說(shuō)，往往這些目標(biāo)f1（x），…fm（x）的最優(yōu)函數(shù)值之間會(huì)相互沖突，不能同時(shí)達(dá)到最優(yōu)值。這里，為了平衡多個(gè)相互沖突的目標(biāo)，采用Pareto最優(yōu)解來(lái)定義多目標(biāo)優(yōu)化問(wèn)題的最優(yōu)解。

定義2 （可行解與可行域）

多目標(biāo)優(yōu)化問(wèn)題通常有非常多或者無(wú)窮多個(gè)Pareto最優(yōu)解，但是要找到所有的Pareto最優(yōu)解往往是不太可能的，因此，希望找到盡可能多的Pareto最優(yōu)解以便為決策者提供更多的選擇。在利用進(jìn)化算法求解多目標(biāo)優(yōu)化問(wèn)題的過(guò)程中，進(jìn)化算法使用適應(yīng)度函數(shù)引導(dǎo)群體向Pareto最優(yōu)前沿收斂，在設(shè)計(jì)算法時(shí)需要考慮下面兩個(gè)方面：一是算法的收斂性，即希望算法的求解過(guò)程是一個(gè)不斷逼近Pareto最優(yōu)解集的過(guò)程；二是算法的分布性，即要求所求出的Pareto最優(yōu)解集中的非支配解盡可能均勻且寬廣的分布在目標(biāo)函數(shù)空間中。

2 高維多目標(biāo)優(yōu)化問(wèn)題研究難點(diǎn)

Hughes通過(guò)實(shí)驗(yàn)表明基于Pareto排序多目標(biāo)進(jìn)化算法（如NSGAII，SPEA2等） 在具有較少目標(biāo)（2個(gè)或3個(gè)）時(shí)非常有效，但是，隨著多目標(biāo)優(yōu)化問(wèn)題目標(biāo)數(shù)目的不斷增多，目前經(jīng)典的求解一般多目標(biāo)優(yōu)化問(wèn)題的多目標(biāo)進(jìn)化算法的搜索性能將大大下降，從而導(dǎo)致求出的近似Pareto最優(yōu)解集的收斂性能急劇下降。對(duì)于此類問(wèn)題的研究難點(diǎn)在于：

1）經(jīng)典的多目標(biāo)進(jìn)化算法通常利用傳統(tǒng)的Pareto支配關(guān)系對(duì)個(gè)體進(jìn)行適應(yīng)度賦值，但是隨著目標(biāo)個(gè)數(shù)的不斷增多，非支配個(gè)體在種群中所占比例將迅速上升，甚至種群中大部分個(gè)體都變?yōu)榉侵浣猓虼耍赑areto支配的個(gè)體排序策略會(huì)使種群中的大部分個(gè)體具有相同的排序值而導(dǎo)致選擇操作無(wú)法挑選出優(yōu)良個(gè)體，從而使得進(jìn)化算法搜索能力下降。

2）隨著目標(biāo)數(shù)目的不斷增多，覆蓋Pareto Front最優(yōu)解的數(shù)量隨著目標(biāo)個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng)，這將導(dǎo)致無(wú)法求出完整的PF前沿[4-5]。

3）對(duì)于高維多目標(biāo)優(yōu)化問(wèn)題來(lái)說(shuō)，當(dāng)Pareto前沿面的維數(shù)多于3個(gè)時(shí)，我們就無(wú)法在空間中將其表示出來(lái)，這給決策者帶來(lái)了諸多不便，因此，可視化也是高維多目標(biāo)優(yōu)化的一個(gè)難點(diǎn)問(wèn)題。目前，研究者們相繼提出了用決策圖、測(cè)地線圖、并行坐標(biāo)圖等方法來(lái)可視化問(wèn)題的Pareto前沿面。

3 高維多目標(biāo)進(jìn)化算法分類

目前的高維多目標(biāo)優(yōu)化問(wèn)題按照Pareto前沿的實(shí)際維數(shù)可以分為以下兩類。一類問(wèn)題是高維多目標(biāo)優(yōu)化問(wèn)題真正的Pareto前沿所含的目標(biāo)個(gè)數(shù)要小于目標(biāo)空間的個(gè)數(shù)，也就是說(shuō)，存在著原始目標(biāo)集合的一個(gè)子集能生成與原始目標(biāo)集合相同的Pareto前沿，具有該性質(zhì)的原始目標(biāo)集合的最小元素子集稱為非冗余目標(biāo)集，而原始目標(biāo)集合中去掉非冗余目標(biāo)集的剩余目標(biāo)稱為冗余目標(biāo)，此類問(wèn)題稱為含有冗余的高維多目標(biāo)優(yōu)化問(wèn)題，求解此類問(wèn)題的方法就是利用目標(biāo)縮減技術(shù)刪除這些冗余目標(biāo)，從而確定構(gòu)造Pareto 最優(yōu)前沿所需的最少目標(biāo)數(shù)目，以此來(lái)達(dá)到使問(wèn)題得到簡(jiǎn)化的目標(biāo)。與此類問(wèn)題相對(duì)的是一類不含冗余目標(biāo)的高維多目標(biāo)優(yōu)化問(wèn)題，其分類結(jié)構(gòu)圖如1所示。

對(duì)于不含冗余目標(biāo)的高維多目標(biāo)優(yōu)化問(wèn)題來(lái)說(shuō)，非支配個(gè)體在種群中所占比例隨著目標(biāo)個(gè)數(shù)的增加迅速上升，利用傳統(tǒng)的Pareto支配關(guān)系大大削弱了算法進(jìn)行排序與選擇的效果，導(dǎo)致進(jìn)化算法搜索能力下降。所以，處理此類問(wèn)題的方法大致分為三種：一是采用松馳的Pareto排序方式對(duì)傳統(tǒng)的Pareto排序方式進(jìn)行修改，從而增強(qiáng)算法對(duì)非支配個(gè)體的排序和選擇能力，進(jìn)一步改善算法的收斂性能；二是采用聚合或分解的方法將多目標(biāo)優(yōu)化問(wèn)題整合成單目標(biāo)優(yōu)化問(wèn)題求解。三是基于評(píng)價(jià)指標(biāo)的方法：基于評(píng)價(jià)指標(biāo)的高維多目標(biāo)進(jìn)化算法（Indicator-based Evolutionary Algorithm 簡(jiǎn)稱IBEA）的基本思想是利用評(píng)價(jià)非支配解集優(yōu)劣的某些指標(biāo)作為評(píng)價(jià)個(gè)體優(yōu)劣的度量方式并進(jìn)行適應(yīng)度賦值，從而將原始的高維多目標(biāo)問(wèn)題轉(zhuǎn)化為以優(yōu)化該指標(biāo)為目標(biāo)的單目標(biāo)優(yōu)化問(wèn)題。直接應(yīng)用一些評(píng)價(jià)指標(biāo)代替Pareto 支配關(guān)系以指導(dǎo)進(jìn)化算法的搜索過(guò)程。

4 含有冗余目標(biāo)的高維多目標(biāo)優(yōu)化問(wèn)題的目標(biāo)縮減算法

求解含有冗余目標(biāo)的高維多目標(biāo)優(yōu)化問(wèn)題的方法就是利用目標(biāo)縮減技術(shù)尋找并刪除冗余目標(biāo)，從而確定構(gòu)造Pareto 最優(yōu)前沿所需的最少目標(biāo)數(shù)目。處理含有冗余目標(biāo)的高維多目標(biāo)優(yōu)化問(wèn)題的方法大致分為兩種：一種是基于目標(biāo)之間相互關(guān)系的目標(biāo)縮減方法，另一種是基于保持個(gè)體間Pareto支配關(guān)系的目標(biāo)縮減方法。下面介紹兩類算法的基本思想。

（1）基于目標(biāo)之間相互關(guān)系的目標(biāo)縮減方法

此方法首先利用多目標(biāo)進(jìn)化算法獲得的非支配解集合作為樣本數(shù)據(jù)來(lái)分析目標(biāo)之間的相互關(guān)系，然后通過(guò)分析目標(biāo)間相關(guān)性的強(qiáng)弱來(lái)尋找冗余目標(biāo)。2005年，Deb等提出了基于主成分分析法的高維多目標(biāo)問(wèn)題的目標(biāo)縮減方法（PCA-NSGAII）。該算法將進(jìn)化算法NSGAII和刪除冗余目標(biāo)的過(guò)程相結(jié)合，目標(biāo)間的相關(guān)性是通過(guò)分析非支配集的相關(guān)系數(shù)來(lái)得到的，并由此生成目標(biāo)集合中兩兩目標(biāo)間的相互關(guān)系矩陣，然后通過(guò)分析相互關(guān)系矩陣的特征值和特征向量來(lái)提取互不相關(guān)沖突目標(biāo)來(lái)表示原始目標(biāo)集合，從而達(dá)到目標(biāo)縮減的目的。Jaimes等提出了基于無(wú)監(jiān)督特征選擇技術(shù)的目標(biāo)縮減方法來(lái)求解高維多目標(biāo)優(yōu)化問(wèn)題。在該方法中，原始目標(biāo)集按照目標(biāo)間的相互關(guān)系矩陣劃分成若干個(gè)均勻的分區(qū)。算法將目標(biāo)間的沖突關(guān)系類比于點(diǎn)之間的距離，兩個(gè)目標(biāo)間的沖突性越強(qiáng)，則它們?cè)谀繕?biāo)空間中對(duì)應(yīng)的兩點(diǎn)之間的距離越遠(yuǎn)。算法要尋找的冗余目標(biāo)是在聯(lián)系最緊密的分區(qū)中尋找的。

（2）基于保持個(gè)體間Pareto支配關(guān)系的目標(biāo)縮減方法

Brockhoff等研究了一種基于Pareto支配關(guān)系的目標(biāo)縮減方法，該方法認(rèn)為如果某個(gè)目標(biāo)的存在與否對(duì)非支配解集中個(gè)體之間的Pareto支配關(guān)系沒(méi)有影響或影響很小，則可以將其視為冗余目標(biāo)刪除。他們?cè)谄湮墨I(xiàn)中定義了目標(biāo)集合間相互沖突的定義，并提出了兩種目標(biāo)縮減算法δ-MOSS和k-MOSS，使得在一定誤差允許下保留非支配解集中個(gè)體間的非支配關(guān)系。

另外，HK Singh提出了一種新的基于Pareto支配關(guān)系的目標(biāo)縮減方法，（Pareto Corner Search Evolutionary Algorithm and Objective Reduction 簡(jiǎn)稱PCSEA），該算法將一些具有代表性的處于邊界區(qū)域的非支配解作為辨識(shí)冗余目標(biāo)的樣本點(diǎn)集，并通過(guò)逐個(gè)刪除每個(gè)目標(biāo)能否保持樣本集中解的非支配性來(lái)辨識(shí)冗余目標(biāo)。

高維多目標(biāo)優(yōu)化問(wèn)題的求解算法是科學(xué)研究和工程實(shí)踐領(lǐng)域的一個(gè)非常重要的研究課題，同時(shí)亦是目前進(jìn)化算法領(lǐng)域的一個(gè)研究熱點(diǎn)問(wèn)題之一。但是由于問(wèn)題求解復(fù)雜，當(dāng)前的研究成果還較少，還有待進(jìn)一步研究和探討。今后，對(duì)于高維多目標(biāo)優(yōu)化問(wèn)題的求解算法的進(jìn)一步研究可以從以下幾個(gè)方面展開：

1）引入新的非支配個(gè)體的評(píng)價(jià)機(jī)制。在高維多目標(biāo)優(yōu)化問(wèn)題中，基于Pareto支配關(guān)系的個(gè)體排序策略由于缺乏選擇壓力而無(wú)法將位于不同區(qū)域的非支配個(gè)體區(qū)分開來(lái)，所以如何設(shè)計(jì)新的非支配個(gè)體的評(píng)價(jià)機(jī)制對(duì)這些個(gè)體進(jìn)行比較和排序，既能保證搜索能力不受目標(biāo)個(gè)數(shù)增加的影響，又能得到Pareto最優(yōu)解。

2）探索新的目標(biāo)縮減算法。為了減輕高維目標(biāo)所帶來(lái)的高額的計(jì)算成本，目標(biāo)縮減技術(shù)仍然是當(dāng)前求解高維多目標(biāo)優(yōu)化問(wèn)題的一個(gè)重要方向。

3）多種策略融合。在高維多目標(biāo)優(yōu)化問(wèn)題的求解過(guò)程中，將基于分解的技術(shù)和新的個(gè)體適應(yīng)度賦值策略相結(jié)合，既能有效的增加個(gè)體在選擇操作中的選擇壓力，又能在進(jìn)化過(guò)程中更好地維持種群的多樣性。

【參考文獻(xiàn)】

篇7

Abstract：The constrained multi-objective evolutionary algorithm based on group clustering was improved， and crowding-density was introduced to measure the relationship among individuals and maintain the diversity of population. The basic idea is that the initial population is divided into four groups with different fitness by multi-criterion clustering method， and the crowding-density of each group is calculated. A poset is defined according to the objective function value and crowding-density， and the individuals are selected from poset by the principle of proportion selection， then the elite set is updated. The convergence and distribution of improved algorithm were studied by means of numerical experiments， and the results showed that the convergence of improved algorithm is roughly equal to the conventional multi-objective evolutionary algorithm， but the distribution of improved algorithm is significantly improved.

Key words：constrained multi-objective evolutionary algorithm； group clustering； crowding density； distribution

約束多目標(biāo)優(yōu)化問(wèn)題的關(guān)鍵是對(duì)約束條件的處理，目前已有一些典型的帶約束多目標(biāo)進(jìn)化算法和約束處理機(jī)制：文獻(xiàn)[1]提出的COMOGA算法，將向量評(píng)估遺傳算法和Pareto排序分級(jí)的方法結(jié)合起來(lái)處理約束問(wèn)題。文獻(xiàn)[2]提出的約束VEGA，將群體劃分成幾個(gè)子群體來(lái)處理。文獻(xiàn)[3]提出的約束MOGA，將基于Pareto優(yōu)勝的選擇方案用來(lái)處理遺傳算法中的約束方程。文獻(xiàn)[4]提出了一種基于群體分類的復(fù)雜約束多目標(biāo)進(jìn)化算法，根據(jù)聚類方法來(lái)處理復(fù)雜約束，算法的基本思想是：按照類內(nèi)距離平方和最小，類間距離平方和最大等多種判據(jù)將種群聚類處理，再按類賦以適當(dāng)?shù)倪m應(yīng)度值。這種算法對(duì)于處理Pareto邊界比較光滑的三目標(biāo)的優(yōu)化問(wèn)題效果較好，收斂速度較快，基本上二百代即已達(dá)到較好的優(yōu)化效果，但在維持種群的多樣性和分布性方面欠佳，現(xiàn)將此算法做了改進(jìn)，在進(jìn)化過(guò)程中引入聚集密度以調(diào)控種群，可以達(dá)到維持種群多樣性的目的，并根據(jù)量化評(píng)價(jià)指標(biāo)和數(shù)值實(shí)驗(yàn)結(jié)果對(duì)改進(jìn)算法的性能特別是分布性進(jìn)行了評(píng)測(cè)。

1多目標(biāo)優(yōu)化問(wèn)題的相關(guān)概念

11多目標(biāo)優(yōu)化問(wèn)題及其最優(yōu)解

多目標(biāo)優(yōu)化問(wèn)題可表述為[5]

min y=f（x）=（f1（x），f2（x），…，fk（x））

s.t e（x）=（e1（x），e2（x），…，em（x））≤0

x=（x1，x2，…，xn）T∈X

y=（y1，y2，…，yn）∈Y

（1）

式中：x為決策向量，f（x）為目標(biāo)向量，X表示決策向量x形成的決策空間，Y表示目標(biāo)向量y形成的目標(biāo)空間，約束條件e（x）≤0確定決策向量的可行取值范圍。

定義1[6]滿足式（1）中的約束條件e（x）的決策向量x的集合，即

Xf={x∈X|e（x）≤0} （2）

稱為可行解集。

定義2[7]設(shè)xA，xB是兩個(gè)可行解，若f（xA）≤f（xB）， 則稱xA比xB優(yōu)越； 若f（xA）

定義3若可行解x*滿足：比x*更優(yōu)越的可行解不存在，則稱x*為弱Pareto最優(yōu)解；

比x*優(yōu)越的可行解不存在，則稱x*為強(qiáng)Pareto最優(yōu)解。

定義4Pareto最優(yōu)解的集合稱為Pareto最優(yōu)解集或非支配解集，記為P*。

定義5Pareto最優(yōu)解集P*中的所有Pareto最優(yōu)解集對(duì)應(yīng)的目標(biāo)向量組成的曲面稱為Pareto最優(yōu)前沿或Pareto最優(yōu)前端，記為

兩目標(biāo)優(yōu)化問(wèn)題的Pareto最優(yōu)前沿是一條平面曲線，三目標(biāo)優(yōu)化問(wèn)題的Pareto最優(yōu)前沿則為一張空間曲面。多目標(biāo)優(yōu)化問(wèn)題的結(jié)果習(xí)慣上多采用Pareto最優(yōu)前沿表示。

12最優(yōu)解集的評(píng)價(jià)標(biāo)準(zhǔn)

多目標(biāo)優(yōu)化算法性能的評(píng)價(jià)包括算法的效率和最優(yōu)解集的質(zhì)量。算法的效率主要指算法的復(fù)雜性即算法占用的CPU時(shí)間，而最優(yōu)解集的質(zhì)量包括算法的收斂性和最優(yōu)解集的分布性。

評(píng)價(jià)多目標(biāo)優(yōu)化算法性能主要依靠量化評(píng)價(jià)標(biāo)準(zhǔn)和有代表性的測(cè)試問(wèn)題。

常用的量化評(píng)價(jià)指標(biāo)有：

1） 世代距離[8]（GD）

GD=∑ni=1d2i n （4）

式中：n為算法所得最優(yōu)前端PFknown中向量個(gè)數(shù)，di為PFknown中每一維向量到最優(yōu)前端PFtrue中最近向量的距離。

GD主要反映了PFknown對(duì)PFtrue的逼近程度。

2） 錯(cuò)誤率[9]（ER）

ER=∑ni=1ein （5）

式中：n為PFknown中的向量個(gè)數(shù)，且PFknown={X1，X2，…，Xn，ei定義如下

ei=0， Xi∈PFtrue

1， 其它（6）

ER描述了PFknown對(duì)PFtrue的覆蓋程度，即最優(yōu)解集的分布性。

3） 分散性（SP） [10]

SP=1n-1∑ni=1（di-）2 （7）

式中：n和di同GD。

顯然，SP即為di的均方差。根據(jù)方差的含義，SP反映的是最優(yōu)解集的均勻性。

2基于聚集密度的約束多目標(biāo)算法

上述群體分類的復(fù)雜約束多目標(biāo)進(jìn)化算法具有較好的收斂性，但在分布性方面存在著的一定的缺陷，原因是算法僅考慮了群體中個(gè)體的R適應(yīng)度，并沒(méi)有考慮群體中個(gè)體間的距離，即群體的擁擠程度，這極有可能降低種群的多樣性，影響解的分布性。

在進(jìn)化算法中，保持解的分布性的常用方法有：小生境技術(shù)，信息熵，聚集密度，聚類分析等[11]。

本文將聚集密度引入選擇過(guò)程，改善解的多樣性和分布性。

21聚集密度

聚集密度的概念是Deb在[12]中提出來(lái)的。聚集密度可以從個(gè)體的相似度，影響因子或者聚集距離幾個(gè)方面來(lái)度量，本文選擇從聚集距離角度度量。聚集密度與聚集距離成反比關(guān)系，聚集距離大的聚集密度小。一個(gè)個(gè)體的聚集距離可以通過(guò)計(jì)算其與相鄰的兩個(gè)個(gè)體在每個(gè)子目標(biāo)上的距離差之和來(lái)求取。

如圖1所示，設(shè)有兩個(gè)子目標(biāo)f1（x）和f2（x），Pm[i]為個(gè)體i在子目標(biāo)m上的函數(shù)值，則個(gè)體i的聚集距離P[i]d是圖中四邊形的長(zhǎng)與寬之和，即

計(jì)算出聚集距離后，再按照個(gè)體間的聚集距離越大，則個(gè)體的聚集密度就越小的原則，即可定義個(gè)體的聚集密度。這里，為了簡(jiǎn)單起見(jiàn)，定義聚集密度為聚集距離的倒數(shù)。

22基于聚集密度的約束多目標(biāo)進(jìn)化算法

基于聚集密度的約束多目標(biāo)進(jìn)化算法的步驟如下

1） 用多判據(jù)聚類方法將整個(gè)群體分成四類，不可行群體、可行非Pareto群體、聚類Pareto群體以及聚類Pareto最優(yōu)群體。分別賦以適應(yīng)度：R（不可行群體）≤R（可行非Pareto群體） ≤R（聚類Pareto群體）≤R（聚類Pareto最優(yōu)群體）。

2） 當(dāng)?shù)螖?shù)小于最大迭代次數(shù)時(shí)，構(gòu)造如下偏序集：① 計(jì)算種群中個(gè)體的目標(biāo)函數(shù)值；② 計(jì)算每個(gè)個(gè)體的聚集密度；③ 根據(jù)目標(biāo)函數(shù)值和聚集密度定義一個(gè)偏序集，該偏序集中的元素有兩個(gè)屬性：個(gè)體的目標(biāo)函數(shù)值和聚集距離。

3） 根據(jù)比例選擇原則，依次從偏序集中選擇個(gè)體。

4） 對(duì)群體進(jìn)行交叉運(yùn)算。

5） 對(duì)群體進(jìn)行均勻變異運(yùn)算。

6） 條件終止判斷。不滿足終止條件，則進(jìn)行新一輪運(yùn)算，若滿足終止條件，則輸出計(jì)算結(jié)果，算法結(jié)束。

算法流程圖如下

下面用基于聚集密度的約束多目標(biāo)進(jìn)化算法對(duì)兩個(gè)標(biāo)準(zhǔn)約束多目標(biāo)測(cè)試函數(shù)Binh4和Viennet 4進(jìn)行了優(yōu)化，并將計(jì)算結(jié)果與文獻(xiàn)[12]中的原算法的計(jì)算結(jié)果進(jìn)行了比較，從而檢驗(yàn)改進(jìn)算法的性能。

1） Binh4測(cè)試函數(shù)

F=（f1（x，y），f2（x，y），f3（x，y））

f1（x，y）=15-x（1-y）

f2（x，y）=225-x（1-y2）

f3（x，y）=2625-x（1-y2） （10）

約束條件為

-10≤x，y≤10

x2+（y-05）2≥9

（x-1）2+（y-05）2≤625 （11）

Binh4測(cè)試函數(shù)的PFlocal如圖3所示。

2） Viennet4測(cè)試函數(shù)

Viennet4測(cè)試函數(shù)的PFlocal如圖4所示。圖4Viennet4 PFtrue 圖圖5Binh4 PFknown 圖（改進(jìn)算法）圖6Binh4 PFknown 圖（原算法）圖7Viennet4 PFknown 圖（改進(jìn)算法）圖8Viennet4 PFknown 圖（原算法）

圖5～圖8分別是用改進(jìn)算法和原算法求出的Binh4和Viennet4的Pareto最優(yōu)邊界。可以很直觀地看出，改進(jìn)算法在解的分布性和均勻性方面均明顯優(yōu)于原算法。

為了更進(jìn)一步定量地評(píng)價(jià)改進(jìn)算法的性能，下面給出改進(jìn)算法和原算法的世代距離、錯(cuò)誤率和分散性指標(biāo)的對(duì)比數(shù)據(jù)。

考慮到計(jì)算結(jié)果的隨機(jī)性，表中給出的是20次實(shí)驗(yàn)結(jié)果的平均值。

從表1和表2中可以很清楚地看出，原算法和改進(jìn)算法的GD指標(biāo)相差不大，但改進(jìn)算法的ER和SP指標(biāo)與原算法相比明顯占優(yōu)。

綜合圖5～圖8和表1～表2，可以得出明確的結(jié)論：基于聚集密度的改進(jìn)約束多目標(biāo)進(jìn)化算法的收斂性與原算法相當(dāng)，但分布性和均勻性有了明顯的提高。

4結(jié)束語(yǔ)

本文根據(jù)聚集密度的特點(diǎn)，將聚集密度引入群體聚類約束多目標(biāo)進(jìn)化算法，數(shù)值實(shí)驗(yàn)結(jié)果和量化指標(biāo)表明：與原算法相比，改進(jìn)算法解的分布性有了明顯的提高。

由于多目標(biāo)進(jìn)化算法的理論基礎(chǔ)目前還很薄弱，收斂性和分布性等關(guān)鍵理論問(wèn)題無(wú)法從理論層次進(jìn)行證明，所以算法的改進(jìn)驗(yàn)證只能基于對(duì)比實(shí)驗(yàn)。

提高多目標(biāo)優(yōu)化算法解的分布性和均勻性的方法有多種，如小生境技術(shù)，信息熵，聚集密度，聚類分析等。本文采用的聚集密度方法與其它方法相比，優(yōu)點(diǎn)是既能從宏觀上刻畫群體的多樣性與分布性，也能從微觀上描述個(gè)體間的內(nèi)在關(guān)系，缺點(diǎn)是計(jì)算復(fù)雜度偏高。這完全符合優(yōu)化中的“沒(méi)有免費(fèi)的午餐定理（No Free Lunch， NFL）”。

參考文獻(xiàn)：

[1]SURRY P D， RADCLIFFE N J. The COMOGA Method： Constrained Optimisation by Multi-objective Genetic Algorithms[J].Control and Cybernetics，1997，26：391-412.

[2]COELLO CAC. Treating Constraints as Objectives for Single-Objective Evolutionary Optimization[J].Engineering Optimization，2000，32：275-308.

[3]COELLO C A C.Constraint-handling using an evolutionary multi-objective optimization technique[J].Civil Engineering and Environmental System，2000，17：319-346.

[4]張麗麗， 許峰. 基于群體分類的復(fù)雜約束多目標(biāo)優(yōu)化遺傳算法[J]. 教育技術(shù)導(dǎo)刊， 2009（12）：38-41.

[5]催遜學(xué). 多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2008：6.

[6]催遜學(xué). 多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2008：7.

[7]鄭金華. 多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社，2010：3-4.

[8]VELDHUIZEN D A， LAMONT G B. Evolutionary computation and convergence to a Pareto front[C]// In John R Koza. Late breaking papers at the genetic programming 1998 conference， Stanford University， California. Stanford Bookstore：221-228.

[9]COELLO COELLO C A. Evolutionary algorithms for solving muli-objective problems [M]. Kluwer Acedemic， 2002：14-18.

篇8

協(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)化過(guò)程中的協(xié)同作用。目前通常使用的協(xié)同進(jìn)化算法主要可以分為兩類：以種群競(jìng)爭(zhēng)的方式加速算法收斂和使用種群合作的方式保持種群多樣性。但是這兩種方式都只是強(qiáng)調(diào)了協(xié)同進(jìn)化中的一部分，都存在其不足。在大自然生物們個(gè)體之間的協(xié)同進(jìn)化過(guò)程中，競(jìng)爭(zhēng)、合作這兩種相互矛盾的關(guān)系往往都是同時(shí)存在的。只有強(qiáng)者才具優(yōu)先的權(quán)利，以遺傳下自身的基因，其他處于弱勢(shì)的個(gè)體會(huì)團(tuán)結(jié)起來(lái)與其對(duì)抗，達(dá)到留下自身基因的目的。劉靜在她的博士論文《協(xié)同進(jìn)化算法及其應(yīng)用研究》中基于種群競(jìng)爭(zhēng)和合作思想構(gòu)建了MOCEA（Multi-objective Coevolutionary Algorithm），通過(guò)競(jìng)爭(zhēng)特性算子――吞并算子來(lái)達(dá)到使得優(yōu)秀的基因得到廣泛的傳播和保持種群基因的多樣性，并得到很好的效果。但由于劉的思想仍然是主要依靠種群合作來(lái)達(dá)到加速收斂的目的，其所采用的競(jìng)爭(zhēng)特性算子――吞并算子對(duì)其算法進(jìn)化并沒(méi)起到?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來(lái)對(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看出來(lái)在中間一段曲線上CCEA算法搜索出來(lái)的為一條連續(xù)曲線，而NSGAII算法在這部分是斷開的，這可證明CCEA算法對(duì)pareto前沿解的搜索性能要強(qiáng)于NSGAII算法。

2 結(jié)論

篇9

本文應(yīng)用一種多目標(biāo)模型和算法于配電網(wǎng)網(wǎng)架規(guī)劃中。該算法同時(shí)考慮經(jīng)濟(jì)性和可靠性兩方面的要求，應(yīng)用一種模糊滿意的方法，最終最大化實(shí)現(xiàn)配電網(wǎng)的經(jīng)濟(jì)性和可靠性指標(biāo)的公共滿意度，使得兩者之間的矛盾最小化。

2 網(wǎng)架規(guī)劃模型

本文同時(shí)考慮經(jīng)濟(jì)性和可靠性兩大要求，經(jīng)濟(jì)性要求通常為網(wǎng)絡(luò)的建設(shè)運(yùn)行費(fèi)用和損耗費(fèi)用。可靠性要求為系統(tǒng)的缺電損失費(fèi)用，兩者的計(jì)算公式如下：

（1）

（2）

上式（1）中L為n維決策量，代表優(yōu)化的解，li是L的元素，當(dāng)線路i被選中架設(shè)時(shí)li=1，否則li=0。Cl=？著l+？茁l，？著l是線路投資回收率，？茁l是設(shè)備折舊維修率；CLP為該條架設(shè)線路單位長(zhǎng)度的投資費(fèi)用；Li指的是線路i的長(zhǎng)度；Cp是電價(jià)（元/kW?h）；？駐P是整個(gè)系統(tǒng)總的網(wǎng)絡(luò)損耗（kW）；？子m指相應(yīng)的年最大損耗時(shí)間（h）。Rbenefit指的是停電損失。

這里用？啄1（e1）和？啄2（e2）分別代表經(jīng)濟(jì)性要求和可靠性要求接近其最佳情況的程度。上述模型可轉(zhuǎn)化成下列模型：

（3）

（4）

式中，？孜為兩者的公共模糊滿意度。

3 求解網(wǎng)架規(guī)劃模型

本文基于蟻群算法來(lái)解決配電網(wǎng)網(wǎng)架規(guī)劃問(wèn)題，針對(duì)配電網(wǎng)的樹性特點(diǎn)，使蟻群的一次游程以某種隨機(jī)策略形成一個(gè)輻射網(wǎng)（即一個(gè)網(wǎng)架規(guī)劃方案）。

本文利用集合的概念進(jìn)行求解：Ant表示t時(shí)刻第n只螞蟻連入輻射型網(wǎng)絡(luò)的節(jié)點(diǎn)集合；Bnt表示t時(shí)刻第n只螞蟻未連入輻射型網(wǎng)絡(luò)的節(jié)點(diǎn)集合；Cn0表示t=0時(shí)刻所有待建線路的集合；Dnt表示t時(shí)刻與連入網(wǎng)絡(luò)的節(jié)點(diǎn)相連的屬于集合Cn0的邊的集合，即可以選擇作為下一步待建邊的集合；變電站和負(fù)荷統(tǒng)稱為節(jié)點(diǎn)；一條線路表示兩個(gè)節(jié)點(diǎn)間的電氣連接。邊包括已建線路和待建線路兩種。待建邊j（j=1，2，…，m）上有兩個(gè)權(quán)值，其中一個(gè)權(quán)值Cj是線路的費(fèi)用；另一個(gè)權(quán)值？子j指的是邊j上的信息素。

在每次游歷過(guò)程中，螞蟻n都是從t=0時(shí)刻出發(fā)。螞蟻n在t時(shí)刻先以隨機(jī)概率從集合Ant中選擇線路然后更新兩節(jié)點(diǎn)集合，同時(shí)更新其他幾個(gè)集合。重復(fù)執(zhí)行上述過(guò)程，直到所有的負(fù)荷節(jié)點(diǎn)都被連入輻射性網(wǎng)絡(luò)。

4 算例分析

本文采用IEEE經(jīng)典算例中其中的單電源規(guī)劃算例]進(jìn)行分析，所用算例為一個(gè)具有10個(gè)負(fù)荷點(diǎn)，1個(gè)變電站的系統(tǒng)。如圖1所示，S1為己經(jīng)存在的變電站，虛線表示可選的待建饋線。

由于變電站的供電范圍已確定，所以需要對(duì)算例中的S1變電站的網(wǎng)架結(jié)構(gòu)進(jìn)行規(guī)劃，分別以經(jīng)濟(jì)性、可靠性和兩者綜合最優(yōu)為目標(biāo)進(jìn)行規(guī)劃，結(jié)果圖分別如圖2、圖3和圖4，費(fèi)用結(jié)果如下表所示：

表1 不同目標(biāo)時(shí)的網(wǎng)架規(guī)劃結(jié)果

不同目標(biāo)要求時(shí)候的配電網(wǎng)網(wǎng)架規(guī)劃，單目標(biāo)規(guī)劃時(shí)候只能最大程度上的改善其中的一個(gè)目標(biāo)，而另一指標(biāo)不可避免的就會(huì)有所增加，只有在多目標(biāo)規(guī)劃的時(shí)候，才能得到兩者的綜合最優(yōu)，使得經(jīng)濟(jì)性和可靠性都能得到相對(duì)滿意的結(jié)果，同時(shí)也會(huì)降低總費(fèi)用。

5 結(jié)束語(yǔ)

將多目標(biāo)模型應(yīng)用到配電網(wǎng)網(wǎng)架規(guī)劃中，選擇應(yīng)用蟻群算法這種智能優(yōu)化算法來(lái)進(jìn)行優(yōu)化。通過(guò)不同目標(biāo)時(shí)候配電網(wǎng)網(wǎng)架規(guī)劃方案的比較分析表明本文的多目標(biāo)規(guī)劃能夠得到更好的效果。

參考文獻(xiàn)

[1]孫洪波，徐國(guó)禹，秦翼鴻.電網(wǎng)規(guī)劃的模糊隨機(jī)優(yōu)化模型[J].電網(wǎng)技術(shù)，1996，20（5）：4-7.

[2]于會(huì)萍，劉繼東，程浩忠等.一種綜合協(xié)調(diào)電網(wǎng)規(guī)劃中經(jīng)濟(jì)性和可靠性矛盾的新方法[J].電力自動(dòng)化設(shè)備，2001，21（2）：5-7.

[3]朱旭凱，劉文穎，楊以涵.綜合考慮可靠性因素的電網(wǎng)規(guī)劃新方法[J].電網(wǎng)技術(shù)，2004，28（21）：51-54.

篇10

現(xiàn)代工程實(shí)踐和科學(xué)研究中遇到的很多問(wèn)題都是多目標(biāo)優(yōu)化問(wèn)題，多個(gè)目標(biāo)之間通過(guò)決策變量項(xiàng)目制約，對(duì)于單個(gè)目標(biāo)的優(yōu)化問(wèn)題的唯一最優(yōu)來(lái)說(shuō)，多目標(biāo)問(wèn)題的解并不是唯一的，而是存在一個(gè)最優(yōu)解結(jié)合，在該集合內(nèi)的每一個(gè)解都稱為多目標(biāo)非支配解。對(duì)于工程項(xiàng)目來(lái)說(shuō)，工期、成本和質(zhì)量是工程項(xiàng)目的“三大目標(biāo)”，也是決定項(xiàng)目成功與否的關(guān)鍵因素，對(duì)于任何一個(gè)項(xiàng)目，即需要在約定時(shí)間內(nèi)完成，也需要控制項(xiàng)目成本，同時(shí)還必須確保項(xiàng)目質(zhì)量符合需求。但是工期、成本和質(zhì)量這三個(gè)目標(biāo)存在相互制約的關(guān)系，一般來(lái)說(shuō)，工期和成本成正比，工期和質(zhì)量成反比，成本和質(zhì)量成反比。。因此，需要采用多目標(biāo)算法來(lái)求解工期、成本和質(zhì)量三個(gè)目標(biāo)優(yōu)化問(wèn)題，并且從得到的解集中根據(jù)需求挑選出最優(yōu)解作為該項(xiàng)目的最優(yōu)規(guī)劃目標(biāo)解。

1 多目標(biāo)粒子群算法

1.1 多目標(biāo)算法

多目標(biāo)優(yōu)化算法可以描述為：一個(gè)由滿足一定約束條件的決策變量組成的向量，使得一個(gè)由多個(gè)目標(biāo)函數(shù)組成的向量函數(shù)最優(yōu)化。目標(biāo)函數(shù)組成了性能標(biāo)準(zhǔn)的數(shù)學(xué)描述， 而性能標(biāo)準(zhǔn)之間通常是互相沖突的。優(yōu)化意味著要找到一個(gè)使得所有目標(biāo)函數(shù)值都可接受的解。

多目標(biāo)優(yōu)化問(wèn)題中的最優(yōu)概念最先由Francis Ysidro Edgeworth提出， 后來(lái)Vilfredo Pareto 給出了系統(tǒng)的定義， 通常稱為Pareto最優(yōu)[1-2]。

不失一般性， 在一個(gè)有 k個(gè)目標(biāo)函數(shù)最大化的問(wèn)題中， 稱決策向量[x*∈F]是Pareto最優(yōu)的， 當(dāng)不存在另外一個(gè)決策向量[x∈F]同時(shí)滿足式1。

[fi（x）≥fj（x*），?i∈{1，2，...，k}fi（x）

同樣地， 在最大化問(wèn)題中稱決策向量x優(yōu)于y，或者支配y，需要滿足式2。

[fi（x）≥fj（y），?i∈{1，2，...，k}] （2）

1.2 多目標(biāo)粒子群算法

結(jié)合粒子群算法搜索思想和多目標(biāo)算法原理設(shè)計(jì)多目標(biāo)粒子群算法，由于相對(duì)于單目標(biāo)粒子群算法中的個(gè)體歷史最優(yōu)和群體歷史最優(yōu)的唯一性，多目標(biāo)算法中個(gè)體歷史最優(yōu)和群體歷史最優(yōu)均是一個(gè)非支配解集，因此在多目標(biāo)算法的設(shè)計(jì)中需要解決從非支配解集中挑選出最優(yōu)跟蹤個(gè)體的問(wèn)題。該文采用了文件記錄的方法來(lái)記錄在算法搜索的過(guò)程中找到的所有的非支配解，并且采用一定的方法來(lái)選擇個(gè)體跟蹤的優(yōu)秀目標(biāo)。

由于多目標(biāo)粒子群算法在搜索的過(guò)程中同時(shí)記錄個(gè)體全局最優(yōu)解，個(gè)體最優(yōu)解和局部最優(yōu)解，因此需要三個(gè)記錄文件來(lái)記錄。但是由于三個(gè)記錄文件中的非支配解存在相互交叉支配的現(xiàn)象，并且為了算法簡(jiǎn)潔高效，該文采用一個(gè)檔案文件同時(shí)記錄全局最優(yōu)解，個(gè)體最優(yōu)解和局部最優(yōu)解，檔案文件在算法搜索的過(guò)程中，只要發(fā)現(xiàn)新得到的搜索解存在支配管理，就把該解放入記錄文件中，同時(shí)根據(jù)支配關(guān)系，密度關(guān)系等調(diào)整記錄文件中的最優(yōu)解。

在記錄文件記錄所有最優(yōu)解的基礎(chǔ)上，通過(guò)非支配解排序的方法來(lái)解決這個(gè)每次迭代搜索的時(shí)候，粒子跟隨的最優(yōu)個(gè)體問(wèn)題，具體思路就是首先評(píng)估排序所有的非支配解，然后從排序好的解集中根據(jù)排序的序號(hào)，以選擇概率的方法選擇排序靠前的非支配解作為個(gè)體跟蹤對(duì)象，非支配解排序的序號(hào)越靠前，其被選中的概率越大。

2 工程項(xiàng)目多目標(biāo)建模

2.1 工程項(xiàng)目分解

本文在求解的時(shí)候首先采用網(wǎng)絡(luò)計(jì)劃技術(shù)把整個(gè)項(xiàng)目進(jìn)行工序分解，并且得到工序流程圖，流程圖中的每個(gè)工序節(jié)點(diǎn)都有多種不同的施工方案，每個(gè)施工方法都對(duì)應(yīng)不同的施工費(fèi)用、工期和質(zhì)量。因此項(xiàng)目建設(shè)規(guī)劃便存在多種工期、成本和質(zhì)量的組合方案，工程項(xiàng)目網(wǎng)絡(luò)計(jì)劃圖如圖1所示[3]。

其中，[Mji]表示第i道工序的第j種執(zhí)行模式，[Cji]、[Tji]、[Qji]為該執(zhí)行模式需要的執(zhí)行成本、執(zhí)行工期以及工序質(zhì)量。

2.2 模型建立

在多目標(biāo)模型建立的環(huán)節(jié)，首先分別建立工期目標(biāo)模型、成本目標(biāo)模型和質(zhì)量目標(biāo)模型，然后把三個(gè)模型進(jìn)行組合，得到了工程項(xiàng)目工期、成本和質(zhì)量多目標(biāo)優(yōu)化模型[4]。

項(xiàng)目工期模型如式（3）所示。

[min] [fT=i=1nMmiLj∈Lxmitmi] （3）

其中，L表示路徑集合，Li 表示具體的路徑，[xmi]為0或者1，代表是否執(zhí)行了活動(dòng)i的第m道執(zhí)行模式，其中1表示執(zhí)行，0表示沒(méi)有執(zhí)行。[tmi]表示執(zhí)行了活動(dòng) i 的的第 m 道執(zhí)行模式所獲得的所需工時(shí)。

項(xiàng)目成本模型如式（4）所示。

[min] [fC=i=1nMmixmi（k∈Kumi，krmi，k+k∈Kidcmi，k）] （4）

其中，[xmi]為0或者1，代表是否執(zhí)行了活動(dòng)i的第m道執(zhí)行模式。[umi，k]表示在執(zhí)行活動(dòng)i第m道執(zhí)行模式時(shí)，所耗費(fèi)的第k項(xiàng)資源的單位費(fèi)用，[rmi，k]表示在執(zhí)行活動(dòng)耗費(fèi)的第k項(xiàng)資源的量。[idcmi，k]表示執(zhí)行活動(dòng)耗費(fèi)的第k項(xiàng)間接資源費(fèi)用。

質(zhì)量目標(biāo)模型如式（5）所示。

[Q=i=1nMmj（xmi?qmi?gρgzgi）i=1nMmj（10xmi?gρgzgi）?10] （5）

其中，[qmi]表示在子工序i的在第 m 道執(zhí)行模式中對(duì)應(yīng)的質(zhì)量值，分母表示[i=1nMmj（10xmi?gρgzgi）]把所有子工序?qū)?yīng)的指標(biāo)質(zhì)量值均設(shè)為10時(shí)的項(xiàng)目總質(zhì)量值。

因此，總體的多目標(biāo)模型如式（6）所示。

[min] [max] [fT=i=1nMmiLj∈Lxmitmi]

[min] [fC=i=1nMmixmi（k∈Kumi，krmi，k+k∈Kidcmi，k] （6）

[max Q=i=1nMmj（xmi?qmi?gρgzgi）i=1nMmj（10xmi?gρgzgi）?10]

[s.t.] [mxmi=1i=1nmxmi?rmi，k≤RkT0≥fTC0≥fCQ0≥fQ]

3 仿真實(shí)驗(yàn)

采用工程項(xiàng)目多目標(biāo)粒子群算法仿真實(shí)際工程道路項(xiàng)目，該道路工程為典型的土方施工項(xiàng)目，根據(jù)項(xiàng)目施工規(guī)劃要求以及施工地的地質(zhì)特點(diǎn)，整個(gè)項(xiàng)目可以細(xì)化為包括施工準(zhǔn)備、路基土方、軟土處理、防護(hù)工程等在內(nèi)的15項(xiàng)具體活動(dòng)，該連接線工程的網(wǎng)絡(luò)計(jì)劃圖如圖2所示。

采用多目標(biāo)粒子群算法優(yōu)化項(xiàng)目工序模式選擇，因?yàn)轫?xiàng)目工序模式為整數(shù)，所以采用對(duì)種群進(jìn)行離散化，即每一次迭代得到新的種群后，都采用四舍五入的方法把新的種群離散化。因?yàn)橐还灿?4道施工工序，所以粒子維數(shù)為14，從而每一個(gè)粒子都代表一個(gè)施工方案，其他的參數(shù)為種群個(gè)數(shù)為100，算法迭代次數(shù)為20。算法得到的多目標(biāo)非支配解如圖3所示。

從圖3可以看出，該文提出的多目標(biāo)粒子群算法搜索性能較高，算法在運(yùn)行的時(shí)候能夠找到較多的非支配解集，對(duì)于每個(gè)非支配解集中的解來(lái)說(shuō)，都代表其中的一個(gè)施工方案。

4 小結(jié)

針對(duì)工程項(xiàng)目建設(shè)規(guī)劃問(wèn)題中工期-成本-質(zhì)量三個(gè)目標(biāo)相互制約，一般算法難以得到三個(gè)目標(biāo)的最優(yōu)解的問(wèn)題，該文采用多目標(biāo)粒子群算法進(jìn)行求解，在建立尋優(yōu)問(wèn)題的基礎(chǔ)上，采用粒子群算法搜索多目標(biāo)問(wèn)題的非支配解集，仿真實(shí)驗(yàn)表明多目標(biāo)粒子群算法能夠得到工期-成本-質(zhì)量多目標(biāo)優(yōu)化問(wèn)題的解集，從而為工程項(xiàng)目規(guī)劃提供了一個(gè)新的參考方法。

參考文獻(xiàn)：

[1] 鄭向偉，劉弘.多目標(biāo)進(jìn)化算法研究進(jìn)展[J].計(jì)算機(jī)科學(xué)，2007，34（7）：187-192.

篇11

1.1資源分配模型NNIA是一種經(jīng)典的進(jìn)化多目標(biāo)優(yōu)化算法，在此算法的運(yùn)行過(guò)程中，只是采用少數(shù)的非支配個(gè)體進(jìn)行操作，考慮到本文采用的多目標(biāo)考試時(shí)間表的建模方式，在算法運(yùn)行過(guò)程中，當(dāng)出現(xiàn)非支配解數(shù)量不足的情況時(shí)，必然會(huì)對(duì)NNIA框架下的算法性能產(chǎn)生十分明顯的影響。顧本文在采用NNIA算法框架的基礎(chǔ)上，在個(gè)體克隆階段，設(shè)計(jì)了一種基于博弈論的資源分配模型，通過(guò)動(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)行過(guò)程中，根據(jù)不同的模型，采用相應(yīng)的克隆策略。早期模型(r≤1/3)：在此階段只有很少的優(yōu)秀個(gè)體（R1個(gè)體）。根據(jù)博弈論的相關(guān)概念，需要抑制R2中個(gè)體的克隆數(shù)量，以保證其無(wú)法影響到R1中的個(gè)體。如公式(5)所示，其中Si表示原始的克隆尺寸，Mi表示資源分配模型計(jì)算過(guò)后，克隆后第i級(jí)別的克隆規(guī)模。

1.2基于超啟發(fā)方法的種群初始化許多學(xué)者的研究及仿真實(shí)驗(yàn)表明[1]，基于圖著色的超啟發(fā)方法十分適合處理單目標(biāo)考試時(shí)間表問(wèn)題。采用超啟發(fā)方法擁有更大幾率快速找到可行解或潛在的優(yōu)勢(shì)個(gè)體。針對(duì)本文所面對(duì)的多目標(biāo)考試時(shí)間表問(wèn)題，若能快速得到可行解或潛在的優(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)生初始解的過(guò)程中，每當(dāng)產(chǎn)生一個(gè)新的考試時(shí)間表示，通過(guò)這些不同的啟發(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è)試。近幾十年來(lái)，幾乎所有關(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)過(guò)10次獨(dú)立運(yùn)行，隨機(jī)選取一組解集，其pareto前沿面如圖2所示。少數(shù)幾個(gè)測(cè)試集（car91,car92,ear83等）在個(gè)別區(qū)域沒(méi)有找到非支配解。除上述測(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é)果來(lái)看，除數(shù)據(jù)集york83，我們的算法均能找到與單目標(biāo)模型中相同的時(shí)間段。從具體結(jié)果上來(lái)說(shuō)，我們的結(jié)果的確與其他幾種最優(yōu)秀的單目標(biāo)優(yōu)化結(jié)果尚存一定差距，但差距并不明顯。重要的是采用本文提出的多目標(biāo)優(yōu)化算法，經(jīng)過(guò)一次運(yùn)行就可提供不同時(shí)間段的多個(gè)解，運(yùn)行效率是單目標(biāo)優(yōu)化的數(shù)十倍。上述結(jié)果表明，將考試時(shí)間表問(wèn)題按照多目標(biāo)優(yōu)化問(wèn)題建模有效且可以極大地提高計(jì)算效率。本文在NNIA框架下，在克隆階段采用了資源分配模型，此模型對(duì)于整個(gè)算法的影響可由下列實(shí)驗(yàn)得出結(jié)論。圖3為十組測(cè)試數(shù)據(jù)分別來(lái)自為采用資源分配模型的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)過(guò)十次獨(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í)間表問(wèn)題，非支配解的數(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í)間表問(wèn)題的多目標(biāo)進(jìn)化算法。

篇12

現(xiàn)代物流從起步期迅速進(jìn)入發(fā)展期的重要標(biāo)志之一是以新建和改建配送中心為主的大規(guī)模物流基礎(chǔ)設(shè)施的投資。目前，投資超過(guò)百億的就有上海、北京、天津、深圳、香港等地。在現(xiàn)代物流系統(tǒng)中，配送中心是集物流、信息流和資金流為一體的流通型節(jié)點(diǎn)，是我國(guó)物流系統(tǒng)建設(shè)中的戰(zhàn)略規(guī)劃之重。通常，對(duì)于物流配送中心的設(shè)計(jì)，絕大多數(shù)研究?jī)H考慮了成本的優(yōu)化。由于在物流配送中心進(jìn)行的各種物流活動(dòng)，如運(yùn)輸過(guò)程中車輛排放的co2、so2；對(duì)舊產(chǎn)品回收后進(jìn)行翻新、循環(huán)產(chǎn)生的有害物質(zhì)；流通加工中的能量消耗等，都會(huì)對(duì)環(huán)境產(chǎn)生影響，因此，在物流配送中心的選址決策問(wèn)題中既要考慮降低成本，又要盡可能降低對(duì)于環(huán)境的影響。這就需要建立多目標(biāo)優(yōu)化模型。近幾年，一些國(guó)外學(xué)者提出了可持續(xù)發(fā)展的供應(yīng)鏈的概念，關(guān)注于物流與供應(yīng)鏈對(duì)環(huán)境的造成的影響。文獻(xiàn)利用多目標(biāo)技術(shù)來(lái)優(yōu)化設(shè)計(jì)可持續(xù)發(fā)展的物流網(wǎng)絡(luò)。但是對(duì)于物流網(wǎng)絡(luò)中需要建立的設(shè)施都視為相同的。實(shí)際上，不同的設(shè)施對(duì)于環(huán)境可能產(chǎn)生的影響不同。文獻(xiàn)通過(guò)建立一個(gè)多目標(biāo)優(yōu)化模型來(lái)降低對(duì)于環(huán)境的影響，但是僅通過(guò)設(shè)施之間的距離來(lái)描述影響環(huán)境的因素，而影響環(huán)境的因素是多方面的。本文通過(guò)粗糙集方法來(lái)建模配送中心對(duì)于環(huán)境的影響時(shí)，利用綠色度概念將影響環(huán)境的多因素綜合起來(lái)，提出了優(yōu)化成本和環(huán)境的多目標(biāo)模型來(lái)確定配送中心，從而更好的反映實(shí)際情況。

二、 配送中心的綠色度

我們建立配送中心的綠色度評(píng)價(jià)指標(biāo)如下：（1）包裝、運(yùn)輸、倉(cāng)儲(chǔ)的綠色化；（2）回收處理綠色化；（3）環(huán)境污染程度。如何確定指標(biāo)的權(quán)重是一個(gè)重要問(wèn)題。在現(xiàn)實(shí)中，人們往往在信息不確定情況下進(jìn)行決策，而粗糙集方法是一種進(jìn)行不確定性決策和推理的有力工具，因此本文利用粗糙集屬性重要度方法獲得指標(biāo)的權(quán)重。下面給出關(guān)于粗糙集的一些基本性質(zhì)。

定義6：s=（u，a，v，f）為一個(gè)信息系統(tǒng)，a=c∪d，c∩d=?覫，e?奐c。屬性a（a∈c\e）的重要性sgf（a，e，d）=h（d|e）-h（d|e∪{a}），對(duì)給定的屬性子集e，sgf（a，e，d）的值越大，屬性a對(duì)決策d就越重要。

本文用“好”、“中”、“差”3個(gè)等級(jí)來(lái)評(píng)價(jià)指標(biāo)（1）和（2）。用“高”、“中”、“低”3個(gè)等級(jí)來(lái)評(píng)價(jià)指標(biāo)（3）。采用3分法，用1、2、3分別對(duì)應(yīng)“好”、“中”、“差”和“高”、“中”、“低”。根據(jù)專家意見(jiàn)設(shè)計(jì)決策表，經(jīng)過(guò)簡(jiǎn)約后得到14種不同的決策組合，如表1所示。

其中決策欄的“1”表示建配送中心，“0”表示不建。經(jīng)過(guò)計(jì)算得到：

于是得到包裝、運(yùn)輸、倉(cāng)儲(chǔ)的綠色化的重要度為0.188 2，回收處理綠色化重要度分別為0.102 2，環(huán)境污染程度的重要度為0.145 2。于是屬性a的權(quán)重wa=0.188 2/（0.188 2+0.102 2+0.145 2）=0.432，屬性b的權(quán)重wb=0.102 2/（0.188 2+0.102 2+0.145 2）=0.235，屬性c的權(quán)重wc=0.145 2/（0.188 2+0.102 2+0.145 2）=0.333。對(duì)每個(gè)備選配送中心在指標(biāo)體系下打分，然后按指標(biāo)加權(quán)，則可得到每個(gè)備選配送中心的綠色度。

三、 選址決策模型

1. 參數(shù)和決策變量定義。

模型參數(shù)如下：

i∈i客戶區(qū)的下標(biāo)；j∈j備選配送中心的下標(biāo)；fj建立配送中心j的固定成本；ai客戶區(qū) 的需求量；dij將單位產(chǎn)品從配送中心j運(yùn)到客戶區(qū)i的運(yùn)費(fèi)；wj配送中心j的綠色度。決策變量定義如下：

xj=1如果在備選地j建立配送中心0否則，zij客戶區(qū)i的產(chǎn)品由配送中心j配送的比例。

2. 多目標(biāo)優(yōu)化模型。

目標(biāo)函數(shù)（1）式為最小化總的建設(shè)成本。（2）最大化配送中心的綠色度。（3）式確保每個(gè)客戶區(qū)的需求都得到滿足。（4）式表示客戶區(qū)i的需求由配送中心j負(fù)責(zé)，當(dāng)且僅當(dāng)建立了j配送中心。（5）、（6）為變量的取值約束。

四、 算例分析

在不同的備選地建立不同等級(jí)的配送中心的成本如表2所示。有8個(gè)客戶區(qū)，每個(gè)備選配送中心到客戶區(qū)的單位產(chǎn)品運(yùn)費(fèi)如表3所示。

通過(guò)決策表的計(jì)算，得到6個(gè)備選配送中心的綠色度分別為0.713、0.882、0.561、0.758、0.608、0.843。

令f*1為目標(biāo)函數(shù)（1）的最優(yōu)值，f*2為目標(biāo)函數(shù)（2）的最優(yōu)值。先分別對(duì)兩個(gè)單目標(biāo)問(wèn)題求出最優(yōu)解f*1=31.380，f*2=4.365，采用理想點(diǎn)法，將“三”之“2”節(jié)中的模型轉(zhuǎn)化為如下形式：

求解得到l=3.652，f1=31.380，f2=0.713，x1=1，x2=0，x3=0，x4=0，x5=0，x6=0，即只建立備選配送中心1。

五、 結(jié)論

配送中心具備發(fā)展現(xiàn)代物流的戰(zhàn)略優(yōu)勢(shì)。目前我國(guó)新建的物流配送中心規(guī)模越來(lái)越大，同時(shí)在配送中心進(jìn)行的各種物流活動(dòng)對(duì)環(huán)境造成了負(fù)面的影響。為了實(shí)現(xiàn)可持續(xù)發(fā)展，需要在建立配送中心的時(shí)候，盡可能減低對(duì)于環(huán)境的污染。本文通過(guò)綠色度評(píng)價(jià)來(lái)獲得備選配送中心的環(huán)境效益，通過(guò)建立最小化建設(shè)運(yùn)營(yíng)成本和最大化環(huán)境效益為目標(biāo)，建立雙目標(biāo)優(yōu)化模型來(lái)進(jìn)行物流配送系統(tǒng)的設(shè)計(jì)，能夠?yàn)槠髽I(yè)和政府相關(guān)決策部門實(shí)施綠色物流提供科學(xué)的方法。

參考文獻(xiàn)：

1. klose a, drexl. a. facility location mod- els for distribution system design. european jou- rnal of operational research，2005，（162）:4-29.

2. melo m.t.et al., facility location and supply chain management: a review. european journal of operational research，2008.

3. 秦固.基于蟻群優(yōu)化的多物流配送中心選址算法. 系統(tǒng)工程理論與實(shí)踐,2006,（4）:120-124.

4. 王曉博,李一軍.電子商務(wù)環(huán)境下物流配送中心選址模型與評(píng)價(jià)方法.系統(tǒng)工程理論方法應(yīng)用,2006,15（3）: 199-204.

5. frota, n. j. and j. m. bloemhof-ruwaard, et al. designing and evaluating sustainable logistics networks. international journal of production economics special section on susta- inable supply chain，2008,111（2）:195-208.

6. 何波，楊超，任鳴鳴.廢棄物處理站選址問(wèn)題及多目標(biāo)演化算法求解.系統(tǒng)工程理論與實(shí)踐，2007,（11）:72-78.

篇13

文章編號(hào):1004-373X(2010)05-047-04

Goals Optimization Based on Quantum Crowd Particle Algorithm in PHY

Layer and MAC Layer in Cognitive Radio System

XUE Zhoucheng1,LV Junwei1,NI Lei2

(1.Ordnance Engineering College,Shijiazhuang,050003,China;2.Unit 61451 of the PLA,Beijing,100094,China)

Abstract:Cognitive radio technology is tendency and the direction of future communication development,it is also the focus of the communication research.Aimming at solving the problem of goals optimization under certain channel condition in its physical layer and medium link layer in cognitive radio system.The problems of goals optimization problem in cognitive radio based on the basic thoughts of quantum particle crowd algorithm are solved and thoughts of quantum particle crowd algorithm in the cognitive radio system are used for carrying out proper improvements.Finally it emulates the optimization problem using the radio station controlled by WSGA.

Keywords:cognitive radio;quantum crowd particle algorithm;goals optimization;PHY layer and MAC layer

0 引 言

認(rèn)知無(wú)線電(Cognitive Radio)將人工智能與無(wú)線電通信相結(jié)合,這個(gè)領(lǐng)域具有高度的多學(xué)科性質(zhì),混合了傳統(tǒng)通信與電子工程的無(wú)線電,同時(shí)應(yīng)用了來(lái)自計(jì)算機(jī)科學(xué)的一些概念[1]。基本定義可歸納為:它是可以感知外界通信環(huán)境的智能通信系統(tǒng),認(rèn)知無(wú)線電系統(tǒng)通過(guò)學(xué)習(xí),不斷地感知外界環(huán)境的變化,并通過(guò)自適應(yīng)調(diào)整內(nèi)部的通信機(jī)理達(dá)到對(duì)環(huán)境變化的適應(yīng)。這樣的自適應(yīng)調(diào)整,一方面是為了改進(jìn)系統(tǒng)的穩(wěn)定性,另一方面也是為了提高頻譜的利用率。根據(jù)認(rèn)知無(wú)線電框架,用戶首先需要檢測(cè)頻譜環(huán)境,估計(jì)當(dāng)前信道中的干擾溫度及其接入對(duì)鄰近用戶的干擾,根據(jù)這些測(cè)量數(shù)據(jù),用戶可以自適應(yīng)地改變傳輸參數(shù),以達(dá)到系統(tǒng)最終的性能最優(yōu)。其基本任務(wù)是:環(huán)境分析、信道預(yù)測(cè)估計(jì)和信道預(yù)測(cè)建模、傳輸功率控制和動(dòng)態(tài)頻譜管理[2]。

認(rèn)知無(wú)線電的目標(biāo)是最優(yōu)化自身性能以及支持用戶的需求,但是“最優(yōu)化”的含義是什么?它不僅僅是無(wú)線電用戶追求自身資源消耗最大化的自適應(yīng)參數(shù)調(diào)整,考慮在無(wú)線電通信上,如果兩對(duì)節(jié)點(diǎn)在不同的網(wǎng)絡(luò)上通信,傳輸在時(shí)間和頻率上的重疊,會(huì)形成干擾。節(jié)點(diǎn)將低信干噪比(SINR)的情況認(rèn)為是觀測(cè)到了干擾,傳統(tǒng)應(yīng)對(duì)干擾的方法是通過(guò)增大發(fā)射功率來(lái)增加SINR,┮惶趿綽飛系姆⑸浠增加發(fā)射功率,另一鏈路也將會(huì)以提高發(fā)射功率來(lái)回應(yīng)[3]。每個(gè)無(wú)線電用戶都將通過(guò)增大自身的發(fā)射功率來(lái)使接收機(jī)的SINR最大化,這樣最終會(huì)使功率增加到硬件的極限[4]。

在嚴(yán)重?fù)砣念l譜環(huán)境中,改變頻率可能不是一個(gè)很好的解決方法,這是為什么要查找可能調(diào)整的所有物理層和鏈路層來(lái)改善其性能的原因[5]。

首先定義,在無(wú)線電中實(shí)現(xiàn)了滿足用戶的性能水平,并最小化其消耗資源(如占用的帶寬、消耗的功率等)時(shí),就認(rèn)為“最優(yōu)化”。因此應(yīng)該知道用戶的需要以及如何調(diào)整無(wú)線電性能才能滿足這些需要。

在物理層中,中心頻率、符號(hào)速率、發(fā)射功率、調(diào)制類型和調(diào)制階數(shù)、脈沖成形濾波器(PSF)類型、階數(shù)、擴(kuò)頻類型、擴(kuò)頻因子等都能進(jìn)行調(diào)整。鏈路層上則為各種可以改進(jìn)網(wǎng)絡(luò)性能的變量,包括信道編碼和交織類型和速率,以及接入控制方法,如流量控制、幀的大小以及多址接入技術(shù)等。

認(rèn)知無(wú)線電遵循的基本過(guò)程是調(diào)整自身的參數(shù)來(lái)實(shí)現(xiàn)某一期望的最優(yōu)性能組合。無(wú)線最優(yōu)化概念是通過(guò)分析許多目標(biāo)函數(shù)的輸入與輸出來(lái)描述的,在這種情況下,描述各個(gè)目標(biāo)之間的相互依賴關(guān)系使用單目標(biāo)分析系統(tǒng)變得困難,用戶和網(wǎng)絡(luò)的需求不能同時(shí)得到滿足,這種需求會(huì)隨著時(shí)間和具體情況發(fā)生很大變化。這時(shí)單目標(biāo)函數(shù)已不能充分表示這些不同目標(biāo)的需求[6]。

設(shè)認(rèn)知無(wú)線電需調(diào)整的N個(gè)參數(shù)為a=,具體參數(shù)是發(fā)射功率、調(diào)制方式、中心頻率、符號(hào)速率等,由于受各種制度、物理環(huán)境、硬件條件等方面的限制,認(rèn)知無(wú)線電參數(shù)通常要滿足很多約束條件。為適應(yīng)當(dāng)前外部條件,認(rèn)知無(wú)線電需優(yōu)化的目標(biāo)函數(shù)為f=,其中n為目標(biāo)函數(shù)的個(gè)數(shù),目標(biāo)函數(shù)的選擇要求能反映當(dāng)前的鏈路質(zhì)量,如平均發(fā)射功率、數(shù)據(jù)速率、識(shí)碼率、帶寬、頻帶效率、數(shù)據(jù)包延時(shí)等。不同的鏈路條件、不同的用戶需求導(dǎo)致不同目標(biāo)函數(shù)的重要性不盡相同。在實(shí)際運(yùn)用中可用權(quán)重?cái)?shù)值的大小來(lái)反映目標(biāo)函數(shù)的重要性程度。由此可知實(shí)現(xiàn)認(rèn)知無(wú)線電參數(shù)的調(diào)整功能是一個(gè)多目標(biāo)優(yōu)化問(wèn)題,即如何調(diào)整無(wú)線電參數(shù)取值來(lái)實(shí)現(xiàn)給定權(quán)重情況下多個(gè)目標(biāo)函數(shù)的優(yōu)化[7]。

由于缺少單目標(biāo)函數(shù)的衡量,所以不能從經(jīng)典的優(yōu)化理論來(lái)獲得調(diào)整無(wú)線電參數(shù)的方法,取而代之的是使用MODE標(biāo)準(zhǔn)來(lái)分析無(wú)線電性能。MODE理論使得人們可以在與之用來(lái)建模的目標(biāo)函數(shù)個(gè)數(shù)一樣多的維數(shù)中實(shí)現(xiàn)最優(yōu)化,目前遺傳算法已被廣泛用于MODE問(wèn)題的求解[1]。

MODE理論的核心是用數(shù)學(xué)方法選擇一系列的參數(shù),從而使一組目標(biāo)函數(shù)最優(yōu)化。MODE方法的基本表示如式(1)、式(2)所示:

min/max(y)=f()=),f2(),…,fn()〗(1)

約束條件:

=(x1,x2,…,xm)∈X

=(y1,y2,…,ym)∈Y(2)

其中,所有的目標(biāo)函數(shù)都定義成最大化y或最小化y,最大化或最小化取決于具體的實(shí)際應(yīng)用。x的值(即x1,x2等)表示輸入;y值表示輸出。式(1)提供了MODE的表示,但沒(méi)有指定優(yōu)化系統(tǒng)的方法。某些目標(biāo)函數(shù)以某種方式進(jìn)行組合會(huì)產(chǎn)生最優(yōu)化的輸出。在實(shí)踐中可以有很多方法實(shí)現(xiàn)最優(yōu)化,目前遺傳算法運(yùn)用最廣泛。

傳統(tǒng)求解多目標(biāo)優(yōu)化問(wèn)題的方法有加權(quán)法、約束法、目標(biāo)規(guī)劃法等,這些求解方法按某種策略確定多目標(biāo)之間的權(quán)衡方式,將多目標(biāo)問(wèn)題轉(zhuǎn)換為多個(gè)不同的單目標(biāo)問(wèn)題,并用這些單目標(biāo)優(yōu)化問(wèn)題的最優(yōu)解構(gòu)成的解集去近似最優(yōu)解。這些方法和每次優(yōu)化結(jié)果,只得到┮桓鐾仔解,而且采用不同的方法求解,結(jié)果可能完全不同。

本文引入的量子粒子群算法用于對(duì)MODE問(wèn)題的求解,同時(shí)對(duì)于量子粒子群算法進(jìn)行了一些改進(jìn)。量子衍生計(jì)算是近年來(lái)新提出的一種新的計(jì)算方法,引進(jìn)量子理論的進(jìn)化算法具有很好的空間搜索能力。量子多目標(biāo)進(jìn)化算法具有更強(qiáng)逼近最優(yōu)前沿的能力和更好的多樣性,具有量子行為的粒子群算法,能保證全局的收斂性,其性能優(yōu)于傳統(tǒng)的遺傳算法。

1 量子粒子群算法

1.1 粒子群算法的基本思想

粒子群算法(PSO)是由Kennedy和Eberhart等于1995年率先提出的,它借鑒鳥群捕食過(guò)程的社會(huì)行為,是一種并行進(jìn)化的計(jì)算方法,引入慣性權(quán)重來(lái)實(shí)現(xiàn)對(duì)解空間的搜索控制,逐步形成了目前普遍應(yīng)用的基本粒子群算法[8]。思想是:為將每個(gè)個(gè)體看作是D維搜索空間中一個(gè)沒(méi)有體積和質(zhì)量的粒子,在搜索空間中,以一定的速度飛行,并根據(jù)個(gè)體和群體飛行經(jīng)驗(yàn)的綜合分析來(lái)動(dòng)態(tài)調(diào)整這個(gè)速度。設(shè)群體中第i個(gè)粒子為Xi,它經(jīng)歷過(guò)的位置為Pi,其中最佳位置記為Pbest,當(dāng)前組成的群體中所有粒子經(jīng)過(guò)的最佳位置記為Pgbest,粒子i速度用vi=(vi1,vi2,…,vid)表示,對(duì)第i次迭代,粒子i在D維空間的運(yùn)動(dòng)方程為:

vid(t+1)=w•vid(t)+c1rand()[pbest-xid(t)]+

c2rand()[Pgbest-x(t)]

xid(t+1)=xid+v(t+1)(3)

式中:w為慣性權(quán)重,它使粒子保持運(yùn)動(dòng)的慣性,使其有能力探索新的區(qū)域;c1,c2為常數(shù);rand為范圍的隨機(jī)數(shù)。

1.2 量子比特的表示

提出量子比特編碼多態(tài)問(wèn)題可由式(4):

α1α2…αm

β2β2…βm〗(4)

表示為。通用量子旋轉(zhuǎn)門調(diào)整則相應(yīng)可表示為:

α′iβ′i〗=cos(Δθ)-sin(Δθ)sin(Δθ)cos(Δθ)〗αiβi〗(5)

1.3 量子粒子群算法

從量子力學(xué)的角度出發(fā)提出了一種新的PSO算法模型。這種模型以DELTA勢(shì)阱為基礎(chǔ),認(rèn)為粒子具有量子行為,并根據(jù)這種模型,提出了一種具有量子行為的粒子群算法。此算法具有簡(jiǎn)單易實(shí)現(xiàn)和調(diào)節(jié)參數(shù)少的優(yōu)點(diǎn),具有良好的穩(wěn)定性和收斂性[9]。

借用粒子群中的群智能策略,將這種群的所有量子看成一個(gè)智能群體,找到每次迭代過(guò)程中局部最優(yōu)解進(jìn)行進(jìn)一步的動(dòng)態(tài)調(diào)整,其操作過(guò)程是:量子粒子i在┑j比特經(jīng)i次迭后,速度、位置、個(gè)體最好和全局位置分別為vij(t),θij(t),θbestij,θgbestij,則速度和位置迭代公式為:

vij(t+1)=w•vij(t)+c1rand()+

c2rand()

θij(t+1)=θij(t)+vij(t+1)(6)

本文基于以上量子粒子群算法的基本思想,采用基于Pareto支配關(guān)系的排序關(guān)系來(lái)更新粒子的個(gè)體最優(yōu)值和局部發(fā)最優(yōu)值,定義一種新的極大極小距離方法,并采用該距離方法裁減非支配解。利用量子粒子旋轉(zhuǎn)門更新粒子的量子角度,提出了一種新的多目標(biāo)優(yōu)法算法。

1.4 基于距離方法的量子粒子群多目標(biāo)優(yōu)化算法

提出用于計(jì)算適應(yīng)值的距離方法――量子粒子群多目標(biāo)優(yōu)化算法(Quantum Bit Particle Swarm Optimization,QBPSO),來(lái)解決多目標(biāo)優(yōu)化問(wèn)題。這種方法的基本思想是根據(jù)每個(gè)個(gè)體到前┮淮獲得的Pareto解之間的距離來(lái)分配其適應(yīng)值。它采用外部懲罰函數(shù)將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)換為無(wú)約束問(wèn)題。其中,參數(shù)r控制懲罰項(xiàng)的幅度,Pi是初始潛在值。

該距離方法對(duì)于Pi和r的設(shè)置比較敏感。對(duì)于任何不可行解,r的值越高,計(jì)算得到的距離值也越高,因此,適應(yīng)值最終接近于0,如果太多,個(gè)體的適應(yīng)值為0,搜索將無(wú)法進(jìn)行。另外,如果初始潛在值與不同解之間的適應(yīng)值差別會(huì)很不明顯。這將導(dǎo)致選擇壓力過(guò)小,結(jié)果導(dǎo)致算法收斂速度較慢。另一方面,如果初始潛在值過(guò)小,計(jì)算得到的適應(yīng)值將趨向于0。

對(duì)于每個(gè)個(gè)體歷史最優(yōu)解的選取,采用以下步驟:

(1) 如果當(dāng)前解支配個(gè)體i個(gè)歷史最優(yōu)解,則作為歷史最優(yōu)解。

(2) 如果當(dāng)前解不支配i個(gè)歷史最優(yōu)解,則比較當(dāng)前解和歷史最優(yōu)解的D(i)值,選擇具有較小D(i)的那個(gè)解作為歷史最優(yōu)解[10]。

1.5 慣性權(quán)重的改進(jìn)

慣性權(quán)重類似模擬退火中的溫度,較大的w有較好的全局收斂能力;而較小的w則有較強(qiáng)的局部收斂能力,慣性權(quán)重w滿足:

w(t)=0.9-(0.5t)/MaxNumber(7)

式中:MaxNumber為最大截止代數(shù)。這樣,將慣性權(quán)重w看成迭代次數(shù)的函數(shù),可從0.9~0.4線性減少。

雖然該方法能保證慣性權(quán)重w隨迭代次數(shù)的增加而減小,但在每一代中,所有粒子的慣性權(quán)重均一樣,不能很好地體現(xiàn)每個(gè)粒子的支配關(guān)系和擁擠程度。因此,在本文算法中,采用不動(dòng)態(tài)設(shè)置慣性權(quán)重。

慣性權(quán)重w=群體粒子數(shù)/個(gè)體粒子數(shù)N+被粒子I所支配的粒子數(shù)+距離密度D(i)。

可以看出,慣性權(quán)重取值區(qū)間為(0.33,1),在算法當(dāng)前期粒子慣性權(quán)重趨向于后期慣性權(quán)重時(shí),逐漸趨于1,而且在每次迭代過(guò)程中各個(gè)粒子的慣性權(quán)重也不盡相同,越好的粒子獲得的慣性權(quán)重越小,越差的粒子獲得的慣性的權(quán)重值越大。該方法能更好的平衡和局部搜索,提高算法的收斂速度。

1.6 算法流程

上述量子粒子群算法流程如下:

(1) t0,初始化種群Q(0)。

(2) 對(duì)初始化種群的各個(gè)體實(shí)施測(cè)量,得到一組狀態(tài)P(0),并進(jìn)行適應(yīng)度評(píng)估。

(3) While 非結(jié)束條件do。

Begin

① tt+1;

② 對(duì)于Q(t-1)實(shí)施觀測(cè),得到P(t),進(jìn)行適應(yīng)評(píng)估;

③ 比較各解,計(jì)算各解所支配的解的個(gè)數(shù);

④ 計(jì)算極大極小距離,求出各Pareto解的D(x)值;

⑤ 利用基于量子門旋轉(zhuǎn)策略更新Q(t)。

End

2 算法驗(yàn)證及基于某型電臺(tái)的最優(yōu)化仿真

本文改進(jìn)的這種基于粒子群化多目標(biāo)優(yōu)化算法,采用新的距離方法,以保持解群體的分布性能,同時(shí),動(dòng)態(tài)設(shè)置粒子的慣性權(quán)重,有效地保持了算法前期全局搜索和后期局部搜索之間的平衡。以多維0/1背包問(wèn)題為測(cè)試對(duì)象,經(jīng)多次實(shí)驗(yàn)結(jié)果表明,該算法具有較好的收劍性和保持解的分布性。該算法能夠快速搜索到多目標(biāo)優(yōu)化問(wèn)題的Pareto前沿,特別對(duì)多維、復(fù)雜優(yōu)化問(wèn)題提供更有效的方法[10]。

下面以某型電臺(tái)為例,它是基于硬件的平臺(tái),具有有限的參數(shù)和調(diào)整范圍,所有的物理層特性如表1所示。

在受限制的無(wú)線電臺(tái)中,量子粒子群算法也是可行的,設(shè)計(jì)試驗(yàn)由WSGA控制的點(diǎn)對(duì)點(diǎn)無(wú)線電鏈路和作為干擾的第三個(gè)同型號(hào)的無(wú)線電臺(tái)組成。

表1 硬件參數(shù)的配置

參數(shù)范圍參數(shù)范圍

頻率5 730~5 820 MHz編碼速率:1/2,2/3,3/4

功率6~17 dBmTDD29.2%~91%

調(diào)制QPSK,QAM8,QAM16

注:QPSK為正交相移鍵控;TDD為時(shí)分雙工。

試驗(yàn)包括建立一條高流量的初始視頻鏈路,當(dāng)出現(xiàn)干擾時(shí),信號(hào)質(zhì)量迅速下降且變得無(wú)法區(qū)別時(shí),WSGA接著運(yùn)行,目標(biāo)函數(shù)設(shè)置為最小化BER、最小化發(fā)射功率、最大化數(shù)據(jù)速率、電臺(tái)不改變現(xiàn)有的頻率,測(cè)試目的是為了測(cè)試無(wú)線電如何處理其他參數(shù)。

試驗(yàn)中顯示了在測(cè)試中WSGA的良好性能,但仍然希望有更靈活的平臺(tái),這樣就能建立一個(gè)軟件無(wú)線電(SDR)的物理層仿真,具有更多的可調(diào)參數(shù),以及更大的調(diào)整范圍,如表2,表3所示。

表2 仿真參數(shù)

參數(shù)范圍參數(shù)范圍

功率0~30 dBmPSF滾降系數(shù)0.01~1

頻率2 400~2 480 MHzPSF階數(shù)5~10

調(diào)制MPSK,MQAM符號(hào)速率1~20 MSPS

調(diào)制M2~64

表3 仿真試驗(yàn)條件

函數(shù)

權(quán)重最小頻譜占用最大流量干擾避免

BER255100200

帶寬25510255

頻譜效率100200200

功率22510200

數(shù)據(jù)速率100255100

干擾00255

在此時(shí)的無(wú)線電仿真參數(shù)和條件下,目標(biāo)函數(shù)為BER、占用帶寬、功率、數(shù)據(jù)速率以及干擾量。

運(yùn)用算法如表3所示,每個(gè)目標(biāo)都得到了優(yōu)化,每個(gè)結(jié)果BER都為0。

第一試驗(yàn):如圖1所示,將占用頻譜最小化為1 MHz。

第二試驗(yàn):如圖2所示,將流量最大化為72 Mb/s。

第三試驗(yàn):如圖3所示,找到一個(gè)嵌入干擾空隙的解。

圖1 占用頻譜最小化為1MHz

圖2 流量最大化為72 Mb/s

圖3 一個(gè)嵌入干擾空隙的解

3 結(jié) 語(yǔ)

認(rèn)知無(wú)線電的設(shè)計(jì)目標(biāo)是優(yōu)化自身的性能,支持用戶需求。當(dāng)無(wú)線電在達(dá)到具有一定水平的性能,且滿足用戶需求時(shí),對(duì)占用帶寬和電池功率等資源消耗最小時(shí),就實(shí)現(xiàn)了優(yōu)化。本文所討論的算法可解決物理層和鏈路層參數(shù)調(diào)整的一些基礎(chǔ)性問(wèn)題。

參考文獻(xiàn)

[1][美] Bruce A Fette.認(rèn)知無(wú)線電技術(shù)[M].趙知?jiǎng)?鄭仕鏈,譯.北京:科學(xué)出版社,2008.

[2]Mitola J,Maguire G.Cognitive Radio:Making Software Radios more Personal[J].IEEE Personal Communication Magazine,1999,6(4):13-18.

[3]Mitola J.Cognitive Radio for Flexible Mobile Multimedia Communications[J].1999 IEEE International Work-shop on Mobile Multimedia Communications,1999,10(3):15-17.

[4]Ganesan G,Li YG.Cooperation Spectrum Sensing in Cognitive Radio Networks[J].Proceedings of IEEE,2005:137-143.

[5]Mitola J.Cognitive Radio for Flexible Mobile Multimedia Communications[J].Mobile Networks and Applications,2001,6(5):435-441.

[6]Urkowitz H.Energy Detection of Unknown Detection Signals[J].Proceedings of IEEE,1997,55:523-231.

[7]Nuttall A H.Some Integrals involving the Qm Function[J].IEEE Trans.on Information Theory,1975,21(1):95-96.