Author: ProofZ

0x00 前言

什么是遗传算法?

遗传算法是一种搜索算法(搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况,从而求出问题的解的一种方法,说白了就是从一大堆可能的解中找出最想要的解)。
接下来我会以一个实际例子来解释遗传算法:
用遗传算法求解f(x) = x^2 + x + 3 在[0, 32]上的最大值

0x01 遗传算法的基本概念

接下来将分别介绍几个基本概念:

编码与解码——>基因——>个体——>种群

编码与解码

编码指的是将问题的所有解统一变成统一的格式。编码的方式有多种。这里这个问题采用二进制编码,采用二进制编码的原因就是这里函数自变量的定义域为[0,32)。即:00000~11111。
所以:
编码:十进制——>二进制(五位)
解码:二进制(五位)——>十进制
这里用到了两个函数实现编码和解码功能:
编码:

def encode(num):
# 个体的编码,即染色体
chromosome = bin(num)[2:]
if len(chromosome) != 5:
    filling_bit = 5 - len(chromosome)
    chromosome = "0" * filling_bit + chromosome
return chromosome

解码:

def decode(chromosome):
# 染色体解码为数字
return int("0b" + chromosome, 2)

基因

基因可以理解为是编码中的每一位。例如编码为00101,则它的每一位就是它的基因。

个体&染色体

基因的集合就是染色体。而染色体代表这一个个体。
在本例中:01101这个编码,它的每一位是一个基因,每一个基因的集合就是染色体,而01101这个染色体代表这一个个体。

种群

种群是个体的集合。在本例中一个种群的个体数是4
在本例中:
01001
01010
11010
01110
这样一个个体集合就是一个种群。

然后再介绍几个基本操作

适应度——>选择——>交叉——>突变

适应度

物竞天择,适者生存。遗传算法也会遵循这个原则,适应度的意思就是个体的适应度。在本例中,我们的目的是求出函数f(x) = x^2 + x + 3 在[0, 32]上的最大值,也就是说个体的函数值越大,它的适应度也就越大。
在本例中:个体01101解码之后为13,它的适应度为f(32)=185。

选择

物竞天择,适者生存。
选择的意思就是物竞天择,选择方法有多种。比如比例原则、轮盘赌、竞争法、等级轮盘法。
然而,在本例中,我没采取上述任何一种策略。
本例采取的策略:
在种群中选取适应度最大的两个个体作为父代。在上述种群例子中:
01001 --->9 --适应度->93
01010 --->10 --适应度->113
11010 --->26 --适应度->705
01110 --->14 --适应度->213
被选择的父代(适应度最大的两个)为:
11010 --->26 --适应度->705 --> 1
01110 --->14 --适应度->213 --> 2

交叉

然后,选择其中适应度最大的三个个体为配对的个体。其中适应度最大的个体多选一次。配对池如下:
11010 --->26 --适应度->705 --> 1
11010 --->26 --适应度->705 --> 2
01110 --->14 --适应度->213 --> 3
01010 --->10 --适应度->113 --> 4
随机选择其中两个进行配对。
这里,假如父代1号随机到了配对池3号:
即父代1和配对池3进行交叉,交叉后会产生两个子代。
父代2号随机到配对池1号:
即父代2号将会和配对池3进行交叉,交叉后产生两个子代。
这样,就有4个子代。
这里说明下交叉操作,交叉操作有多种,本例采取的策略以上述父代1和配对池3交叉为模板:
先产生一个1~5的随机数,例如,这里产生的随机数为3,这里将父代1和配对池3进行交叉,将它们低三位进行交换:
父代1:11010 --->26 --适应度->705 --> 1
配对3:01110 --->14 --适应度->213 --> 3
将它们低三位进行交换产生的两个子代如下:
子代1: 11110 --->30
子代2: 01010 --->10

突变

突变的含义很明确——为了更好的模拟“大自然”。
哈哈,骗你的,突变的目的主要是为了解决陷入局部最优的问题。

0x02 实例

流程图如下:
L44T3E7S_QZ8E5UYUIYE9}Q.png

用遗传算法求解f(x) = x^2 + x + 3 在[0, 32]上的最大值:
先初始化种群:

def init_population():
# 初始化种群,种群数目为4
p = range(32)
population = random.sample(p, 4)
return population

先产生0~31上的值,然后在随机选四个作为初始种群。
适应度函数:

def fit(num):
# 适应度函数
return num * num + num + 3

选择操作:

def selection(*args):
# 选择函数
args = list(args)
fit_list = []
pair_list = []
for i in args:
    fit_list.append(fit(i))
print("种群中个体适应度", end=":")
print(fit_list)
n = 0
while n < len(args):
    m = n + 1
    while m < len(args):
        if fit_list[n] < fit_list[m]:
            tmp1 = fit_list[n]
            fit_list[n] = fit_list[m]
            fit_list[m] = tmp1
            tmp2 = args[n]
            args[n] = args[m]
            args[m] = tmp2
        m += 1
    n += 1
pair_list.append(args[0])
pair_list.extend(args[0:3])
print("选出的配对个体", end=":")
print(pair_list)
return pair_list

这里的选择,选择出了配对的个体。
交叉操作:

def cross(num1, num2, point):
# 交叉操作
n1 = encode(num1)
n2 = encode(num2)
# print(n1)
# print(n2)
tmp = n1[point:]
n1 = n1[0:point] + n2[point:]
n2 = n2[0:point] + tmp
# print(n1)
# print(n2)
return [decode(n1), decode(n2)]

def crossover(parents_list, pair_list):
# 交叉函数
p = range(4)
pair = random.sample(p, 2)
next_popolution = []
for i in range(2):
    cross_point = random.randrange(0, len(parents_list))
    print("第" + str(i) + "个交叉点为", end=":")
    print(cross_point)
    next_popolution.extend(cross(parents_list[i], pair_list[pair[i]], cross_point))

return next_popolution

我这里交叉之后直接产生了后代,没进行突变操作。
总体流程执行函数为:

def GA():
gen = 0
population = init_population()
while gen < gen_num:
    population.sort()
    population.reverse()
    print("第" + str(gen) + "代种群:", end=":")
    print(population)
    pair_list = selection(population[0], population[1], population[2], population[3])
    population = crossover(population, pair_list)
    print("子代为", end=":")
    print(population)
    gen += 1
    print("\n\n\n\n")

执行结果为:

如图,在第二代的时候就已经收敛了。而在这个范围中函数的最大值就是f(31)

0x03 后记

当然,事情是不可能这样子简单的结束的,再看一组结果:

这组结果就不是最优的那种理想情况了,它逐渐收敛于27,它到底缺少了什么呢?