评价网 > 科教论文 > 工学毕业论文 > 计算机应用论文 > 正文

遗传算法在计算机仿真技术中的应用

2013-07-09 01:11 摘 要：通过对随机性问题进行计算机仿真，从而得出待解问题的解。提出了基于遗传算法进行计算机仿真 的基本模型。通过圆周率的计算，实践了该模型的应用过程。实践证明，该模型在进行计算机仿真时准确度比较高。 关键词：蒙特卡罗方法；；随机数；遗传算法  

0      引 言

计算机的出现和计算技术的发展为仿真技术的发展 提供了强有力的手段和工具。最近几年，随着计算机的迅 速发展和普及，尤其是微型计算机的发展和普及，很多大 计算量的仿真系统得以实现，并在国民生产、科学研究等 领域得到广泛的应用。

现代科技发展中提出愈来愈复杂的随机性问题, 除极 少数外, 要想通过仿真给出其严格解是困难的, 用确定性 方法给出其近似解也很困难, 甚至不可能。遗传算法 GA (Genetic Algorithm)[1]是模拟生物进化的优化算法，把遗 传算法GA 应用到仿真技术中，是一种很强的特殊的数值 方法。

 

 

1      遗传算法[ 1 ]

1.1 并行遗传算法实现方案 目前并行遗传算法的实现方案大致可分为3 类： (1)全局型—主从式模型(master-slave model)：并行

系统分为一个主处理器和若干个从处理器。主处理器监控 整个染色体种群，并基于全局统计执行选择操作；各个从 处理器接受来自主处理器的个体进行重组交叉和变异，产 生新一代个体，并计算适应度，再把计算结果传给主处理

器。

（科教作文网http://zw.ΝsΕac.cOM编辑）

从而加快满足终止条件的要求。粗粒度模型也称岛屿模型

(island model)，基于粗粒度模型的遗传算法也称为分布 式遗传算法(Distributed Genetic Algorithm)，也是目 前应用最广泛的一种并行遗传算法。

(3)分散型—细粒度模型(fine-grained model)：为种 群中的每一个个体分配一个处理器，每个处理器进行适应 度的计算，而选择、重组交叉和变异操作仅在与之相邻的 一个处理器之间相互传递个体中进行，细粒度模型也称邻 域模型(neighborhood model)，适合于连接机、阵列机和 SIMD 系统。

1.2 迁移策略

迁移(migration)是并行遗传算法引入的一个新的算 子，它是指在进化过程中子群体间交换个体的过程，一般 的迁移方法是将子群体中最好的个体发给其它的子群体， 通过迁移可以加快较好个体在群体中的传播，提高收敛速 度和解的精度。最基本的迁移模型是环状拓扑模型，如图

1 所示。

（转载自http://www.ＮＳＥＡＣ.com中国科教评价网）

(2)独立型—粗粒度模型(coarse-grained model)：将 种群分成若干个子群体并分配给各自对应的处理器，每个 处理器不仅独立计算适应度，而且独立进行选择、重组交 叉和变异操作，还要定期地相互传送适应度最好的个体，

从而加快满足终止条件的要求。粗粒度模型也称岛屿模型 (island model)，基于粗粒度模型的遗传算法也称为分布 式遗传算法(Distributed Genetic Algorithm)，也是目 前应用最广泛的一种并行遗传算法。 (3)分散型—细粒度模型(fine-grained model)：为种 群中的每一个个体分配一个处理器，每个处理器进行适应 度的计算，而选择、重组交叉和变异操作仅在与之相邻的 一个处理器之间相互传递个体中进行，细粒度模型也称邻 域模型(neighborhood model)，适合于连接机、阵列机和 SIMD 系统。 1.2 迁移策略 迁移(migration)是并行遗传算法引入的一个新的算 子，它是指在进化过程中子群体间交换个体的过程，一般 的迁移方法是将子群体中最好的个体发给其它的子群体， 通过迁移可以加快较好个体在群体中的传播，提高收敛速 度和解的精度。最基本的迁移模型是环状拓扑模型，如图

