谈谈遗传算法：用遗传算法求最大值

遗传算法简介

遗传算法运用自然界优胜劣汰的法则，可以解决大多数最优解问题，算法过程如下：

  1. 将要解决的问题主体进行编码，形成初始种群。
  2. 用选择函数对种群中的个体进行选择。
  3. 将生存的个体进行交叉，生成子代。
  4. 交叉中设置一定的变异率，防止陷入局部最优解。
  5. 将2.3.4.循环操作最终的到最优种群集合，在其中找到最优解

问题

求解函数 2 * math.sin( 2 * x ) + math.cos( 3 * x )在区间[0,9]的最大值。(保留)

遗传算法解决策

假定需要保留四位小数，那么就一共有90000个可能性，那么

2^16 < 90000 < 2^17

可以将所有可能性都包含在内，下面将其进行二进制的转换

1
2
3
4
5
6
7
def get_chromosome(self, length):
	# 随机生成染色体变量
    # a bit ( 0, 1 ) represent a gene
    chromosome = 0
    for i  in range(length):
		chromosome |= ( 1 << i ) * random.randint(0, 1)
   return chromosome

将字符二进制编码后还需进行解码，解码我们用

1
2
3
def decode(self, chromosome):
	# 将二进制还原成十进制
    return chromosome * 9.0/ (2**(self.length)-1)

将得到的种群进行选择，我们要用到题目中所给的选择条件

1
2
3
4
def fitness(self, chromosome):
	# 解码和适应性函数
    x = self.decode(chromosome)
    return 2 * math.sin( 2 * x ) + math.cos( 3 * x )

然后进行编写选择模块

1
2
3
4
5
6
7
8
9
10
11
12
def selection(self, retain_rate, random_select_rate):
	# 通过适应度大小从大到小进行排序，最后生成的仍然是二进制的列表
    graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
    graded = [x[1] for x in sorted(graded, reverse=True)]
    # 选出适应性强的染色体,挑选20%作为父类
    retain_length = int(len(graded) * retain_rate)
    parents = graded[:retain_length]
    # 从剩余的80%里面选出适应性不强，但是幸存的染色体（概率0.5）
    for chromosome in graded[retain_length:]:
    	if random.random() < random_select_rate:
            parents.append(chromosome)
    return parents

编写交叉模块

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(self, parents):
    # 交叉产生后代
    # 新出生的孩子，最终会被加入存活下来的父母之中，形成新一代的种群。
    children = []
    # 需要繁殖的数量
    target_count = len(self.population) - len(parents)
    while len(children) < target_count:
        malelocation = random.randint(0, len(parents) - 1)
        femalelocation = random.randint(0, len(parents) - 1)
        male = parents[malelocation]
        female = parents[femalelocation]
        if malelocation != femalelocation:
            # 随机选择交叉点
            cross_pos = random.randint(0, self.length)
            # 生成掩码，方便位运算
            mask = 0
            for i in range(cross_pos):
                mask |= (1 << i )
            # 孩子将获得父亲在交叉点前的基因和母亲在交叉点后（包括交叉点）的基因
            child = (male & mask) | (female & ~mask)
            children.append(child)
    # 经过繁殖后，孩子和父母的数量与原始种群数量相等，在这里可以更新种群。
    self.population = parents + children

编写变异模块

1
2
3
4
5
6
7
def mutation(self, rate):
    # 对种群中的所有个体，随机改变某个个体中的某个基因
    for i in range(len(self.population)):
        if random.random() < rate:
            j = random.randint(0, self.length - 1)
            # 随机取得一个数j对变异基因1进行随机移动
            self.population[i] = self.population[i] ^ ( 1 << j )  # ^是异或运算

遗传算法求最大值的总体思路就是这样，思想上还是相当简单的，下面我们把所有代码组合起来，加上框架，就可以做成一个完整的遗传算法求最大值的程序

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
# !/usr/bin/env python
# -*- coding:utf-8 -*-
# 求解函数 2 * math.sin( 2 * x ) + math.cos( 3 * x )在区间[0,9]的最大值。

import math
import random
import matplotlib.pyplot as plt

