Algorithm之OP:OP之GA遗传算法思路理解相关配图资料(二)-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

Algorithm之OP:OP之GA遗传算法思路理解相关配图资料(二)

简介: Algorithm之OP:OP之GA遗传算法思路理解相关配图资料

GA算法代码


1、伪代码


Procedure Genetic Algorithm

begin

   t  =  0  ;

   初始化  P(t)  ;

   计算  P(t)  的适应值  ;

   while  (不满足停止准则)  do begin

       t  =  t+1  ;

       从P(t-1)中选择  P(t)  ;  %selection

       重组  P(t)  ;       % crossover  and  mutation

   end

end


SGA实例讲解


1、求函数最值


求函数f(x)=x^2的最大值,x为自然数且0≤x≤31。


编码

编码方式:二进制码

   00000 ↔ 0;    01101 ↔    13;  11111 ↔ 31

随机初始群体 种群规模:4

 “转盘赌”选择

一点杂交,二进制变异



2、求连续函数的最值


求f ( x) = x sin(10π x) + 2.0  x ∈ [−1, 2]

image.png




Fitness.m文件

function [sol,eval]=fitness(sol,options)

   x=sol(1);

   eval = x*sin(10*pi*x)+2.0;

编码

实数问题:变量x为实数,如何把z∈[x,y] → {a1,…,aL} ∈{0,1}L

{a1,…,aL} ∈{0,1}L 必须可逆(一个表现型对应一个基因型) .

解码算子:Γ: {0,1}L  → [x,y]


染色体长度L决定可行解的最大精度。高精度  ⇄  长染色体(慢进化)

      设定求解精确到6位小数,因区间长度位2-(-1)=3,则需将区间分为 3X106等份。因 2097152=221< 3X106≤222=4194304。故编码 的二进制串长L=22。


比如:

<0000000000000000000000>    ↔ -1;

<1111111111111111111111>          ↔ 2

<1110000000111111000101>       ↔ 1.627 888

1.627888 = -1+3x(1110000000111111000101) 2 /(222-1) = -1+3x3674053/(222-1)

随机初始化种群  

适应度评估

适应函数

本实例目标函数在定义域内均大于0,且是求函数最大值, 故直接引用目标函数作为适应函数:

f(s) = f(x) 其中二进制串s对于变量x的值。

s1 =<0000001110000000010000> ↔ x1= -0.958 973       适应值: f(s1) = f(x1) =1.078 878

s2=<1110000000111111000101>    ↔ x2= 1.627 888       适应值: f(s2) = f(x2) = 3.250 650

 

选择操作(“轮盘赌”选择)

交叉操作(单点交叉)

交叉前(父):

         s1=<00000 | 01110000000010000>

         s2=<11100 | 00000111111000101>

交叉后(子):

         s’1=<00000 | 00000111111000101>

         s’2=<11100 | 01110000000010000>

适应值:    

        f(s’1) = f(-0.998 113) =1.940 865

        f(s’2) = f(1.666 028) = 3.459 245

s’2的适应值比其双亲个体的适应值高。


遗传算法的参数

种群规模: 50

染色体长度: L=22

最大进化代数: 150

交叉概率: Pc=0.25

变异概率: Pm=0.01

模拟结果

模拟结果(最佳个体进化情况)

image.png



3、无约束优化问题


image.png


GA编码

X=(x1,x2,…,xn)的各个变量可以按二进制编码方法分别编码。

对于变量xi 的上、下限约束li≤xi ≤ ui(i=1,2,…,n),依据解的精度要求(有效位数) 求得各个变量X=(x1,x2,…,xn)的二进制码位数(m1,m2,…,mn),确定方法 类似于SGA实例2,

因此将n个二进制位串顺序连接起来,构成一个个 体的染色体编码,编码的总位数m=m1+m2+…+mn。

GA解码

解码时仍按各个变量的编码顺序分别实现常规的二进制编码解码方法。

4、约束最优化问题




Matlab的实现之GAOT工具箱


1、核心函数:

(1) [pop]=initializega(num,bounds,eevalFN,eevalOps,options)-----初始种群的 生成函数

【输出参数】

pop-----生成的初始种群

【输入参数】

num-----种群中的个体数目

bounds-----代表变量的上下界的矩阵 eevalFN-----适应度函数

eevalOps-----传递给适应度函数的参数

options-----选择编码形式(浮点编码或是二进制编码)与精度,如 [type prec], type-----为1时选择浮点编码,否则为二进制编码

prec-----变量进行二进制编码时指定的精度,默认[1e-6 1]


(2) [x,endPop,bPop,traceInfo] =ga(bounds,evalFN,evalOps,startPop,opts,termFN,termOps,selectFN,…

selectOps,xOverFNs,xOverOps,mutFNs,mutOps)

-------遗传算法函数

 【输出参数】

x------求得的最优解

endPop------最终得到的种群

bPop------最优种群的一个搜索轨迹

traceInfo------每代种群中最优及平均个体构成的矩阵

 【输入参数】

bounds------代表变量上下界的矩阵 evalFN------适应度函数

evalOps------传递给适应度函数的参数 startPop------初始种群


【输入参数】

opts------- [epsilon prob_ops display],opts(1:2)等同于initializega的 options参数,第三个参数控制是否输出,一般为0。如[1e-6 1 0]

termFN-------终止函数的名称,如['maxGenTerm']

termOps-------传递个终止函数的参数,如[100] selectFN-------选择函数的名称,如['normGeomSelect'] selectOps-------传递个选择函数的参数,如[0.08]

xOverFNs-------交叉函数名称表,以空格分开,如['arithXover heuristicXover simpleXover']

xOverOps-------传递给交叉函数的参数表,如[2 0;2 3;2 0] mutFNs-------变异函数表,如['boundaryMutation

multiNonUnifMutation nonUnifMutation unifMutation']

mutOps-------传递给交叉函数的参数表,如[4 0 0;6 100 3;4 100 3;4 0 0]


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章