并行遗传算法（精选十篇）
并行遗传算法 篇1
并行多机调度问题是NP-Hard问题，它既有丰富的研究内容，同时在生产调度，机械制造等方面有广泛的实际应用价值。但是在实际操作中，人们常常按经验法则 (如处理时间短优先调度或到期日早优先调度) 进行调度，这样得到的调度结果一般不能满足实际环境的需求，而且当并行机数和工件数增加时，问题的复杂度成指数增加，传统方法不适合解决此类问题。目前的并行机调度问题研究大部分是集中于简化问题，然后寻找最优解或次优解。
如何使并行机调度问题更接近实际生产状况并找到次优解成为本问题研究热点之一。遗传算法由于其固有的全局搜索与收敛特性，能够较好地解决此类优化组合问题。用遗传算法解决并行机调度问题已经有相关研究，其中Cheng提出一套方案，利用特殊符号 (*) 和工件号组成染色体，特殊符号为分隔符，将工件分成不同的组，每个工件组指派到不同的并行机中。本文对Cheng的方案进行了改进，并且把工件延迟与提前完成成本、机器闲置时间成本和机器设备启动成本等列入考虑因素，使多机调度问题的解决更接近实际的生产状况，目的在于求得考虑实际因素下的次优调度结果，以降低存货存储、交货延迟的违约、设备及人力等成本。
（二）遗传算法与并行机调度问题
1. 遗传算法
遗传算法是一种模仿自然界中优胜劣汰自然选择规则的随机搜索方法，该算法是从一系列的初始点 (被称为初始种群) 开始，通过循环执行选择、交叉和变异等遗传操作，逐步得到问题接近全局的最优解。
2. 并行机调度问题
考虑并行机调度中的实际需求定义如下并行机调度问题：设有m (m>1) 台并行机M1, M2, …Mm，需要加工n个工件，F时调度工作结束，每个工件订单零时刻到达，可在任一台机器上完成加工。工件一旦分配给某机器加工就必须加工完毕，不许中断。工件i在机器j上加工前准备时间为Zij，加工时间为Tij，工件i的到期时间为Qi，机器j一天的工作时间为Wj，启动成本为Sj，闲置成本权重比例为Rj，则工件i的完成日期Ci为本身加工前准备时间Zij (j为工件i的加工机器) 、加工时间Tij与机器j中i工件之前所有工件消耗时间之和，提前完成时间Bi为max (0, Qi-Ci) ，延迟时间Di为max (0, Ci-Qi) ，机器j的闲置时间为Ij (F减j上最后一个工件完工时间) 。问如何安排每台机器上所加工的工件及加工顺序使成本最小。
（三）算法设计
在Cheng的方案基础上，提出了一个染色体的改进的编码组成方式，重新设计了适应度函数和进化机制。
1. 染色体编码与适应度函数设计
并行机调度问题的染色体必须表示两个方面的信息：一方面确定工件加工所在的机器，另一方面确定每台机器上工件的加工顺序。本算法中染色体编码时用自然数序列表示工件排列，用含数字下标的分隔符*i (0
遗传算法演化过程的目的在于使适应度函数最小化，如果用B, D, S, I分别表示提前、延迟、重启和闲置成本，则演化的目的是要找到最好的排列使得：
F (B*, D*, S*, I*) =min{F (B, D, S, I) }, 适应度函数为F,
Bi, Di, Sj, Rj, Ij意义同上，α (Bi) , β (Di) 分别为提前和延迟完工成本函数，γj的值在机器j上有工件分配时等于1，否则为0。
2. 种群初始化
初始种群的个体分为两类，第一类个体随机生成;另一类个体可以按一定经验法则生成，比如可以把处理时间作为考虑因素，处理时间越短越先安排，确保在最短的时间里做尽可能多的工件，或者按到期日期为标准，越早到期的工件越早安排，可以使大部分工件如期完成。
3. 选择
选择过程的目的是为了从当前群体中选出优良个体，使他们有机会作为父代将其优良的个体信息传递给下一代，使子代向最优解逼近[1]。判断个体优良与否的标准是各自的适应值。每个个体的选择概率采用基于排序的适应度分配 (rank-based fitness assignment) 方法，种群按适应度进行排序，个体的生存概率使用Baker提出的线性排序计算公式求得：其中i为个体排序序号，N为种群大小，1<=η+<=2, η–=2–η+。然后用轮盘赌选择法 (roulette wheel selection) 来决定每个个体的选择份数，选择后的N个个体送到配对库，以备配对繁殖。
4. 交叉
交叉是结合来自父代种群的信息产生新的个体，依据个体基因编码表示方法的不同有多种交叉算法。这里采用两点顺序交叉 (OX) ，顺序交叉能够保留排列并融合不同排列的有序结构单元。如有下面两个父个体，交叉操作步骤如下：
(1) 随机选择两个交叉点”|”，保留交叉点之间的中间段不变。
(2) 把父个体2从第2个交叉点作排列，到达表尾时返回表头继续，得到排列*3 2 7*4 8 4 1*2 5*1 3 6，减去父个体1中已有基因部分4 5*1*3 2得到排列顺序7*4 8 1*2 36，再将这个顺序从第2个交叉点开始复制给子个体1，以此决定子个体1对应位置的未知码x，生成子个体1即q1: (3 64 5*1*3 2 7*4 8 1*2) ，同样产生子个体q2: (*3 2*2 5*13 6 7*4 8 1 4) 。
5. 变异
变异是子代基因按小概率产生的变化。同样可以采用多种方法实现基因变异，如可以采用交换两个基因位置实现变异，但是这种方法个体变异较小，不利于新个体的生成，特别是当交换的两个基因都是数字时，新个体只是改变了两个工件的加工位置。这里使用另外一种方法实现变异操作即首先随机选取父代中的某优秀染色体，对照染色体基因个数 (m+n) 随机生成一个二进制序列，将染色体中对应0的基因选为一组，对应1的基因选为另一组，两组基因重新组合得到子个体。变异操作如下：
6. 种群进化与停止准则
标准遗传算法若在群体选择前 (或后) 保留当前最优值，则最终能收敛到全局最优值。本算法通过改进标准遗传算法，在群体选择作用前保留当前最优解，则保证本算法在某些情况下收敛到全局最优解。
停止准则一般预先设定一个最大的繁殖代数Nmax，在繁殖过程中进行到最大的繁殖代数则停止运行。
综上所述，本并机行排序问题的遗传算法伪码如下：
（四）结果
设有45个工件要在3台机器上加工。在工作提早与延迟完成成本方面，按照工件的重要性将提前与延迟完成成本公式分为三类：
对重要性不高的工件成本公式为：
对重要性一般的工件成本公式为：
对优先权高的工作成本公式为：
工件在不同机器上的加工时间，加工前准备时间，机器启动和闲置成本表略。种群大小为50，最大遗传代数为80，交叉概率为0.6，变异概率为0.01。按本文与Cheng所提算法分别演算，所得结果如表1所示：
由表1可知，本文算法有助于使最后解答的染色体之间的差异性小，每次运算后的解接近最优解。
（五）结束语
本文重新设计了染色体的组成方式，问题的解空间表示得更明确，设计了算法进化机制，求解效率得到提升，考虑了并行机调度问题中的更多实际因素，本算法有一定的实用价值。然而实际影响并行机调度的因素并不限于本文所讨论的范围，另外适应度函数中的权重比例，也需要根据不同工厂的需求做适当的调整。今后将研究影响并行机调度的其它一些因素，使并行机调度问题与实际应用紧密结合，并且考虑把遗传算法与其它算法结合，使遗传算法收敛更快更高效。
摘要：为解决接近实际生产状况的并行机调度问题, 将工件延迟与提前完成成本、机器闲置时间成本、机器启动成本列入考虑因素。在遗传算法的设计上, 提出了一套染色体的组成方式, 设计了适应度函数和进化机制, 使其能较好地表示问题的解空间并提升求解效率, 具有一定的实用价值。
关键词：并行机调度,遗传算法,适应度
参考文献
[1]何军辉, 周泓.求解含调整时间并行机排序问题的遗传算法[J].系统工程理论方法应用, 2002, 12.
[2]欧锦文, 施保昌.平行机排序邻域搜索算法设计[J].计算机工程与应用, 2003, 18.
[3]Cheng, Runwei.Minmax Earliness/Tardiness Scheduling in Identical Parallel Machine System Using Genetic Algorithms[J].International Conference on computers and industrial Engineering, 1995:29:513-517.
[4]张聚, 李平.基于演化算法的车间作业调度问题的求解方法[J].浙江大学学报, 2004, 12.
并行遗传算法 篇2
基于MPI并行实数编码混合遗传算法的波阻抗反演
地球物理反演的`局部线性方法易使解陷入局部极值,并严重依赖初始模型,而传统的遗传算法在优化应用中存在局部搜索能力弱、早熟收敛等问题,为此,提出了一种解决地球物理反演问题的并行实数编码混合遗传算法(MRCGA).该方法采用拟网格法初始种群、综合交叉策略和线性算子,实现了并行实码混合遗传算法.理论模型试算证明了该算法反演地震波阻抗的有效性.
作 者：白俊雨 赵俊省 潘凌飞 郭嵩魏 Bai Junyu Zhao Junsheng Pan Lingfei Guo Songwei 作者单位：成都理工大学地球探测与信息技术教育部重点实验室,四川,成都610059 刊 名：勘探地球物理进展 英文刊名：PROGRESS IN EXPLORATION GEOPHYSICS 年，卷(期)：2009 32(4) 分类号：P631.4 关键词：MPI 遗传算法 实数编码 初始种群 综合交叉策略 线性算子 波阻抗反演并行遗传算法 篇3
关键词:试题库;组卷;遗传算法;伪并行;精英个体
中图分类号:TP18文献标识码:A文章编号:1000-8136(2009)17-0091-03
在国内,近年来题库的建设受到高度重视。目前,题库系统有3类:基于单机、基于局域网和基于WEB。基于单机的系统已经逐渐被淘汰,其缺点是题库的建立和维护非常困难;基于局域网的系统通常用于比较严格的考试,基本上都是由某一重要的大机关封闭运行,缺乏开放性,无法真正在教学过程中发挥其应有的作用。基于WEB的系统具有集中管理、共享使用、简单易用、开放性强的特点,可提供考试、自测、联机评卷等多项功能,还能提供强大的统计与分析功能,揭示全方位的教学过程信息。相对来说,现在的开发主流为基于WEB的系统。而作为该系统的组卷策略因其在整个系统中的核心地位成为研究的热点。
遗传算法是一种模拟自然选择和遗传机制的全局概率寻优算法,它的寻优过程是一个迭代过程,通过基因遗传机制将每一代的基本特征遗传到下一代。该方法能解决随机算法的盲目随机性,能从群体中选择更满足条件的个体,具有很强的智能性。同时,由于遗传算法具有内在的并行性,不会出现像回溯试探法一样计算量大的问题。许多研究人员对基于遗传算法的试题生成方法作了深入的研究,取得了比较好的效果。本文对标准的遗传算法进行了改进,提高了试卷生成的效率。
1 组卷问题分析
1.1 试题命题的基本原则
1.1.1 目的性原则
考试的功能是多方面的,目的不同,试卷编制的结构和试题的难度就不同。前面提到,平常的检测主要是诊断教学内容的掌握情况,期中、期末考试则主要是考查考生的学习水平。
1.1.2 科学性原则
编写的试题不但要求其本身没有科学性和知识性错误,而且试题表述要规范,尽可能采用学科术语。
1.1.3 简洁性原则
试题的语言表达要简洁、精练,每道试题应该清楚地提出一个或几个独立而明确的问题,学生阅读题干后能够明确他们要解答的内容,不存在理解题意的障碍。
1.1.4 层次性原则
层次性原则就是根据学生认知结构的差异性、教材内容的难易度、教学大纲要求,编制的试卷必须具有一定的梯度。
1.1.5 创新性原则
创新性主要体现在试题的新颖性上,而试题的新颖性则主要反映在取材的新颖性、创设情境的新颖性、设问的创新性以及考查角度的独到性等方面。严格来讲,在一份试卷中,至少应有20%~
30%的试题是新命题才算较好地体现了创新性原则。
1.2 试题分析
在智能教学系统的研究中,一个非常重要的课题是怎样在已生成的题库中自动生成满足教学和教师要求的试卷。通常,全部试题按内容分为若干篇章、题类和多个细目,每一道试题又包含多个属性,但过多的约束条件会增加实际自动组卷的难度、降低效率。由于多约束条件的重要性是不一样的,且它们之间存在内在的联系,有必要选择一些核心属性作为组卷的约束条件(总时间、试卷分数、试卷难度系数、题型比例、能力层次、知识点、区分度、已被选择次数、最近被选时间等),具体属性定义如下:
(1)题型:用正整数1～6分别代表选择题、填空题、判断题、简答题、作图题和计算题。
(2)难度系数:设P为试卷的难度系数,x为试卷平均分,w为试卷满分,则试卷的难度为: p=1-(1)
试题的难易程度分五级,难:0.8～1.0,较难:0.6～0.8,中等:0.4～0.6,较易:0.2～0.4,易:0.0～0.2。
(3)区分度:取值1～3,分别表示优秀、良、差3种状态。
(4)知识点:某道题属于某门课程的哪个知识点。用1～20代表学科的20个知识点。
(5)分值:某题的分数。
(6)答题时间,估计该题所需的时间。
(7)已被选择次数:某题被选重的次数。
(8)最近被选时间:某题最近被选的时间。
1.3 组卷模型的建立
组卷主要是根据给定的约束条件(总时间、试卷分数、试卷难度系数、题型比例、能力层次、知识点、区分度等)从大量的试题库中抽取出最优的试题组合,由此可见,组卷问题是一个具有多重约束的组合优化问题。因此,组一份m道试题的试卷,并且每道试题有n项属性,就相当于构建了一个m×n的目标矩阵。(本论文n=6)。
目标矩阵应满足以下的约束条件
(由用户给定,即试卷分数的约束);
(由用户给定,即试卷难度约束);
(由用户给定,即试卷区分度的约束);
我们设定整套试卷综合指标f来反映与用户要求的误差,实际试题生成工作中,上述各项指标的重要程度是不相同的,因此,整卷指标f就是各项指标与用户要求之间误差的加权和,为了避免各个误差的相互抵消,各指标与用户要求的误差都取绝对值,可以用如下方式表示:f=wi(e1+e3+e4)+w2e2+w3e5。(9)
在公式中wi表示第i个指标的权值,ei表示第i种约束条件与目标值的偏差(取绝对值)。
1.4 遗传算法求解
1.4.1 编码
采用分组实数编码策略,试卷初始种群也不是随机产生,而是根据题型比例、总分的要求随机产生,使得初始种群已经满足了题型和总分的要求。
1.4.2 选择操作
选择操作的目的是为了从当前群体中选择优良的个体,使它们有机会作为父代为下一代繁殖子孙。本文采用赌轮选择。
1.4.3 交叉操作
由于分段实数编码,结合单点交叉和一致交叉,我们采用段内/段间两种交叉方式实现种群中个体的交叉操作,具体操作方法如下:
(1)仿照单点交叉操作的一、二步,对种群中个体进行配对,并对每一对配对个体随机设置一个交叉点。
(2)根据交叉点所在的位置进行段间/段内交叉操作。
1.4.4 变异操作
本文将采用自适应变焦变异,以加强变异算子的局部搜索能力。
1.4.5 精英保留策略
在遗传算法搜索的过程中,对其所发现的最佳个体作适时“记录”,则全局最优个体总能被找到。在遗传算法中耦合这种最佳个体记录的策略,被称之为精英保留策略。
1.4.6 算法的基本流程
步骤1分段实数编码。
步骤2复制:为了避免最优基因丢失,提高全局收敛性和计算效率,将适应值最优的m条染色体复制到精英个体序列库中。
步骤3选择、分组:随机将种群按比例分组,并行进行改进的遗传算法和标准遗传算法的遗传操作(选择、交叉、变异);各组的最优值通过迁移算子传给下一代。
步骤4交叉。
步骤5变异。子代中,两种遗传算法伪并行运算,相互之间通过迁移算子进行信息交换,得出子代个体,选出同样数目的最优染色体与精英个体序列库进行比较,取50%高适应值的个体保留在库中,其余留给子代。
步骤6判断是否满足收敛准则,满足,输出搜索结果;否则,执行第二步。
改进的遗传算法的基本流程图见图1。
2 结论
我们通过模拟题库在MATLAB平台上对算法性能进行测试,以课程《电路基础》试卷为例。在测试中,题库中共设置4种题型,整个试题库根据题型分为4部分,每个题型对应的试题表中的试题数分别为100、100、50、50。各题的属性已经事先设定好。
取群体规模为50,对比标准遗传算法与改进的伪并行遗传算法在生成满足要求的组卷系统中的应用,见表1。
从实验结果可以看出,改进的伪并行遗传算法能更有效地解决试题库智能组卷问题,与其他方法相比,它能较早地找到满足条件的群体。同时,本文也为解决类似于该问题的多重约束目标的问题提供一种新的、有效的途径。
Research on an Intelligent Generating Papers based on the
Improved Pseudo-Parallel Genetic Algorithm
Guo Lixin,Xie Keming
Abstract:The traditional way of test paper composition has many flaws, for example the time test paper composition needed is long and the efficiency is low. This paper proposed a improved Pseudo-Parallel Genetic Algorithms, it needs short time in test papers composition and has a high success ratio, and has fine function and usability. Simultaneously it improved the test papers’ quality and the test becomes more scientific and objective, has a vital practical significance to implement the work smoothly.
一种主从式并行遗传算法设计 篇4
遗传算法是一种模拟生物在自然环境中的遗传和进化过程而形成的概率搜索算法,它模仿生物在自然环境中的遗传和进化机理。它将问题的解表示二进制编码串。在搜索前给出一定种群大小的染色体群,然后按适者生存、优胜劣汰的遗传机制,从中选出较适应环境的染色体进行复制,再进行交叉、变异过程。最后就会收敛到最适应环境的一个染色体上,即问题的最优解。
早在70年代,遗传算法的奠基人Holland通过模式定理的分析阐述了它所隐含的固有并行性。近年来,随着并行计算研究的深入和发展,遗传算法的并行实现研究也得到了进一步发展。
2 并行遗传算法与MPI并行算法
2.1 并行遗传算法
就目前的研究现状来看,并行遗传算法可以分为主从模型、粗粒度模型和细粒度模型三种[1]。
主从式模型的特点是将个体适应度的计算交给各个从处理机并行进行,而遗传操作由主处理机完成。1992年Abramson在共享存储的并行计算机上实现了主从式并行遗传算法,用于时间表的优化。主从式方法在适应度评估很费时、远超过通信时间的情况下才有效,否则通情时间超过计算时间反而会降低速度。而且这种方法要求有同步机制,这就会导致主进程忙而子进程闲或反之,引起负载不平衡,效率不高。粗粒度模型就是将群体划分成若干子群体,它们独立地进行演化,每经过一定的时间间隔就将它们的最佳个休迁移到其它子群体中。粗粒度模型是目前应用最为广泛的一种并行遗传算法模型,它主要开发群体之间的并行性。细粒度模型将群体划分成众多的小群体,与粗粒度模型相同,选择、变异等遗传操作均限于子群体内部,不同之处在于细粒度模型是通过同类群的重叠(overlap)完成个体迁移的[2]。
2.2 MPI并行算法
并行计算(Parallel Computing):简单的讲,就是在并行计算机上或分布式计算机等高性能计算系统所作的超级计算,其物质基础是高性能并行计算机(包括分布式网络计算机)[3]。
消息传递接口MPI(Message Passing Interface)是为MIMD模式分布式存储器并行计算机和机群系统制定的消息标准。目标是为这类机器建立一个可移植的、易使用的标准消息传递环境。MPI提供一个独立于平台的消息传递库标准,实现程序可移植性的目的,支持PC机、工作站和几乎所有并行机,用MPI编写的程序可不加修改的应用于所有的操作系统平台。MPI环境的初始化和结束流程如下:在调用MPI例程之前,各个进程都应该执行MPI_INIT,接着调用MPI_COMM_SIZE获取缺省组(group)的大小,调用MPI_COMM_RANK获取调用进程在缺省组中的逻辑编号(从0开始)。然后,进程可以根据需要,向其它节点发送消息或接收其它节点的消息,经常调用的函数是MPI_SEND和MPI_RECV。最后,当不需要调用任何MPI例程后,调用MPI_FINALIZE消除MPI环境,进程此时可以结束,也可以继续执行与MPI无关的语句。
3 基于MPI的主从式遗传算法的设计
3.1 算法设计
该模式采用主从式的MPI程序设计思想:将主进程设计为寻找当前代的最优个体并将其发送给各个从进程,从进程进行串行的GA,寻找最优个体给主进程。
1)产生一个进程(该进程为主进程,用于存放和发送当前最优个体);
3)各从进程进行串行GA,当从进程中遗传代数被n整除,从进程发送最优个体至主进程;
4)主进程选择当前各从进程中最优个体,发送给各从进程;
5)各从进程把主进程选择的最优个体替换各从进程当前代种群中适应值最低个体;
6)若各从进程皆满足条件,执行第7)步,否则执行第3)步;
7)算法终止。
3.2 并行程序间消息传递实现的核心代码
主程序代码:
4 实例测试
4.1 问题描述
针对求遗传算法解的精度和解的效率,常常采用经典的测试遗传算法效率的OliverTSP问题来测试。OliverTSP问题的30个城市位置坐标如图表1所示[4]。
4.2 测试方法和环境
测试方法是:通过从硬盘的文件中读取数据来设置染色体长度、种群的规模、交叉概率和变异概率等参数,分别记录串、并行程序到达指定代数时最短路经的长度。需要指出的是遗传算法是一种概率搜索算法,每次的计算结果各有差异,因此算法的计算结果中最短距离路径的长度指得是计算5次的平均值。测试环境是:通过将四台机器加入一个域中,利用域中的同一个用户来调用四台IBM机器中的资源,实现了并行环境。测试的硬件环境如表2所示,测试的软件环境如表3所示,遗传算法参数如表4所示。
4.3 测试结果及结论
通过多次试验和研究总体的发展趋势如图1所示,不难得出下面结论:
并行遗传算法提高了遗传算法的收敛速度,缩短了达到给定精确度的耗时。但是就遗传算法的精确性而言还是由遗传算法本身的特性决定的。
摘要：该文对串行遗传算法进行了并行设计,加入对当前通用消息传递接口MPI的支持,形成了一个主从式并行遗传算法。针对该算法用经典的测遗传算法效率的OliverTSP问题进行测试,得出并行遗传算法可以更好的提高遗传算法的收敛性。
关键词：主从式并行遗传算法,MPI
参考文献
[1]陈国良,王照法,庄镇泉,等.遗传算法及其应用[M].北京:人民邮电出版社,1996.
[2]郭绚,石晓虹.并行遗传算法的性能分析[J].航空计算技术,1998,28(3):86-89.
[3]陈国良.并行计算——结构～算法～编程[M].北京:高等教育出版社,2001.
并行遗传算法 篇5
二维自适应非结构网格DSMC并行算法研究
研究了二维自适应非结构网格DSMC并行算法实现的过程.首先提出了一类非结构网格自适应策略,有效降低了网格尺度对计算结果的影响,提高了流场的.分辨率;然后基于PC-CLUSTER群机并行体系结构与消息传递库MPI并行环境,利用分区并行思想,设计了非结构网格DSMC并行算法,节约了计算时间.利用For-tran90的动态分配内存技术编制了通用计算程序;最后对过渡流域高超声绕流进行了数值模拟,计算结果初步验证了算法的可行性与有效性.
作 者：王学德 伍贻兆 夏健 林晓宏 WANG Xue-de WU Yi-zhao XIA Jian LIN Xiao-hong 作者单位：王学德,林晓宏,WANG Xue-de,LIN Xiao-hong(南京理工大学动力工程学院,南京,210094)伍贻兆,夏健,WU Yi-zhao,XIA Jian(南京航空航天大学,航空宇航学院,南京,210016)
刊 名：计算力学学报 ISTIC EI PKU英文刊名：CHINESE JOURNAL OF COMPUTATIONAL MECHANICS 年，卷(期)：2009 26(2) 分类号：V211.3 关键词：自适应非结构网格 DSMC 并行算法 MPI并行分布式遗传算法的研究 篇6
并行计算理论的研究始于20世纪70年代,经过40多年的发展,其技术日趋成熟。在生活中有大量的实际应用,比如天气预报、地震数据处理、飞行器数值模拟等等,这些领域的事务处理往往需要几十万亿甚至几百万亿次的浮点运算,并行计算[1]是适合这类事务处理的一种技术。近年来云计算的兴起,使得分布式计算技术也逐渐趋于成熟,并得到了广泛的应用,它把网络上分散于各处的计算机资源汇聚起来完成各种大规模的计算和数据处理任务。
遗传算法(genetic algorithm,GA)基于达尔文自然选择定律以及孟德尔遗传理论,它模拟自然生物遗传和选择的过程将适应度相对高的个体保留,适应度相对低的个体逐渐淘汰,循环重复这一过程,直到满足停止条件,因此它是一种迭代搜索算法。遗传算法的全局搜索比较容易实现与加强,目前在许多领域有广泛的应用,比如建筑的结构性优化、化工领域的资源分配、计算机自动控制等等。但在高维、超高维多模态问题中,传统遗传算法仍会表现出一些不足,全局搜索能力不足,易限于局部极优,收敛速度以及精度有待提高。
文章针对传统遗传算法用于高维、超高维多模态问题时存在的不足,提出了基于PVM的并行分布式遗传算法(PVM-IMGA)。PVM-IMGA算法基于PVM平台,采用了一种比较好的适应度评估方法,并对交叉算子、变异算子做了一些改进,使其具有自适应加速特性。为了验证改进工作的有效性,文章最后对一高维多峰值函数进行了实验测试,实验结果表明PVM-IMGA算法克服了传统遗传算法易限于局部极优的问题,全局搜索能力、收敛能力都有了比较明显的提高。
2 问题分析
高维、超高维问题的一个特点是其搜索空间巨大,要在巨大的范围内搜索到合适精度的目标可行解,耗时往往较长,有时甚至无法找到。多个极值是多峰值问题的特点,多峰值问题较一般的单一峰值问题,寻优难度要更大,算法易陷于局部极值,对遗传算法的全局搜索能力会有更高的要求。
3 优化目标
在多峰值问题中,一般是寻找单类型的所有极值,即在有限定义域、可接受的时间范围内要么寻找所有极大值,要么是极小值。本文实验测试所用的多峰函数寻找的是极小值。
为了检验论文提出的并行分布计算方式的有效性,笔者将论文改进后的遗传算法分别在PVM并行环境以及单机环境对Keane’s Bump函数进行实验测试20次,然后求它们的平均时间。两种算法的实验条件相同,例如相同的种群规模、迭代次数等等。图2是在不同维度下,使用PVM-IMGA算法以及单机环境下的IMGA算法的平均搜索时间变化趋势图。从图我们可以看到,在较低维度的条件下,单机环境下的IMGA算法的搜索时间要比并行环境下的PVM-IMGA算法的执行时间要短,但是当维度逐渐增高之后,它们的搜索时间的差距有了一些变化,当维度高到一定程度时,PVM-IMGA算法的执行效率要比单机环境的IMGA算法要高。另外,当维度达到一定高度后,IMGA算法无法在指定的迭代次数内找到所有极值,当增加种群规模以及迭代次数时,其搜索结果会有一点变化,但是仍然是无法达到多峰值问题的寻优要求。之所以出现这样的结果,究其原因,当维度比较低,问题的搜索空间不是很大时,IMGA具有较好的求解能力,可以比较快速的找到可行解,PVM-IMGA算法虽然也具有求解能力,但是因为网络传输需要比较长的时间,所以PVM-IMGA算法的耗时比IMGA算法要长。但是当维度较高,搜索空间比较巨大时,IMGA算法的局限性就暴露出来了。而PVM-IMGA算法因为能将搜索空间分块细化,并交由不同的计算节点来执行,执行效率开始变得更高。当问题维度增大到一定程度时,笔者可以通过调整数据块大小以及增加计算节点来提高算法的搜索效率。
为进一步验证PVM-IMGA算法的稳定性以及收敛能力,笔者对算法能收敛到的最小极值进行统计,并与文献[5]的DE、ABC、HABC算法,文献[3]的IMBF-GA算法进行比较。从表1的4项实验数据可见,在收敛能力和稳定性方面,PVM-IMGA算法皆优于DE、ABC、HABC、IMBF-GA算法,说明PVM-IMGA算法在高维条件下,对多峰函数具有较好的收敛能力,文章针对多模态问题,对传统遗传算法进行的多项修改是有效的。
文献[3]中提到IMBF-GA算法在一定维度下,搜索到所有极值的概率是比较高的,但是当维度增加时,成功率会下降。对于本文的PVM-IMGA算法,如果去除并行分布式计算形式,仅使用单机运行,其运行效果与IMBF-GA算法大致类似,增大种群规模以及迭代搜索次数尽管能在一定程度上提高成功率,但是当函数维度达到一定程度后,算法执行效率、收敛效果仍然难以让人满意。并行分布式计算方式是解决超大规模计算的有效手段,这也是当今云计算与分布式系统流行的一个重要原因。
摘要：传统遗传算法在面对一些搜索空间巨大的复杂问题时,其表现往往难以令人满意。作者针对传统遗传算法解决高维多峰值问题时可能会出现的困难进行了分析,然后根据困难出现的原因,基于PVM设计了并行分布式遗传算法,并对适应度评估、交叉、变异算子做了一些改进,旨在加强算法的全局搜索能力,提高算法的收敛速度。为了验证算法多项措施的有效性,对一多峰函数在高维条件下进行多方面的测试,实验结果表明这几项措施是有效的。
关键词：并行,分布式,多峰,遗传算法
参考文献
[1]Kai Hwang.云计算与分布式系统:从并行处理到物联网[M].北京:机械工业出版社,2013.
[2]刘洪杰,王秀峰.峰搜索的自适应遗传算法[J].控制理论与应用,2004,4(21):303-310.
[3]黄春.改进遗传算法的函数优化及应用[D].南宁:广西大学,2015.
[4]Adam.Parallel Virtual Machine:A Users'Guide and Tutorial for Networked Parallel Computing[M].The MIT Press,1994.
基于遗传算法的并行生产调度的研究 篇7
关键词：退火算法,遗传算法,并行,生产调度
作业调度问题在CIM中受到了广泛的关注[1,2]。作业调度在生产中发挥着两方面重要作用:一方面,接受计划决策信息,在空间和时间上合理配置任务和资源,形成具体生产实施方案,驱动整个生产系统高效运作,保证计划的实现;另一方面,接受生产过程的实际信息,通过统计分析,有机协调整个生产系统,并向决策层反馈计划执行情况。
研究表明,调度问题中的绝大多数属于NP难题[3,4],不存在有效的最优求解算法。有鉴于此,本文提出了一种基于改进的人机交互式的并行作业调度的求解方法,并在遗传算法初始种群中允许用户输入有效的作业调度安排,从而提高了初始种群的染色体的质量并且增加了染色体来源的多样性,提高遗传算法的效率。本文采用遗传算法,对并行生产车间作业调度属于静态调度领域中的Job Shop调度问题进行了研究,并用软件实现了算法。
1 并行生产模式
传统的生产调度模式,可以理解为一种垂直的方式,即有了新的生产任务,就把它安排到已有生产任务的后面。在市场竞争日益激烈和经济全球化的今天,这种生产调度模式已经不受欢迎了。这种模式的缺点是:不能从全局优化生产作业,使得产品生产周期延长,设备利用率低,造成企业资源浪费,影响企业的市场反应能力和竞争能力。
并行生产任务的调度,在我国是一种常见的生产组织方式,它区别于连续型生产。生产制造的各个环节往往是并行进行的,各个环节之间通过工艺要求来相互衔接,并行生产车间作业调度实际就是车间生产作业的排序问题,它可以描述为:已知N个工件按确定的工艺路线通过M台设备加工,要求确定各台机器上工件的加工顺序,使得预定目标达到最优。但是现有的作业调度模式,缺乏整体的优化,仍然会出现整体效率低的情况,并且不能从全局考虑,利润最高的任务得不到及时的完成,实现企业利益的最大化。
2 作业调度的数学模型
车间作业调度的优化数学模型可以有许多不同的优化目标,以完成加工所需时间最短为优化目标的数学模型如下式[5,6]。
式中,tMi,j为第i设备上的第j加工的加工时间;tWi,j为第i设备上的第j加工的等待时间;p为设备数;qi为第i设备上的最大加工数;tSr,l为第r工件的第l工序的加工开始时间;tEr,l为第r工件的第l工序的加工结束时间;tUi,j为第i设备上第j加工的开始时间;tVi,j为第i设备上第j加工的结束时间;m为工件数;nr为第r工件的最大工序。
目标函数中,表示安排在设备i上进行加工的所有加工工序(qi个加工工序)的加工时间tMij和等待时间tWij之和。也就是完成加工任务,设备i所应该服务的时间。此服务时间不仅包含设备的加工时间也包含设备的等待时间。目标函数式(1)代表最长服务时间,因为加工是并行进行的,所以这个最长服务时间也就代表整个加工任务完成所需的时间。整个加工任务完成所需的时间是指加工完成时间和加工开始时间之差,代表加工完成所需的等待时间。
约束tSr,l>tEr,l-1表示第r工件的第l工序的加工开始时间必须大于第r工件的第l-1工序的加工结束时间。这个约束保证了同一工件的加工工序前后不会颠倒。
如果所有的任务都可以按时完成,就可以满足企业最大化利润。但是如果时间不允许完成所有加工任务,则可以按照时间最短和利润最大化来优化。按照每个生产任务的利润进行加权,然后再进行任务调度。
3 遗传算法相关算子的设计
3.1 编码
我们直接将生产任务编号作为基因进行编码,并且保证每个任务编号在染色体中只出现一次。如六个生产任务,用6 2 1 5 4 3来表示一条染色体。初始染色体的获得我们通过自动生成和手工输入相结合的交互式输入方式获得。自动获取的方式为:通过分析各个任务的优先级来生成,所生成的染色体优良率高,而且也易于编程实现。
3.2 选择算子
选择算子从群体中选择优胜的个体,淘汰劣质的个体,其目的是把优化的个体(或解)直接遗传到下一代或者通过配对交叉算子产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。常用的选择算子有以下几种:适应值比例选择、排序选择、联赛选择等。
并行生产调度中,会有许多非优的方案(其适应度值较低),此时仅有一个或少数几个较优解,若选择压力得不到控制,群体就过早收敛,无法得到进一步优化的解。因此,本文使用选择压力可有效控制排序选择算子。
3.3 交叉算子设计
交叉的作用在于将群体中原有的优良基因遗传给下一代个体,并生成包含更复杂基因结构的新个体。常用的交叉算子有一点交叉、两点交叉、多点交叉、一致交叉等。本文对任务的编码属于单纯方式,仅采用实数编码,不包括符号编码,针对这种级联编码的特点,以下设计了相应的交叉算子。
交叉与局部调整相结合的思想类似于多点交叉,具体实现如下:(1)交叉实现加工任务的互换,就是采用一点或两点交叉,交叉点选择在染色体上随机任务与任务之间,然后互换被选中的染色体片段;(2)局部调整只针对单个任务的染色体片段。在交叉中被选中的染色体片段上(包含一个或多个任务的编码),以一定的概率对加工任务实施一次单点交叉。
上述方法既能实现染色体的部分互换,又能进行个别的调整,改变了单一的染色体片段整串交换的模式,有利于为遗传算法探索新的解空间。
3.4 变异算子设计
基本遗传算法进行的变异操作是对每一个等位基因进行均匀变异,即以一个很小的变异概率对每一位基因实施变异操作。由于并行生产调度中的全部解都是可行的,问题是找出最优解,所以简单增大均匀变异的概率会破坏算法到最优解附近的搜索效果,可以通过附加新的变异方式来达到探索新的解空间的目的。
本文对生产任务的编码方式是统一的,当随意抽出一个或几个编码放到另一位置时,其物理意义相当于移动某一个或几个生产任务的先后顺序。根据这种特点,可以设计如下几种变异算子[7]:(1)随机抽取一个或连续几个任务,插入到另一位置;(2)随机选择两个任务,将它们互换;(3)随机选择一个或连续几个任务,将它们逆序排列,放回原位置或插入到新的位置;(4)随机选择一个或连续几个任务,将它们乱序排列,放回原位置或插入到新的位置。
3.5 保留策略
从遗传算法的选择策略上讲,精英保留策略是群体以概率1收敛到最优解的一种基本保障。精英保留策略以如下方式实现:如果上一代群体最佳个体的适应值大于当前群体最佳个体的适应值,则将上一代群体中最佳个体或者适应值大于当前代最佳个体适应值的多个个体直接复制到当前代,随机替代或者替代当前代中相应数量的最差个体。这样的策略,既保存了大部分优良个体,让算法始终保持探索新的解空间的能力,再结合冷却进度表来防止早熟。
冷却进度表是用于控制算法进程的一组参数的集合,包括控制参数的初值t及其衰减因子Δt、对应的Mapkov链的长度L和停止准则S,其选取原则参见文献[8]。
4 应用实例
图1是5个任务在3台设备加工的例子,5个任务的利润加权值排序为1、2、3、4、5,最后本算法得到的排序为1、2、5、3、4。假设本文给工件编号为01,02,…,n,设备编号为01,02,…,m,工件的每一步工序编号为01,02,…,则符号05.04.03符号表示工件05的04工序在设备03上完成。所在格的跨度代表所需时间的长短。
运用本算法的求解结果为见图2。
5 结语
从测试结果来看,混合遗传模拟退火算法在搜优率上较遗传算法和模拟退火算法有了较大的提高。从运算过程中的数据可以看出,由于混合遗传模拟退火算法中邻域的选择、变异发生的概率都取自模拟退火的接受概率,再加上它采取了适应度拉伸系数λ,使得遗传算法的“早熟”现象得到很好的解决。另外本文所采用的混合遗传模拟算法的还具有以下优点:(1)优化行为的增强。它具有GA算法的优化时间性能和SA算法可以最终趋于全局最优的优点,克服了GA算法“过早收敛”问题和SA算法优化时间性能较差的缺点。(2)优化效率的提高。它是一种并行而且具有自动保优功能的算法,同时利用GA和SA各自不同的邻域搜索结构相结合,这样使得算法在解空间中的搜索能力所增强,优化效率得到提高。(3)鲁棒性的提高。它的多点搜索消弱了SA算法对初值的依赖性,同时它还利用GA算法不影响平稳分布的特性,提高了整个算法的鲁棒性。如何自动提取任务的信息并计算器加权值,将是我们下一步对该方法进行改进的重点。
参考文献
[1]Barker J R,Mcmahon G B.Scheduling the general jobshop[J].Management Science,1985,31(1):594-598.
[2]Helena R L.Job-shop scheduling:computational study oflocal search and larger-step optimization methods[J].European Journal of Operational Research,1995,83(1):347-364.
[3]董斌,李颖,邵惠鹤.基于遗传算法的类Jop-Shop调度[J].控制与决策,1998,13(1):71-75.
[4]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999:104-193.
[5]李军,边肇祺.用于最优化的计算智能[M].北京:清华大学出版社,1999:49-116.
[6]Gold berg D E,Richardson J.Genetic algorithms with sharing for multimodal function optimization[C]//Proc.2nd Int.Conf.Genetic Algorithms and Their Applications.Hillsdale:Lawrence Erlbaum,1987:41-49.
[7]Larranaga P,Kuijpers C M H,Murga R H,Yur-ramendi Y.Learning Bayesian network structures by searching for the bestorderingwith genetic algorithms[J].Systems,Man and Cybernetics,PartA,IEEE Transactions,1996,26(4):478-493.
并行遗传算法 篇8
1 并行遗传算法
遗传算法始于一个初始群体, 群体中的个体都要进行这三种运算。运算后的结果如自然选择一样, 比初始群体具有更好的适应性。并行遗传算法就是一种很好的选择, 它能很容易的实现并得到一个很好数值解。除此之外, 并行遗传算法比遗传算法运算速度更快, 并且能得到一个更优结果[2,3,4,5]。标准的遗传算法以群体集合为运算对象, 对个体所进行的各种遗传操作都有一定的相互独立性, 所以它具有一种天然的并行结构。由于遗传算法的天然并行性, 人们认识到了对其进行并行处理的可能性, 从而基于各种并行计算机或局域网开发了多种并行遗传算法 (Parallel Genetic Algorithm, 简称PGA) 。开发并行遗传算法的主要目的是为了提高遗传算法的运算速度[7,8]。
2 目标函数
损伤由刚度减小率βi表示, 定义为减小刚度与初始刚度的比值。损伤结构的刚度矩阵[Kd]表示所有单元矩阵乘以减小因数的和[4]:
βi=0表示结构未损伤, 0<βi<1表示结构部分或全部损伤。
频率变化:
式中:下标0———初始未损伤状态;
λi———第i个特征值;
ωi———第i个频率。
模态保证标准:
式中:φiu———未损伤的第i阶模态向量;
φid———损伤后的第i阶模态向量。
MAC是一个无量纲的量, 范围从0到1, 代表了两组模态向量之间的关联程度, 1指完全关联, 0指完全不关联。
目标函数:
Fλ, 0, FMAC, 0表示结构未损伤时的值 (β=0) 。FD表示损伤补偿函数。当损伤补偿函数加到目标函数中, 还要包括最小损伤。由此, 由计算误差引起的错误损伤检测就可以避免了。罚函数如下:
此等式由Meruance和Heylen提出, 补偿了全部的损伤, 常数γ取决于计算模型的精确度。
最优问题定义如下:
3 算例
3.1 计算模型及基本假定
用一跨预应力混凝土简支梁进行数值模拟, 为了更好地观察结果, 简支梁外伸形成悬臂梁。如图1所示, 该模型有30个单元, 31个节点, 弹性模量是3.0×1010Pa, 密度是2500kg/m3, 面积是0.06m2, 惯性矩是4.5×10-4m4。
模态观测数据用结构的有限元模型模拟获得, 损伤用弹性模量折减来模拟。损伤工况设计如下[5, 7, 10]:
工况一:10号单元10%损伤, 20号单元35%损伤;
工况二:10号单元20%损伤, 20号单元35%损伤;
工况三:10号单元35%损伤, 20号单元35%损伤。
3.2 初始参数的确定
为了提高收敛速度, 避免过早收敛, 遗传算法的参数和算子取值如下:种群大小:N=75;变异概率pm=0.02;交叉概率ps=0.8。初始种群值为1[5,6,7,8,9]。
3.3 计算结果与讨论
迁移时段如图2所示, 以敏感度分析定义。得到的最优迁移时段是70。图3示出的是通过并行遗传算法收敛率的提高。
并行遗传算法 (PGA) 求解最优解的时间是500多秒钟, 而遗传算法 (GA) 则需要1000多秒。并行遗传算法运算时间是遗传算法的0.5倍。
三种工况的下的损伤探测如图4所示。
从图中可以看出, 损伤检测结果已经达到了完美的程度, 和模拟的损伤很接近, 但并不能说明实际的应用当中也有很好的应用, 所以这方面的研究工作将在以后进行讨论。
4 结论
本文提出了并行遗传算法检测结构损伤的方法。数值模拟结果表明相比于遗传算法, 并行遗传算法在表现上更进一步, 在计算结果相同的条件下, 计算速度是遗传算法的1.5倍。因此, 对于明确问题的并行遗传算法可以使结果得到改进。
本文提出的方法只是针对于预应力简支梁桥模型的损伤识别进行了研究, 对于其他结构, 如高层结构、框架结构等的损伤识别同样有很好的表现。提出的并行遗传算法定位、定量的识别了模拟的损伤, 但是没有考虑损伤发生时刻的检测。其在实际结构损伤中的应用也未做具体的分析实验。这些将在以后进行研究分析, 在损伤识别领域中, 并行遗传算法会有更好的发展。
参考文献
[1]Mares, C.and Surace, C.An application of genetic algorithms to identify damage in elastic structures[J].Journal of Sound and Vibration, 1996, (195) :195-215.
[2]袁颖.遗传算法在结构损伤识别中的应用研究[J].防灾减灾工程学报, 2005, 25 (4) :114-116.
[3]曾国荪.并行遗传算法分析[J].计算机工程, 2001, 29 (9) :96-98.
[4]Meruane, V.and Heylen, W.Damage detection with Parallel Genetic Algorithms and Operational Modes[J].Structural Health Monitoring, 2010, (9) .
并行遗传算法 篇9
车间调度问题JSP是一类满足任务配置和顺序约束要求的组合优化问题,是许多实际生产调度问题的简化模型,也是一类典型的NP完全问题,其研究具有重要的理论意义和工程价值。众多学者对此问题采用了各种方法进行解决,有一些传统优化方法如分枝定界法,Lagrangian松驰法。这些算法可以解决一些规模较小的JSP问题,但是随着问题的规模扩大,其计算量大量增加,例如15×15的JSP问题,是这些传统优化方法所无法解决的,于是一些研究者将一些人工智能优化方法应用于JSP问题的解决,如模拟退火[1]、禁忌搜索[2]、遗传算法[3]、移动瓶颈法[4]等。后来许多研究表明单一的算法对于解决一些NP问题,有时效果并不是很好,于是发展了很多混合算法。而对于遗传算法而言,它的全局搜索能力较强,而局部搜索能力较弱,于是往往会与一些启发式算法相结合,增强局部搜索能力。诸如将模拟退火与遗传算法结合[5]、禁忌搜索与遗传算法[6] 、禁忌搜索与模拟退火结合[7]等。
文献[8]中将JSP问题的调度分为半活动调度、活动调度和非延迟调度,三者关系是半活动调度包含活动调度,活动调度包含非延迟调度,活动调度的调度时间要优于半活动调度。他们证明了最优解包含在活动调度中,并提出G-T算法,它能产生所有的活动调度。文献[6]中提出了完全活动调度,完全活动调度是活动调度的一个子集,它的调度时间要优于活动调度,且包含了最优解。
JSP问题解的编码方式有多种,有基于工序的编码、基于优先规则的编码、基于先后表的编码和基于完成时间的编码等[9]。本文采用基于先后表编码的一个变种按机器分段编码的编码方法,此编码方法具有易于理解,便于遗传算子对同一机器的加工工序操作,解空间小的优点。但有一缺点:不是所有编码都是可行解,而本文PLFA算法,可以将可行解与不可行解均转化为完全活动调度。由于遗传算法本身具有良好并行特性,本文采用了主从模式的并行遗传算法模型,使用改进的启发算法PLFA G-T算法来产生完全活动调度的初始种群,使用LOX交叉算子与基于PLFA G-T算法的变异算子,最终形成了一种应用于JSP求解的并行混合遗传算法。
1 问题描述
假设现在m台机器,要加工n个产品,每件产品有若干gi(0<i≤n)道工序需加工。
已知条件如下:
(1) 产品每道工序加工的机器号,用矩阵M表示,其中mij表示i产品的第j道工序加工的机器号。
(2) 产品每道工序加工所需时间,用矩阵T表示,其中tij表示i产品的第j道工序加工所需的时间。
约束条件如下:
(1) 每件产品必须按规定的工序加工;
(2) 每一台机器同一时间只能加工一个产品。
优化目标是安排每台机器上所应加工产品的加工顺序,使得在尽可能短时间内完成所有产品的加工任务。
2 编码设计
将每个染色体R用分别对应于m台不同机器的m个子串构成,各子串是一个长度为n的符号串,每个符号由产品号与工序号组成i-j,表示i号产品的第j道工序,若产品的调度顺序严格按照各符号排列的先后顺序进行,则可能会与约束条件冲突而产生不可行解。例如一个两台机器和两件产品的JSP,若调度矩阵R为:
该矩阵表示,在机器1上加工顺序是产品2的第2道工序、产品1的第1道工序,在机器2上的加工顺序是产品1的第2道工序、产品2的第1道工序,这与约束条件1冲突,因此这是非可行解。要解决此问题有两种方法,一是在最终解码时,将此调度表看成优先表,当调度无法进行下去时,将后面最早可调度的工序提前调度,这种编码方式叫基于先后表的编码。例如对上面调度的解码,当发现机器1和2上都无法调度产品的第2道工序时,优先调度排在后面的产品1的第1道工序与产品2的第1道工序,然后再调度产品的第2道工序;另一方面,仍严格按照各符号先后顺序进行,修改遗传算子,保证产生的解是可行解。为区别于基于先后表编码,本文称之为按机器分段编码。由于PLFA算法不仅能将可行解转化为完全活动调度,也可以将不可行解转化为完全活动调度。因为,在解码时都是可行解,无须在解码时将不可行解转化为可行解了,所以本文将采用按机器分段编码,此编码方式更直观、更易于理解。假设每道产品有m道工序,每台机器加工n道工序,按机器分段编码的解空间为(n!)m。由于问题最终目标是安排每台机器上产品的加工顺序,因此,交叉算子和变异算子只有对每台机器上产品的加工顺序进行操作才是有效的。本文所采用的编码相对于按工序编码而言,便于对同机器上的工序顺序进行交叉和变异操作。
3 调度类型
如果在不改变机器加工顺序的条件下,没有工序可以提前,就称一个调度为半活动调度。如果在不推迟其他工序或破坏优先顺序的条件下,没有一个工序可以提前加工,就称一个调度为活动调度。若一个调度为半活动调度,则一定可以找到某些操作,在不推迟其他操作或破坏优先顺序的条件下,将其左移,插入到同一机器的空闲时间内,将其转化为活动调度。因此,活动调度的调度时间优于半活动调度,且最优解包含在活动调度中。在文献[6]中提出了完全活动调度,如果将一个活动调度的工序调度顺序倒转过来,即产品的最后一道工序先调度,该调度仍是活动调度,则称此调度为完全活动调度。图1所示为将一个活动调度转化为完全调度的过程,其中:(a)为一活动调度;(b)为将工序调度顺序倒转过来,从产品的最后一道工序开始调度,即半活动调度;(c)是将工序1-1左移,将(b)转化为活动调度;最后将(c)的工序调度顺序倒转回来便是(d)了。通过上述四个步骤将活动调度转化为完全活动调度,其调度总时间缩小了,由原来的11变为现在的9。完全活动调度的调度时间小于等于活动调度,且包含了最优解。
下面给出将一个按机器分段编码的可行解转化为活动调度的算法,该算法称之为Active算法:
算法1 Active算法
其中fijk表示产品i的j道工序在机器k上的完成时间;oijk表示产品i的j道工序在机器k加工的工序;r(oijk)表示oijk对应的产品i的j道工序到机器k的时间;S表示各台机器可加工的工序集合;f(o*)表示在S中o*是完成时间最早的工序;半活动调度的染色体为Rsemi,记转化后为活动调度的染色体为Ractive,两者都是按机器分段编码。
(1) 初始化S为所有产品的第1道工序集合;
(2) while(还有工序未被加工){
o*为满足f(o*)=min{f(oijk), oijk∈S}的工序,对o*所在的机器m*进行如下操作:
a) 若半活动调度染色体Rsemi的m*机器当前第一道工
工序在集合中{oijm∈S ,r(oijm)<f(o*)},则选择此工
序;否则,选择o*。记选中的工序为oi*j*m*
b) 在半活动调度染色体Rsemi中第m*行除去i*-j*,即
除去工序oi*j*m*,在活动调度染色体Ractive的第m* 行添加i*-j*,在S集合中除去oi*j*m*,添加产品i*的下道工序到S中。
}
下面给出将一个按机器分段编码的不可行解转化为活动调度的算法。由于该算法具有修复不可行解与将调度转化为活动调度的双重功能,因此,将该算法称之Repair and Active算法:
算法2 Repair and Active算法
(1) 初始化S为所有产品的第1道工序集合;
(2) while(还有工序未被加工){
o*为满足f(o*)=min{f(oijk), oijk∈S}的工序,对o*所在的机器m*进行如下操作:
a) 从半活动调度染色体Rsemi的m*机器加工工序中选一个最早出现的工序oi*j*m*,该工序且要在集合中{oijm∈S ,r(oijm)<f(o*)}
b) 在半活动调度染色体Rsemi中第m*行除去i*-j*,即除去工序oi*j*m*,在活动调度染色体Ractive的第m*行添加i*-j*,在S集合中除去oi*j*m*,添加产品i*的下道工序到S中
}
以上两个算法主要区别在于对o*所在的机器的工序选择上。Active算法选择的是当前第一道工序且要在集合{oijm∈S ,r(oijm)<f(o*)}中或o*,其结果是在不推迟其他操作或破坏优先顺序的条件下,将一些工序左移,插入到同一机器的空闲时间内,将半活动调度转化为活动调度。Active算法也能将不可行解转化为活动调度,但是一些不可行解转化后可能出现同质化,因为不可行解的当前第一道工序经常不在集合{oijm∈S ,r(oijm)<f(o*)}中,使得只能选择o*。例如一不可解某机器的加工工序是(1-6,2-3,4-5,3-2,6-4,5-1),工序1-6要较晚才能被加入到可调度集合S中,因此只能选择o*。Repair and active算法选择的是最早出现在m*机器的加工工序中且在集合{oijm∈S ,r(oijm)<f(o*)}中的工序,可以保持原有调度的加工工序的大部分调度排序,保证种群的多样性。Repair and Active算法也可应用于可行解,将其转化为活动调度,但可能在将一些工序左移时,会推迟其他操作或破坏优先顺序,相当于原可行解有可能产生变异。在没法判断原调度是可行解还是不可行解时,若想增加解的多样性,可用Repair and Active算法,若想保持可行解的优质特性,可用Active算法。在遗传算法迭代前期,可用Repair and Active算法,增加种群多样性,在后期可用Active算法加速收敛。
下面是将一个按机器分段编码转化为完全调度的算法,将该算法称之为基于按机器分段编码的完全活动调度算法PLFA:
算法3 PLFA算法
(1) 若原调度是可行解用Active算法,是不可行解用Repair and Active算法,将该调度变为活动调度;
(2) 将活动调度染色体编码倒转过来;
(3) 加工顺序更改为从产品最后一道工序开始加工,第一道工序最后加工,调用Active算法;
(4) 将编码倒转回来。
4 初始种群
初始解对最终的搜索结果有着重要的影响,不好的初始解将可能导致需要更长的搜索时间得到最优解,还可能降低获得最优解的可能性。G-T算法是J. Giffler 和 G.L. Thompson 在1963年提出的,生成的解都是活动调度的[8]。本文对G-T算法进行了改进,使之产生的解都是完全活动调度,我们把改进的G-T算法称为PLFA G-T算法。本文便用PLFA G-T算法来产生初始种群,具体算法描述如下:
算法4 PLFA G-T算法
(1) 将S初始化为所有产品第1道工序的集合;
(2) while(还有工序未被加工){
o*为满足f(o*)=min{f(oijk), oijk∈S}的工序,对o*所在的机器m*进行如下操作:
a) 从集合中{oijm∈S ,r(oijm)<f(o*)}中随机确定一个操 作oijm,在矩阵R的m*行中添加i-j;
b) 并在集合S中除去oijm,添加产品i的下道工序到S中;
}
(3) 调用PLFA算法作用于R。
5 交叉算子
交叉算子是遗传算法的主要算子,直接决定了遗传算法的全局搜索能力,它需要能够很好地继承父代染色体的一些特性。本文采用的线性次序交叉(LOX)算子[10],就可较好地继承父母的基因。具体而言,首先随机确定两个交叉位置,交换交叉点之间的片段,并在原先父代个体中删除将从另一父代个体交换过来的基因,然后从第1个基因位置起依次在两交叉位置外填入剩余基因。例如,先随机选择一对父母染色体,然后随机选择要进行交叉的机器号,使用LOX算子交叉在这些机器号上加工的工序。如选出一对父母染色体p1、p2分别为:
选出的机器号是2,则对2号机器的加工工序执行LOX交叉,交叉点的位置为2和4,则片段(1-2,2-2,2-4)与(1-2,3-1,3-5)将交换,在p1的2号机器的加工工序上删除(1-2,3-1,3-5)后剩余(2-2,2-4,1-5),然后将片段2在剩余基因的位置2处填入,得到后代1的2号机器加工工序(2-2,2-4,1-2,3-1,3-5,1-5),相应的后代2的2号机器加工序为(3-1,3-5,1-2,2-2,2-4,1-5),生成的子代为:
此交叉算子能较好继承父母的优秀基因。但由于采用的是按机器分段编码,交叉有可能产生非可行解,所以须对交叉结果进行矫正,将产生的非可行解变为可行解。由于PLFA算法不仅能将可行解转化为完全活动调度,也可以将不可行解转化为完全活动调度,因此本文将对交叉后产生的后代运用PLFA算法,这样可以改将可行解转化为完全活动调度,改善解的调度时间,而将不可行解矫正为完全活动调度。
6 变异算子
变异算子决定了遗传算法的局部搜索能力,它是对染色体做一些扰动,以增加种群的多样性,避免过早收敛,突破局部最优。本文采用基于PLFA G-T算法的变异算子[11],该算法与PLFA G-T算法不同的是,PLFA G-T算法是随机产生完全活动调度解,而在该变异算子中PLFA G-T算法在为每台机器选择加工工序时,随机选择的概率是变异概率pm,1- pm的概率要依据变异母染色体进行选择。染色体变异产生的后代,都是可行解,都是完全活动调度,大大提高了变异后代的质量。具体算法如下:
算法5 基于PLFA G-T算法的变异算子
pm为基因变异概率:
(1) 随机选一条染色体作为变异染色体的母染色体Rold,初始化S为所有产品的第1道工序集合;
(2) while(还有工序未被加工){
o*为满足f(o*)=min{f(oijk), oijk∈S}的工序,对o*所在的机器m*进行如下操作:
a) 产生一个(0,1)随机数δ,如果δ<pm,从变异染色体 Rold的m机器加工工序中选一个最早出现的工序oijm,该工序且要在集合中{oijm∈S ,r(oijm)<f(o*)},否则,从集合中{oijm∈S ,r(oijm)<f(o*)}中随机确定一个操作oijm;
b) 在新染色体Rnew的第m*行添加i-j,在S集合中除去oijm,添加产品i的下道工序到S中;
}
(3) 调用PLFA算法作用Rnew
7 并行遗传算法
目前并行遗传算法模型主要分为四类:主从式模式、粗粒度模式、细粒度模式和混合模式。主从模式是遗传算法的直接并行化方案,不改变遗传算法的基本结构特点,它只有一个群体,个体之间可以任意匹配,每个个体都有机会和其他个体杂交而竞争,因而在种群上所作的选择和匹配是全局的。选择、交叉和变异等全局操作由主节点机(或主处理器)串行进行,而适应度的评价和计算由各从节点机(或主处理器)并行执行,主节点机(或主处理器)和从节点机(或主处理器)的通信表现在两个方面:一方面主节点机(或主处理器)把选择的群体部分个体发送给从节点(或主处理器);另一方面从节点机(或主处理器)把适应度的评价结果发送给主节点机(或主处理器)[12]。
根据实验,发现用遗传算法解决JSP时,主要的计算时间用在了适应度值的计算上,因此应用主从模型解决JSP将是一种非常有效的并行方法。
8 应用实例分析
本文的并行混合遗传算法选择遗传代数作为终止条件,采用Java编程实现,在双核1.6GHZ的平台运行,并行遗传算法使用双线程计算适应度值。采用Fisher和Thompson(1963年)提出的FT06、FT10和FT20,与Lawrence(1984年)提出的LA系列作为检验算法优劣的测试实例。表1对九个测试实例先用随机算法产生300个随机解,然后再用Active算法、PLFA算法对随机解进行改进得到活动调度解和完全活动调度解,最后求出这300个随机解、活动调度解和完全活动调度解的平均值。表中所列的就是这些平均值。从计算结果可看出,Active算法相对随机解改进约20%～30%, PLFA算法相对活动调度解改进约6%～7%。表2比较了并行混合遗传算法(PHGA)与串行混合遗传算法(HGA)的运行时间。表3比较了融入PLFA算法(PLFA-GA)与没有融入PLFA算法(Non PLFA-GA)的遗传算法的运行结果。Non PLFA-GA算法就是在初始种群产生,以及交叉,变异算子中不将调度转化为完全活动调度。表2和表3的运行参数如下,种群规模100,遗传代数为100代,交叉概率0.7,染色体变异概率0.3(将选择30%的染色体进变异),基因变异概率0.1(变异算法中pm的值),并把前10%的精英染色体拷贝到下一代。表3对每个测试案例进行了20次计算,得到了20次解的最优值Best,平均值Average,从表中可看出在一些较复杂的JSP问题的计算结果,如FT10,LA16,PLFA-GA比Non PLFA-GA上有了明显的改进。表2对每个测试案例进行了20次计算得到平均时间,处理器结点为2个,并行混合遗传算法的加速比约为1.3～1.4。
9 结 论
本文设计了基于按机器分段编码的完全活动调度算法PLFA,并将该算法融合于遗传算法,形成了并行混合遗传算法。通过PLFA G-T启发算法来产生全是完全活动调度的初始种群,良好的初始种群提高了算法的搜索性能。采用的LOX交叉算子可以很好地继承父染色体的特性,以及基于PLFA G-T算法的变异算子可以很好地增加种群的多样性,并且交叉算子与变异算子都结合了PLFA算法,产生的后代都是完全活动调度。最后,结合了主从模式的并行遗传算法模型。实验结果表明,Active算法与PLFA算法对随机解有显著的改进,在较复杂JSP的计算结果上PLFA-GA比Non PLFA-GA有明显的改进,并行混合遗传算法比非并行混合遗传算法,在计算时间上可以减少20%～30%,其加速比约为1.3～1.4。
摘要：结合先后表编码和完全活动调度概念,设计了基于先后表的完全活动调度算法PLFA,该算法能将可行解与不可行解转化为完全活动调度。并将PLFA算法与遗传算法结合,提出了一种并行混合遗传算法,初始种群由PLFA G-T算法产生,其产生的解都是完全活动调度,采用LOX的交叉算子与基于PLFA G-T算法的变异算子,并使用主从模型的并行遗传算法模型。最后JSP基准实例验证了算法的有效性。
关键词：车间调度,遗传算法,完全活动调度
参考文献
[1]Laarhoven P J MV,Aarts E HL,Lenstra J K.Job shop scheduling bysimulated annealing[J].Operations Research,1992,40:113125.
[2]Taillard E D.Parallel taboo search techniques for the job shop schedu-ling problem[J].ORSA Journal on Computing,1994,6(2):108117.
[3]Davis L.Job shop scheduling with genetic algorithms[C]//Proceedingsof the First International Conference on Genetic Algorithms and theirApplications.Morgan Kaufmann,1985:136140.
[4]Adams J,Balas E,Zawack D.The shifting bottleneck procedure for jobshop scheduling[J].Management Science,1988,34:391401.
[5]Cai L W,WUQH,Yong Z Z.Agenetic algorithm with local search forsolving job shop problems.Lecture Notes in Computer Science,2000:107116.
[6]Chaoyong Zhang,Yunqing Rao,Peigen Li.An effective hybrid geneticalgorithm for the job shop scheduling problem[J].The InternationalJournal of Advanced Manufacturing Technology,2008:965974.
[7]Chao Yong Zhang,PeiGen Lia,YunQing Raoa,et al.A very fast TS/SA algorithm for the job shop scheduling problem[J].Computers&Operations Research,2006:282294.
[8]Giffler J,Thompson G L.Algorithms for solving production schedulingproblems[J].Operations Research,1960.
[9]Cheng R,Gen M,Tsujimura Y.A tutorial survey of job-shop schedulingproblems using genetic algorithms,part I:representation[J].InternationalJournal of Computers and Industrial Engineering,1996,30:983997.
[10]Cheng R,Gen M,Tsujimura Y.Atutorial survey of job-shop schedulingproblems using genetic algorithms,part II:hybrid genetic search strate-gies[J].International Journal of Computers and Industrial Engineer-ing,1999,30:343364.
[11]Yamada T,Nakano R.A genetic algorithm applicable to large-scale job-shop problems[C]//R Manner,B Manderick.Proceedings of the SecondInternational Conference on Parallel Problem Solving,Nature ElsevierScience Publishers,North-Holland,1992:281290.
并行遗传算法 篇10
人类在享受互联互通和信息共享带来的便捷与效益的同时，网络技术发展过程中对安全性的忽视，导致网络环境中存在各式各样的安全隐患，严重威胁着网络运营及合法用户的信息安全。因此，寻找并弥补威胁网络关键资源的脆弱性是提高网络安全性的一种有效方法。文献[1]基于逻辑推理的方法，首先将最优弥补求解问题转化为布尔表达式；然后求解该布尔表达式的析取范式，从而得到所有的弥补措施；最后通过分析比较得到最优弥补建议。该方法在最坏情况下具有不可避免的指数时间复杂度，无法应用于网络规模较大的真实目标网络系统。文献[2]提出采用归纳有序二元决策图（ROBDD）的方法求解最优弥补。该方法可以有效地获取攻击图的最优弥补，但在该方法中，未对脆弱性进行度量标准的说明，因此在实际应用上具有一定的局限性。
由于求解最优弥补问题是NP完全性问题，对于NP完全性问题，采用启发式搜索方法可以更快地获得结果。并行遗传算法[3,4,5,6]具有以下优势：覆盖面大，利于全局择优；对问题的依赖性较小，求解的鲁棒性较好；具有并行计算的特点，可以用大规模的并行计算来提高计算速度；特别适用于复杂大系统问题的优化求解，但其存在收敛速度慢、局部搜索能力差等不足之处。并行遗传算法可以克服经典遗传算法的不足，提高遗传算法求解的速度和质量。基于此，本文将攻击图与并行遗传算法相结合，提出了一种基于并行遗传算法的网络最优弥补模型（Optimal Network Hardening Model Based on Paralle Genetic Algorithm,PGA-ONHM）。
1 最优弥补问题的转化
虽然并行遗传算法可以克服经典遗传算法的不足，特别适用于复杂大系统问题的优化求解[7,8,9]，但在具体的实现过程中，其适应度函数不能有约束条件，适应度函数的值需大于0，其最终得到的最优个体适应度函数值为最大值。求解最优弥补是有约束条件的，即需要满足约束条件g(x)=0，然后在满足此条件的弥补策略中寻找最优弥补。
为了能够将攻击图与并行遗传算法相结合，从而找到适用于求解大规模复杂目标网络系统最优弥补的模型，本文首先通过建立相应的数学模型，将最优弥补问题转化成一个带有惩罚的非约束优化问题，然后利用并行遗传算法得到其最优弥补的近似解。
令c1,c2,⋯,cn为目标网络系统的初始属性点，cost(ci)(i=0,1,2,⋯,n)为弥补初始属性节点ci需付出的成本代价，通过总结分析，并进行大量的模拟实验，建立的数学模型为：
通过此数学模型，可以将带有约束条件g(x)的最优弥补问题转化成能够应用并行遗传算法的非约束优化问题。r为惩罚因子，目的是设法对违背约束条件的个体给予惩罚，即当弥补策略不能保证目标网络系统正常、安全运行时，给予该策略一定的惩罚，使该策略所消耗的成本代价适应度放大，这样更易于选择最优弥补。
2 PGA-ONHM模型的设计与实现
2.1 并行遗传算法设计
目前，并行遗传算法的模型主要有三种：主从式、粗粒度、细粒度。其中，粗粒度模型首先将初始群体按照处理器数量分割成若干个子群体；然后将子群体分配给不同的处理器相互独立地并行执行，每经过一定的进化代，各子群体间会交换若干个体以引入其他子群体的优秀基因，防止未成熟收敛的发生。由于该模型通信开销少，而且适应性强、应用广，因此本文采用并行遗传算法的粗粒度模型。
(1）初始化总群体及子群体参数
总群体大小的选取应适中，过小则不易全局最优解，反之则运算量过大，收敛速度减慢。通常取编码长度的2倍。若总群体的大小为N，依据处理器数量将总群体均匀划分为U个子群体，则各子群体的大小为M=N U,M>1。
(2）子群体间的通信方式
由于从进程都是各自独立地运行遗传算法，每个进程到达符合迁移条件所需要的时间是不同的，因此，为了消除等待同步耽搁的时间，本文采用子群体间异步通信的方式。当主进程收到从进程提交的个体后，将染色体存放在缓冲区，并将缓冲区中上次收到的染色体发送给它。这样不仅降低了迁移算子的复杂度，同时省去了等待进程同步的时间，提高了运算速度。
(3）子群体的迁移策略
迁移是并行遗传算法引入的一个新算子，它是指进化过程中子群体间交换个体的过程，迁移策略主要控制的参数如下：
(1)迁移规模：每次迁移个体的数量。
(2)迁移率：个体迁移的时间间隔，即进化几代迁移一次。
(3)迁移策略：在确定迁移规模和迁移率后，就要确定哪些个体进行迁移。对于迁移个体的选择，本文采用子群体中的最优个体向外移民的策略。
(4）终止条件
程序终止的方式有两种：一是根据目标网络系统的规模，设定最大迭代次数，当迭代次数达到最大迭代次数时，则程序结束；二是在进化若干代后，若新一代中存在某个染色体的选择概率超过80%（此概率由用户设定），或者新一代中所有的染色体都相同，则程序结束。
2.2 子群体参数设计
(1）编码
编码的基本要求是为染色体的基因型（代码串）和表现型（参数值）建立对应关系，从而决定初始化种群。根据实际的应用需求，本文采用二进制代码进行编码，则对应关系就是二进制与十进制的转换关系。
(2）适应度函数
适应度函数是经典遗传算法中进行选择、交叉和变异操作的依据，该函数的选取是一个技巧性很高，但理论上的研究又很不充分的复杂问题。通过大量的模拟实验和分析，本文采用的适应度函数ti为：
其中r采用动态惩罚函数法。该方法在遗传算法的进化初期，为了保证算法能在全局范围内进行搜索，选取较小的惩罚因子，但在遗传算法的后期，为了增强局部搜索能力，将选取较大的惩罚因子。
(3）遗传算子
选择为经典遗传算法基本的遗传算子之一，常用的选择方法有期望值法、适应度概率法以及最佳个体保存法。文献[5]对以上三种方法的遗传算法性能进行对比，实验表明，采用期望值法的经典遗传算法，其离线性能与在线性能均高于采用另外两种方法。采用适应度概率法时可能会产生随机误差，这种误差在群体数较大时更易发生。因此，本文采用期望值法，且计算选择概率的公式为Pi=ti∑ti，其中：∑ti表示适应度值的总和；ti表示种群中第i个染色体的适应度值。
交叉为经典遗传算法基本的遗传算子之一，即将两个染色体的基因进行互换产生新的后代。与选择操作相比较，该操作能使基因排序变化更加灵活，实现真正意义上的人为重组，适用于大范围操作。在具体操作中，交叉分两个步骤：第一步是选择两两匹配的对象，第二步是决定交换点及交换规则。常用的交叉方式有单点交叉、双点交叉、按序交叉和位置交叉等，根据实际应用情况，本文采用按序交叉。
变异为经典遗传算法基本的遗传算子之一。由于本文采用二进制代码进行编码，即就是将基因值取反。
2.3 PGA-ONHM模型的实现
利用PGA-ONHM模型求解目标网络系统的最优弥补时，首先由主进程设定总群体大小、初始化子群体、设定子群体的参数（交叉、选择、变异等），把生成的子群体分配给从进程；然后子群体在从进程中进行独立进化，当达到预定代数时，向主进程发出迁移申请，主进程执行迁移策略，当从进程满足终止条件时，向主进程输出最优解；最后主进程从所有从进程输出的最优解中选择一个最优解。算法主进程流程图如图1所示。
各从进程独立地运行遗传算法进行进化，首先根据子群体参数设计对个体进行染色体二进制编码，并利用式（2）和式（3）计算每个个体的适应度函数，得到每个个体的选择概率，然后对父本进行选择、交叉、变异操作，产生下一代个体。当进化的代数满足迁移率时，向主程序返回最优解。从进程算法流程如图2所示。
2.4 算法复杂度分析
设目标网络系统中初始属性节点数量为C，迭代次数上限为D。
在主进程中，首先根据初始属性节点数量，从所有弥补策略中平均选取N个个体组成总群体，然后将总群体划分为U个子群体，一般来说N=2C，所以时间复杂度为：
在从进程中，子群体的大小为M=N U，各个子群体独立运行遗传算法，其时间复杂度主要从以下几部分分析：
(1）二进制编码。对每个个体进行二进制编码，时间复杂度为O(M)。
(2）适应度函数计算。对每个个体进行适应度函数计算，因为式（2）的时间复杂度为O(C)，所以适应度函数计算的时间复杂度为O(MC)。
(3）选择。首先计算每个个体的选择概率，然后将选择概率小的个体替换为选择概率大的个体，时间复杂度为O(M)。
(4）交叉。随机选择父本中的两个个体进行交叉操作，从而产生新的个体，时间复杂度为O(M2)。
(5）变异。根据变异概率，对个体执行变异操作，时间复杂度为O(M)。
(6）迁移。根据迁移率，向主进程提交当前子种群中选择概率大的个体，时间复杂度为O(M)。
当每一代进化未满足终止条件时，算法进行迭代。因此，遗传算法的时间复杂度为O(MC)⋅O(D)=O(2DC2/U)。
3 实验结果与分析
为了验证PGA-ONHM模型的可行性、有效性和可扩展性，本文从不同分析角度做了两组实验，并对实验结果进行了分析。实验环境如下：服务器PowerEDGE R710，操作系统RetHAT V5.4，内存32 GB,CPU 2.26 GHz。
3.1 算法性能验证实验
由算法性能分析可知，该算法性能与目标网络系统中初始属性节点数量C,迭代次数D,子群体U等参数有关。为了验证不同网络环境下这些参数对算法性能的影响，在得到最优解的前提下，分别设计了如下两组实验。
第一组实验验证初始属性节点数量不同时，单次迭代的平均计算时间如图3所示。由图3可知，单次迭代的平均计算时间随着初始属性节点数量C的增加呈多项式增加趋势。
第二组实验验证子群体数量（即处理器数量）对算法性能的影响。令初始属性节点数量为500，当子群体数量不同时，单次迭代的平均时间如图4所示。由图4可知，单次迭代的平均计算时间随着U的增加呈减小趋势。
由上述两组实验结果可知，在PGA-ONHM模型中，算法CPU消耗的时间随着初始属性节点数量C的增加呈多项式增加趋势，随着子群体数量U的增加呈减小趋势，实验结果与算法性能分析结果一致。
3.2 算法对比实验
(1）经典遗传算法和并行遗传算法对比实验，实验结果如表1所示。表1列出了在初始属性节点数量不同的情况下，求解最优弥补时两种算法的平均迭代次数和单次迭代的平均计算时间。
从实验结果可以看出：一方面，针对同一目标网络环境，无论是平均迭代次数还是单次迭代的平均计算时间，并行遗传算法比经典遗传算法都要优越，其主要原因是在并行遗传算法的具体实现过程中，首先将总群体分成若干子群体，然后将子群体分配到各自的处理机上，独立地进行遗传算法的进化操作，实现了从全局角度开发群体进化的并行性，从而提高了计算效率；另一方面，并行遗传算法具有良好的可扩展性，当初始属性节点数量达到2 000时，单次迭代的平均计算时间也不过7 ms。
(2）加速比实验。目前公认的评价并行遗传算法性能的指标是加速比，即并行遗传算法与经典遗传算法完成等量工作所耗时间的比例，它标志着一个并行遗传算法的好坏。本文在相同的硬件环境下，对同一目标网络环境通过改变处理器数量，进行了加速比实验，实验结果如表2所示。加速比和处理器数量的关系如图5所示。由图5可知，加速比与处理器几乎呈线性关系，因此，本文所提并行遗传算法可以得到较好的加速比，是行之有效的并行手段。
4 结论
PGA-ONHM模型通过建立数学模型将攻击图与并行遗传算法相结合，得到最优弥补的近似解。为了验证该模型的可行性、有效性和可扩展性，本文从不同的分析角度做了两组实验，实验结果表明：CPU消耗时间随着初始属性节点数量的增加呈多项式增加，随着子群体数量的增加呈减小趋势；无论是平均迭代次数还是单次迭代的平均计算时间，并行遗传算法比经典遗传算法都要优越；加速比与处理器呈线性关系；能够克服局部最优解的问题，可以适用于大规模复杂的网络系统。
参考文献
[1]JHA S,SHEYNER O,WING J M.Two formal analyses of attack graphs[C]//Proceedings of 15th IEEE Conference on Computer Security Foundations Workshop.[S.l.]:IEEE,2002:49-63.
[2]NOEL S,JAJODIA S,O′BERRY B,et al.Efficient minimumcost network hardening via exploit dependency graphs[C]//Proceedings of 19th Annual Conference on Computer Security Applications.[S.l.]:IEEE,2003:86-95.
[3]WANG L Y,NOEL S,JAJODIA S.Minimum-cost network hardening using attack graphs[J].Computer communications,2006,29(18):3812-3824.
[4]HOMER J.From attack graphs to automated configuration management:an iterative approach[R].Kansas:Kansas State University Technical Report,2008.
[5]SI J Q,ZHANG B,MAN D P,et al.Approach to making strategies for network security enhancement based on attack graphs[J].Journal on communications,2009,30(2):123-128.
[6]CHEN F,WANG L Y,SU J S.An efficient approach to minimum-cost network hardening using attack graphs[C]//Proceedings of 2008 the 4th International Conference on Information Assurance and Security.Naples:IEEE,2008:209-212.
[7]CHEN F,ZHANG Y,SU J S,et al.Two formal analyses of attack graphs[J].Journal of software,2010,21(4):838-848.
[8]CHEN F.A hierarchical network security risk evaluation approach based on multi-goal attack graph[D].Changsha:National University of Defense Technology,2008.