1 所示。

1.3 并行遗传算法的性能参数 为了评价并行算法的性能，人们提出了许多不同的 评价指标，其中最重要的一个评价标准是加速比。设T 1 为

 

某算法在串行计算机上的运行时间，T P 是该算法在由p 个 处理机所构成的并行机上的运行时间，则此算法在该并行 机上的加速比S p 定义为：

                                      ,                                 （1） 并行遗传算法的性能主要体现在收敛速度和精度两

个方面，它们除了与迁移策略有关，还与一些参数选取的 合理性密切相关，如遗传代数、群体数目、群体规模、迁 移率和迁移间隔。

 

 

2     计算机仿真

“系统仿真是通过对系统模型的实验，研究一个存在 的或设计中的系统”[2] 。对于给定目标，仿真过程可大致分 为仿真建模、程序实现、仿真结果的统计分析三大部分[3] 。 其中仿真建模是最基础的、关系整个仿真成败的环节。如 果有软件能够辅助用户方便快捷地完成仿真建模工作，那 么不仅可大大减少工作量，而且还可使用户集中精力于提 高建模质量[4] 。

通过以上的概念分析，可以看出：仿真成败的关键是 仿真前的建模，模型建起来以后对输入数据的优化也很重 要。因此，可以把并行遗传算法应用在计算机仿真中，从 而来提高仿真的准确度。

 

 

3     并行遗传算法在计算机仿真中的应用

并行遗传算法叙述如下：

( 1) 基于对待解问题的详细分析，建立详细的符合其 特点的并行遗传算法模型。

( 2) 基于并行遗传算法模型确定仿真前各参数的实现 方案。

(3)运用蒙特卡罗方法生成的大量随机数，结合(2)的 实现方案对随机数进行优化。

( 4) 进行仿真试验，得出仿真结果。

( 5) 若这个结果和预期理论结果不相符，则说明仿真 失败，重新回到第一步。否则，此次仿真过程成功。仿真 过程如图2 所示。

（科教范文网 Lw.nsEAc.com编辑整理）

遗传算法在计算机仿真技术中的应用 张少刚 面随意地投掷长度为 l 的细针, 设细针与平行线的垂直方 向的夹角为a,则细针与平行线相交的概率为I=Ig∣cosa∣。

由于a 是在[0, π] 间均匀分布的，所以细针与平行线相交

的概率等于1/ ∣cosa ∣da=2/ π。设进行了N 次投针试 验，有M 次与平行线相交，当N 足够大时，细针与平行线相 交的频率就等于以上的概率，于是得到计算的π公式为： π=2N/M。

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 ± ，如果y1>1 或y2<0，说明

细针已不在选定的区域之内，应舍弃，回到(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.2.3 计算结果

（科教作文网http://zw.ΝsΕac.cOM编辑）

 

 

 

 

 

 

4     投针试验

4.1 试验

（科教范文网 lw.nSeAc.com编辑发布）

图2 仿真过程图

著名的Bufon 投针实验是一种求π近似值的方法, 该 方法是在平坦桌面上划一组相距为 l 的平行线, 然后向桌

您可以访问中国科教评价网（www.NsEac.com）查看更多相关的文章。

图3 模拟计算结果

 

模拟计算结果如图 3 所示，可以看出，基于并行遗传

（转载自http://zw.NSEAC.com科教作文网）

度和求解质量。

 

参考文献

算法模型确定的仿真前各参数的实现方案准确，所得圆周 率的计算精度比较高。因此，并行遗传算法模型具有一定 的实用性。

5      结束语

本文将遗传算法应用到计算机仿真技术中，提出了 基于并行遗传算法的仿真模型，并通过圆周率的计算，实 践了它的应用过程。成功地解决了一类多变量、多约束条 件的线性仿真问题。结果表明，PGA 有效地提高了运行速

内容来自www.nseac.com

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