RPA百科-【数据结构与算法】用 Python 实现遗传算法(一)

222人参与 |分类: 研究中心|时间: 2019年11月01日

这里,我们用遗传算法求一个函数的最大值。

f(x)=10sin5x+7cos4x,x[0,10]


我们将求解过程分为以下几步:

  1. 将自变量 x 进行编码
    取基因片段的长度为 10, 则 10 位二进制位可以表示的范围是 0 到 1023。基因与自变量转变的公式是 x = b2d(individual) * 10 / 1023。编码方式为随机从 0 和 1 中选择十次并放在一个列表中。

  2. 计算目标函数值
    根据自变量与基因的转化关系式,求出每个个体的基因对应的自变量,然后将自变量代入函数 f(x),求出每个个体的目标函数值。

  3. 适应度函数
    适应度函数是用来评估个体适应环境的能力,是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成 0。因为我们求的是最大值,所以要使目标函数值是负数的个体不适应环境,使其繁殖后代的能力为 0。适应度函数的作用将在自然选择中体现。

  4. 选择
    使用轮盘赌算法。其具体步骤:
    假设种群中共 5 个个体,适应度函数计算出来的个体适应性列表是 fitvalue = [1 ,3, 0, 2, 4] ,totalvalue = 10 , 如果将 fitvalue 画到圆盘上,值的大小表示在圆盘上的面积。在转动轮盘的过程中,单个模块的面积越大则被选中的概率越大。选择的方法是将 fitvalue 转化为累加的和 [1, 4, 4, 6, 10], fitvalue / totalvalue = [0.1, 0.4, 0.4, 0.6, 1.0]。然后产生 5 个 0-1 之间的随机数,将随机数从小到大排序,假如是 [0.05, 0.2, 0.7, 0.8, 0.9],则将 0 号个体、1 号个体、4 号个体、4 号个体、4 号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。

  5. 交叉
    假设个体 a、b 的基因是
    a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
    b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
    这两个个体发生基因交换的概率 pc = 0.6。如果要发生基因交换,则产生一个随机数 point 表示基因交换的位置,假设 point = 4,则:
    a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
    b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
    交换后为:
    a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
    b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]

  6. 变异
    遍历每一个个体,假设基因的每一位发生突变(0 变为 1,1 变为 0)的概率 pm 为 0.001。突变可以增加解空间


来源:[jane小姐](微信/QQ号:1055692322),转载请保留出处和链接!

地址: