基于粗糙集-遗传算法的0-1背包问题求解

《基于粗糙集-遗传算法的0-1背包问题求解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、太原理工大学硕士研究生学位论文基于粗糙集-遗传算法的0-1背包问题求解摘要本论文主要进行粗糙集和遗传算法的理论研究，属于智能信息处理和进化计算学科的交叉范畴。论文在对粗糙集和遗传算法进行理论研究的基础上，将粗糙集理论融入遗传算法来求解0-1背包问题。即利用粗糙集分析遗传进化过程中产生的大量数据，发现重要基因位，并以此确定进化的方向，从而对大规模背包问题进行有效求解。0-1背包问题（KnapsackProblem，简称KP）是一个经典的组合优化问题，具有广泛的实际应用背景。生活中的许多问题都可以用背包问题来描述，如资源分配、货仓装载、资金预算

2、、存储分配和项目选择等都可以建模成背包问题，并且它还常常作为其他复杂组合优化问题的一个子问题。但是当背包问题规模过大时，如果想得到最优解是极其困难的，因此开展对大规模0-1背包问题的研究具有重要的意义。以往解决背包问题的方法大体上可以分为两类：精确算法和近似算法。由于精确算法在问题规模较大时，计算复杂性一般很大，因此在工程中往往不够实用。而以遗传算法（GeneticAlgorithm，GA）为代表的近似算法虽然可以得到近似最优解，但该算法在问题规模较大时容易早熟，得到的结果并不理想。针对以上问题，本文在前人研究经验的基础上做了进一步的研究，

3、将粗糙集（RoughtSet，RS）的属性化简功能融入遗传算法来求解0-1背包问I太原理工大学硕士研究生学位论文题，以提高遗传算法的搜索速度和解的质量。本文主要做了以下工作：第一、论述了目前关于背包问题求解的各种算法，对这些方法的优缺点进行了比较和总结，指出背包问题研究的发展趋势。第二、对遗传算法进行了研究和分析，由遗传算法的局限性引出了进化算法研究的新方向——基于知识的混合进化。第三、将粗糙集的属性化简功能融入遗传算法（RoughSetinGA,RSGA）求解背包问题。利用粗糙集的属性化简功能找出背包问题中进化求解的重要基因，并以此基因作

4、为遗传算法交叉操作的根据，利用这些确定的基因位引导GA的进化方向。并将该算法在Matlab仿真平台上进行测试，实验结果表明该方法改变了遗传算法随机寻找交叉点的方式，提高了解的品质。关键词：粗糙集，约简，遗传算法，背包问题II太原理工大学硕士研究生学位论文SOLVING0-1KNAPSACKPROBLEMBASEDONROUGHSETTHEORYANDGENETICALGORITHMABSTRACTRoughSetTheory(RST)andGeneticAlgorithm(GA)aremainlyresearchedonthispaper，

5、itbelongstothecrossdisciplinesofcomputerscience，intelligentinformationprocess，andevolutioncomputing.Thisstudyembedsroughsettheoryintogeneticalgorithmanduses0-1knapsackproblemastestproblem.Roughsettheoryisusedtoanalyzetheknowledgeandinformationhiddeningeneticalgorithmproces

6、s，whichresultintherapiddiscoveryofimportantgenes，thenusedtodeterminetheevolutiondirection.0-1knapsackproblem(KP)isatypicalcombinatorialoptimizationproblem，whichhasverywidebackground.Manyproblemscanbedescribedbyknapsackproblem，suchasresourseallocation，warehouseloading，capit

7、albudget,storagedistributionandprojectselection，etc.Anditisoftenasasubproblemofothercomplexcombinatorialoptimizationproblems.However,forlargescale0-1knapsackproblem,peoplestillcannotfindtheperfectsolutionmethod.Itisextremelydifficulttogetthetheoptimalsolution.Therefore，iti

8、sasignificantworkofstudyingthelargescale0-1knapsackproblem.Inthepastthemethodstosolveknap