利用遗传算法求解Ackley函数

利用遗传算法对Ackley函数求解，

张鱼小丸子er

4875人浏览 · 2022-04-18 19:26:37

张鱼小丸子er · 2022-04-18 19:26:37 发布

利用遗传算法求解Ackley函数，python源码

问题重述

问题重述

Ackley’s函数求解：
不想敲字了，直接贴图

遗传算法简介

遗传算法（GA）可能是最早开发出来的模拟生物遗传系统的算法模型。它首先由Fraser提出，后来有Bremermann和Reed等人再次提出。最后，Holland对遗传算法做了大量工作并使之推广，因此被认为是遗传算法的奠基人。遗传算法模拟了基因进化，在这个模型中，个体的性状通过基因型表达。选择算子（模拟适者生存）与交叉算子（模拟繁殖），是遗传算法的主要驱动算法。

遗传算法的基本运算过程

A)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
B)个体评价：计算群体P(t)中各个个体的适应度。
C)选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
D)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。
E)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
F) 终止条件判断：若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
在这里插入图片描述

（实验开始）初始化种群

利用matplotlib画出目标函数图像，如下图：
在这里插入图片描述
由图像可以看出，函数最小值位于原点左右，因此在选取父代（初始群种）时，利用Python中的random库在区间[-5，5]生成100个个体，每个个体拥有两条“染色体”：x1和x2。
父代染色体如下：（直接粘贴图了）
在这里插入图片描述

编码

本题采用实数编码。实数编码时将染色体编码为一定长度的实数串，其中v时编码后的染色体，x为实值。在本题目中只有两个变量，因此：v=[v1,v2] 。
由于实数编码后的染色体没有数值上的变化，与上表格相同，此处不再展示。

最好种群选择

对于要求解的函数，因为目标函数值均为正值，但考虑到求解的是最小化问题，所以应将目标函数值取反并加上一个合适的正常数c以产生适应度函数，所以适应度函数应该具有如下形式：
eval（v)=-f(v)+c
同时要求，适应度函数要针对输入可计算出能加以比较的非负结果，所以将c选取为当前代中的最大值，即。这样就可以保证适应度输出值为非负结果。
利用这个适应度函数来计算父代中每个个体的适应度，如下：
1 3.853986090190822,
2 8.040955440645641,
3 3.1722464019070093,
4 10.686184774384285,
5 1.3326486157167714,
6 4.144700102236256,
7 2.5227261247543007,
8 4.157790543239311,
9 2.919876472609343,
10 4.033638408919372
… …
99 7.552930151867396
100 2.3567321942187993

计算选择概率。
总适应度 :选择概率 :

根据上述公式计算得父代总适应度： =402.6832400460793
父代每个个体的选择概率：
p1 =0.009482108970339104, p2 =0.01978346935602664,
p3 =0.007804798813417376, p4 =0.026291627975977817,
p5 =0.0032787662170239767, p6 =0.010197363742128589,
p7 =0.006206759302563395, p8 =0.010229570653403302,
p9 =0.007183883450871591, p10 =0.009924114422121587,
…
p99 =0.01858276212455674, p100 = 0.005798358104188846。

计算累积概率
累积概率：

根据公式得到：
q1=0.009482108970339104, q2 =0.029265578326365744,
q3 =0.03707037713978312, q4 =0.06336200511576093,
q5 = 0.0666407713327849, q6 =0.0768381350749135,
q7 =0.08304489437747682, q8 =0.09327446503088013,
q9 =0.10045834848175172, q10 =0.11038246290387331,
…
q99 =0.9942016418958112, q100 =1.0
随机生成100个[0,1]内的数，将生成的数与累计概率相对比，应用轮盘选择的方法依次选择出100个个体。
最终选择的个体如下:
1 -0.07621521612081139 -0.6742031796393508
2 -3.9303527302336705 1.2260729085048974
3 -0.9491544035064328 -0.6744469396950157
4 -2.89641287243521 -1.3185740526328305
5 -0.2893919123161893 0.6358455585724236
6 4.715678158120841 1.2510654003704493
7 -4.146832843227334 3.3155944329081173
8 0.925816059994613 -1.3265651368553124
9 2.6386097472471732 -1.906926412442309
10 1.4911043493944511 -1.6296310633960207
… … …
99 -1.2895980006705763 0.5825305932983147
100 2.6386097472471732 -1.906926412442309

