混合遗传算法及其应用

混合编码遗传算法在matlab中的应用1. 混合编码遗传算法的概念混合编码遗传算法是一种通过将离散和连续编码结合起来进行优化的方法。

它将问题的离散和连续变量分别进行编码，在进化过程中同时进行离散和连续空间的搜索，以充分利用不同编码方式的优势，提高搜索效率和优化结果的质量。

2. 混合编码遗传算法的原理混合编码遗传算法的原理主要包括两个方面：一是离散和连续编码的结合，二是利用遗传算法进行进化搜索。

在离散编码中，问题的解空间被划分为有限个离散的候选解，通过进化搜索找到最优解。

在连续编码中，问题的解空间是连续的，利用进化搜索算法对连续空间进行搜索。

混合编码遗传算法将这两种编码方式融合在一起，以期在搜索过程中充分利用不同编码方式的特点，提高搜索效率。

3. Matlab中的混合编码遗传算法在Matlab中，可以通过编写相应的代码来实现混合编码遗传算法。

Matlab提供了丰富的工具箱和函数，可以方便地实现混合编码遗传算法的各项操作，包括种裙初始化、选择、交叉、变异等。

Matlab还提供了丰富的绘图和分析工具，可以方便地对算法的运行结果进行可视化和分析。

4. 混合编码遗传算法的应用领域混合编码遗传算法在实际问题中有着广泛的应用。

比如在工程优化问题中，混合编码遗传算法可以有效地处理同时存在离散和连续变量的优化问题，如工程设计中的参数优化、控制系统中的参数调节等。

另外，在组合优化和调度问题中，混合编码遗传算法也有着良好的应用效果。

5. 混合编码遗传算法的优势和局限性混合编码遗传算法充分利用了离散和连续编码的优势，在处理复杂的优化问题时有着良好的性能表现。

但混合编码遗传算法的实现也较为复杂，需要充分考虑离散和连续编码的协调和平衡，算法的参数设置也较为繁琐。

6. 总结混合编码遗传算法在Matlab中的实现具有一定的挑战性，但通过充分利用Matlab提供的工具和函数，可以高效地实现混合编码遗传算法的各项操作。

混合编码遗传算法在实际问题中有着广泛的应用前景，可以有效地解决各种复杂的优化问题。

遗传算法理论及其应用发展摘要:首先介绍了遗传算法的基本工作原理和主要特点; 然后讨论了近年来从遗传算子、控制参数等方面对遗传算法的发展,并对遗传算法在国内外的研究进展和新的应用领域进行了讨论; 最后评述了遗传算法未来的研究方向和主要研究内容。

关键词:遗传算法; 遗传算子; 控制参数; 组合优化遗传算法[1] (Genetic Algorithms，简称GA )是由美国Michigan 大学的Holland教授于1975年首先提出的。

它源于达尔文的进化论、孟德尔的群体遗传学说和魏茨曼的物种选择学说; 其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。

从公开发表的论文看, 我国首先开始研究应用遗传算法的有赵改善和华中理工大学的师汉民等人。

遗传算法最早应用于一维地震波形反演中, 其特点是处理的对象是参数的编码集而不是问题参数本身, 搜索过程既不受优化函数联系性的约束, 也不要求优化函数可导, 具有较好的全局搜索能力; 算法的基本思想简单, 运行方式和实现步骤规范, 具有全局并行搜索、简单通用、鲁棒性强等优点, 但其局部搜索能力差, 容易出现早熟现象。

自1985年起, 国际遗传算法会议每两年召开一次, 在欧洲, 从1990年开始每隔一年也举办一次类似的会议。

1993年, 国际上第一本以遗传算法和进化计算为核心内容的学术期刊5 Evolutionary Com putation6 (进化计算) 在MIT 创刊; 1994年, 在美国奥兰多召开的IEEE World Congress on Computation Intelligence ( IEEE全球计算智能大会)上, 进化计算与模糊逻辑、神经网络一起统称为计算智能; 1997年, 5 IEEE Transaction son Evolutionary Computation6创刊。

