遗传算法-求函数最大值为例

其他 评论

基本思路

02代码实现

1）主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#主函数
def main():
    print('y = 10 * sin(5 * x) + 7 * cos(4 * x)')
     
    #查看要处理的函数
    plot_obj_func()
     
    #设置初始参数
    size = 500  # 种群数量
    start = 0 #变量最小值
    end = 10  # 变量最大值
    bit = 2 #变量精度
    iter = 500 #演化代数
    pc = 0.6 # 杂交概率
    pm = 0.01  # 变异概率
    mini = 0 #淘汰环节阈值（越大淘汰率越高）
    results = []  # 存储每一代的最优解，N个二元组
    #记录每代最优个体
    best_x = []
    best_y = []
    x = create_num(start,end,bit,size)
     
    #进行迭代
    for i in range(iter):
        y = fitness(x) #计算适应度
         
        fit_value = calc_fit_value(y,mini)#将个体适应度不好的（值小于某阈值的）归0，即在后续去掉该个体
        now_best_x,now_best_y = find_best(x,fit_value) #记录本代最优个体信息
        best_x.append(now_best_x)
        best_y.append(now_best_y)
         
        selection(x,fit_value) #选择新个体，更新x
        gene = code(x,end,bit,size) #获得个体(x)的染色体表示
        crossover(gene, pc) # 交叉
        mutation(gene,pm) #变异
        x = decode(gene,bit) #获得新一代的种群
    plot_currnt_individual(x,fitness(x))#查看最终种群分布
    plot_iter_curve(iter,best_y) #查看每一代的最优解
    print(max(best_y)) #找出所有解中最优的一个

主函数展示了算法的整体思路，即

①确定各参数（种群数量、函数自变量范围、自变量精确度、演化代数、杂交及变异概率）

②产生个体，对个体进行评价

③更新个体，将不适应的个体清除

④重新生成新的种群（通过重新选择、交叉、变异产生）

重复③④直到满足设定的迭代次数

得到迭代过程中的最优解

2）个体生成函数

1
2
3
4
5
6
7
def create_num(start,end,bit,size):
   listx = []
   #产生规定范围内的小数集作为个体
   for i in range(size):
       listx.append(round(random.uniform(start,end),bit))
    
   return listx

random.uniform()生成随机浮点数，round()设置小数点后位数，获得初代个体，保存至列表

3）计算适应度

1
2
3
4
#计算适应度
def fitness(x):
    Y = [10 * math.sin(5 * i) + 7 * math.cos(4 * i) for i in x]
    return Y

适应度即随机生成的x值对应的函数值

4）淘汰个体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#淘汰
def calc_fit_value(value_y,mini):
    fit_value = []
     
    # 去掉小于mini的值，更改c_min会改变淘汰的下限
    # 比如设成10可以加快收敛
    # 但是如果设置过大，有可能影响了全局最优的搜索
    c_min = mini
    for value in value_y:
        if value > c_min:
            temp = value
        else:
            temp = 0.
        fit_value.append(temp)
    # fit_value保存的是活下来的值,淘汰个体的值变为0
    return fit_value

通过适应度，将淘汰个体适应度（函数值）变为0，保证在后续个体选择时不会选中它

5）选出当代最优个体

1
2
3
4
5
#找出当前最优解对应的x、y
def find_best(x,y):
    value_y = max(y)
    value_x = x[y.index(value_y)]
    return value_x,value_y

找出当前代最优个体，进行记录，供最后查看代际迭代情况

6）轮盘赌选择个体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#轮盘赌选个体
def selection(now_x,now_value):
    value_rate = []
     
    # 适应度总和
    total_fit = sum(now_value)
     
    # 归一化，使概率总和为1
    for i in range(len(now_value)):
        value_rate.append(now_value[i] / total_fit)
    value_rate = np.cumsum(value_rate)
     
    #产生新种群个体的个数
    x_len = len(now_x)
     
    # 轮盘赌每次的概率值
    ms = sorted([random.random() for i in range(x_len)])
     
    #轮盘赌选出个体
    fitin = 0
    newin = 0
    new_gen = now_x
    # 转轮盘选择法
    while newin < x_len:
        # 如果这个概率大于随机出来的那个概率，就选这个
        if (ms[newin] < value_rate[fitin]):
            new_gen[newin] = now_x[fitin]
            newin = newin + 1
        else:
            fitin = fitin + 1
    x = new_gen

轮盘赌基本思想：每个个体的适应度/总适应度 就是改个体被选中的概率，然后将其累加，得到0-1的圆盘，通过随机数进行选择。是印度越大，在轮盘上所占据空间越大，被选中的概率也越大。

本算法轮盘赌选择的个体有重复选择的情况出现

7）编码

1
2
3
4
5
6
7
8
9
10
#编码
def code(listx,end,bit,size):
    #计算所需染色体长度
    len_gen = len(bin(end*10**bit))-2
 
    #将小数转化为相应的染色体编码
    gene = [round(100*x) for x in listx]
    for i in range(size):
        gene[i] = bin(gene[i])[2:].rjust(len_gen,'0')#长度不足lens的，左边补0
    return gene

