遺傳算法論文范文10篇

編者按：本文主要從單親演化過程；群體演化過程；實驗結果與分析；結束語四個方面進行論述。其中，主要包括：TSP的搜索空間是有限的、很可能不存在確定的算法能在多項式時間內求到問題的解、遺傳算法是一種借鑒生物界自然選擇和遺傳機制的隨機化搜索算法、用遺傳算法求解TSP能得到令人滿意的結果、個體質量的高低決定了算法的全局性能、TSP編碼表示、構建TSP基因庫、單親演化算法、基因段錯位操作是隨機確定基因段、交叉算子、局部啟發式算子、選擇機制和收斂準則、基于多重搜索策略的群體演化算法、所有的結果都是在P42.0G微機上完成、該文算法的求解質量要優于GA、PGA、MMGA算法等，具體材料請詳見。

論文摘要：TSP是組合優化問題的典型代表,該文在分析了遺傳算法的特點后,提出了一種新的遺傳算法(GB—MGA),該算法將基因庫和多重搜索策略結合起來,利用基因庫指導單親遺傳演化的進化方向,在多重搜索策略的基礎上利用改進的交叉算子又增強了遺傳算法的全局搜索能力。通過對國際TSP庫中多個實例的測試,結果表明:算法(GB—MGA)加快了遺傳算法的收斂速度,也加強了算法的尋優能力。

論文關鍵詞：旅行商問題遺傳算法基因庫多重搜索策略

TSP(travelingsalesmanproblem)可以簡述為:有n個城市1,2,…,n,一旅行商從某一城市出發,環游所有城市后回到原出發地,且各城市只能經過一次,要求找出一條最短路線。TSP的搜索空間是有限的,如果時間不受限制的話,在理論上這種問題終會找到最優解,但對于稍大規模的TSP,時間上的代價往往是無法接受的。這是一個典型的組合最優化問題,已被證明是NP難問題,即很可能不存在確定的算法能在多項式時間內求到問題的解[1]。由于TSP在工程領域有著廣泛的應用,如貨物運輸、加工調度、網絡通訊、電氣布線、管道鋪設等,因而吸引了眾多領域的學者對它進行研究。TSP的求解方法種類繁多,主要有貪婪法、窮舉法、免疫算法[2]、螞蟻算法[3]、模擬退火算法、遺傳算法等。

遺傳算法是一種借鑒生物界自然選擇和遺傳機制的隨機化搜索算法,其主要特點是群體搜索策略和群體中個體之間的信息交換,搜索不依賴于梯度信息[4]。遺傳算法主要包括選擇、交叉和變異3個操作算子,它是一種全局化搜索算法,尤其適用于傳統搜索算法難于解決的復雜和非線性問題。遺傳算法雖然不能保證在有限的時間內獲得最優解,但隨機地選擇充分多個解驗證后,錯誤的概率會降到可以接受的程度。

用遺傳算法求解TSP能得到令人滿意的結果,但是其收斂速度較慢,而且種群在交叉算子作用下,會陷入局部解。采用局部啟發式搜索算法等,雖然能在很短的時間內計算出小規模城市的高質量解,一旦城市規模稍大就容易陷入局部最優解。因此,為了能夠加快遺傳算法的收斂速度,又能得到更好的近似最優解,該文采納了文[5]中楊輝提出的基因庫的想法,并結合文[6]中Cheng-FaTsai提出的多重搜索策略思想,使用單親演化與群體演化相結合的方式來求解TSP問題。該文根據文[7]中最小生成樹MST(minimumcostspanningtree)的應用,由MST建立TSP的基因庫,保存有希望成為最優解的邊,利用基因庫提高初始群體的質量進行單親演化,然后利用改進后的交叉算子和的多重搜索策略進行群體演化。

遺傳算法的思想由來已久。早在20世紀50年代，一些生物學家就著手于計算機模擬生物的遺傳系統。1967年，美國芝加哥大學的Holland,J.H.教授在研究適應系統時，進一步涉及進化演算的思考，并于1968年提出模式理論。1975年，Holland教授的專著《自然界和人工系統的適應性》問世，全面地介紹了遺傳算法，為遺傳算法奠定了基礎[228]。此后，遺傳算法無論在理論研究方面，還是實際應用方面都有了長足發展。

伴隨遺傳算法的發展，其獨特的優越性逐漸被體現出來，且各種理論、方法都得到了進一步發展和完善。但是，遺傳算法的實際應用仍然存在著缺陷，具體表現在：

