Matlab下遗传算法的优化运用——展示为多维影像

1 基本概念1.1基本算法原理1.2 比较对应1.3理论支持 2 具体算法流程2.1 染色体的编码2.2 群体初始化2.3 适应值评价2.4选择算子2.5 交配算子(杂交算子)2.6 变异算子2.7 算法流程 3Matlab环境下的遗传算法多维展示①主函数GA.m②求适应值③ 开始遗传迭代（轮盘赌选择）④ 采用单点交叉，交配算子⑤变异算子⑥ 输出

1 基本概念

借鉴自然进化的理念，问题优化的过程可以看成类似于生物进化的过程，通过模拟自然界的生物进化，研究者提出了一种解决优化问题的创造性方法———GA遗传算法。

1.1基本算法原理

GA算法最开始为一种随机自适应的全局搜索算法。 遗传算法正是通过模拟自然界中生物的遗传进化过程，对优化问题的最优解进行搜索。算法维护一个代表问题潜在解的群体，对于群体的优化，算法引入了类似自然进化中选择、交配、以及变异算子。遗传算法搜索全局最优解的过程是一个不断迭代的过程，每一次迭代相当于生物进化中的一次循环，直到满足算法的终止条件为止。

在遗传算法中，问题的每个有效解被称为一个“染色体”，在有些书籍中也称为“串”，相对于群体中每个生物个体，染色体的具体形式是一个使用特定编码方式生成的串，编码串中的每一个编码单元称为基因。

1.2 比较对应

1.3理论支持

①模式定理

对于遗传算法，Holland给出了著名的模式定理，为遗传算法提供了理论支持。

模式： 是指群体中编码的某些位置具有相似结构的染色体集合。这边可用0或1组成的二进制符号序列作为染色体的编码。其中如： 模式01 x x x 0 则表示以01开头且0结尾的编码串对应的染色体的集合。

阶： 模式中具有确定取值的基因个数，如0 1 x x x 0 的阶为3。

模式定义长度： 是指模式中第一个具有确定取指的基因到最后一个具有确定取值的基因的距离，上例为5。 而x 1 x x x x 定义长度为0.

该定理指出，遗传算法的实质是通过选择、交配、变异算子对模式进行搜索，缔结定义长度较小且平均适应高于群体平均适应值的模式在群体中方的比例将呈现指数级增长，即随着精华的不断进行，教优染色体个数将快速增加。模式定理证明了遗传算法寻求全局最优解的可能性，但是不能抱枕算法一定能找到全局最优解，Goldberg提出的积木块假设，能对该定理做出补充，说明遗传算法具有能找到全局最优解的能力。

2 具体算法流程

遗传算法的实现主要包含以下七个重要问题：

染色体的编码；躯体的初始化；适应值评价；选择种族；种族交配；群体变异；算法流程；

2.1 染色体的编码

目前用于染色体编码的方式有格雷码编码，字母编码，多参数交叉编码。这里我们采用两种较为简单的编码：二进制编码和浮点数（实数）编码。其中二进制编码较为简单，但是在编码精度方面较差，史书编码方式适合于表示取值范围比较大的数值，用于多维函数优化问题，效果较为突出，对降低采用遗传算法对染色体进行处理的复杂性起到了很好的作用。

2.2 群体初始化

遗传算法在一个给定的初始进化群体进行迭代搜索，一般情况下遗传算法在躯体初始化阶段采用的是随机数初始方法的。

2.3 适应值评价

评估函数用于评估各个染色体的适应值，进而区分优劣。具体问题时，可以套用问题定义的函数表达式。例如求解某个函数的最小值可以对问题定义的目标函数F（x）进行以下变化得到算法的评估函数Eval（C）。

Eval（c）= -f（x） 其中x表示一个有效解，c表示x对应的染色体