##交叉
本题采用的算术交叉。算术交叉定义为两个染色体和的线性组合
交叉概率： 0.8
因此在本仿真过程中，父代中每个个体都有如此的80%的几率与其他个体进行结合。交叉后每个个体的染色体具体情况如下：
1 -4.935817051361072 -0.5473890037374529
2 0.886698557175071 -4.025723051521496
3 -2.871443207578035 1.1480228663177696
4 1.905099186777482 -2.0113747777332085
5 2.341541866233275 -1.6899630445274103
6 -2.5480582881830047 -3.7960382594751207
7 0.5411529678459847 3.0560248303085427
8 1.3686639822405864 -3.9186821182261946
9 0.381454985085785 0.35542239414914356
10 0.8387623109931608 -3.4042066155530852
… … …
99 2.518747731766003 -3.947435088128432
100 2.06234887973105 -1.6509870652198109

变异

变异采用非一致性变异。对于给定的父代个体v，若其第k个元素被选定进行变异，在这里插入图片描述

在这里插入图片描述
变异后的种群染色体情况如下：

1 -4.935817051361072 -0.5473890037374529
2 0.886698557175071 -4.025723051521496
3 -2.871443207578035 1.1480228663177696
4 1.905099186777482 -2.0113747777332085
5 2.341541866233275 -1.6899630445274103
6 -2.5480582881830047 -3.7960382594751207
7 0.5411529678459847 3.0560248303085427
8 1.3686639822405864 -3.9186821182261946
9 0.381454985085785 0.35542239414914356
10 0.8387623109931608 -3.4042066155530852
… … …
99 2.518747731766003 -3.947435088128432
100 2.06234887973105 -1.6509870652198109
由列表可以看出，因为变异概率为0.03，特别小。因此在这一代并没有产生变异的染色体。

迭代1000次后结果

在这里插入图片描述
并制成表格数据：
第n代最小值
1 0.010428896812090915
2 0.010428896812090915
3 0.005339717195309124
4 0.006034887075351936
······
997 0.004196407810017622
998 0.004196407810017622
999 0.004196407810017622
1000 0.004196407810017622

观察发现，最终在第三百多代的时候能够收敛，最小值收敛在0.004左右，此时求得的最优解与最有目标函数值均与理想值十分接近。

实验验证

为验证算法的准确性，选择不同初始化种群进行多次仿真实验，得到以下几张图：

在这里插入图片描述

由上图发现，最后一张图收敛速度比较快，可能由于在初始化种群时候，种群多样性太小，并且选择随机性太强而导致。

总结

1、种群初始化如果多样性太小，那么收敛的速度可能过快，可以通过增加种群个数，或者提高变异和交叉概率，来改善收敛速度过快的问题。
2、多次仿真实验证明：经过迭代1000代后，发现最终种群个体基本收敛在：v=[0.000004,-0.000035] .与理想值基本接近。
代码奉上：

import numpy as np
import random
import matplotlib.pyplot as plt
import matplotlib as mpl
import math

#种群参数设置
popsize = 100   #种群个数
pc = 0.8           #交叉概率
pm = 0.03           #变异概率
maxGen = 1000       #最大跌代次数

pi = np.pi
e = np.e


#目标函数
def Ackley(nums: list):
    x = nums[0]*pi*2.0
    y = nums[1]*pi*2.0
    x1s = np.power(nums[0], 2)
    x2s = np.power(nums[1], 2)
    sum1 = np.cos(x) + np.cos(y)
    num1 = np.sqrt(0.5 * (x1s + x2s))
    num2 = np.exp(-0.2 * num1)
    num3 = np.exp(0.5 * sum1)
    ans = -20 * num2 - num3 + 20 + e
    return ans


#初始化种群
def original(num: int):          #输入种群数量
    generation = []
    for i in range(num):
        x = np.random.uniform(-5, 5)
        y = np.random.uniform(-5, 5)
        generation.append([x, y])
    generation = list(generation)
    return generation


#目标函数求解
def target(nums: list):  #计算目标值
    adoption = []
    for j in range(len(nums)):
        add = Ackley(nums[j])
        adoption.append(add)
    adoption = list(adoption)
    return adoption


