刘奕岑 徐蔚鸿 陈沅涛 马红华

摘  要：针对遗传算法在非线性系统优化问题中易陷入局部最优，且大量研究改进后仍存在不足的问题。根据混沌运动的结构特点，提出了一种解决非线性系统优化问题的混沌遗传算法（CGA，Chaos Genetic Algorithm）。该算法将混沌变量引入遗传算法的优化变量中，使两者的取值范围相互映射，利用更新后的混沌变量转换为“染色体”进行遗传操作，同时根据适应度大小选择需要附加混沌扰动的群体，使变异操作具有导向性，经过多次进化，得出问题的最优解。仿真实验利用多种测试函数和相似的智能优化算法进行对比验证。结果表明，该算法保证了非线性系统优化问题动态响应的速度和寻优结果的精度，定量的评价了混沌遗传算法的优化效果。

关键词：混沌运动;遗传算法;适应度函数;模糊神经网络;智能污水处理系统

中图分类号：TP393                                            文献标识码：A

Chaos Genetic Algorithm with Fitness Selection

Adjustment Strategy and Its Application

LIU Yi-cen1？覮，XU Wei-hong1，2，CHEN Yuan-tao1，MA Hong-hua3

（1.Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation，School of Computer &

Communication Engineering，Changsha University of Science and Technology，Changsha，Hunan 410114，China;

2. School of Computer Science and Engineering，Nanjing University of Science

and Technology，Nanjing，Jiangsu 210094，China;

3.Zixing Muncipal Bureau of Science and Technology of Hunan，Chenzhou，Hunan，423400，China）

Abstract：For genetic algorithm，it is easy to fall into the local optimum in the nonlinear system optimization problem，and there are still many problems in the research after the improvement. According to the structural characteristics of chaotic motion，a Chaos Genetic Algorithm （CGA） is proposed to solve the nonlinear system optimization problem. The algorithm introduces chaotic variables into the optimized variables of the genetic algorithm，maps the range of values of the two，and uses the updated chaotic variables to transform into "chromosomes" for genetic manipulation. At the same time，the chaotic disturbances are selected according to the size of the fitness. It makes the mutation operation oriented，and after many evolutions，the optimal solution of the problem is obtained. Simulation experiments use multiple test functions and similar intelligent optimization algorithms for comparison verification. The results show that the algorithm guarantees the speed of the dynamic response of the nonlinear system optimization problem and the accuracy of the optimization result，and quantitatively evaluates the optimization effect of the chaotic genetic algorithm.

Key words：chaotic motion;genetic algorithm;fitness function;fuzzy neural network;intelligent sewage treatment system

遺传算法以其算法独立性、强鲁棒性、全局选优性等特点，通过有目的性的随机搜索，被广泛应用于解决复杂的优化问题。如，遗传算法与蚂蚁算法的融合[1];利用遗传算法调节非均匀天线阵中的各项参数[2];受到遗传算法的启发，将跳跃基因加入目前最流行的多目标遗传算法--NSGA-Ⅱ，解决实际多目标优化问题[3]，等。然而，现实中需要解决的复杂问题往往是一些无规律的非线性系统优化问题，传统遗传算法在解决此类问题的过程中，各个阶段的遗传算子对应参数保持不变，容易陷入局部最优状态，且难以保存群体中的最优染色体，导致遗传算法过早收敛。针对不同类型的问题，前人已经提出了一系列改进的遗传算子。如，利用不同的遗传算子组合改进遗传算法在多播路由中的应用[4];循环遗传算子在质子交换膜燃料电池中的应用[5]。因此，利用遗传算法解决复杂问题的关键，便是找到合适的遗传算子及其控制参数。

利用混沌优化算法的结构特点和遗传算法相结合，提出了一种混沌遗传算法（CGA，Chaos Genetic Algorithm）。其基本思想是将混沌优化算法[6]融入传统遗传算法中，使混沌运动的遍历范围映射到优化变量的取值范围种[7]，保证整个过程的全局选优性。更新后的混沌变量进行编码操作，表示成“染色体”进行遗传操作。对于子代群体，选择适应度相对较小的部分附加随机扰动，通过多次进化，收敛到一个最优的个体上，求得问题的最优解。仿真实验利用多种测试函数和相似的智能优化算法进行对比验证，通过多种性能评价指标[8]，对混沌遗传算法的优化效率进行了定量研究，结果表明混沌遗传算法对于解决非线性系统优化问题有着明显的优势，在类似智能污水处理系统等一系列人工智能系统上的应用价值较大。

