【遗传算法】

一、基本介绍

1.概念

遗传算法(genetic algorithm，GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。最早由美国Michigan大学Holland教授提出，起源于60年代对自然和人工自适应系统的研究。

2.相关术语

染色体(chromosome)：又称为基因个体(individuals)，一定数量的个体组成了群体(population).
基因(gene):用于表达个体的特征。例如有一个串S=1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(alleles)。
基因位点(locus)：在算法中表示一个基因在串中的位置，称为基因位置(gene position).
特征值(feature):基因的特征值与二进制数的权一致。例如，在串S=1011中，基因位置为3中的1，它的基因特征值为2.
适应度(fitness):各个个体对环境的适应环境的适应程度称为适应度。为体现染色体的适应能力，引入了对每一个染色体都能进行度量的函数，叫适应度函数。

3.特点

①以决策变量的编码作为运算对象。
②直接以目标函数值作为搜索信息。
③同时使用多个搜索点的搜索信息。
④使用概率搜索技术。

二、主要运算过程

1.运算过程

步骤一：初始化。
步骤二：个体评价。计算各个个体的适应度。
步骤三：选择运算。把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。其中轮盘赌选择法是最简单也最常用的选择方法，该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为$n$，其中个体$i$的适应度为$f$，则$i$被选择的概率为$p_i=\frac{f_i}{\sum _{j=1}^n{f}_i}$
步骤四：交叉运算。是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。根据编码表示方法的不同有以下几种算法：
①实值重组；②二进制交叉。最常用的交叉算子为二进制交叉中的单点交叉，即在个体串中随机设定一个交叉点，实行交叉时，该点前后两个个体的部分结构进行交换，并生成个新个体。全局随机搜索
步骤五：变异运算。对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变。群体$P(t)$经过选择、交叉、变异运算之后得到下一代群体$P(t+1)$。局部随机搜索
终止条件判断：三种情况下终止：①以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。②最优个体的适应度达到给定的阈值。③迭代次数达到预设的代数时，算法终止。

2.MATLAB工具箱

1.ga函数
对目标函数进行遗传计算，其格式如下：

%fitnessfun:适应度句柄函数
%nvars:目标函数自变量的个数
%options:算法属性设置
%fval:最佳染色体的适应度
%exitflag:算法停止的原因
%output:输出的算法结构
%population:最终得到种群适应度的列向量
%scores:最终得到的种群
[x,fval.exitflag,output,population,scores] = ga(fitnessfcn,nvars,...options)

2.gaoptimset函数
设置遗传算法的参数和句柄函数。

3.gaotimget函数
用于得到遗传算法参数结构中的参数具体值，其调用格式如下：

%options:结构体变量
%name:需要得到的参数名称，返回值为val
val = gaotimget(options, 'name')

三、应用

1.求解TPS问题。
2.求解优化。
3.求解函数极值。

参考资料：1.MATLAB智能算法. 温正，孙华克
2.MATLAB智能优化算法——从写代码到算法思想. 曹旺
3.遗传算法原理及应用. 周明，孙树栋