下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 APS算法分析之五基因算法

APS算法分析之五基因算法.doc

APS算法分析之五基因算法

li51850000
2012-01-03 0人阅读 举报 0 0 暂无简介

简介:本文档为《APS算法分析之五基因算法doc》,可适用于生产运营领域

APS算法分析之五基因算法基因算法GA(GeneticAlgorithm)是基于自然系统的进化过程算法创立一初始化方案的人种基于初始化方案,算法再产生新的一个人种通过许多代的连续过程方案的质量被改善算法结束于当达到一特别的中断规则(如当加工时间已经达到)它实际上是随机搜寻算法。 它已经用于许多优化问题如销售员旅行问题货柜包装问题排程问题顺序问题设施布局问题等。 和本地搜索策略不同的是GA和Tabu搜索(TS)在搜索中比较一最较差的目标函数值接受临时的方案来克服本地优化找到全局优化。然而因为GA和TS是探索法可能不是最佳的方案但是大部分情况下至少可以找到一个非常好可行的方案。 GA是随机搜寻算法因为用较差目标函数值的方案用特别的可能性是可以接受的。因此用一个一样的初始方案开始和一样的参数设置也可能导致不同的方案。而用确定性搜索算法如TS就会导致同样的方案。 基本概念:人种保持在内存为进一步改善的一列数字集新列数字使用特别的基因运作产生。选择是根据它们的适应性来选择出“父代”基本基因运作:·复制·交叉·变异一人种的数字串选择可以用一特别的数字串的进化函数产生后一代。进化函数反映染色体的“适应”。比如:在车间流水线排序问题·N任务必须在M机器排程·每一任务包含m工序·每一工序需要不同的机器·所有任务在同样的加工订单上处理特别假设:                      所有任务在零时间可以得到                      工序的准备时间包含在加工时间里                      对所有机器所有工序的顺序已定义                      目标:最小化时间跨度适应函数:对一人种的目标函数值的所有成员如计算跨度。从这个较低的跨度被决定和得到最高的适应值fmax从不同的人种结果中的每一成员的适应值到它的前辈的索引清单中的适应值。这个作法就保证了为一较低跨度的排程选择的可能性是高的。缩减规模d影响到选择的可能性。必须的条件是:fmin>适应值(用fmax=,d==>fmin=):*f()=*f()=*f()=*f()=*整个人种的适应值:(在人种里的所有个体的适应合计) 复制选择·大部分公用的复制选择概率是给定的。是排列的适应值和共计种群的适应值的商·我们的案例,我们得到*概率()==*概率()==*概率()==*概率()==在下一代里保留一个复制操作者选择的机会。它是成比例列出适应。就像排列的选择如一个孩子一个父亲。用较低跨度排列比那些用低的适应值有一较高生存选择可能性。那么(,)随机变量产生如果低于,那么排列选择如果在和,之间那么被选择。如果在和之间,那么被选择如果大于,那么排列被复制。交叉·选择两个父项结构从选择的个体中·产生一二进制串m长度·对子项:拿所有父项的位置在二进制串里用“”对子项:拿所有父项的位置在二进制串里用“”·父项的其它因素被存作为在父项里出现时。然后他们被插入子项的自由位置。对子项也是同样的过程。例如:·选择(父项)和(父项)·二进制字串:·子项:子项:·子项:子项:有许多不同交叉操作者。这里“基于同样订单的交叉”被显示。父项:>在父项出现:父项:>在父项出现:变异选择一个体的父项选择随机两个位置在这个父项排列中在这个间隔里的新顺序值是随机产生的。如父项:两个位置:和老的顺序:>新顺序:=>新排列:GA的优势:·基于在排序里的高性能·专注于排程问题(没有太多的基于限制的约束)APS的GA:主要应用在生产计划与详细排程可以产生唯一可行的方案。最小化时间和优化排序(目标:最小化冲突)。

VIP免券下载文档

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/6

APS算法分析之五基因算法

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利