长江大学学报（自然科学版） ２００９年６月第６卷第２期：理工
Ｊｏｕｒｎａｌ ｏｆ Ｙａｎｇｔｚｅ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔ Ｓｃｉ Ｅｄｉｔ） Ｊｕｎ．２００９。Ｖ０１．６ Ｎｏ．２：Ｓｃｉ＆Ｅｎｇ
一
种基于元胞自动机的改进遗传算法
李 凯，田双亮 （西北民族大学计算机与信息工程学院，甘肃兰州７３００３０）
耿丽君 （山西财经大学会计学院，山西太原０３００ｉ ２）
张 喜 （淄博技术学院，山东淄博２５５０００）
［摘要］针对遗传算法中存在搜索效率和解精度低的问题，结合元胞自动机模型，提出了一种改进的遗传算
法——竞争杂交算法。在适应度函数中运用元胞自动机模型进行竞争复制，在确定交叉算子时进行杂交，
依此来对遗传算法进行改进。仿真结果表明，竞争杂交算法在搜索速度和概率上比简单遗传算法要高一些。
［关键词］竞争杂交算法；元胞自动机；遗传算法；适应度；交叉算子
［中图分类号］ＴＰ３９１ ［文献标识码］Ａ ［文章编号］１６７３—１４０９（２００９）０２一Ｎ２３７一Ｏ２
遗传算法Ｌ１ ］是一种模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模
拟自然进化过程搜索最优解的方法，具有隐含的并行性、非线性求解及易于和其他模型结合等特点。
遗传算法首先进行基因编码，产生初始种群，接着按照适者生存的原理根据适应度大小来挑选个
体，产生较好的近似解。再借助遗传算子进行交叉和变异，产生代表新的解集的种群。这样一代代的进
化，最后就会收敛到最适应环境的染色体上，它就是问题的最优解。但遗传算法存在搜索效率低和解精
度低等问题，为此，笔者结合自动机模型，提出了一种改进的遗传算法。
１元胞自动机模型
元胞自动机模型 最基本的组成是元胞、元胞空间、
邻居和规则４部分。简言之，元胞自动机可以视为由一个元
胞空间和定义于该空间的变换函数所组成。
如图１所示，构造二维元胞自动机的４方网格，每个网
格代表一个元胞，所有的元胞构成元胞空间，一个元胞周围
的８个元胞称为该元胞的邻居。笔者采用周期型。对二维空
间，上下相接，左右相接，形成一个拓扑的圆环面。对于摩
尔型邻居模型，每个元胞都有与之对应的８个邻居。定义元
胞的状态为待优化问题的任意某一合法解和其所对应的目标
函数值。元胞自动机模型的规则就是根据元胞当前状态及邻
居状况确定下一时刻该元胞状态的动力学函数。
２基于元胞自动机模型的竞争杂交算法的实现
图１二维元胞自动机的邻居模型（摩尔型）
利用遗传算法中的各种竞争、杂交算法进行个体的繁殖、杂交、异变的处理。采用一种简单的竞争和
杂交算法ｌ＿７ ］，该算法将竞争和杂交只限于局部范围内进行。首先将所有个体按顺序排放在一张二维表格
上，使每个个体的上、下、左、右都与其他个体相邻接。然后，按照以下算法进行个体的遗传进行处理。
１）竞争复制 分别计算基因种群中所有个体的环境适应度函数。适应度函数表明个体或解的优劣
性，不同的问题，适应度函数的定义方式也不同。
运用二维元胞自动机的邻居模型，每个个体与它左边邻居比较环境的适应度，如果左边邻居的环境
［收稿日期］２００９一Ｏ３—１２
［作者简介］李凯（１９８６一），男，２００８年大学毕业，硕士生，现主要从事数据挖掘方面的研究工作。
长江大学学报（自然科学版） ２００９年６月
适应度大，就用左边邻居的遗传信息替代自己的遗传特性，否则不做改变。这样就将导致适应度小的个
体死亡，而适应度大的个体得以复制。
２）杂交繁殖 选择适应度大的个体复制完成后，从任意个体某个随机位置开始，将其与上方的邻
居进行杂交繁殖，相互交换部分遗传信息，完成所有个体的交叉繁殖。
３）异变处理对新生代个体进行随机异变处理，即以１ 至２％的概率随机选择新生代个体，并且
随机改变被选中个体位串上某个位置的值。将原来是１的改变为０，原来是０的改变为１。
随即改变竞争和杂交方向，重复１）至３）的过程，即下一代的竞争、杂交方向可与右边邻居进行，
而不是以前的与左边邻居的杂交处理。完成上述操作后，这样持续地迭代下去，使群体的平均适应度和
最优个体的适应度不断上升，直至得到满意解或样本的适应度不再提高为止。
３仿真分析及结果
为了验证笔者提出的改进算法的性能，将对函数－厂（ｚ）一Ｘ一５ｓｉｎ（２ｘ）＋１０ｃｏｓ（ｘ）的最大值寻优进
行试验 ］。设置种群大小为１ｏ，每个个体只包括一个变量，用实数编码。首先随机的生成初始种群：
Ｘ１—０．０２８１ Ｘ２—４．６００２ Ｘ３—５．６７９７ Ｘ４＝：＝４．３８９７ Ｘ５—４．３３１２
Ｘ６—２．１４３４ Ｘ７—６．５３４９ Ｘ８—４．６０００ Ｘ９—２．８９７４ Ｘｌ０—６．７０６０
根据评价函数，计算个体的适应度，利用遗传算子和交叉算子得到新种群。经过２５次迭代后得到最优解：
Ｘ一７．９２３６ －厂（ｚ）一１８．２３２３
试验中种群的初始大小设置为１００，采取二进制编码，个体随机初始化。最大迭代次数为５００次。
为了避免算法对交叉概率Ｐ 和变异概率Ｐ 初始值过度依赖，试验中对这些概率参数运用自适应策略，即：
：：：
厂≥
Ｐｍ：＝：
厂≥
【忌ｚ 厂 ＜ ｌ ．厂＜
式中，，ｍ 为群体中最大的适应度值；ｆａ 为每代群体的平均适应度值；ｆ 为要交叉的２个个体中较大的
适应度值；，为要变异个体的适应度值。设 表ｌ 简单遗传算法与竞争杂交算法性能比较
定点 ，ｋｚ，ｋｓ，忌 取（０，１）之间的值，就可以自—————— 西 广
适应调整了。在初始化状态下，Ｐ。一ｏ．６，Ｐ 墼 竖 笙墨
一
ｏ．１。 警 ｊ孝 。 ・眈。 ・ 。∞
算法性能比较如表１。从表１中可以看
出，在求的相同变量最优解的情况下，竞争杂交算法在搜索速度和概率上比简单遗传算法要高一些。
４结 语
在简单遗传算法的基础上，通过元胞自动机模型的竞争方法，将竞争分别作用于个体的适应度，同
时引入杂交思想，利用各个子种群不同阶段的最优个体的相互杂交来对算法作进一步改进。试验证明，
竞争杂交算法加快了进化速度，不但保持了遗传算法的随机搜索、优胜劣汰等优点，同时提高了算法的
整体性能。
［参考文献］
［１］Ｈｏｌｌａｎｄ Ｊ Ｈ．Ａｄａｐｔａｔｉｏｎ ｉｎ Ｎａｔｕｒａｌ ａｎｄ Ａｒｔｉｆｉｃｉａｌ Ｓｙｓｔｅｍｓ［Ｍ］．ＭＩＴ Ｐｒｅｓｓ，１９７５．
［２］Ｗｉｎｔｅｒ Ｇ（ｅｄ）．Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ ｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ［Ｍ］．Ｗｉｌｅｙ，１９９５．
［３］王小平，曹立明．遗传算法理论应用与软件实现［Ｍ］．西安：西安交通大学出版社，２００２．
［４］Ｐｉｒｅｓ Ａ，Ｌａｎｄａｕ Ｄ Ｐ，Ｈｅｒｒｍａｎｎ ｅｄｉｔｏｒｓ Ｈ．Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｐｈｙｓｉｃｓ ａｎｄ Ｃｅｌｌｕｌａｒ Ａｕｔｏｍａｔａ［Ｍ］．Ｗｏｒｌｄ Ｓｃｉｅｎｔｉｆｉｃ，１ ９９０．
［５］（英国）肖帕德．物理系统的元胞自动机模拟［Ｍ］．祝玉学译．北京：清华大学出版社，２００３．
［６］程健，金菊良，周玉良，等．基于正交试验和元胞自动机模型的加速并行遗传算法［Ｊ］．系统工程理论方法应用，２００６，（８）：３６４￣３６９
［７］周根贵．数据仓库与数据挖掘［Ｍ］．杭州：浙江大学出版社，２００４．
［８］张晶，黄沛．一种基于种群划分及杂交的免疫遗传算法［Ｊ］．计算机工程，２００８，（２）：２２０ ２２２．
［９］李雄飞，李军．数据挖掘与知识发现［Ｍ］．北京：高等教育出版社，２００３．
［编辑］ 洪云飞