遺傳算法在尋優過程中易出現“早熟”、設計變量增多時效率較低以及結構分析時間長，在線功能差。為此，在實際運用中尚需改進，尋找更優秀的算子和編碼方法等。目前，改進的方法也各有優劣，有對遺傳算法遺傳算子進行改進的，也有將遺傳算法與其他方法結合起來的。編碼方法有二進制編碼、多值編碼、實值編碼、區間值編碼、Delta編碼等多種編碼方法。在執行策略方面有如下幾種方法值得注意：遺傳算法與模擬退火算法的結合、遺傳算法與局部優化方法的結合、并行遺傳算法、共存演化遺傳算法、混亂遺傳算法。

遺傳算法的噪聲適應性問題。遺傳算法主要是針對無噪聲的確定性環境設計的，在應用過程中，知識的不確定性、訓練樣本的錯誤、人為因素等都可導致問題求解環境包含一個或多個噪聲。事實上，噪聲是不可避免的，在實際工程測量中，測量得到的靜態應變常常會伴有一定的噪聲。遺傳算法的進化過程是通過適應度大小來進行選擇、變異、交*等遺傳算子操作，從而對個體進行優勝劣汰。然而在噪聲環境下，目標函數或適應度帶有噪聲，不能反映個體真正的適應度。顯然，用有噪聲的適應度去進化，其結果可能會被誤導。在這種情況下，遺傳算法的性能如何，怎樣改進，還有待深入研究。

摘要本文通過對基本遺傳算法添加初始化啟發信息、改進交叉算子和利用本身所固有的并行性構架粗粒度并行遺傳算法等方法提高了遺傳算法的收斂性及其尋優能力。

關鍵詞遺傳算法；TSP；交叉算子

1引言

遺傳算法是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法?？偟恼f來，遺傳算法是按不依賴于問題本身的方式去求解問題。它的目標是搜索這個多維、高度非線性空間以找到具有最優適應值(即最小費用的)的點[1]。

基本遺傳算法是一個迭代過程，它模仿生物在自然環境中的遺傳和進化機理，反復將選擇算子、交叉算子和變異算子作用于種群，最終可得到問題的最優解和近似最優解。

2遺傳算法程序設計改進比較

1遺傳算法設計

1．1基因編碼設計

編碼就是將遺傳算法中處理不了的空間參數轉換成遺傳空間的由基因組成的染色體或個體的過程．其中基因在一定意義上包含了它所代表的問題的解．基因的編碼方式有很多，這也取決于要解決的問題本身．常見的編碼方式有：二進制編碼，基因用0或1表示，通常用于解決01背包問題，如基因A：00100011010（代表一個個體的染色體）；互換編碼，主要用于解決排序問題，如調度問題和旅行商問題，用一串基因編碼來表示遍歷城市順序，如234517986，表示在9個城市中先經過城市2，再經過城市3，依此類推；樹形編碼，用于遺傳規劃的演化編程或表示，其編碼的方法就是樹形結構中的一些函數，本文采用的是樹形編碼．

1．2交叉算子設計

交叉運算的含義是參照某種方式和交叉概率，將兩組相互配對的個體互換部分基因，生成新個體的過程．交叉運算在遺傳算法中起關鍵作用，是產生新個體的主要方法．交叉操作流程如圖1所示．交叉操作首先判定要交叉的基因是否相同，如果相同進行子基因組的交叉，然后再判定交叉是否完成，沒完成就繼續，完成就退出；如果交叉的基因不相同，就要選擇是否依據概率進行基因交換，選擇交換就交換其所有的次級基因結構，然后再判定交叉是否完成，選擇不交換就直接判定交叉是否完成．

1．3變異算子設計

摘要：本文運用遺傳算法的全局尋優對考試中的自動化組卷進行了研究，并得到了一個解決適合考方要求的試題模型的好的算法。

關鍵詞：遺傳算法全局尋優自動化組卷

1引言

計算機輔助考試系統的自動組卷的效率與質量完全取決于抽題算法的設計。如何設計一個算法從題庫中既快又好的抽出一組最佳解或是抽出一組非常接近最佳解的實體，涉及到一個全局尋優和收斂速度快慢的的問題，很多學者對其進行了研究。遺傳算法以其自適應尋優及良好的智能搜索技術，受到了廣泛的運用。PottsJC等人基于變異和人工選擇的遺傳算法對最優群體規模進行了論述；HamiltonMA等結合遺傳算法把其運用到神經網絡中，并取得了良好的效果[4]；也有眾多的學者對保留最佳狀態的遺傳算法的收斂速度做了討論。通過理論推導和事實運用，發現遺傳算法在尋優和收斂性方面都是非常有效的。