1   混沌优化算法的原理

混沌现象是指发生在确定性系统中貌似混乱，实则具有“随机性”、“遍历性”及“规律性”等特点[6]的一种运动，其普遍存在于非线性系统中，并在一定范围内能按其自身的"规律"不重复地遍历所有状态。在现实生活和实际工程技术问题中利用混沌的思想解决了大量的非线性系统问题，如基于布洛赫量子混沌算法的DNA编码设计[9];基于混沌算法的数字水印研究[10];基于遗传混沌优化算法的机器人轨迹规划方法[11]。因此，混沌现象是无处不在的。

混沌优化过程分为以下两个阶段进行：一、按照混沌优化算法的规律在变量的取值范围内遍历经过各点，找出当前最优解;二，在当前最优点为中心的小范围内进行选优，并附加适当的混沌扰动，进行微观搜索寻找全局最优解，混沌优化算法对新产生的当前最优解使用适应度函数重新进行评估，若产生的新最优解适应度值更加优异，则替代原最优解，否则不变，直到达到最大迭代次数或理想最优范围。此方法既可以解决遗传算法局部收敛过快的现象，又可以引导种群进化的方向。

根据混沌优化算法的遍历性来进行全局选优，根据Logistic映射的表达式：

x（n +1） = μx（n）[1 - x（n）]（1）

其中，n = 1，2，3，…，0 < x（0） < 1，0 < μ ≤ 4当μ = 4时，Logistic映射进入完全混沌状态。从理论上来说，经过足够大的迭代次数N时，才能遍历区间内的所有值。

混沌优化在实际问题所建立的优化模型中的应用主要表现在控制参数的优化。用混沌优化算法求解优化问题minf（X），寻优变量X一般都有一定的取值范围，故需构造混沌变量t与寻优变量X取值区间的映射关系，优化算法的使用式为：

xi = ci + di t  （2）

其中ci、 di是当混沌变量在区间[0，1]遍历时寻优变量xi均能在指定范围内变化的常向量。

2   具有适应度选择调整策略的混沌遗传

算法

2.1   传统遗传算法和混沌遗传算法对比

通过对传统混沌遗传算法[11]的分析可知，该算法主要是在遗传算法进行過一次变异操作之后，将新后代的编码映射到混沌变量中，使混沌变量从混沌空间变换到对应解空间中，利用混沌变量进行搜索，并对适应度函数进行重新评估得出优化结果，这样的方法增加了遗传算法的步骤，难以达到算法高效性的目的。而本文提出的混沌遗传算法CGA，在遗传算法构建染色体组时将混沌变量引入到优化变量中，把混沌变量线性映射到优化变量的取值区间上，利用更新后的混沌变量构建混沌染色体组进行遗传操作，根据适应度的大小选择需要附加混沌扰动的后代，通过多次迭代进化，得出问题的最优解。

2.2   相关系数的改进与确定

针对混沌搜索调节系数μ和空间变换系数 的错误选择会导致无法找到全局最优点的问题，本文在参考文献[12]的基础上对混沌优化算法进行改进，使系数μ和α随着算法的进行，动态发生变化，降低了两个参数对不同目标函数优化结果的影响。即按照如下方程进行反复迭代：

此时，设混沌区间为[0，1]，x*为当前最优解（x1*，x2*，…，xr*） 映射到[0，1]区间后形成的最优混沌向量;x（t）为迭代t次后的混沌向量，x（t）′为附加随机扰动后（x1，x2，…，xr）对应的混沌向量;搜索初期希望最优解在每一次迭代后的变动较大，故需要选择较大的μ（0 < μ < 1）。随着搜索的进行，最优解的取值逐渐趋于稳定，故需要选择较小的μ，使最优解在小范围内搜索。

由此可以看出，为了保证混沌优化算法在最优解附近进行微调，μ是一个与迭代次数有关的较小常数，且该常数不断减小，使寻优结果达到一定的精度，找到理想的最优解。根据以上思想，本文提出μ的具体公式如下，其中k为一正整数，依优化目标函数而定，t为迭代次数.：

随着算法的进行，搜索空间应不断缩小，其变化方法如式（5）所示，此时需用到空间变换系数α：

