閩江學院大學生創新創業訓練計畫
專案研究報告
專案名稱memetic演算法求解多維揹包問題
專案編號201310395014
專案型別√□ 創新訓練專案 □ 創業訓練專案
□ 創業實踐專案
專案負責人何玲
系（院）、年級、專業數學系11級金融數學專業
聯絡**188
指導老師林耿
二〇一四年 3 月 29 日
目錄摘要1
1. 前言1
1.1問題描述1
1.2問題研究現狀及實際應用1
1.3禁忌搜尋2
1.4文化基因演算法2
2. memetic演算法3
2.1數學模型3
2.2 求解演算法4
2.2.1演算法框架4
2.2.2演算法流程5
2.3演算法具體操作5
2.3.1帶反饋機制的禁忌搜尋演算法5
2.3.2交叉運算元7
3.例項**9
3.1**實驗9
3.2標準測試例子和演算法引數設定9
4.專案成果12
結束語13
參考文獻14
memetic演算法求解多維揹包問題
摘要本小組成員在去年參加大學生創新性實驗計畫專案——多維揹包問題，通過近一年的努力，我們的專案至今為止已經較為圓滿的完成了我們的預計目標。
本文給出了求解多維揹包問題的memetic演算法，演算法主要由帶反饋機制的禁忌區域性搜尋演算法，交叉運算元，種群更新策略組成。該種群更新策略同時考慮種群中解的質量與種群的多樣性，提高演算法搜尋的多樣性。利用標準測試例子測試表明，該演算法能夠有效避免陷入區域性最優解,能夠找到比現有演算法更好的結果。
第1節前言
1.1 問題描述
揹包問題(knapsack problem)是一種組合優化的np完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和**，在限定的總重量內，我們如何選擇，才能使得物品的總**最高。
問題的名稱**於如何選擇最合適的物品放置於給定揹包中。相似問題經常出現在商業、組合數學，計算複雜性理論、密碼學和應用數學等領域中。也可以將揹包問題描述為決定性問題，即在總重量不超過w的前提下，總價值是否能達到v？
它是在2023年由merkel和hellman提出的。
多維揹包問題(multidimensional knapsackproblem，mkp)即維數不定的揹包問題。即對一件物品多種限制。比如0-1揹包裡物品有價值和重量的限制。
那麼多維揹包就可能出現物品有價值、重量、購買**、對此物品喜好程度等一系列限制。
1.2問題研究現狀及實際應用
多維揹包問題是乙個經典的組合優化問題，其求解的本質就是在滿足一些資源約束的前提下，從候選物件集中發現乙個能夠使總的利益函式值最大的物件子集，該問題的求解是乙個典型的np一難問題。由於現實世界中許多典型問題如分布式系統中的處理器分配，航運中的貨物裝載、市政工程中專案選擇以及金融界的投資預算、計算機系統的設計、集合的劃分、組合拍賣、材料的切割、儲存分配等[1]，都可轉化為多維揹包問題來求解，因此，多維揹包問題的求解一直以來是人們關注的乙個研究熱點。
目前，求解多維揹包問題的演算法大致可分為精確演算法和啟發式演算法。精確演算法包括隱列舉法、分支定界[2]、動態規劃[3]等。這些精確演算法能夠有效地找到較小規模多維揹包問題的精確解，但對於較大規模的多維揹包問題，難以在可接受的時間內找到高質量的解。
近年來，學者們根據不同的思想提出了許多啟發式演算法，如遺傳演算法[4,5]、蟻群演算法[6,7]、分布估計演算法[8]、禁忌搜尋[9]、演化演算法[10,11,12]、粒子群演算法[13]、分散搜尋演算法[14]、競爭決策演算法[15]、免疫演算法[16]等。
其中．貪婪演算法、模擬退火演算法和禁忌搜尋演算法等近似演算法雖運算速度快，但是運算元設計需要一定的經驗和技巧，演算法穩定性差，且不能保證求解到最優解[17|。遺傳演算法在求解揹包問題等複雜組合優化問題時，往往會出現早熟收斂和種群多樣性喪失快等問題。
本文採用禁忌搜尋與遺傳演算法相結合的memetic演算法。
1.3禁忌搜尋
禁忌搜尋是人工智慧的一種體現，是區域性領域搜尋的一種擴充套件。禁忌搜尋最重要的思想是標記對應已搜尋的區域性最優解的一些物件，並在進一步的迭代搜尋中盡量避開這些物件（而不是絕對禁止迴圈），從而保證對不同的有效搜尋途徑的探索。禁忌搜尋涉及到臨域（neighborhood）、禁忌表（tabu list）、禁忌長度（tabu length）、候選解（candidate）、藐視準則（aspiration criterion）等概念;
1.4文化基因演算法
牛津大學的道金斯因著作《自私的基因》(theselfish gene，1976)[17]而名噪一時，在這本書中，道金斯提出了乙個全新的概念一一meme，它是乙個與gene相對應的單詞，代表乙個文化傳播或模仿單位。pablo moscato於2023年首次提出memeticalgorithm的概念。memetic一詞由meme而來，根據道金斯提出的本意，應理解為「文化基因」，因此我們將memetic algorithm稱為文化基因演算法。
文化基因演算法是一種基於種群的全域性搜尋和基於個體的區域性啟發式搜尋的結合體，這樣的結合機制使其搜尋效率在某些問題領域比傳統遺傳演算法快幾個數量級，可應用於廣泛的問題領域並得到滿意的結果。很多人將文化基因演算法看作混合遺傳演算法、遺傳區域性搜尋或是拉馬克式進化演算法，實際上，文化基因演算法提出的是一種框架、是乙個概念，在這個框架下，採用不同的搜尋策略可以構成不同的文化基因演算法，如全域性搜尋策略可以採用遺傳演算法、進化策略、進化規劃等，區域性搜尋策略可以採用爬山搜尋、模擬退火、貪婪演算法、禁忌搜尋、導引式區域性搜尋等。
第2節 memetic演算法
2.1數學模型
給定個物品的集合,多維揹包問題考慮的是從集合中選出一組滿足所有問題約束的物品，使得這些物品的價值之和最大。引入維0-1向量，其中為對應第個物品的變數。當第個物品被選中放入揹包時，；否則，。
則多維揹包問題可以描述為如下的整數規劃：
其中，，為正實數。
2.2求解演算法
2.2.1演算法框架
step 1 隨機構造初始種群。
step 2 對種群中的每個解，分別採用帶反饋機制的禁忌搜尋演算法進行區域性搜尋，所得的區域性最優解仍記為。令。
step 3 從種群中任意選擇兩個解，然後通過交叉運算元產生乙個新的解，並以為初始點，應用帶反饋機制的禁忌搜尋演算法進行區域性搜尋，所得的區域性最優解仍記為。如果且，則令。
step 4 利用同時考慮種群中解的質量和種群多樣性的種群更新策略更新種群。
step 5 如果演算法的停止準則滿足，則停止，輸出；否則，轉step 3。
其中為了降低區域性搜尋階段的計算量，本文採用精確罰函式法定義適應度函式為：
，其中為懲罰引數。
設為多維揹包問題(mkp)的可行域，即
。2.2.2演算法流程
否2.3演算法具體操作
2.3.1帶反饋機制的禁忌搜尋演算法
禁忌搜尋於2023年由glover提出後，已經成功地應用於解決各種優化問題。本文採用帶有反饋機制的禁忌搜尋演算法做為memetic演算法的區域性搜尋演算法。下面首先給出鄰域的概念。
給定兩個解和，它們間的距離為
1)本文採用1變換鄰域，鄰域內的解與當前解最多只有乙個變數的取值不同，即：
2)變數的增益為翻轉後的適應度函式值與當前解的適應度函式值的差，即3)
其中。在鄰域搜尋時，該禁忌搜尋演算法從自由的變數(不在禁忌列表)中選擇增益最大的變數翻轉。當某個變數被翻轉後，更新所有自由變數的增益，並禁止變數在後面的次迭代中再次翻轉。
若翻轉在禁忌列表中的某個變數能夠產生比當前最優解更好的解，則允許翻轉禁忌列表中的變數。經過一定數量(maxcount)的迭代後，該禁忌搜尋停止，返回整個禁忌搜尋過程中找到的最好的解。
禁忌長度是所有禁忌演算法中的乙個重要引數。本文通過種群中的資訊來動態更新禁忌的長度。用乙個整數變數來表示變數的禁忌長度。
表示變數可以自由翻轉。設種群，當變數翻轉後，由以下公式確定：
4)其中為引數，表示初始的禁忌長度。
2.3.2交叉運算元
交叉運算元是memetic演算法中的乙個重要運算元，用於產生新的解。新產生的解應該繼承種群中解的優良結構，同時應該具有一些新的結構，擴充套件新的搜尋空間。
美學複習題究極進化版
一 黑格爾在 美學 第3卷 中結合古希臘悲劇名作 安提戈涅 提出 基本的悲劇性就在於這種衝突中對立的雙方各有它那一方面的辯護理由，因此，雙方都在維護倫理理想之中而且就通過實現這種倫理理想而陷入罪過中。結合黑格爾的分析談談你對悲劇性的理解，分析中可結合你所熟悉的藝術作品，要求有理有據，切勿空言。黑格爾...
建築結構試驗試題究極版
一 單項選擇題 1.在觀測混凝土構件的裂縫時將測量儀交替布置在梁的受拉區段，如出現下列何種情形，則證明開始開裂。某一測點儀器讀數突然增大，相鄰測點儀器讀數可能變小 2.結構試驗中，常用科研性試驗解決的問題是 為發展和推廣新結構 新材料與新工藝提供實踐經驗 3.下列引數屬於結構動力反應指標的是 自振頻...
礦業專案盡職調查報告清潔版
中融 西北礦業股權收益權投資 一期 集合資金信託計畫 盡職調查報告 調查單位 中融信託機構業務部 調查日期 2010年10月 一 專案簡介 我公司擬發起設立中融 西北礦業股權收益權投資 一期 集合資金信託計畫，委託人基於對受託人的信任，自願將其合法擁有的並有權支配的資金交付給受託人。由受託人按照委託...