适应值会出现两种情况，一种时极小情形即院十适应值越小个体性能越好，另一种反之。 遗传算法中某些选择策略则要求适应函数时非负的，而且适应值越大表明个体的性能越好。

2.4选择算子

种群的选择使用轮盘赌选择算法该算法是遗传算法最经常使用的选择算法，基本思想是给予概率的随机选择。不同的选择策略将 导致不同的选择压力，即下一代附带个体的复制数目的不同分配关系。

轮盘赌选择算法 首先根据群体中每个染色体的适应值得到群体中所有染色体的适应值综合，并且分别计算每个染色体适应值于群体适应值总和的比Pi即所占总体的百分比，将一个圆盘分为若干份，对应成正比关系。 每次转动轮盘表示一次选择，，依次进行N次选择即可得到规模同样为N的种群。 以下为轮盘转动的伪代码:

FUNCTION RWS M->0; R->random(0,1); for i=0 to N M->M+Pi; if R<=M return i; end if end for end FUNCTION

从以上机制可以看出，较优染色体的P值较大，被选择的概率就相对较大，但是由于选择过程具有随机性，不能每次都选中较优染色体，因此给予了较差染色体的生存空间。

2.5 交配算子(杂交算子)

杂交运算是指对两个相互匹配的染色体按某种方式相互交换其部分基因而形成两个新的个体。 ① 单点杂交：称为简单杂交，它指在个体编码串中值随机设计一个杂交点，然后再该店互换两个配对个体的部分染色体。

如下： 0110 1 0110 0 ————> 1100 1 1100 1

②双点杂交与多点杂交 双点杂交是指再个体编码串中设置了两个杂交点，然后再进行基因交换。

③均匀杂交 均匀杂交是指两个配对个体每一个基因座上的基因都以相同的杂交概率进行交换，从而形成两个新的个体。均匀杂交实际上可归属多点杂交的范围。

2.6 变异算子

染色体的变异作用于基因上，对于交配后新中去中染色体的每一位基因根据变异概率Pm判断该基因是否进行变异。实际运用中可适当降低变异率，目的是为了保持遗传算法较好的运行性能。一般设置在0.001~0.1之间。遗传算法中使用变异算子主要偶以下两个目的： 1）改善遗传算法的局部搜索能力。 2）维持群体的多样性，防止出现早熟现象。

2.7 算法流程

初始化规模为N的群体，其中染色体每个基因的值采用随机数产生器生成并满足问题定义的范围，当前进化代数Generation为0。采用评估函数对群体中所有染色体进行评价，分别计算每个染色体的适应值，保存适应值最大的染色体Betst。采用轮盘赌选择算法对群体的染色体进行选择操作产生规模同样的为N的种群。按照概率Pc从种群中选择染色体进行交配，每两个进行交配的附带染色体，交换部分基因产生两个新的子代染色体，子代染色体取代父代染色体进入新种群。没有进行交配的染色体直接复制进入新的种群。按照概率Pm对新种群中染色体的基因进行变异操作，发生变异基因数值发生改变。变异后的染色体取代原有染色体进入新群体，未发生变异的染色体直接进入新群体。变异后的新群体取代原有群体，重新计算群体中各个染色体的适应值，倘若群体的最大适应值大于Best的适应值，则以该最大适应值对应染色体替代Best。当前进化代数Generation加1，如果Generation超过规定的最大进化代数或B二十天达到规定的误差要求，算法结束 否则返回第三步。

3Matlab环境下的遗传算法多维展示

①主函数GA.m

设置初始化参数

②求适应值

选择评估函数，进行适应值评价 其中运用到三种优化函数

RastriginSchafferGriewank 1）griewank

2）Rastrigin 3） Schaffer

③ 开始遗传迭代（轮盘赌选择）

随机选取进行交配的算子。

④ 采用单点交叉，交配算子

⑤变异算子

⑥ 输出

输出函数绘制代码如下： 结果如下图所示： 迭代五百次后逐渐趋于稳定。