基于粗糙集-遺傳算法的0-1背包問題求解.pdf

1、本論文主要進(jìn)行粗糙集和遺傳算法的理論研究，屬于智能信息處理和進(jìn)化計(jì)算學(xué)科的交叉范疇。論文在對粗糙集和遺傳算法進(jìn)行理論研究的基礎(chǔ)上，將粗糙集理論融入遺傳算法來求解0-1背包問題。即利用粗糙集分析遺傳進(jìn)化過程中產(chǎn)生的大量數(shù)據(jù)，發(fā)現(xiàn)重要基因位，并以此確定進(jìn)化的方向，從而對大規(guī)模背包問題進(jìn)行有效求解。
　　 0-1背包問題(Knapsack Problem，簡稱KP)是一個(gè)經(jīng)典的組合優(yōu)化問題，具有廣泛的實(shí)際應(yīng)用背景。生活中的許多問題都可

2、以用背包問題來描述，如資源分配、貨倉裝載、資金預(yù)算、存儲分配和項(xiàng)目選擇等都可以建模成背包問題，并且它還常常作為其他復(fù)雜組合優(yōu)化問題的一個(gè)子問題。但是當(dāng)背包問題規(guī)模過大時(shí)，如果想得到最優(yōu)解是極其困難的，因此開展對大規(guī)模0-1背包問題的研究具有重要的意義。
　　 以往解決背包問題的方法大體上可以分為兩類：精確算法和近似算法。由于精確算法在問題規(guī)模較大時(shí)，計(jì)算復(fù)雜性一般很大，因此在工程中往往不夠?qū)嵱?。而以遺傳算法(Genetic Al

3、gorithm，GA)為代表的近似算法雖然可以得到近似最優(yōu)解，但該算法在問題規(guī)模較大時(shí)容易早熟，得到的結(jié)果并不理想。
　　 針對以上問題，本文在前人研究經(jīng)驗(yàn)的基礎(chǔ)上做了進(jìn)一步的研究，將粗糙集(Rought Set，RS)的屬性化簡功能融入遺傳算法來求解0-1背包問題，以提高遺傳算法的搜索速度和解的質(zhì)量。
　　 本文主要做了以下工作：
　　 第一、論述了目前關(guān)于背包問題求解的各種算法，對這些方法的優(yōu)缺點(diǎn)進(jìn)行了比較和

4、總結(jié)，指出背包問題研究的發(fā)展趨勢。
　　 第二、對遺傳算法進(jìn)行了研究和分析，由遺傳算法的局限性引出了進(jìn)化算法研究的新方向——基于知識的混合進(jìn)化。
　　 第三、將粗糙集的屬性化簡功能融入遺傳算法(Rough Set in GA，RSGA)求解背包問題。利用粗糙集的屬性化簡功能找出背包問題中進(jìn)化求解的重要基因，并以此基因作為遺傳算法交叉操作的根據(jù)，利用這些確定的基因位引導(dǎo)GA的進(jìn)化方向。并將該算法在Matlab仿真平臺上進(jìn)行