遗传算法实践(二) 配词问题

在非线性函数寻优中我们看到了编码方式对于问题求解的重要性，但是遗传算法中的评价函数设定也对求解有至关重要的作用。如果设定的评价函数不好，可能导致算法无法正确收敛。下文就给出这样一个例子。

配词问题描述

配词问题(word matching problem)是给定某字符串，以生成同样字符串为目的的问题。

例如对目标短语"to be or not to be"，要求用遗传算法生成该短语。

这里最简单直接的个体编码方式是采用13个ASCII码进行编码（当然用字符编码也是可以的，这里因为探讨的主要问题在于评价函数的选择，因此就不对编码方式多做探索了）。考虑评价函数时，很自然地会有两种评价思路：

• 第一种思路是将目标函数设定为与给定的字符串的ASCII码差异。此时配词问题转化为一个将目标函数最小化的问题；
• 第二种思路是将目标函数设定与原文相同的字符个数。此时配词问题转化为一个将目标函数最大化的问题。

评价方式一

遗传算法操作

这里采用的遗传算法操作如下：

• 个体编码：使用ASCII码数字编码，长度为13
• 评价函数：与给定的字符串的ASCII码差的绝对值之和
• 育种选择：binary锦标赛选择
• 变异算法：交叉-均匀交叉，突变-乱序突变
• 环境选择：精英保留策略

完整代码

# 导入模块
import numpy as np
import matplotlib.pyplot as plt
from deap import base, tools, creator, algorithms
import random

params = {
    'font.family': 'serif',
    'figure.dpi': 300,
    'savefig.dpi': 300,
    'font.size': 12,
    'legend.fontsize': 'small'
}
plt.rcParams.update(params)
# ----------------------
# 问题定义
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #　最小化问题
creator.create('Individual', list, fitness=creator.FitnessMin)

# 个体编码
geneLength = 13
toolbox = base.Toolbox()
toolbox.register('genASCII',random.randint, 97, 122)
toolbox.register('individual', tools.initRepeat, creator.Individual, toolbox.genASCII, n=geneLength)

# 评价函数 -- 与给定的字符串的ASCII码差异之和
def evaluate(ind):
    target = list('tobeornottobe')
    target = [ord(item) for item in target]
    return (sum(np.abs(np.asarray(target) - np.asarray(ind)))),

toolbox.register('evaluate', evaluate)

# 记录迭代数据
stats = tools.Statistics(key=lambda ind:ind.fitness.values)
stats.register('avg', np.mean)
stats.register('max', np.max)
stats.register('min', np.min)
stats.register('std', np.std)

logbook = tools.Logbook()
logbook.header = ['gen', 'nevals'] + (stats.fields)

# 生成初始族群
popSize = 100
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
pop = toolbox.population(popSize)

# 注册遗传算法操作 -- 选择,交叉,突变
toolbox.register('select', tools.selTournament, tournsize=2)
toolbox.register('mate', tools.cxUniform, indpb=0.5)
toolbox.register('mutate', tools.mutShuffleIndexes, indpb=0.5)

# ----------------------
# 遗传算法
ngen = 400 # 迭代步数
cxpb = 0.8 # 交叉概率
mutpb = 0.2 # 突变概率
# 评价初始族群
invalid_ind = [ind for ind in pop if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate, pop)
for fitness, ind in zip(fitnesses, invalid_ind):
    ind.fitness.values = fitness

# 记录数据
record = stats.compile(pop)
logbook.record(gen=0, nevals=len(invalid_ind), **record)

# 迭代
for gen in range(1, ngen+1):
    # 配种选择
    offspring = toolbox.select(pop, popSize)
    offspring = [toolbox.clone(_) for _ in offspring]
    # 交叉
    for ind1, ind2 in zip(offspring[::2], offspring[1::2]):
        if random.random()<cxpb:
            toolbox.mate(ind1, ind2)
            del ind1.fitness.values
            del ind2.fitness.values
    # 突变
    for ind in offspring:
        if random.random()<mutpb:
            toolbox.mutate(ind)
            del ind.fitness.values
    # 评价子代
    invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
    fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
    for fitness, ind in zip(fitnesses, invalid_ind):
        ind.fitness.values = fitness
    # 环境选择
    combinedPop = pop + offspring
    pop = tools.selBest(combinedPop, popSize) # 精英保存策略
    # 记录数据
    record = stats.compile(pop)
    logbook.record(gen=gen, nevals=len(invalid_ind), **record)
print(logbook)

计算结果

# 输出结果
bestInd = tools.selBest(pop,1)[0]
bestFit = bestInd.fitness.values[0]
bestInd = [chr(item) for item in bestInd]
print('最优解为: '+str(bestInd))
print('函数最小值为: '+str(bestFit))

## 结果
## 最优解为: ['t', 'o', 'b', 'f', 'o', 'q', 'n', 'p', 't', 't', 'o', 'b', 'e']
## 函数最小值为: 3.0

迭代过程的可视化

