利用遗传算法解决函数最优化问题
一、问题描述
利用遗传算法求解一些典型的二元函数优化问题,对五个二元最优化函数(函数表达式、决策变量取值范围)进行求解,结果要尽可能精确。
五个函数分别为:
二维球形函数:,
De-Jong函数:,
Himmelblau函数: ,
SIX-HUMP CAMEL函数:,
BOHACHEVSKY函数: ,
二、解决思路和方案
遗传算法是一种借鉴生物界自然选择和遗传机制的随机化搜索最优解的算法。它模拟自然选择和遗传过程中发生的环境选择、有性繁殖和基因突变现象,在每次迭代都从种群中选取较优的个体,利用交叉算子和变异算子使个体发生交叉(产生新个体的主要方式)和变异(产生新个体的辅助方式,有利于跳出函数的局部最优解),产生适应性更好(使函数更加最优解)的新一代种群,重复此过程,直到满足某种收敛指标为止。应用遗传算法需确定的几个主要内容是:初始种群的产生、适应度函数的确定、遗传算子(选择、交叉、变异)的确定、终止条件。
(1)初始种群的产生
产生初始种群的编码采取二进制编码方式,在产生初始种群之前,要确定染色体的基因数目,这是由算法想达到的精度决定的,如果要求最终求得的决策变量精确为5(精确到小数点后五位),根据公式,即可确定该决策变量需要的基因数,其中 和 为该决策变量取值的上下界,一个个体所需的基因数目为所有决策变量对应的之和。
在基因数目确定了之后,即可产生初始种群,采取二进制编码随机生成的方式,
(2)适应度函数
适应度评价函数反映了个体对环境的适应能力,在以上几个最小化的函数中,f函数值越小说明其适应能力越强。为了符合常规习惯,将求 f 最小值的问题转化为求 -f 的最大值,那么适应度评价函数即为 -f, 其值越大,适应能力越强,越应该被保留。
(3)遗传算子的确定
对于选择步骤,采取轮盘赌选择,其思想是适应度更大的个体更大概率会被保留。另外加入了精英保留策略,即每次选择时都将适应度最高的个体保留下来不淘汰,这样可以优化种群质量,提升收敛速度。
对于交叉步骤,采用单点交叉方式,交叉算子设置为0.75,交叉是针对个体而言的,如果随机产生的概率小于0.75,则该个体可以参与交叉,随机与另外一个个体交叉,生成新的子代。
对于变异步骤,采用单点变异,变异算子设置为0.01,变异是针对染色体的每个基因而言的,如果随机产生的概率小于0.01,则该基因位发生变异,0和1互换。
(4)终止条件
首先设置了一个进化代数的上下限,最多迭代1000代,最小100代。另外,如果持续很多代最优值的改善幅度很小,便会提前终止,在算法执行时间和精确性之间取得了一个平衡。这里,如果持续200代最优值的改善幅度不超过1e-6(10^-6)便提前终止。
使用python语言进行仿真实现,求解每个最优化函数的最优解和对应的决策变量值,并可视化进化代数和最优值的关系。决策变量的精度为5,目标变量精度为6。
三、仿真结果及分析
(1)函数 f1 仿真结果
函数 ,在迭代了307代后收敛,图3.1为迭代结束后的结果展示,在x=-0.00049,y=0.00285处取得了最优值8e-06,基本收敛到精确解0。其他函数同,其他函数便不进行解释,只进行结果展示。
图3.1 f1 求解结果
图3.2可视化了函数 f1 和x, y之间的关系,红点表示最后函数收敛到了最小。其他函数同。
图3.2 f1 可视化
图3.3表示了随着进化代数的增加,“当代最优值”(绿色曲线)和“目前为止最优值”(红色曲线)的变化情况,可以看出,红色曲线始终在绿色的下方,说明最优值不会变差,当代最优值虽有波动,但整体来看,也在变好。并且,图中每隔50代标注了目前为止的最优值(具体数值见表3.1),可以看出,随着代数的增加,最优值的改善不会很明显,同时函数也基本收敛。其他函数同。
图3.3 f1 进化代数-最优值变化图
表3.1 f1 进化代数-最优值变化表
进化代数 | 1 | 51 | 101 | 151 | 201 | 251 | 301 |
---|---|---|---|---|---|---|---|
最优值 | 0.247035 | 0.001725 | 1.2e-05 | 8e-06 | 8e-06 | 8e-06 | 8e-06 |
(2)函数 f2 仿真结果
函数 ,
图3.4 f2 求解结果
图3.5 f2 可视化
图3.6 f2 进化代数-最优值变化图
表3.2 f2 进化代数-最优值变化表
进化代数 | 1 | 51 | 101 | 151 | 201 |
---|---|---|---|---|---|
最优值 | 1.418274 | 0.00648 | 0.00648 | 0.00518 | 0.002211 |
进化代数 | 251 | 301 | 351 | 401 | 451 |
最优值 | 0.000868 | 0.00085 | 0.00085 | 0.00085 | 0.00085 |
(3)函数 f3 仿真结果
函数 ,
图3.7 f3 求解结果
图3.8 f3 可视化
图3.9 f3 进化代数-最优值变化图
表3.3 f3 进化代数-最优值变化表
进化代数 | 1 | 51 | 101 | 151 | 201 | 251 | 301 |
---|---|---|---|---|---|---|---|
最优值 | 37.36007 | 0.177718 | 0.177718 | 0.06862 | 0.021468 | 0.001839 | 0.001839 |
(4)函数 f4 仿真结果
函数 ,
图3.10 f4 求解结果
图3.11 f4 可视化
图3.12 f4 进化代数-最优值变化图
表3.4 f4 进化代数-最优值变化表
进化代数 | 1 | 51 | 101 | 151 | 201 | 251 |
---|---|---|---|---|---|---|
最优值 | -0.836399 | -1.029728 | -1.030549 | -1.030549 | -1.030549 | -1.031549 |
进化代数 | 301 | 351 | 401 | 451 | 501 | 551 |
最优值 | -1.031576 | -1.031617 | -1.031625 | -1.031625 | -1.031625 | -1.031625 |
(5)函数 f5 仿真结果
函数 ,
图3.13 f5 求解结果
图3.14 f5 可视化
图3.15 f5 进化代数-最优值变化图
表3.5 f5 进化代数-最优值变化表
进化代数 | 1 | 51 | 101 | 151 | 201 | 251 |
---|---|---|---|---|---|---|
最优值 | 0.261395 | 0.023016 | 0.005106 | 0.000206 | 0.0 | 0.0 |