简单遗传算法优化简单一元函数(python)

👉待优化函数

本文待优化函数选取自《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$的二进制编码符号串来表示该参数，则它总共能够产生 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:bl​bl−1​bl−2​...b2​b1​

则对应的解码公式为： 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=1l​bi​⋅2i−1)⋅2l−1Umax​−Umin​​

而 ∑ i = 1 l b i ⋅ 2 i − 1 \sum_{i=1}^l b_i \cdot 2^{i-1} ∑i=1l​bi​⋅2i−1 正是二进制对应的十进制数。

👉程序及运行结果

关于遗传算法各阶段运算，包括选择（复制）运算、交叉运算、变异运算均有不同的实现，本文代码参考了《遗传算法原理及应用》附录中C语言实现的简单遗传算法，有兴趣的读者可以对以上各阶段运算尝试其他的实现方式。
代码如下：

import math
import random
import copy
import matplotlib.pyplot as pltPI = 3.1415926
# 个体长度
CHROM_LEN = 20
# 种群大小
POP_SIZE = 40
CMIN = 0
# 最大遗传代数
MAX_GENERATION = 40
# 交叉概率
PC = 0.7
# 变异概率
PM = 0.01# 优化函数
def F(x):return math.sin(10 * PI * x) / x# 解码器
def decode(chrom, lb, ub):# 二进制对应的十进制数temp = int(chrom, 2)# 最终解码值x = lb + temp * (ub - lb) / (math.pow(2, CHROM_LEN) - 1)return x# 个体类
class Individual:def __init__(self):temp = []for _ in range(CHROM_LEN):temp.append(random.randint(0, 1))self.chrom = "".join([str(t) for t in temp])self.fitness = 0# 计算个体适应度def get_fitness(self, lb, ub):x = decode(self.chrom, lb, ub)value = -F(x) + CMINself.fitness = max(0, value)return self.fitnessdef __str__(self):return "chrom:{}, fitness:{}".format(self.chrom, self.fitness)# 获得当代最佳和最差个体索引
def best_and_worst(population):# 最佳个体索引best_idx = 0# 最差个体索引worst_idx = 0for _idx, p in enumerate(population):if p.fitness > population[best_idx].fitness:best_idx = _idxelif p.fitness < population[worst_idx].fitness:worst_idx = _idxreturn best_idx, worst_idx# 选择（复制）操作
def select(population):# 新种群new_pop = []# 当代个体适应度总和fitness_sum = max(sum([i.fitness for i in population]), 0.0001)# 当代个体累计适应度占比cfitness = []# 计算相对适应度占比for j in range(POP_SIZE):cfitness.append(population[j].fitness / fitness_sum)# 计算累计适应度占比for j in range(POP_SIZE):if j == 0:continuecfitness[j] = cfitness[j-1] + cfitness[j]# 依据累计适应度占比进行选择复制，随机数大于对应的累计适应度占比，则进行复制for k in range(POP_SIZE):index = 0while random.random() > cfitness[index]:index += 1# 若无法找到要复制的其他个体，则沿用当前个体if index >= POP_SIZE:index = kbreaknew_pop.append(copy.deepcopy(population[index]))return new_pop# 交叉操作
def crossover(population):# 随机产生个体配对索引，类似于洗牌的效果index = [i for i in range(POP_SIZE)]for i in range(POP_SIZE):point = random.randint(0, POP_SIZE - i - 1)temp = index[i]index[i] = index[point + i]index[point + i] = tempfor i in range(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_gene2population[index[i + 1]].chrom = population[index[i + 1]].chrom[0: cross_start] + cross_gene1# 变异操作
def mutation(population):for individual in population:# 初始化新染色体new_chrom_ch = [c for c in individual.chrom]for i in range(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)# 绘制结果
def draw_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)# 绘制进化过程
def draw_evolution(evolution):x = [i for i in range(len(evolution))]plt.plot(x, evolution)plt.show()# plt.savefig('sga_evolution.png', dpi=800)def main():# 种群population = []# 下界lb = 1# 上界ub = 2# 初始化种群for _ in range(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 in range(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

待优化函数及最优解如下图所示：

每一代最优解的进化过程如下图所示（由于初始种群的随机性，每一次执行产生的结果可能会不同）：

搜索最优解的动态图如下图所示（由于初始种群的随机性，每一次执行产生的结果可能会不同）：

👉问题

由于初始种群的随机性，每一次得到的最优解可能会稍有差异，本文代码有时会找不到全局最优解，稳定性有待提升，在此作者抛砖引玉，希望有实力的读者能进一步优化并留言

笔者水平有限，若有不对的地方欢迎评论指正

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！