科技信息O科教前沿0SCIENCE & TECHNOLOGY INFORMATION2008年第23 期多目標優(yōu)化的進化優(yōu)化算法Evolutionary Algorithms for Multi- -objective Optimization張一倩12(1.山東大學(xué)計算機學(xué)院山東濟南250014;2.濟 南職業(yè)學(xué)院計算機系山東濟南250103).[摘要]進化優(yōu)化算法具有全局優(yōu)化能力, 可以一次性求解多個非劣解。近年來,此類方法已經(jīng)成為求解多目標優(yōu)化問題一個重要的研究方向。本文分析了進化優(yōu)化算法的關(guān)鍵步朦,介紹了幾種代表性的多目標進化優(yōu)化算法,并指出了值得進一步研究的相關(guān)問題。[關(guān)鍵詞]多目標優(yōu)化;進化優(yōu)化算法;非劣解1.概述表示。根據(jù)向量元素的不同可以分為實數(shù)編碼、十進制編碼和二進制傳統(tǒng)的單目標優(yōu)化理論和算法經(jīng)過幾十年的發(fā)展和完善,在實踐編碼等。 編碼的本質(zhì)是將現(xiàn)實問題的解空間與編碼空間相對應(yīng)起來。中逐漸獲得了廣泛應(yīng)用。但很多實際問題往往涉及多個目標和約束，前者 與生物體的表現(xiàn)型相對應(yīng)，如組織器官的生理形態(tài)和生物的習(xí)不同目標之間難以進行客觀公平的比較，且各目標密切關(guān)聯(lián)、相互制性等;后者則對應(yīng)于生物體的基因型.即底層的基因編碼。理想的編碼約甚至彼此矛盾。因此對于此類單目標優(yōu)化模型難以解決的問題，有方案 是保證可行解與編碼--對應(yīng)。 一個解對應(yīng)多種編碼,將導(dǎo)致編必要建立多目標優(yōu)化模型予以全面考慮。碼空間的重疊,降低優(yōu)化計算的效率。而多種解對應(yīng)于一個編碼,則會多目標優(yōu)化問題最顯著的特點之--是其最優(yōu)解通常不是唯-的，使編碼的解釋陷人混亂和低效，是衢要盡可能避免的情況。而是一個集合。 該集合中的每個元素稱為非劣解或pareto解"。非劣解進化策略足對現(xiàn)有個體的編碼進行修改，從而得到新個體的操的含義是:不存在比其中至少一個目標更好而其它目標不劣的解,也作。 常見的進化策略包括交叉、變異。交叉操作模擬了生物界中普遍存就是不可能使該解的部分目標優(yōu)化而其它目標不至變劣。因此在理論在的有性繁殖。 由于在有性繁殖中雙親的遺傳基因發(fā)生了分割和交研究中,通常希望算法能夠在非劣解集中找到盡可能多的.分布均勻換 ,通過基因信息的交換可以實現(xiàn)新的基因組合,極大的豐富了基因解。的多樣性。傳統(tǒng)的加權(quán)求和法可以將多個目標進行折算,但得到的非劣解數(shù)變異操作模擬了遺傳變異,包括基因突變、染色體突變和葦因重量有限，且對權(quán)重值的確定有較大主觀性。組三種分子水平的突變。適當?shù)淖儺惗Ｒ越o生物體帶來有利的調(diào)整，進化優(yōu)化算法是一-類求解優(yōu)化問題的有效方法.在單目標優(yōu)化問并能夠隨 著環(huán)境的變化面變化。題中得到了迅速的發(fā)展。隨著進化優(yōu)化算法的深入研究,提出了多種選擇策略包括個體評價和個體選擇兩部分。個體評價即對群體中多目標進化優(yōu)化算法，,具有-次性求取多個非劣解的能力。本文對具的每個個體的優(yōu)劣 進行評價。在單目標優(yōu)化問題中,個體的評價比較有代表性的算法進行了介紹和比較,并提出了多目標進化優(yōu)化算法研簡單,一 般采用目標函數(shù)即可。而多目標優(yōu)化問題沙及到多個不同的究中需要深人思芍的問題。目標,各非劣解的評價和比較難以直接實現(xiàn)，是研究重點之一。個體選2.基于加權(quán)求和方法的算法擇是優(yōu)勝劣汰的環(huán)節(jié)，但選擇壓力過大會造成過早收斂到局部最優(yōu)利用加權(quán)求和法網(wǎng)可以將多個目標折算為單一目標進行優(yōu)化,而解,選擇壓力過小,又 會影響收斂速度和優(yōu)化效率。且可以證明，轉(zhuǎn)化后得到的最優(yōu)解是原多目標優(yōu)化問題的一個非劣3.2代表性的多目標進化優(yōu)化算法解。但此類方法的結(jié)果取決于各目標權(quán)重的選取,而權(quán)重的選取帶有3.2.1基于加權(quán)求和方法的進化優(yōu)化算法很大的主觀性。目標較多時,根據(jù)經(jīng)驗確定各目標權(quán)重的難度較大。此第一個多目標進化優(yōu)化算法是由SchafferJD于1985年提出的外由于各目標的單位、量綱不同,難以公平比較,更加大了確定權(quán)重的基于向鹽評 估的遺傳算法(Vector Evluated Genetie Algorithm,VEGA),其特點是:在選擇過程中,對各個目標分別加以考慮,即將全文獻[3]建立隸屬度函數(shù)對各個目標進行評價,將不同量綱的多個部個體平均劃分為多個子群， 每個子群只針對某-一個目標進行優(yōu)化，目標轉(zhuǎn)換為對該目標的滿意度，以便于各目標的比較;根據(jù)各目標兩因此從本質(zhì)上說,VEGA仍然是一種加權(quán)求和的方法。兩之間的相對重要性構(gòu)建判斷矩陣.采用判斷矩陣法確定各目標的權(quán)另外一種基于加權(quán)求和的優(yōu)化算法是由Hajela和Lin于1992年重值。這在- -定程度上解決了目標比較和權(quán)重確定兩個問題,但仍只提出的基于權(quán)重的遺傳算法(Weighing-based Genetie Agorithm),其特能得到一個非劣解,而不是整個非劣解集,只適用于特定問題的求解。點是務(wù) 目標的權(quán)重值不是固定不變的，而是作為個體編碼的一部分。3.多目標進化優(yōu)化算法在評價個體優(yōu)劣時,每個個體均按照不同權(quán)重進行計算,因此可以實模擬生物進化過程的進化優(yōu)化算法是一類通用的優(yōu)化問題求解現(xiàn)權(quán)重和解 的共同進化,其優(yōu)化效率和結(jié)果要好于VEGA。思路。此類算法在單目標優(yōu)化問題中能夠以逃離局部最優(yōu)解，具有全3.2.2 MOGA局尋優(yōu)能力,對目標函數(shù)沒有連續(xù)可導(dǎo)等要求,并具有并行性好等優(yōu)在Fonsea和Fleming于1993年提出的多目標遺傳算法(Muli-點。適用于求解傳統(tǒng)數(shù)學(xué)優(yōu)化算法難以處理的非線性、離散變量和強obijetive Genetie Algorithmn, MOGA)中,采用了基于排序數(shù)的評價方法約束條件的優(yōu)化模型，經(jīng)過幾十年的發(fā)展，獲得了豐碩的理論成果和(評價值等于 排序數(shù)加1)。所謂排序數(shù),即在當前群體中,絕對優(yōu)于某廣泛應(yīng)用。一個體的其他個體的數(shù)量。如圖1所示,5個非劣解的評價值為1,而一隨著進化算法研究的深人， 將進化計算的思想應(yīng)用于求解多目標最差解 的評價值為10。優(yōu)化問題，提出了VECA .NPCA.NSCA ,SPEA等算法以及改進算法。這些多目標進化優(yōu)化算法的實現(xiàn)和性能各異,但都具有一次性求取非劣解集的能力。3.1進化優(yōu)化算法的關(guān)鍵技術(shù)進化計算的特點是以群體優(yōu)化搜索,代替了傳統(tǒng)算法的單- -個體中國煤化工的優(yōu)化.通過群體內(nèi)信息的交互機制，可以更有效的提高計算效率,并有利于擺脫局部最優(yōu)解陷阱。這一特點對于求解多目標優(yōu)化問題,無MYHCNMHG疑是極為有利的特點。一般來說,進化類算法的設(shè)計和具體實現(xiàn)主要包括以下三個步驟:編碼方案進化策略、選擇策略。所謂編碼方案.即如何將問題的解以一個向量或一組數(shù)字的形式圈1 MOGA 的評價方寨(下轉(zhuǎn)第27頁).科技信息O科教前沿OSCENCE & TECHNOLOGY INFORMATION2008年第23期貯藏。為了解決人工種子萌發(fā)率和成苗率低的問題,薛建平等以半夏活性成分 相關(guān)酶類,并進行分子克隆和基因調(diào)控的相關(guān)研究。此外,還試管小塊莖為材料，用3%梅藻酸鈉和2%殼聚糖為種皮基質(zhì)，添加要 注重組織培養(yǎng)物的產(chǎn)品開發(fā)。如丁家宜教授以人參愈傷組織為原料CAs、多菌靈.CuCl2和NiCI等物質(zhì)制成了復(fù)合型人工種皮,可獲95%開 發(fā)出了一系列暢銷的化妝品,就是我國藥用植物組織培養(yǎng)開發(fā)產(chǎn)晶的萌發(fā)率和90%的成苗事，大大提高了人工種子的萌發(fā)率和成苗事，方 面的成功之作。利用半夏組培物可以進行生物制藥及植物殺蟲劑等為半夏人工種子的規(guī)?；a(chǎn)和大田應(yīng)用提供技術(shù)支持。但人工種子的研究 ,開發(fā)出新的產(chǎn)品,有產(chǎn)品的支持的半夏組織培養(yǎng),其工業(yè)化步經(jīng)過常溫或低溫貯藏不同時間后,是否影響其萌發(fā)率和成苗率等問題伐也將 大大加快。還有待進一步研究。4.3建立和完善半夏的快速繁殖體系3.半夏細胞培養(yǎng)的研究利用半夏的組織培養(yǎng)進行快速繁殖，可以采取一次性成苗的方近年來.利用細胞培養(yǎng)技術(shù)生產(chǎn)天然產(chǎn)物的研究十分活躍,并越法。 但若為了滿足市場需求,進行大量的生產(chǎn)和種質(zhì)保存,則最好建立來越受到人們的關(guān)注。尤其是半夏細胞培養(yǎng)條件的模索和細胞生長規(guī)半夏的 無性系快速繁殖體系。但必須以市場需求為導(dǎo)向,在合理進行律等基礎(chǔ)性研究較為活躍，關(guān)于細胞培養(yǎng)過程中次生代謝產(chǎn)物的研可行性分析的基礎(chǔ) 上再著手建立。建立快繁體系的基本方法是以外植究反應(yīng)器的研制等方面開展的相對較少。賈永芳等用半夏幼嫩葉片體誘導(dǎo) 出愈傷組織,通過繼代,建立能夠不斷傳代的半夏愈傷組織體培養(yǎng)誘導(dǎo)出愈傷組織,然后進行懸浮振蕩培養(yǎng),經(jīng)3~4歡繼代培養(yǎng)得系 ,再對愈傷組織進行擴大培養(yǎng),形成大量的試管苗。穩(wěn)定的半夏快速到分散性好的細胞懸浮系。將細胞懸浮液過健得到的小細胞團接種于繁殖系統(tǒng),繁殖系數(shù)高,1 個1cm直徑的半夏塊莖理論上可繁殖1x10MS附加NAA.2mg/L和BA1.Omg/L分化培養(yǎng)基上,40d可分化出小植個以上的試管苗。 從愈傷組織到可移裁的試管苗需50d左右,從而可株。范美華等研究得出半夏細胞的生長曲線星“S”型,細胞的最佳收獲及時 高效的為生產(chǎn)上提供大量優(yōu)質(zhì)種苗。但是,在愈傷組織長期繼代時間為21d,培養(yǎng)基的最佳組合為:20g/L葡萄糖+100mg/L肌醇+培養(yǎng)過程中 ,會造成遺傳變異,影響試管苗的品質(zhì)。因此,在建立快速1.8mmo/LCaCL 2H20+0.06mml/LFeSO. 7H;0。此外,還發(fā)現(xiàn)光照有利繁殖體 系的同時,要不斷的完善相關(guān)技術(shù)環(huán)節(jié):從外植體的選擇、培養(yǎng)于半夏細胞的生長并且蛋白質(zhì)含量與酶活性呈正相關(guān)性,MDA含量條件 、最佳植物生長調(diào)節(jié)劑的配比到煉苗移栽都需要在實踐中總緒經(jīng)和細胞的生長、分化呈負相關(guān)性。驗,不斷改進,以達到高效、經(jīng)濟的目的。丹4.結(jié)語和展望植物組織培養(yǎng)作為一項重要的生物技術(shù)存在無限的潛力和應(yīng)用[參考文獻] .價值。半夏的組織和細胞培養(yǎng)研究工作已取得成功,并獲得了不少成(1]中國醫(yī)學(xué)科學(xué)院藥物研究所等編,中藥志(M.第二版,北京:人民衛(wèi)生出版社，果,但也還有不少向題需要深人研究。4.1 研究半夏組織培養(yǎng)和植株再生過程中的生理及結(jié)構(gòu)上的變化[2]冉懸雄名貴中藥材綠色栽培技術(shù)[M.北京:科學(xué)技術(shù)文獻出版社20024.經(jīng)研究發(fā)現(xiàn),組織培養(yǎng)的半夏塊莖中各成分的總含量要高于野生[3]任家惠,陳克潤,徐瓊芳.三葉半夏試管苗器官的誘導(dǎo)U.植物生理學(xué)通報，塊莖。但其具體的生理生化方面的原因還不清楚。郭余龍等用HPLC1983.4:44.[4]萬美亮,陳宏康，詹亞華,等.半夏組織培養(yǎng)與快迷繁殖研克[J.中國中藥雜志，法比較分析了組織培養(yǎng)塊基和野生塊莖的成分,也發(fā)現(xiàn)了前者各成分9.909:592 -531.的總含量高于后者,二者的主成分構(gòu)成也相似,但半夏培養(yǎng)物又觖乏[5]張騰國半 夏組織培養(yǎng)快繁技術(shù)研究，，甘肅農(nóng)業(yè).科19911:15-17.某些野生塊莖中的特有成分，遣成該種影響的生理變化也尚未明白。[6]張?zhí)K鋒謝索霞,半夏組織培 養(yǎng)快速繁殖的研究[D.信陽師范學(xué)院學(xué)報1998,11半夏組織培養(yǎng)過程中,植株再生途徑有兩種:一是從愈傷組織形成:外()86-89.植體上誘導(dǎo)愈傷組織的形成再轉(zhuǎn)至分化培養(yǎng)基,發(fā)育成完整植株:二[7]武宗信，解紅蛾,赫建平,等半夏快速繁殖研兗J.山西大學(xué)學(xué)報(自然科學(xué)版),是從非愈傷組織形成:外植體上誘導(dǎo)形成球狀體,再發(fā)育成完整植株，205,283)315-317.未經(jīng)脫分化面完成了再分化。造成這兩種途徑,除了有外源教素的影[8)何美民，劃剛，路鐵剛，等，半夏基尖培養(yǎng)及塊蒸的品質(zhì)改 良U植物學(xué)報。94.61)39 44.響外,其內(nèi)部又有哪些生理和結(jié)構(gòu)變化等都有待進一步探討。[9]張小斌,趙月梅.商格半夏的組織塘養(yǎng)研兗[.商格師范專科學(xué)校學(xué)報[D4.2深化半夏細胞培養(yǎng)及工業(yè)化生產(chǎn)的研究半夏組織培養(yǎng)的培養(yǎng)基篩選植物生長調(diào)節(jié)劑的季加量,氨源及205.1914:40-43.培養(yǎng)條件等基本技術(shù)已經(jīng)比較成熟。更深層次的研究工作應(yīng)著重于半作者簡介:顧明率,女19728出生,漢族。中藥學(xué)本科,全國執(zhí)業(yè)藥師。主攻夏組織培養(yǎng)的工業(yè)化:如適合半夏培養(yǎng)的反應(yīng)器的研制.細胞生長規(guī)方向:中藥基定學(xué)。律的探討.細胞在反應(yīng)器中的生長動力學(xué)考察、誘導(dǎo)子的使用等。同時,還要開展對半夏塊莖中總生物賊麻黃賊.半夏蛋白等次生代謝機[責(zé)任編輯:張艷芳]制的研究。通過對次生代謝機理的研究,可以深入分析調(diào)控半夏塊莖(上接第32頁)3.2.3 NSCA的非劣解作為精英保留在一一個附屬外部種群;外部種群也參與所有的NSCA(Nondominated Sorting Genetic Algorithm)算法是基于對多目遺傳操作 ;對外部種群不斷的進行更新,并采用聚類的方法保持非劣標解群體進行逐層分類的方法。每代選種配對之前先按解個體的非劣解 的數(shù)量不超過規(guī)定值。性進行排序,并引進基于決策空間的共享函數(shù),優(yōu)點是優(yōu)化目標個數(shù)4.結(jié)束語任選,非劣最優(yōu)解分布均勻,允許存在多個不同等效解;缺點是計算效進化優(yōu)化算法是- -類模擬生物進化過程的優(yōu)化方法,具有全局尋事較低,未采用精英保留策略(itisn),共享參數(shù)需要預(yù)先確定。隨后，優(yōu)的能力。 利用進化優(yōu)化算法求解多目標優(yōu)化問題，可以一次求取非Deb與Pratap等通過引進快速非劣性排序和新的多樣性保護方法,提劣解 集中多個非劣解的能力,是多目標優(yōu)化問題研究的熱點。出了第二代NSCA,簡稱NSCAII,在- -定程度 上克服了NSGA的缺點。多目標優(yōu)化問題的進化優(yōu)化算法中待研兗的問題還很多,特別是3.2.4 NPGA非劣最優(yōu)解的質(zhì)量評估.選種配對機制和選擇機制等,是目前新算法1994年Horm,Napliotisi 和Goldberg等人于提出了小生境Pareto的研究重點。風(fēng)遣傳算法(Niched Pareto Genetic Algorihm,NPGA)。NPGA將共享函數(shù)的概念引人到多目標進化優(yōu)化算法中,采用基于錦標賽方法的選擇機[參考文獻]制。該算法的非劣解選擇是基于小生境,即一部分種群而非全體。其優(yōu)[1]謝濤 .陳火吁名日標設(shè)化與冰管問樣的油化暫塊.計算機學(xué)報,003.26(8),點是能很快找到一些好的非劣最優(yōu)解城,并能維持一個較長的種群更9-103中國煤化工新期。這就要求算法需要對小生境的規(guī)模和數(shù)量加以限制,以保證解[2]朝毓達1990的多樣性,使最優(yōu)解能夠盡可能均勻的分散到整個非劣解集中。YHCN M H G電壓優(yōu)化控制.電力系統(tǒng)3.2.5 SPEAZitaler與Thiele提出了一種采用精英保留策略的強度Pareto進[4]王正志，薄詩進化計算.長沙:國防科技大學(xué)出版社,000.0化算去(Srengh Pareto Evoluionary Algorithm ,SPEA)。該算法將每代2