基于遺傳算法的01背包問(wèn)題研究

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

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