基于自适应罚函数的改进遗传算法

[摘 要]遗传算法（Gnectic Algorithm，GA）是由60年代美国的Mcihigna大学的Hollnad教授首先提出。其原理是借助于自然演化原则和人工自适应系统的原则，通过模拟孟德尔的遗传理论以及达尔文的自然进化论从而创造出的求解极值问题的方法，但是基本遗传算法在全局最优收敛方面仍存在部分漏洞。本文将传统遗传算法改进，以便尽可能保留遗传过程中的最优解。

[关键词]遗传算法；算子；自适应罚数

作为一种搜索算法，虽然遗传算法可以通过优化过程中的各个环节进行适当的设计和操作从而实现全局和局部均衡的搜索，在某些问题上也达到了理想的效果，但是基本遗传算法在全局最优收敛方面仍存在部分漏洞。如最优解往往处于可行区域和不可行区域边界，而优化过程中很可能就把最接近最优解的那些个体规划入不可行解的区域从而淘汰掉。特别是应用于本文的非均匀信道增益优化以及功率控制的约束优化问题，在约束条件的制约下，如何高效率地搜索得到可行解以及最优解将是算法面临的首要问题。针对该问题，本文在基本遗传算法的基础上，设计了包含动态交叉变异算子、精英个体保存、自适应罚函数的改进遗传算法（modify Genetic Algorithm，mGA），并将其应用于柔性转发器的非均匀信道增益调整及功率控制优化问题。

一、动态交叉及变异算子及倒序算子

基本遗传算法中交叉概率和变异概率是恒定值的这一特点，往往会使某些优化问题提前陷入早熟的境地，从而影响算法收敛性，降低算法的搜索效率。为此本文引入了交叉概率和变异概率随种群变化的动态交叉及变异算子，能够在一定程度上提高优化算法的收敛速度和运行效率。

动态交叉算子中，采用多点交叉和均匀交叉两种基本的基因操作，随着进化次数的增加，逐步均匀交叉的概率；多点交叉的意思是在基因交叉过程中，设定多个交叉点进行交叉运算，该算法中选择交叉点数为决策变量的两倍；均匀交叉即一致交叉，就是在交叉过程中两个配对的个体基因都以相同的概率进行交换，从而形成新的个体。在交叉过程中，首先生成一个与个体染色体长度一致的屏蔽字，屏蔽字每一位只有0和1两种选择，然后个体根据屏蔽字分别选择对应位的父代基因，进而完成交叉。

倒序基因操作通过选取少量的个体中的某段染色体进行倒序处理，从而使得算法获得更加广泛的搜索能力，一定程度地降低算法早熟概率，其有着和变异类似的机理，只是处理的染色体段并不做内容的改变，而是顺序的调整。

二、精英个体保留

在求最优解的搜索过程中，由于受到各个运算过程随机性的影响，通过交叉、变异运算产生新个体的过程中存在一定概率的破坏性，如破坏掉当前群体中适应度最优解的个体，这样会导致整个群体的平均适应度的大幅度降低，并且对遗传算法的运行效率产生不利的影响，故为了避免此类现象发生，使得种群中最优的个体能够完整地遗传给下一代，算法设计了精英个体的保留操作。由于本文针对的是约束优化问题，某一代的最优解并不一定是可行解，对于不可行解的最优保存并不在基本遗传算法的设计范围，故本文针对性地设计了包含约束问题的精英保留操作如下：1、如果种群中存在可行解，找到可行解最小的个体，将其随机地替换子代的某个个体；2、如果种群中无不可行解，找到约束违反最小的解集，随机选取一个替换子代的某个个体。实施最优保存策略是保证遗传算法收敛的重要保证，对不可行解的随机选择而不是选择相同条件下目标函数最小的值是一定程度上在搜索前期尽量扩大搜索的范圍，对约束边界的适应性更强，也使得算法不易陷入局部最优。

三、自适应罚函数

在实际的工程实践中，一般情况下，优化算法问题往往存在着各种约束条件，最优解的首要条件是要满足各种约束条件，才能规划进可行解范畴。

对于优化算法中的约束问题的处理，目前主要的方法包括：拒绝法、修补方法和罚函数方法。其中拒绝方法是指丢弃进化过程中所有不可行解，显而易见，该方法运行效率低下。修补方法将不可行个体进行修补成为可行解，其往往受到优化问题的制约，对于组合问题容易使用，而大多数问题，修补往往难以实施。罚函数方法是最为常用和典型的约束处理方法，该方法通过对不可行解的目标函数值进行修改，加入一定的惩罚量，从而使其一定程度地劣于可行个体，进而使得搜索算法向可行解的方向搜索。罚函数的优点在于在种群中有了一定数量的不可行解，从而使得搜索从可行区域和不可行区域两个方向搜索最优解，有利于提高搜索效率。罚函数的罚因子设计一直是罚函数设计的难题，如何确定惩罚项，从而使得算法在选择压力（拒绝一些不可行解）和信息保留（保持一些不可行解）之间保持良性的平衡，避免过度惩罚或者惩罚不足的现象出现。

通常罚因子参数设定非常困难，其值的大小，将直接影响搜索，所以针对罚因子设计的困难，本文采用了一种无需设定任何参数的自适应罚函数方法，该方法通过种群中的不可行比例动态调整惩罚的大小。算法的思想是约束优化问题的最优解往往处于可行区域和不可行区域边界，不可行个体携带了大量的有利于搜索最优解的信息，利用好该信息将有助于算法的搜索。当种群中出现不可行个体数目较多的时候，加大对不可行个体的惩罚力度，使得算法搜索方向指向可行解区域；而当种群中可行解个数较多，适当降低不可行个体的惩罚力度，有利于发掘不可行个体所携带的信息，使得算法从不可行区域向最优解搜索。

作者简介：曹强（1967-），男，浙江嘉兴人，武警士官学校教授，研究方向：船舶轮机、船舶通信技术。endprint