基于遗传算法的函数极值求解-Python与AI编程

函数优化

对于一个函数y=f(x)，当x在一定范围内取值时，函数可能存在最大值或者最小值，如下图所示的两个单变量函数，存在最小值，求取最小值的过程就是函数优化。

函数优化问题

传统的函数优化算法往往基于微积分进行求解，而启发式算法则另辟蹊径，它往往从一群初始解出发，通过对这些解周围的解空间不断地进行探索，从而找到更好的解，直到再也找不到更好的解为止。下面我们将使用一种常用的人工智能算法——遗传算法——对函数优化问题进行求解。

遗传算法的基本原理

大自然在漫长的历史中留下了那些能够适应环境的物种，这种进化方式被人工智能借鉴来建立优化算法，其中应用比较广泛的一种进化算法就是遗传算法。遗传算法基于达尔文的进化论，模拟了自然选择，即物竞天择、适者生存，将染色体设计为与问题的解相对应，通过染色体N代的遗传、变异、交叉、复制，进化出问题的最优解。

假设有这样一个数学问题：y=(x-8)2-1，当x在[10，30]取整数时，求取y的最小值。

与传统数学方法不同，遗传算法等进化算法的方式是生成一些随机解（种群），测试这些种群中每个染色体（对应一个解）的适应度（求取相应的y值，越小/大适应度越高），遗传算法进而对这些随机解进行一系列的操作。

例如，解采用二进制进行编码（1与0的数字串，一个串对应一个染色体，每一位都对应一个基因），新的解复制旧有的好的解并保留下来（选择复制），解与解之间进行部分位的交换（交叉），解的某些位发生变化（变异），这样经过一代又一代的进化，保留那些适应度高的解。

比如，在上面的例子中，我们把解编码为一个6位的二进制串，如010001，表示17（0×25+1×24+0×23+0×22+0×21+1×20=17）。一共生成4组解（种群数为4），经过计算适应度，保留前4组解，这4组解复制后进行交叉（部分位进行交换），例如000000与111111从中间进行切割交换，成为111000与000111，然后再经过小概率的变异，例如000111的最后一位发生变异，成为001110。

遗传算法的基本原理

一个完整的遗传算法的流程图如下。

遗传算法的流程图

编码就是将问题的解变成一个基因串（染色体），然后评估多个基因串的适应度，即代入相应的适应度函数，计算适应度值，这个适应度函数一般与所求问题相关，将优化问题转为适应度函数，优化问题的解就是最优的染色体。初始解产生后就进入选择、交叉和变异阶段。一般来说，为了在进化

基于GAFT的函数最优值寻找过程中能够不断地获得较好的解，每次选择时都会保留下那些适应度值较高的个体（例如前10%或20%），下一代的新个体可以直接复制这些好的个体，而被淘汰的个体空下的位置将通过好的个体之间进行交叉或者个体变异来获得补充。在选择时一般也并非直接选择适应度好的个体，而是通过一定概率进行选择，只是这个概率与个体的适应度相关，适应度越高，被选中的概率就越高，这就是常用的轮盘赌算法。变异指修改个别基因，与自然界的变异相同，这个操作一般仅对个别个体或者少量位置的基因进行改变，这既保证了当前个体的优势，也增加了个体的多样性，提高了搜索到全局最优解的可能性。

这里采用https://github.com/PytLab/gaft中上传的遗传算法库和例子来说明这类具有自我进化功能的人工智能如何解决问题。在GAFT中，设计者把固定的遗传算子、适应度函数写成接口，方便后续自定义算符和定制适应度函数。

下面就以一个一维函数作为例子，来使用GAFT对目标函数进行优化。

求f(x)=x+10sin(5x)+7cos(4x)的极大值，x的取值范围为[0,10]。

找到函数f(x)=x+10sin(5x)+7cos(4x)的最大值。

---------------------part 1 导入相关类---------------------

from math import sin,cos

#导入种群和内置算子相关类

from gaft import GAEngine

from gaft.components import BinaryIndividual

from gaft.components import Population

from gaft.operators import TournamentSelection

from gaft.operators import UniformCrossover

from gaft.operators import FlipBitMutation

#用于编写分析插件的接口类

from gaft.plugin_interfaces.analysis import OnTheFlyAnalysis

#内置的存档适应度函数的分析类

from gaft.analysis.fitness_store import FitnessStore

-------------------part 2遗传算法的设置-------------------

#定义种群

indv_template=BinaryIndividual(ranges=[(0,10)],eps=0.001)#范围[0,10]

population=Population(indv_template=indv_template,size=30).init()#种群数为30

#创建遗传算子

selection=TournamentSelection()#选择

crossover=UniformCrossover(pc=0.8,pe=0.5)#交叉

mutation=FlipBitMutation(pm=0.1)#变异(www.xing528.com)

#创建遗传算法引擎,分析插件和适应度函数可以参数的形式传入引擎中

engine=GAEngine(population=population,selection=selection,crossover=crossover,mutation=mut ation,analysis=[FitnessStore])

------------------part 3适应度函数的设置------------------

#定义适应度函数，可以通过修饰符@的方式将适应度函数注册到引擎中

#修饰符带的那个函数的入口参数engine.fitness_register就是下面的那个整个的函数fitness

@engine.fitness_register

def fitness(indv):

x,=indv.solution

return x+10＊sin(5＊x)+7＊cos(4＊x)

----------------part 4 调用遗传算法进行优化----------------

if'__main__'==__name__:

#Run the GA engine.

engine.run(ng=100)#ng为进化的代数

#绘制函数本身的曲线和使用遗传算法得到的进化曲线

from math import sin,cos

import numpy as np

import matplotlib.pyplot as plt

from best_fit import best_fit

steps,variants,fits=list(zip(＊best_fit))

best_step,best_v,best_f=steps[-1],variants[-1][0],fits[-1]

fig=plt.figure()

ax=fig.add_subplot(211)

f=lambda x:x+10＊sin(5＊x)+7＊cos(4＊x)

x=np.linspace(0,10,1000)

y=[f(i)for i in x]

ax.plot(x,y)

ax.scatter([best_v],[best_f],facecolor='r')

ax.set_xlabel('x')

ax.set_ylabel('y')

ax=fig.add_subplot(212)

ax.plot(steps,fits)

ax.set_xlabel('Generation')

ax.set_ylabel('Fitness')

#画出最优值

ax.scatter([best_step],[best_f],facecolor='r')

ax.annotate(s='x:{:.2f}\ny:{:.2f}'.format(best_v,best_f),xy=(best_step,best_f),xytext=(best_step-0.3,best_f-0.3))

plt.show()

一维函数优化结果