本文結合遺傳算法的原理和思想，對考試自動出題組卷的問題進行了研究，找到了一種獲得與考試試題控制指標符合的試題模型的解決方法。

2問題描述

摘要在浮點編碼遺傳算法中加入Powell方法，構成適于不可微函數全局優化的混合遺傳算法。混合算法改善了遺傳算法的局部搜索能力，顯著提高了遺傳算法求得全局解的概率。由于只利用函數值信息，混合算法是一種求解可微和不可微函數全局優化問題的通用方法。

關鍵詞全局最優；混合算法；遺傳算法；Powell方法

1引言

不可微非線性函數優化問題具有廣泛的工程和應用背景，如結構設計中使得結構內最大應力最小而歸結為極大極小優化（minmax）問題、數據魯棒性擬合中采取最小絕對值準則建立失擬函數等。其求解方法的研究越來越受到人們的重視，常用的算法有模式搜索法、單純形法、Powell方法等，但是這些方法都是局部優化方法，優化結果與初值有關。

近年來，由Holland研究自然現象與人工系統的自適應行為時，借鑒“優勝劣汰”的生物進化與遺傳思想而首先提出的遺傳算法，是一種較為有效的求不可微非線性函數全局最優解的方法。以遺傳算法為代表的進化算法發展很快，在各種問題的求解與應用中展現了其特點和魅力，但是其理論基礎還不完善，在理論和應用上暴露出諸多不足和缺陷，如存在收斂速度慢且存在早熟收斂問題[1,2]。為克服這一問題，早在1989年Goldberg就提出混合方法的框架[2]，把GA與傳統的、基于知識的啟發式搜索技術相結合，來改善基本遺傳算法的局部搜索能力，使遺傳算法離開早熟收斂狀態而繼續接近全局最優解。近來，文獻[3]和[4]在總結分析已有發展成果的基礎上，均指出充分利用遺傳算法的大范圍搜索性能，與快速收斂的局部優化方法結合構成新的全局優化方法，是目前有待集中研究的問題之一，這種混合策略可以從根本上提高遺傳算法計算性能。文獻[5]采用牛頓－萊佛森法和遺傳算法進行雜交求解旅行商問題，文獻[6]把最速下降法與遺傳算法相結合來求解連續可微函數優化問題，均取得良好的計算效果，但是不適于不可微函數優化問題。

本文提出把Powell方法融入浮點編碼遺傳算法，把Powell方法作為與選擇、交叉、變異平行的一個算子，構成適于求解不可微函數優化問題的混合遺傳算法，該方法可以較好解決遺傳算法的早熟收斂問題。數值算例對混合方法的有效性進行了驗證。

摘要在浮點編碼遺傳算法中加入Powell方法，構成適于不可微函數全局優化的混合遺傳算法?；旌纤惴ǜ纳屏诉z傳算法的局部搜索能力，顯著提高了遺傳算法求得全局解的概率。由于只利用函數值信息，混合算法是一種求解可微和不可微函數全局優化問題的通用方法。

關鍵詞全局最優；混合算法；遺傳算法；Powell方法

1引言

不可微非線性函數優化問題具有廣泛的工程和應用背景，如結構設計中使得結構內最大應力最小而歸結為極大極小優化（minmax）問題、數據魯棒性擬合中采取最小絕對值準則建立失擬函數等。其求解方法的研究越來越受到人們的重視，常用的算法有模式搜索法、單純形法、Powell方法等，但是這些方法都是局部優化方法，優化結果與初值有關。