# 可视化迭代过程
minFit = logbook.select('min')
avgFit = logbook.select('avg')
plt.plot(minFit, 'b-', label='Minimum Fitness')
plt.plot(avgFit, 'r-', label='Average Fitness')
plt.xlabel('# Gen')
plt.ylabel('Fitness')
plt.legend(loc='best')

Evaluation 1

评价方式二

遗传算法操作

这里只更换评价函数，其余的遗传算法操作保持完全相同：

• 个体编码：使用ASCII码编码，长度为13
• 评价函数：与原文相同的字符个数
• 育种选择：binary锦标赛选择
• 变异算法：交叉-均匀交叉，突变-乱序突变
• 环境选择：精英保留策略

完整代码

# 导入模块
import numpy as np
import matplotlib.pyplot as plt
from deap import base, tools, creator, algorithms
import random

params = {
    'font.family': 'serif',
    'figure.dpi': 300,
    'savefig.dpi': 300,
    'font.size': 12,
    'legend.fontsize': 'small'
}
plt.rcParams.update(params)
# ----------------------
# 问题定义
creator.create('FitnessMax', base.Fitness, weights=(1.0,)) #　最大化问题
creator.create('Individual', list, fitness=creator.FitnessMax)

# 个体编码
geneLength = 13
toolbox = base.Toolbox()
toolbox.register('genASCII',random.randint, 97, 122)
toolbox.register('individual', tools.initRepeat, creator.Individual, toolbox.genASCII, n=geneLength)

# 评价函数 -- 生成的字符串与目标字符串相同字符个数
def evaluate(ind):
    target = list('tobeornottobe')
    target = [ord(item) for item in target]
    return (sum(np.asarray(target) == np.asarray(ind))),

toolbox.register('evaluate', evaluate)

# 迭代数据
stats = tools.Statistics(key=lambda ind:ind.fitness.values)
stats.register('avg', np.mean)
stats.register('max', np.max)
stats.register('min', np.min)
stats.register('std', np.std)

logbook = tools.Logbook()
logbook.header = ['gen', 'nevals'] + (stats.fields)

# 生成族群
popSize = 100
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
pop = toolbox.population(popSize)

# 注册遗传算法操作 -- 选择,交叉,突变
toolbox.register('select', tools.selTournament, tournsize=2)
toolbox.register('mate', tools.cxUniform, indpb=0.5)
toolbox.register('mutate', tools.mutShuffleIndexes, indpb=0.5)

# ----------------------
# 遗传算法
ngen = 400 # 迭代步数
cxpb = 0.8 # 交叉概率
mutpb = 0.2 # 突变概率
# 评价初始族群
invalid_ind = [ind for ind in pop if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate, pop)
for fitness, ind in zip(fitnesses, invalid_ind):
    ind.fitness.values = fitness

# 记录数据
record = stats.compile(pop)
logbook.record(gen=0, nevals=len(invalid_ind), **record)

# 迭代
for gen in range(1, ngen+1):
    # 配种选择
    offspring = toolbox.select(pop, popSize)
    offspring = [toolbox.clone(_) for _ in offspring]
    # 交叉
    for ind1, ind2 in zip(offspring[::2], offspring[1::2]):
        if random.random()<cxpb:
            toolbox.mate(ind1, ind2)
            del ind1.fitness.values
            del ind2.fitness.values
    # 突变
    for ind in offspring:
        if random.random()<mutpb:
            toolbox.mutate(ind)
            del ind.fitness.values
    # 评价子代
    invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
    fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
    for fitness, ind in zip(fitnesses, invalid_ind):
        ind.fitness.values = fitness
    # 环境选择
    combinedPop = pop + offspring
    pop = tools.selBest(combinedPop, popSize) # 精英保存策略
    # 记录数据
    record = stats.compile(pop)
    logbook.record(gen=gen, nevals=len(invalid_ind), **record)
print(logbook)

计算结果

# 输出结果
bestInd = tools.selBest(pop,1)[0]
bestFit = bestInd.fitness.values[0]
bestInd = [chr(item) for item in bestInd]
print('最优解为: '+str(bestInd))
print('函数最大值为: '+str(bestFit))

## 结果
## 最优解为: ['t', 'o', 'b', 'e', 'o', 'r', 'n', 'o', 't', 't', 'o', 'b', 'e']
## 函数最大值为: 13.0

迭代过程的可视化

# 可视化迭代过程
maxFit = logbook.select('max')
avgFit = logbook.select('avg')
plt.plot(maxFit, 'b-', label='Maximum Fitness')
plt.plot(avgFit, 'r-', label='Average Fitness')
plt.xlabel('# Gen')
plt.ylabel('Fitness')
plt.legend(loc='best')

Evaluation 2

小结

• 这里给出的评价方法一的结果是多次运行后的一个较优解：['t', 'o', 'b', 'f', 'o', 'q', 'n', 'p', 't', 't', 'o', 'b', 'e']，它显然并非全局最优解 — 并没有能完全复现我们的目标；
• 评价方法二的结果是多次运行中随便取了一次结果 — 它每次都能以很快的速度收敛到最优解。
• 两个程序的差别仅仅在于更换了评价函数，别的遗传算法操作完全相同，可以看到评价函数选择对于遗传算法设计的重要性。