这些刊物及时全面地报道了近年来遗传算法的最新研究成果。

遗传算法原理与应用实例遗传算法是一种模拟自然进化过程的优化算法，它通过模拟自然选择、交叉和变异等过程，不断优化解决问题的方案。

遗传算法具有全局搜索能力、并行计算能力和自适应性等优点，在许多领域得到了广泛应用。

遗传算法的原理遗传算法的基本原理是模拟自然进化过程，通过不断的选择、交叉和变异等操作，逐步优化解决问题的方案。

具体来说，遗传算法的过程包括以下几个步骤：1. 初始化种群：随机生成一组初始解作为种群。

2. 适应度评价：对每个个体进行适应度评价，即计算其解决问题的能力。

3. 选择操作：根据适应度大小，选择一部分个体作为下一代的父代。

4. 交叉操作：对父代进行交叉操作，生成新的子代。

5. 变异操作：对子代进行变异操作，引入新的基因。

6. 重复执行：重复执行2-5步，直到满足停止条件。

7. 输出结果：输出最优解。

遗传算法的应用实例遗传算法在许多领域都有广泛的应用，下面介绍几个典型的应用实例。

1. 机器学习遗传算法可以用于机器学习中的特征选择和参数优化等问题。

例如，在图像分类问题中，可以使用遗传算法选择最优的特征子集，从而提高分类准确率。

2. 优化问题遗传算法可以用于各种优化问题，如函数优化、组合优化和约束优化等。

例如，在工程设计中，可以使用遗传算法优化设计参数，从而降低成本或提高性能。

3. 人工智能遗传算法可以用于人工智能中的搜索和规划问题。

例如，在机器人路径规划中，可以使用遗传算法搜索最优路径，从而避免障碍物和优化路径长度。

4. 游戏设计遗传算法可以用于游戏设计中的智能体行为优化和关卡生成等问题。

例如，在游戏中，可以使用遗传算法优化智能体的行为策略，从而提高游戏体验。

总结遗传算法是一种强大的优化算法，具有全局搜索能力、并行计算能力和自适应性等优点，在许多领域得到了广泛应用。

通过模拟自然进化过程，遗传算法可以不断优化解决问题的方案，从而提高问题的解决能力。

混合智能计算方法及其应用混合智能计算方法及其应用智能计算是计算机科学领域中的一种重要研究方向，旨在模仿人类智能的思维能力，以解决复杂问题。

近年来，随着人工智能和机器学习的快速发展，混合智能计算方法也应运而生。

混合智能计算方法将多个智能计算技术相结合，形成一种更加高效和精确的解决方案。

本文将介绍几种常见的混合智能计算方法，并着重探讨其在实际应用中的优势和局限性。

一、遗传算法与模拟退火算法的混合方法遗传算法是一种模拟自然进化过程的计算方法，它使用选择、交叉和变异等操作来搜索全局最优解。

模拟退火算法则是一种利用物理的退火过程来寻找最优解的方法，通过温度控制和随机搜索来避免陷入局部最优。

将这两种方法相结合，可以充分利用遗传算法的种群搜索和模拟退火算法的全局搜索能力，提高求解问题的效率和准确度。

在实际应用中，遗传算法与模拟退火算法的混合方法被广泛应用于优化问题，如机器学习中的参数优化、图像处理中的图像重建、物流中的路径规划等。

通过将两种算法相互补充，可以克服各自单一算法的弱点，得到更好的优化结果。

然而，这种混合方法也存在一些局限性。

首先，遗传算法与模拟退火算法都需要大量的计算资源和时间，因此对于计算资源有限的问题可能不适用。

其次，混合方法需要调整两种算法的参数，参数的选择不当可能会导致性能下降或局部最优解的出现。

二、神经网络与模糊逻辑的混合方法神经网络是一种模仿生物神经系统行为的计算模型，具有学习和推理能力。

而模糊逻辑则是一种模糊推理与模糊控制的方法，能够处理不确定性与模糊性的问题。

