写在前面
前天写完了基于传递闭包的模糊聚类，今天准备写“遗传算法求解无约束单目标优化问题”。昨天和npy玩了一下午，去齐白石艺术学院看了画展，一起在最高处看了夕阳，并在落日前接吻。
实验题目
遗传算法求解无约束单目标优化问题
实验目的
理解遗传算法原理，掌握遗传算法的基本求解步骤，包括选择、交叉、变异等，学会运用遗传算法求解无约束单目标优化问题。
背景知识
遗传算法(Genetic Algorithm)是借鉴生物界自然选择、适者生存遗传机制的一种随机搜索方法。遗传算法模拟了进化生物学中的遗传、突变、自然选择以及杂交等现象，是进化算法的一种。对于一个最优化问题，一定数量的候选解(每个候选解称为一个个体)的抽象表示(也称为染色体)的种群向更好的方向解进化，通过一代一代不断繁衍，使种群收敛于最适应的环境，从而求得问题的最优解。进化从完全随机选择的个体种群开始，一代一代繁殖、进化。在每一代中，整个种群的每个个体的适应度被评价,从当前种群中随机地选择多个个体(基于它们的适应度)，通过自然选择、优胜劣汰和突变产生新的种群，该种群在算法的下一次迭代中成为当前种群。传统上，解一般用二进制表示(0 和 1 组成的串)。遗传算法的主要特点是直接对结构对象进行操作，不存在函数求导、连续、单峰的限定；具有内在的隐闭并行性和更好的全局寻优能力;采用概率化的寻优方法，能自动获取和指导优化搜索，自适应调整搜索方向，不需要确定的规则。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工智能等领域中的问题求解，已成为现代智能计算中的一项关键技术。
关键术语：
(1)个体( individuals):遗传算法中所处理的对象称为个体。个体通常可以含解的编码表示形式、适应度值等构成成分，因而可看成是一个结构整体。其中，主要成分是编码。
(2)种群(population):由个体构成的集合称为种群。
(3)位串(bit string):解的编码表示形式称为位串。解的编码表示可以是 0、1 二值串、0～9 十进制数字串或其他形式的串，可称为字符串或简称为串。位串和染色体(chromosome)相对应。在遗传算法的描述中，经常不加区分地使用位串和染色体这两个概念。位串/染色体与个体的关系:位串/染色体一般是个体的成分，个体还可含有适度值等成分。个体、染色体、位串或字符串有时在遗传算法中可不加区分地使用。
(4)种群规模(population scale):又称种群大小,指种群中所含个体的数目。
(5)基因(gene):位串中的每个位或元素统称为基因。基因反映个体的特征。同一位上的基因不同，个体的特征可能也不相同。基因对应于遗传学中的遗传物质单位。在 DNA 序列表示中，遗传物质单位也是用特定编码表示的。遗传算法中扩展了编码的概念，对于可行解，可用 0、1 二值、0~9 十个数字,以及其他形式的编码表示。例如，在 0、1 二值编码下，有一个串 S=1011，则其中的 1，0，1，1这 4 个元素分别称为基因。基因和位在遗传算法中也可不加区分地使用。
(6)适应度(fitness):个体对环境的适应程度称为适应度(fitness)。为了体现染色体的适应能力，通常引入一个对每个染色体都能进行度量的函数﹐称为适应度函数。
(7)选择(selection):在整个种群或种群的一部分中选择某个个体的操作。
(8)交叉(crossover):两个个体对应的一个或多个基因段的交换操作。
(9)变异(mutation):个体位串上某个基因的取值发生变化。如在 0、1 串表示下，某位的值从 0 变为 1，或由 1 变为 0。
遗传算法的基本流程如下：
本案例意在说明如何使用遗传算法求解无约束单目标优化问题，即求一元函数：
在区间[-1, 2]上的最大值。该函数图像如下：
由图像可知该函数在在区间[-1, 2]上有很多极大值和极小值，对于求其最大值或最小值的问题，很多单点优化的方法（梯度下降等）就不适合，这种情况下可以考虑使用遗传算法。。
示例代码
import numpy as np
import matplotlib.pyplot as plt
def fun(x):
return x * np.sin(10*np.pi*x) + 2
Xs = np.linspace(-1, 2, 100)
np.random.seed(0) # 令随机数种子=0，确保每次取得相同的随机数
# 初始化原始种群
population = np.random.uniform(-1, 2, 10) # 在[-1,2)上以均匀分布生成10个浮点数，做为初始种群
for pop, fit in zip(population, fun(population)):
print("x=%5.2f, fit=%.2f" % (pop, fit))
plt.plot(Xs, fun(Xs))
plt.plot(population, fun(population), '*')
plt.show()
def encode(population, _min=-1, _max=2, scale=2**18, binary_len=18): # population必须为float类型，否则精度不能保证
# 标准化，使所有数据位于0和1之间,乘以scale使得数据间距拉大以便用二进制表示
normalized_data = (population-_min) / (_max-_min) * scale
# 转成二进制编码
binary_data = np.array([np.binary_repr(x, width=binary_len)
for x in normalized_data.astype(int)])
return binary_data
chroms = encode(population) # 染色体英文(chromosome)
for pop, chrom, fit in zip(population, chroms, fun(population)):
print("x=%.2f, chrom=%s, fit=%.2f" % (pop, chrom, fit))
def decode(popular_gene, _min=-1, _max=2, scale=2**18): # 先把x从2进制转换为10进制，表示这是第几份
# 乘以每份长度（长度/份数）,加上起点,最终将一个2进制数，转换为x轴坐标
return np.array([(int(x, base=2)/scale*3)+_min for x in popular_gene])
fitness = fun(decode(chroms))
for pop, chrom, dechrom, fit in zip(population, chroms, decode(chroms), fitness):
print("x=%5.2f, chrom=%s, dechrom=%.2f, fit=%.2f" %
(pop, chrom, dechrom, fit))
fitness = fitness - fitness.min() + 0.000001 # 保证所有的都为正
print(fitness)
def Select_Crossover(chroms, fitness, prob=0.6): # 选择和交叉
probs = fitness/np.sum(fitness) # 各个个体被选择的概率
probs_cum = np.cumsum(probs) # 概率累加分布
each_rand = np.random.uniform(size=len(fitness)) # 得到10个随机数，0到1之间
# 轮盘赌，根据随机概率选择出新的基因编码
# 对于each_rand中的每个随机数，找到被轮盘赌中的那个染色体
newX = np.array([chroms[np.where(probs_cum > rand)[0][0]]
for rand in each_rand])
# 繁殖，随机配对（概率为0.6)
# 6这个数字怎么来的，根据遗传算法，假设有10个数，交叉概率为0.6，0和1一组，2和3一组。。。8和9一组，每组扔一个0到1之间的数字
# 这个数字小于0.6就交叉，则平均下来应有三组进行交叉，即6个染色体要进行交叉
pairs = np.random.permutation(
int(len(newX)*prob//2*2)).reshape(-1, 2) # 产生6个随机数，乱排一下，分成二列
center = len(newX[0])//2 # 交叉方法采用最简单的，中心交叉法
for i, j in pairs:
# 在中间位置交叉
x, y = newX[i], newX[j]
newX[i] = x[:center] + y[center:] # newX的元素都是字符串，可以直接用+号拼接
newX[j] = y[:center] + x[center:]
return newX
chroms = Select_Crossover(chroms, fitness)
dechroms = decode(chroms)
fitness = fun(dechroms)
for gene, dec, fit in zip(chroms, dechroms, fitness):
print("chrom=%s, dec=%5.2f, fit=%.2f" % (gene, dec, fit))
# 对比一下选择和交叉之后的结果
fig, (axs1, axs2) = plt.subplots(1, 2, figsize=(14, 5))
axs1.plot(Xs, fun(Xs))
axs1.plot(population, fun(population), 'o')
axs2.plot(Xs, fun(Xs))
axs2.plot(dechroms, fitness, '*')
plt.show()
# 输入一个原始种群1，输出一个变异种群2 函数参数中的冒号是参数的类型建议符，告诉程序员希望传入的实参的类型。函数后面跟着的箭头是函数返回值的类型建议符，用来说明该函数返回的值是什么类型。
def Mutate(chroms: np.array):
prob = 0.1 # 变异的概率
clen = len(chroms[0]) # chroms[0]="111101101 000010110" 字符串的长度=18
m = {'0': '1', '1': '0'} # m是一个字典，包含两对：第一对0是key而1是value；第二对1是key而0是value
newchroms = [] # 存放变异后的新种群
each_prob = np.random.uniform(size=len(chroms)) # 随机10个数
for i, chrom in enumerate(chroms): # enumerate的作用是整一个i出来
if each_prob[i] < prob: # 如果要进行变异(i的用处在这里)
pos = np.random.randint(clen) # 从18个位置随机中找一个位置，假设是7
# 0~6保持不变，8~17保持不变，仅将7号翻转，即0改为1，1改为0。注意chrom中字符不是1就是0
chrom = chrom[:pos] + m[chrom[pos]] + chrom[pos+1:]
newchroms.append(chrom) # 无论if是否成立，都在newchroms中增加chroms的这个元素
return np.array(newchroms) # 返回变异后的种群
newchroms = Mutate(chroms)
def DrawTwoChroms(chroms1, chroms2, fitfun): # 画2幅图，左边是旧种群，右边是新种群，观察平行的两幅图可以看出有没有差异
Xs = np.linspace(-1, 2, 100)
fig, (axs1, axs2) = plt.subplots(1, 2, figsize=(14, 5))
dechroms = decode(chroms1)
fitness = fitfun(dechroms)
axs1.plot(Xs, fitfun(Xs))
axs1.plot(dechroms, fitness, 'o')
dechroms = decode(chroms2)
fitness = fitfun(dechroms)
axs2.plot(Xs, fitfun(Xs))
axs2.plot(dechroms, fitness, '*')
plt.show()
# 对比一下变异前后的结果
DrawTwoChroms(chroms, newchroms, fun)
# 上述代码只是执行了一轮，这里反复迭代
np.random.seed(0) #
population = np.random.uniform(-1, 2, 100) # 这次多找一些点
chroms = encode(population)
for i in range(1000):
fitness = fun(decode(chroms))
fitness = fitness - fitness.min() + 0.000001 # 保证所有的都为正
newchroms = Mutate(Select_Crossover(chroms, fitness))
if i % 300 == 1:
DrawTwoChroms(chroms, newchroms, fun)
chroms = newchroms
DrawTwoChroms(chroms, newchroms, fun)
实验内容
运行和理解示例代码，回答下列问题：
1）代码第 64 行的语义是什么？两个[0]各自代表什么？最后 newX 有几个元素？
newX = np.array([chroms[np.where(probs_cum > rand)[0][0]]
for rand in each_rand])
2）代码第 70 行的语义是什么？为什么要除以 2 再乘以 2？reshape 中的-1 表示什么？
pairs = np.random.permutation(
int(len(newX)*prob//2*2)).reshape(-1, 2) # 产生 6 个随机数乱排一下分成二列
3）请结合 Mutate 函数的内容，详述变异是如何实现的。
4）将代码第 145 行修改为 newchroms = Select_Crossover(chroms, fitness)，即不再执行变异，执行结果有什么不同，为什么会出现这种变化？
5）轮盘让个体按概率被选择，对于适应度最高的个体而言，虽然被选择的概率高，但仍有可能被淘汰，从而在进化过程中失去当前最优秀的个体。一种改进方案是，让适应度最高的那个个体不参与选择，而是直接进入下一轮（直接晋级），这种方案被称为精英选择(elitist selection)。请修改Select 部分的代码，实现这一思路。
6）【选做】请借鉴示例代码，实现教材 P57 的例 2.6.1，即用遗传算法求解下列二元函数的最大值。
实验结果与分析
第一题
1）代码第 64 行的语义是什么？两个[0]各自代表什么？最后 newX 有几个元素？
newX = np.array([chroms[np.where(probs_cum > rand)[0][0]]
for rand in each_rand])
经过拆分，得到结果：
上面的代码等于
其中[]中的for为列表生成式，返回一个列表。第一个[0]表示np.where()生成tuple元组中数组的行索引，np.where()[0]的值是tuple中的第一个数组，由于本例只有一个数组，故只返回一个一维数组，第二个[0]是该一维数组的首位元素。
最后newX一共有100个元素。
第二题
2）代码第 70 行的语义是什么？为什么要除以 2 再乘以 2？reshape 中的-1 表示什么？
pairs = np.random.permutation(
int(len(newX)*prob//2*2)).reshape(-1, 2) # 产生 6 个随机数乱排一下分成二列
-
随机生成6个在[0,5]之间的数字，并将其排列成二维的形状是(3,2)的数组。
-
newX一共有十个元素，可以理解成有十条染色体。因为要随机配对，所以我们把染色体两两分组，这样//2表示一共分成了五组。分成五组后，乘以随机配对概率，得到一共有三组染色体要进行配对。配对是单条染色体与另一个单条染色体进行的行为，故我们要乘以2，表示一共有六条染色体之间要配对。
-
reshape中的-1表示，通过列数对数组的行数进行自动计算。新的shape属性应该要与原来的配套，如果等于-1的话，那么Numpy会根据剩下的维度计算出数组的另外一个shape属性值。
第三题
3）请结合 Mutate 函数的内容，详述变异是如何实现的。
def Mutate(chroms: np.array):
prob = 0.1 # 变异的概率
clen = len(chroms[0]) # chroms[0]="111101101 000010110" 字符串的长度=18
m = {'0': '1', '1': '0'} # m是一个字典，包含两对：第一对0是key而1是value；第二对1是key而0是value
newchroms = [] # 存放变异后的新种群
each_prob = np.random.uniform(size=len(chroms)) # 随机10个数
for i, chrom in enumerate(chroms): # enumerate的作用是整一个i出来
if each_prob[i] < prob: # 如果要进行变异(i的用处在这里)
pos = np.random.randint(clen) # 从18个位置随机中找一个位置，假设是7
# 0~6保持不变，8~17保持不变，仅将7号翻转，即0改为1，1改为0。注意chrom中字符不是1就是0
chrom = chrom[:pos] + m[chrom[pos]] + chrom[pos+1:]
newchroms.append(chrom) # 无论if是否成立，都在newchroms中增加chroms的这个元素
return np.array(newchroms) # 返回变异后的种群
- 首先，得到变异概率与单个染色体的长度(二进制数位数)，再利用字典对变异的两种情况做一个存储。
- newchroms是存放变异后新种群的array。
- 通过each_prob计算出每个染色体的随机变异概率
- 遍历染色体，如果随机变异概率低于变异概率，则发生变异
- 发生变异，通过计算pos，从染色体中随机找个位置变异，即二进制数某个位发生突变
- 无论染色体是否发生变异，都在新种群中添加染色体(发生突变的与岁月静好的都算)
- 返回整个新的种群
未修改前：
修改后：
执行结果变化如上。
染色体进行过交叉后，不再发生变异。少了一次变异，新种群与原种群概率上讲，差异要更小一些。
第五题
5）轮盘让个体按概率被选择，对于适应度最高的个体而言，虽然被选择的概率高，但仍有可能被淘汰，从而在进化过程中失去当前最优秀的个体。一种改进方案是，让适应度最高的那个个体不参与选择，而是直接进入下一轮（直接晋级），这种方案被称为精英选择(elitist selection)。请修改Select 部分的代码，实现这一思路。
def Select_Crossover(chroms, fitness, prob=0.6): # 选择和交叉
probs = fitness/np.sum(fitness) # 各个个体被选择的概率
probs_cum = np.cumsum(probs) # 概率累加分布
each_rand = np.random.uniform(size=len(fitness)) # 得到10个随机数，0到1之间
# 轮盘赌，根据随机概率选择出新的基因编码
# 对于each_rand中的每个随机数，找到被轮盘赌中的那个染色体
# 修改代码处
ak = chroms[np.argmax(probs_cum)]
np.delete(chroms,np.argmax(probs_cum))
# 修改代码处
newX = np.array([chroms[np.where(probs_cum > rand)[0][0]]
for rand in each_rand])
# 繁殖，随机配对（概率为0.6)
# 6这个数字怎么来的，根据遗传算法，假设有10个数，交叉概率为0.6，0和1一组，2和3一组。。。8和9一组，每组扔一个0到1之间的数字
# 这个数字小于0.6就交叉，则平均下来应有三组进行交叉，即6个染色体要进行交叉
pairs = np.random.permutation(
int(len(newX)*prob//2*2)).reshape(-1, 2) # 产生6个随机数，乱排一下，分成二列
center = len(newX[0])//2 # 交叉方法采用最简单的，中心交叉法
for i, j in pairs:
# 在中间位置交叉
x, y = newX[i], newX[j]
newX[i] = x[:center] + y[center:] # newX的元素都是字符串，可以直接用+号拼接
newX[j] = y[:center] + x[center:]
# 修改代码处
np.append(newX,ak)
# 修改代码处
return newX