蘇宇逍

(中國空空導(dǎo)彈研究院總體部，河南洛陽 471009)

幾乎每個(gè)決策和預(yù)測問題上都要在考慮不同約束的同時(shí)，處理若干相互沖突的目標(biāo)，這些問題均涉及多個(gè)數(shù)值目標(biāo)在給定區(qū)域上最優(yōu)化問題，這就是多個(gè)目標(biāo)優(yōu)化問題(Multi－objective Optimization Problem，MOP)［1－2］，但這些約束并不是獨(dú)立存在的，其通常是互相競爭、相互束縛的。這些約束具有不同的物理意義，對其中任何一個(gè)約束的優(yōu)化必須以犧牲其他約束作為代價(jià)，且每個(gè)約束的單位又是不一致的。因此，多目標(biāo)優(yōu)化問題的關(guān)鍵之處在于尋找一組既能滿足全部約束條件同時(shí)又可使目標(biāo)函數(shù)能夠達(dá)到最優(yōu)的約束變量取值［3－5］。傳統(tǒng)的多目標(biāo)優(yōu)化問題求解方法是將各個(gè)子目標(biāo)函數(shù)集合成一個(gè)加權(quán)和的單目標(biāo)函數(shù)，然后采用單目標(biāo)優(yōu)化算法求解，這樣會導(dǎo)致出現(xiàn)每個(gè)單目標(biāo)函數(shù)的系數(shù)決定帶有較大的主觀性，且各子目標(biāo)互相競爭、相互約束，使得加權(quán)目標(biāo)函數(shù)的拓?fù)浣Y(jié)構(gòu)復(fù)雜［6－7］。隨著人工智能進(jìn)化算法(Evolutionary Algorithm，EA)在多目標(biāo)優(yōu)化領(lǐng)域應(yīng)用的深入，遺傳算法成為迄今為止進(jìn)化算法中應(yīng)用最多的算法，在解決工業(yè)工程領(lǐng)域中復(fù)雜優(yōu)化問題有著巨大潛力。本文主要介紹改進(jìn)型的遺傳算法與和人工智能密切相關(guān)的神經(jīng)網(wǎng)絡(luò)算法［8－10］。

1 多目標(biāo)遺傳算法

1.1 多目標(biāo)遺傳算法

多目標(biāo)遺傳算法(Multi Objective Genetic Algorithm，MOGA)是近幾年興起的利用遺傳算法處理多目標(biāo)優(yōu)化問題的算法，其不但能處理大規(guī)模問題，不受問題性質(zhì)的限制，且能搜索獲得問題的全局最優(yōu)解［11－12］。遺傳算法(Genetic Algorithms，GA)是一種受生物進(jìn)化啟發(fā)的學(xué)習(xí)方法，在本質(zhì)上是一種不依賴具體問題的直接搜索方法，其通過變異和重組當(dāng)前已知的最好假設(shè)來生成后續(xù)的假設(shè)。在模式識別、神經(jīng)網(wǎng)絡(luò)、圖像處理、工業(yè)優(yōu)化控制和生物科學(xué)等領(lǐng)域遺傳算法都得到了廣泛應(yīng)用。遺傳算法研究的問題是搜索候選假設(shè)空間并確定最佳的假設(shè)，“最佳假設(shè)”被定義為是使適應(yīng)度最優(yōu)的假設(shè)，適應(yīng)度是為當(dāng)前問題預(yù)先定義的數(shù)字度量［13］。遺傳算法的實(shí)現(xiàn)主要有6個(gè)因素:參數(shù)的編碼、初始種群的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作、算法控制參數(shù)的設(shè)定和約束條件的處理，其構(gòu)造步驟如圖1所示。

圖1 遺傳算法的構(gòu)造過程

基于Pareto最優(yōu)概念的多目標(biāo)遺傳算法是當(dāng)前進(jìn)化計(jì)算領(lǐng)域的研究和應(yīng)用熱點(diǎn)。多目標(biāo)遺傳算法的研究目標(biāo)主要是使算法快速收斂，且均勻分布在問題的非劣最優(yōu)域。這里在MOGA設(shè)計(jì)時(shí)要考慮如何實(shí)現(xiàn)適應(yīng)度分配與選擇，算法收斂性能的改善，如何保持多樣性以及提高多目標(biāo)演化算法的求解效率等。