将神经网络与模糊逻辑相结合，可以通过神经网络的学习能力获取输入输出的映射关系，并通过模糊逻辑的推理能力处理输入输出之间的不确定性。

在实际应用中，神经网络与模糊逻辑的混合方法被广泛应用于模式识别、控制系统、决策支持系统等领域。

通过神经网络的学习能力和模糊逻辑的模糊推理能力，可以处理具有不确定性和模糊性的问题，提高系统的鲁棒性和适应性。

遗传算法在混合动力汽车参数优化中的应用连志伟 颜 超 (武汉理工大学)摘要 混合动力汽车的动力部件参数和控制器参数对整车燃油经济性和排放有重要的影响。

文章分别以基于遗传算法的3种算法:权重系数法、并列选择法和共享函数法对一辆样车的参数进行离线仿真。

结果表明,应用这些方法获得的优化参数,在满足车辆特定性能的前提下能有效地减少油耗和降低排放。

对比分析优化结果,找出最适合H EV参数优化的算法,并给出参数优化的多组Pareto最优解。

主题词 混合动力 汽车 遗传算法0 引言混合动力汽车是由多个部件构成的复杂系统,其多动力系统给车辆动力分配带来了灵活性,可以在满足车辆性能的前提下减少油耗和降低排放。

但是,这些特性不仅与动力部件参数有关,还取决于控制策略及其相关参数;由于多个目标之间存在相互制约和高度非线性,几乎无法在所有目标上都获得最优解。

因此,要实现H EV 多目标参数优化设计必须对这些参数同时进行优化。

目前,求解这样复杂的有约束非线性多目标参数优化问题主要是根据工程经验设置参数初值,然后通过!试错法∀对这些参数进行调整。

常用的序列二次规划法(SQP)就是基于梯度的算法,它要求目标函数连续、可微,并满足Lipsch itz 条件,而对于H E V这样复杂的系统,这些条件很难满足。

遗传算法(GA)是一种具有很强全局寻优能力的仿真算法,它对于多峰、非连续、不可微或不满足Lipsch itz条件的多目标优化问题是行之有效的方法。

本文分别应用基于遗传算法的3种算法:权重系数方法、并列选择法和共享函数法,着重就并联混合动力汽车(P HEV)的动力部件参数和控制器参数进行优化,从而得出各种算法优化的最优解;并对这些结果进行对比分析,总结出在车辆参数优化中最适宜的算法;同时为P H EV参数优化提供多组方案。

1 PH EV参数优化问题1.1 优化参数的选取并联混合动力系统主要由发动机、电机、电池及传动系统等部件组成。

混合遗传算法求解航班延误恢复调度综合考虑航班延误各类损失，建立了合理的大规模航班延误恢复调度模型。

以此模型的目标函数为适应度函数，设计了基于遗传算法和模拟退火算法的混合遗传算法来快速有效的寻找优化恢复调度方案。

仿真结果表明，该算法与先到先服务的现行调度方法相比，可以有效的减少各种延误损失。

标签：航班延误；调度模型；混合遗传算法引言航班延误恢复调度（Recovery Scheduling of Flight Delays，RSFD）是指由于某些原因造成了大面积的航班延误，当恢复起飞时，需要重新调度延误航班。

航班恢复调度问题是一个多目标的优化问题，目前国际、国内在理论与实际应用上都没有很好的解决方法。

国内机场的普遍做法是靠航空管制员自身的经验和判断进行的，基于先到先服务原则（First Come First Serve，FCFS），调度效率较低。

因此本文考虑引入遗传算法，遗传算法（Genetic Algorithm，GA）在解决最优化问题上有较好的效果，但“早熟”（Prematurely）现象是目前遗传算法研究中的关键问题。

所以在这种情况下考虑引入模拟退火算法对遗传算法进行改进，利用该算法在搜索时可以以一定概率接受劣质解的策略避免遗传迭代过程提前陷入局部最优，从而提高算法的鲁棒性，将两者结合，有利于丰富优化过程中的搜索行为，增强全局和局部搜索能力和搜索效率。