其中，mi（t）、 ni（t）分别为第i个混沌变量在第t次的混沌迭代时搜索空间的上限和下限。随着混沌优化算法的进行，搜索空间越来越小，此时α也应随之变小，保证搜索的精度。本文提出了α的定义公式，如式（6）所示：

从式（6）可以得出，随着搜索空间的缩小，α逐渐减小，且符合α∈[0，1]的要求。

2.3   混沌遗传算法的算法原理及流程

根据上述改进方案，设定部分参数：变量的取值范围[ai，bi]、种群规模M、算子交叉机率P1、P2和变异机率Pm。则搜索待优化参数xi的步骤如下：

1、选用合适的Logistic映射：

其中，i = 1，2，…，r、u = 0，1，…，M 分别为混沌变量和种群的序号;Ci为混沌变量，0≤Ci≤1;attr表示吸引子，当attr = 4时，进入完全混沌状态。初始化式（7）中混沌变量Ci（u）的r个初值，并得到M个初始解群。

2、将式（7）中得到的r个混沌变量Ci（u + 1）引入模型的优化函数（8）中，使混沌变量的取值范围与优化变量的取值范围相互映射，得到混沌变量xi′，其具体转换方法如式（9）：

max f（x1，x2，…，xr）（8）

xi′ = ki + hiCi（u + 1）（9）

X = （x1，x2，…，xr）（10）

X = （x1′，x2′，…，xr′）（11）

其中，ki、hi为转换常数，用来保证xi′可在指定的范围内变化。

3、令式 （8）为本次搜索的适应度函数，计算适应度值f（X′），由于f（X′）的非负属性且需使某一代群体相对变化较大，加快算法收敛速度，故对f（X′）按下式进行改进：

其中，ft（X′）、ft′（X′）分别为调整前后的适应度值，f（X′）max、 f（X′）min为调整前的最大、最小适应度值，k为迭代次数，经过此改进后的适应度值

f（X′）不仅非负，并且扩大了相对变化范围，提高了收敛速度。

4、在进行遗传操作前对调整后的变量进行二进制编码，利用降序排列的方法调整父代种群的适应度值。为了保护种群中的优秀个体，父代种群中适应度最大的5%不进行任何操作，直接进入子代种群中;余下的子代部分由父代通过遗传操作产生，最后对子代种群进行解码操作得到新的变量及其通过步骤3后的适应度值。

5、降序排列适应度值，计算出适应度平均值后按式（13）与本种群适应度最大值进行比较，若满足条件，则结束本次混沌遗传算法，输出此时的结果作为全局最优解，否则继续执行步骤6。

6、为了将适应度值较小的95%子代群体基因进行导向式遗传变异，对该部分对应的混沌变量根据式（3）的方法附加混沌扰动，然后重复步骤2、3进行迭代计算。该方法可以减少遗传算法的进化代数，甚至可能通过该变异方法得到比适应度值较高的5%群体更优秀的基因，提高获得全局最优解速度的同时，避免了遗传算法过早进入局部最优状态。另外，由于少部分优秀父代基因直接进入了子代，并没有经过复杂操作，提高了混沌遗传算法的效率。随着迭代过程的进行，μ值不断减小，意味着混沌扰动的力度逐渐减弱，结果逐渐向全局最优解逼近，直到相邻两代适应度平均值之差小于预先给定的某个正数ξ2时，如（14）所示，结束迭代过程。

7、执行步骤5，若式（13）成立则输出全局最优解，否则转向步骤4。

3   仿真实验及结果分析

3.1   测试函数的选择

为了检测本文所提出的混沌遗传算法的优化性能，仿真实验选取了3种被广泛使用在智能优化算法中的数值测试函数进行验证，并与标准PSO算法[13]、ABC算法[14]、ACO[15]算法比较，证明本文提出的CGA的優化性能。在仿真实验中，初始化各项参数，编码串长度φ = 8，种群数M = 30，进化代数G = 50，交叉概率Pc = 0.9，变异概率Pm = 0.1，混沌迭代次数N = 500，各算法循环次数L = 50。PSO、ABC、ACO算法的参数设置见文献[13-15]。当算法达到最大迭代次数或相邻两次优化结果连续3次结果相差小于10-6时结束循环操作，输出各项数据指标。表1列出了3种测试函数的基本属性。

