【正文】 多領(lǐng)域得到了應(yīng)用. 該文將從遺傳算法的理論和技術(shù)兩方面概述目前的研究現(xiàn)狀描述遺傳算法的主要特點(diǎn)、基本原理以及改進(jìn)算法，介紹遺傳算法的應(yīng)用領(lǐng)域，并用MATLAB實(shí)現(xiàn)了遺傳算法及最優(yōu)解的求解.2 文獻(xiàn)綜述 國內(nèi)外研究現(xiàn)狀及評(píng)價(jià)國內(nèi)外有不少的專家和學(xué)者對(duì)遺傳算法的進(jìn)行研究與改進(jìn). 比如：1991年（ADJACENCY BASED CROSSOVER） ，這個(gè)算子是特別針對(duì)用序號(hào)表示基因的個(gè)體的交叉，并將其應(yīng)用到了TSP問題中，通過實(shí)驗(yàn)對(duì)其進(jìn)行了驗(yàn)證. 2022年，戴曉明等應(yīng)用多種群遺傳并行進(jìn)化的思想，對(duì)不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進(jìn)行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題. 國內(nèi)外很多文獻(xiàn)都對(duì)遺傳算法進(jìn)行了研究. 現(xiàn)查閱到的國內(nèi)參考文獻(xiàn)[119]中, 周勇、周明分別在文獻(xiàn)[1]、[2]中介紹了遺傳算法的基本原理；徐宗本在文獻(xiàn)[3]中探討了包括遺傳算法在內(nèi)的解全局優(yōu)化問題的各類算法，文本次論文寫作提出了明確的思路；張文修、王小平、張鈴分別在文獻(xiàn)[4]、[5]、[6]從遺傳算法的理論和技術(shù)兩方面概述目前的研究現(xiàn)狀；李敏強(qiáng)、吉根林、玄光南分別在文獻(xiàn)[7]、[8]、[9]中都不同程度的介紹了遺傳算法的特點(diǎn)以及改進(jìn)算法但未進(jìn)行深入研究；馬玉明、張麗萍、戴曉輝、柴天佑分別在文獻(xiàn)[10]、[11]、[12]、[13]中探討了遺傳算法產(chǎn)生的背景、起源和發(fā)展；李敏強(qiáng)、徐小龍、林丹、張文修分別在文獻(xiàn)[14]、[15]、[16]、[17]探討了遺傳算法的發(fā)展現(xiàn)狀及以后的發(fā)展動(dòng)向；李敏強(qiáng)，寇紀(jì)凇，林丹，李書全在文獻(xiàn)2[18]中主要論述了遺傳算法的具體的實(shí)施步驟、應(yīng)用領(lǐng)域及特點(diǎn)；孫祥，徐流美在文獻(xiàn)[19]中主要介紹了Matlab的編程語句及基本用法. 所有的參考文獻(xiàn)都從不同角度不同程度的介紹了遺傳算法但都不夠系統(tǒng)化不夠詳細(xì)和深入. 提出問題隨著研究的深入，人們逐漸認(rèn)識(shí)到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能，也不現(xiàn)實(shí)，因而求出近似最優(yōu)解或滿意解是人們的主要著眼點(diǎn)之一. 很多人構(gòu)造出了各種各樣的復(fù)雜形式的測(cè)試函數(shù)，有連續(xù)函數(shù)，有離散函數(shù)，有凸函數(shù)，也有凹函數(shù)，人們用這些幾何特性各異的函數(shù)來評(píng)價(jià)遺傳算法的性能. 而對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題用其他優(yōu)化方法較難求解遺傳算法卻可以方便地得到較好的結(jié)果. 鑒于遺傳算法在函數(shù)優(yōu)化方面的重要性，該文在參考文獻(xiàn)[119]的基礎(chǔ)上，用Matlab語言編寫了遺傳算法程序, 并通過了調(diào)試用一個(gè)實(shí)際例子來對(duì)問題進(jìn)行了驗(yàn)證，這對(duì)在Matlab環(huán)境下用遺傳算法來解決優(yōu)化問題有一定的意義.3 遺傳算法的理論研究 遺傳算法的產(chǎn)生背景科學(xué)研究、工程實(shí)際與國民經(jīng)濟(jì)發(fā)展中的眾多問題可歸結(jié)作“極大化效益、極小化代價(jià)”這類典型模型. 求解這類模型導(dǎo)致尋求某個(gè)目標(biāo)函數(shù)（有解析表達(dá)式或無解析表達(dá)式）在特定區(qū)域上的最優(yōu)解. 而為解決最優(yōu)化問題目標(biāo)函數(shù)和約束條件種類繁多，有的是線性的，有的是非線性的；有的是連續(xù)的，有的是離散的；有的是單峰值的，有的是多峰值的. 隨著研究的深入，人們逐漸認(rèn)識(shí)到：在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能，也不現(xiàn)實(shí)，因而求出近似最優(yōu)解或滿意解是人們的主要著眼點(diǎn)之一. 總的來說，求最優(yōu)解或近似最優(yōu)解的方法有三種: 枚舉法、啟發(fā)式算法和搜索算法.(1)枚舉法. 枚舉出可行解集合內(nèi)的所有可行解以求出精確最優(yōu)解. 對(duì)于連續(xù)函數(shù)，該方法要求先對(duì)其進(jìn)行離散化處理，這樣就有可能產(chǎn)生離散誤差而永遠(yuǎn)達(dá)不到最優(yōu)解. 另外，當(dāng)枚舉空間比較大時(shí)該方法的求解效率比較低，有時(shí)甚至在目前最先進(jìn)的計(jì)算工具上都無法求解.(2)啟發(fā)式算法. 尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則以找到一個(gè)最優(yōu)解或近似最3優(yōu)解. 該方法的求解效率雖然比較高，但對(duì)每一個(gè)需要求解的問題都必須找出其特有的啟發(fā)式規(guī)則，這個(gè)啟發(fā)式規(guī)則無通用性不適合于其它問題.(3)搜索算法. 尋求一種搜索算法，該算法在可行解集合的一個(gè)子集內(nèi)進(jìn)行搜索操作以找到問題的最優(yōu)解或近似最優(yōu)解. 該方法雖然保證了一定能夠得到問題的最優(yōu)解，但若適當(dāng)?shù)乩靡恍﹩l(fā)知識(shí)就可在近似解的質(zhì)量和求解效率上達(dá)到一種較好的平衡.隨著問題種類的不同以及問題規(guī)模的擴(kuò)大，要尋求一種能以有限的代價(jià)來解決上述最優(yōu)化問題的通用方法仍是一個(gè)難題. 而遺傳算法卻為我們解決這類問題提供了一個(gè)有效的途徑和通用框架開創(chuàng)了一種新的全局優(yōu)化搜索算法. 遺傳算法的起源與發(fā)展 遺傳算法的起源50年代末到60年代初，自然界生物進(jìn)化的理論被廣泛接受生物學(xué)家Fraser，試圖通過計(jì)算的方法來模擬生物界“遺傳與選擇”的進(jìn)化過程，這是遺傳算法的最早雛形. 受一些生物學(xué)家用計(jì)算機(jī)對(duì)生物系統(tǒng)進(jìn)行模擬的啟發(fā)，Holland開始應(yīng)用模擬遺傳算子研究適應(yīng)性. 在1967年，Bagley關(guān)于自適應(yīng)下棋程序的論文中，他應(yīng)用遺傳算法搜索下棋游戲評(píng)價(jià)函數(shù)的參數(shù)集并首次提出了遺傳算法這一術(shù)語. 1975年，Holland出版了遺傳算法歷史上的經(jīng)典著作《自然和人工系統(tǒng)中的適應(yīng)性》，首次明確提出遺傳算法的概念. 該著作中系統(tǒng)闡述了遺傳算法的基本理論和方法，并提出了模式(schemat atheorem)[4]，證明在遺傳算子選擇、交叉和變異的作用下具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將以指數(shù)級(jí)增長(zhǎng). Holand創(chuàng)建的遺傳算法，是基于二進(jìn)制表達(dá)的概率搜索方法. 在種群中通過信息交換重新組合新串；根據(jù)評(píng)價(jià)條件概率選擇適應(yīng)性好的串進(jìn)入下一代；經(jīng)過多代進(jìn)化種群最后穩(wěn)定在適應(yīng)性好的串上. Holand最初提出的遺傳算法被認(rèn)為是簡(jiǎn)單遺傳算法的基礎(chǔ)，也稱為標(biāo)準(zhǔn)遺傳算法. 遺傳算法的發(fā)展(1)20世紀(jì)60年代，John Holland教授和他的數(shù)位博士受到生物模擬技術(shù)的啟發(fā)，認(rèn)識(shí)到自然遺傳可以轉(zhuǎn)化為人工遺傳算法. 1962年，John Holland提出了利用群體進(jìn)化模擬適應(yīng)性系統(tǒng)的思想，引進(jìn)了群體、適應(yīng)值、選擇、變異、交叉等基本概念.(2)1967年，“遺傳算法”的概念.(3)1975年，Holland出版了《自然與人工系統(tǒng)中的適應(yīng)性行為》（Adaptation in 4Natural and Artificial System）.該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，提出了遺傳算法的基本定理—模式定理，從而奠定了遺傳算法的理論基礎(chǔ). 同年De Jong在其博士論文中，首次把遺傳算法應(yīng)用于函數(shù)優(yōu)化問題對(duì)遺傳算法的機(jī)理與參數(shù)進(jìn)行了較為系統(tǒng)地研究并建立了著名的五函數(shù)測(cè)試平臺(tái).(4)20世紀(jì)80年代初，Holland教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)—分類器系統(tǒng)（Classifier System簡(jiǎn)稱CS），開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念.(5)1989年，David Goldberg出版了《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》（Geic Algorithms in Search Optimization and Machine Learning）.該書全面系統(tǒng)地總結(jié)了當(dāng)時(shí)關(guān)于遺傳算法的研究成果，結(jié)合大量的實(shí)例完整的論述了遺傳算法的基本原理及應(yīng)用，奠定了現(xiàn)代遺傳算法的基礎(chǔ).(6)1992年，John 《遺傳編程》（Geic Programming）提出了遺傳編程的概念，并成功地把遺傳編程的方法應(yīng)用于人工智能、機(jī)器學(xué)習(xí)、符號(hào)處理等方面. 隨著遺傳算法的不斷深入和發(fā)展，關(guān)于遺傳算法的國際學(xué)術(shù)活動(dòng)越來越多，遺傳算法已成為一個(gè)多學(xué)科、多領(lǐng)域的重要研究方向.今天遺傳算法的研究已經(jīng)成為國際學(xué)術(shù)界跨學(xué)科的熱門話題之一. 遺傳算法是一種有廣泛應(yīng)用前景的算法，但是它的研究和應(yīng)用在國內(nèi)尚處于起步階段. 近年來遺傳算法已被成功地應(yīng)用于工業(yè)、經(jīng)濟(jì)管理、交通運(yùn)輸、工業(yè)設(shè)計(jì)等不同領(lǐng)域解決了許多、流水車間調(diào)度、作業(yè)車間調(diào)度、機(jī)器調(diào)度、設(shè)備布局設(shè)計(jì)、圖像處理以及數(shù)據(jù)挖掘等. 遺傳算法的數(shù)學(xué)基礎(chǔ)研究模式定理及隱含并行性原理被看作遺傳算法的兩大基石，后來又提出了建筑塊假設(shè)，但是模式定理無法解釋遺傳算法實(shí)際操作中的許多現(xiàn)象，隱性并行性的論證存在嚴(yán)重漏洞，而建筑塊假設(shè)卻從未得到過證明. 對(duì)遺傳算法的基礎(chǔ)理論的研究主要分三個(gè)方面：模式定理的拓廣和深入、遺傳算法的新模型、遺傳算法的收斂性理論.(1)模式定理的拓廣和深入. Holland給出模式定理：具有短的定義長(zhǎng)度、低階、并且模式采樣的平均適應(yīng)值在種群平均適應(yīng)值以上的模式在遺傳迭代過程中將按指數(shù)增長(zhǎng)率被采樣模式定理可表達(dá)為：m(H,t+1)?m(H,t). ??fH. ?????????.? (1)5其中m(Ht)：在t代群體中存在模式H 的串的個(gè)數(shù).??f：在t 代群體中包含模式H 的串的平均適應(yīng)值.：表示串的長(zhǎng)度 pc表示交換概率 pm表示變異概率.Holland的模式定理奠定了遺傳算法的數(shù)學(xué)基礎(chǔ)根據(jù)隱性并行性得出每一代處理有效模式的下限值是 ??l213.其中n是種群的大小 c1是小整數(shù). Bertoui和Dorigo進(jìn)行了深入的研究獲得當(dāng) ?l?,β為任意值時(shí)處理多少有效模式的表達(dá)式. 上海交通大學(xué)的惲為民等獲得每次至少產(chǎn)生 1?no數(shù)量級(jí)的結(jié)果. 模式定理中模式適應(yīng)度難以計(jì)算的概念采用Walsh函數(shù)的離散形式有效地計(jì)算出模式的平均適應(yīng)度并對(duì)遺傳算法進(jìn)行了有效的分析. 1972年Frantz首先發(fā)現(xiàn)一種常使GA從全局最優(yōu)解發(fā)散出去的問題，稱為GA欺騙題 [5]. Goldberg最早運(yùn)用Walsh模式轉(zhuǎn)換設(shè)計(jì)出最小的GA欺騙問題并進(jìn)行了詳細(xì)分析.(2)遺傳算法的新模型. 由于遺傳算法中的模式定理和隱性并行性存在不足之處，為了搞清楚遺傳算法的機(jī)理，近幾年來人們建立了各種形式的新模型最為典型的是馬氏鏈模型遺傳算法的馬氏鏈模型 [67]，主要由三種分別是種群馬氏鏈模型、Vose模型和Cerf 擾動(dòng)馬氏鏈模型. 種群馬氏鏈模型將遺傳算法的種群迭代序列視為一個(gè)有限狀態(tài)馬氏鏈來加以研究，運(yùn)用種群馬氏鏈模型轉(zhuǎn)移概率矩陣的某些一般性質(zhì)分析遺傳算法的極限行為，但轉(zhuǎn)移概率的具體形式難以表達(dá)妨礙了對(duì)遺傳算法的有限時(shí)間行為的研究；Vose模型是在無限種群假設(shè)下利用相對(duì)頻率導(dǎo)出，表示種群的概率的向量的迭代方程，通過這一迭代方程的研究，可以討論種群概率的不動(dòng)點(diǎn)及其穩(wěn)定性，從而導(dǎo)致對(duì)遺傳算法的極限行為的刻畫，但對(duì)解釋有限種群遺傳算法的行為的能力相對(duì)差一些. Cerf擾動(dòng)模型是法國學(xué)者Cerf將遺傳算法看成一種特殊形式的廣義模擬退火模型，利用了動(dòng)力系統(tǒng)的隨機(jī)擾動(dòng)理論，對(duì)遺傳算法的極限行為及收斂速度進(jìn)行了研究. 還有其它改進(jìn)模型，例如張鈴、張鈸等人提出的理想濃度模型，它首先引入濃度和家族的概念，通過濃度計(jì)算建立理想濃度模型 [810]，其濃度變化的規(guī)律為：6c(Hi，t +1)=c (H，t) .??tfOi, (2)c(Hi，t+1)表示模式Hi在t時(shí)刻的濃度，并對(duì)其進(jìn)行分析，得出結(jié)論：遺傳算法本質(zhì)上是一個(gè)具有定向制導(dǎo)的隨機(jī)搜索技術(shù)，其定向制導(dǎo)原則是導(dǎo)向適應(yīng)度高的模式為祖先的染色體“家族”方向.(3)遺傳算法的收斂性理論. 對(duì)于遺傳算法的馬氏鏈分析本身就是建立遺傳算法的收斂性理論 [1112]， Eiben等用馬爾可夫鏈證明了保留最優(yōu)個(gè)體的遺傳算法的概率性全局收斂，Rudolph用齊次有限馬爾可夫鏈證明了具有復(fù)制、交換、突變操作的標(biāo)準(zhǔn)遺傳算法收斂不到全局最優(yōu)解，不適合于靜態(tài)函數(shù)的優(yōu)化問題，建議改變復(fù)制策略以達(dá)到全局收斂，Back和Muhlenbein研究了達(dá)到全局最優(yōu)解的算法的時(shí)間復(fù)雜性問題，近幾年，徐宗本等人建立起鞅序列模型，利用鞅序列收斂定理證明了遺傳算法的收斂性. 遺傳算法的組成要素遺傳算法所涉及的五大要素：參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作的設(shè)計(jì)和控制參數(shù)的設(shè)定，其具體內(nèi)容如下：(1)參數(shù)編碼. 遺傳算法中常用的編碼方法是二進(jìn)制編碼，它將問題空間的參數(shù)用字符集{0，1}構(gòu)成染色體位串，符合最小字符集原則，操作簡(jiǎn)單，便于用模式定理分析.(2)適應(yīng)度函數(shù)的設(shè)計(jì). 適應(yīng)度函數(shù)是評(píng)價(jià)個(gè)體適應(yīng)環(huán)境的能力，使選擇操作的依據(jù)，是由目標(biāo)函數(shù)變換而成. 對(duì)適應(yīng)度函數(shù)唯一的要求是其結(jié)果為非負(fù)值. 適應(yīng)度的尺度變換是對(duì)目標(biāo)函數(shù)值域的某種映射變換，可克服未成熟收斂和隨機(jī)漫游現(xiàn)象. 常用的適應(yīng)度函數(shù)尺度變化方法主要有線性變換、冪函數(shù)變換和指數(shù)變換. [13](3)遺傳操作的設(shè)計(jì). 包括選擇、交叉、變異.①選擇(Selection). 選擇是用來確定交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體. 其主要思想是個(gè)體的復(fù)制概率正比于其適應(yīng)值，但按比例選擇不一定能達(dá)到好的效果. 選擇操作從早期的輪盤賭選擇發(fā)展到現(xiàn)在最佳個(gè)體保存法、排序選擇法、聯(lián)賽選擇法、隨機(jī)遍歷抽樣法、局部選擇法、柔性分段復(fù)制、穩(wěn)態(tài)復(fù)制、最優(yōu)串復(fù)制、最優(yōu)串保留等.②交叉(Crossover). 交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新7個(gè)體的操作，其作用是組合出新的個(gè)體，在串空間進(jìn)行有效搜索，同時(shí)降低對(duì)有效模式的破壞概率. 各種交叉算子均包含兩個(gè)基本內(nèi)容：確定交叉點(diǎn)的位置和進(jìn)行部分基因的交換. 常用的交叉操作方法有單點(diǎn)交叉、雙點(diǎn)交叉、一致交叉、均勻交叉、算術(shù)交叉、二維交叉、樹結(jié)構(gòu)交叉、部分匹配交叉、順序交叉和周期交叉等等.③變異(Mutation). 變異是指將個(gè)體編碼串中的某些基因值用其它基因值來替換,形成一個(gè)新的個(gè)體. 遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，其目的是使遺傳算法具有局部的隨機(jī)搜索能力和保持群體的多樣性. 變異算法包括確定變異點(diǎn)的位置和進(jìn)行基因值替換