没有合适的资源?快使用搜索试试~ 我知道了~
用遗传算法解决0-1背包问题概述(实用应用文).doc
需积分: 2 0 下载量 189 浏览量
2024-01-24
21:59:49
上传
评论
收藏 59KB DOC 举报
温馨提示
试读
38页
用遗传算法解决0-1背包问题概述(实用应用文).doc
资源推荐
资源详情
资源评论
用遗传算法解决0-1背包问题概述
文档信息
主题:
关于“IT计算机”中“数据结构与算法”的参考范文。
属性:
Doc-8FZLL8,doc格式,正文14604字。质优实惠,欢迎下载!
适用:
作为内容写作的参考文案,解决如何写作、正确编写文案格式、内容摘取等相关
工作。
目录
目录 .....................................................................................................................................1
正文 .....................................................................................................................................1
一、问题描述 .............................................................................................................3
二、遗传算法特点介绍: ............................................................................................3
实例1:.............................................................................................................................20
实例2:.............................................................................................................................20
实例3:.............................................................................................................................21
实例2:.............................................................................................................................22
实例3:.............................................................................................................................22
/*实例1*............................................................................................................................25
/*实例2*............................................................................................................................26
/*实例3*............................................................................................................................27
t=0;....................................................................................................................................37
正文
用遗传算法解决0-1背包问题概述
实现遗传算法的0-1背包问题
求解及其改进
姓名:
学号:
班级:
提交日期:2012年6月27日
实现遗传算法的0-1背包问题求解
研究了遗传算法解决0-1背包问题中的几个问题
1)对于过程中不满足重量限制条件的个体的处理,通过代换上代最优解保持
种群的进化性
2)对于交换率和变异率的理解和处理方法,采用逐个体和逐位判断的处理方
法
3)对于早熟性问题,引入相似度衡量值并通过重新生成个体替换最差个体方
式保持种群多样性。4)一种最优解只向更好进化方法的尝试。
通过实际计算比较表明,本文改进遗传算法在背包问题求解中具有很好的收敛
性、稳定性和计算效率。通过实例计算,表明本文改进遗传算法优于简单遗传算法
和普通改进的遗传算法。
1.基本实现原理:
一、问题描述
0-1背包问题属于组合优化问题的一个例子,求解0-
1背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一
般描述如下:
给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。
选择合适的物品装入背包,使得背包中装入的物品的总价值最大。注意的一点是,
背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时,对每
种物品i只有两种选择:装入背包或者不装入背包,即只能将物品i装入背包一次。
称此类问题为0/1背包问题。
其数学模型为:
0-
1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法
不能有效地解决0-1背包问题。遗传算法(Genetic
Algorithms)则是一种适合于在大量的可行解中搜索最优(或次优)解的有效算
法。
二、遗传算法特点介绍:
遗传算法(Genetic Algorithm,
GA)是1962年Holland教授首次提出了GA算法的思想是近年来随着信息数据量激
增,发展起来的一种崭新的全局优化算法,它借用了生物遗传学的观点,通过自然
选择、遗传、变异等作用机制,实现各个个体的适应性的提高。
基本遗传算法求解步骤:
Step 1
参数设置:在论域空间U上定义一个适应度函数f(x),给定种群规模N,交叉率P c
和变异率P m,代数T;
Step 2 初始种群:随机产生U中的N个染色体s1, s2, …, s
N,组成初始种群S={s1, s2, …, s N},置代数计数器t=1;
Step 3计算适应度:S中每个染色体的适应度f() ;
Step 4
判断:若终止条件满足,则取S中适应度最大的染色体作为所求结果,算法结束。
Step 5 选择-复制:按选择概率P(x
i)所决定的选中机会,每次从S中随机选定1个染色体并将其复制,共做N次,然后
将复制所得的N个染色体组成群体S1;
Step 6 交叉:按交叉率P
c所决定的参加交叉的染色体数c,从S1中随机确定c个染色体,配对进行交叉操作
,并用产生的新染色体代替原染色体,得群体S2;
Step 7 变异:按变异率P
m所决定的变异次数m,从S2中随机确定m个染色体,分别进行变异操作,并用产
生的新染色体代替原染色体,得群体S3;
Step 8 更新:将群体S3作为新一代种群,即用S3代替S,t=t+1,转步3;
遗传算法是一种仿生算法,
即模拟生命演化的算法,它从一个代表问题初始解的初始种群出发,
不断重复执行选择, 杂交和变异的过程,
使种群进化越来越接近某一目标既最优解,如果视种群为超空间的一组点,
选择、杂交和变异的过程即是在超空间中进行点集之间的某种变换,
通过信息交换使种群不断变化,遗传算法通过模拟达尔文“优胜劣汰,
适者生存”的原理激励好的结构, 同时寻找更好的结构,
作为一种随机的优化与搜索方法, 遗传算法有着其鲜明的特点。
—遗传算法一般是直接在解空间搜索,
而不像图搜索那样一般是在问题空间搜索, 最后才找到解(如果搜索成功的话)
—遗传算法的搜索随机地始于搜索空间的一个点集,
而不像图搜索那样固定地始于搜索空间的初始节点或终止节点,
所以遗传算法是一种随机搜索算法。
—遗传算法总是在寻找优解(最优解或次优解),
而不像图搜索那样并非总是要求优解,
而一般是设法尽快找到解(当然包括优解),
所以遗传算法又是一种优化搜索算法。
—
遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不
像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜
索, 适合大规模并行计算, 而且这种种群到种群的搜索有能力跳出局部最优解。
剩余37页未读,继续阅读
资源评论
omygodvv
- 粉丝: 504
- 资源: 2078
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功