【正文】 變異概率 δ (H) 表示模式 H的定義距； o（ H）表示模式 H的階。 在遺傳操作中，即使階數(shù)相同的模式，也會(huì)有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 設(shè)計(jì)（論文）專用紙 11 定義 定義距 (defining length)模式 H 中的第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為該模式的定義距，記作δ (H)。例如： o(011*1*)=4。因此模式也可解釋為相同的構(gòu)形。它將 GA 的運(yùn)算過程理解為模式運(yùn)算過程，并從模式運(yùn)算的角度解釋 GA 的性能特點(diǎn)。遺傳算法的 執(zhí)行過程包括了大量的隨機(jī)性操作，因此有必要對(duì)其數(shù)學(xué)機(jī)理進(jìn)行分析。還是求目標(biāo)函數(shù)的最小值 )及其數(shù)學(xué)描述形式或量化方法； 第三步：確定表示可行解的染色體編碼方法，即確定出個(gè)體的基因型 X及遺傳算法的搜索空間； 第四步：確定解碼方法， 即確定出由個(gè)體基因型 x 和個(gè)體表現(xiàn)型 X的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法； 第五步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo)函數(shù)值 f(x)個(gè)體適應(yīng)度 F(X)的轉(zhuǎn)換規(guī)則； 第六步：設(shè)計(jì)遺傳算子，即確定出選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法； 第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的 M， Pc， Pm等參數(shù)。 d) 運(yùn)行參數(shù)：群體大小 M；遺傳運(yùn)算的終止 進(jìn)化代數(shù) T 乃一般取為 100500；交叉概率 Pc，一般取為 ；變異概率 Pm，一般取為 。 b) 個(gè)體適應(yīng)度評(píng)價(jià)：基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。這個(gè)群體不斷的經(jīng)過遺傳和進(jìn)化操作，并 且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個(gè)體更多的遺傳到下一代，這樣最終在種群中將會(huì)得到一個(gè)優(yōu)良的個(gè)體 X，它所對(duì)應(yīng)的的表現(xiàn)型 X 將達(dá)到或接近問題的最優(yōu)解 X*。 生物進(jìn)化是以集團(tuán)為主體的，與此相適應(yīng)的，遺傳算法的運(yùn)算對(duì)象是由 M個(gè)個(gè)體所組成的集合，成為群體。在一系列研究工作基礎(chǔ)上。它最早是有沒過密歇根大學(xué)的 Holland 教授提出的，起源于 60 年代對(duì)自然和人工自適 應(yīng)系統(tǒng)的研究 [13]。 d. 在 matlab 環(huán)境中進(jìn)行 GUI 界面設(shè)計(jì)， 運(yùn)行界面中遺傳算法主要的參數(shù)可通過手動(dòng)輸入自行修改，同時(shí)通過 GUI 界面可以直接觀察到仿真曲線的變化情況。介紹了進(jìn)化算法的基本理論，對(duì)典型的幾種進(jìn)化算法進(jìn)行了簡(jiǎn)要說明，并對(duì)遺傳算法的基本理論、應(yīng)用情況和研究趨勢(shì)做了較為詳細(xì)的論述。 本文主要工作 a. 介紹了 01 背包問題的概念，接著論述求解該問題的各種傳統(tǒng)算法，并對(duì) 01背包問題進(jìn)行數(shù)學(xué)描述。數(shù)據(jù)挖掘就是大型數(shù)據(jù)庫(kù)中提取人們感興趣的、隱含的、有潛在應(yīng)用價(jià)值的知識(shí) 。例如：利用 GA的機(jī)器學(xué)習(xí)來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的權(quán)值等；利用 GA學(xué)習(xí)模糊控制的奴隸度函數(shù)以改進(jìn)模糊控制系統(tǒng)的性能。 。 。 ，遺傳算法在自動(dòng)控制領(lǐng)域的應(yīng)用日益增加并取得了較好的成果。學(xué)者構(gòu)造了各種復(fù)雜的測(cè)試函數(shù)，既有連續(xù)函數(shù)也有離散函數(shù)，有高維的也有低維的，有凹的也有凸的，有多峰的也有單峰的，遺傳算法較其他優(yōu)化方法便于得到較好的結(jié)果。 。隨著組合優(yōu)化問題規(guī)模的增加，其搜索空間也急劇增加，在計(jì)算機(jī)上用窮舉法不可能求出其最優(yōu)解，而遺傳算法可以在此類問題上尋求問題的滿意解。其典型應(yīng)用領(lǐng) 域如下。 可以對(duì)群體按一定的方式進(jìn)行分組，分組后各組的個(gè)體遺傳進(jìn)化過程可以在不同的處理機(jī)上相互獨(dú)立地進(jìn)行，在適當(dāng)?shù)臅r(shí)候，各處理機(jī)之間相互交換信息。這樣，產(chǎn)生群體過程中的選擇、交叉、變異操作就可以相互獨(dú)立地并行進(jìn)行。 。 互依賴關(guān)系，這樣各個(gè)個(gè)體的適應(yīng)度計(jì)算過程就可以相互獨(dú)立、并行地進(jìn) 行。 個(gè)體適應(yīng)度的評(píng)價(jià) 或計(jì)算在遺傳算法的運(yùn)行過程中所占用的運(yùn)行時(shí)間比較長(zhǎng)。并行遺傳算法主要從下列四個(gè)方面對(duì)其進(jìn)行改進(jìn)和發(fā)展。由于遺傳算法與傳統(tǒng)優(yōu)化方法的互補(bǔ)性，混合遺傳算法通常比單一算法優(yōu)越?；旌线z傳算法的基本思想是：對(duì)于每個(gè)新產(chǎn)生的后代在其進(jìn)入下一代群體之前應(yīng)用局部?jī)?yōu)化技術(shù) (如爬山法、模擬退火算法等 )，使之移動(dòng)到最近的局部最優(yōu)點(diǎn)。 設(shè)計(jì)（論文）專用紙 6 遺傳算法分類 （ 1） 混合遺傳算法 單用簡(jiǎn)單的遺傳算法在許多情況下不是十分有效，容易產(chǎn)生早熟現(xiàn)象以及局部尋優(yōu)能力較差等問題，于是提出了多種混 合算法。 d. 算法中的選擇、交叉、和變異都是隨機(jī)操作，而不是確定的精確規(guī)則。這就是一個(gè)強(qiáng)烈的過濾過程，并且是一個(gè)并行濾波機(jī)制。 遺傳算法的初始串 集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息。遺產(chǎn)算法只需自適應(yīng)值和串編碼等通用信息，故幾乎可以處理任何問題。 b. 求解時(shí)使用特定問題的信息極少，容易形成通用算法程序。傳統(tǒng)優(yōu)化算法是從單個(gè)初值迭代求最優(yōu)解的，容易誤入局部最優(yōu)解。 遺傳算法的特點(diǎn) a. 算法從問題解的串集開始搜索，而不是從單一解開始。 工科數(shù)學(xué)教育也應(yīng)有所調(diào)整 ,以適應(yīng)高新技術(shù)發(fā)展的需要 。 學(xué)術(shù)界要主動(dòng)和企業(yè)界連手開發(fā)遺傳算法的應(yīng)用 ,要重視引進(jìn)或自行研制類似 于 SP licer 的程序設(shè)計(jì)環(huán)境 ,使遺傳算法的應(yīng)用更加方便和快捷 。 理論研究與實(shí)際應(yīng)用不夠緊密 ,阻礙了我國(guó)高新技術(shù)的迅速發(fā)展 ,幾乎已經(jīng)成為頑癥 。 例如 ,清華大學(xué)李衍達(dá)院士領(lǐng)導(dǎo)的研究集體在幾乎同一時(shí)期開展了這一重要方向的研究 1995年 , Zadeh 在 IFSA 的第六屆世界會(huì)議上再次強(qiáng)調(diào)了這一方向的重要 設(shè)計(jì)（論文）專用紙 5 性 ,并且認(rèn)為上述所謂的混合智能系統(tǒng)的應(yīng)用將覆蓋從消費(fèi)品生產(chǎn)到核反應(yīng)堆設(shè)計(jì)以至證券管理 ,而 “ 在未來幾年中可能無處不在 ” 。 這一思想在 90 年代初逐步形成 ,而由模糊集論的創(chuàng)始人 ,美國(guó) Zadeh LA在 1993 年于漢城召開的國(guó)際模糊系統(tǒng)協(xié)會(huì) ( IFSA )第五屆世界會(huì)議首先明確提出隨后在許多有關(guān)的國(guó)際學(xué) 術(shù)會(huì)議上得到充分體現(xiàn)。 當(dāng)前一個(gè)特別值得重視的趨勢(shì)是一些面向?qū)ο?的智能技術(shù) ,其中主要是模糊邏輯 [8](Fuzzy Logic, FL ),神經(jīng)網(wǎng)絡(luò) [9](Neural Network, NN )以及遺傳算法等的綜合應(yīng)用。 自然 ,不論從理論還是應(yīng)用的角度看 ,最緊迫的應(yīng)是關(guān)于算法收斂性問題的研究 ,特別是過早收斂的防止 。 與此同時(shí) ,這并不意味著理論研究會(huì)被忽視 , 這方面同樣有大量工作要做。 今 后幾年 ,可以預(yù)期 ,拓廣更加多樣的應(yīng)用領(lǐng)域 ,其中包括各種 遺傳算法 程序設(shè)計(jì)環(huán)境的 開發(fā)仍將是遺傳算法發(fā)展的主流 。 遺傳算法在應(yīng)用方面取得的豐碩成果 ,使人們對(duì)它的發(fā)展前景充滿信心 。在國(guó)內(nèi)，武漢大學(xué)成立了一個(gè)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室。 1991 年 Davis 在他的《 Hand book of geic algorithm》 [7]一書中介紹了大量的實(shí)例。在此之后世界范圍內(nèi)掀起了關(guān)于遺傳算法研究與 設(shè)計(jì)（論文）專用紙 4 應(yīng)用的高潮。他將遺傳算法定義為適應(yīng)算法，可以廣泛的應(yīng)用于系統(tǒng)最優(yōu)化的研究， 1975 年 DeJone 做了大量實(shí)驗(yàn)，建立了著名的 DeJone 的測(cè)試函數(shù) [5]。 基于 生物進(jìn)化理論，從 20 世紀(jì) 60年代起科學(xué)家們就嘗試用計(jì)算的方法模擬生物遺傳和選擇進(jìn)化過程。凡是在生存斗爭(zhēng)中獲勝的個(gè)體對(duì)環(huán)境的適應(yīng)性都比較強(qiáng)，因此生物進(jìn)化的過程就是這種“物競(jìng)天擇，適者生存”的過程，這種過程是一個(gè)緩慢的、連續(xù)和長(zhǎng)期的過程。 遺傳算法的研究現(xiàn)狀與發(fā)展趨勢(shì) 查克斯在遺傳算法的每一代中，根據(jù)個(gè)體在問題領(lǐng)域中的適應(yīng)度值和從自然遺傳學(xué)中借鑒來的再造方法進(jìn)行選擇，產(chǎn)生一個(gè)新的近似解。其本質(zhì)是一種高效、并行、全局搜索的方法，它 能在搜索過程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自適應(yīng)地控制搜索過程以求得最優(yōu)的方法。進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來的，這些 設(shè)計(jì)（論文）專用紙 3 現(xiàn)象包括遺傳、突變、自然選擇以及雜交等 。 本文將對(duì)遺傳算法做進(jìn)一步研究并結(jié)合應(yīng)用于背包問題的求解，并通過實(shí)驗(yàn)證明遺傳算法對(duì)求解背包問題是比較有效的。 其次， 進(jìn)化算子的各態(tài)歷經(jīng)性使得遺傳算法能夠非常有效地進(jìn)行概率意義的全局 搜索 。與以上幾種算法相比遺傳算法具有一定的優(yōu)勢(shì)。第二，貪婪算法速度快，爬坡能力強(qiáng)，但是它適用于搜索局部最優(yōu)解 ,可能會(huì)陷入局部極值而得不到全局最優(yōu)解。首先，很多算法的計(jì)算量都很大，迭代的時(shí)間很長(zhǎng)。 傳統(tǒng)求解背包問題的方法可以概括為精確算法和近似算法，其中精確算法有動(dòng)態(tài)規(guī)劃法，回溯法和分支限界法，近似算法有遺傳算法，貪婪算法和蟻群算法，由于精確算法的時(shí)間復(fù)雜性和空間復(fù)雜性等缺點(diǎn)，近年來利用近似算法求解背包問題已成為重點(diǎn)。上世紀(jì)九十年代以后，隨著生物仿生技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展 ，各種模擬生物物理規(guī)律的并行近似算法不斷涌現(xiàn)，例如：遺傳算法已經(jīng)在 01背包問題上得到了較好的應(yīng)用，螞蟻算法等仿生算法也很好的應(yīng)用 設(shè)計(jì)（論文）專用紙 2 到了組合優(yōu)化問題中。此后 20幾年背包問題沒有較大的發(fā)展，直到 1974 年，hoeowitz 和 salmi 利用分支節(jié)點(diǎn)法 [3]解答背包問題，他們提出背包問題的可分性，為該問題的求解指出了一條新型道路。所以在 前人研究經(jīng)驗(yàn)的基礎(chǔ)上開展對(duì)背包問題的研究具有 重要意義 。 在我們的現(xiàn)實(shí)生活中許多問題都可以用背包問題來描述，例如工廠中的下料問題、管理中的資源分配問題、裝箱問題、資金預(yù)算問題等等都可以建模為背包問題。對(duì)于大規(guī)模的背包問題要列出所有可能的物品在計(jì)算上是不可能實(shí)現(xiàn)的。背包問題主要思路是假定一個(gè)人擁有大量物品，物品的重量各不相同，他要選擇一些物品放入背包中。最后在 matlab 環(huán)境中進(jìn)行 GUI 界面設(shè)計(jì)，通過 GUI界面可以直觀的看到 01背包問題的 2個(gè)算例在不同參數(shù)設(shè)置下仿真曲線的變化情況。 在論文首先詳細(xì)介紹了遺傳算法的數(shù)學(xué)基礎(chǔ)、基本原理、實(shí)現(xiàn)過程，以及使用遺傳算法求解 01 背包問題的 2 個(gè)算例并得到相關(guān)仿真結(jié)果，并對(duì)仿真結(jié)果進(jìn)行分析。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。 遺傳算法（ Geic Algorithm）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法。背包問題可分為一維背包，二維背包問題，完全背包問題，多重背包問題、分組背包問題等等。 Analyzes the population size, number of iterations, and the influence of the mutation probability on the algorithm results。 Geic algorithm for the theoretical research, elaborated the basic principle of geic algorithm in detail, the research trend and application in the 01 knapsack problem。 專題（子課題）題目： 專題（子課題）內(nèi)容： 畢業(yè)設(shè)計(jì)（論文）指導(dǎo)教師（簽字）： 主 管 教 學(xué) 院 （部） 長(zhǎng)（簽字）： 年 月 日 設(shè)計(jì)（論文）專用紙 第 I 頁(yè) 摘要 本文介紹了 01 背包問題的基本概念，綜述了求解 01 背包問題的傳統(tǒng)方法；對(duì)遺傳算法進(jìn)行了理論研究，詳細(xì)的闡述了遺傳算法的基本原理、研究趨勢(shì)和在 01背包問題中的應(yīng)用；利用 Matlab 仿真平臺(tái)對(duì) 2 個(gè)算例進(jìn)行了測(cè)試，證明了遺傳算法求解背包問題的有效性；通過實(shí)例分析了種群規(guī)模、迭代次數(shù)以及變異概率對(duì)算法結(jié)果的影響； 設(shè)計(jì)了圖形用戶界面（ GUI） ，實(shí)現(xiàn)了參數(shù)的輸入與仿真結(jié)果顯示。 設(shè)計(jì)（論文）專用紙 學(xué)士學(xué)位論文 基于遺傳算法的 01 背包問題研究 學(xué) 院： 信息工程與自動(dòng)化學(xué)院 專業(yè)年級(jí) : 自動(dòng)化 2020 級(jí) 起止時(shí)間： 2020 年 3 月 — 2020 年 6 月 設(shè)計(jì)（論文）專用紙 Kun Ming University of Science and Technology Bachelor39。s Degree Thesis Geic Algorithm for 01 Knapsack Problem