摘要：果蝇优化算法（FOA）作为一类新的优化搜索算法，广泛应用于各种优化问题。针对该算法后期求解精度低、容易陷入局部最优且收敛缓慢的缺点，提出一种结合元胞自动机的果蝇优化算法（CAFOA）。该算法在首次求解时利用元胞演化规则选择果蝇最优个体邻域，然后对选择后的果蝇个体位置进行随机扰动，分别用邻域个体复制更新演化前个体位置，再次进行迭代寻优，从而有效克服算法陷入局部最优。对6种常见测试函数进行了运算仿真。实验结果表明，所提算法比传统算法的平均收敛精度提高10%，达到稳定全局最优值的平均迭代次数减少870次，从而论证了算法的有效性。

　　关键词：元胞自动机；果蝇优化算法；演化规则；邻域；随机扰动中图分类号： TP301.6； TP18文献标志码：AAbstract： The Fruit fly Optimization Algorithm （FOA） was widely used in all kinds of optimization problems as a new kind of optimization search algorithm. In order to overcome the shortcomings of low precision， easily trapping in local optimum and the slow convergence in later period， a novel algorithm of FOA based on Cellular Automata （CAFOA） was proposed. CAFOA used cellular evolution rules to select the best individual drosophila neighborhood during the first evolution， then it selected the location of individual fruit fly to conduct random perturbation and replaced the previous location before evolution with its neigborhoods， so it could obtain the value of secondary optimization， jump out of local extremum and continue to optimize. Experiments were conducted on the six kinds of classical test functions for operation simulation. The experimental results show that， the average convergence precision of the proposed algorithm is 10% higher than the traditional algorithms and the average number of iterations to achieve stable global optimal values is reduced to 870， which demonstrates the effectiveness of the new algorithm.

　　Key words： Cellular Automata （CA）； Fruit fly Optimization Algorithm （FOA）； evolution rule； neighborhood； random perturbation0引言果蝇优化算法（Fruit fly Optimization Algorithm， FOA）[1-2]是一类基于生物启发式的全局优化智能算法，源于对果蝇群体觅食行为的仿真，目前为止，果蝇最佳化演算法仍是一个较新的研究领域，该算法已经被应用于财政、工程和科学等领域，也可混合神经网络、模糊数学等一起使用，现已将其成功应用于优化控制设计、预测、多维背包问题以及求解数学函数极值微调ZSCORE模型系数与支持向量机参数的优化等方面[3]。

　　FOA是一种新型的群智能算法，与其他群智能算法比较，FOA简洁，收敛速度快且收敛精度高。它只有两个参数（种群规模与进化代数）供调节，程序代码容易实现，计算量小，执行时间短，与其他群智能算法相比，更容易被用于解决实际问题。FOA和其他全局优化算法（如蚁群算法、蜂群算法等）[3-5]一样，在处理较复杂问题时候缺乏稳定性，收敛速度缓慢，易发散，尤其是对于高维多极值复杂优化问题。

　　针对FOA的收敛速度缓慢，易陷入局部最优和收敛精度低的缺点，本文提出一种基于元胞自动机的果蝇优化算法（FOA based on Cellular Automata， CAFOA）。该算法通过元胞自动机（Cellular Automata， CA）演化规则进行最优种群的选择，提高种群的多样性，然后对于选择后的群体位置进行随机扰动，避免陷入停滞，分别用邻域个体复制更新演化前个体位置，继续二次迭代寻优，有效避免算法陷入局部收敛，可以跳出局部极值，提高FOA的收敛精度和收敛速度。并通过对6个典型函数进行仿真测试，测试结果表明，本文所提出的基于元胞自动机的果蝇优化算法（CAFOA）的全局收敛性、收敛速度和寻优精度有了很大的提高。

　　1元胞自动机元胞自动机（CA）[6-7]是经典的自然计算模型，它用于模拟生命系统所具有的自我复制功能，具有时间和空间上的离散性，并且每个元胞的变化是同步的，具有很好的并行性，能够进行自我修复和重建的规则。元胞在某一个时刻只能有一种状态，而且该状态只能是从一个有限离散状态集中进行取值；邻居是元胞个体周围按一定规则划定的元胞的集合，元胞在下一时刻的状态是由这个元胞及其邻居决定；规则是根据元胞当前状态及其邻居状态确定下一时刻该元胞状态的动力学函数[8]。 　　CA有5个主要基本组成部分：元胞（Cellular）、元胞空间（Lattice）、邻域（Neighbor）、演化规则（Evolution rules）和状态集（State set）。用数学符号表示元胞的组成C=（Ld，S，N， f），各变量含义如下。

　　1）C称作为元胞，也可以称为单元。元胞集就是由若干个单元组成的，本文将每个果蝇个体的味道浓度作为单元。

　　2）Ld表示每个元胞分布在任意d维的空间网格，也叫作元胞空间。本文采取二维元胞空间，四边形网格空间排列对问题进行求解。

　　3）S表示状态集。每个时刻，一个元胞只有一种状态，本文用果蝇群体当前的位置表示。

　　4）N叫作元胞邻居。在每个邻域内，所有元胞的组成，记为N=（S1，S2，…，Sn），n表示元胞邻域的个数。常见的3种元胞邻居模型如图1所示，本文采用了扩展的摩尔型（Moore）邻居模型。

