【21页】【毕业设计】遗传算法的特点及其应用.doc文档全文免费阅读
1、手机端页面文档仅支持阅读 15 页,超过 15 页的文档需使用电脑才能全文阅读。
它模拟生物进化过程中的繁殖现象,优良品种,即在匹配集中任选两个染色体称为双亲的染色体随机选择点或多点交换点位置,是染色体数字串的长度交换双亲染色体交换点右边的部分,即可得到两个新的下代染色体数字串。
也就是说,交换操作能够创造新的染色体子孙染色体,从而允许测试在搜索空间中的新点。
交换也体现了自然界中信息交换的思想。
请看下例例从匹配集中取出的对染色体为染色体染色体随机产生的点交换位置是,交换染色体,中第位右边的部分和,则得两个下代子孙染色体数字串染色体染色体变异变异运算用来模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变,它以很小概率随机地改变遗传基因表示染色体的符号串的位的值。
在染色体以二进制编码的系统中,它随机地将染色体的个基因由变成,或由变成。
若只有选择和交换,而没有变异操作,则无法在初始基因组合以外的空间进行搜索,使进化过程在早期就陷入局部解而终止进化过程,从而使解的质量受到很大限制。
通过变异操作,可确保群体中遗传基因类型的多样性,以使搜索能在尽可能大的空间中进行,避免丢失在搜索中有用的遗传信息而陷入局部解,获得质量较高的优化解答。
简单的遗传算法运算示例让我们从下面两个非常简单的例子来具体了解下简单遗传算法的各种操作。
虽然下面的例子都有更好处理方式,但为了深入了解遗传算法的各种操作,还是从简单的例子入手例计算机公司的经营策略优化问题个计算机公司追求的目标是最高的利润,为达此目标,必须选择适当的经营策略。
种可能的策略是对以下四个问题作出决策每台计算机的价格定为元低价还是元高价与机配套的免费软件是还是是否提供网络技术服务提供保修期为半年或是年下面用遗传算法来解决这个决策优化问题。
把问题的可能解表示为染色体数字串。
因为有四个决策变量,而每个变量只有两种选择,其取值可用或来表示,于是,可用四位的二进制数表示种可能的经营策略,解的搜索空间为,即共有种经营策略可供选择,表表示出了其中计算机公司经理已知的种经营策略初始解答。
表中数字串的第位取表示高价,表示低价第二位取表示,表示配套第三位取表示不支持网络技术服务,表示支持网络技术服务第四位取表示保修期为年,表示表示保修期为半年。
表问题的初始解答序号价格配套软件网络服务保修期染色体数字串高支持年高支持半年低不支持年高不支持半年求各染色体的适应度。
在这个问题中,我们不妨设染色体的适应度就是染色体的二进制数字串的数值,对应经营策略的利润。
表第代种群的适应度序号染色体串适应度适应度总和最坏适应度最好适应度平均适应度选择进入交换集的染色体由表可知,所有染色体串适应度的总和是,串的适应度是,占适应度总和的,也就是串被选中的机会接近两次串被选中的概率分别是。
按前述适应度比例法,选择进入交换集的染色体串及其适应度情况如表所示。
表第代种群选择后的适应度序号染色体串适应度适应度总和最坏适应度最好适应度平均适应度由表可知,选择操作的作用是改进了种群的平均适应度,使其由原来的提高到了,最坏适应度由原来的改进为,性能最差的染色体已从种群中删除。
但是,选择不能创造新的染色体,须进行交换操作。
交换操作设采用单点交换,随机产生的交换点是,从交换集中任取对染色体和,互换它们的第,位,得子孙染色体串和。
由此得到下代种群。
如表所示。
表第代种群的适应度序号染色体串适应度适应度总和最坏适应度最好适应度平均适应度估新代的种群的适应度由表可知,在新代第代种群中,最优染色体适应度由原来提高到了,其对应的二进制串是,表示种优化的经营策略。
平均适应度由原来的提高到,整个种群的适应度从总体上提高了,被优化了。
遗传算法重复地执行每代的运算操作,产生新的代,直到满足些终止标准或条件。
在本例中,假定已知染色体数字串代表的是已知的最好利润,则遗传算法停止运行。
例函数优化问题设有函数∈,∈求其在区间内的最大值。
下面用遗传算法求解这问题。
确定适当的编码,把问题的可能解表示为染色体数字串。
因为有个决策变量,其取值范围为,使用位无符号二进制数组成染色体数字串,即可表达变量,以及问题的解答方案。
选择初始种群。
通过随机的方法产生由个染色体数字串组成的初始种群,见表。
计算适应度值及选择概率。
此问题中染色体的适应度取函数自身。
将每个染色体的计算出来,作为适应度值。
在此基础上计算选择概率。
选择进入交换集的染色体。
按适应度比例法,选择进入交换集的染色体串,如表。
可见,染色提和都被选择了次染色体被选择了次染色体没有被选择。
所选的个染色体被送到交换集,准备参加交换。
交换染色体。
首先对进入交换集的染色体进行随机配对,此例中是染色体和配对,染色体和配对。
接着随机确定交换位置,结果是第对染色体的交换位置是,第对染色体的交换位置是。
经过交换操作后表函数优化过程编号染色体值适应度目标函数选择概率实集合群体结果集合元素个数子集和,集合元素和,当前最优解的差距输入,初始化遗传算法适应度选择运算适应度复制数计算适应度适应度作变换计算交换部分差距若差异变大则不交换交换变异运算染色体基因是否满足结束条件交换变异输出主程序说明在子集和问题中,随机构造的数据基本上都能达到最优解,偶尔也会收敛到准最优解。
总体情况非常良好。
例问题源程序输入文件输出文件城市最大值染色体个数遗传概率结束条件无通路邻接矩阵染色体结果城市个数当前最短路径长度输入初始化贪心,构造初始群遗传算法适应度选择变异输出主程序说明由于问题本身就是个问题。
对于随机构造的数据,无从知道最优解,而且由于随机性,最优解与局部最优解的差距不会非常明显,虽然差距不明显,但是可能路线截然不同。
因此,可能会收敛到局部最优解。
而人为构造的数据,最优解有较明显的区别时,般可以收敛到最优解。
参考文献邵军力张景魏长华人工智能基础电子工业出版社傅清祥王晓东算法与数据结构电子工业出版社吴文虎王建德实用算法的分析与程序设计电子工业出版社遗传算法的特点及其应用上海复旦大学附属中学张宁关键词摘要正文遗传算法的基本概念简单的遗传算法选择交换变异简单的遗传算法运算示例计算机公司的经营策略优化问题函数优化问题遗传算法应用举例子集和问题旅行商问题结束语附录子集和问题源程序旅行商问题源程序参考文献关键词遗传算法遗传变异染色体基因群体摘要遗传算法是基于达尔文进化论,在计算机上模拟生命进化机制而发展起来的门新学科。
它根据适者生存,优胜劣汰等自然进化规则来进行搜索计算和问题求解。
文章的第部分介绍了遗传算法的基本概念。
第二部分介绍了遗传算法的原理以及三种运算选择交换变异。
第三部分着重介绍三种运算的具体实现,以及简单实例,主要体现遗传算法的实现过程。
第四部分介绍了两个具体问题,都是属于完全问题,如何用遗传算法来解决,以及实现时的些基本问题。
文章在介绍遗传算法的原理以及各种运算的同时,还分析了些应用中出现的基本问题,对于我们的解题实践有定的指导意义。
正文遗传算法作为门新兴学科,在信息学竞赛中还未普及,但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题,特别是优化问题,提供了个行之有效的新途径,且能够较好地解决信息学竞赛中的难题,因此值得我们进行深入的讨论。
要掌握遗传算法的应用技巧,就要了解它的各方面的特点。