将所选中的x变为相应的二进制编码，以进行交叉变异。

编码思路为：

因随机生成x存在小数，首先将小数放大10的n次方，变为整数，之后对该整数进行编码

编码过程中出现取值范围的最小值与最大值转化出的二进制表达，其长度不相同（eg.10→1010，1000→1111101000），因此把最大取值的二进制长度作为染色体长度，不足的在前面补0。

将所有x转化为相应的二进制形式放入列表[gene]进行存储

8）交叉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#杂交
def crossover(pop, pc):
    # 一定概率杂交，主要是杂交种群种相邻的两个个体
    pop_len = len(pop)
    i = 0
    while i < pop_len :
        # 随机数看达到杂交概率没
        if (random.random() < pc):
            #随机选取两个个体进行杂交
            rand1 = random.randint(0, len(pop)-1)
            rand2 = random.randint(0, len(pop)-1)
 
            # 随机选取杂交点，然后交换数组
            cpoint = random.randint(1, len(pop[0])-1)
 
            out1 = pop[rand1][0:cpoint]
            out2 = pop[rand1][cpoint:]
            out3 = pop[rand2][0:cpoint]
            out4 = pop[rand2][cpoint:]
 
            pop[i] = out1 + out4
            pop[i+1] = out2 + out3
        i+=2

交叉变异为算法核心之一，此处交叉选择的是又放回的从种群中随机抽取两个个体进行染色体交叉，生成两个新的个体。

如果达到杂交概率，则子代两个个体由父代杂交生成，否则直接继承父代染色体。

每次杂交生成两个个体，直到新生成的子代个体数达到设定的种群数量。

个体选择及染色体交叉点通过random.randint()函数生成

新染色体通过字符串切片，将两条染色体分为4份，进行重新拼接

9）变异

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#基因突变
def mutation(pop,pm):
    px = len(pop)
    py = len(pop[0])
    #py = 10
    # 每条染色体随便选一个杂交
    for i in range(px):
        if (random.random() < pm):
            mpoint = random.randint(0, py - 1)
            if (pop[i][mpoint] == 1):
                pop[i] = pop[i][:mpoint] + '0' + pop[i][mpoint+1:]
                #pop[i][mpoint] = 0
            else:
                #pop[i][mpoint] = 1
                pop[i] = pop[i][:mpoint] + '1' + pop[i][mpoint+1:]

杂交产生的子代染色体存在一定概率突变，因此设定突变概率，对每个子代染色体：

生成随机数判断是否突变，

若没有，则染色体不变，确定为子代染色体

若发生突变，则随机选取染色体某一位置的数字进行取反（0变1，1变0），完成突变，成为子代染色体

！至此，子代已经确定，可以进行下一轮的自然选择

10）解码

1
2
3
4
5
6
7
8
9
#解码
def decode(ones,bit):
    tens = []
    for i in range(len(ones)):
        ten = int(ones[i],2)
        tens.append(ten)
    for i in range(len(ones)):
        tens[i] = tens[i]/10**bit
    return tens

通过交叉变异得到的子代是染色体形式，在进行自然选择的时候根据其实际数值进行，因此需要进行解码。

解码过程为：

首先将十位染色体编码，通过int()变为十进制整数，

之后除以10的n次方，变为定义域范围内的自变量函数值

11）结果展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#查看要处理函数
def plot_obj_func():
    """y = 10 * math.sin(5 * x) + 7 * math.cos(4 * x)"""
    X1 = [i / float(10) for i in range(0, 100, 1)]
    Y1 = [10 * math.sin(5 * x) + 7 * math.cos(4 * x) for x in X1]
    plt.plot(X1, Y1)
    plt.show()
 
 
#查看当前种群落点情况
def plot_currnt_individual(current_x, current_y):
    X1 = [i / float(10) for i in range(0, 100, 1)]
    Y1 = [10 * math.sin(5 * x) + 7 * math.cos(4 * x) for x in X1]
    plt.plot(X1, Y1)
    plt.scatter(current_x,current_y, c='r', s=5)
    plt.show()
 
 
#查看迭代过程中结果变化
def plot_iter_curve(iter, results):
    X = [i for i in range(iter)]
    Y = [results[i] for i in range(iter)]
    plt.plot(X, Y)
    plt.show()

#查看要处理函数：对所求问题代表的函数进行画图，直观展示
#查看当前种群落点情况：将当前种群的个体情况（x和y值）以点的形式展现出来
#查看迭代过程中结果变化：因记录了每一代的最优个体，因此可以查看迭代过程中，每一代最优解的变化情况

12）运行程序

1
2
3
4
start_time = time.time()  # 记录程序开始运行时间
main()
end_time = time.time()  # 记录程序结束运行时间
print('Took %f second' % (end_time - start_time))

设置了时间统计，记录算法运行花费时间

13）用到的库

1
2
3
4
5
import matplotlib.pyplot as plt
import math
import random
import numpy as np
import time

运行结果

最终运行结果：

输出所求函数表达式、函数图形、最后一代种群分布、迭代过程中的最优解变化情况

参考资料

遗传算法(GA)的新手入门必备，python3案例_hiudawn-CSDN博客_遗传算法python实例

枫与风