最優(yōu)控制-遺傳算法綜述

最優(yōu)控制論文遺傳算法的發(fā)展

摘要最優(yōu)控制是現(xiàn)代控制理論的核心，它研究的主要問(wèn)題是：在滿足一定約束條件下，尋求最優(yōu)控制策略，使得性能指標(biāo)取極大值或極小值。解決最優(yōu)控制問(wèn)題的主要方法有古典變分法、極大值原理和動(dòng)態(tài)規(guī)劃。最優(yōu)控制理論已被應(yīng)用于綜合和設(shè)計(jì)最速控制系統(tǒng)、最省燃料控制系統(tǒng)、最小能耗控制系統(tǒng)、線性調(diào)節(jié)器等。目前研究最優(yōu)控制理論最活躍的領(lǐng)域有神經(jīng)網(wǎng)絡(luò)優(yōu)化、模擬退火算法、趨化性算法、遺傳算法、魯棒控制、預(yù)測(cè)控制、混沌優(yōu)化控制以及穩(wěn)態(tài)遞階控制等。作為一種比較新的一種新的優(yōu)化算法一遺傳算法(GeneticAlgorithm,簡(jiǎn)稱GA)正在迅速發(fā)展。遺傳算法是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索與優(yōu)化方法。近年來(lái)，由于遺傳算法求解復(fù)雜優(yōu)化問(wèn)題的巨大潛力及其在工業(yè)工程領(lǐng)域的成功應(yīng)用 ，這種算法受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。本文介紹了遺傳算法的研究現(xiàn)狀，描述了它的主要特點(diǎn)和基本原理，概述了它的理論、技術(shù)和應(yīng)用領(lǐng)域，討論了混合遺傳算法和并行遺傳算法，指出了遺傳算法的研究方向，并對(duì)遺傳算法的性能作了分析。目錄TOC\o"1-5"\h\z\o"CurrentDocument"1前言 1\o"CurrentDocument"2遺傳算法基本理論 1-\o"CurrentDocument"2.1遺傳算法的基本步驟 1-\o"CurrentDocument"2.2遺傳算法的現(xiàn)狀 2...\o"CurrentDocument"2.3遺傳算法的應(yīng)用 3...2.3.1函數(shù)優(yōu)化 3...2.3.2組合優(yōu)化 4...2.3.3生產(chǎn)調(diào)度問(wèn)題 4...2.3.4自動(dòng)控制 4...2.3.5機(jī)器入學(xué) 4...2.3.6圖像處理 4...2.3.7人工生命 5...2.3.8遺傳編程 5...2.3.9機(jī)器學(xué)習(xí) 5...2.3.10數(shù)據(jù)挖掘 5...\o"CurrentDocument"3遺傳算法的研究方向 5...\o"CurrentDocument"參考文獻(xiàn) 7...1前言遺傳算法(GeneticAlgorithm,GA)是近年來(lái)迅速發(fā)展起來(lái)的一種全新的隨機(jī)搜索與優(yōu)化算法，其基本思想是基于Darwin的進(jìn)化論和Mendel的遺傳學(xué)說(shuō)。該算法由密執(zhí)安大學(xué)教授Holland及其學(xué)生于1975年創(chuàng)建⑴。此后，遺傳算法的研究引起了國(guó)內(nèi)外學(xué)者的關(guān)注。自1985年以來(lái)，國(guó)際上已召開(kāi)了多次遺傳算法的學(xué)術(shù)會(huì)議和研討會(huì),國(guó)際遺傳算法學(xué)會(huì)組織召開(kāi)的ICGA(lnternationalConferenceonGeneticAlgorithms)會(huì)議和FOGA(WorkshoponFoundationofGeneticAlgorithms)會(huì)議，為研究和應(yīng)用遺傳算法提供了國(guó)際交流的機(jī)會(huì)。近年來(lái)，遺傳算法已被成功地應(yīng)用于工業(yè)、經(jīng)濟(jì)管理、交通運(yùn)輸、工業(yè)設(shè)計(jì)等不同領(lǐng)域，解決了許多問(wèn)題⑵。例如，可靠性優(yōu)化、流水車間調(diào)度、作業(yè)車間調(diào)度、機(jī)器調(diào)度、設(shè)備布局設(shè)計(jì)、圖像處理以及數(shù)據(jù)挖掘等。本文將從遺傳算法的理論和技術(shù)兩方面概述目前的研究現(xiàn)狀，描述遺傳算法的主要特點(diǎn)、基本原理以及各種改進(jìn)算法，介紹遺傳算法的應(yīng)用領(lǐng)域，并對(duì)遺傳算法的性能進(jìn)行分析。2遺傳算法基本理論2.1遺傳算法的基本步驟遺傳算法的思想源于生物遺傳學(xué)和適者生存的自然規(guī)律，是具有“生存+檢測(cè)”的迭代過(guò)程的搜索算法。它以一種群體中的所有個(gè)體為對(duì)象，并利用隨機(jī)化技術(shù)指導(dǎo)對(duì)一個(gè)被編碼的參數(shù)空間進(jìn)行高效搜索。其中，選擇、交叉和變異構(gòu)成了遺傳算法的遺傳操作；參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)、控制參數(shù)設(shè)定五個(gè)要素組成了遺傳算法的核心內(nèi)容。我們習(xí)慣上把1975Holland年提出的GA稱為傳統(tǒng)的GA它的主要步驟如下：編碼:GA在進(jìn)行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，這些串結(jié)構(gòu)數(shù)據(jù)的不同組合便構(gòu)成了不同的點(diǎn)。初始群體的生成：隨機(jī)產(chǎn)生N個(gè)初始串結(jié)構(gòu)數(shù)據(jù)，每個(gè)串結(jié)構(gòu)數(shù)據(jù)稱為一個(gè)個(gè)體，N個(gè)個(gè)體構(gòu)成了一個(gè)群體。GA以這N個(gè)串結(jié)構(gòu)數(shù)據(jù)作為初始點(diǎn)開(kāi)始迭代。適應(yīng)度評(píng)估檢測(cè)：適應(yīng)度(適應(yīng)性函數(shù))表明個(gè)體或解的優(yōu)劣性。不同的問(wèn)題，適應(yīng)度的定義方式也不同。選擇:選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代為下一代繁殖子孫。遺傳算法通過(guò)選擇過(guò)程體現(xiàn)這一思想，進(jìn)行選擇的原則是適應(yīng)性強(qiáng)的個(gè)體為下一代貢獻(xiàn)一個(gè)或多個(gè)后代的概率大。選擇實(shí)現(xiàn)了達(dá)爾文的適者生存原則。（5） 交換：交換操作是遺傳算法中最主要的遺傳操作。通過(guò)交換操作可以得到新一代個(gè)體，新個(gè)體組合了其父輩個(gè)體的特性。交換體現(xiàn)了信息交換的思想。（6） 變異:變異首先在群體中隨機(jī)選擇一個(gè)個(gè)體，對(duì)于選中的個(gè)體以一定的概率隨機(jī)地改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)串的值。同生物界一樣， GA中變異發(fā)生的概率很低，通常取值在0.001-0-01之間。變異為新個(gè)體的產(chǎn)生提供了機(jī)會(huì)。 （8）遺傳算法的流程為：開(kāi)始（選擇編碼方式；產(chǎn)生初始群體；計(jì)算初始群體的適應(yīng)度；若不滿足結(jié)束條件則循環(huán)執(zhí)行：（選擇操作；交換操作；變異操作；計(jì)算新一代群體的適應(yīng)度；））結(jié)束（3）2-2遺傳算法的現(xiàn)狀仿生算法是一大類目前研究的比較火熱的算法，遺傳算法是其中一個(gè)重要的分支。仿生過(guò)程算法：遺傳算法仿生算法仿生結(jié)構(gòu)算法：神經(jīng)網(wǎng)絡(luò)仿生行為算法：模糊邏輯圖1仿生算法組成圖在遺傳算法的研究中，主要有三類研究方向：（1）研究遺傳算法本身的理論基礎(chǔ)。（2）用遺傳算法作為工具解決工程問(wèn)題，主要是進(jìn)行優(yōu)化，矣心的是是否能在傳統(tǒng)方法上有所提高。（3）用遺傳算法研究演化現(xiàn)象，一般涉及到人工生命和復(fù)雜性科學(xué)領(lǐng)域?！?]在工程實(shí)踐中的遺傳算法應(yīng)用主要是利用了其并行性和全局搜索的特點(diǎn)來(lái)進(jìn)行優(yōu)化。盡管遺傳算法本身是一種通用弱方法，仍需要盡量結(jié)合特定領(lǐng)域的知識(shí)，實(shí)現(xiàn)解決特定問(wèn)題的一個(gè)遺傳算法特定實(shí)現(xiàn)，其范圍可能更窄，但效果會(huì)更好。遺傳算法在應(yīng)用中最關(guān)鍵的問(wèn)題有如下3個(gè)：串的編碼方式：其本質(zhì)是問(wèn)題編碼。一般把問(wèn)題的各種參數(shù)用二進(jìn)制編碼，構(gòu)成子串；然后把子串拼接構(gòu)成“染色體”串。串長(zhǎng)度及編碼形式對(duì)算法收斂影響極大。適應(yīng)度的確定：適應(yīng)度也稱適應(yīng)函數(shù)(fitnessfunction)或目標(biāo)函數(shù)(objectivefunction)，這是問(wèn)題求解品質(zhì)的測(cè)量函數(shù);往往也稱為問(wèn)題的“環(huán)境”。一般可以把問(wèn)題的模型函數(shù)作為目標(biāo)函數(shù)；但有時(shí)需要另行構(gòu)造。(4)遺傳算法自身參數(shù)設(shè)定：遺傳算法自身參數(shù)有3個(gè)，即群體大小n、交叉概率P。和變異概率P_,群體大小n太小時(shí)難以求出最優(yōu)解，太大則增長(zhǎng)收斂時(shí)間，一般n=30八-160;交叉概率Po太小時(shí)難以向前搜索，太大則容易破壞高適應(yīng)值的結(jié)構(gòu)，一般取P}=0.25A-0.75；變異概率Pm太小時(shí)難以產(chǎn)生新的基因結(jié)構(gòu)，太大使遺傳算法成了單純的隨機(jī)搜索，一般取Pm-0.01-0.2。事實(shí)上，遺傳算法不僅可以解決我們一般意義所理解的最優(yōu)化問(wèn)題，現(xiàn)在在越來(lái)越多的領(lǐng)域內(nèi)取得了成功：圖像分割，圖像檢測(cè)，圖像識(shí)別，神經(jīng)網(wǎng)絡(luò)權(quán)重設(shè)計(jì)，數(shù)據(jù)挖掘，載人航天，大壩安全監(jiān)測(cè)，天線設(shè)計(jì)，物流管理，控制理論，集成電路設(shè)計(jì)，聚類分析，醫(yī)療診斷，材料設(shè)計(jì)？?？梢?jiàn)，遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解拓展到了許多更新、更工程化的應(yīng)用方面?！?】2.3遺傳算法的應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域。2.3.1函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。很多人構(gòu)造出了各種各樣的復(fù)雜形式的測(cè)試函數(shù)，有連續(xù)函數(shù)也有離散函數(shù)，有凸函數(shù)也有凹函數(shù)，有低維函數(shù)也有高維函數(shù)，有確定函數(shù)也有隨機(jī)函數(shù)有單峰值函數(shù)也有多峰值函數(shù)等，用這些幾何特性各具特色的函數(shù)來(lái)評(píng)價(jià)遺傳算法的性能，更能反映算法的本質(zhì)效果。而對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問(wèn)題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。2.3.2組合優(yōu)化隨著問(wèn)題規(guī)模的增大，組合優(yōu)化問(wèn)題的搜索空間也急劇擴(kuò)大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對(duì)這類復(fù)雜問(wèn)題，人們已意識(shí)到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法已經(jīng)在求解旅行商問(wèn)題、背包問(wèn)題、裝箱問(wèn)題、布局優(yōu)化、圖形劃分問(wèn)題等各種具有NP難度的問(wèn)題得到成功的應(yīng)用。2.3.3生產(chǎn)調(diào)度問(wèn)題生產(chǎn)調(diào)度問(wèn)題在很多情況下建立起來(lái)的數(shù)學(xué)模型難以精確求解，即使經(jīng)過(guò)一些簡(jiǎn)化之后可以進(jìn)行求解，也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。目前在現(xiàn)實(shí)生產(chǎn)中主要是靠一些經(jīng)驗(yàn)來(lái)進(jìn)行調(diào)度。現(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問(wèn)題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用⑼。2.3.4自動(dòng)控制在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問(wèn)題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯示出良好的效果。例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計(jì)空間交會(huì)控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計(jì)、基于遺傳算法的參數(shù)辨識(shí)、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)等，都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性［11］。2.3.5機(jī)器人學(xué)機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來(lái)自于人工自適應(yīng)系統(tǒng)的研究，所以，機(jī)器人學(xué)理所當(dāng)然地成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。例如，遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用"均。2.3.6圖像處理圖像處理是計(jì)算機(jī)視覺(jué)中的一個(gè)重要研究領(lǐng)域。在圖像處理過(guò)程中，如掃描、特征提取、圖像分割等不可避免地會(huì)存在一些誤差，從而影響圖像的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺(jué)達(dá)到實(shí)用化的重要要求。遺傳算法在這些圖像處理中的優(yōu)化計(jì)算方面找到了用武之地，目前已在模式識(shí)別（包括漢字識(shí)別）、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用1101o2.3.7人工生命人工生命是用計(jì)算機(jī)、機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學(xué)習(xí)能力是人工生命的兩大主要特征。人工生命與遺傳算法有著密切的關(guān)系。基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論，雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力 ，并且必將得到更為深入的應(yīng)用和發(fā)展。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供一彳、有效的工具，人工生命的研究也必將促進(jìn)遺傳算法的進(jìn)一步發(fā)展。2.3.8遺傳編程1989年，美國(guó)Standford大學(xué)的Koza教授發(fā)展了遺傳編程的概念，其基本思想是:采用樹(shù)型結(jié)構(gòu)表示計(jì)算機(jī)程序，運(yùn)用遺傳算法的思想，通過(guò)自動(dòng)生成計(jì)算機(jī)程序來(lái)解決問(wèn)題。雖然遺傳編程的理論尚未成熟，應(yīng)用也有一些限制，但它已成功地應(yīng)用于人工智能、機(jī)器學(xué)習(xí)等領(lǐng)域，目前公開(kāi)的遺傳編程實(shí)驗(yàn)系統(tǒng)有十多個(gè)，例如,Koza開(kāi)發(fā)的ADF系統(tǒng),White開(kāi)發(fā)的GPELST系統(tǒng)等"。2.3.9機(jī)器學(xué)習(xí)學(xué)習(xí)能力是高級(jí)自適應(yīng)系統(tǒng)所具備的能力之一，基于遺傳算法的機(jī)器學(xué)習(xí)，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。例如，遺傳算法被用于學(xué)習(xí)模糊控制規(guī)則，利用遺傳算法來(lái)學(xué)習(xí)隸屬度函數(shù)，從而更好地改進(jìn)了模糊系統(tǒng)的性能；基于遺傳算法的機(jī)器學(xué)習(xí)可用來(lái)調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)，也可用于人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)；分類器系統(tǒng)也在學(xué)習(xí)式多機(jī)器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用。2.3.10數(shù)據(jù)挖掘數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫(kù)技術(shù)，它能夠從大型數(shù)據(jù)庫(kù)中提取隱含的、先前未知的、有潛在應(yīng)用價(jià)值的知識(shí)和規(guī)則。許多數(shù)據(jù)挖掘問(wèn)題可看成是搜索問(wèn)題，數(shù)據(jù)庫(kù)看作是搜索空間，挖掘算法看作是搜索策略。因此，應(yīng)用遺傳算法在數(shù)據(jù)庫(kù)中進(jìn)行搜索，對(duì)隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化，直到數(shù)據(jù)庫(kù)能被該組規(guī)則覆蓋,從而挖掘出隱含在數(shù)據(jù)庫(kù)中的規(guī)則。Sunilmi已成功地開(kāi)發(fā)了一個(gè)基于遺傳算法的數(shù)據(jù)挖掘工具，利用該工具對(duì)兩個(gè)飛機(jī)失事的真實(shí)數(shù)據(jù)庫(kù)進(jìn)行了數(shù)據(jù)挖掘?qū)嶒?yàn),結(jié)果表明遺傳算法是進(jìn)行數(shù)據(jù)挖掘的有效方法之一。1413遺傳算法的研究方向遺傳算法在各種問(wèn)題的求解與應(yīng)用中展現(xiàn)了其特點(diǎn)和魅力，同時(shí)也暴露出它在理論和應(yīng)用上的諸多不足和缺陷。未來(lái)幾年內(nèi)遺傳算法的研究重點(diǎn)可能集中在以下幾方面：算法的數(shù)學(xué)基礎(chǔ)，包括算法的收斂性、收斂速度估計(jì)、早熟機(jī)理的探索與預(yù)防、交叉算子的幾何意義與統(tǒng)計(jì)解釋、參數(shù)設(shè)置對(duì)算法的影響等方面。算法的收斂速度估計(jì)是當(dāng)前特別值得研究和探討的問(wèn)題，它能從理論上對(duì)遺傳算法的任何修正形式提供評(píng)判標(biāo)準(zhǔn)，從而指明改進(jìn)算法能的正確方向。遺傳算法與優(yōu)化技術(shù)的融合。對(duì)遺傳算法的大范圍群體搜索性能與快速收斂的局部?jī)?yōu)化方法進(jìn)行混合，從而產(chǎn)生有效的全局優(yōu)化方法。這種策略可從根本上提高遺傳算法計(jì)算性能，對(duì)此可以進(jìn)行大量的理論分析和實(shí)驗(yàn)。算法的改進(jìn)與深化。根據(jù)具體應(yīng)用領(lǐng)域?qū)z傳算法進(jìn)行改進(jìn)與完善，僅泛泛地對(duì)一■般問(wèn)題進(jìn)行研究是遠(yuǎn)遠(yuǎn)不夠的。當(dāng)前針對(duì)具體應(yīng)用問(wèn)題深化研究遺傳算法是特別值得提倡的工作。算法的選擇。基于實(shí)驗(yàn)研究的結(jié)論并不具有普遍意義上的指導(dǎo)作用，因此從數(shù)學(xué)的角度進(jìn)行遺傳算法的理論研究將對(duì)算法的合理選擇提供理論指導(dǎo)。算法的并行化研究。遺傳算法的群體適應(yīng)度評(píng)價(jià)、隨機(jī)搜索等特征使其具有明顯的并行性。因此，設(shè)計(jì)各種并行執(zhí)行策略、建立相應(yīng)的并行化遺傳算法的數(shù)學(xué)基礎(chǔ)，是一項(xiàng)具有重要意義的工作。參考文獻(xiàn)⑴王仁宏，數(shù)值逼近，北京:高等教育出版社.1999.李岳生，黃友謙，數(shù)值逼近，北京:人