遗传算法的Python实现

Learning , , 评论

遗传算法的原理可以参考此文章

看着图片从杂乱的像素点一点一点逼近目标图片是一个十分有趣的过程。

本次以360的logo作为目标图片

logo

1.设置相关参数

SIZE = 64
TOTAL_POP = 4
MUTATION = 0.4
MIN_MUTATION = 0.1 / (SIZE*SIZE)
MUTATION_DECAY = 3e-5
MAX_FIT = []
TOTAL_FIT = []
MUTATION_SPAN = SIZE//2 + 1
  • size：图片缩放后尺寸
  • TOTAL_POP：种群内的个体数量
  • MUTATION：初始突变系数
  • MIN_MUTATION：最低突变系数
  • MUTATION：突变系数在每次迭代的衰减值
  • MAX_FIT：保存每次筛选的最佳fitness，此例中fitness取最小值
  • TOTAL_FIT：每次筛选中的所有个体的fitness的总和
  • MUTATION_SPAN：基因重组片段的最长范围

2. 实现基因重组

1
2
3
4
5
6
7
8
9
10
11
12
def recombination(population):
    # 将按fitness排序的种群顺序打乱
    children = population.copy()
    np.random.shuffle(children) 
    # 两两杂家
    for i in range(0, TOTAL_POP, 2):
        pos = np.random.randint(SIZE*SIZE)   # 随机选择重组位点
        span = np.random.randint(1,MUTATION_SPAN) # 随机选择重组片段长度
        children[i,pos:pos+span], children[i+1, pos:pos+span] = \
        children[i+1, pos:pos+span], children[i,pos:pos+span] # 交换片段
    population = np.concatenate([population, children],axis=0) # 重组后的种群与未重组的合并
    return population

3.实现点突变

def mutation(population):
    total = population.shape[0]  # 种群内个体数目
    p = np.array([1-MUTATION, MUTATION]) # 突变率与不突变率
    # 生成与种群矩阵形状一致的突变矩阵，其中1和0表示突变和不突变，数目与突变率一致
    mask = np.random.choice([0,1], total*SIZE*SIZE, p=p).reshape((total,-1))
    # 进行点突变
    population = np.square(mask - population)
    return population

4. 定义筛选过程

1
2
3
4
5
6
7
8
9
10
11
def choice(population, target):
    total = population.shape[0]
    target = target.reshape((1,-1))   # 将图片展平便于计算
    target = target.repeat(total, axis=0) # 扩充图片维度与个体数一致
    # 计算fitness
    fitness = np.sum(np.square(population - target), axis=1) / (SIZE*SIZE)
    order = fitness.argsort()   # 从小到大排列个体，此处保存的为索引值
    MAX_FIT.append(fitness[order[0]])
    TOTAL_FIT.append(np.sum(fitness))
    # 选择fitness最低的个体进入下一个轮回
    return population[order[:TOTAL_POP]]

5. 功能函数

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
# 绘制结果图
def draw(population, target):
    plt.subplot(4, 1, 1)
    plt.title(f"Min:{MIN_MUTATION:.1e}  Decay:{MUTATION_DECAY:.1e}\n"
              f"Pop:{TOTAL_POP}  Span:{MUTATION_SPAN-1}  Min:{MAX_FIT[-1]:.1e}")
    plt.imshow(target)
    plt.xticks([])
    plt.yticks([])

    for i in range(4):
        plt.subplot(4,2,i+3)
        plt.imshow(population[i].reshape((SIZE,SIZE)))
        plt.xticks([])
        plt.yticks([])


    plt.subplot(4,2,7)
    plt.plot(TOTAL_FIT)
    plt.legend("Total", fontsize=6)
    plt.subplot(4,2,8)
    plt.plot(MAX_FIT)
    plt.legend("Min", fontsize=6)
    plt.tight_layout()
    plt.show()
    
# 读取图片并进行压缩
def readImage(filename)
 image = cv2.imread(filename)
    image = cv2.resize(image, (SIZE,SIZE))
    image = np.sum(image, axis=-1)
    image[image<=127*3] = 0
    image[image>127*3] = 1
    return image

6.开始进行选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import cv2
import numpy as np
from matplotlib import pyplot as plt

target = readImage("360logo.png")

for i in range(100000):
    if MUTATION > MIN_MUTATION:
        MUTATION -= MUTATION_DECAY
        
    if i % 500 == 499:
        print("Generation: "+str(i+1))
        
    population = recombination(population)
    population = mutation(population)
    population = choice(population, target)
    if i % 20000 == 19999: # 两万轮展示一次当前进度
  draw(population, target)

按照上述参数进行筛选完成后，即可得到最佳个体

logo

遗传算法的关键就是计算fitness，只能够对每轮迭代内个体的优劣及逆行评估就能使用遗传算法进行优化，本例中是将个体与简化后的目标图片的像素值做差来进行评估，使用原始三通道图片将其像素值转化为8位二进制（0-255）也可进行计算。

DragonZBioEngineer&DataEngineer

An ordinary human。