精华内容
下载资源
问答
  • 模拟二进制交叉算子详解

    千次阅读 多人点赞 2019-10-12 15:13:48
    一起来学演化计算-SBX(Simulated binary crossover)模拟二进制交叉算子详解 觉得有用的话,欢迎一起讨论相互学习~Follow Me 参考文献 衷心感谢武汉科技大学张凯教授的精心培育和指导 交叉算子cross operator 交叉...

    一起来学演化计算-SBX(Simulated binary crossover)模拟二进制交叉算子详解

    觉得有用的话,欢迎一起讨论相互学习~

    我的微博我的github我的B站

    参考文献
    衷心感谢武汉科技大学张凯教授的精心培育和指导
    以下内容包含老师授课内容,欢迎大家报考武汉科技大学计算机科学与技术学院信息安全系

    交叉算子cross operator

    • 交叉算子和变异算子的区别在于,交叉算子 必须从两个或以上子代中继承到有用的遗传物质 否则只能称为是某种变异算子。
    • 重组/交叉算子的设计应考虑其表示形式,使重组不总是灾难性的。
    • 重组应产生有效的染色体

    Introduction

    • SBX是模拟二进制编码的遗传算法中的单点交叉 ,对于后者简单示意图如下图所示:

    交叉前后解码实数值的平均相等

    p1+p22=c1+c22\frac{p_1+p_2}{2}=\frac{c_1+c_2}{2}

    交叉前后解码实数值差的商略等于1

    • 思想即为子代会离其父代较近(传播因子β\beta定义为子女与父母之间距离的比值)
    • Spread Factor β=c1c2p1p2\beta=|\frac{c_1-c_2}{p_1-p_2}|

    但是Spread Factor也会大于或者小于1或者等于1


    • 基于此,考虑一个长度为15的二进制编码的个体,之间随机挑选所有可能的分割位点进行单点变异后的子代和父代计算的β\beta数值

    Proposed methods

    • 针对使用二进制编码的单点交叉具有的Average Property 和 Spread Factor Property ,使用概率密度函数的方式在实数中也对此进行模拟。 --使用实数进行操作有效的避免了
    • Hamming cliffs汉明悬崖 即10000和01111(二进制) 16和15在10进制中看似只相差一位,但是如果使用二进制表示的单点变异需要同时改变5位
    • fixed precision固定精度 二进制表示十进制数通过位数表示精度,即如果需要表示的小数点后的位数增加,则使用的二进制编码长度也增加
    • bound variables有界变量 对于固定长度的染色体,其能表示的变量范围是有界限的,超出长度的部分表示不出
    • Average Property 解码后的平均值是守恒的
    • Spread Factor Property 子代的差和父代的差的比表示为传播因子,这个值大致等于1

    反解出子代

    根据

    1. c1+c2=p1+p2c_1+c_2=p_1+p_2
    2. c1c2p1p2=β|\frac{c_1-c_2}{p_1-p_2}|=\beta
      ==>
      c1=1/2(p1+p2)1/2β(p2p1)c_1=1/2(p_1+p_2)-1/2\beta(p_2-p_1)
      c2=1/2(p1+p2)+1/2β(P2p1)c_2=1/2(p_1+p_2)+1/2\beta(P_2-p_1)
    • 如果能够随机生成不同的β\beta,那么就能根据父代生成不同的子代

    通过概率密度函数拟合β\beta

    • 更大的分布指标n意味着子代和父代更接近。
    • 通过概率密度求出分布函数

    总结

    展开全文
  • 交叉算子是遗传算法中最主要的遗传算子,对种群的搜索性能起着重要的作用。作者就维持种群多样性的角度,提出了有效交叉位置距和有效交叉点的概念,并分析了随交叉点位置不同一点交叉、两点交叉和一致交叉之间的关系...
  • 遗传算法一些交叉算子

    千次阅读 多人点赞 2020-09-07 12:13:01
    演化计算-遗传算法一些交叉算子(动画演示) 文章目录第二十章 遗传算法-史上最直观交叉算子(动画演示)20.1 单点交叉(Single-point crossover)20.2 两点交叉(Two-points crossover)20.3 多点交叉(Multi...

    演化计算-遗传算法一些交叉算子(动画演示)

    第二十章 遗传算法-史上最直观交叉算子(动画演示)

    遗传算法通过交叉算子来维持种群的多样性,应该说交叉算子是遗传算法中最重要的操作。针对不同的优化问题,有多种不同的交叉算子,今天将带领大家以动画的形式,直观地介绍不同交叉算子的原理。制作不易,感谢关注。

    20.1 单点交叉(Single-point crossover)

    单点交叉通过选取两条染色体,在随机选择的位置点上进行分割并交换右侧的部分,从而得到两个不同的子染色体。单点交叉是经典的交叉形式,与多点交叉或均匀交叉相比,它交叉混合的速度较慢(因为将染色体分成两段进行交叉,这种方式交叉粒度较大),然而对于选取交叉点位置具有一定内在含义的问题而言,单点交叉可以造成更小的破坏。
    在这里插入图片描述

    20.2 两点交叉(Two-points crossover)

    两点交叉是指在个体染色体中随机设置了两个交叉点,然后再进行部分基因交换。两点交叉的具体操作过程是:

    1. 在相互配对的两个个体编码串中随机设置两个交叉点;
    2. 交换两个个体在所设定的两个交叉点之间的部分染色体。
      在这里插入图片描述

    20.3 多点交叉(Multi-point crossover)

    多点交叉或称广义交叉,是指在个体染色体中随机设置多个交叉点,然后进行基因交换。其操作过程与单点交叉和两点交叉相类似。如果多点交叉只选择了一个交叉点,那么多点交叉就变成了单点交叉。
    在这里插入图片描述

    20.4 部分匹配交叉(Partially-matched crossover,PMX)

    部分匹配交叉保证了每个染色体中的基因仅出现一次,通过该交叉策略在一个染色体中不会出现重复的基因,所以PMX经常用于旅行商(TSP)或其他排序问题编码。
    PMX类似于两点交叉,通过随机选择两个交叉点确定交叉区域。执行交叉后一般会得到两个无效的染色体,个别基因会出现重复的情况,为了修复染色体,可以在交叉区域内建立每个染色体的匹配关系,然后在交叉区域外对重复基因应用此匹配关系就可以消除冲突。
    Step1:随机选择一对染色体(父代)中几个基因的起止位置(两染色体被选位置相同)。
    在这里插入图片描述

    Step2:交换这两组基因的位置。
    在这里插入图片描述
    Step3:做冲突检测,根据交换的两组基因建立一个映射关系,如图所示,以7-5-2这一映射关系为例,可以看到第二步结果中子代1存在两个基因7,这时将其通过映射关系转变为基因2,以此类推至没有冲突为止。最后所有冲突的基因都会经过映射,保证形成的新一对子代基因无冲突。
    在这里插入图片描述
    最终结果为:
    在这里插入图片描述
    动画效果如下:
    在这里插入图片描述

    20.5 均匀交叉(Uniform crossover)

    均匀交叉也称一致交叉,在均匀交叉中,两个染色体的索引i处的基因以交换概率pS进行交换。经验研究表明,均匀交叉比是一种更具利用性的方法,这样可以更好地搜索设计空间,同时保持良好的信息交换。
    在这里插入图片描述

    20.6 顺序交叉(Order Crossover,OX)

    在两个父代染色体中随机选择起始和结束位置,将父代染色体1该区域内的基因复制到子代1相同位置上,再在父代染色体2上将子代1中缺少的基因按照顺序填入。另一个子代以类似方式得到。与PMX不同的是,OX不用进行冲突检测工作(实际上也只有PMX需要做冲突检测)。
    Step1:与PMX相同,随机选择一对染色体(父代)中几个基因的起止位置(两染色体被选位置相同)。
    在这里插入图片描述
    Step2:生成一个子代,并保证子代中被选中的基因的位置与父代相同。
    在这里插入图片描述
    Step3:先找出第一步选中的基因在另一个父代中的位置,再将其余基因按顺序放入上一步生成的子代中。
    在这里插入图片描述
    动画效果如下:
    在这里插入图片描述

    20.7 基于位置的交叉(Position-based Crossover,PBX)

    在两个父代染色体中随机选择几个位置,位置可以不连续,将父代染色体1这些位置上的基因复制到子代1相同位置上,再在父代染色体2上将子代1中缺少的基因按照顺序填入。另一个子代以类似方式得到。PBX与OX的不同在于选取的位置可以不连续。
    Step1:随机选择一对染色体(父代)中几个基因,位置可不连续,但两染色体被选位置相同。

    在这里插入图片描述
    Step2:与OX的第二步相同,生成一个子代,并保证子代中被选中的基因的位置与父代相同。

    在这里插入图片描述

    Step3:也与OX的第三步相同,先找出第一步选中的基因在另一个父代中的位置,再将其余基因按顺序放入上一步生成的子代中。
    在这里插入图片描述
    动画效果如下:
    在这里插入图片描述

    20.8 基于顺序的交叉(Order-Based Crossover,OBX)

    在两个父代染色体中随机选择几个位置,位置可以不连续,先在父代染色体2中找到父代染色体1被选中基因的位置,再用父代染色体2中其余的基因生成子代,并保证位置对应,将父代染色体1中被选择的基因按顺序放入子代剩余位置中。另一个子代以类似方式得到。OBX与PBX相比,生成子代的“基础”基因来源不同,PBX来自被选中基因,OBX来自剩余基因。
    Step1:随机选择一对染色体(父代)中几个基因,位置可不连续,但两染色体被选位置相同。
    在这里插入图片描述
    Step2:先在父代2中找到父代1被选中基因的位置,再用父代2中其余的基因生成子代,并保证位置对应。
    在这里插入图片描述
    Step3:将父代1中被选择的基因按顺序放入子代剩余位置中。
    在这里插入图片描述
    动画效果如下:
    在这里插入图片描述

    20.9 循环交叉(Cycle Crossover,CX)

    在某个父代上随机选择1个基因,然后找到另一个父代相应位置上的基因编号,再回到第一个父代找到同编号的基因的位置,重复先前工作,直至形成一个环,环中的所有基因的位置即为最后选中的位置。用父代染色体1中选中的基因生成子代,并保证位置对应,最后将父代染色体2中剩余基因放入子代中。另一个子代以相同方式获得。CX的特点在于只需要随机选择一个位置即可得到多个交叉位置。
    在这里插入图片描述

    20.10 子路径交叉交叉(Subtour Exchange Crossover,SEX)

    在某个父代上选择1组基因,在另一父代上找到这些基因的位置,保持未选中基因不变,按选中基因的出现顺序,交换两父代染色体中基因的位置,一次生成两个子代。SEX的特点是只在一个染色体上选择基因的位置。
    在这里插入图片描述

    展开全文
  • 通过分析比较标准二进制交叉算子和标准十进制交叉算子的异同点,得出结论:交叉算子的实质是在父代个体的数值和所决定的“家族”中随机取值,因而其不能保证交叉操作后的子代个体优于父代个体,体现出盲目搜索的特点...
  • 模拟二进制交叉算子

    2021-03-31 16:30:51
    模拟二进制交叉算子

    模拟二进制交叉算子

    在这里插入图片描述

    展开全文
  • 用于多目标进化算法的基因级混合交叉算子
  • 提出一种应用于参数优化问题的引导交叉算子。该交叉算子利用父代染色体的适应值差异,引导交叉操作产生的子代向适应值高的父代倾斜,以产生高适应值的子代个体。对于连续函数,高适应值个体的邻域内也是高适应值的...
  • 阐述了基本交叉算子和交叉机理. 通过一个具体的工程应用———项目投资决策,对比和分析了同一 遗传算法在不同交叉算子作用下的性能,结果表明,依据置换群理论,算术交叉算子和线性序列交叉算子均可看 作多点交叉算子的...
  • 单亲交叉算子遗传算法混合策略思想,王颖慧,刘万军,本文主要针对遗传算法效率和收敛速度问题,提出了三种基于单亲的交叉算子,即单亲单对交叉、单亲双对交叉和单亲屏蔽字交叉。并将
  • 为优化生物多序列比对问题,降低计算难度,提高计算效率,采用遗传算法模拟多序列比对,构造了四种简单的交叉算子及三种后处理方式,分析交叉算子和交叉后处理方式对多序列比对结果的影响。通过实验比较,结果表明多行横向...
  • 基于反学习和正交交叉算子的元胞差分进化算法
  • 为了更有效地处理建筑块,提出有导向的交叉算子。首先反复运行快速演化算法找到多个局部最优解,然后识别这些局部最优解中的重要基因位,将其标识为潜在的建筑块,然后应用有导向的交叉算子,组合父代中的建筑块。...
  • 多父辈遗传算法交叉算子研究多父辈遗传算法交叉算子研究多父辈遗传算法交叉算子研究多父辈遗传算法交叉算子研究
  • 为提高多星测控调度问题简单遗传算法的搜索精度,设计一种基于局部分层路径搜索的交叉算子(local layering path-relinking crossover operator,LLPRCO)。分析多星测控调度问题的遗传算法编码特点,得出解空间的复杂...
  • 交叉算子是遗传算法中的一种重要算子,本文首先对遗传算法中较成熟的交叉算子进 行了简单介绍,在此基础上结合文献内容, 从理论应用以及作用机理等几个方面对遗传算法 中改进的交叉算子进行了分析和讨论, 可以...
  • 遗传算法中几种交叉算子小结

    万次阅读 多人点赞 2017-01-16 15:24:18
    遗传算法中几种交叉算子的计算方法小结,PMX OX PBX OBX CX SEX

    (图片例子来自上课时老师的PPT,不过老师说PPT是他从网上组合的,所以没有出处)

    1、Partial-Mapped Crossover (PMX)
      过程:
        第一步,随机选择一对染色体(父代)中几个基因的起止位置(两染色体被选位置相同):

        第二步,交换这两组基因的位置:

        第三步,做冲突检测,根据交换的两组基因建立一个映射关系,如图所示,以1-6-3这一映射关系为例,可以看到第二步结果中子代1存在两个基因1,这时将其通过映射关系转变为基因3,以此类推至没有冲突为止。最后所有冲突的基因都会经过映射,保证形成的新一对子代基因无冲突:

        最终结果:

       

    2、Order Crossover (OX)
      过程:
        第一步,与PMX相同,随机选择一对染色体(父代)中几个基因的起止位置(两染色体被选位置相同):


         第二步,生成一个子代,并保证子代中被选中的基因的位置与父代相同:


        第三步(可再分两小步),先找出第一步选中的基因在另一个父代中的位置,再将其余基因按顺序放入上一步生成的子代中:
      需要注意的是,这种算法同样会生成两个子代,另一个子代生成过程完全相同,只需要将两个父代染色体交换位置,第一步选中的基因型位置相同,本例中的另一个子代为:254913678
      与PMX不同的是,不用进行冲突检测工作(实际上也只有PMX需要做冲突检测)。
     
    3、Position-based Crossover (PBX)
      过程:
        第一步,随机选择一对染色体(父代)中几个基因,位置可不连续,但两染色体被选位置相同:

        第二步,与OX的第二步相同,生成一个子代,并保证子代中被选中的基因的位置与父代相同:

        第三步,也与OX的第三步相同,先找出第一步选中的基因在另一个父代中的位置,再将其余基因按顺序放入上一步生成的子代中:

      与上俩个算法不同的是,选择的基因型位置可以不连续,出来这一点外与OX基本一致,同样有两个子代,本例的另一个为:243519678。 
     
    4、Order-Based Crossover (OBX)
      过程:
        第一步,随机选择一对染色体(父代)中几个基因,位置可不连续,但两染色体被选位置相同:

        第二步(分为两小步),先在父代2中找到父代1被选中基因的位置,再用父代2中其余的基因生成子代,并保证位置对应:

       第三步,将父代1中被选择的基因按顺序放入子代剩余位置中:

      同理,交换父代1、2可得到另一个子代(被选择基因的位置不变),本例结果为:423156798。
      OBX与PBX相比生成子代的“基础”基因来源不同一个来自被选中基因,一个来自剩余的,此外思想基本相似。 

    5、Cycle Crossover (CX)
      过程:
        第一步,在某个父代上随机选择1个基因,然后找到另一个父代相应位置上的基因编号,再回到第一个父代找到同编号的基因的位置,重复先前工作,直至形成一个环,环中的所有基因的位置即为最后选中的位置:


        第二步,用父代1中选中的基因生成子代,并保证位置对应:

        第三步,将父代2中剩余基因放入子代中:

      与上述算法不同的是,仅需要在一个染色体上随机选择一个位置;本例另一个子代结果为:543926781。

    6、Subtour Exchange Crossover
      过程:
        第一步,在某个父代上选择1组基因,在另一父代上找到这些基因的位置:

        第二步,保持未选中基因不变,按选中基因的出现顺序,交换两父代染色体中基因的位置,一次生成两个子代:

      与上述算法不同的是,只在一个染色体上选择基因的位置。

    展开全文
  • 实数编码遗传算法中交叉算子的研究与改进,王巍,彭力,为了克服实数编码遗传算法进化过程易于停滞的缺点,从个体以及种群的平均适应度两个方面,对常用的中间重组交叉算子进行了详细的
  • 该算法的核心在于,一方面通过父子竞争保留优秀个体和改进型交叉算子保证收敛性,另一方面对参与交叉的基因段进行基于海明距离相似度检测提高交叉操作的有效性;最后,采用基于基因位多样度的自识别高变异率算子来...
  • 交叉算子 单点交叉 双点交叉与多点交叉 均匀交叉 算数交叉 变异算子 基本位变异 均匀变异 边界变异 非均匀变异 高斯变异 遗传算法的运行参数 (1)编码串长度lll (2)群体大小MMM (3)交叉概率PcP_cPc​ (4)变异...
  • 关于遗传算法中的permutation coding问题的交叉算子种类介绍见文章 Inver-over 算子1998:Inver-over 算子可以看作是GA中交叉和变异的混合方法 Inver-over步骤: 随机初始化种群P 如果没达到temination,对...
  • 改进的自适应交叉算子、变异算子,实现遗传算法
  • Roberts交叉算子程序实例 from PIL import Image, ImageFont import numpy as np import matplotlib.pyplot as pyplot import pylab im =Image.open(‘Bikesgray.jpg’)#记得要用灰度图,如果是彩色图需要转换成灰度...
  • 交叉算子的自适应量子粒子群优化算法,陈琳,肖波,聚类分析是数据挖掘中一个很活跃的研究领域,其核心目标是将待处理对象的集合在相似的基础上分成多个类。随着研究的深入,新的聚
  • 贪婪交叉算子 function r=crossover(p,n,k,x,y) r1=randperm(k,1); r2=randperm(k,1); while r1r2 r2=randperm(k,1); end l1=p(r1,:); l2=p(r2,:); r=randperm(n); for p1=2:n r(p1)=0; end for p1=2:n m1=find(l1r...
  • 利用贪心策略和自适应交叉算子改进君主蝴蝶优化(MBO)。 此代码演示了 GCMBO 如何用于无约束优化(Ackley 函数),它可以轻松扩展以有效解决各种全局优化问题。 提供了两个版本: GCMBO_Generation_V1.m 用于固定...
  • 一起来学演化计算-SBX(Simulated binary crossover)模拟二进制交叉算子和DE(differential evolution)差分进化算子 觉得有用的话,欢迎一起讨论相互学习~Follow Me 参考文献 [1] ...
  • 文章目录第二十章 遗传算法-史上最直观交叉算子(动画演示)20.1 单点交叉(Single-point crossover)20.2 两点交叉(Two-points crossover)20.3 多点交叉(Multi-point crossover)20.4 部分匹配交叉(Partially-...
  • 图像边缘检测——Roberts交叉算子

    千次阅读 2013-11-25 21:05:32
    经典图像边缘检测(微分法思想)——Roberts交叉算子 如果我们沿如下图方向角度求其交叉方向的偏导数,则得到Roberts于1963年提出的交叉算子边缘检测方法。该方法最大优点是计算量小,速度快。但该方法由于是采用...
  • 部分匹配交叉规则是遗传算法中常用到的交叉算子运用频率最高的一种。 首先简述一下,部分匹配交叉规则的具体步骤: step1:从采用自然数编码的种群中,获取两条染色体,作为父代染色体; 如父代染色体1:【8, 4, 5, ...
  • 三种遗传算法的交叉算子:OX、PMX、CX 运行环境:Visual Studio 2019 源文件:.cpp文件 代码 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 995
精华内容 398
关键字:

交叉算子