1.2 多目標(biāo)遺傳算法

求解多目標(biāo)問題的遺傳算法的基本結(jié)構(gòu)與求解單目標(biāo)問題的遺傳算法的基本結(jié)構(gòu)大致相似。主要包括向量評估遺傳算法(VEGA)、多目標(biāo)遺傳算法(MOGA)、基于距離的Pareto遺傳算法(DPGA)、小生境Pareto遺傳算法(NPGA)、非劣分類遺傳算法(NSGA)。本文主要考慮優(yōu)化小生境Pareto遺傳算法(NPGA)。

2 BP神經(jīng)網(wǎng)絡(luò)算法

在多目標(biāo)優(yōu)化過程中，由于各個(gè)學(xué)科不同的目標(biāo)，這些目標(biāo)往往相互制約。在系統(tǒng)綜合設(shè)計(jì)時(shí)，不可能找到能使所有目標(biāo)均同時(shí)達(dá)到最優(yōu)的設(shè)計(jì)方案，只有非劣意義上的最優(yōu)。進(jìn)化BP神經(jīng)網(wǎng)絡(luò)算法是一種以非數(shù)學(xué)模型為基礎(chǔ)的優(yōu)化方法，其能快速、簡便且可分段地找到Pareto最優(yōu)解。為了獲取多目標(biāo)優(yōu)化問題的有效解集，通常將其轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，應(yīng)用標(biāo)量優(yōu)化算法進(jìn)行求解。然而，由于非線性標(biāo)量優(yōu)化問題的求解在眾多情況下仍較為困難，尤其是對于不可微、不連續(xù)問題更是如此。因此，應(yīng)用BP神經(jīng)網(wǎng)絡(luò)模型代替相應(yīng)的子目標(biāo)函數(shù)，可較好地解決上述問題。

2.1 神經(jīng)元網(wǎng)絡(luò)模型

神經(jīng)元網(wǎng)絡(luò)是BP神經(jīng)網(wǎng)絡(luò)的關(guān)鍵組成部分。根據(jù)神經(jīng)元之間連接的方式不同，神經(jīng)元網(wǎng)絡(luò)可分為前向網(wǎng)絡(luò)和相互結(jié)合型網(wǎng)絡(luò)，其中前向網(wǎng)絡(luò)由輸入層、中間層(隱層)和輸出層組成。

2.2 BP神經(jīng)網(wǎng)絡(luò)算法

神經(jīng)網(wǎng)絡(luò)算法是以人腦的智能功能為研究對象，研究人類大腦的信息處理能力的方法，特別是研究人類大腦的智能信息處理能力相關(guān)的信息處理理論方法。BP神經(jīng)網(wǎng)絡(luò)算法其基本思想是最小二乘算法，其采用最小梯度搜索技術(shù)來使目標(biāo)函數(shù)的實(shí)際輸出值與期望輸出值的誤差均方值達(dá)到最小;該算法采用Sigmoid型可微函數(shù)作為傳遞函數(shù)，實(shí)現(xiàn)了輸入和輸出間的非線性映射，具有工作狀態(tài)穩(wěn)定和可操作性強(qiáng)等特點(diǎn)，被廣泛地應(yīng)用于函數(shù)逼近、模式識別、數(shù)據(jù)壓縮等領(lǐng)域。如圖2所示。

圖2 神經(jīng)元和BP神經(jīng)網(wǎng)絡(luò)模型結(jié)構(gòu)

圖2(a)為反饋神經(jīng)網(wǎng)絡(luò)模型。根據(jù)對能量函數(shù)的極小點(diǎn)利用的情況可分為兩類:第一類是所有極小點(diǎn)均起作用，主要用于各種存儲器;第二類只利用全局極小點(diǎn)，主要用來求解最優(yōu)化問題;圖2(b)中，隱層可有若干層，每一層的神經(jīng)元只接受來自前一層神經(jīng)元的輸出。反饋型神經(jīng)網(wǎng)絡(luò)中的任意兩個(gè)神經(jīng)元間都可以有連接，包括神經(jīng)元到自身的反饋。

