時(shí)間：2023-07-07 09:20:15
緒論：在尋找寫作靈感嗎？愛發(fā)表網(wǎng)為您精選了8篇多目標(biāo)優(yōu)化概念，愿這些內(nèi)容能夠啟迪您的思維，激發(fā)您的創(chuàng)作熱情，歡迎您的閱讀與分享！
關(guān)鍵詞：多目標(biāo)進(jìn)化算法；人工免疫算法；聚集密度；分布性
中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：1672-7800（2013）012-0067-04
作者簡介：馬春連（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)算法的自身研究成果并不多，主要有基于克隆選擇原理的克隆選擇算法和基于陰性選擇原理的陰性選擇算法等。
Coello Coello等于2002年最早提出將人工免疫系統(tǒng)算法用于求解多目標(biāo)優(yōu)化問題，并陸續(xù)對(duì)其進(jìn)行了改進(jìn)；Luh等于2003年提出了多目標(biāo)免疫算法MOIA；Jiao等于2005年提出免疫克隆多目標(biāo)算法IDC-MA。
關(guān)鍵詞：海洋工程結(jié)構(gòu)多目模糊優(yōu)化
中圖分類號(hào)：K928.44 文獻(xiàn)標(biāo)識(shí)碼： A
一、多目模糊優(yōu)化背景與發(fā)展歷史
1. 模糊優(yōu)化設(shè)計(jì)的背景
是造價(jià)最低,或是達(dá)到某一專項(xiàng)目標(biāo),或是同時(shí)達(dá)到幾項(xiàng)目標(biāo)但在設(shè)計(jì)過程中,時(shí)常會(huì)遇上大量的模糊概念,如/重量不超過...0!/體積不大于...0等等由于缺乏處理手段和方法而把這些概念當(dāng)成確定性量來對(duì)待,這樣把設(shè)計(jì)的約束條件和目標(biāo)函數(shù)人為簡單化,以至于設(shè)計(jì)結(jié)果不符合要求隨著設(shè)計(jì)學(xué)的發(fā)展,大量的模糊信息需要定量描述,使設(shè)計(jì)達(dá)到真正的優(yōu)化目的"在普通優(yōu)化的基礎(chǔ)上引入模糊數(shù)學(xué),建立在模糊集理論基礎(chǔ)上的模糊優(yōu)化設(shè)計(jì)方法產(chǎn)生了模糊優(yōu)化設(shè)計(jì)為解決具有上述模糊概念的優(yōu)化問題提供了可行的方法和有效的手段模糊優(yōu)化設(shè)計(jì)的概念首先是別爾曼和扎德提出來的,提出的背景主要有以下幾個(gè)方面:(l)事物間的差異中介過渡給事物帶來模糊性;對(duì)事物研究的定量化會(huì)遇上大量模糊因素:所研究的事物涉及多方面的模糊因素;以及在計(jì)算機(jī)應(yīng)用領(lǐng)域中會(huì)考慮對(duì)模糊信息的識(shí)別和處理等等"這些都會(huì)給優(yōu)化設(shè)計(jì)帶來大量的模糊因素,導(dǎo)致模糊優(yōu)化問題的出現(xiàn)(2)對(duì)于一項(xiàng)工程設(shè)計(jì)會(huì)發(fā)現(xiàn)設(shè)計(jì)比分析涉及的因素更多,尤其是人文因素例如,一種新產(chǎn)品的設(shè)計(jì),不僅要滿足工作要求和技術(shù)性能指標(biāo),而且經(jīng)濟(jì)!可靠!使用條件性也是不可忽視的因素其實(shí),優(yōu)化設(shè)計(jì)的發(fā)展也是向多方面發(fā)展,已經(jīng)打破了原先只在物理!幾何性質(zhì)上做文章的格局當(dāng)今社會(huì)的發(fā)展以人為本,在理工科高等教育中加強(qiáng)人文知識(shí)教育也是為了使理工科研究不能脫離人文,所以人文因素已經(jīng)滲透于整個(gè)設(shè)計(jì)過程"人文因素的模糊性是優(yōu)化設(shè)計(jì)遇到的主要問題,必會(huì)產(chǎn)生模糊優(yōu)化的問題顯然,模糊優(yōu)化設(shè)計(jì)的產(chǎn)生是優(yōu)化設(shè)計(jì)領(lǐng)域的一次革命,大大地促進(jìn)了優(yōu)化設(shè)計(jì)的發(fā)展,為解決優(yōu)化設(shè)計(jì)中出現(xiàn)的問題提供了理想的方法。
2模糊優(yōu)化設(shè)計(jì)的產(chǎn)生和發(fā)展歷史
隨著科學(xué)與科學(xué)研究的發(fā)展,從物理發(fā)展到事理,從物態(tài)進(jìn)展到事態(tài)的研究,傳統(tǒng)的經(jīng)典數(shù)學(xué)已顯得蒼白無力,或者說過去那些與數(shù)學(xué)毫無糊數(shù)學(xué)誕生于1965年,美國加利福尼亞大學(xué)控制論專家查德教授(LA.zdahe)發(fā)表了著名論文-下uzyzsets0(模糊集合),提出模糊集合的思想,給出模糊現(xiàn)象的模型!模糊問題的定量表示方法及數(shù)學(xué)處理方法"他指出,刻畫一個(gè)模型集合時(shí),不必指明哪些元素屬于它,哪些元素不屬于它,只需對(duì)給定范圍內(nèi)的各元素確定一個(gè)"到1之間的實(shí)數(shù),用它表明這個(gè)元素以多大程度屬于這個(gè)集合,這個(gè)數(shù)就叫作該元素對(duì)這個(gè)集合的隸屬度"例如,30歲的人肯定不算老年,他對(duì)/老年人0這個(gè)概念的隸屬度為仇50歲的人屬于/老年人0的程度近于0.5;70歲的人為老年人,他對(duì)/老年人0的隸屬度為1"這說明/中年0和/老年0的概念是相互粘連的,它們之間沒有一條絕對(duì)分明的界限,而是有一個(gè)連續(xù)過渡的過程"查德正是用隸屬度這個(gè)概念表現(xiàn)處于中介過渡的事物對(duì)差異一方的傾向程度,這就是他創(chuàng)立模糊集合論時(shí)提出的新思想"模糊集合論把原來某元素對(duì)于集合要么/屬于0,要么/不屬于0的確定性關(guān)系,推廣到元素對(duì)于集合按/一定程度0/屬于0或/不屬于0的確定關(guān)系(即在一定程度上/屬于0或/不屬于,.)以此就標(biāo)志了模糊理論的產(chǎn)生,模糊數(shù)學(xué)就是從數(shù)學(xué)上來刻畫和研究客觀世界中存在的模糊量,即從量上來描述模糊現(xiàn)象,并以之為突破點(diǎn)建立了研究模糊現(xiàn)象的基本理論模糊數(shù)學(xué)是研究和處理模糊性現(xiàn)象的數(shù)學(xué)所謂模糊性,是指客觀事物在中介過渡時(shí)呈現(xiàn)的概念劃分上的不確定性,即/亦此亦彼0性客觀世界中存在著大量的模糊性現(xiàn)象,它們很難找到明確的界限,這樣的概念叫做模糊概念模糊概念不是不科學(xué)的概念,它大量地存在于物理學(xué)!化學(xué)和生物學(xué)中,在經(jīng)濟(jì)和人文科學(xué)中表現(xiàn)尤為突出,人腦的識(shí)別!判斷以及概念的形成過程都具有模糊性為了描述模糊概念,滿足各門學(xué)科的數(shù)學(xué)化!定量化要求,這就是模糊數(shù)學(xué)產(chǎn)生的思想基礎(chǔ)"隨著模糊數(shù)學(xué)的誕生,一種全新的模糊論方法學(xué)也就發(fā)展起來了"模糊論是建立在(l)事物的不確定性(隨機(jī)性和模糊性);(2)廣義設(shè)計(jì)中的模糊性,即定量地研究從狹義設(shè)計(jì)到廣義設(shè)計(jì)中,必然要遇到大量的模糊概念:(3)復(fù)雜化和精確化之間的矛盾"模糊數(shù)學(xué)由于打破了形而上學(xué)的束縛,即認(rèn)識(shí)到事物的/非此即彼0的明晰性形態(tài),又認(rèn)識(shí)到事物的/亦此亦彼0的過渡性形態(tài),因此模糊理論的產(chǎn)生就在數(shù)學(xué)領(lǐng)域本身以及許多的實(shí)用領(lǐng)域里得了廣泛迅速的發(fā)展和應(yīng)用模糊理論是在模糊數(shù)學(xué)基礎(chǔ)上發(fā)展起來的一門新學(xué)科,經(jīng)過近些年來的發(fā)展,己經(jīng)形成為一門新的應(yīng)用技術(shù)學(xué)科,到20世紀(jì)90年代,己經(jīng)形成了具有完整體系和鮮明特點(diǎn)的模糊拓?fù)鋵W(xué)!框架日趨成熟的模糊隨機(jī)數(shù)學(xué)!模糊分析學(xué)以及模糊邏輯理論,并滲透到各個(gè)學(xué)科領(lǐng)域,如:人工智能!管理信息!機(jī)械制造!自動(dòng)化控制等等,應(yīng)用相當(dāng)廣泛。
二、多目模糊優(yōu)化設(shè)計(jì)優(yōu)點(diǎn):
(1)優(yōu)化設(shè)計(jì)方法能夠加速設(shè)計(jì)進(jìn)度,節(jié)省工程造價(jià)優(yōu)化設(shè)計(jì)與傳統(tǒng)的結(jié)構(gòu)設(shè)計(jì)相比較,一般情況下,對(duì)簡單的構(gòu)件可節(jié)省工程造價(jià)的3一5%,對(duì)較復(fù)雜的結(jié)構(gòu)可達(dá)10%,對(duì)新型結(jié)構(gòu)可望達(dá)2000/(2)結(jié)構(gòu)優(yōu)化設(shè)計(jì)有較大的伸縮性作為優(yōu)化設(shè)計(jì)中的設(shè)計(jì)變量,可以從一兩個(gè)到幾十,上百個(gè)"作為優(yōu)化設(shè)計(jì)的工程對(duì)象,可以是單個(gè)的構(gòu)件,整個(gè)建筑物甚至建筑群設(shè)計(jì)者可以根據(jù)需要和本人的經(jīng)驗(yàn)加以選擇0的大小,為設(shè)計(jì)者進(jìn)一步改進(jìn)結(jié)構(gòu)設(shè)計(jì)指出方向"(4)某些優(yōu)化設(shè)計(jì)方法(如網(wǎng)格法)能夠提供一系列可行設(shè)計(jì)直至優(yōu)化設(shè)計(jì),為設(shè)計(jì)者決策時(shí)提供方便(5)設(shè)計(jì)者能夠利用優(yōu)化設(shè)計(jì)方法進(jìn)一步貫徹設(shè)計(jì)意圖"例如在鋼筋混凝土結(jié)構(gòu)的優(yōu)化設(shè)計(jì)中,若設(shè)計(jì)者在設(shè)計(jì)中想相對(duì)的少用些鋼筋,多用些水泥,只要修改一下目標(biāo)函數(shù)就可以了"
三、多目模糊優(yōu)化設(shè)計(jì)
1.多目模糊優(yōu)化設(shè)計(jì)
具體說來,就是給出該問題的數(shù)學(xué)模型"模糊優(yōu)化的數(shù)學(xué)模型和普通優(yōu)化的數(shù)學(xué)模型一樣,也是從設(shè)計(jì)變量,目標(biāo)函數(shù)和約束條件這三方面給出的模糊優(yōu)化的設(shè)計(jì)變量,仍然是決定設(shè)計(jì)方案的!可由設(shè)計(jì)人員調(diào)整的!獨(dú)立變化的參數(shù)它們或者是決定形狀大小的幾何參數(shù),或者是決定結(jié)構(gòu)性能的物理參數(shù)"這些參數(shù),過去都視為確定性的,但嚴(yán)格說來,大多具有不同程度的模糊性"如結(jié)構(gòu)設(shè)計(jì)中的動(dòng)載系數(shù),抗震設(shè)計(jì)中的地震烈度,動(dòng)態(tài)設(shè)計(jì)中的阻尼參數(shù)等它們很難由一個(gè)確定的值來給出,都有一個(gè)從完全是到完全非的中介過渡過程,都具有不同程度的模糊性模糊優(yōu)化的目標(biāo)函數(shù),仍然是衡量設(shè)計(jì)方案優(yōu)劣的某一個(gè)指標(biāo)(單目標(biāo)函數(shù))或某幾個(gè)指標(biāo)(多目標(biāo)函數(shù))/優(yōu)0和/劣0本身就是個(gè)模糊概念,沒有一個(gè)確定的界限和標(biāo)準(zhǔn)通常,我們說:要使某項(xiàng)指標(biāo)達(dá)到某個(gè)值附近,或達(dá)到某一范圍,或越小越好等等實(shí)際上,都說的是目標(biāo)函數(shù)的模糊性另外,由于目標(biāo)函數(shù)是設(shè)計(jì)變量的函數(shù),當(dāng)考慮了設(shè)計(jì)變量的模糊性時(shí),目標(biāo)函數(shù)也必然是模糊的"模糊優(yōu)化的約束條件,仍然是限制設(shè)計(jì)變量取值的條件,也即是設(shè)計(jì)方案所必須滿足的條件"這些約束條件.
2. 拓?fù)鋬?yōu)化方法
拓?fù)鋬?yōu)化設(shè)計(jì)是現(xiàn)代創(chuàng)新設(shè)計(jì)領(lǐng)域中的重要核心技術(shù)與定量設(shè)計(jì)方法,是傳統(tǒng)的尺寸設(shè)計(jì)和形狀設(shè)計(jì)的擴(kuò)展與延伸它的基本原理是在給定材料重量的條件下,通過優(yōu)化設(shè)計(jì)與數(shù)值求解過程獲得具有最大剛度的結(jié)構(gòu)布局形式及構(gòu)件尺寸自1988年丹麥學(xué)者Bnedsoe與美國學(xué)者Kikuhci提出結(jié)構(gòu)拓?fù)鋬?yōu)化設(shè)計(jì)基本理論以來可以說近二十年間結(jié)構(gòu)設(shè)計(jì)領(lǐng)域發(fā)生了革命性的變化"基于結(jié)構(gòu)設(shè)計(jì)要求的剛度一重量一振動(dòng)多準(zhǔn)則優(yōu)化,研究使用保凸近似與凸規(guī)劃建立快速有效極大極小值優(yōu)化算法以及通用非線性廣義加權(quán)法隊(duì)將凸規(guī)劃對(duì)偶求解算法與結(jié)構(gòu)多目標(biāo)優(yōu)化設(shè)計(jì)相結(jié)合并應(yīng)用于拓?fù)鋬?yōu)化設(shè)計(jì)該研究方向目前已成為國際工程結(jié)構(gòu)與產(chǎn)品創(chuàng)新設(shè)計(jì)領(lǐng)域的研究熱點(diǎn)"目前拓?fù)鋬?yōu)化設(shè)計(jì)方法作為一項(xiàng)關(guān)鍵技術(shù)已應(yīng)用于衛(wèi)星!飛機(jī)!汽車的關(guān)鍵承力結(jié)構(gòu),薄壁件結(jié)構(gòu)的加強(qiáng)筋,布局設(shè)計(jì)以及微機(jī)械系統(tǒng)(MEMs}!柔性機(jī)構(gòu)布局設(shè)計(jì)等多個(gè)領(lǐng)域因此從軍事應(yīng)用及國防需求前景上講,拓?fù)鋬?yōu)化設(shè)計(jì)方法具有直接而廣泛的應(yīng)用價(jià)值
3.多目標(biāo)協(xié)調(diào)優(yōu)化
1994年,Kroo與Balling!sobieski等人提出了協(xié)調(diào)優(yōu)化(eo),1997年,工甲peta和Rneuad將該方法修正后用于解決多目標(biāo)優(yōu)化問題并對(duì)該方法的三種不同的版木做了比較"這種方法的中心思想是:把多目標(biāo)問題劃分成一個(gè)個(gè)的次問題,然后逐步優(yōu)化,直到最終得到優(yōu)化解"
4.模糊優(yōu)化方法
1992年,Allne探討了一種能夠非常有效地求解分層設(shè)計(jì)問題的模糊優(yōu)化方法,顯示了該方法解決綜合優(yōu)化設(shè)計(jì)問題的優(yōu)點(diǎn)該方法就是利用模糊集理論,構(gòu)造目標(biāo)函數(shù)!約束函數(shù)和設(shè)計(jì)變量的隸屬函數(shù),進(jìn)而轉(zhuǎn)化為單目標(biāo)函數(shù)進(jìn)行優(yōu)化考慮模糊因素的設(shè)計(jì)問題有以下好處:1使用模糊關(guān)系描述某此問題比確定性描述更準(zhǔn)確;o考慮問題的模糊性能有效地拓展求解空間;
5.隨著優(yōu)化設(shè)計(jì)的深入,
關(guān)鍵詞 多目標(biāo)優(yōu)化 粒子群 遺傳算法 蟻群算法 人工免疫系統(tǒng)
中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A
一、背景
多目標(biāo)優(yōu)化（Multiobjective OptimizaTionProblem，MOP）是最優(yōu)化的一個(gè)重要分支，多目標(biāo)問題中的各目標(biāo)往往是有著沖突性的，其解不唯一，如何獲得最優(yōu)解成為多目標(biāo)優(yōu)化的一個(gè)難點(diǎn)，目前還沒有絕對(duì)成熟與實(shí)用性好的理論。近年來，粒子群算法、遺傳算法、蟻群算法、人工免疫系統(tǒng)、等現(xiàn)代技術(shù)也被應(yīng)用到多目標(biāo)優(yōu)化中，使多目標(biāo)優(yōu)化方法取得很大進(jìn)步。本文將其中四種多目標(biāo)優(yōu)化的進(jìn)化算法進(jìn)行一個(gè)簡單的介紹和比較。
二、不同算法介紹
（一）多目標(biāo)遺傳算法。
假定各目標(biāo)的期望目標(biāo)值與優(yōu)先順序已給定，從優(yōu)先級(jí)最高的子目標(biāo)向量開始比較兩目標(biāo)向量的優(yōu)劣性，從目標(biāo)未滿足的子目標(biāo)元素部分開始每一級(jí)子目標(biāo)向量的優(yōu)劣性比較，最后一級(jí)子目標(biāo)向量中的各目標(biāo)分量要全部參與比較。給定一個(gè)不可實(shí)現(xiàn)的期望目標(biāo)向量時(shí)，向量比較退化至原始的Pareto排序，所有目標(biāo)元素都必須參與比較。算法運(yùn)行過程中，適應(yīng)值圖景可由不斷改變的期望目標(biāo)值改變，種群可由此被引導(dǎo)并集中至某一特定折中區(qū)域。當(dāng)前種群中（基于Pareto最優(yōu)概念）優(yōu)于該解的其他解的個(gè)數(shù)決定種群中每一個(gè)向量解的排序。
（二）人工免疫系統(tǒng)。
人工免疫算法是自然免疫系統(tǒng)在進(jìn)化計(jì)算中的一個(gè)應(yīng)用，將抗體定義為解，抗原定義為優(yōu)化問題，抗原個(gè)數(shù)即為優(yōu)化子目標(biāo)的個(gè)數(shù)。免疫算法具有保持個(gè)體多樣性、搜索效率高、群體優(yōu)化、避免過早收斂等優(yōu)點(diǎn)。其通用的框架是：將優(yōu)化問題的可行解對(duì)應(yīng)抗體，優(yōu)化問題的目標(biāo)函數(shù)對(duì)應(yīng)抗原，Pareto最優(yōu)解被保存在記憶細(xì)胞集中，并采取某種機(jī)制對(duì)記憶集進(jìn)行不斷更新，進(jìn)而獲得分布均勻的Pareto最優(yōu)解。
（三）多目標(biāo)PSO約束算法。
將粒子群優(yōu)化算法運(yùn)用于優(yōu)化問題，關(guān)鍵是如何確定群體全局最優(yōu)位置pbest和每個(gè)粒子的最優(yōu)位置gbest。由于多目標(biāo)優(yōu)化問題并無單個(gè)的最優(yōu)解，所以不能直接確定gbest，pbest。PSO算法的優(yōu)勢(shì)在于：第一，有著高效的搜索能力。第二，并行地同時(shí)搜索多個(gè)非劣解。第三，有著較好的通用性。PSO算法在處理多目標(biāo)約束優(yōu)化問題時(shí)，主要是解決自身和群體最佳位置，對(duì)于群體最佳位置的選擇，一是所得到的解要在Pareto邊界上具有一定得分散性，二是要求算法收斂速度好。對(duì)于自身最佳位置的選擇要求是通過較少的比較次數(shù)達(dá)到非劣解的更新。PSO算法在處理約束時(shí)，多采用懲罰函數(shù)法。
（四）多目標(biāo)蟻群算法。
多目標(biāo)蟻群算法的思想是：根據(jù)目標(biāo)函數(shù)的數(shù)目將螞蟻分成若干子群體，為每個(gè)子群體分配一個(gè)目標(biāo)函數(shù)，在其他子群體優(yōu)化結(jié)果的基礎(chǔ)上通過Pareto過濾器來獲得均衡解。基本步驟如下：
1、轉(zhuǎn)移概率：對(duì)每一個(gè)目標(biāo)k需要考慮一些信息素軌跡 k，在算法的每一代中，每一只螞蟻都計(jì)算一組權(quán)重p=（p1，p2，…，pk），并且同時(shí)使用啟發(fā)式信息和信息素軌跡。
2、局部信息素更新：當(dāng)每只螞蟻?zhàn)咄阛ij邊之后，對(duì)每個(gè)目標(biāo)k我們采取更新：
ijk=（1- ） ijk+ 0
其中， 0是初始信息素的值， 是信息素?fù)]發(fā)速率。
3、全局信息素更新：對(duì)每個(gè)目標(biāo)k，在當(dāng)前代只對(duì)產(chǎn)生最好和第二好的解進(jìn)行信息素更新，使用規(guī)則如下：
ijk=（1- ） ijk+ ijk
4、設(shè)置Pareto解集過濾器：
設(shè)置Pareto解集過濾器來存放算法運(yùn)行時(shí)產(chǎn)生的Pareto解。
三、結(jié)論
四種進(jìn)化算的優(yōu)缺點(diǎn)總結(jié)如下：
多目標(biāo)遺傳算法：有著良好的魯棒性和優(yōu)越性，在擁擠選擇算子時(shí)，限制種群大小使用擁擠比較過程，使算法失去了收斂性。人工免疫系統(tǒng)：可以得到優(yōu)化問題的多個(gè)Pareto最優(yōu)解，算法運(yùn)行缺乏穩(wěn)定性。多目標(biāo)PSO約束算法：能夠?qū)崿F(xiàn)對(duì)多維復(fù)雜空間的高效搜索，研究還處于起步階段。多目標(biāo)蟻群算法：Pareto前沿均勻性以及Pareto解集多樣性，早熟停滯和在控制參數(shù)難以確定。
（作者單位： 四川大學(xué)商學(xué)院）
參考文獻(xiàn)：
[1]馬小姝.傳統(tǒng)多目標(biāo)優(yōu)化方法和多目標(biāo)遺傳算法的比較綜述[J].電氣傳動(dòng)自動(dòng)化 ，2010.
[2]謝濤， 陳火旺.多目標(biāo)優(yōu)化與決策問題的演化算法[J].中國工程科學(xué)，2002.
[3]王魯，羅婷，趙琳，段海峰.基于遺傳算法的多目標(biāo)優(yōu)化技術(shù)[J].科技廣場(chǎng)，2009.
[4]樊紀(jì)山， 王經(jīng)卓.基于人工免疫系統(tǒng)的多目標(biāo)優(yōu)化算法的研究[J].福建電腦2008.
[5]池元成，蔡國飆.基于蟻群算法的多目標(biāo)優(yōu)化[J].計(jì)算機(jī)工程，2009.
[6]孔翔宇.基于蟻群算法的多目標(biāo)優(yōu)化問題研究[J]四川理工學(xué)院學(xué)報(bào)，2010.
關(guān)鍵詞： 發(fā)電權(quán)交易；模型；效益；能耗；Pareto；PSO
中圖分類號(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購買的電量， 為第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)：
[1]國務(wù)院辦公廳，國務(wù)院辦公廳關(guān)于轉(zhuǎn)發(fā)發(fā)展改革委等部門《節(jié)能發(fā)電調(diào)度辦法（試行）》的通知（[2007]53號(hào)文）[Z].2007.08.02.
關(guān)鍵詞：飛機(jī)除冰；多目標(biāo)；遺傳；調(diào)度
中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）26-5978-03
北方機(jī)場(chǎng)中，由于冬季天氣寒冷，飛機(jī)在機(jī)場(chǎng)停留過夜時(shí)因?yàn)闈穸群吞鞖庖蛩卦斐娠w機(jī)表面結(jié)冰現(xiàn)象。飛機(jī)表面結(jié)冰會(huì)對(duì)飛機(jī)氣動(dòng)外形帶來不好的影響，不僅會(huì)增加飛機(jī)飛行阻力，造成飛機(jī)升力損失，而且會(huì)改變飛機(jī)蒙皮的力學(xué)特性，嚴(yán)重時(shí)甚至造成飛機(jī)事故發(fā)生。因此，飛機(jī)除冰受到了國內(nèi)外經(jīng)常的廣泛注意，飛機(jī)除冰操作也是機(jī)場(chǎng)機(jī)務(wù)人員的常備工作之一。對(duì)機(jī)除冰來說，國內(nèi)大多數(shù)機(jī)場(chǎng)采用的是“隨到隨除”的分散式除冰方式，該方法簡單有效，但是由于缺乏調(diào)度管理，存在除冰作業(yè)環(huán)境污染嚴(yán)重，除冰效率低等諸多問題。針對(duì)此問題，該文在Pareto多目標(biāo)解的理論基礎(chǔ)之上，提出了基于費(fèi)用最少和除冰作業(yè)時(shí)間最短的多目標(biāo)搜索飛機(jī)除冰方法。
1 Pareto多目標(biāo)算法
Francis 首先提出了多目標(biāo)最優(yōu)概念，Pareto在Francis的基礎(chǔ)上提出了多目標(biāo)最優(yōu)的定義，也成為Pareto最優(yōu)。在一個(gè)有k個(gè)目標(biāo)函數(shù)最大化的問題中，決策向量[x*∈F]是Pareto最優(yōu)是指不存在另外一個(gè)決策向量[x∈F]同時(shí)滿足式（1）
[fi（x）≥fj（x*），?i∈{1，2，...，k}fi（x）
在最大化問題中稱決策向量x優(yōu)于y，或者支配y，需要滿足式（2）。
[fi（x）≥fj（y），?i∈{1，2，...，k}] （2）
在式（1）和式（2）的頂一下，多目標(biāo)優(yōu)化得到的結(jié)果是一個(gè)解集，該解集也被稱為Pareto最優(yōu)解集，該解集中的所有的決策向量都被稱為非劣解或者非支配解。使用Pareto解集中的所有非支配解可以做出該解集的Pareto前沿，如果多目標(biāo)問題只存在兩個(gè)目標(biāo)[f1]和[f2]，且這兩個(gè)目標(biāo)值都是越大越優(yōu)，則該解集的Pareto前沿如圖1所示1-2。
其中，實(shí)線和虛線包圍的區(qū)域稱為多目標(biāo)函數(shù)值域。
2 飛機(jī)除冰多目標(biāo)模型
假設(shè)機(jī)場(chǎng)中有多種待除冰飛機(jī)和多種不同的除冰液運(yùn)載量的除冰車，飛機(jī)除冰優(yōu)化調(diào)度問題的目的就是為待除冰飛機(jī)分配除冰車輛，從而使得調(diào)度模型能夠在有限的時(shí)間和除冰車輛中為更多的飛機(jī)除冰。在飛機(jī)除冰調(diào)度模型中，待除冰飛機(jī)從除冰地點(diǎn)入口根據(jù)起飛順序依次進(jìn)入除冰場(chǎng)所，除冰車輛根據(jù)優(yōu)化調(diào)度模式對(duì)飛機(jī)進(jìn)行除冰操作，在除冰車輛完成對(duì)該飛機(jī)的除冰操作后從出口劃出3-4。
除冰調(diào)度的數(shù)學(xué)模型如式3所示。
[minT=i=1mFivk=1mxik+M?k=1mΦkminC=i=1mCostis.t.Φk=i=1nFixikk=1mxikqi] （3）
其中，m為除冰車輛數(shù)量，n為除冰飛機(jī)數(shù)量， [Fi]為第i臺(tái)車輛的除冰液存儲(chǔ)量，v為除冰液噴灑速度，[qi]為除冰液添加速度，[xik]為除冰操作決策變量，[xik]為1時(shí)表示除冰車輛[k]是否為飛機(jī)[i]除冰，為0表示不除冰，[Costi]為除冰車操作費(fèi)用。
3 算法流程
多目標(biāo)遺傳算法的優(yōu)化目標(biāo)為除冰費(fèi)用和除冰時(shí)間同時(shí)達(dá)到最小，其中算法的交叉操作為雙點(diǎn)整數(shù)交叉，算法的變異操作為單點(diǎn)整數(shù)變異，在算法操作的過程中，根據(jù)支配集合理論，不斷的更新記錄非支配解集中的個(gè)體，并且根據(jù)擁擠度等控制學(xué)習(xí)進(jìn)化的方向和非支配解集中解的個(gè)數(shù)，多目標(biāo)遺傳算法的計(jì)算流程如圖2所示。
4 仿真實(shí)驗(yàn)
為了驗(yàn)證本文提出的算法的有效性，在MATLAB中進(jìn)行仿真實(shí)驗(yàn)，仿真實(shí)驗(yàn)的參數(shù)為除冰車輛有10輛，飛機(jī)數(shù)為20架，除冰位有4個(gè)，每架飛機(jī)除冰液需求和除冰車運(yùn)載量如表1所示。
遺傳算法的參數(shù)設(shè)置為，種群數(shù)為100，迭代次數(shù)為100，交叉概率為0.3，變異概率為0.1，仿真過程中記錄的非支配解中兩個(gè)目標(biāo)的變化如圖3所示。
算法最終得到的多目標(biāo)解集如圖4所示。
從圖3和圖4中可以看出，該文提出的基于遺傳算法的飛機(jī)除冰調(diào)度多目標(biāo)算法能夠在較復(fù)雜的問題中取得良好的結(jié)果。
5 結(jié)論
飛機(jī)除冰調(diào)度問題是一個(gè)具有較好實(shí)際應(yīng)用前景的問題，該文提出了一種基于多目標(biāo)算法的飛機(jī)除冰多目標(biāo)調(diào)度模型，該模型在算法建模的基礎(chǔ)上，以除冰時(shí)間和除冰費(fèi)用最小為運(yùn)行目標(biāo)，采用多目標(biāo)遺傳算法搜索得到非支配解集。經(jīng)過仿真實(shí)驗(yàn)表明，該算法取得了良好的調(diào)度效果，為飛機(jī)除冰操作提供了一個(gè)新的思路。
參考文獻(xiàn)：
[1] 趙亮.一種改進(jìn)的遺傳多目標(biāo)優(yōu)化算法及其應(yīng)用[J].中國電機(jī)工程學(xué)報(bào)，2008（1）
[2] 劉立波，曾雪梅.遺傳多目標(biāo)優(yōu)化算法及其引用[J]. 電腦知識(shí)與技術(shù)，2012（07）.
關(guān)鍵詞動(dòng)態(tài)多目標(biāo)，聚類，預(yù)測(cè)，進(jìn)化算法
中圖分類號(hào)O224文獻(xiàn)標(biāo)識(shí)碼A文章編號(hào)1000-2537（2014）02-0056-06
現(xiàn)實(shí)世界中的許多優(yōu)化問題都是動(dòng)態(tài)多目標(biāo)優(yōu)化問題（dynamic multi-objective optimization problems，簡稱DMOPs），多個(gè)目標(biāo)之間經(jīng)常沖突，同時(shí)目標(biāo)函數(shù)、約束函數(shù)和相關(guān)參數(shù)都可能隨著時(shí)間的變化而改變，如何跟蹤變化后新的最優(yōu)解集是求解動(dòng)態(tài)多目標(biāo)優(yōu)化問題的主要難點(diǎn)[1].在處理DMOPs上，靜態(tài)的方法具有明顯的局限性.傳統(tǒng)的進(jìn)化算法目標(biāo)是使種群逐漸收斂，最終得到Pareto最優(yōu)解集[2-3].而種群一旦收斂，種群的多樣性減少，很難適應(yīng)新的環(huán)境變化.因此，只有對(duì)靜態(tài)算法加以改進(jìn)，才能更好地適應(yīng)于動(dòng)態(tài)環(huán)境[4].
近些年來，研究者們?cè)陟o態(tài)算法的基礎(chǔ)上設(shè)計(jì)了許多新的方法來求解DMOPs[5-8]，這些方法大多集中在保持種群多樣性上，通過隨機(jī)移民，動(dòng)態(tài)遷移，超變異和多種群等策略增加種群多樣性，使新的種群具有響應(yīng)環(huán)境變化的能力.然而這些方法是一種隨機(jī)的、不確定的多樣性保持策略，不能為適應(yīng)新的環(huán)境提供正確的引導(dǎo)，因此具有盲目性，收斂速度是存在的主要問題.
如何充分利用歷史信息，通過預(yù)測(cè)為當(dāng)前環(huán)境下的種群進(jìn)化提供正確的引導(dǎo)已成為求解DMOPs的又一新的發(fā)展趨勢(shì).目前，這類方法已受到了研究者的廣泛關(guān)注.2006年，Hatzakis等人提出了一種前饋法[9]，該方法記錄目標(biāo)空間相鄰歷史Pareto前沿面上的邊界點(diǎn)信息，通過自回歸模型預(yù)測(cè)新的最優(yōu)解集的位置，但是該方法僅記錄歷史解集上邊界點(diǎn)的信息并加以預(yù)測(cè)，采用的預(yù)測(cè)模型提供的信息有限，未能充分考慮環(huán)境變化之間可能存在的關(guān)聯(lián)性，因而影響了預(yù)測(cè)效果.2011年，彭星光等人提出了一種基于Pareto解集關(guān)聯(lián)與預(yù)測(cè)的動(dòng)態(tài)多目標(biāo)進(jìn)化算法[10]，然而該方法僅根據(jù)相鄰時(shí)間序列上的解集關(guān)聯(lián)性進(jìn)行預(yù)測(cè)，并且僅預(yù)測(cè)超塊中的代表性個(gè)體，不能預(yù)測(cè)新的最優(yōu)解集的形狀，當(dāng)環(huán)境發(fā)生較大程度的變化時(shí)，預(yù)測(cè)的解集將出現(xiàn)偏差.因此，怎樣設(shè)計(jì)一個(gè)更為精確的預(yù)測(cè)模型仍是現(xiàn)在的研究重點(diǎn).
基于以上分析，為了避免盲目地增加種群多樣性，并充分利用歷史信息，提高預(yù)測(cè)模型的準(zhǔn)確性，使其能適應(yīng)于不同程度的環(huán)境變化，本文提出一種基于聚類預(yù)測(cè)模型的動(dòng)態(tài)多目標(biāo)進(jìn)化算法（A dynamic multi-objective evolutionary algorithm based on cluster prediction model，簡稱CPM-DMOEA），通過對(duì)種群聚類建立預(yù)測(cè)模型，將對(duì)每個(gè)子類的預(yù)測(cè)分為對(duì)中心點(diǎn)的預(yù)測(cè)和對(duì)形狀的預(yù)測(cè)，從而產(chǎn)生新的預(yù)測(cè)種群.在動(dòng)態(tài)多目標(biāo)優(yōu)化算法的整體框架下進(jìn)行迭代，通過標(biāo)準(zhǔn)動(dòng)態(tài)測(cè)試問題進(jìn)行仿真比較，實(shí)驗(yàn)結(jié)果充分驗(yàn)證了所提算法的有效性.
1優(yōu)化問題及相關(guān)概念
4結(jié)論
本文提出了一種基于聚類預(yù)測(cè)模型的動(dòng)態(tài)多目標(biāo)優(yōu)化算法，算法通過建立聚類預(yù)測(cè)模型，對(duì)種群進(jìn)行分段預(yù)測(cè)，提高了預(yù)測(cè)解集的分布性和廣泛性.根據(jù)歷史信息預(yù)測(cè)每個(gè)子類的中心點(diǎn)和形狀，從而在環(huán)境變化后產(chǎn)生整個(gè)新的初始種群.預(yù)測(cè)產(chǎn)生的新種群能有效地對(duì)新環(huán)境下的PS潛在區(qū)域進(jìn)行探索，加速了算法在新環(huán)境下的收斂.利用三個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)多目標(biāo)測(cè)試函數(shù)，比較了CPM-DMOEA與其他三種動(dòng)態(tài)多目標(biāo)優(yōu)化算法，分析結(jié)果表明了本文算法的有效性，能更好地適應(yīng)不同程度的環(huán)境變化，快速地跟蹤新的Pareto最優(yōu)解集.
未來將把CPM-DMOEA算法應(yīng)用于更多的實(shí)際問題中，以進(jìn)一步分析其在不同的動(dòng)態(tài)環(huán)境中的表現(xiàn)，不斷地改善算法的性能.
參考文獻(xiàn)：
[1]FARINA M， DEB KK， AMATO P. Dynamic multiobjective optimization problems： test cases， approximations， and applications[J]. IEEE Trans Evolut Comput， 2004，8（5）：425-442.
[2]鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社， 2007.
[3]COELLO C A， VAN VELDHUIZEN D A， LAMONT G B. Evolutionary algorithms for solving multi-objective problems[M]. New York： Springer-Verlag， 2007.
[4]NGUYEN T T， YANG S X， BRANKE J. Evolutionary dynamic optimization： A survey of the state of the art[J]. Swarm Evolut Comput， 2012（6）：1-24.
[5]尚榮華， 焦李成， 公茂果， 等. 免疫克隆算法求解動(dòng)態(tài)多目標(biāo)優(yōu)化問題[J]. 軟件學(xué)報(bào)， 2007，18（11）：2700-2711.
[6]DEB K， RAO U V， KARTHIK S. Dynamic multi-objective optimization and decision-making using modified NSGA-Ⅱ-a case study on hydro-thermal power scheduling[D]. in Evolutionary Multi-Criterion Optimization （EMO）， Berlin： Springer， 2007.
[7]劉淳安，王宇平.基于新模型的動(dòng)態(tài)多目標(biāo)優(yōu)化進(jìn)化算法[J].計(jì)算機(jī)研究與發(fā)展， 2008，45（4）：603-611.
[8]GOH C K， TAN K C. A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization[J]. IEEE Trans Evolut Comput， 2009，13（1）：103-127.
[9]武燕，劉小雄，池程芝.動(dòng)態(tài)多目標(biāo)優(yōu)化的預(yù)測(cè)遺傳算法[J].控制與決策， 2013，28（5）：677-682.
[10]彭星光， 徐德民， 高曉光. 基于Pareto 解集關(guān)聯(lián)與預(yù)測(cè)的動(dòng)態(tài)多目標(biāo)進(jìn)化算法[J].控制與決策， 2011，26（4）：615-618.
[11]YAO X， LIU Y， LIN G. Evolutionary programming made faster[J]. IEEE Trans Evolut Comput， 1999，3（2）：82-102.
[12]HILLERMEIER C. Nonlinear multiobjective optimization―a generalized homotopy approach[M]. Boston： Birkhauser， 2001.
本文基于大自然進(jìn)化過程中種群之間、種群與環(huán)境之間的在進(jìn)化過程中的協(xié)同作用，提出一種個(gè)體之間相互競(jìng)爭(zhēng)和協(xié)助的協(xié)同進(jìn)化算法CCEA（Coexistence co-evolutionary Algorithm）。基本思想為通過優(yōu)勢(shì)度和責(zé)任度概念，來控制各子種群繁殖的數(shù)量，在總的種群個(gè)體數(shù)量一定的前提下，使得優(yōu)勢(shì)種群擁有更多的繁殖機(jī)會(huì)，達(dá)到擴(kuò)大搜索空間的目的，并迫使弱勢(shì)種群更多的引入其他種群的優(yōu)秀基因，達(dá)到增強(qiáng)自身優(yōu)勢(shì)度的目的。通過計(jì)算表明能有效的增強(qiáng)算法的搜索性能。
【關(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é)論
本文基于本文利用大自然中種群競(jìng)爭(zhēng)和合作的特性，基于大自然中種群首領(lǐng)在種群遇到外部危險(xiǎn)時(shí)會(huì)對(duì)整個(gè)種群進(jìn)行保護(hù)的特點(diǎn)，引入優(yōu)勢(shì)度和責(zé)任度的概念。提出一種個(gè)體之間相互競(jìng)爭(zhēng)和協(xié)助的協(xié)同進(jìn)化算法CCEA來控制各子種群繁殖的數(shù)量，在總的種群個(gè)體數(shù)量一定的前提下，使得優(yōu)勢(shì)種群擁有更多的繁殖機(jī)會(huì)，達(dá)到擴(kuò)大搜索空間的目的，并迫使弱勢(shì)種群更多的引入其他種群的優(yōu)秀基因，達(dá)到增強(qiáng)自身優(yōu)勢(shì)度的目的。通過測(cè)試報(bào)表明該算法可以顯著的提高其搜索性能，對(duì)于復(fù)雜的多目標(biāo)優(yōu)化問題具有較大的實(shí)用價(jià)值。
關(guān)鍵詞：粒子群算法;多目標(biāo)背包問題;禁忌算法;貪婪算法
中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2012）003-0036-02
基金項(xiàng)目：湖南省自然科學(xué)基金項(xiàng)目（06JJ50107)；湖南省教育廳項(xiàng)目（10C0445）
作者簡介：張雁（1981-），女，湖南岳陽人，湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，研究方向?yàn)橹悄苡?jì)算與移動(dòng)計(jì)算；肖偉（1971-），男，湖南溆浦人，博士生，湖南師范大學(xué)碩士研究生導(dǎo)師，研究方向?yàn)橹悄苡?jì)算與移動(dòng)計(jì)算。
0引言
背包問題是一類在給定約束條件的情況下，求最大值的組合優(yōu)化問題，是典型的非確定多項(xiàng)式完全難題，無論在理論研究上或是在實(shí)際應(yīng)用中都具有重要的意義。
1多目標(biāo)優(yōu)化問題和基本概念
一般地，一個(gè)多目標(biāo)優(yōu)化問題(MOP) 由 n 個(gè)決策變量，m個(gè)約束條件和 k 個(gè)目標(biāo)函數(shù)組成，可形式化描述如下：
Min y=f( x) =( f1( x) ，f2( x) ，…，fk( x) )
Subject to ej( x)≤0，j=1，2，…，m.
其中，x=( x1，x2，…，xn)∈X，y=( y1，y2，…，yk)∈Y。
X為決策向量 x 組成的決策空間，Y 為目標(biāo)向量 y 組成的目標(biāo)空間。
滿足約束條件的決策向量組成可行空間。
一個(gè)解x*∈S是Pareto最優(yōu)解，當(dāng)且僅當(dāng)不存在X∈S滿足：①fi(X) ≤fi(X*) ， i=1,...,k;且②fi(X)
換句話說，如何沒有一個(gè)解能改善目標(biāo)函數(shù)的某個(gè)分量而不破壞任何一個(gè)分量，那么這個(gè)解就是Pareto最優(yōu)解。既然沒有哪個(gè)解能比Pareto最優(yōu)解更優(yōu)，求解多目標(biāo)優(yōu)化問題時(shí)就應(yīng)該尋找盡可能多的Pareto最優(yōu)解。
1.1多目標(biāo) 0-1背包問題
一般地，一個(gè)0-1背包問題包含了由若干項(xiàng)物品所組成的集合，每項(xiàng)物品都有其重量和效益值，而且背包具有容量上界。背包問題的目的在于: 從多項(xiàng)物品中，選擇適當(dāng)?shù)奈锲纷蛹沟盟x中的物品效益值總和最大化，同時(shí)使選中的物品重量總和不超過背包容量上界。
若增加背包數(shù)目，則單一背包問題就被擴(kuò)展為多目標(biāo)0-1背包問題。一個(gè)由 n 項(xiàng)物品和 k 個(gè)背包組成的多目標(biāo)0-1背包問題可以形式化定義如下:
Maximize y=f(x) =( f1(x) ,
f2(x) ，…，fk(x) )
Subject to i=1,…,k
其中fi(i)=xipij為物品j對(duì)于背包i的效益值，wij為物品 j 對(duì)于背包 i 的重量,x∈(x1,x2,…,xn) ∈{0,1}n,xj=1,物品j被選中；否則xj=0，物品j未被選中。
1.2算法思路和框架
粒子群算法（PSO）是一種進(jìn)化計(jì)算技術(shù)，起源于對(duì)鳥類群體的研究。與早期的遺傳算法比較，PSO的信息共享機(jī)制是很不同的。在遺傳算法中，染色體互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻地向最優(yōu)區(qū)域移動(dòng)。在PSO中,gBest (orlBest) 給出信息給其它粒子， 這是單向的信息流動(dòng)。整個(gè)搜索更新過程是跟隨當(dāng)前最優(yōu)解的過程。與遺傳算法比較，在大多數(shù)情況下，所有的粒子可能更快地收斂于最優(yōu)解。
PSO中并沒有許多需要調(diào)節(jié)的參數(shù)，下面列出了這些參數(shù)以及經(jīng)驗(yàn)設(shè)置。
粒子數(shù)：一般取20~40，其實(shí)對(duì)于大部分的問題，10個(gè)粒子已經(jīng)足夠可以取得好的結(jié)果，不過對(duì)于比較難的問題或者特定類別的問題，粒子數(shù)可以取到100或200。
粒子的長度：這是由優(yōu)化問題決定的，就是問題解的長度。
粒子的范圍：由優(yōu)化問題決定，每一維可以設(shè)定不同的范圍。
最大速度Vmax，決定粒子在一個(gè)循環(huán)中的最大移動(dòng)距離，通常設(shè)定為粒子的范圍寬度，如（x1，x2）∈∈\[-2,2\],那么Vmax的大小就是4。
學(xué)習(xí)因子：C1和C2通常等于2，不過在文獻(xiàn)中也有其它的取值，但一般C1等于C2，并且范圍在0和4之間。
中止條件：最大循環(huán)數(shù)以及最小錯(cuò)誤要求。
禁忌搜索算法設(shè)計(jì)：
禁忌就是禁止重復(fù)前面的工作。由于它模擬了人類智力中的“記憶”功能，通過設(shè)置一個(gè)靈活的存儲(chǔ)器結(jié)構(gòu)，記住一些最近被檢查過的解，并使它們成為選取下一個(gè)解的禁忌(被禁止)，由此有效避免了迂回搜索，使算法在解空間的探索能力增大，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，從而優(yōu)化領(lǐng)域結(jié)構(gòu)。首先確定編碼方式，若采用順序編碼，即0-9共10個(gè)數(shù)字的一個(gè)排列便是一個(gè)合法的編碼。定義互換操作為這個(gè)問題的領(lǐng)域結(jié)構(gòu)，便得到一個(gè)領(lǐng)域解。
禁忌表的結(jié)構(gòu)：以互換的兩種數(shù)字（0-9的編碼表示）構(gòu)成的數(shù)對(duì)作為禁忌表的元素。
目標(biāo)函數(shù)值：以最大值作為目標(biāo)函數(shù)值，目標(biāo)函數(shù)值越大越好。
禁忌表的長度：假若禁忌長度取為3，也就是說，當(dāng)?shù)谒膫€(gè)元素進(jìn)入禁忌表時(shí)，第一個(gè)元素就從禁忌表中退出。
渴望水平：如果當(dāng)前解得某移動(dòng)得到的解優(yōu)于歷史最優(yōu)解，則無論移動(dòng)是否在禁忌表中，都將接受作為下一次迭代的初始解。
由上面的分析可知，要克服PSO的缺點(diǎn)，可以從多方面入手。本文對(duì)兩個(gè)方面進(jìn)行了改進(jìn)。首先對(duì)W進(jìn)行了改進(jìn)，較大的W有助于算法在解空間中作大范圍的探測(cè)，又助于算法跳離局部極值點(diǎn)，但不利于算法的收斂并降低解的精度；較小的W有助于算法在解空間內(nèi)開拓，可以幫助主算法加快收斂速度及提高解法，如果在開始時(shí)W就較小，那么算法就很容易陷入局部解值點(diǎn)。
禁忌粒子群混合策略中，由于粒子算法的廣域搜索能力較強(qiáng)，一般作為“主算法”；由于禁忌算法的局部搜索能力較強(qiáng)，一般作為“從算法”。主算法和從算法的概念并不是針對(duì)兩個(gè)算法的重要性，而是這樣的混合算法從整體上看來比較像一般的粒子群算法，而其中的實(shí)現(xiàn)方法又帶有禁忌算法的思想。
3結(jié)果分析
禁忌粒子群算法的改進(jìn)增加了多目標(biāo)0-1背包問題求解空間的多樣性，且兼顧了單獨(dú)使用粒子群算法的快速尋找全局最優(yōu)的特性，其收斂性和解的精度等方面與以前相比都有了提高。
參考文獻(xiàn)：
\[1\]王凌.智能優(yōu)化算法及其應(yīng)用\[M\].北京: 清華大學(xué)出版社，2001.
\[2\]TING C K, LI S T, LEE C N.TGA: a new integrated approach to evolutionary algorithms\[J\].IEEE Congress on Evolutionary Computation, 2001(2).
\[3\]FAIGLE V,KERN W.Some convergence results for probabilistic tabu search\[J\].ORSA on Computing,1992(1).