近年來，由Holland研究自然現象與人工系統的自適應行為時，借鑒“優勝劣汰”的生物進化與遺傳思想而首先提出的遺傳算法，是一種較為有效的求不可微非線性函數全局最優解的方法。以遺傳算法為代表的進化算法發展很快，在各種問題的求解與應用中展現了其特點和魅力，但是其理論基礎還不完善，在理論和應用上暴露出諸多不足和缺陷，如存在收斂速度慢且存在早熟收斂問題[1,2]。為克服這一問題，早在1989年Goldberg就提出混合方法的框架[2]，把GA與傳統的、基于知識的啟發式搜索技術相結合，來改善基本遺傳算法的局部搜索能力，使遺傳算法離開早熟收斂狀態而繼續接近全局最優解。近來，文獻[3]和[4]在總結分析已有發展成果的基礎上，均指出充分利用遺傳算法的大范圍搜索性能，與快速收斂的局部優化方法結合構成新的全局優化方法，是目前有待集中研究的問題之一，這種混合策略可以從根本上提高遺傳算法計算性能。文獻[5]采用牛頓－萊佛森法和遺傳算法進行雜交求解旅行商問題，文獻[6]把最速下降法與遺傳算法相結合來求解連續可微函數優化問題，均取得良好的計算效果，但是不適于不可微函數優化問題。

本文提出把Powell方法融入浮點編碼遺傳算法，把Powell方法作為與選擇、交叉、變異平行的一個算子，構成適于求解不可微函數優化問題的混合遺傳算法，該方法可以較好解決遺傳算法的早熟收斂問題。數值算例對混合方法的有效性進行了驗證。

摘要：遺傳算法是根據生物學上的染色體基因因子構成機制而產生的一種啟發式算法。該算法以群體中的所有個體為對象，通過選擇、交叉、變異和重排序等類似生物遺傳的操作算子，得到滿足一定群體適應度的新種群。遺傳算法為頻率分配問題提供了解決途徑。

關鍵字：頻率分配遺傳算法GECP組合優化

1.通信網頻率分配問題的背景

無線通信設備之間通過相互發射電磁波達成信息溝通。相互通信的設備之間使用特定的頻率（信道）構成無線通信鏈路。由于電磁波的自然特性，無線通信設備發射的電磁波可能對位于附近、滿足一定功率和頻率條件的其它設備形成干擾。頻率分配（FAP）的目的就是給工作在一定地域內的無線通信設備指定使用的工作頻率(或信道)，使所有設備都以盡量小的概率被干擾，從而使整個網絡的可用性得到優化。FAP可以描述為：對N個給定的待分配工作頻率的鏈路，設G={S1,S2,…Sn}為所有狀態構成的解空間，C(si)為狀態si對應的目標函數值，尋找最優解s*，使任意si∈G，C(s*)=minC（si）。因此FAP是一種組合優化問題。

具體設備頻率分配方法雖然會隨著設備的工作方式（單工、雙工）、工作頻段、天線類型、信號的調制解調方式的不同而有所區別，但是大部分頻率分配算法都可以轉換為等價的圖的邊著色問題。從圖論算法理論上講，圖的廣義邊著色問題是NPC問題[7]，也就是說無法在多項式時間內求得問題的最優解。例如對于存在n條邊的無向圖，使用c種顏色對其著色，在沒有其它約束條件下，其解空間是cn。即使在不考慮顏色重復使用（c>n）的情況下，其解空間也達到n!。這兩者都是超越數，在c和n的值較大的情況下想利用窮舉搜索的方法求得問題的最優解在時間上是不可行的。

在工程實踐中許多NPC問題使用一些使用的近似算法得到問題的可行解。這些方法包括[]：只對問題的特殊實例求解；動態規劃（DP）或者分支界限算法（BC）；概率算法；求近似解；啟發式算法（HeufisticAlgorithms）等。這些方法的和核心是分割問題的解空間，按照特定規則搜索典型解作為次最優解。

論文摘要:將一種在在水質評價中得到廣泛應用的評價方法——投影尋蹤評價法引入生態城市評價領域中。采用基于實數遺傳算法的投影尋蹤評價法，以生態城市課題組建立的指標體系(指標涉及資源，經濟，社會，環境，體制等各方面因素)為基礎，利用M棚AB軟件對石家莊市2000~~2007年的生態城市建設進行了評價。

論文關鍵詞:投影尋蹤法；生態城市評價；石家莊市

“生態城市”是20世紀80年代產生的一個全新概念，指將“生態系統”思想引入到城市建設和管理的過程中。它最早是由前蘇聯生態學家0．Yanitsky1971年在聯合國教科文組織發起“人與生物圈計劃(MAB)”時提出的。之后，很多學者都對其進行了研究，并給出了定義。如1984年城市生態學家0．Yanistky提出，生態城市是指自然、技術、人文充分融合，物質、能量、信息高效利用，人的創造力和生產力得到最大限度的發揮，居民的身心健康和環境質量得到維護，一種生態、高效、和諧的人類聚居新環境。美國生態學家R．Richard認為，生態城市即生態健康的城市，是低污、緊湊、節能、充滿活力并與自然和諧共存的聚居地。雖然生態城市的概念尚處于不停的爭論、探索、修改、完善之中，但在原則問題上，人們已經達成一些基本共識：“生態城市”的核心思想是它的區域整體觀和可持續發展的生態觀，且一般要求具有以下幾種特性：和諧性、高效性、持續性、整體性、區域性、結構合理以及關系協調。