class GA():
    # initalise
    def __init__(self, length, count):
        # 染色体长度
        self.length = length
        # 染色体数量
        self.count = count
        # 形成原始种群
        self.population = self.get_population(length, count)
    
    def get_population(self, length, count):
        # get a list of count numbers chromosome (length : length)
        return [self.get_chromosome(length) for i in range(count)]
    
    def get_chromosome(self, length):
        # 随机生成染色体变量
        # a bit ( 0, 1 ) represent a gene
        chromosome = 0
        for i  in range(length):
            chromosome |= ( 1 << i ) * random.randint(0, 1)
        print(chromosome)
        print(chromosome * 9.0/ (2**(self.length)-1))
        return chromosome
    
    def evolve(self, retain_rate = 0.2, random_select_rate = 0.5, mutation_rate = 0.01 ):
        
        parents = self.selection(retain_rate, random_select_rate)
        self.crossover(parents)
        self.mutation(mutation_rate)
    
    def fitness(self, chromosome):
        # 解码和适应性函数
        x = self.decode(chromosome)
        return 2 * math.sin( 2 * x ) + math.cos( 3 * x )
    
    def selection(self, retain_rate, random_select_rate):
        # 通过适应度大小从大到小进行排序，最后生成的仍然是二进制的列表
        graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
        graded = [x[1] for x in sorted(graded, reverse=True)]
        
        # 选出适应性强的染色体,挑选20%作为父类
        retain_length = int(len(graded) * retain_rate)
        parents = graded[:retain_length]
        
        # 从剩余的80%里面选出适应性不强，但是幸存的染色体（概率0.5）
        for chromosome in graded[retain_length:]:
            if random.random() < random_select_rate:
                parents.append(chromosome)
        return parents
    
    def crossover(self, parents):
        # 交叉产生后代
        # 新出生的孩子，最终会被加入存活下来的父母之中，形成新一代的种群。
        children = []
        # 需要繁殖的数量
        target_count = len(self.population) - len(parents)
        while len(children) < target_count:
            malelocation = random.randint(0, len(parents) - 1)
            femalelocation = random.randint(0, len(parents) - 1)
            male = parents[malelocation]
            female = parents[femalelocation]
            if malelocation != femalelocation:
                # 随机选择交叉点
                cross_pos = random.randint(0, self.length)
                # 生成掩码，方便位运算
                mask = 0
                for i in range(cross_pos):
                    mask |= (1 << i )
                # 孩子将获得父亲在交叉点前的基因和母亲在交叉点后（包括交叉点）的基因
                child = (male & mask) | (female & ~mask)
                children.append(child)
        # 经过繁殖后，孩子和父母的数量与原始种群数量相等，在这里可以更新种群。
        self.population = parents + children
    
    def mutation(self, rate):
        # 对种群中的所有个体，随机改变某个个体中的某个基因
        for i in range(len(self.population)):
            if random.random() < rate:
                j = random.randint(0, self.length - 1)
                # 随机取得一个数j对变异基因1进行随机移动
                self.population[i] = self.population[i] ^ ( 1 << j )  # ^是异或运算

    def decode(self, chromosome):
        # 将二进制还原成十进制
        return chromosome * 9.0/ (2**(self.length)-1)
    
    def result(self):
        # 获得当前最优的个体值
        graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
        graded = [ x[1] for x in sorted(graded, reverse = True)]
        X1 = [i / float(10) for i in range(0, 100, 1)]
        Y1 = [2 * math.sin( 2 * x ) + math.cos( 3 * x ) for x in X1]
        plt.plot(X1, Y1)
        plt.show()
        return ga.decode(graded[0])


if __name__ == '__main__':
    # 染色体长度为17，群落数量是300
    ga = GA(17, 300)
    for x in range(200):
        ga.evolve()
    print('x = %f' %(ga.result()))

总结

  • 遗传算法在思想上还是很简单的存在，并且可以通过变异避免陷入局部最优解，但是缺点也很明显，因为要通过不停迭代不停选择，所以运行时间比较长，而且种群数量变大的话，对于电脑的资源消耗也变高。

  • 遗传算法的难点在于对于现实中的物体进行编码，并且染色体交叉后是否会出现不合规的染色体，比如在用遗传算法解决pick up and delivery问题上，配送的先后顺序也要考虑到，这些都是今后需要考虑的点。

谈谈技术
#python #算法 #遗传算法
谈谈遗传算法：用遗传算法求最大值
http://liuminxuan.github.io/2020/08/20/谈谈遗传算法/
发布于
2020年8月20日
许可协议