【正文】 103 1000 3103 1000 3103 1000 3103 1000 3103 1000 從表 23 可以看出當(dāng)交叉概率增大時(shí)與之對(duì)應(yīng)的總值和 總體積 也隨之增加并在交叉概率為 時(shí)命中最優(yōu)解，隨著交叉概率增加大依然保持命中最優(yōu)解。 表 21 算例 1求解結(jié)果 循環(huán)次數(shù) 迭代次數(shù) 最優(yōu)值 最差值 平均值 命中最優(yōu)解概率 20 500 3103 1429 45% 從表 21可以看出在程序運(yùn)行 20次中命中了 9次最優(yōu)解 3103，平均值為 ，最優(yōu)值與最差值的差值為 1674，說(shuō)明遺傳算法求解背包問(wèn)題不易陷入局部最優(yōu)。對(duì)各個(gè)染色體計(jì)算其適應(yīng)度值，淘汰適應(yīng)度值最低的，復(fù)制適應(yīng)度值最高的，用最高的代替最低的，這樣完成選擇；再隨機(jī)產(chǎn)生交叉點(diǎn)及相互交叉的染色體進(jìn)行交叉，計(jì)算交叉后的染色體是否符合要求，即裝入背包的物品的總體積小于背包容量，若不符合則交叉失敗，重新交叉，達(dá)到交叉最多 次數(shù)未交叉成功則退出；交叉完成后就進(jìn)行變異，根據(jù)變異概率隨機(jī)選擇變異的染色體，隨機(jī)產(chǎn)生變異點(diǎn)進(jìn)行變異，變異后也需要計(jì)算染色體是否符合要求，若不符合則變異失敗，重新變異，達(dá)到變異最多次數(shù)未變異成功則退出。 %變異操作，直接針對(duì)整個(gè)樣本集操作 muta_arr=( rand(POP_NUM, LEN) P_MUTA )。 %交叉點(diǎn)位置 ,[1, POP_NUM1] temp_cross=samp_arr(cross_index(i), cross_pos:end)。 % 交叉操作 cross_index=1:POP_NUM。 %輪盤(pán)， rotary table %生成輪盤(pán)，類(lèi)似于概率分布 For i=2:POP_NUM rtable(i)=rtable(i1)+rtable(i)。)。這個(gè)問(wèn)題解的總組合數(shù)有 2 個(gè)，其數(shù)學(xué)模型表示為：1niii XW C? ??時(shí)，使得1niii XP??大， Xi=1 或 0（ i=1， 2，?， n)。每產(chǎn)生一個(gè)染色體，就對(duì)它進(jìn)行一次檢驗(yàn)，如果不滿足約束條件，則拒絕接受。運(yùn)用簡(jiǎn)單遺傳算法求解背包問(wèn)題時(shí)，若問(wèn)題的規(guī)模不大時(shí)能夠得到最優(yōu)解或近似最優(yōu)解。 單靠變異不能在求解中得到好處。這個(gè)過(guò)程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。給出目標(biāo)函數(shù) f，則 f(bi)稱為個(gè)體 bi的適應(yīng)度。概括地講，遺傳算法求解組合優(yōu)化問(wèn)題的具體步驟可描述如下： (1)初始化：選擇一個(gè)群體，即選擇一個(gè)串或個(gè)體的集合 bi， i=l， 2，? n。 遺傳算法的原理可以簡(jiǎn)要給出如下：選擇初始值，確定合適的值，完成選擇；進(jìn)行交叉，變異；重 復(fù)直到得到最優(yōu)解這里所指的某種結(jié)束準(zhǔn)則一般是指?jìng)€(gè)體的適應(yīng)度達(dá)到給定的閥值；或者個(gè)體的適應(yīng)度的變化率為零。在每個(gè)串中，每個(gè)二進(jìn)制位就是個(gè)體染色體的基因。 滿足這個(gè) 假設(shè)的條件比較簡(jiǎn)單，包括兩方面： a) 表現(xiàn)型相近的個(gè)體，其基因型相近； b) 遺傳因子間相關(guān)性低。 設(shè)計(jì)（論文）專(zhuān)用紙 11 定義 定義距 (defining length)模式 H 中的第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為該模式的定義距，記作δ (H)。遺傳算法的執(zhí)行過(guò)程包括了大量的隨機(jī)性操作，因此有必要對(duì)其數(shù)學(xué)機(jī)理進(jìn)行分析。這個(gè)群體不斷的經(jīng)過(guò)遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個(gè)體更多的遺傳到下一代，這樣最終在種群中將會(huì)得到一個(gè)優(yōu)良的個(gè)體 X，它所對(duì)應(yīng)的的表現(xiàn)型 X 將達(dá)到或接近問(wèn)題的最優(yōu)解 X*。 d. 在 matlab 環(huán)境中進(jìn)行 GUI 界面設(shè)計(jì)， 運(yùn)行界面中遺傳算法主要的參數(shù)可通過(guò)手動(dòng)輸入自行修改，同時(shí)通過(guò) GUI 界面可以直接觀察到仿真曲線的變化情況。例如：利用 GA的機(jī)器學(xué)習(xí)來(lái)調(diào)整人工神經(jīng)網(wǎng)絡(luò)的權(quán)值等；利用 GA學(xué)習(xí)模糊控制的奴隸度函數(shù)以改進(jìn)模糊控制系統(tǒng)的性能。學(xué)者構(gòu)造了各種復(fù)雜的測(cè)試函數(shù)，既有連續(xù)函數(shù)也有離散函數(shù)，有高維的也有低維的，有凹的也有凸的，有多峰的也有單峰的，遺傳算法較其他優(yōu)化方法便于得到較好的結(jié)果。 可以對(duì)群體按一定的方式進(jìn)行分組，分組后各組的個(gè)體遺傳進(jìn)化過(guò)程可以在不同的處理機(jī)上相互獨(dú)立地進(jìn)行，在適當(dāng)?shù)臅r(shí)候，各處理機(jī)之間相互交換信息。 個(gè)體適應(yīng)度的評(píng)價(jià) 或計(jì)算 在遺傳算法的運(yùn)行過(guò)程中所占用的運(yùn)行時(shí)間比較長(zhǎng)。 設(shè)計(jì)（論文）專(zhuān)用紙 6 遺傳算法分類(lèi) （ 1） 混合遺傳算法 單用簡(jiǎn)單的遺傳算法在許多情況下不是十分有效，容易產(chǎn)生早熟現(xiàn)象以及局部尋優(yōu)能力較差等問(wèn)題，于是提出了多種混合算法。遺產(chǎn)算法只需自適應(yīng)值和串編碼等通用信息，故幾乎可以處理任何問(wèn)題。 工科數(shù)學(xué)教育也應(yīng)有所調(diào)整 ,以適應(yīng)高新技術(shù)發(fā)展的需要 。 這一思想在 90 年代初逐步形成 ,而由模糊集論的創(chuàng)始人 ,美國(guó) Zadeh LA在 1993 年于漢城召開(kāi)的國(guó)際模糊系統(tǒng)協(xié)會(huì) ( IFSA )第五屆世界會(huì)議首先明確提出隨后在許多有關(guān)的國(guó)際學(xué)術(shù)會(huì)議上得到充分體現(xiàn)。 今 后幾年 ,可以預(yù)期 ,拓廣更加多樣的應(yīng)用領(lǐng)域 ,其中包括各種 遺傳算法 程序設(shè)計(jì)環(huán)境的開(kāi)發(fā)仍將是遺傳算法發(fā)展的主流 。在此之后世界范圍內(nèi)掀起了關(guān)于遺傳算法研究與 設(shè)計(jì)（論文）專(zhuān)用紙 4 應(yīng)用的高潮。 遺傳算法的研究現(xiàn)狀與發(fā)展趨勢(shì) 查克斯 本文將對(duì)遺傳算法做進(jìn)一步研究并結(jié)合應(yīng)用于背包問(wèn)題的求解，并通過(guò)實(shí)驗(yàn)證明遺傳算法對(duì)求解背包問(wèn)題是比較有效的。首先，很多算法的計(jì)算量都很大，迭代的時(shí)間很長(zhǎng)。所以在前人研究經(jīng)驗(yàn)的基礎(chǔ)上開(kāi)展對(duì)背包問(wèn)題的研究具有 重要意義 。最后在 matlab 環(huán)境中進(jìn)行 GUI 界面設(shè)計(jì)，通過(guò) GUI界面可以直觀的看到 01背包問(wèn)題的 2個(gè)算例在不同參數(shù)設(shè)置下仿真曲線的變化情況。背包問(wèn)題可分為一維背包，二維背包問(wèn)題，完全背包問(wèn)題，多重背包問(wèn)題、分組背包問(wèn)題等等。 設(shè)計(jì)（論文）專(zhuān)用紙 學(xué)士學(xué)位論文 基于遺傳算法的 01 背包問(wèn)題研究 學(xué) 院： 信息工程與自動(dòng)化學(xué)院 專(zhuān)業(yè)年級(jí) : 自動(dòng)化 2020 級(jí) 學(xué)生姓名： 學(xué) 號(hào)： 指導(dǎo)教師： 職 務(wù)： 實(shí)驗(yàn)師 起止時(shí)間： 2020 年 3 月 — 2020 年 6 月 設(shè)計(jì)（論文）專(zhuān)用紙 Kun Ming University of Science and Technology Bachelor39。 Design a graphical user interface (GUI), realize the input parameters and the simulation results show Key Words： 01 knapsack problem； Geic algorithm； Popsize； Matlab； GUI 設(shè)計(jì)（論文）專(zhuān)用紙 第 III 頁(yè) 目錄 摘要 ............................................................................................................................................................................ I ABSTRACT ............................................................................................................................................................ II 目錄 ......................................................................................................................................................................... III 前言 ........................................................................................................................................................................... V 第一章 緒 論 .........................................................................................................................................................1 背包問(wèn)題簡(jiǎn)介 ................................................................................................................................................1 01 背包問(wèn)題背景 ........................................................1 ......................................................1 遺傳算法簡(jiǎn)介 ...............................................................................................................................................2 遺傳算法的研究現(xiàn)狀與發(fā)展趨勢(shì) ............................................3 遺傳算法的特點(diǎn) .........................................................5 遺傳算法分類(lèi) ...........................................................6 ..........................................................7 本文主要工作 ...............................................................................................................................................7 第二章 基于遺傳算法的 01背包問(wèn)題研究 .....................................................................................................9 遺傳算法的思想 ...........................................................................................................................................9 .....................................................10 .......................................................12 .....................................................13 使用遺傳算法求解 01背包問(wèn)題 ........................................................................................................... 16 數(shù)值試驗(yàn)以及結(jié)果分析 ........................................