3.2   实验结果及分析

本实验运行环境为Matlab2014a，7.89GB内存，Intel（R） Core（TM） i7-7700HQ处理器。表2、3分别记录了4种智能优化算法在3种测试函数下运行50次后平均值和方差值的对比情况。

图1-图3为4种优化算法在不同测试函数下的收敛曲线。从仿真结果可以清晰的看出，提出的CGA相对于其他三种算法拥有更优越的收敛速度和精度。

4   具体案例分析

4.1   神经网络模型的构建

通过以模糊神经网络模型为核心的东江湖流域综合数据管理与智能分析应用系统为例，为了证明本文提出的CGA算法在智能污水处理系统的运行效果，引入三种不同的神经网络模型，通过对比三种模型达到稳定后的各项指标差异，得出最终结论。三种不同的神经网络模型分别是基于遗传算法BP神经网络的PID控制系统[16]、基于模糊RBF神经网络的智能PID控制[17]以及融合本文提出的混沌遗传算法后的模糊神经网络模型。

将提出的混沌遗传算法加入模糊神经网络中，对其中的运算过程进行了改良，以此来训练模糊神经网络中的可调参数，这种算法简称为CGAFNN（Fuzzy Neural Network of Chaos Genetic Algorithm），图4为CGAFNN运算流程图。

4.2   性能评价指标

通过设定合适的性能指标，比较容易对不同的控制算法之间的偏差有一个清晰的认识，并识别这些算法性能区别的目的和实际意义，以便更好地在不同应用中采取不同的控制算法。本文通过如下指标的对比，从多方面的展示出CGAFNN的优异性：

1）上升时间tu与稳态时间tc。分别指输出量首次到达输出稳态值所对应的时间及到达并保持在有限误差宽度（一般为稳态值的 ）附近的稳态值所对应的时间。

2）阶跃响应峰值max（y）和峰值时间t。

3）最大超调量k。最大超调量是输出最大值

max（yout）与输出稳态值xc（∞）的误差百分比，即

4）除了控制系统的指标外，本文还引入神经网络性能评价指标MAE（算法的绝对平均误差）和MSE （算法的均方误差），即：

4.3   数据仿真

根据仿真实验的要求，设置以下参数：

结合图5、6、7和表5、6可以得出以下结论：

1）图5中三种方法均能实现智能污水处理系统的参数整定，而本文提出的CGAFNN较其他两种算法具有更好的准确性和快速性;

2）基于模糊RBF神经网络与CGAFNN相比，到达阶跃响应稳定状态的时间较长且误差控制效果欠佳，即使在达到峰值的时间上比后者提前了73%，但综合性能依然低于后者;

3）基于遗传算法的BP神经网络与CGAFNN相比，没有明显的超调现象，但是峰值时间、稳态时间、上升时间均落后于后者，无法达到智能污水处理系统的快速性标准;

4）CGAFNN相对于其他两种神经网络，无超调现象，稳态时间和上升时间比RBF网络提前18%和31%，MAE和MSE指标较BP网络提高了34%和19%，基本达到了智能污水处理系统调整参数过程中准确性、快速性的标准。

图6和图7为采用传统遗传算法和人工蜂群算法、蚁群算法、粒子群算法、混沌遗传算法优化模糊神经网络的效果对比。传统遗传算法由于全局搜索阶段参数保持不变，容易陷入局部最优状态，无法达到选取最优参数的目的。而采用智能优化算法，特别是混沌遗传算法，适应度函数不仅搜索速度更快，且一直保持全局选优状态，使得阶跃响应达到稳态的时间更短，证明了本文提出的混沌遗传算法拥有更加良好的性能。

4.4   实际应用效果分析

从湖南省资兴市东江湖流域2008年到2013年的环保水文数据中选取200组数据来进行训练和测试。本实验采用对照原理进行比较，在同一生物池中分别进行未采用和采用基于混沌遗传算法改进的智能污水处理系统精确控制，实验时间设定为48小时，出水按GB18918-2002一级B标准排放。随机抽取5组的数据样本进行水质评价，各自的组分浓度参数与对应的正常值范围如表7所示。

通过智能污水处理系统的分析，由于池中氧气浓度没有达到污水处理的标准，导致样本中聚磷菌的数值偏低。此时，利用该系统的选出最优的解决方案，完成污水处理的任务。