3 改進(jìn)遺傳算法其與BP神經(jīng)網(wǎng)絡(luò)融合

智能計(jì)算問題的優(yōu)化是最近幾年優(yōu)化算法研究的熱門課題。遺傳算法和神經(jīng)網(wǎng)絡(luò)是該領(lǐng)域研究的兩個(gè)方向，但其基于不同的機(jī)理，其研究的大部分成果和思路只是應(yīng)用在各自的領(lǐng)域中，因此這兩種優(yōu)化算法的互相融合已成為探討的一個(gè)重要課題。借助遺傳算法與神經(jīng)網(wǎng)絡(luò)自身的優(yōu)點(diǎn)，如果將遺傳算法對尋優(yōu)問題有較好的自適應(yīng)與神經(jīng)網(wǎng)絡(luò)算法的自適應(yīng)學(xué)習(xí)能力相結(jié)合，便可實(shí)現(xiàn)彼此的相互優(yōu)化，從而獲得更高效的解決實(shí)際問題能力。

3.1 GA－BP神經(jīng)網(wǎng)絡(luò)融合

本文采用3層BP網(wǎng)絡(luò)來初步確定解空間，首先設(shè)定網(wǎng)絡(luò)的訓(xùn)練次數(shù)n以及網(wǎng)絡(luò)的訓(xùn)練誤差ω;在訓(xùn)練樣本誤差ω和檢測樣本都相對滿意時(shí)，將連接權(quán)值中的最大值和最小值分別記為ωmax與ωmin，設(shè)連接權(quán)值的基本解空間為［ωmin－ δ1，ωmax+ δ2］，其中，δ1，δ2為調(diào)節(jié)參數(shù)。適應(yīng)度函數(shù)是神經(jīng)網(wǎng)絡(luò)的誤差計(jì)算，誤差越大，適應(yīng)度越小。設(shè)定輸入種群規(guī)模、交叉概率Pc、變異概率Pm、網(wǎng)絡(luò)層數(shù)、每層的神經(jīng)元數(shù)，使用GA反復(fù)優(yōu)化神經(jīng)網(wǎng)絡(luò)的權(quán)值，直到平均值不再有意義地增加為止，此時(shí)解碼得到的參數(shù)組合已經(jīng)充分接近最佳，再用BP算法在這些小的解空間中對網(wǎng)絡(luò)的連接權(quán)和閾值再次尋優(yōu)，搜索出最優(yōu)解。

3.2 GA－BP算法設(shè)計(jì)

基于遺傳算法的BP神經(jīng)網(wǎng)絡(luò)融合算法(GABP)的流程圖，如圖3所示。

圖3 GA－BP算法的流程圖

首先初始化BP網(wǎng)絡(luò)模型，確定輸出與輸入個(gè)數(shù)X，Y，網(wǎng)絡(luò)的層數(shù)L、網(wǎng)絡(luò)的訓(xùn)練次數(shù)N等;順序級聯(lián)輸入層與隱含層權(quán)值和閾值和隱含層與輸出層的，形成初始化種群;計(jì)算種群的適應(yīng)度，獲取子代種群;判斷是否到達(dá)最大迭代次數(shù)，若符合則根據(jù)解碼確定BP，否則返回上步繼續(xù)執(zhí)行;根據(jù)最優(yōu)個(gè)體按編碼順序解碼，獲取BP網(wǎng)絡(luò)的初始權(quán)值和閾值;計(jì)算全局誤差，并判斷是否符合要求，如果符合則結(jié)束網(wǎng)絡(luò)學(xué)習(xí)，否則修改閾值繼續(xù)上述步驟。

4 改進(jìn)算法的性能測試與結(jié)果