#适应度函数
def evaluate(nums: list):
    adoption_op = []
    a = target(nums)
    c = max(a)
    for i in range(len(nums)):
        asd = c - Ackley(nums[i]) + 0.000001
        adoption_op.append(asd)
    # max_num = max(adoption_op)
    # min_num = min(adoption_op)
    # for i in range(len(adoption_op)):               #归一化处理，防止未成熟收敛
    #     adoption_op[i] = (adoption_op[i] - min_num + 0.1)/(max_num - min_num + 0.1)
    # # c = max(adoption_op)
    # # for j in range(len(adoption_op)):
    # #     adoption_op[j] = c - adoption_op[j] + 0.000001
    return adoption_op


#计算选择概率
def cacu_choice(nums: list):
    choice_pro = []
    adoption = np.sum(nums)
    for i in range(len(nums)):
        aw = nums[i] / adoption
        choice_pro.append(aw)
    return choice_pro


#计算累积概率
def cacu_accumulate(nums: list):
    choice_prob = []
    accumulated_prob = []
    adoption = np.sum(nums)
    for i in range(len(nums)):
        aw = nums[i] / adoption
        choice_prob.append(aw)
        ax = np.sum(choice_prob)
        accumulated_prob.append(ax)
    return accumulated_prob             #返回累计概率


#轮盘赌选择个体
def roulette(nums1: list, nums2: list):    #累积概率，父代，随机数
    choice = []
    nums1 = [0] + nums1
    nums1_ = nums1
    for i in range(len(nums2)):  # 轮盘赌选择
        DI = 0
        SI = 1
        RD = random.random()
        for j in range(len(nums2)):
            if SI <= len(nums2):
                if nums1[DI] <= RD < nums1_[SI]:  # 随机小数与适应度区间对比
                    choice.append(nums2[DI])
                    break
                else:
                    DI += 1
                    SI += 1
    return choice


#交叉
def cross(nums: list):
    copy_ = nums
    for i in range(len(copy_)):
        rand = np.random.uniform(0, 1)
        if 0 <= rand < pc:
            rand2 = np.random.randint(0, len(nums)-1)
            copy_[i] = np.add(np.dot(copy_[i], 0.9), np.dot(nums[rand2], 0.1))
    return copy_


#变异
def variation(nums: list, generation: int):
    for i in range(len(nums)):
        for j in range(2):
            rand = np.random.random()
            if 0 <= rand <= pm:
                r = 0.4
                gene_min = min(nums[i])
                dec_num = nums[i][j] - gene_min
                delta = dec_num * r * math.pow((1 - generation / maxGen), 4)
                nums[i][j] = nums[i][j] - delta
            else:
                continue
    return nums


def process(nums: list, number: int):   #每一代进行种群的选择，交叉和变异
    evaluates = evaluate(nums)
    accumulates = cacu_accumulate(evaluates)
    next_generations = roulette(accumulates, nums)
    next_generations = cross(next_generations)
    next_generations = variation(next_generations, number)
    for i in range(len(next_generations)):
        next_generations[i] = list(next_generations[i])
    return next_generations


def main():
    min_popsize = []
    min_target = []
    next_generation = original(popsize)
    print("初始化种群：", next_generation)
    print(">>>>>>>>>>>>>>>>>>>>>>>>正在进行最优解选取<<<<<<<<<<<<<<<<<<<<<<<<")
    for i in range(maxGen):
        next_generation = process(next_generation, i)
        targets = target(next_generation)
        target_min = min(targets)
        m = targets.index(target_min)
        min_target.append(target_min)
        min_popsize.append(list(next_generation[m]))
    print("最后一代情况：", next_generation)
    end_target = min_popsize[target(min_popsize).index(min(target(min_popsize)))]
    end_min = min(target(min_popsize))
    print("最小的种群是：", min_popsize)
    print('每个的目标值是：', target(min_popsize))
    print("最小值是：", end_min)
    print('最优解: ', end_target)
    mpl.rcParams['font.sans-serif'] = ['KaiTi']
    mpl.rcParams['font.serif'] = ['KaiTi']
    x = np.linspace(1, maxGen, maxGen)
    y = min_target
    plt.figure()
    plt.plot(x, y)
    plt.xlabel("遗传的代数")
    plt.ylabel("每一代中的最小值")
    plt.show()

if __name__ == '__main__':
    main()