由图8可知，采用智能污水处理系统精确曝气控制前后氧气浓度（Do）的对比图。前者生物池中氧气浓度的波动非常大，除磷效果明显不理想，出水排放超标率依然很高。

采用智能污水处理系统精确曝气控制后，生物池中氧气浓度的波动减小，出水水质明显提高。因此，将本文提出的混沌遗传算法应用于智能污水处理系统，更加适合用户对于智能污水处理系统的基本需求。

5   结   论

针对传统遗传算法收敛速度慢、易陷入局部最优等缺点，结合混沌运动的优点提出了一种混沌遗传算法。该算法利用混沌变量初始化染色体编码，进行遗传操作，降序排列子代适应度值后选择较小适应度的子代群体进行随机扰动，以避免陷入局部最优状态，该扰动力度根据搜索进程不断调整，加快了算法的收敛速度。仿真实验表明，提出的混沌遗传算法拥有良好的性能，应用价值较大。如何将混沌遗传算法应用在人工智能系统中是下一步研究内容。“互联网+”的时代已经来临，人工智能必将推动信息技术的迅速发展。未来的人工智能系统的重点是建立理论与实际相结合，得到更加灵活、多样化的先进知识，使信息技术达到高智能化的目标。

参考文献

[1]    丁建立，陈增强，袁著祉. 遗传算法与蚂蚁算法的融合[J]. 计算机研究与发展，2003，9： 1351—1356.

[2]    ZHANG X，ZHANG Q L，ZHANG X. Nonuniform antenna array design by parallelizing three-parent crossover genetic algorithm [J]. EURASIP Journal on Wireless Communications and Networking，2017，2017 （1）： 1—7.

[3]    TAKAGI H. The elitist non-dominated sorting genetic algorithm with inheritance （i-NSGA-II） and its jumping gene adaptations for multi-objective optimization[J].Information Science，2017：15—37.

[4]  SKARTHIKEYAN P，BASKAR S，ALPHONES A. Improved genetic algorithm using different genetic operator combinations （GOCs） for multicast routing in ad hoc networks [J]. Soft Computing，2013，17（9）：1563—1572.

[5]   ZHU Q Q，WANG N，ZHANG L. Circular genetic operators based RNA genetic algorithm for modeling proton exchange membrane fuel cells[J]. International Journal of Hydrogen Energy，2014： 17779—17790.

[6]    張彤，王宏伟，王子才.变尺度混沌优化算法及其应用[J].控制与决策，1999，14（3）：285—288.

[7]    李兵，蒋慰孙.混沌优化方法及其应用[J].控制理论与应用，1997，14（4）： 613— 615.

[8]    POWERS DAVID M W.Evaluation： from precision，recall，and f-measure to ROC，informedness，markedness，and correlation[J]. Journal of Machine Learning Technologies，2（1）： 37—83.

[9]   GUO Q J，WANG B，ZHOU C J，et al.DNA code design based on the bloch quantum chaos algorithm[J].IEEE Access，2017，9：22453 — 22461.

[10] WANG Z Q，HAN L，YANG S S，et al.Study of digital watermark based on chaos algorithm[C]//Cyberspace Technology （CCT 2015）.Third International Conference on，2015，10：17—18.

[11]  ZHANG Q W，YUAN M T，SONG R. Robot trajectory planning method based on genetic chaos optimization algorithm[C]//Advanced Robotics （ICAR）.2017 18th International Conference on，2017，7：10—12.

[12]  王子才，张彤，王宏伟.基于混沌变量的模拟退火优化方法[J].控制与决策，1999，14（4）： 382—384.

[13] KENNEDY，EBERHART R. Particle swarm optimization[C]//IEEE Int Conf on Neural Net-works. IEEE，1995：1942—1948.

[14] DORIGO M， STUTZLE T. Ant colony optimization[M].Cambridge，MA：MIT Press，2004.

[15]  KARABOGA D. An idea based on bee swarm for numerical optimization[R]. Turkey：Erciyes Unuversity，Engineering Facul-ty，Computer Engineering Departmeng，2005.

[16]  呂国芳，张明艳. 基于遗传算法BP神经网络的恒压供水系统的研究[J].电子设计工程，2015，15：78—81.

[17]  胥良，郭林，梁亚，等. 基于模糊RBF神经网络的智能PID控制[J].工业仪表与自动化装置，2015，6：67—69+75.