1 航班延误经济损失航班延误经济损失通常包括显性损失和隐性损失两部分[1][2]，如图1：延误航班的运营成本2 混合遗传算法求解航班延误回复调度问题本文采用遗传算法与模拟退火算法相结合，设计混合遗传算法[3][4][5][6][7]如下：（1）选择编码，生成初始群体本文对于研究的航班延误恢复调度问题采用实数编码，如：12345678代表发生延误的航班序列，在经过优化后得到新的染色体18524376，这条新的染色体代表延误发生后给出的最新调度方案。

混合遗传算法和支持向量机的股票预测模型股票预测一直是金融市场中的一个重要研究方向，一个准确的股票预测模型可以帮助投资者做出更准确的投资决策，在投资市场中赚取更多的利润。

传统的股票预测方法使用了大量的统计学和数学理论，如时间序列分析、回归分析、滑动平均和指数平滑等。

但是这些方法在处理非线性和非平稳的股票数据时效果不理想。

为了解决这个问题，混合遗传算法和支持向量机模型被提出并被广泛使用。

混合遗传算法是一种自适应最优化算法，使用了遗传算法的“交叉”和“突变”操作来提高计算效率和优化结果。

混合遗传算法的主要优点是能够快速收敛到全局最优解，并具有较高的搜索精度和稳定性。

支持向量机是一种基于统计学习理论的非线性分类方法，被广泛应用于股票预测模型中。

支持向量机的优点是能够解决非线性问题和高维数据，具有较好的泛化性能和预测精度。

将混合遗传算法和支持向量机结合起来，可以得到一个更加全面和精确的股票预测模型。

具体来讲，该模型可以分为以下几个步骤：1. 数据预处理首先需要进行数据预处理，对股票数据进行清洗和规范化处理。

这个阶段包括数据清洗、数据处理和数据降维等。

2. 特征提取在数据预处理之后，需要提取有效的特征。

这个阶段可以使用主成分分析和核主成分分析等特征提取方法。

提取出来的特征可以作为支持向量机的输入数据。

3. 支持向量机模型的构建这个阶段需要使用支持向量机构建一个非线性分类模型，依据历史数据对股票价格进行预测。

在构建模型时需要选择核函数和优化算法，并根据不同的任务进行调节。

4. 混合遗传算法优化构建好了支持向量机模型之后，需要使用混合遗传算法来优化该模型。

混合遗传算法的操作包括个体选择、交叉操作、突变操作和适应度函数的计算等。

这个阶段的最终目的是最小化支持向量机模型的预测误差，并找到最优的模型参数。

5. 模型测试在得到最优的支持向量机模型参数之后，需要进行一系列的模型测试来评估预测效果。

这个阶段可以采用交叉验证和留一验证等常用的方法，并绘制ROC曲线和混淆矩阵等评估指标。

