👉待优化函数
本文待优化函数选取自《MATLAB智能算法30个案例分析（第2版）》中的第一个案例
利用遗传算法计算以下函数的最小值：
f
(
x
)
=
sin
(
10
π
x
)
x
，
x
∈
[
1
,
2
]
f(x) = \frac{\sin(10 \pi x)}{x}，x\in[1,2]
f(x)=xsin(10πx)，x∈[1,2]
👉遗传算法流程
关于遗传算法的原理，书籍和文章均比较多，这里就不再赘述，这里给出简单遗传算法的流程
👉编码
这里着重说明一下编码方式，本文算法采用二进制编码。假设某一参数的取值范围是
[
U
m
i
n
，
U
m
a
x
]
[U_{min}，U_{max}]
[Umin，Umax]，我们用长度为
l
l
l的二进制编码符号串来表示该参数，则它总共能够产生
2
l
2^l
2l种不同的编码，若使参数编码时的对应关系如下:
则二进制编码的编码精度为：
δ
=
U
m
a
x
−
U
m
i
n
2
l
−
1
\delta = \frac{U_{max} - U_{min}}{2^l - 1}
δ=2l−1Umax−Umin
假设某一个体的编码是：
X
:
b
l
b
l
−
1
b
l
−
2
.
.
.
b
2
b
1
X: b_lb_{l-1}b_{l-2}...b_2b_1
X:blbl−1bl−2...b2b1
则对应的解码公式为：
x
=
U
m
i
n
+
(
∑
i
=
1
l
b
i
⋅
2
i
−
1
)
⋅
U
m
a
x
−
U
m
i
n
2
l
−
1
x=U_{min}+(\sum_{i=1}^l b_i \cdot 2^{i-1})\cdot \frac{U_{max}-U_{min}}{2^l - 1}
x=Umin+(∑i=1lbi⋅2i−1)⋅2l−1Umax−Umin
而
∑
i
=
1
l
b
i
⋅
2
i
−
1
\sum_{i=1}^l b_i \cdot 2^{i-1}
∑i=1lbi⋅2i−1 正是二进制对应的十进制数。
👉程序及运行结果
关于遗传算法各阶段运算，包括选择（复制）运算、交叉运算、变异运算均有不同的实现，本文代码参考了《遗传算法原理及应用》附录中C语言实现的简单遗传算法，有兴趣的读者可以对以上各阶段运算尝试其他的实现方式。
代码如下：
import math
import random
import copy
import matplotlib.pyplot as plt
PI =3.1415926# 个体长度
CHROM_LEN =20# 种群大小
POP_SIZE =40
CMIN =0# 最大遗传代数
MAX_GENERATION =40# 交叉概率
PC =0.7# 变异概率
PM =0.01# 优化函数defF(x):return math.sin(10* PI * x)/ x
# 解码器defdecode(chrom, lb, ub):# 二进制对应的十进制数
temp =int(chrom,2)# 最终解码值
x = lb + temp *(ub - lb)/(math.pow(2, CHROM_LEN)-1)return x
# 个体类classIndividual:def__init__(self):
temp =[]for _ inrange(CHROM_LEN):
temp.append(random.randint(0,1))
self.chrom ="".join([str(t)for t in temp])
self.fitness =0# 计算个体适应度defget_fitness(self, lb, ub):
x = decode(self.chrom, lb, ub)
value =-F(x)+ CMIN
self.fitness =max(0, value)return self.fitness
def__str__(self):return"chrom:{}, fitness:{}".format(self.chrom, self.fitness)# 获得当代最佳和最差个体索引defbest_and_worst(population):# 最佳个体索引
best_idx =0# 最差个体索引
worst_idx =0for _idx, p inenumerate(population):if p.fitness > population[best_idx].fitness:
best_idx = _idx
elif p.fitness < population[worst_idx].fitness:
worst_idx = _idx
return best_idx, worst_idx
# 选择（复制）操作defselect(population):# 新种群
new_pop =[]# 当代个体适应度总和
fitness_sum =max(sum([i.fitness for i in population]),0.0001)# 当代个体累计适应度占比
cfitness =[]# 计算相对适应度占比for j inrange(POP_SIZE):
cfitness.append(population[j].fitness / fitness_sum)# 计算累计适应度占比for j inrange(POP_SIZE):if j ==0:continue
cfitness[j]= cfitness[j-1]+ cfitness[j]# 依据累计适应度占比进行选择复制，随机数大于对应的累计适应度占比，则进行复制for k inrange(POP_SIZE):
index =0while random.random()> cfitness[index]:
index +=1# 若无法找到要复制的其他个体，则沿用当前个体if index >= POP_SIZE:
index = k
break
new_pop.append(copy.deepcopy(population[index]))return new_pop
# 交叉操作defcrossover(population):# 随机产生个体配对索引，类似于洗牌的效果
index =[i for i inrange(POP_SIZE)]for i inrange(POP_SIZE):
point = random.randint(0, POP_SIZE - i -1)
temp = index[i]
index[i]= index[point + i]
index[point + i]= temp
for i inrange(0, POP_SIZE,2):if random.random()> PC:# 随机选择交叉开始位置
cross_start = random.randint(0, CHROM_LEN -2)+1# 需要交换的基因
cross_gene1 = population[index[i]].chrom[cross_start:]
cross_gene2 = population[index[i +1]].chrom[cross_start:]# 交叉操作
population[index[i]].chrom = population[index[i]].chrom[0: cross_start]+ cross_gene2
population[index[i +1]].chrom = population[index[i +1]].chrom[0: cross_start]+ cross_gene1
# 变异操作defmutation(population):for individual in population:# 初始化新染色体
new_chrom_ch =[c for c in individual.chrom]for i inrange(CHROM_LEN):# 随机数小于变异概率，则进行变异操作if random.random()< PM:
new_chrom_ch[i]="1"if individual.chrom[i]is"0"else"0"# 更新染色体
individual.chrom ="".join(new_chrom_ch)# 绘制结果defdraw_result(best):import numpy as np
# 绘制优化函数
x = np.linspace(1,2,100)
y =[F(_x)for _x in x]
plt.plot(x, y)# 绘制最优解
best_x = decode(best.chrom,1,2)
best_y = F(decode(best.chrom,1,2))
plt.scatter(best_x, best_y, s=100, c='red', marker='*', zorder=2)
plt.show()# plt.savefig('sga_result.png', dpi=800)# 绘制进化过程defdraw_evolution(evolution):
x =[i for i inrange(len(evolution))]
plt.plot(x, evolution)
plt.show()# plt.savefig('sga_evolution.png', dpi=800)defmain():# 种群
population =[]# 下界
lb =1# 上界
ub =2# 初始化种群for _ inrange(POP_SIZE):
population.append(Individual())# 计算初始种群适应度for individual in population:
individual.get_fitness(lb, ub)# 初始种群最佳和最差个体
best_idx, worst_idx = best_and_worst(population)# 历史最佳个体
current_best = population[best_idx]# 进化过程，每一代的最佳个体的函数值
evolution =[]# 循环直到最大代数for generation inrange(MAX_GENERATION):# 选择复制
population = select(population)# 交叉
crossover(population)# 变异
mutation(population)# 重新计算适应度for individual in population:
individual.get_fitness(lb, ub)# 当代种群最佳和最差个体索引
best_idx, worst_idx = best_and_worst(population)# 利用精英模型执行进化操作，用历史最佳个体代替当代的最差个体if population[best_idx].fitness > current_best.fitness:
current_best = population[best_idx]else:
population[worst_idx]= current_best
# 更新进化过程
evolution.append(round(F(decode(current_best.chrom,1,2)),4))# 绘制进化过程# draw_evolution(evolution)# 绘制结果
draw_result(current_best)# 打印最佳结果print("X = {}".format(round(decode(current_best.chrom,1,2),4)))print("Y = {}".format(round(F(decode(current_best.chrom,1,2)),4)))if __name__ =="__main__":
main()
代码输出最优解为：
X = 1.1491
Y = -0.8699
待优化函数及最优解如下图所示：
每一代最优解的进化过程如下图所示（由于初始种群的随机性，每一次执行产生的结果可能会不同）：
搜索最优解的动态图如下图所示（由于初始种群的随机性，每一次执行产生的结果可能会不同）：
👉问题
由于初始种群的随机性，每一次得到的最优解可能会稍有差异，本文代码有时会找不到全局最优解，稳定性有待提升，在此作者抛砖引玉，希望有实力的读者能进一步优化并留言
笔者水平有限，若有不对的地方欢迎评论指正
本文转载自: https://blog.csdn.net/weixin_37522117/article/details/124964482
版权归原作者 肥猪猪爸 所有， 如有侵权，请联系我们删除。
版权归原作者 肥猪猪爸 所有， 如有侵权，请联系我们删除。