1生態城市測評方法概述

生態城市評價是生態城市建設的基礎工作，一套科學客觀的生態城市評價體系應具備以下功能：①幫助在操作層次理解什么是生態城市；②使城市建設轉向生態城市建設；③衡量生態城市建設的趨勢和速度，綜合衡量生態城市各子系統的協調程度。

具體到測評方法而言，不同的測評方法從不同的角度描述指標體系的屬性，由于各種方法的機理不同，方法的層次屬性相異，在應用不同的測評方法時，測評的結果也存在差異。因此，要反映一個城市的全貌，體現上述生態城市的內涵要求，必須從多角度、全方位進行研究，這樣得出的結論才能體現城市系統的本質和原貌。在數學分析方面，系統科學專家運用定量分析技術開發了幾十種測評方法。目前，常用的主要有層次分析法(AnalyticHierarchyProcess，AHP)，因子分析法(FactorAnalysis，FA)以及網絡層次分析法(ANP)等。但是，這些方法都有其局限性。層次分析法對應生態城市評價是不適用的，因為指標之間是不完備、不互斥的；因子分析法是較常用且簡單的方法，能夠反映生態城市建設的大概狀況，但會丟失部分信息；網絡分析法能夠比因子分析法更全面地反映生態城市的概況，但其前提是各因子之間的關系比較清晰，這一過程需要作大量的研究工作。該文借鑒在水質評價中得到廣泛應用，并被實踐證明比較科學、合理的評價方法——投影尋蹤評價法，將其應用到生態城市評價體系中。

摘要：復雜函數的全局最優化問題是在求解各種復雜工程與科學計算問題中提煉出來的亟待解決的計算問題，均勻設計具有讓試驗點在高維空間內均勻分散的特點，而Powell算法具有很好的求解局部最優解的能力，將兩種方法進行有效改進后使之相結合，設計出并行全局最優化算法。通過經典的全局最優化函數對算法進行了比較測試，發現該算法具有比以前的算法更好的尋優能力，并對算法時間、空間復雜度以及并行性進行分析和測試?；诰鶆蛟O計與Powell算法的全局最優化并行算法具有尋優能力強，時間開銷與問題因素個數的平方和布點數成線性復雜度，空間開銷與因素個數和布點數成線性復雜度，并行效率好的特點。

關鍵詞：并行計算；均勻設計；Powell算法；全局最優化

0引言

最優化理論方法是應用數學的一門分支，研究決策問題的最佳選擇，構造尋找最佳解的計算方法，探討這些計算方法的理論性質及計算表現。目前，求解線性規劃、非線性規劃、隨機規劃、非光滑規劃、多目標規劃、組合優化等各種最優化問題的新方法不斷涌現。除了自然科學的各個領域之外，在建筑設計、金融設計、醫藥設計、生產管理、交通運輸等諸多方面均涉及最優化的應用。隨著高速計算機的普及和優化方法的不斷進步，規模越來越大的優化問題得到解決。

面對最優化問題，目前的困難主要表現在兩個方面：①目標函數常常多峰，隨著優化問題規模的增大，局部最優解的數目將會迅速增加，往往得到的是局部最優解，而不能得到全局最優解。如何有效地跳出局部最優點而又不大幅度地增加計算代價，是目前的一個難題。②許多在串行計算環境下的最優化算法并不適合于并行環境，并行化難度大。

首先利用均勻設計具有使實驗點高維空間均勻分散的特點，與Powell算法結合，并適當改進，經過經典的全局最優化函數測試發現它能夠跳出局部最優陷阱，從而準確地找到全局最優點。最后，對算法的時間空間復雜度進行了測試，數據統計顯示本文算法時間復雜度與計算問題需要考慮的因素個數的二次方和布點數成線性關系，空間復雜度與因素個數和布點數成線性關系。對算法進行了并行化，經測試得知并行效率很高。該算法具有很好的求解大型優化問題的潛力。