遗传算法探讨与改良.ppt

遗传算法探讨与改良,适应度共享法选择,基于表现型的交叉操作,3,形态学技术在演化硬件领域的应用,1,2,对于自适应遗传算法的改良,4,1,5,实验硬件及编码,olmc模块配置逻辑图,等效电路图,控制位流12*8,位流转换：12*86*8,软硬件仿真流程,与传统演化硬件比照,进化产生的电路,各电路的最小项,形态学技术在遗传算法领域的应用,演化硬件所使用的进化算法决定了它的性能，遗传算法就是一种普通的进化算法，但是遗传算法的搜索能力不太好，因为不能很好地维持种群的多样性。而且相似功能的硬件构造（由基因型决定）数目庞大，所以会有很多遗传算法谬误出现. 需要补充的是,尽管我们可以应用遗传算法找到与目标电路构造相似的电路,这也不能保证电路性能的相似度.这一因素导致了收敛时间加长,甚至遗传游走现象的产生.,形态学技术在遗传算法领域的应用,为了弥补遗传漂移现象导致的损失,人们发展了生态位方法.这些方法维持种群多样性并扩展了遗传算法的平行搜索域.同时避免了算法收敛于局部最优解. 生态位法基于自然生态系统的构造.自然界中有很多不同的物种,所谓物种是值拥有相似生物学特征的一群个体,物种中的个体相互杂交.生态资源被所有生态位共享. 在遗传算法的生态系统中，算法推动种群的进化,使好的个体存活下来.生态位通常被理解为某一区域的最适应条件,适应度则用于描述这一生态位的资源。物种则被定义为以相似度度量相似个体集合。近年来应用这种定义机制的多数生态为法也被称作形态学技术。,形态学技术在遗传算法领域的应用,形态学方法是指在种群中产生和维持多个物种。一些形态学算法限制具有相似个体的种群间的杂交，一些则对适应度进行操作以控制选择压力。尤其是后者应用一种叫做生态位法的步骤。本文中也用了一种生态位法，叫做适应度共享法。 适应度共享法的内容如下：如果某些相似个体适应度相通，那么它们在新种群的数量将被限制。 适应度共享法通过减小个体密集区的适应度的方法改变了搜索域。它以一个给定的大小减小了个体的适应度,形态学技术在遗传算法领域的应用,个体i的共享适应度计算方式如下,计算个体间的距离使用基因型和表现型两种方式.表达式如下:,形态学技术在遗传算法领域的应用,形态学技术在遗传算法领域的应用,在我们的实验种,染色体分八块,每块代表向olmc输入的一个最小项.每一块都有鲜明的特点. 我们用海明距离hk(i,j)表示第i和第j个个体中第k块基因间的距离.这样,海明距离hij就与个体间距dij联系起来了,这一联系是由基于欧几里德距离的表现型相似度构造.,传统遗传算法中选择的总体思想是轮盘赌式选择.这种选择过程为按适应度比例制造赌盘,进行n次n个个体选一的轮盘赌式选择,每个个体被选中的概率为si:,适应度共享法选择,适应度共享法选择,其中ps为选择概率,n是选作下一代母染色体的个体数.因为通过选择优秀个体的方式实现了基因进化,所以这种选择方式是遗传算法重要的一步.然而这一步骤会因选择了相似个体或不好个体而产生噪音,容易丢掉好基因而收敛于局部最优。 使用加权平均轮盘赌选择可避免这些问题。这里所推荐的方法改善了个体的选择概率，开辟了更具操作性的领域。个体赌盘中包含概率为si入口空间和概率为1-si的禁入空间，它们帮助决定选择。重复选择过程直到有n个个体被选中,在轮盘赌选择中，个体被选中的概率如下：,其中sfi为形态学遗传算法适应度。在这个公式中，si的值比传统算法中的略大，当染色体的适应度在种群中最大时其值可达到1,也就是该个体不可避免地被选中。 尽管传统轮盘赌式选择由适应度一步决定，而本文推荐的选择由两步完成：个体获得和选择， 在第一步中，个体被以相等的概率（ps）公平地选择,形态学改进算法流程,我们平等地运用了三种交叉方法，分别为单点交叉、均匀交叉和分块均匀交叉。 单点交叉的交叉点是随机的。 均匀交叉随机决定执行交叉的两条染色体的每一位是否交叉，这帮助基因快速混合。 分块均匀交叉是指改良了的统一交叉，它所交换的对象是基因块而非比特位。一条染色体有包含8个最小项信息和8位最小项加载信息，并且他们相互独立。分块均匀交叉与这些信息相关。,基因型,表现型,对于自适应遗传算法的改良,遗传算法的参数中交叉概率pc和变异概率pm的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性，pc越大，新个体产生的速度就越快。然而，pc过大时遗传模式被破坏的可能性也越大，使得具有高适应度的个体结构很快就会被破坏；但是如果pc过小，会使搜索过程缓慢，以致停滞不前。 对于变异概率pm，如果pm过小，就不易产生新的个体结构；如果pm取值过大，那么遗传算法就变成了纯粹的随机搜索算法。针对不同的优化问题，需要反复实验来确定pc和pm，这是一件繁琐的工作，而且很难找到适应于每个问题的最佳值。srinvivas等提出一种自适应遗传算法（adaptive ga,aga）,pc和pm能够随适应度自动改变。,对于自适应遗传算法的改良,当种群各个适应度趋于一致或者趋于局部最优时，使pc和pm增加，而当群体适应度比较分散时，使pc和pm减少。 同时，对于适应值高于群体平均适应值的个体，对应于较低的pc和pm，使该解得以保护进入下一代；而低于平均适应值的个体，相对应于较高的pc和pm，使该解被淘汰掉。 所以，自适应的pc和pm能够提供相对某个解的最佳pc和pm。自适应遗传算法在保持群体多样性的同时，保证遗传算法的收敛性。,传统自适应参数控制程式,对于自适应遗传算法的改良,对于自适应遗传算法的改良,交叉概率pc测试实验结果,几种改进遗传算法举例,矢量代数交叉算子 -基于遗传算法的无线传感器网络节点自身定位算法研究,再生算子h x、y为母代染色体z为子代,chc算法,第一个c代表跨世代精英选择（cross generational elitist selection）策略，h代表异物种重组（heterogeneous recombination），第二个c代表大变异（cataclysmic mutation） （1）通常，遗传算法是依据个体的适应度复制个体完成选择操作的，而在chc算法中，上世代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体。这一策略称为跨世代精英选择。,（2）chc算法使用的重组操作是对均匀交叉的一种改进。均匀交叉对父个体位值的各位位置以相同的概率实行交叉操作，这里改进之处是：当两个父个体位值相异的位数为m时，从中随机选取m/2个位置，实行父个体位值的互换。显然，这样的操作对模式具有很强的破坏性，因此，确定一个阀值，当个体间的海明距离（hamming distance）低于该阀值时，不进行交叉操作。并且，与种群进化收敛的同时，逐渐地减少该阀值。 （3）chc算法在进行前期不采取变异操作，当种群进化到一定的收敛时期，从优秀个体中选择一部分个体进行初始化。初始化的方法是选择一定比例的基因座，随机地决定它们的位值。这个比例值称为扩散率，一般取0.35。,演化硬件按照评估载体的不同分为离线演化、在线演化。 离线演化是指在演化过程中每个个体的适应值都是通过软件仿真得到的,只有最终的个体才下载到芯片中去以验证其功能性; 在线演化是指在演化过程中的每个个体都下载到芯片,由芯片来计算其适应值,并将适应值返回给演化算法。 在线演化按照演化算法的实现载体不同又可以分为两种:一种是指演化算法在pc 上运行,芯片只负责评估个体的适应值;另外一种是指演化的整个过程包括演化算法都在fpga 芯片上面运行,为了和前一种情况区分开来,称之为“在片演化”,基于演化硬件的自适应系统,基于演化硬件的自适应系统,原有的电子系统是指正在运行的电子系统,它可以是人工预先设计好的电子系统,也可以是通过演化硬件系统产生的电子系统 外部环境的干扰或者系统内部的故障都可能使它不能正常工作; 新的电子系统是每一次执行演化硬件技术后产生的最优的电子系统,当新系统满足期望要求时将替代原系统; 演化硬件系统是整个系统的核心部分 实时监控系统负责实时检测整个系统是否正常工作,并产生控制信号。,实验环境 程序语言:c(vc + + ) ,v hdl , 仿真软件:modelsim6. 0 , 综合软件: xil inx ise8. 2 , 母板:amd2xpl , fpga 芯片: xil inx virtex2ii pro (xc2vp20) 。 母板通过pci 插槽与pc 向连,应用程序通过sdk提供的接口函数(c 语言描述) 可以方便地与芯片进行交互。,生态位（ecological niche)是指一个种群在生态系统中，在时间空间上所占据的位置及其与相关种群之间的功能关系与作用。 生态位又称生态龛。表示生态系统中每种生物生存所必需的生境最小阈值,因此又称小生境。 后人引申了确定该种生物在其群落中机能作用和地位的内容，并主要强调该生物体对其它种的营养关系。 事实上生态位可以抽象为一组约束条件，表征物种生存进化所处的自然资源 在特定生态环境中赢得竞争的胜利者，是能够最有效地利用食物资源和生存空间的种，其种群以出生率高、死亡率低而有较快的增长。,1957年，g.e.哈钦森建议用数学语言、用抽象空间来描绘生态位。 例如，一个物种只能在一定的温度、湿度范围内生活，摄取食物的大小也常有一定限度 如果把温度、湿度和食物大小3个因子作为参数,这个物种的生态位就可以描绘在一个三维空间内； 如果再添加其他生态因子,就得增加坐标轴，改三维空间为多维空间,所划定的多维体就可以看作生态位的抽象描绘，用多维空间描述生态位有助于概念的精确化。 但实际工作中只能对少数几个，通常只是一两个生态因子作定量分析。,生态位重叠 生物群落中，多个物种取食相同食物的现象就是生态位重叠的一种表现，由此造成物种间的竞争，而食物缺乏时竞争加剧。（显然这里只选用了一维生态因子：食物） 生态位重叠与物种竞争密切相关，因此生态位概念是竞争排除原理的重要根据。,可见生态位重叠概念的引入旨在描述自然界中种内的竞争现象。 基于生物进化理论的遗传算法又是如何体现这一问题的呢？ 1987 年，goldberg 和richardson 提出了一种基于适应值共享机制的小生境技术，通过定义群体中个体的共享度，采用适应值非线性标度变换调整个体的适应值，使得群体同时保持多个高阶模式，使之能够搜索到全部全局最优解和尽量多的局部最优解，提高种群的多样性。,参考词汇 speciati