《遗传算法在计算机仿真技术中的应用.doc》由会员分享，可在线阅读，更多相关《遗传算法在计算机仿真技术中的应用.doc（6页珍藏版）》请在三一办公上搜索。
1、遗传算法在计算机仿真技术中的应用文章来源 毕业论文网 摘 要：通过对随机性问题进行计算机仿真，从而得出待解问题的解。提出了基于遗传算法进行计算机仿真 的基本模型。通过圆周率的计算，实践了该模型的应用过程。实践证明，该模型在进行计算机仿真时准确度比较高。关键词：蒙特卡罗方法；随机数；遗传算法 0 引 言计算机的出现和计算技术的发展为仿真技术的发展 提供了强有力的手段和工具。最近几年，随着计算机的迅 速发展和普及，尤其是微型计算机的发展和普及，很多大 计算量的仿真系统得以实现，并在国民生产、科学研究等 领域得到广泛的应用。现代科技发展中
2、提出愈来愈复杂的随机性问题, 除极 少数外, 要想通过仿真给出其严格解是困难的, 用确定性 方法给出其近似解也很困难, 甚至不可能。遗传算法 GA (Genetic Algorithm)1是模拟生物进化的优化算法，把遗 传算法GA 应用到仿真技术中，是一种很强的特殊的数值 方法。 1 遗传算法 1 1.1 并行遗传算法实现方案 目前并行遗传算法的实现方案大致可分为3 类： (1)全局型主从式模型(master-slave model)：并行系统分为一个主处理器和若干个从处理器。主处理器监控 整个染色体种群，并基于全局统计执
3、行选择操作；各个从 处理器接受来自主处理器的个体进行重组交叉和变异，产 生新一代个体，并计算适应度，再把计算结果传给主处理器。从而加快满足终止条件的要求。粗粒度模型也称岛屿模型(island model)，基于粗粒度模型的遗传算法也称为分布 式遗传算法(Distributed Genetic Algorithm)，也是目 前应用最广泛的一种并行遗传算法。(3)分散型细粒度模型(fine-grained model)：为种 群中的每一个个体分配一个处理器，每个处理器进行适应 度的计算，而选择、重组交叉和变异操作仅在与之相邻的 一个处理器之间相互传递个体中进行，细粒度模型也称邻 域模型(neigh
4、borhood model)，适合于连接机、阵列机和 SIMD 系统。1.2 迁移策略迁移(migration)是并行遗传算法引入的一个新的算 子，它是指在进化过程中子群体间交换个体的过程，一般 的迁移方法是将子群体中最好的个体发给其它的子群体， 通过迁移可以加快较好个体在群体中的传播，提高收敛速 度和解的精度。最基本的迁移模型是环状拓扑模型，如图1 所示。(2)独立型粗粒度模型(coarse-grained model)：将 种群分成若干个子群体并分配给各自对应的处理器，每个 处理器不仅独立计算适应度，而且独立进行选择、重组交 叉和变异操作，还要定期地相互传送适应度最好的个体，从而加快满足终
5、止条件的要求。粗粒度模型也称岛屿模型(island model)，基于粗粒度模型的遗传算法也称为分布 式遗传算法(Distributed Genetic Algorithm)，也是目 前应用最广泛的一种并行遗传算法。(3)分散型细粒度模型(fine-grained model)：为种 群中的每一个个体分配一个处理器，每个处理器进行适应 度的计算，而选择、重组交叉和变异操作仅在与之相邻的 一个处理器之间相互传递个体中进行，细粒度模型也称邻 域模型(neighborhood model)，适合于连接机、阵列机和 SIMD 系统。1.2 迁移策略迁移(migration)是并行遗传算法引入的一个新的
6、算 子，它是指在进化过程中子群体间交换个体的过程，一般 的迁移方法是将子群体中最好的个体发给其它的子群体， 通过迁移可以加快较好个体在群体中的传播，提高收敛速 度和解的精度。最基本的迁移模型是环状拓扑模型，如图1 所示。1.3 并行遗传算法的性能参数为了评价并行算法的性能，人们提出了许多不同的 评价指标，其中最重要的一个评价标准是加速比。设T 1 为 某算法在串行计算机上的运行时间，T P 是该算法在由p 个 处理机所构成的并行机上的运行时间，则此算法在该并行 机上的加速比S p 定义为：
7、; , &nb
8、sp; （1） 并行遗传算法的性能主要体现在收敛速度和精度两个方面，它们除了与迁移策略有关，还与一些参数选取的 合理性密切相关，如遗传代数、群体数目、群体规模、迁 移率和迁移间隔。 2 计算机仿真“系统仿真是通过对系统模型的实验，研究一个存在 的或设计中的系统”2 。对于给定目标，仿真过程可大致分 为仿真建模、程序实现、仿真结果的统计分析三大部分3 。 其中仿真建模是最基础的、关系整个仿真成败的环节。如
9、果有软件能够辅助用户方便快捷地完成仿真建模工作，那 么不仅可大大减少工作量，而且还可使用户集中精力于提 高建模质量4 。通过以上的概念分析，可以看出：仿真成败的关键是 仿真前的建模，模型建起来以后对输入数据的优化也很重 要。因此，可以把并行遗传算法应用在计算机仿真中，从 而来提高仿真的准确度。 3 并行遗传算法在计算机仿真中的应用并行遗传算法叙述如下：( 1) 基于对待解问题的详细分析，建立详细的符合其 特点的并行遗传算法模型。( 2) 基于并行遗传算法模型确定仿真前各参数的实现 方案。(3)运用蒙特卡罗方法生成的大量随机数，结合(2
10、)的 实现方案对随机数进行优化。( 4) 进行仿真试验，得出仿真结果。( 5) 若这个结果和预期理论结果不相符，则说明仿真 失败，重新回到第一步。否则，此次仿真过程成功。仿真 过程如图2 所示。遗传算法在计算机仿真技术中的应用 张少刚 面随意地投掷长度为 l 的细针, 设细针与平行线的垂直方 向的夹角为a,则细针与平行线相交的概率为I=Igcosa。由于a 是在0, 间均匀分布的，所以细针与平行线相交的概率等于1/ cosa da=2/ 。设进行了N 次投针试 验，有M 次与平行线相交，当N 足够大时，细针与平行线相 交的频率就等于以上的概率，于是得到计算的公式
11、为： =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) 由蒙特卡罗方法产生两个
12、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>05 且x2>05,或者x1<05 且x2<05，则细针与平
13、行线不相交，回到(2)；否则相交，并令M=M+1； (7)如果N=Nmax，试验结束，输出结果，否则，(回到2)，继续下一次投针试验。4.2.3 计算结果 4 投针试验4.1 试验图2 仿真过程图著名的Bufon 投针实验是一种求近似值的方法, 该 方法是在平坦桌面上划一组相距为 l 的平行线, 然后向桌图3 模拟计算结果 模拟计算结果如图 3 所示，可以看出，基于并行遗传度和求解质量。 参考文献算法模型确定的仿真前各参数的实现方案准确，所得圆周 率的计算精度比较高
14、。因此，并行遗传算法模型具有一定 的实用性。5 结束语本文将遗传算法应用到计算机仿真技术中，提出了 基于并行遗传算法的仿真模型，并通过圆周率的计算，实 践了它的应用过程。成功地解决了一类多变量、多约束条 件的线性仿真问题。结果表明，PGA 有效地提高了运行速1 Holland J. Adaptation in Natural and Artificial SystemsM.Michigan:University of Michigan Press,20052 李书臣, 赵礼峰. 仿真技术的现状及发展J.自动化与仪表,2004,14(6):143 徐庚保.系统仿真的过去、现在和未来J.计算机仿真,2006,15(3):244 惠天舒,李裕山,陈宗基.仿真模型的可重用性研究J.北京航 空航天大学学报,2008,25(3):329333