為了測試改進(jìn)的融合遺傳算法和神經(jīng)網(wǎng)絡(luò)算法的性能，選擇用C++語言與Matlab將改進(jìn)的并行混合遺傳算法完全實(shí)現(xiàn)，用此程序產(chǎn)生多目標(biāo)優(yōu)化的結(jié)果，通過將改進(jìn)的遺傳算法與BP神經(jīng)網(wǎng)絡(luò)融合后的算法應(yīng)用于車間動態(tài)調(diào)度中，證明本文提出的GA－BP算法的可行性與有效性。遺傳－神經(jīng)算法(GA－BP)充分利用了遺傳算法的全局搜索能力和BP網(wǎng)絡(luò)的局部搜索能力。由圖4可明顯看出，遺傳－神經(jīng)算法與純BP算法在性能上的差異。

圖4 BP網(wǎng)絡(luò)與GA－BP的收斂曲線比較

5 結(jié)束語

本文提出的基于遺傳算法的BP神經(jīng)網(wǎng)絡(luò)算法，

不僅利用了BP神經(jīng)網(wǎng)絡(luò)的通過樣本研究完成任意空間局部搜索的優(yōu)點(diǎn)，又利用了遺傳算法可對復(fù)雜的、非線性及不可微的函數(shù)實(shí)現(xiàn)全局搜索的優(yōu)勢，在解決多目標(biāo)優(yōu)化問題中，取得了良好的效果。目前智能算法融合技術(shù)正處在發(fā)展階段，從多目標(biāo)優(yōu)化的發(fā)展原則不難看出，智能算法應(yīng)用在多目標(biāo)優(yōu)化領(lǐng)域的研究成果是明顯的，進(jìn)一步研究該算法具有深遠(yuǎn)意義。

［1］ 崔遜學(xué)．多目標(biāo)進(jìn)化算法及其應(yīng)用［M］．北京:國防工業(yè)出版社，2006．

［2］ 謝濤，陳火旺，康立山．多目標(biāo)優(yōu)化的演化算法［J］．計(jì)算機(jī)學(xué)報(bào)，2003，26(8):997 －1003．

［3］ 王志良．人工心理［M］．北京:機(jī)械工業(yè)出版社，2007．

［4］ 史忠植．智能科學(xué)［M］．北京:清華大學(xué)出版社，2005．

［5］ 鐘珞，饒文碧，鄒承明．人工神經(jīng)網(wǎng)絡(luò)及其融合應(yīng)用技術(shù)［M］．北京:科學(xué)出版社，2007．

［6］ 陳國良，王熙法，莊鎮(zhèn)泉，等．遺傳算法及其應(yīng)用［M］．北京:人民郵電出版社，1996．

［7］ Mitchell T M．機(jī)器學(xué)習(xí)［M］．曾華軍，張銀奎，譯．北京:機(jī)械工業(yè)出版社，2003．

［8］ Bergey P K，Ragsdale C T，Hoskote M．A simulated annealing genetic algorithm for the electrical power districting problem［J］．Annals of Operations Research，2003，121(1 －4):33 －35．

［9］ 武兆慧，張杜娟，劉希玉．基于模擬退火遺傳算法的關(guān)聯(lián)規(guī)則挖掘［J］．計(jì)算機(jī)應(yīng)用，2005，25(5):1009 －1011．

［10］呂軍，馮博琴，李波．免疫遺傳算法及其應(yīng)用研究［J］．微電子學(xué)與計(jì)算機(jī)，2005，22(6):221 －224．

［11］ Wei Lingyun，Zhao Mei．A niche hybrid genetic algorithm for global optimization of continuous multimodal functions［J］．Applied Mathematics and Computation，2005，160(3):649 －661．

［12］ Yun Youngsu，Gen Mitsuo．Performance analysis of adaptive genetic algorithms with fuzzy logic and heuristics［J］．Fuzzy Optimizationand Decision Making，2003，2(2):161 －175．

［13］鄧?yán)?，魯瑞華．一種改進(jìn)的抑制早熟收斂的模糊遺傳算法［J］．計(jì)算機(jī)科學(xué)，2007，34(11):150 －153．