多目標優(yōu)化的進(jìn)化優(yōu)化算法

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