基于遺傳算法的01背包問題研究

基于遺傳算法的0-1背包問題研究摘要本文介紹了0-1背包問題的基本概念，總結(jié)了解決0-1背包問題的傳統(tǒng)方法。問題中的應(yīng)用；利用Matlab仿真平臺對兩個實例進行了測試，證明了遺傳算法解決背包問題的有效性；通過實例分析了種群規(guī)模、迭代次數(shù)和變異概率對算法結(jié)果的影響；圖形用戶界面（GUI）實現(xiàn)參數(shù)的輸入和仿真結(jié)果的顯示。關(guān)鍵詞：0-1背包問題；遺傳算法；人口規(guī)模；MATLAB；圖形用戶界面目錄摘要一摘要二目錄III前言五第1章引言11.1背包問題介紹11.1.10-1背包問題背景11.1.2背包問題研究現(xiàn)狀11.2遺傳算法介紹21.2.1遺傳算法研究現(xiàn)狀及發(fā)展趨勢31.2.2遺傳算法的特點51.2.3遺傳算法的分類61.2.4遺傳算法的應(yīng)用71.3本文主要工作7第2章基于遺傳算法的0-1背包問題研究92.1遺傳算法的思想92.1.1遺傳算法的數(shù)學(xué)基礎(chǔ)102.1.2遺傳算法的基本原理122.1.3遺傳算法的實現(xiàn)過程132.2用遺傳算法解決0-1背包問題162.3數(shù)值實驗及結(jié)果分析202.3.1示例1212.3.2示例224第3章GUI界面設(shè)計293.1概述293.2GUI界面設(shè)計293.2.1GUI界面設(shè)計步驟293.2.2界面運行結(jié)果33第四章結(jié)論與展望364.1結(jié)論364.2展望36總結(jié)與經(jīng)驗38到40參考文獻41附錄1源程序43MATLAB主程序43GUI界面設(shè)計程序51附錄二外文文件翻譯60附錄三外文文獻71前言背包問題是一個組合優(yōu)化NP-完全問題，類似問題經(jīng)常出現(xiàn)在商業(yè)、組合學(xué)、計算復(fù)雜性理論、密碼學(xué)、應(yīng)用數(shù)學(xué)等領(lǐng)域。背包問題可分為一維背包問題、二維背包問題、完全背包問題、多重背包問題、分組背包問題等。0-1背包問題作為最基本的背包問題，包括背包問題的設(shè)計狀態(tài)和方程的最基本思想。因此，其他背包問題也可以轉(zhuǎn)化為0-1背包問題來求解。遺傳算法