鲁东大学学报(自然科学版)　LudongUnive rsity Journa l(Natura l Sc ience Editi on)2007,23(4):318—322　 收稿日期6223;修回日期22 作者简介苏子林(—),男,副教授,硕士,主要从事计算机集成制造与管理信息系统的研究,()z y @63最小时间窗规则及其在混合遗传算法中的应用苏子林,陈北强,王保卫,苑金梁,张　帅(鲁东大学交通学院,山东烟台264025)摘要:为了研究与优先规则结合的混合遗传算法,提出了最小时间窗规则(ST W ),设计了采用最小时间窗规则生成初始种群的算法.发现调度结果中时间窗越少和越小,则完工时间就越小.探讨了优先规则应用于遗传算法中在生成初始种群时的完工时间、广义海明距离和完工时间的标准偏差等性能指标.对不同规模基准调度问题的测试结果表明,ST W 规则在以最小化完工时间为目标的调度中,与其他几种简单规则相比,能产生较好的调度效果.在混合遗传算法中,采用ST W 规则产生的初始种群整体适应度最高,多样性较好.关键词:作业车间调度问题;最小时间窗规则;优先规则;混合遗传算法中图分类号:TP18 文献标识码:A 文章编号:167328020(2007)0420318205 作业车间分配规则,又称优先规则,是实际应用中解决调度问题的简单常用的启发式方法,其主要优点是易于实现,运行速度快.作业车间调度问题的优先规则主要分为简单规则和由简单规则组合而成的复合规则[1].简单规则主要有最短加工时间规则(SPT )、最长加工时间规则(LPT )、剩余最多工作规则(MWR )、剩余最少工作规则(LWR )、剩余最多工序规则(MOR )、剩余最少工序规则(LOR )、最早到期时间规则(ED D )、先来先服务规则(FCFS)和随机选择规则(RND)[2].优先规则的调度与其他方法相比,速度快,但调度结果的质量不高.遗传算法(G A )利用生物进化机制,在一个较大的初始解空间中通过优胜劣汰的方法进行优化求解,具有全局优化、隐含并行、自组织、自适应和自学习性等特点,因此得到了人们的广泛关注.优先规则与遗传算法结合的混合遗传算法能进行优势互补,效果较好.本文在此基础上提出一种简单的优先规则———最小时间窗规则(ST W ),并探讨了它在混合遗传算法中的应用.经典的基准调度问题分析表明,在以最小化完工时间为目标的调度中,最小时间窗规则比其他规则具有更好的效果.1　最小时间窗规则 时间窗概念在调度问题中一般指一段连续的时间.这里的时间窗定义为:作业车间调度问题的调度结果中连续的空闲时间.在图1的甘特图(a)中,工件1的工序2(P 12)和工件2的工序2(P 22)之间产生了一个时间窗,在(b )中的相同位置却没有产生.图1　时间窗(T W )示意图 对比图1的两种调度结果容易发现,(b )产生的时间窗较少且较小,其完工时间也较小.在文献[3]的调度甘特图(图2)中没有产生时间窗,因此也是文献[3]调度问题的最优解.对于传统的车间调度模型,调度过程就是在工序和机床约束条件下,合理安排工序的加工开始时间,以满足完工时间最小的调度目标.对于工序路径确定的调度问题,所有机床的加工工序及其加工时间是确定的,因此调度过程就成为减少并减小时间窗的组合优化过程.以最小化完工时间为目标,调度:200101:20070910:1970E -m a il su ili n t 1.co m.　第4期苏子林,等:最小时间窗规则及其在混合遗传算法中的应用319　结果的时间窗越小且越少,则调度结果的质量就越高.据此提出最小时间窗规则,即在调度过程中优先选择产生时间窗最小的工序.图2　文献[3]实例最优解的甘特图2　优先规则在混合遗传算法中应用的性能指标 启发式方法与遗传算法的混合方式有多种,如利用启发式方法产生初始种群、进行染色体的解码或结合到选择、交叉和变异等遗传算法的循环中.作为最简单的启发式方法的优先规则常用来产生初始种群[3—4].初始种群个体的适应度越高,即算法的起点越高,算法运算结果的质量就越高.另外,遗传算法要求种群个体具有较多的模式,一次处理的模式数目越多,性能就越高[5].因此采用优先规则产生遗传算法初始种群时的性能指标定义如下. 1)完工时间(t)　在以最小化完工时间为目标的调度中,遗传算法的适应值函数定义为完工时间的单调递减函数,因此,完工时间越小,适应值就越高,个体的性能就越好. 2)广义海明距离(h)　种群个体具有的模式越多,多样性越高.个体多样性通过反映个体相似程度的广义海明距离定义.假设采用基于工序的字符串编码方法,定义工件编号为01,02,…,n,每个工件的工序编号为01,02,…,k,机床编号为01,02,…,m,则每个基因由n,k和m按顺序组成,如基因010101表示工件01的工序01在机床01上完成,那么扩展二进制格雷码中海明距离[6]的概念,定义个体间的广义海明距离为h(xi (g),xj(g))=∑l k=1|x ik(g)-x jk(g)|.(1)(1)式中,xi(g)表示第g代进化种群的第i个个体,x()表示x()中的第个基因,为编码长度其中运算符“”连接个体的两个等位基因,若两个操作数的工件编号、工序编号和机床编号三个属性值完全相同,则运算结果为0,否则为1.个体间的广义海明距离越大,其相似程度越低,种群多样性越高. 3)种群个体表达完工时间的标准偏差　标准偏差(s)反映了样本相对于其平均值的离散程度.个体表达完工时间不同,则个体必然不同,因此种群个体表达完工时间的标准偏差从另一个方面反映了种群的多样性.采用“P-1”方法来计算随机样本的标准偏差,定义如下s(x1(g),x2(g),…,x P(g))=(P×∑t i2-(∑t i)2)÷(P×(P-1)).(2) (2)式中,xi(g)表示第g代进化种群的第i个个体,P为种群规模,t i为第i个个体表达调度解的完工时间.3　采用最小时间窗规则生成初始种群 采用一个规则生成多个个体,必然在种群个体的生成过程中引入随机因素,即在基因排序的每一步,若符合优先规则的基因有多个,可随机选择一个.采用最小时间窗规则生成初始种群个体的算法如下. begin i=0;∥i为基因在个体中的序号 PSi初始化;Si初始化;Oi初始化;Mi初始化; d o while(i<P){∥P为种群规模 Boolean lb B est=false;int t mp Index=-1; fl oa tM i n V alue=MAXN UM; 产生随机数r;∥0≤r<PAR T NU M for(int j=r;j<P ART NU M;j++){ 根据j和S i生成基因Gene; if(Mi[Gene.machine]>=Oi[j]){ lb B est=true;break;} els e{∥不产生时间窗,退出循环 if(O i[j]-M i[Gene.machi ne]<M in Value){ M in Va lue=Oi[j]-Mi[Gene.machine]; t mp Index=j;} }∥搜索最小时间窗 }∥end for if(l bBe st==fals e){∥继续搜索最小时间窗 for(int j=0;j<r;j++){ 根据j和S i生成基因Gene; f(M[G]>=O[j]){ B=;;}ik gig k l.-iiene.mach inei lb est tru e b reak320　鲁东大学学报(自然科学版)第23卷 els e{∥不产生时间窗,退出循环 if(Oi [j]-Mi[Gene.machine]<M in Value){ M in Va lue=O i[j]-M i[Gene.machine]; t mp Inde x=j;} }∥继续搜索最小时间窗 }∥end for }∥end i f if(lb Be st==false)据t m p Index和Si生成Gene; 将Gene加入集合PSi; 更新集合Si ,Oi和Mi;i=i+1; }∥end do while end 以上算法中,PS i为包含i个已调度工序的基因集合,当i达到编码长度时完成个体生成.Si为在步骤i中可调度的工序集合,其长度为工件数量.S0所有元素的值为工件的第一道工序.Oi为在步骤i中所有工件的已调度工序的完工时间集合,其长度为工件数量.Oi元素的初始值都为零.Mi为在步骤i中所有机床完成已调度工序的时间集合,其长度为机床数量.M i元素的初始值都为零. 算法在从可调度工序集合Si中选择工序时,优先选择其加工机床的可用时间大于或等于其紧前工序完工时间的工序,这样排序后不会产生时间窗.图1(b)中工件1的第2道工序调度时符合这一条件.反之,则会产生时间窗,就需要通过循环选择产生最小时间窗的工序. 算法采用随机数作为可调度工序集合S i遍历起点的方法,使得多次运行时,选择不同工件的符合最小时间窗规则的第一个可调度工序.与完全遍历然后选择的方法相比,提高了运行效率.4　经典基准调度问题的测试与分析 利用优先规则的混合遗传算法采用C语言编程实现,算法运行微机的主频为PⅣ2.4G Hz,内存为256MB. 目前,实例ft10已经成为公认的检验调度算法优劣的基准实例,其最优解的完工时间为930[7].选择ST W与其他启发式规则作为比较,对实例ft10进行了测试(表1).初始种群的产生算法相同,限制算法运行时间不超过1s,产生不同个体的数量n不超过2000.从平均完工时间指标看,ST W最优,LW R次之,再次为MOR.从广义海明距离指标看,RND最优.可见随机选择产生个体多样性最高;ST W,LWR与LOR相近,优于其他规则.从完工时间的标准偏差看,LOR最优, RN D次之,再次为SPT,ST W.从产生不同个体的数量看,1s内ST W,RND和LOR产生的不同个体最多,MWR多数时间都耗费在产生重复个体上,仅产生了3个不同个体.综合评价显示,ST W最优,LW R和MOR次之.早期研究重视的SPT规则[8]没有取得理想效果.表1　不同规则的性能比较(ft10)规则t a vg t m in t ma x n h avg sST W128611011644200091.1369.93 L PT2902285129491712.7545.77 SPT2846256931012719.46146.30 LOR316626113700200091.57183.01 MOR141112881656175389.6467.10 L WR1289128912891048.040 MWR265726572657300.82 R ND183513072370200097.50170.85 注:t a vg,t m in,t m ax分别为平均、最小和最大完工时间;n为产生个体的数量;havg为平均广义海明距离;s为完工时间的标准偏差. 为了验证ST W规则对不同规模调度实例的运行效果,选择LWR和MOR作为比较进行了测试.测试实例的规模根据工件数量和机床数量的乘积,分别来自文献[9—10].由于测试实例的规模变化较大限制算法运行时间最长为1s,产生不同个体的数量不超过2000,测试结果见表2.由于算法完全随机产生不超过2000个个体,因此,据最优值的距离不同,其中la31的最优值为1784, ST W规则的运行结果比最优值大106;ft10的最优值为930,ST W规则的运行结果比最优值大71;ft6的最优值为55,ST W规则的运行结果比最优值大4.可见随着调度问题规模的增大,完工时间的最小值与最优值的距离逐渐增加;运行结果显示,ST W在完工时间和多样性方面明显优于其他规则. 由以上分析可见,ST W规则在以最小化完工时间为目标的调度中,与其他几种简单规则相比具有更大优势.在混合遗传算法中,采用ST W规则产生的初始种群整体适应度最高,多样性较好.　第4期苏子林,等:最小时间窗规则及其在混合遗传算法中的应用321　表2　ST W,L WR与MOR规则对不同规模经典实例的测试结果实例n,mS T Wt m in t avg h avgLWRt m in t a vg h avgMORt m in t avg h a vgft66,6596729.1697210.2596929.3 ft1010,101101164491.1128912898.01288144489.6 ft2020,51304153295.91955199912.01725202994.8 l a2620,1014211682195.61789179018.915991829189.8 l a2720,1014811735194.61918191816.616341962190.1 l a3130,1018902170296.22328232842.221452414290.5 l a3230,1019902275295.92601265442.622742598290.5 l a3615,1515741793209.817691981212.017331991211.6 l a3715,1517652095216.92087208715.418882227209.8 s wv0620,1524212831299.130********.427442988284.5 s wv0720,1522472643292.72912295438.424512768284.8 s wv1150,1045205089495.259285932115.856856061489.8 s wv1250,1047805192495.765466651125.657426119489.8 注:n为工件数量;m为机床数量;t m in,t avg分别为最小和平均完工时间;h a vg为平均海明距离.5　结束语 为了研究与优先规则组合的混合遗传算法,本文提出了一种简单优先规则———最小时间窗规则,探讨了优先规则在混合遗传算法中应用的性能指标,设计了采用优先规则的初始种群生成算法并且发现了调度结果的时间窗与完工时间之间的必然联系.对不同规模基准调度问题的测试结果显示,最小时间窗规则明显优于其他规则.参考文献:[1]　Wu D.An ex pert syste m s app r oach for the controland scheduling of flexible m anufacturing system s[D].Pennsylvania:Pennsylvania Sta te Unive rsity,1987.[2]　X UAN Guang2nan,CHE NG R un2we i.G enetic a lg o2rith m s and enginee ring de sign[M].Ne w York:JohnW iley&S ons,1996:100—140.[3]　张克宇,周浚哲,郝永平,等.基于遗传算法车间流控制中调度问题的研究[J].小型微型计算机系统,2004,4(25):743—746.[4]　Davis L.Job sho p scheduling with geneti c alg orit hm s[C]∥P r oceedings of the1st int e rnational confer2ence on genetic a l gorith m s and their applicati ons.P ittsburgh P A.Camegie M ell on University,1985:136—149.[5]　王正志,薄涛.进化计算[M].长沙:国防科技大学出版社,2000:96—97.[6]　吴养会,王乃信,王正中.一种新的改进遗传算法及其性能分析[J].西北农林科技大学学报(自然科学版),2004,9(32):124—126.[7]　WANG L i,Z HA NG Da2zhong.An effec tive hybridopti m izati on strategy for j ob2s hop scheduling p rob2lem s[J].Co mputers&Ope ra ti ons R esearch,2001,6(28):585—596.[8]　Montaze rM,Wa ssenhov e L V.Analysis of schedulingrule s for an F M S[J].Int e rnational Journal of Pro2duc ti on Re s ea rch,1990,28:785—802.[9]　Fisher H,Tho mps on GL.Probabilistic learning co m2binations of l oca l j ob2sho p s cheduling rules[M].Engl ewood C liffs,New Jersey:P renti ce Hall,1963:225—251.[10]　St orer R H,W u S D,Vaccari R.New search space sfor sequenc i ng instance sw ith applica tion t o job shopscheduling[J].Managem ent Sc ience,1992,38:1495—1509.　鲁东大学学报(自然科学版)第23卷　322Shor test T i m e W i n dow Rule and Its Appli ca ti on i n Hybr i d Genet i c Algor ith m S U　Zi2lin,CHEN　B ei2qiang,WA NG　Bao2wei,Y UAN　Jin2liang,ZHA N G　Shua i(Traffi c S chool,L udong University,Yan t ai264025,Ch i na)Ab stra ct:To study hybrid genetic a lgorithm com bined with p ri ority r ules,shortest ti m e window r ule(ST W)is put f or ward,initial population generati on algorithm with ST W is designed.It is found tha t the fe wer and shorter ti m e w indow s in scheduling results ar e,the less the pr ocessing ti me is.Several perf or m ance indexes of pri ority r ule s used in genetic algorithm’s initia l population generation are discussed,such as make span,gene r a lized Hamm ing distance,and m ake span’s standard deviation.The test result t o s olve dif ferent sca les benchm ark scheduling pr oble m shows that ST W can generate better scheduling r e sults than other si mple pri ority rules do, and the initia l popula tion gene r ated with ST W has better fitness and diversity in hybrid genetic algorith m. Key wor ds:job2shop scheduling p r oble m;shortest ti m e w indow rule;p riority rule;hybrid genetic algorithm(责任编辑　司丽琴)(上接第317页)Abstra c t I D:167328020(2007)04203142E AAn Appr oa ch to O p ti m i ze Softwa r e Pr oject R isk C on tr olL I U　Guang2Yan,HUA N G　Bao2Hai(Depart m ent of B usines s Adm i n istrati on,Shandong Electric Power C o ll ege,J i nan250002,Ch i na)Ab stra ct:A mode l f or op ti m izing soft ware risk contr ol ba sed on risk transf e r is given,and a discrete opti m iza2 tion a lgorithm of dyna m ic p r ogr a mm ing soft ware risk c ontr ol is pr oposed.An exa mple of using above m ethod to s olve a pr oble m is given t o show its eff ectiveness.Key wor ds:soft ware pr oject;risk contr ol;risk manage m ent;tr ans m issi on a lgorithm(责任编辑　司丽琴)。