遗传算法在计算机仿真技术中的应用
摘 要：通过对随机性问题进行计算机仿真，从而得出待解问题的解。提出了基于遗传算法进行计算机仿真 的基本模型。通过圆周率的计算，实践了该模型的应用过程。实践证明，该模型在进行计算机仿真时准确度比较高。 关键词：蒙特卡罗方法；；随机数；遗传算法0 引 言
计算机的出现和计算技术的发展为仿真技术的发展 提供了强有力的手段和工具。最近几年，随着计算机的迅 速发展和普及，尤其是微型计算机的发展和普及，很多大 计算量的仿真系统得以实现，并在国民生产、科学研究等 领域得到广泛的应用。
现代科技发展中提出愈来愈复杂的随机性问题, 除极 少数外, 要想通过仿真给出其严格解是困难的, 用确定性 方法给出其近似解也很困难, 甚至不可能。遗传算法 GA (Genetic Algorithm)[1]是模拟生物进化的优化算法，把遗 传算法GA 应用到仿真技术中，是一种很强的特殊的数值 方法。
1 遗传算法[ 1 ]
1.1 并行遗传算法实现方案 目前并行遗传算法的实现方案大致可分为3 类： (1)全局型—主从式模型(master-slave model)：并行
系统分为一个主处理器和若干个从处理器。主处理器监控 整个染色体种群，并基于全局统计执行选择操作；各个从 处理器接受来自主处理器的个体进行重组交叉和变异，产 生新一代个体，并计算适应度，再把计算结果传给主处理
器。
从而加快满足终止条件的要求。粗粒度模型也称岛屿模型
(island model)，基于粗粒度模型的遗传算法也称为分布 式遗传算法(Distributed Genetic Algorithm)，也是目 前应用最广泛的一种并行遗传算法。
(3)分散型—细粒度模型(fine-grained model)：为种 群中的每一个个体分配一个处理器，每个处理器进行适应 度的计算，而选择、重组交叉和变异操作仅在与之相邻的 一个处理器之间相互传递个体中进行，细粒度模型也称邻 域模型(neighborhood model)，适合于连接机、阵列机和 SIMD 系统。
1.2 迁移策略
迁移(migration)是并行遗传算法引入的一个新的算 子，它是指在进化过程中子群体间交换个体的过程，一般 的迁移方法是将子群体中最好的个体发给其它的子群体， 通过迁移可以加快较好个体在群体中的传播，提高收敛速 度和解的精度。最基本的迁移模型是环状拓扑模型，如图
1 所示。
1.3 并行遗传算法的性能参数 为了评价并行算法的性能，人们提出了许多不同的 评价指标，其中最重要的一个评价标准是加速比。设T 1 为
个方面，它们除了与迁移策略有关，还与一些参数选取的 合理性密切相关，如遗传代数、群体数目、群体规模、迁 移率和迁移间隔。
2 计算机仿真
“系统仿真是通过对系统模型的实验，研究一个存在 的或设计中的系统”[2] 。对于给定目标，仿真过程可大致分 为仿真建模、程序实现、仿真结果的统计分析三大部分[3] 。 其中仿真建模是最基础的.、关系整个仿真成败的环节。如 果有软件能够辅助用户方便快捷地完成仿真建模工作，那 么不仅可大大减少工作量，而且还可使用户集中精力于提 高建模质量[4] 。
通过以上的概念分析，可以看出：仿真成败的关键是 仿真前的建模，模型建起来以后对输入数据的优化也很重 要。因此，可以把并行遗传算法应用在计算机仿真中，从 而来提高仿真的准确度。
3 并行遗传算法在计算机仿真中的应用
并行遗传算法叙述如下：
( 1) 基于对待解问题的详细分析，建立详细的符合其 特点的并行遗传算法模型。
( 2) 基于并行遗传算法模型确定仿真前各参数的实现 方案。
(3)运用蒙特卡罗方法生成的大量随机数，结合(2)的 实现方案对随机数进行优化。
( 4) 进行仿真试验，得出仿真结果。
遗传算法在计算机仿真技术中的应用 张少刚 面随意地投掷长度为 l 的细针, 设细针与平行线的垂直方 向的夹角为a,则细针与平行线相交的概率为I=Ig∣cosa∣。
由于a 是在[0, π] 间均匀分布的，所以细针与平行线相交
的概率等于1/
4.2 计算方法和结果
4.2.1 模型
在二维平面上画三条相距为O.5 ，长度为L 的平行线， 取细针长度为 O.5 ，如图 3 所示，因为本文所用随机数在 [0 ，1] 之间，所以平行线的有效长度为L ，也就是说所有投 掷试验都等效于在上述边长为 L 的正方形区域内进行的。
根据对这个问题的分析，可以确定该仿真例子适合 遗传算法的第(1) 类全局型—主从式模型，基于并行遗传 算法模型确定仿真前各参数为x1、x2、y1、y2，其实现方案见
以下算法。
4.2.2 算法
(1)为计算作准备，取总投针次数初始值N=0 ，相交次 数M=0，设定总投针试验次数Nmax；
(2) 由蒙特卡罗方法产生两个[O ，1] 间均匀分布的随 机数，并作为随机构造的细针的一个端点的坐标(x 1 ,y 2 )； (3) 再产生一个随机数，作为细针另一端点的横坐标
X2 ；
(4)如果∣x2-x1 ∣>0.5，说明本次欲构造的细针长度已 超过0.5 ，应舍弃之，并回到上步；
(5) 利用细针长度为0.5 这个约束条件，计算细针端 点的纵坐标y2=y1 ±
细针已不在选定的区域之内，应舍弃，回到(3 )；否则投针
有效，投针次数加1，N=N+1； (6)判断细针是否与平行线相交如果x1>0．5 且x2>0．5,
或者x1<0．5 且x2<0．5，则细针与平行线不相交，回到(2)；
否则相交，并令M=M+1； (7)如果N=Nmax，试验结束，输出结果，否则，(回到2)，
继续下一次投针试验。
4 投针试验
4.1 试验
图2 仿真过程图
著名的Bufon 投针实验是一种求π近似值的方法, 该 方法是在平坦桌面上划一组相距为 l 的平行线, 然后向桌
图3 模拟计算结果
模拟计算结果如图 3 所示，可以看出，基于并行遗传
度和求解质量。
参考文献
算法模型确定的仿真前各参数的实现方案准确，所得圆周 率的计算精度比较高。因此，并行遗传算法模型具有一定 的实用性。
5 结束语
本文将遗传算法应用到计算机仿真技术中，提出了 基于并行遗传算法的仿真模型，并通过圆周率的计算，实 践了它的应用过程。成功地解决了一类多变量、多约束条 件的线性仿真问题。结果表明，PGA 有效地提高了运行速
1 Holland J. Adaptation in Natural and Artificial Systems
[M].Michigan:University of Michigan Press,2005
2 李书臣, 赵礼峰. 仿真技术的现状及发展[J].自动化与仪表,
2004,14(6):1～4
3 徐庚保.系统仿真的过去、现在和未来[J].计算机仿真,2006,
15(3):2～4
4 惠天舒,李裕山,陈宗基.仿真模型的可重用性研究[J].北京航 空航天大学学报,2008,25(3):329～333
【遗传算法在计算机仿真技术中的应用】相关文章：