算法）是從生物世界的進化規(guī)律（適者生存，適者生存的遺傳機制）演化而來的一種隨機搜索方法。由美國J.Holland教授于1975年首次提出，其主要特點是直接對結(jié)構(gòu)對象進行運算，對推導(dǎo)和功能連續(xù)性沒有限制；具有出色的并行性和更好的全局優(yōu)化能力；使用概率優(yōu)化方法，可以自動獲取并引導(dǎo)優(yōu)化后的搜索空間，自適應(yīng)調(diào)整搜索方向，不需要一定的規(guī)則。遺傳算法的這些特性已廣泛應(yīng)用于組合優(yōu)化、機器學(xué)習(xí)、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代智能計算的關(guān)鍵技術(shù)。文中詳細介紹了遺傳算法的數(shù)學(xué)基礎(chǔ)、基本原理和實現(xiàn)過程，給出了兩個利用遺傳算法求解0-1背包問題的例子并得到了相關(guān)的仿真結(jié)果，仿真結(jié)果進行了分析。然后，通過設(shè)置不同的種群規(guī)模、交叉概率和迭代次數(shù)，討論了這些算子對遺傳算法求解背包問題性能的影響。最后在matlab環(huán)境下設(shè)計了GUI界面。通過GUI界面，可以直觀地看到0-1背包問題的兩個例子在不同參數(shù)設(shè)置下的仿真曲線變化。第一章介紹1.1背包問題簡介1.1.10-1背包問題背景背包問題是Markel和Hellman提出的一類具有實際應(yīng)用背景的經(jīng)典NP問題[1]。背包問題的主要思想是假設(shè)一個人有大量物品，物品的重量不同，他想選擇一些物品放入背包中。物品的重量是已知的，所有可能的物品也是已知的，但背包里的物品是除了背包的重量限制之外的。列出大規(guī)模背包問題的所有可能項目在計算上是不可能的。在各類背包問題中，0-1背包問題是最基本的背包問題，其他的背包問題往往可以轉(zhuǎn)化為0-1背包問題。在我們的現(xiàn)實生活中，很多問題都可以用背包問題來描述，比如工廠的裁剪材料問題、管理中的資源配置問題、包裝箱問題、資金預(yù)算問題等等。建模為背包問題。此外，背包問題經(jīng)常作為其他復(fù)雜組合優(yōu)化問題的子問題出現(xiàn)。對于由簡單結(jié)構(gòu)組成的復(fù)雜結(jié)構(gòu)，深入探索簡單問題往往可以解決復(fù)雜問題。因此，在前人研究經(jīng)驗的基礎(chǔ)上開展背包問題的研究具有重要意義。1.1.2背包問題研究現(xiàn)狀Dantzing于1950年代首次進行開創(chuàng)性研究，利用貪心算法[2]獲得0-1背包問題的最優(yōu)解的上界。在接下來的20年里，背包問題并沒有得到很大的發(fā)展。直到1974年，hoeowitz和salmi使用分支節(jié)點方法[3]解決了背包問題。他們提出了背包問題的可分離性，并指出了解決該問題的新途徑。隨后balas和zemel提出了背包問題的“核”思想，使背包問題的研究得到了長足的發(fā)展。1990年代以后，隨著仿生技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，各種模擬生物物理規(guī)律的并行逼近算法不斷涌現(xiàn)。例如，遺傳算法已經(jīng)很好地應(yīng)用于0-1背包問題。，螞蟻算法和其他仿生算法也很好地應(yīng)用于組合優(yōu)化問題。近年來，出現(xiàn)了許多結(jié)合多種算法的混合算法來解決背包問題，并取得了很好的效果。解決背包問題的傳統(tǒng)方法可以摘要為精確算法和近似算法，其中精確算法包括動態(tài)規(guī)劃法、回溯法和分支定界法，近似算法包括遺傳算法、貪心算法和螞蟻算法。殖民地算法，由于精確算法的時間復(fù)雜度，近年來，使用近似算法解決背包問題成為焦點。前人對背包問題做了一些深入的研究，得到了一些經(jīng)典的方法。雖然有些方法在解決背包問題上能取得很好的效果，但也存在很多不足。首先，許多算法是計算密集型的并且需要很長時間來迭代。例如窮舉法和動態(tài)規(guī)劃法簡單易實現(xiàn)，但效率很低，魯棒性不強。它們只能用于解決小規(guī)模問題，但有時實際問題中面臨的問題的搜索空間可能非常大。，求解效率會逐漸降低。其次，貪心算法速度快，爬升能力強，但適用于尋找局部最優(yōu)解，在沒有得到全局最優(yōu)解的情況下可能陷入局部極值。第三，蟻群算法可以得到一個近似最優(yōu)解，但是數(shù)據(jù)規(guī)模大時收斂太慢；第四，知識進化算法、DNA計算等新興方法也能有效解決背包問題，但這些理論并不完善。背包問題屬于組合優(yōu)化問題。獲得嚴格意義上的最優(yōu)解是非常困難的。因此，研究高速近似算法是一個重要的發(fā)展方向。與上述算法相比，遺傳算法具有一定的優(yōu)勢。首先，遺傳算法對要解決的優(yōu)化問題沒有太多的數(shù)學(xué)要求。由于其進化特征，在搜索過程中不需要問題的性質(zhì)。對于任何形式的目標函數(shù)和約束，無論是線性的還是非線性的，離散的或連續(xù)的都可以處理。其次，進化算子的遍歷性質(zhì)使遺傳算法能夠非常有效地執(zhí)行概率上有意義的全局搜索。最后，遺傳算法可以為各種特殊問題提供極大的靈活性來混合和構(gòu)造與領(lǐng)域無關(guān)的啟發(fā)式，從而保證算法的有效性。本文將進一步研究遺傳算法并將其應(yīng)用于背包問題，實驗證明遺傳算法對于解決背包問題更為有效。遺傳算法簡介遺傳算法（GeneticAlgorithms）是計算數(shù)學(xué)中求解優(yōu)化問題的一種搜索算法，是一種進化算法。進化算法最初是從進化生物學(xué)中的一些現(xiàn)象發(fā)展而來的，包括遺傳、突變、自然選擇和雜交。遺傳算法是模仿自然界生物進化機制發(fā)展起來的一種隨機全局搜索和優(yōu)化方法。它借鑒了達爾文的進化論和孟德爾的遺傳學(xué)理論。其本質(zhì)是一種高效的、并行的、全局的搜索方法，在搜索過程中可以自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程以獲得最優(yōu)方法。適者生存的原則用于遺傳操作，以在潛在解決方案的群體中連續(xù)生成近似最優(yōu)解決方案。在遺傳算法的每一代中，根據(jù)問題域中個體的適應(yīng)度值和借鑒自然遺傳學(xué)的重構(gòu)方法，生成一個新的近似解。這個過程導(dǎo)致了種群中個體的進化，產(chǎn)生了比原來更適應(yīng)環(huán)境的新個體，就像自然界中的重塑一樣。遺傳算法及發(fā)展趨勢查克斯·達爾文的自然選擇理論認為，生物進化的驅(qū)動力和機制在于自然選擇，生物在其中為生存而斗爭，在其中具有有利變異的個體很可能存活下來，并且有更多的機會將這種變異傳給后代，而具有不利變異的個體將被淘汰，并且產(chǎn)生后代的機會更少。所有在生存斗爭中獲勝的個體對環(huán)境的適應(yīng)能力更強，所以生物進化的過程就是這個“物競天擇，適者生存”的過程，是一個緩慢的、持續(xù)的、長期的過程。過程。遺傳和變異是決定生物進化和促進生物進化發(fā)展的因素?；谏镞M化理論，自1960年代以來，科學(xué)家們嘗試用計算方法來模擬生物遺傳和選擇進化的過程。1975年，美國霍蘭德教授發(fā)表了他的開創(chuàng)性著作《自然與人工系統(tǒng)中的適應(yīng)》[4]，開創(chuàng)了遺傳算法的概念，系統(tǒng)地闡述了遺傳算法的理論，奠定了遺傳算法的數(shù)學(xué)基礎(chǔ)。理論及其在優(yōu)化和機器學(xué)習(xí)領(lǐng)域的應(yīng)用。他將遺傳算法定義為一種自適應(yīng)算法，可廣泛應(yīng)用于系統(tǒng)優(yōu)化研究。1975年，DeJone做了很多實驗，建立了著名的DeJone測試函數(shù)[5]。1989年，戈德堡博士出版了專著《搜索、優(yōu)化和機器學(xué)習(xí)中的遺傳算法》[6]，這是第一本遺傳算法的教科書，全面論述了遺傳算法的原理和應(yīng)用，并結(jié)合實例.提供大量源程序，供技術(shù)專家借鑒，進行實際應(yīng)用。此后，世界掀起了遺傳算法研究與應(yīng)用的高潮。從1985年開始，遺傳算法及其應(yīng)用國際會議每兩年召開一次，很多人工智能領(lǐng)域的專家開始發(fā)表遺傳算法論文。1991年，Davis在他的《遺傳算法手冊》[7]中引入了大量的例子。遺傳算法因其能有效解決NP型組合優(yōu)化問題和多目標函數(shù)優(yōu)化問題而受到許多學(xué)科的高度重視。在中國，該大學(xué)建立了軟件工程國家重點實驗室。以進化計算為重要研究方向，研究成果目前處于國內(nèi)領(lǐng)先水平；中科大郭亮出版了遺傳算法專著；此外，科技大學(xué)的克明教授還模擬了人類思維的進化過程。進化算法也成為進化計算領(lǐng)域的一個重要分支。遺傳算法在應(yīng)用中取得的豐碩成果，使人們對其發(fā)展前景充滿信心。認識到這一點，遺傳算法的創(chuàng)始人之一GoldsbergD開玩笑說：“不再需要水晶球了?！笨梢灶A(yù)見，未來幾年，更多元化的應(yīng)用領(lǐng)域的發(fā)展，包括各種遺傳算法編程環(huán)境的開發(fā)，仍將是遺傳算法發(fā)展的主流。事實上，這也是本世紀高科技高速發(fā)展的特點，具有規(guī)律性，即應(yīng)用型。同時，這并不意味著理論研究會被忽視，這方面還有很多工作要做。例如：控制參數(shù)的選擇；交換和變異這兩個最重要的算子的確切作用；并行遺傳算法和分布式遺傳算法的研究；模仿其他類型的生物機制，如免疫、病毒、寄生等，豐富遺傳算法等內(nèi)容。自然，無論從理論還是應(yīng)用的角度來看，最迫切的研究應(yīng)該是算法收斂問題，尤其是早熟收斂的預(yù)防。這對遺傳算法的實際應(yīng)用具有重要意義。目前，一個值得特別關(guān)注的趨勢是一些面向?qū)ο蟮闹悄芗夹g(shù)，主要是模糊邏輯[8]（FuzzyLogic，F(xiàn)L）、神經(jīng)網(wǎng)絡(luò)[9]（NeuralNetwork，NN）和遺傳算法的集成應(yīng)用。眾所周知，F(xiàn)L具有很強的知識表達能力，而NN的強項在于自學(xué)習(xí)。它們與遺傳算法相結(jié)合，形成一種新的集成技術(shù)，即所謂的混合智能系統(tǒng)。這一思想是在1990年代初逐漸形成的，首先由模糊集理論的創(chuàng)始人ZadehLA在1993年在首爾舉行的國際模糊系統(tǒng)協(xié)會（IFSA）第五屆世界大會上明確提出，然后在許多相關(guān)的在國際學(xué)術(shù)會議上都得到了充分體現(xiàn)。需要指出的是，中國學(xué)者對這一趨勢有較早的認識。例如，清華大學(xué)燕達院士領(lǐng)導(dǎo)的課題組幾乎同時在這一重要方向開展了研究。所謂的混合智能系統(tǒng)的應(yīng)用，將涵蓋從消費產(chǎn)品生產(chǎn)到核反應(yīng)堆設(shè)計再到證券管理的方方面面，“可能在未來幾年內(nèi)無處不在”。就遺傳算法本身的研究而言，應(yīng)該說中國起步比較晚，只是近幾年才看到一些介紹性文章，不超過兩三本專著和初步研究報告，與國外工作相比，一個顯著的區(qū)別是，國內(nèi)大部分工作只停留在論文層面，幾乎沒有具體的實際應(yīng)用，與研究成果商品化的差距更大。理論研究與實際應(yīng)用不夠緊密，阻礙了我國高新技術(shù)的快速發(fā)展，幾乎成為一種慢性病。因此，在我國遺傳算法的發(fā)展中，應(yīng)特別重視其應(yīng)用和推廣。學(xué)術(shù)界應(yīng)主動與企業(yè)界共同開發(fā)遺傳算法的應(yīng)用，并應(yīng)注意引入或開發(fā)類似于SPlicer的編程環(huán)境，使遺傳算法的應(yīng)用更加方便快捷。國家設(shè)立的工程研究中心應(yīng)在這方面發(fā)揮更大的作用。工程數(shù)學(xué)教育也要適應(yīng)高新技術(shù)發(fā)展的需要。例如，工程運籌學(xué)與優(yōu)化方法等課程應(yīng)適當增加遺傳算法的內(nèi)容，以開闊學(xué)生的視野，也有助于加快傳統(tǒng)課程內(nèi)容的更新。1.2.2遺傳算法的特點該算法從一組問題的解決方案字符串開始搜索，而不是從單個解決方案開始。這是遺傳算法與傳統(tǒng)算法的最大區(qū)別。傳統(tǒng)的優(yōu)化算法從單個初始值迭代尋找最優(yōu)解，容易陷入局部最優(yōu)解。遺傳算法從字符串集合開始搜索，覆蓋范圍大，有利于全局選擇。求解所用的具體問題的信息很少，很容易形成通用的算法程序。由于遺傳算法應(yīng)該使用這些信息進行搜索，因此它不需要與問題直接相關(guān)的信息，例如問題的導(dǎo)數(shù)。傳統(tǒng)算法只需要自適應(yīng)值和字符串編碼等一般信息，因此它們幾乎可以處理任何問題。算法具有極強的容錯性。遺傳算法的初始字符串集本身有很多信息，離最優(yōu)解還很遠。通過選擇、交叉和變異操作，可以快速消除與最優(yōu)解相差很大的字符串。這是一個密集的過濾過程，也是一個并行的過濾機制。因此，遺傳算法具有較高的容錯性。算法中的選擇、交叉和變異是隨機操作，而不是確定性的精確規(guī)則。這說明遺傳算法采用隨機方法搜索最優(yōu)解，選擇反映了對最優(yōu)解的逼近，交叉代表最優(yōu)解的產(chǎn)生，變異代表全局最優(yōu)解的覆蓋范圍。1.2.3遺傳算法的分類(1)混合遺傳算法單純的簡單遺傳算法在很多情況下效果不佳，容易產(chǎn)生早熟現(xiàn)象，局部優(yōu)化能力差，因此提出了多種混合算法。比如Ackley推薦的遺傳爬山法；Mathefoud提出的遺傳模擬退火算法；在遺傳算法中加入局部改進操作等。混合遺傳算法的基本思想是在每個新生成的后代進入下一代種群之前，對其應(yīng)用局部優(yōu)化技術(shù)（如爬山、模擬退火等），使其移動到最近的局部最優(yōu)值。在混合遺傳算法中，啟發(fā)式方法用于局部優(yōu)化，遺傳算法用于全局最優(yōu)的探索。由于遺傳算法與傳統(tǒng)優(yōu)化方法的互補性，混合遺傳算法通常優(yōu)于單一算法。(2)并行遺傳算法遺傳算法在解決一些實際問題時，由于一般群體規(guī)模較大，需要對大量個體進行大量的遺傳和進化運算，尤其是對大量個體的適應(yīng)度計算或評價，使得算法的進化運算過程進展緩慢，難以滿足計算速度的要求，因此遺傳算法的并行計算問題一直受到關(guān)注。并行遺傳算法主要從以下四個方面進行改進和發(fā)展。一個。個體適應(yīng)度評價的平行性。在遺傳算法的運行過程中，個體適應(yīng)度的評估或計算需要很長時間。通過對個體適應(yīng)度并行計算方法的研究，可以找到并行評估個體適應(yīng)度的算法。灣。整個群體中每個個體的適應(yīng)度評估與平行組中每個個體的適應(yīng)度沒有相互依賴關(guān)系，使得每個個體的適應(yīng)度計算過程可以獨立并行地進行。也就是說，不同個體的適應(yīng)度計算可以在不同的處理器上同時進行。C。組生成過程的并行性。在從父組生成下一代的過程中，選擇操作只與個體的適應(yīng)度有關(guān)，而交叉和變異操作只與參與操作的個體的編碼有關(guān)。這樣，在種群生成過程中的選擇、交叉和變異操作可以相互獨立地并行執(zhí)行。d?；诮M分組的并行性?？梢砸阅撤N方式對組進行分組。分組后，每組個體的遺傳進化過程可以在不同的處理器上獨立進行。在適當?shù)臅r候，處理器相互交換信息。1.2.4遺傳算法的應(yīng)用目前，遺傳算法廣泛應(yīng)用于許多科學(xué)和工程領(lǐng)域。其典型應(yīng)用領(lǐng)域如下。一個。組合優(yōu)化。隨著組合優(yōu)化問題規(guī)模的增大，其搜索空間也急劇增加，在計算機上不可能通過窮舉法找到其最優(yōu)解，而遺傳算法可以為這類問題尋求滿意的解。目前，遺傳算法已成功應(yīng)用于旅行商問題（TSP）[10]、背包問題[11]、網(wǎng)絡(luò)路由、貨物倉庫裝載[12]等方面的NP難度組合優(yōu)化。灣。功能優(yōu)化。函數(shù)優(yōu)化是遺傳算法的一個經(jīng)典應(yīng)用領(lǐng)域。學(xué)者們構(gòu)建了各種復(fù)雜的測試函數(shù)，包括連續(xù)函數(shù)和離散函數(shù)、高維和低維、凹凸、多峰和單峰。遺傳算法比其他優(yōu)化方法更方便。獲得更好的結(jié)果。函數(shù)優(yōu)化也是評估遺傳算法的常用工具。C。自動控制，遺傳算法在自動控制領(lǐng)域的應(yīng)用日益增多，并取得了良好的效果。目前，GA在系統(tǒng)辨識、模糊控制器設(shè)計、航空系統(tǒng)優(yōu)化等方面取得了一定的成果。d。圖像處理。遺傳算法已成功應(yīng)用于圖像處理、圖像恢復(fù)和圖像邊緣特征提取。e.機器學(xué)習(xí)。目前，基于遺傳算法的機器學(xué)習(xí)已經(jīng)在很多領(lǐng)域得到應(yīng)用。例如：利用GA的機器學(xué)習(xí)來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的權(quán)重等；利用遺傳算法學(xué)習(xí)模糊控制的從屬度函數(shù)以提高模糊控制系統(tǒng)的性能。F。數(shù)據(jù)挖掘。數(shù)據(jù)挖掘是從大型數(shù)據(jù)庫中提取有趣的、隱含的和潛在有用的知識。數(shù)據(jù)挖掘問題可以看成一個搜索問題，數(shù)據(jù)庫看成一個搜索空間，挖掘算法看成一種搜索策略，這樣就可以用遺傳算法來搜索數(shù)據(jù)庫中的數(shù)據(jù)，而隨機生成的規(guī)則集可以進化。，直到數(shù)據(jù)庫可以被這條規(guī)則覆蓋，然后挖掘出大數(shù)據(jù)庫中的隱含規(guī)則。1.3本文的主要工作介紹了0-1背包問題的概念，討論了解決該問題的各種傳統(tǒng)算法，給出了0-1背包問題的數(shù)學(xué)描述。進行遺傳算法的理論研究。介紹了進化算法的基本理論，簡要說明了幾種典型的進化算法，詳細討論了遺傳算法的基本理論、應(yīng)用和研究趨勢。應(yīng)用遺傳算法解決0-1背包問題，探討遺傳算法通過設(shè)置不同參數(shù)解決背包問題的可行性，并在Matlab仿真平臺上實現(xiàn)算法。GUI界面是在matlab環(huán)境下設(shè)計的。運行界面中遺傳算法的主要參數(shù)可以手動輸入修改，通過GUI界面可以直接觀察仿真曲線的變化。第二章基于遺傳算法的0-1背包問題研究2.1遺傳算法的思想遺傳算法是通過模擬自然界中生物遺產(chǎn)的進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它最早由密歇根大學(xué)的Holland教授提出，起源于1960年代對自然和人工適應(yīng)系統(tǒng)的研究[13]。1970年代，DcJong基于遺傳算法的思想在計算機上進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗[14]。基于一系列的研究工作。1980年代，Goldberg總結(jié)并形成了遺傳算法的基本框架。生物進化以群體為主，因此遺傳算法的運算對象是由M個個體組成的集合，即成為一個群體。類似于生物世代相傳的自然進化過程，遺傳算法也是一個迭代過程。第t代組記為P(t)。經(jīng)過一代遺傳和進化，得到第t+1代群，由多個個體組成。形成的集合表示為P(t+1)。這個群體經(jīng)過不斷的遺傳和進化操作，每次都按照優(yōu)勝劣汰的規(guī)則，將更多的適應(yīng)度更高的個體遺傳給下一代，最終在群體中得到一個優(yōu)秀的個體X，對應(yīng)于X的表型將等于或接近問題X*的最優(yōu)解。遺傳算法有四個組成部分：染色體編碼方法：用一個固定長度的二進制符號串來表示種群中的個體，其等位基因由二進制符號集{0,l}組成。個體適應(yīng)度評估：基本遺傳算法根據(jù)與個體適應(yīng)度成正比的概率，確定當前群體中每個個體被遺傳到下一代群體中的概率。遺傳算子：使用比例選擇算子、單點交叉算子、基本位變異算子或均勻變異算子。操作參數(shù)：種群大小M；遺傳運算的終止進化代數(shù)T一般為100-500；交叉概率Pc一般為0.4-0.99；突變概率Pm一般為0.001-0.1。對于需要優(yōu)化計算的實際應(yīng)用問題，可以按照以下步驟構(gòu)建求解該問題的遺傳算法：第一步：確定決策變量及其各種約束條件，即確定個體表型X和問題的解空間；第二步：建立優(yōu)化模型，即確定目標函數(shù)的類型（是求目標函數(shù)的最大值。還是求目標函數(shù)的最小值）及其數(shù)學(xué)描述形式或量化方法;第三步：確定代表可行解的染色體編碼方式，即確定個體的基因型X和遺傳算法的搜索空間；第四步：確定解碼方法，即確定個體基因型x與個體表型X的對應(yīng)關(guān)系或轉(zhuǎn)換方法；第五步：確定個體適應(yīng)度的量化評價方法，即確定目標函數(shù)值f(x)對個體適應(yīng)度F(X)的轉(zhuǎn)換規(guī)則；Step6：設(shè)計遺傳算子，即確定遺傳算子的具體操作方法如選擇操作、交叉操作、變異操作等；第七步：確定遺傳算法的相關(guān)運行參數(shù)，即確定遺傳算法的M、Pc、Pm等參數(shù)。2.1.1遺傳算法的數(shù)學(xué)基礎(chǔ)遺傳算法在機制上具有搜索過程和優(yōu)化機制的特性?？梢酝ㄟ^分析模式定理和構(gòu)建模塊假設(shè)來討論數(shù)學(xué)的性質(zhì)。馬爾可夫鏈也是分析遺傳算法的有效工具。遺傳算法的執(zhí)行過程中包含大量的隨機操作，因此有必要對其數(shù)學(xué)機制進行分析。模態(tài)定理[15'16'17]是JohnHolland在1971年提出的，是GA的基本定理。它將遺傳算法的運行過程理解為模式運行過程，從模式運行的角度解釋了遺傳算法的性能特點。定義2.1模式是描述一組字符串的模板，這些字符串在某些位置具有相似性。所以該模式也可以解釋為相同的配置。定義2.2模式順序（schemaorder）在模式H中確定的位置的數(shù)量稱為模式順序，記為o(H)。例如：o(011*1*)=4。模階用于反映不同模態(tài)確定性的差異。眾數(shù)階數(shù)越高，眾數(shù)的確定性越高，匹配的樣本越少。定義2.3定義距離（定義長度）圖案H中第一個確定位置與最后一個確定位置之間的距離稱為圖案定義距離，記為δ(H)。例如：δ(011*1**)=4。在遺傳操作中，即使是同一階的模式也會有不同的屬性，模式的定義距離反映了屬性的差異。模式定理在遺傳算子選擇、交叉和變異的作用下，低階、短距離、平均適應(yīng)度高于種群平均適應(yīng)度的模式在后代中呈指數(shù)增長。模式定理可以用數(shù)學(xué)形式表示為：在公式中，m(H,t+1)標識了t+1代種群中存在的模式H的數(shù)量f(H)表示第t代人群中包含模式H的個體的平均適應(yīng)度l是個體的長度Pc是交叉的概率Pm是突變的概率δ(H)表示模式H的定義距離；o(H)表示模式H的階數(shù)。模式定理是遺傳算法的基本理論，它保證了最優(yōu)模式（遺傳算法的最優(yōu)解）的數(shù)量呈指數(shù)增長，為解釋遺傳算法的機理提供了數(shù)學(xué)工具。定義2.4模式定理中的積木（buildingblock）是指將具有低階、短定義距離且平均適應(yīng)度高于種群平均適應(yīng)度的模式定義為積木。構(gòu)建塊假設(shè)[18]低階、短定義距離、高平均適應(yīng)度基因塊通過選擇、交叉、變異等遺傳算子的功能，可以將它們拼接在一起，形成一個高階、長定義距離、高平均的適應(yīng)度模型，最終逼近全局最優(yōu)解。滿足這個假設(shè)的條件比較簡單，包括兩個方面：具有相似表型的個體具有相似的基因型；遺傳因素之間的相關(guān)性較低。目前大量實踐支持積木假設(shè)，該假設(shè)在許多領(lǐng)域取得了成功，例如光滑多模態(tài)問題、帶干擾的多模態(tài)問題和組合優(yōu)化問題。模式定理保證最優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而滿足尋找最優(yōu)解的必要條件，即遺傳算法有可能找到全局最優(yōu)解；積木假設(shè)指出遺傳算法具有尋找全局最優(yōu)解的能力。解的能力，即積木在遺傳算子的作用下能夠生成低階、短程、高平均的適應(yīng)度模式，最終生成全局最優(yōu)解。雖然模式定理在一定程度上解決了基本遺傳算法的有效性，但它仍然存在以下缺點：眾數(shù)定理只適用于二進制編碼，其他編碼方案沒有相應(yīng)的結(jié)論；模式定理只給出了下一代包含模式H的個體數(shù)量的下限。我們不能由此推斷算法的收斂性；模態(tài)定理沒有解決算法設(shè)計中控制參數(shù)選擇的問題。2.1.2遺傳算法的基本原理典型的遺傳算法CGA[19]（CanonicalGeneticAlgorithm）通常用于解決以下靜態(tài)優(yōu)化問題：考慮一組長度為L的二進制碼bi，i=1,2,...,n；有bi{0,l}L給定目標函數(shù)f，如果f(bi)>0且f(bi)≠f(bi+1)，求表達式max{f(bi)|{0,1}L}的bibi;.顯然，遺傳算法是一種優(yōu)化方法。它通過進化和遺傳機制從給定的原始解組不斷演化并產(chǎn)生新的解，最終收斂到特定的字符串bi，即得到最優(yōu)解。最優(yōu)解。的n個二進制串bi(i=1,2,...,n)構(gòu)成遺傳算法的初始解群，也稱為初始群。在每個字符串中，每個位都是單個染色體的基因。在進化術(shù)語中，對組執(zhí)行三種類型的操作：選擇：這是從群體中選擇更適合環(huán)境的個體。這些選定的個體用于繁殖下一代。因此，這種操作有時被稱為再現(xiàn)（Reproduction）。在選擇個體進行下一代繁殖時，個體的繁殖量是根據(jù)個體對環(huán)境的適應(yīng)度來確定的，因此有時也稱為差異繁殖。交叉：這是在選擇用于下一代繁殖的個體之間交換兩個不同個體的相同位置的基因，從而產(chǎn)生新個體。突變：這是對選定個體中的某些基因進行異向轉(zhuǎn)化。在字符串bi中，如果一個基因為1，則發(fā)生突變時變?yōu)?；反之亦然。遺傳算法的原理可以簡單地給出如下：選擇初值，確定合適的值，完成選擇；進行交叉和變異；重復(fù)直到得到最優(yōu)解。一定的門檻；或者個體適應(yīng)度的變化率為零。2.1.3遺傳算法的實現(xiàn)過程遺傳算法是一種自適應(yīng)全局概率搜索算法，它模擬了達爾文的生物自然選擇理論和自然界中生物進化的過程。在解決具體問題時，首先粗略確定該問題的一組潛在解決方案，即算法的初始種群。種群是由計算機生成的一定數(shù)量的個體（一般是隨機生成的）組成的，個體是潛在解的計算機代碼，那么我們需要的最終解就是從這些最初生成的個體進化而來的。每個人都有自己的特點。我們根據(jù)這些個體的不同特征來確定存活到下一代的概率。根據(jù)優(yōu)勝劣汰的規(guī)律，我們用父母來生產(chǎn)后代，以此類推。當然，在具體的進化過程中，為了保持種群的多樣性，防止早熟收斂，需要讓個體以一定的小概率發(fā)生變異。這樣，最終滿足收斂條件后的種群最優(yōu)個體就是問題的近似最優(yōu)解。遺傳算法的實現(xiàn)過程主要包括編碼、生成種群、計算適應(yīng)度、復(fù)制、交換、變異等操作。一般來說，遺傳算法求解組合優(yōu)化問題的具體步驟可以描述如下：(1)初始化：選擇一個組，即選擇一組字符串或個體bi,i=l,2,...n.這個初始種群也是該問題的一組假設(shè)解決方案。一般取n=301-60。一組字符串或個體bi,i=1,2,...n通常以隨機方式生成。通過演化這些初始假設(shè)解決方案將找到問題的最佳解決方案。（2）選擇：按照優(yōu)勝劣汰的原則選擇下一代個體。在選擇中，適應(yīng)度是選擇的原則。適應(yīng)度標準反映了適者生存、適者淘汰的自然規(guī)律。給定目標函數(shù)f，f(bi)稱為個體bi的適應(yīng)度。取選定的bi作為下一代個體的數(shù)量。體質(zhì)較高的個體有更多的后代。適應(yīng)度較小的個體將繁殖更少的世代；他們甚至可能被淘汰。這樣就產(chǎn)生了對環(huán)境適應(yīng)性更強的后代。從解決問題的角度來看，就是選擇一個更接近最優(yōu)解的中間解。(3)交叉：對于選擇繁殖下一代的個體，根據(jù)交叉概率pc，隨機選擇兩個個體的相同位置。在所選位置執(zhí)行交換。這個過程反映了隨機的信息交換；目的是產(chǎn)生新的基因組合，即新個體。穿越時，可進行單點穿越或多點穿越。比如有個人：S1=100101； S2=010111選擇它們的左3位進行交叉操作，則有：S1=010101；S2=100111總則來說，交叉概率為0.25-0.75。(4)突變：根據(jù)生物遺傳中的基因突變原理，對某些個體的某些位元進行突變，其突變概率為Pm。變異時，將待變異字符串的對應(yīng)位取反，即1變?yōu)?，0變?yōu)?。變異概率Pm與生物變異極小的情況是一致的，所以Pm的值為小，一般為0.01-0.2。例如，有一個個體S=101011。第1位和第4位基因發(fā)生突變，S1=001111。單獨的突變對解決方案沒有好處。但是，它保證算法過程不會產(chǎn)生無法進化的單一種群。因為當所有個體都相同時，交叉不能產(chǎn)生新個體，新個體只能通過變異產(chǎn)生。也就是說，變異增加了全局優(yōu)化的特質(zhì)。(5)收斂到全局最優(yōu)當最優(yōu)個體的適應(yīng)度達到給定閾值，或者最優(yōu)個體的適應(yīng)度和群體的適應(yīng)度不再上升時，算法的迭代過程收斂，算法結(jié)束。否則，用選擇、交叉、變異得到的新一代種群替換上一代種群，返回第二步，即選擇操作繼續(xù)循環(huán)執(zhí)行。遺傳算法流程圖如圖2-1所示：隨機選擇種群數(shù)隨機選擇種群數(shù)計算適應(yīng)度變異交叉停止?jié)M足條件？是否圖2-1遺傳算法流程圖Goldberg使用一個簡單的遺傳算法來描述和舉例說明遺傳算法的基本組成部分。T代種群由變量P(t)表示，初始種群P(o)是隨機設(shè)計的。簡單遺傳算法的偽代碼描述如下：程序GA 開始t=0；初始化P(t)；評估P(t)；雖然沒有完成開始t=t+l；從P(t-1)中選擇P(t)；在P(t)中復(fù)制對；評估P(t)；結(jié)尾結(jié)尾2.2用遺傳算法解決0-1背包問題遺傳算法在解決背包問題上取得了一定的效果。使用簡單遺傳算法求解背包問題時，如果問題規(guī)模不大，可以得到最優(yōu)解或近似最優(yōu)解。使用簡單遺傳算法求解0-1背包問題的基本步驟如下：(1)種群的初始化：確定種群大小M、交叉概率Pc、變異概率pm、染色體長度N和最大進化代數(shù)maxgen。隨機初始化染色體，給出物品體積、物品價值和背包容量C.(2)生成遺傳密碼：使用二進制n維向量解X作為解空間參數(shù)的遺傳密碼，字符串T的長度等于n，xi=1表示將對象加載到背包，xi=0表示該物體沒有裝入背包。例如，x={0,1,0,1,0,0,1)表示第2、4、7項被選中進入背包。而其他人沒有被選中。也就是說，現(xiàn)在這個背包里只有2、4、7三個物件。這個遺傳密碼也需要隨機產(chǎn)生，隨機產(chǎn)生數(shù)字0或1，組成染色體串，即遺傳密碼。每次生成染色體時，如果不滿足約束條件，就會對其進行測試并拒絕。再生一條新的染色體；如果生成的染色體滿足條件，則接受它為種群的成員，經(jīng)過有限采樣，得到M條可行染色體。具體來說，最終會產(chǎn)生M條染色體，每條染色體有N個基因，即每條染色體的長度為N。因此，初始化的種群應(yīng)該是一個M*N的二維矩陣。如果M=5，N=IO，那么初始化的種群可以看成一個5行10列的矩陣。例如，初始化的種群可以如下：01100010111111010001100110100000011001110010110010(3)適應(yīng)度函數(shù)構(gòu)建：適應(yīng)度函數(shù)的建立是解決背包問題的關(guān)鍵。首先，背包問題的目標函數(shù)和約束條件可以表示為：目標函數(shù)：，約束條件：。由于我們之前定義了當物品i被選擇到背包中時，設(shè)置變量Xi=1，否則Xi=0?？紤]選擇n個物品，背包中物品的總體積，物品的總價值，如何確定變量Xi(i=l,2,...,n)的值（即，確定物品的組合）使背包中物品的總價值達到最大值。該問題的解的組合總數(shù)為2，其數(shù)學(xué)模型表示為：當，使大時，Xi=1或0(i=1,2,...,n)。通過對這個問題的具體分析，它的適應(yīng)度函數(shù)應(yīng)該定義為每次裝入背包的物品之和，現(xiàn)在它的適應(yīng)度函數(shù)構(gòu)造如下：,Xi=1or0(i=1,2,...，n）。把所有的東西都放在背包里，那么它可能會比背包的容量大。如果較大，則按照價值密度的順序，取出價值密度低的背包，直到滿足設(shè)定的背包容量。適應(yīng)度計算過程如下：temp_sum=vol*samp_arr'；速率=val./vol；%計算每個物體單位體積的值，即值密度對于i=1:POP_NUMj=0；如果temp_sum(i)>MAX_CAP[temp,index]=sort(rate,'ascend');而temp_sum(i)>MAX_CAPj=j+1；如果samp_arr(i,index(j))==1samp_arr(i,index(j))=0;temp_sum(i)=temp_sum(i)-vol(index(j));結(jié)尾結(jié)尾結(jié)尾結(jié)尾(4)選擇操作：根據(jù)選擇概率選擇染色體，將上述個體作為第一代。這里采用與適應(yīng)度成正比的輪子隨機選擇方法。每個個體的適應(yīng)度值為fi，則i被選中的概率psi為：;;對于初始化的種群，首先計算每條染色體的適應(yīng)度值，然后計算其被選擇的概率，比較它們，淘汰選擇概率最小的染色體，選擇概率最高的染色體進行復(fù)制，這個復(fù)制的染色體為用于替換消除的染色體位置。這樣就完成了種群的選擇操作。相應(yīng)的程序如下：%選擇動作（輪盤賭）fit_sum=sum(fit_arr);rtable=fit_arr./fit_sum;%輪盤賭，轉(zhuǎn)盤%生成輪盤賭，類似于概率分布Fori=2:POP_NUMrtable(i)=rtable(i-1)+rtable(i);結(jié)尾對于i=1:POP_NUMp=蘭德（1）；指數(shù)=1；而p>rtable(索引)指數(shù)=指數(shù)+1；結(jié)尾獲勝者指數(shù)（i）=指數(shù)；結(jié)尾上述過程是將所有個體的適應(yīng)度值相加，然后計算每個個體的適應(yīng)度值與總數(shù)的比值。比值越大，個體對應(yīng)的適應(yīng)度范圍越大。(5)交叉操作：判斷染色體是否為活染色體。如果是活染色體，則交叉染色體。一般采用單點交叉法，交叉概率為Pc。具體操作是在單個字符串中隨機設(shè)置一個crossover。進行交叉時，交換點前后兩個個體的部分結(jié)構(gòu)，生成兩個新個體。這里我們嘗試使用“和/或”交叉方法，使后代繼承父母的同型基因。對于親本的異型基因，“和/或”交叉法采用兩種不同的“支配”方式，“AND”運算是0支配1的方式，“OR”運算是1支配的方式。支配0。使用“和/或”交叉策略可以使優(yōu)化過程更快地到達全局最優(yōu)解，得到全局最優(yōu)解。最優(yōu)解僅是“單點交叉”策略時間的1/9到1/3。%交叉cross_index=1:POP_NUM;%參與交叉的樣本的索引對于i=1:POP_NUMtemp=unidrnd(POP_NUM-i+1);%取一個1到POP_NUM-i+1之間的隨機數(shù)temp_pos=i+temp-1；temp_val=cross_index（temp_pos）；cross_index(temp_pos)=cross_index(i);cross_index(i)=temp_val;結(jié)尾在個體中選擇兩個位置，并交換兩個位置的對應(yīng)值。交叉操作首先對可能交叉的樣本進行索引，并隨機獲取一個數(shù)字。如果這個數(shù)小于交叉概率，則進行相鄰交叉，否則不進行。叉。fori=1:2:POP_NUM%兩個相鄰的交叉%隨機取一個數(shù)，如果小于交叉概率，則交叉如果rand(1)<P_CROSScross_pos=unidrnd(POP_NUM-1);%交叉點位置，[1,POP_NUM-1]temp_cross=samp_arr(cross_index(i),cross_pos:end);samp_arr(cross_index(i),cross_pos:end)=...samp_arr(cross_index(i+1),cross_pos:end);samp_arr(cross_index(i+1),cross_pos:end)=temp_cross;結(jié)尾結(jié)尾(6)突變操作：染色體突變采用位點突變的方法。基因座突變相對簡單。對于這個問題，只需將染色體突變位1改為0，0改為1，其他位不變。前突變?nèi)旧w為：1110001101突變后的染色體為：0001110010變異概率為Pm，變異的目的是使變異后的適應(yīng)度大于或等于其原始適應(yīng)度。首先選擇一個變異位進行變異，然后計算它的適應(yīng)度，看是否大于等于原來的適應(yīng)度，如果不是，重新選擇變異位進行變異。在群體依次選擇、雜交和變異后，對獲得的新個體進行測試。當某一代得到的結(jié)果滿足要求或當前代數(shù)等于結(jié)束代數(shù)時，算法結(jié)束，得到結(jié)果。否則，重復(fù)選擇、交叉和變異操作，直到獲得滿意的結(jié)果。直到結(jié)果。%變異操作，直接對整個樣本集進行操作muta_arr=(rand(POP_NUM,LEN)<P_MUTA);索引=查找（muta_arr）；samp_arr（索引）=1-samp_arr（索引）；%找到上一代中最好的樣本[max_val,max_index]=max(fit_arr);temp=samp_arr(max_index,:);索引=查找（溫度）；%index記錄獲得的對象編號2.3數(shù)值試驗及結(jié)果分析程序思路分析如下：使用二進制0-I編碼。裝入背包的物品用1表示，未裝入的用0表示，一種裝載方式用一條染色體表示，產(chǎn)生的染色體總數(shù)等于種群大小。計算每條染色體的適應(yīng)度值，剔除適應(yīng)度值最低的一條，復(fù)制適應(yīng)度值最高的一條，用最高的替換最低的，這樣就完成了選擇；然后隨機產(chǎn)生交叉點，對相互交叉的染色體進行交叉，計算交叉后檢查染色體是否滿足要求，即裝入背包的物品總體積小于背包的容量。如果不符合要求，則交叉失敗，重新交叉。如果達到最大交叉次數(shù)，則取消交叉；選擇變異的染色體，隨機產(chǎn)生變異點進行變異，計算變異后的染色體是否滿足要求。如果不滿足要求，則變異失敗，重新變異，直到達到最大變異數(shù)，變異不成功。這樣就完成了遺傳算法的基本步驟，重復(fù)上述步驟，直到完成設(shè)計的進化次數(shù)。2.3.1示例1A.實驗裝置和模擬結(jié)果v值=[220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72、70、69、66、65、63、60、58、56、50、30、20、15、10、8、5、3、1]；w八=[80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1];C=1000其中，value代表背包中物品的價值，weight代表對應(yīng)物品的重量，代表背包的最大容量。此示例的最優(yōu)解已知為3103。將總體大小設(shè)置為50，最大迭代次數(shù)為500，交叉概率為0.8，變異概率為0.07。程序循環(huán)運行20次，結(jié)果如表2-1所示，仿真圖如圖2-2所示。表2-1實施例1的求解結(jié)果循環(huán)迭代次數(shù)最優(yōu)值最差值平均值達到最優(yōu)解的概率20500310314292418.1545%從表2-1可以看出，在程序20次運行中，最優(yōu)解3103被命中9次，平均值為2418.15，最優(yōu)值與最差值之差為1674，說明遺傳解決背包問題的算法不容易陷入局部最優(yōu)。圖2-2示例1運行20次結(jié)果仿真圖通過圖2-2可以清楚地看到算法運行20次后產(chǎn)生的最優(yōu)值、最差值和平均值的仿真曲線。從圖中可以看出，最優(yōu)值的模擬曲線和模擬曲線的平均值波動不大，說明遺傳算法具有較好的尋優(yōu)能力。最差值波動相對較大，從模擬曲線可以看出，最優(yōu)值與最差值差距較大，說明種群具有一定的多樣性。不同參數(shù)對算法性能的影響(1)種群大小對算法性能的影響設(shè)置交叉概率為0.8，變異概率為0.07，最大迭代次數(shù)為500，染色體長度為50。當種群規(guī)模分別為100、200、400、500時，求解計算例1,結(jié)果如表2-2所示。表2-2解決方案示例1對不同人口規(guī)模的結(jié)果人口規(guī)?？們r值總?cè)萘?00309499620030959964003103100050031031000從上表可以看出，隨著種群規(guī)模的增加，總值和總量也隨之增加，當種群規(guī)模為400時，已經(jīng)命中最優(yōu)解3103，當種群規(guī)模為400時，也命中最優(yōu)解。種群規(guī)模為500。最優(yōu)解是指當種群規(guī)模增大時，遺傳算法在求解背包問題時選擇范圍更廣，更容易命中最優(yōu)解。(2)交叉概率對算法性能的影響設(shè)置變異概率為0.07，最大迭代次數(shù)為500，染色體長度為50，交叉概率為0.1、0.2、0.3、0.4、0.5、0.6、0.7，求解計算例1，結(jié)果見表2-3。表2-3不同交叉概率的計算例1結(jié)果交叉概率總價值總?cè)萘?.130919980.2309510000.3310310000.4310310000.5310310000.6310310000.731031000從表2-3可以看出，當交叉概率增大時，對應(yīng)的總值和總量也隨之增大，并且在交叉概率為0.3時命中最優(yōu)解，仍然保持最優(yōu)命中為交叉概率增加。解開。它表明交叉頻率越高，收斂到最優(yōu)區(qū)域的速度越快。(3)最大迭代次數(shù)對算法性能的影響將變異概率設(shè)置為0.07，交叉概率設(shè)置為0.8，染色體長度設(shè)置為50，迭代次數(shù)分別設(shè)置為100、200、300和500，并運行示例120次。結(jié)果如表2-4所示。表2-4計算例1不同迭代次數(shù)的求解結(jié)果最大迭代次數(shù)總價值總?cè)萘?003068999200308410003003091100050031031000從表2-4可以看出，總價值和總體積隨著迭代次數(shù)的增加而增加，在500次迭代時達到最優(yōu)解。說明當種群進化代數(shù)增加時，得到的解將更接近或直接擊中最優(yōu)解。對遺傳算法求解0-1背包問題時找到最優(yōu)解的影響非常明顯。通過上面的實驗，我可以看到當交叉概率為0.4，迭代次數(shù)為500時達到最優(yōu)解3103，那么我可以用這兩個參數(shù)來測試例2。2.3.2示例2設(shè)物品的價值為Pi，物品的重量為Wi，Wi的重量為(1,10)的隨機數(shù)，背包的最大容量為C。Pi和C由以下等式給出。(2-1)(2-2)設(shè)置交叉概率Pc=0.4，迭代次數(shù)為500，變異概率為0.07。當項目總數(shù)分別為50、100和150時，將示例2運行20次，觀察人口規(guī)模為50、100和200時的結(jié)果。當項目數(shù)為50時，20個循環(huán)的結(jié)果如表2-5所示，仿真圖分別如圖2-4、圖2-5和圖2-6所示。表2-52不同人口規(guī)模計算實例的結(jié)果人口規(guī)模迭代次數(shù)最大值最低限度平均值50500316176249.438100500322161252.524200500324160254.476圖2-4示例2的仿真圖，人口規(guī)模為50圖2-5案例2人口規(guī)模為100的仿真圖圖2-6示例2人口規(guī)模為200的仿真圖當項目數(shù)為100時，計算例2循環(huán)20次的結(jié)果如表2-6所示，仿真圖分別如圖2-7、圖2-8和圖2-9所示。表2-6計算示例2循環(huán)20次結(jié)果人口規(guī)模迭代次數(shù)最大品質(zhì)因數(shù)最低限度平均值50500616396502.48100500618378513.28200500629377518.27圖2-7示例2人口規(guī)模為50的仿真圖圖2-8案例2人口規(guī)模為100的仿真圖圖2-9案例2人口規(guī)模為200的仿真圖當項目數(shù)為150時，例2循環(huán)20次的結(jié)果如表2-7所示，仿真圖分別如圖2-10、圖2-11和圖2-12所示。表2-7程序循環(huán)20次結(jié)果人口規(guī)模迭代次數(shù)最大值最低限度平均值50500911611774.47100500911606768.38200500914592772.11圖2-10示例2的仿真圖，種群大小為50個循環(huán)和20個循環(huán)圖2-11案例2人口規(guī)模為100的仿真圖圖2-12案例2人口規(guī)模為200的仿真圖從以上實驗結(jié)果可以看出，在項目數(shù)不變的情況下，隨著種群規(guī)模的增大，計算例2經(jīng)過20個循環(huán)后得到的最大值呈現(xiàn)增加趨勢，而最小值呈現(xiàn)減小的趨勢趨勢。從模擬曲線可以看出，最大值與最小值之間的差距非常大，這也說明種群規(guī)模具有一定的多樣性。第三章GUI界面設(shè)計3.1概述圖形用戶界面（GUI），簡稱GUI，又稱圖形用戶界面，是指使用圖形來顯示計算機操作的用戶界面。圖形界面比早期計算機使用的命令行界面更容易被用戶接受。GUI的廣泛應(yīng)用是當今計算機發(fā)展的主要成果之一，對于非專業(yè)用戶的使用極為方便。從此，人們不再需要死記硬背大量的命令。相反，它們可以通過串口、菜單、按鈕等方便地進行操作。一般來說，GUI界面分為窗口、標簽、菜單、圖標、按鈕等部分。同時，GUI界面設(shè)計還應(yīng)遵循以下原則：減輕用戶的認知負擔，保持界面的一致性，滿足不同目標用戶的創(chuàng)意需求，用戶界面友好，圖標識別平衡，圖標功能一致性，建立界面和用戶交互，更人性化的視覺優(yōu)化，更易識別的圖標等元素，更可控和可擴展的易用性。MATLAB軟件GUIDE為用戶提供了一個方便高效的集成環(huán)境，GUI支持的所有用戶控件都集成在這個環(huán)境中，并提供界面外觀、屬性和行為的設(shè)置方法。GUIDE將用戶保存和設(shè)置的GUI界面保存在FIG資源文件中，并自動生成包含GUI初始化和組件界面布局控制代碼的M文件，為實現(xiàn)回調(diào)函數(shù)提供參考框架。3.2GUI界面設(shè)計3.2.1GUI界面設(shè)計步驟MATLAB的GUI開發(fā)環(huán)境(GUIDE)提供了一組用于可視化創(chuàng)建圖形窗口的工具。使用用戶界面開發(fā)環(huán)境可以輕松創(chuàng)建GUI應(yīng)用程序。它可以根據(jù)用戶設(shè)計的GUI布局自動生成M文件?？蚣?，用戶使用這個框架來編寫自己的應(yīng)用程序。使用GUIDE可以完成GUI靜態(tài)界面制作和程序編寫。步驟1：打開MATLAB新GUI，將出現(xiàn)如圖3-1所示的窗口。GUI界面提供新界面（GreatNewGUI）或打開現(xiàn)有文件的屬性頁（OpenExistingGUI）。創(chuàng)建新界面時，可以選擇空白界面、帶有控件的模板界面、帶有軸對象和菜單的模板界面以及標準查詢窗口。選擇任何一項都可以打開GUI設(shè)計工作臺，對界面靜態(tài)組件的具體修改在工作臺中實現(xiàn)。圖3-1圖形用戶界面對話框Step2：選擇BlankGUI，點擊OK，生成如圖3-2所示的空白模板。打開后，編輯區(qū)將沒有圖形子對象。我們可以根據(jù)程序的需要來編輯界面。圖3-2GUI設(shè)計界面本設(shè)計中使用的控件描述如下：一個觸摸按鈕，可選擇作為程序運行的啟動按鈕；一個可編輯的文本組件，可以作為輸入框作為參數(shù)使用；一個靜態(tài)文本標簽，可用于指示每個組件的用途；是一個彈出菜單，可以作為示例2中選擇項目數(shù)的按鈕；是一個列表框，可以用來顯示計算結(jié)果；它是一個坐標軸組件，可以顯示指定的結(jié)果圖。Step3：將本次設(shè)計中要使用的各種控件合理布局后，形成如下靜態(tài)圖：圖3-3和圖3-4是遺傳算法求解兩個實例的靜態(tài)GUI界面0-1背包問題。.在界面中，左側(cè)是參數(shù)輸入界面，可以手動編輯計算所需的算法參數(shù)，以及示例2中添加的項目數(shù)選擇選項。右側(cè)是結(jié)果顯示界面，以及上面的列表框?qū)@示20個循環(huán)中每個循環(huán)的最佳值、最差值和平均值。下面的axis1是結(jié)果顯示的坐標圖，計算結(jié)果可以坐標圖的形式顯示。圖3-3示例1的GUI靜態(tài)圖圖3-4示例2的GUI靜態(tài)圖第四步：編寫每個控件布局后的回調(diào)函數(shù)。首先，選擇“循環(huán)次數(shù)”并單擊鼠標右鍵，顯示選擇菜單，如下圖3-5所示。選擇ViewCallback選項下的回調(diào)，出現(xiàn)如圖3-6所示界面。其中，不同的功能代表不同的功能控制按鈕，只有在相應(yīng)的控制功能下寫上相應(yīng)的功能才能激活該控制。將算法程序帶入控制函數(shù)中，在函數(shù)的最后加入如下函數(shù)，將圖形輸出到軸：軸（handles.axes1）情節(jié)（1：循環(huán)編號，tracedo）；title('20循環(huán)結(jié)果','fontsize',10)xlabel('循環(huán)次數(shù)','fontsize',10);ylabel('每個循環(huán)的適應(yīng)度','fontsize',10);圖例（'最佳價值'，'最差價值'，'平均'）網(wǎng)格開啟；為了在文本框中顯示20次循環(huán)的結(jié)果，應(yīng)將存儲20次循環(huán)結(jié)果的tracedo數(shù)組調(diào)用到列表listbox1中，其中l(wèi)istbox1是文本框的標簽名稱。具體描述如下：函數(shù)listbox1_Callback(hObject,eventdata,句柄)圖3-5選擇回調(diào)函數(shù)圖3-6回調(diào)函數(shù)編寫界面3.2.2界面運行結(jié)果測試完兩個GUI界面，首先在第一個GUI界面設(shè)置參數(shù)，輸入循環(huán)數(shù)為20，最大容量為1000，個體數(shù)為50，交叉概率為0.8，變異概率為0.3點擊開始運行，然后設(shè)置第二個界面的參數(shù)，輸入循環(huán)次數(shù)為20次，最大容量為1000，個體數(shù)為50，交叉概率為0.8，變異概率為0.3，所選項目的總數(shù)分別為50.100和150。單擊“運行”，運行結(jié)果如圖3-7、圖3-8、圖3-9、圖3-10所示。圖3-7示例1的GUI運行結(jié)果圖3-8項目數(shù)為50時的運算結(jié)果圖3-9項目數(shù)為100時的運算結(jié)果圖3-10項目數(shù)為150時的運算結(jié)果第四章結(jié)論與展望4.1結(jié)論本文主要致力于利用遺傳算法求解背包問題的研究。首先簡單介紹一下背包問題，然后主要介紹本文要使用的遺傳算法。在分析現(xiàn)有遺傳算法優(yōu)缺點的基礎(chǔ)上，解決了背包問題，詳細描述了算法的結(jié)構(gòu)和過程。具體工作總結(jié)如下。(1)介紹0-1背包問題的基本概念并描述其數(shù)學(xué)模型，說明遺傳算法的基本原理和求解0-1背包問題的實現(xiàn)步驟。(2)利用遺傳算法求解兩個背包問題，得到數(shù)值結(jié)果和仿真曲線并進行分析。(3)分析不同參數(shù)對例1算法性能的影響，得到一些最優(yōu)參數(shù)，并將這些參數(shù)作為例2的實驗設(shè)置；例2中進一步研究了種群大小對遺傳算法的影響。解決0-1背包問題的效果。(4)GUI界面采用Matlab軟件設(shè)計。在操作界面，可以手動輸入遺傳算法的主要參數(shù)設(shè)置，界面顯示不同參數(shù)下的操作結(jié)果。4.2展望遺傳算法是解決背包問題等NP-hard問題的一種很好的解決方法，使用遺傳算法可以獲得很好的結(jié)果。遺傳算法因其思想簡單、易于實現(xiàn)、應(yīng)用效果顯著而被眾多應(yīng)用領(lǐng)域所接受，并在自適應(yīng)控制、組合優(yōu)化、模式識別、機器學(xué)習(xí)、管理決策等領(lǐng)域得到廣泛應(yīng)用。通過實驗驗證，取得了令人滿意的結(jié)果。由于時間緊迫，很多問題還沒有深入探討，因此在本文研究的基礎(chǔ)上，可以進一步研究和討論以下問題。(1)背包問題在實踐中有著廣泛的應(yīng)用，但其在不同應(yīng)用中的實際特點，以及數(shù)據(jù)量對遺傳算法效果的影響，本文并未進行比較。遺傳算法的一些參數(shù)的選擇，如變異概率、編碼方法和選擇方法，需要進一步研究。（2）目前遺傳算法模擬生物進化只是一種形式，還不能深入模擬生物進化的部分規(guī)律，也無法模擬學(xué)習(xí)過程的神經(jīng)元思維。因此，遺傳算法模型本身需要更加深入。研究。(3)遺傳算法在解決0-1背包問題上還存在一定的缺陷。結(jié)合蟻群算法和量子算法，可以進一步研究遺傳算法在解決背包問題中的優(yōu)勢。總結(jié)與經(jīng)驗2013年3月初，我們正式開始了我的畢業(yè)設(shè)計工作。現(xiàn)在已經(jīng)三個月了。這三個月有酸有甜，有苦有辣。期間，我經(jīng)歷了不知所措和迷茫，也經(jīng)歷了節(jié)目順利運行時的興奮。想這個時期，從最初的發(fā)呆，到慢慢進入狀態(tài)，再到思維逐漸清晰，整個過程難以用言語形容?？爝f，在這期間不僅學(xué)到了很多有用的知識。2月底，畢業(yè)設(shè)計的題目確定后，我很茫然，對這個題目感到很困惑。由于之前很少使用Maltlab軟件，遺傳算法和背包問題的知識完全沒有接觸過，可以說這篇畢業(yè)論文是從零開始的。不過，這是人的事。我每天都從網(wǎng)上下載資料學(xué)習(xí)。查閱資料后，寫了第一篇基于遺傳算法解決背包問題的評測報告。完成這兩部作品后，我對遺傳算法的原理和算法過程以及背包問題的數(shù)學(xué)模型有了基本的了解。這對以后的工作很有幫助。當數(shù)據(jù)審核和審稿報告的撰寫完成時，已經(jīng)是三月下旬了，接下來就是整個畢業(yè)論文的重頭戲——算法報告的撰寫和程序的撰寫。雖然大二的時候接觸了一些matlab，但是對M語言的應(yīng)用并不是很熟練，所以編程是整個工作中最讓我害怕的事情。在這期間，我經(jīng)歷了無數(shù)次的修改，咨詢了網(wǎng)友，咨詢了老師，然后進行了修改?；藢⒔鼉蓚€月的時間，終于完成了算法報告、主程序和GUI界面的設(shè)計。在編程和修改的過程中，我要非常感謝我的導(dǎo)師和我的同學(xué)們。編程及相關(guān)部分寫完后，5月30號提交了畢業(yè)論文初稿，郭老師認真改正后，指出了很多需要修改的地方。畢業(yè)設(shè)計是每個大學(xué)生都必須經(jīng)歷的過程，也是我們畢業(yè)前非常珍貴的記憶。每當我們看到我們的努力得到了回報，我們總是那么自豪和興奮。一切都是這樣，我們要腳踏實地，一步一步完成，認真嚴謹，有好的心態(tài)做好一件事。我從這個畢業(yè)設(shè)計過程中受益匪淺。最大的收獲是培養(yǎng)了認真務(wù)實、客觀嚴謹、踏實的學(xué)習(xí)態(tài)度，以及不怕困難、堅持不懈、努力拼搏的精神。在論文寫作和程序編寫過程中，不僅需要耐心，還需要細心。每當我的想法無法實現(xiàn)或跑不掉時，我都會有浮躁的情緒，但我不會放棄，而是及時調(diào)整心態(tài)。最重要的是理清思路，在困難面前找到突破口。一點，一步一步地實現(xiàn)自己的既定目標。你不明白的東西越多，看起來困難的東西就越多，你必須學(xué)習(xí)和克服它們。在學(xué)習(xí)的過程中你會收獲很多，學(xué)習(xí)后會有很大的成就感。完成畢業(yè)設(shè)計后最大的感受。我覺得這個畢業(yè)設(shè)計是對我們意志的鍛煉，是對我實踐能力的提高。相信這些都會對我以后的學(xué)習(xí)和事業(yè)有很大的幫助。至?xí)r光荏苒，轉(zhuǎn)眼間，大學(xué)生活就要結(jié)束了。值此畢業(yè)論文完成之際，向所有關(guān)心我、幫助過我的人表達最誠摯的感情和最美好的祝愿。論文是在導(dǎo)師郭寧的悉心指導(dǎo)下完成的。郭老師是我們畢業(yè)設(shè)計的導(dǎo)師。老師以淵博的學(xué)識和嚴謹?shù)膶W(xué)術(shù)態(tài)度，教給我們很多知識。他還以卓越的工作作風和孜孜不倦的高尚老師為我指導(dǎo)論文。從選題到完成這篇文章，草稿經(jīng)過多次修改。每一步都是在郭老師的悉心指導(dǎo)下完成的。選題，如何組織材料和布局。為我畢業(yè)論文的選題和創(chuàng)作奠定了基礎(chǔ)。還要感謝我們班的穆匡林、新翔和楚文斌，他們經(jīng)常鼓勵和幫助我，對我的論文修改提出了寶貴的意見。我愿意幫助我的老師、同學(xué)、老師和學(xué)生，友誼天長地久！在此，向我的論文導(dǎo)師郭寧表示最深切的哀悼和祝福！這篇文章的完成，也離不開其他老師、同學(xué)、朋友的幫助和關(guān)心。我要特別感謝我的班主任徐小平和我的輔導(dǎo)員周璐。這篇文章的完成離不開學(xué)校的基礎(chǔ)設(shè)施。圖書館里大量的書籍豐富了我的視野，開闊了我的視野。并為我的論文創(chuàng)作提供了很多信息。圖書館收藏了中國期刊多年來在線發(fā)表的所有學(xué)術(shù)論文，為我的論文提供了很好的參考。愿科技大學(xué)的基礎(chǔ)設(shè)施越來越完善，也希望各位師兄師姐珍惜母校寶貴的知識資源！此外，還要感謝我的家人在我學(xué)習(xí)生活中給予我的無微不至的關(guān)懷和幫助，感謝他們的辛勤付出和汗水為我換來了獲得知識的機會。“誰說一寸草，三陽”，在這里祝愿我的家人永遠健康快樂！參考[1]RalphMerkleandMartinHellman.HidingIformationandSignaturesinTrapdoorKnapsacks[J].IEEETransactionsonIformationTheory.1978,24(5);525-530[2]裴煥.基于聚類分析的背包問題求解方法研究與應(yīng)用[D].大學(xué)，2007年。[3]HorowitzE,SalmiS將分區(qū)應(yīng)用于背包問題[J].JournalofACM.1974,21(2);277-292[4]HollandJH.ADaptationinNaturalandArtificialSystems[M].AnnArborMich;密歇根大學(xué)出版社，1975年。[5]德容，KA。一類遺傳自適應(yīng)系統(tǒng)的行為分析[D]。安阿伯；密歇根大學(xué)，1975年。[6]德·戈德伯格。搜索、優(yōu)化和機器學(xué)習(xí)中的遺傳算法[M].MA;艾迪生衛(wèi)斯理.1989。[7]勞倫斯·戴維斯。遺傳算法手冊[M]．紐約;范諾斯特蘭德·萊因霍爾德，1999。[8]高慶石．Zadeh模糊集理論存在性證明及其改進。2005年第5期。[9]閔強，許博義，寇繼松．遺傳算法和神經(jīng)網(wǎng)絡(luò)的結(jié)合。1999年第2期。[10]湯唯.基于改進遺傳算法求解TSP問題的研究[D].海事大學(xué)，2008年。[11]宋海生，傅仁義，徐瑞松。求解多背包問題的混合遺傳算法[J]．計算機工程與應(yīng)用2009,45(20):45-48。[12]老虎，霍家珍，姚。一種求解船舶配載問題的混合遺傳算法[J].工業(yè)工程與管理。2006,11(3);27-31[13]荷蘭JH。自然和人工系統(tǒng)的適應(yīng)。麻省理工學(xué)院出版社。1992[14]德容卡。一類遺傳自適應(yīng)系統(tǒng)的行為分析。密歇根大學(xué)。1995.76-93P[15]于輝，王洪國，徐偉志，郭彥偉。改進的自適應(yīng)遺傳算法及其在背包問題中的應(yīng)用[J].計算機工程與應(yīng)用,200844(10):75—77[16]徐偉志，王洪國，海，于輝．矩陣鏈積序問題的并行算法研究[J]．信息技術(shù)與信息化。2007(6):71-73[17]郭彥偉，王洪國，王欣，于輝。一種基于并行策略的改進BP算法[J]．計算機技術(shù)與發(fā)展。2008年18（10）：110-112[18]郭曉輝，遺傳算法在求解背包問題中的應(yīng)用[J]．鐵道學(xué)院學(xué)報,2001,22(3):32.附錄1源程序MATLAB主程序示例1主程序clc清除關(guān)閉所有循環(huán)編號=1；traceAll=細胞（循環(huán)編號）；對于ii=1:LoopNumber%%0-1基于遺傳算法的背包算法%項目價值val=[22020818192180180165162160158155130125122120...118115110105101100100989695908882807775...7372706966656360585650302015108...531]；%項目體積體積=[8082857072706650552550554048503222603032...403835322528302250304530605020652025301020...25151010104421]；背包最大容量的百分比MAX_CAP=1000；％范圍LEN=大小（val，2）；%樣本長度POP_NUM=50；%人口P_CROSS=0.8；%交叉概率P_MUTA=0.07；%突變概率%最大迭代代數(shù)MAX_GEN=500；%初始化樣本samp_arr=2*rand(POP_NUM,LEN)-1;samp_arr=hardlim（samp_arr）；%記錄參數(shù)max_samp=samp_arr(1,:);max_val_old=-9999999;max_index_old=0；max_val_new=0；max_index_new=0；min_val=0;min_index=0;%記錄參數(shù)%存儲適者生存得到的樣本的索引獲勝者指數(shù)=ones（1，POP_NUM）；%輪盤賭rtable=ones(1,POP_NUM);%最大適應(yīng)值記錄fit_best=zeros(1,MAX_GEN);fit_worst=zeros(1,MAX_GEN);fit_mean=zeros(1,MAX_GEN);%適應(yīng)性fit_arr=zeros(1,POP_NUM);%初始化隨機種子rand('state',sum(100*clock));%迭代計數(shù)器計數(shù)=0；而1計數(shù)=計數(shù)+1P_MUTA=0.05+計數(shù)*0.0001；%計算適應(yīng)度值temp_sum=vol*samp_arr'；%利用矩陣乘法的便利計算每個個體的總體積，注意第二個矩陣必須轉(zhuǎn)置速率=val./vol；%計算每個物體單位體積的值，即值密度對于i=1:POP_NUMj=0;如果temp_sum(i)>MAX_CAP[temp,index]=sort(rate,'ascend');而temp_sum(i)>MAX_CAPj=j+1；如果samp_arr(i,index(j))==1samp_arr(i,index(j))=0;temp_sum(i)=temp_sum(i)-vol(index(j));結(jié)尾結(jié)尾結(jié)尾結(jié)尾%更新最優(yōu)值fit_arr=val*samp_arr';%與上述方法相同，使用每個個體的總值計算[max_val_new,max_index_new]=max(fit_arr);fit_worst(count)=min(fit_arr);fit_mean(count)=mean(fit_arr);%如果小于最后一個，用最后一個替換如果max_val_new<max_val_oldmax_val_new=max_val_old；samp_arr(max_index_new,:)=max_samp;fit_arr(max_i