　　由表3可以看出，本文提出的CAFOA比FOA具有更高的收敛精度；在CAFOA的实验条件（如种群数进化迭代次数）和函数约束条件（如函数维数）比较苛刻的情况下，在所有测试函数中比文献[3，11-13]提到的算法有更高的收敛精度。对于函数Sphere f1来说，CAFOA的优化均值显著优于各种算法（文献[13]除外），数量级相差20多倍；CAFOA虽然在Rosenbrock f2函数上比文献[3]中算法结果差，但相对于其他几个算法精度均得到了提高；对于函数Rastrigin f3来说，CAFOA精度比其他算法性能有显著的提高，收敛精度数量级比文献[12]算法相差15个数量级；对于函数Griewank f4来说，CAFOA比其他算法精度高，有很好的全局优化特点；对于函数Ackley f5，CAFOA优化精度比文献[12]算法提高了14个数量级；对于函数Schaffer f6，CAFOA可以找到全局的最优值，充分说明改进后算法具有更好的全局搜索能力、更快的收敛速度和更高的收敛精度。

　　4结语本文将基本果蝇优化算法与元胞自动机结合，提出基于元胞自动机果蝇优化算法，在迭代进化过程中，通过元胞演化规则进行最优个体的选择，然后进行随机扰动，有效地避免了局部收敛，并提高了种群的多样性，进而用最优个体进行二次寻找全局最优解。通过对6个基准测试函数的对比实验，并与各种算法进行了比较。实验结果表明， CAFOA具有更好的全局搜索能力，克服了基本果蝇优化算法易陷入局部最优解的缺点，在收敛速度及收敛精度上均比基本果蝇优化算法有很大的提高，因而该算法具有高效性、实用性。

　　参考文献：

　　[1]PAN W. Fruit fly optimization algorithm [M]. Taibei： Bookstore of Canghai， 2011： 1-12.（潘文超。果蝇最佳化演算法[M].台北：沧海书局，2011：1-12）。

　　[2]PAN WT. A new fruit fly optimization algorithm： taking the financial distress model as an example [J]. KnowledgeBased Systems， 2012， 26： 69-74.

　　[3]HAN J， LIU C. Fruit fly optimization algorithm based on bacterial chemotaxis [J]. Journal of Computer Applications， 2013， 33（4）： 964-966.（韩俊英，刘成忠。基于细菌趋化的果蝇优化算法[J].计算机应用，2013，33（4）：964-966）。

　　[4]LI L， NIU B. Particle swarm optimization [M]. Beijing： Metallurgical Industry Press， 2009： 70-103.（李丽，牛奔。粒子群优化算法[M].北京：冶金工业出版社，2009：70-103）。

　　[5]DUAN H. Principles and applications of ant colony algorithm [M]. Beijing： Science Press， 2005： 166-172.（段海滨。蚁群算法原理及其应用[M].北京：科学出版社，2005：166-172）。

　　[6]XIA X， ZENG J， GAO H. Niche PSO algorithm based on CA [J]. Computer Engineering and Applications， 2007， 43（11）： 66-68.（夏小翔，曾建潮，高慧敏。基于元胞自动机的小生境微粒群算法[J].计算机工程与应用，2007，43（11）：66-68）。

　　[7]ZHU G， MA L. Cellular ant algorithm for multiobjective function optimization [J]. Control and Decision， 2007， 22（11）： 1317-1320.（朱刚，马良。多目标函数优化的元胞蚂蚁算法[J].控制与决策，2007，22（11）：1317-1320）。

　　[8]MAERIVOET S， de MOOR B. Cellular automata models of road traffic [J]. Physics ReportsReview Section of Physics Letters， 2005， 419（1）： 1-64.

　　[9]LING W， XIAO L， SHENG Y. A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem [J]. KnowledgeBased Systems， 2013， 48： 17-23.

　　[10]HU W， LI Z. A simpler and more effective particle swarm optimization algorithm [J]. Journal of Software， 2007， 18（4）： 861-868.（胡旺，李志蜀。一种更简化而高效的粒子群优化算法[J].软件学报，2007，18（4）：861-868）。

　　[11]CLERC M，KENNEDY J. The particle swarm： explosion stability and convergence in a multidimensional complex space [J]. IEEE Transactions on Evolution Computation， 2002， 6（1）： 58-73.

　　[12]LIN C， FENG Q. New adaptive particle swarm optimization algorithm [J]. Computer Engineering， 2008， 34（7）： 181-183.（林川，冯全源。一种新的自适应粒子群优化算法[J].计算机工程，2008，34（7）：181-183）。

　　[13]WANG L， HONG Y， SHI Q. Global edition artificial fish swarm algorithm [J]. Journal of System Simulation， 2009， 21（23）： 7483-7486.（王联国，洪毅，施秋红。全局版人工鱼群算法[J].系统仿真学报，2009，21（23）：7483-7486）。

　　[14]LYU Z， HOU Z. Particle swarm optimization with adaptive mutation [J]. Acta Electronica Sinica， 2004， 32（3）： 416-420.（吕振肃，侯志荣。自适应变异的粒子群优化算法[J].电子学报，2004，32（3）：416-420）。