混合遗传算法求解航班延误恢复调度

混合遗传算法求解航班延误恢复调度

摘要：综合考虑航班延误各类损失，建立了合理的大规模航班延误恢复调度模型。以此模型的目标函数为适应度函数，设计了基于遗传算法和模拟退火算法的混合遗传算法来快速有效的寻找优

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

关键词：航班延误；调度模型；混合遗传算法

引言

航班延误恢复调度（recovery scheduling of flight delays，rsfd）是指由于某些原因造成了大面积的航班延误，当恢复起飞时，需要重新调度延误航班。航班恢复调度问题是一个多目标的优化问题，目前国际、国内在理论与实际应用上都没有很好的解决方法。国内机场的普遍做法是靠航空管制员自身的经验和判断进行的，基于先到先服务原则（first come first serve，fcfs），调度效率较低。因此本文考虑引入遗传算法，遗传算法（genetic algorithm，ga）在解决最优化问题上有较好的效果，但“早熟”（prematurely）现象是目前遗传算法研究中的关键问题。所以在这种情况下考虑引入模拟退火算法对遗传算法进行改进，利用该算法在搜索时可以以一定概率接受劣质解的策略避免遗传迭代过程提前陷入局部最优，从而提高算法的鲁棒性，将两者结合，有利于丰富优化过程中的搜索行为，增强全局和局部搜索能力和搜索效率。

1 航班延误经济损失

MATLAB实验遗传算法和优化设计

实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）； 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题； 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。微带电极的结构参数如图所示，W 、t 分别是上电极的宽度和厚度，D 是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率1GHz ），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）： 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率， ρ为电阻率。可见电极的结构参数影响着电极损耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个：W 、D 、t ，它们组成决策向量[W, D ,t ] T ，待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述： ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2)

基于遗传算法的车间调度算法

得分：_______ 南京林业大学 研究生课程论文 2011～2012学年第一学期 课程号：73327 课程名称：Matlab语言 论文题目：基于遗传算法的车间调度算法 学科专业：交通运输工程 学号：8113102 姓名：闫盖 任课教师：王一雄 二○一一年十二月

基于遗传算法的车间调度算法 【摘要】车间调度问题具有建模复杂性、计算复杂性、动态多约束、多目标性等特点。近几年，各种演化计算方法逐渐被引入到生产调度中，特别是遗传算法的应用。本文主要介绍了企业车间调度问题的遗传算法实现，通过Matlab 实现对遗传算法的编程，其仿真调度结果验证了遗传算法用于求解车间调度问题的可行性和有效性。 【关键词】遗传算法 车间调度 Matlab Flow-Shop scheduling based on genetic algorithm Abstract ：The Flow-Shop scheduling problem has the property of modeling complexity, computational complexity, dynamic multi-constraint and multi-targeted. In recent years a variety of evolutionary computation methods, in particular, the application of genetic algorithms has been gradually introduced into the production scheduling problem. This paper puts forward a method to design Flow-Shop by using genetic algorithm. Program about genetic algorithm designs by using Matlab, Simulation results of our experiment show the feasibility and effectiveness of genetic algorithm for solving Flow-Shop scheduling. Key words ：Genetic algorithm Flow-Shop scheduling Matlab 引言 生产调度对企业的生产作业过程具有重要的作用。有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键。研究和解决好调度问题，能极大提高企业的生产效率，从而提高这些企业的竞争力。自从1954年Johnson 发表第一篇关于流水车间调度问题的文章以来，流水车间调度问题引起了许多学者的关注，提出了许多解决的方法。其中，以遗传算法、模拟退火、禁忌搜索以及人工神经网络为代表的智能化优化技术迅速发展，用来解决流水车间调度问题，受到人们的普遍关注。遗传算法以其优良的计算性能和显著的应用效果而特别引人注目，很多启发式混合方法都是在此基础上发展起来的。本文采用遗传算法进行求解。 1车间调度问题描述 车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源，提高企业经济效益的目的。车间调度问题从数学上可以描述为有n 个代加工的零件在m 台机器上加工，车间调度的数学模型如下： （1） 机器集},,{21m m m m M ，?=，j m 表示第j 台机器，j=1,2,…,m 。 （2） 零件集},,{21n p p p P ，?=，i p 表示第i 个零件，i=1,2,…,n 。 （3） 工序序列集},,{21n op op op OP ，?=，},,{21ik i i i op op op op ，?=表示零件i p 加工工序序列。 （4） 可选机器集},,{21ik i i op op op OPM ，?=,},,{21ijk ij ij ij op op op op ，?=表示零件 i p 加工工序j 可以选择的加工机器。

遗传算法与优化问题(重要,有代码)

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： 序号遗传学概念遗传算法概念数学概念 1 个体要处理的基本对象、结构也就是可行解 2 群体个体的集合被选定的一组可行解 3 染色体个体的表现形式可行解的编码 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体， 淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解 9 交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组新解 10 交叉概率染色体对应基因段交换的概 率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.90 11 变异染色体水平上基因变化编码的某些元素被改变

流水线车间生产调度的遗传算法MATLAB源代码

流水线车间生产调度的遗传算法MATLAB源代码 n个任务在流水线上进行m个阶段的加工，每一阶段至少有一台机器且至少有一个阶段存在多台机器，并且同一阶段上各机器的处理性能相同，在每一阶段各任务均要完成一道工序，各任务的每道工序可以在相应阶段上的任意一台机器上加工，已知任务各道工序的处理时间，要求确定所有任务的排序以及每一阶段上机器的分配情况，使得调度指标(一般求Makespan)最小。 function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P) %-------------------------------------------------------------------------- % % 流水线型车间作业调度遗传算法 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→输入参数列表 % M 遗传进化迭代次数 % N 种群规模(取偶数) % Pm 变异概率 % T m×n的矩阵，存储m个工件n个工序的加工时间 % P 1×n的向量，n个工序中，每一个工序所具有的机床数目 % 输出参数列表 % Zp 最优的Makespan值 % Y1p 最优方案中，各工件各工序的开始时刻，可根据它绘出甘特图 % Y2p 最优方案中，各工件各工序的结束时刻，可根据它绘出甘特图 % Y3p 最优方案中，各工件各工序使用的机器编号 % Xp 最优决策变量的值，决策变量是一个实数编码的m×n矩阵 % LC1 收敛曲线1，各代最优个体适应值的记录 % LC2 收敛曲线2，各代群体平均适应值的记录 % 最后，程序还将绘出三副图片：两条收敛曲线图和甘特图（各工件的调度时序图） %第一步：变量初始化 [m,n]=size(T);%m是总工件数，n是总工序数 Xp=zeros(m,n);%最优决策变量 LC1=zeros(1,M);%收敛曲线1 LC2=zeros(1,N);%收敛曲线2 %第二步：随机产生初始种群 farm=cell(1,N);%采用细胞结构存储种群 for k=1:N X=zeros(m,n); for j=1:n for i=1:m X(i,j)=1+(P(j)-eps)*rand; end end

遗传算法和蚁群算法的比较

全局优化报告 ——遗传算法和蚁群算法的比较 某：X玄玄 学号：3112054023 班级：硕2041

1遗传算法 1.1遗传算法的发展历史 遗传算法是一种模拟自然选择和遗传机制的寻优方法。20世纪60年代初期，Holland教授开始认识到生物的自然遗传现象与人工自适应系统行为的相似性。他认为不仅要研究自适应系统自身，也要研究与之相关的环境。因此，他提出在研究和设计人工自适应系统时，可以借鉴生物自然遗传的基本原理，模仿生物自然遗传的基本方法。1967年，他的学生Bagley在博士论文中首次提出了“遗传算法”一词。到70年代初，Holland教授提出了“模式定理”，一般认为是遗传算法的基本定理，从而奠定了遗传算法的基本理论。1975年，Holland出版了著名的《自然系统和人工系统的自适应性》，这是第一本系统论述遗传算法的专著。因此，也有人把1975年作为遗传算法的诞生年。 1985年，在美国召开了第一届两年一次的遗传算法国际会议，并且成立了国际遗传算法协会。1989年，Holland的学生Goldberg出版了《搜索、优化和机器学习中的遗传算法》，总结了遗传算法研究的主要成果，对遗传算法作了全面而系统的论述。一般认为，这个时期的遗传算法从古典时期发展了现代阶段，这本书则奠定了现代遗传算法的基础。 遗传算法是建立在达尔文的生物进化论和孟德尔的遗传学说基

础上的算法。在进化论中，每一个物种在不断发展的过程中都是越来越适应环境，物种每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来；否则，就将被淘汰。在遗传学中认为，遗传是作为一种指令遗传码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有特殊的位置并控制某个特殊的性质。每个基因产生的个体对环境有一定的适应性。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。在求解过程中，遗传算法从一个初始变量群体开始，一代一代地寻找问题的最优解，直到满足收敛判据或预先假定的迭代次数为止。 遗传算法的应用研究比理论研究更为丰富，已渗透到许多学科，并且几乎在所有的科学和工程问题中都具有应用前景。一些典型的应用领域如下： （1）复杂的非线性最优化问题。对具体多个局部极值的非线性最优化问题，传统的优化方法一般难于找到全局最优解；而遗传算法可以克服这一缺点，找到全局最优解。 （2）复杂的组合优化或整数规划问题。大多数组合优化或整数规划问题属于NP难问题，很难找到有效的求解方法；而遗传算法即特别适合解决这一类问题，能够在可以接受的计算时间内求得满意的近似最优解，如著名的旅行商问题、装箱问题等都可以用遗传算法得到满意的解。

种函数优化问题的混合遗传算法

一种函数优化问题的混合遗传算法 彭伟卢锡城 摘要将传统的局部搜索算法和遗传算法相结合,可以较好地解决遗传算法在达到全局最优解前收敛慢的问题.文章给出一种结合可变多面体法和正交遗传算法的混合算法.实验表明,它通过对问题的解空间交替进行全局和局部搜索,能更有效地求解函数优化问题. 关键词遗传算法,可变多面体法,正交交叉,函数优化. 中图法分类号TP A Hybrid Genetic Algorithm for Function Optimization PENG Wei LU Xi-cheng (Department of Computer Changsha Institute of Technology Changsha 410073) Abstract To overcome the problem of slow convergence before the genetic algorithms (GAs) reach the global optima, it is an effective way to combine the conventional local search algorithms with GAs. A new hybrid algorithm that incorporates the flexible polyhedron method into the orthogonal genetic algorithm (OGA) is presented in this paper. The experiments showed that it can achieve better performance by performing global search and local search alternately. The new algorithm can be applied to solve the function optimization problems efficiently. Key words Genetic algorithm, flexible polyhedron, orthogonal crossover, function optimization. 遗传算法（genetic algorithms）通过模拟生物进化的途径来在问题的解域中定向搜索最优解,在组合优化、机器学习、自适应控制、多目标决策等领域中有许多应用.对于传统方法较难求解的一些NP问题,遗传算法往往能得到更好的结果.但对传统方法已能较好解决的问题（如一般的非线性优化问题）,它并不显示较强的优势.原因在于,遗传算法对问题特定的知识（如梯度、Hessian阵、某些定理等）利用较少.它主要采用群体搜索技术,通过对解的不断组合、随机改变以及对候选解的评估和选择来完成求解过程.在达到全局最优解前,它尚存在收敛慢的问题.设计遗传算法时往往需要在其通用性与有效性之间折衷.设计针对问题的特定遗传算子,可以更有效地求解问题,但缺乏通用性.另一种途径是将遗传算法与问题领域中一些传统的寻优方法（如爬山法、模拟退火法、牛顿法等）结合起来,可在保持算法一定的通用性时提高算法的效率.这类混合算法的基本框架如图1所示.

云计算环境下基于改进遗传算法的任务调度算法

收稿日期:2010-07-15;修回日期:2010-09-06。 基金项目:四川省科技支撑计划项目(06K J T 013;2009GZ0153)。 作者简介:李建锋(1987-),男,河南项城人,硕士研究生,主要研究方向:网格计算、云计算; 彭舰(1970-),男,四川成都人,教授,博士, 主要研究方向:分布式系统、移动计算。 文章编号:1001-9081(2011)01-0184-03 do:i 10.3724/SP .J .1087.2011.00184 云计算环境下基于改进遗传算法的任务调度算法 李建锋,彭 舰 (四川大学计算机学院,成都610065) (ji anpeng @sc https://www.wendangku.net/doc/3217229259.html, .cn ) 摘 要:在云计算中面对的用户群是庞大的,要处理的任务量与数据量也是十分巨大的。如何对任务进行高效 的调度成为云计算中所要解决的重要问题。针对云计算的编程模型框架,提出了一种具有双适应度的遗传算法(DFGA ),通过此算法不但能找到总任务完成时间较短的调度结果,而且此调度结果的任务平均完成时间也较短。通过仿真实验将此算法与自适应遗传算法(AGA )进行比较,实验结果表明,此算法优于自适应遗传算法,是一种云计算环境下有效的任务调度算法。 关键词:云计算;遗传算法;双适应度;任务调度 中图分类号:T P393 文献标志码:A Task scheduli ng al gorith m based on improved genetic algorith m i n cloud co mputi ng environ m ent LI Jian feng ,PE NG Jian (C olle ge of Co mpu te r S cie nce ,S ichuan Un i versit y,Chengd u S ic huan 610065,Ch i na ) Abstract :T he number of users i s huge in c l oud computi ng ,and t he nu mber o f tasks and t he a m ount of da ta are also huge.H ow to schedule tasks efficiently i s an i m portant i ssue to be reso l ved i n c l oud computi ng env iron m ent .A Doub l e F itness G enetic A lgor i th m (DFGA )w as brought up for t he prog ramm i ng fram e w ork o f c l oud computi ng.T hrough th i s a l gor ith m,the be tter task scheduli ng no t only sho rtens to tal task comp l e ti on ti m e and a lso has shorter average co m pletion ti m e .T he re i s a contrast bet ween DFGA and Adapti ve G ene tic A l gor it hm (AGA )t hrough si m u lati on exper i m ent ,and the resu lt i s :t he DFGA i s be tter ,it is an effi c i ent task schedu li ng a l go rith m i n c l oud co m puti ng env iron m ent . K ey words :cloud co m puti ng ;G ene ti c A l go rith m (GA );doub le fitness ;task schedu li ng 0 引言 近几年云计算[1-2]成为了人们讨论的热点。目前IB M 、G oog l e 、Am azon 、M icroso ft 等纷纷涉足云计算,提供了众多基于云计算的服务,如Gm a il 、Goog le E arth 、G oog l e Ana l y ti cs 、G oog l e 搜索、G oog l e 文档[3];Am azon 的弹性云计算(EC2)服务和存储服务(S3);M i crosoft 的W i ndow s L ive W eb 应用套件及H ot m ail 等[4]。 云计算是并行计算、网格计算[5-6]的发展,是分布式计算的一种,其最基本的思想是透过网络将庞大的计算处理程序自动分拆成无数个较小的子程序,再交由多部服务器所组成的庞大系统,经搜寻、计算分析之后将处理结果回传给用户,提供这些资源的网络被称为 云 。云计算所提供的服务面向的用户群是庞大的,因此 云 中的任务数量是巨大的,系统每时每刻都要处理海量的任务,所以任务调度[7]是云计算中的重点与难点。本文对如何充分利用 云 中的资源使其中的任务进行高效合理的调度进行了研究,提出了一种基于双适应度遗传算法(D oub l e F itness G enetic A l go rith m,DFGA )的任务调度算法,并通过了仿真实验,验证了其良好的性能。 1 云计算中的编程模型 目前的云计算环境中大部分采用G oog le 提出的M ap /R educe 的编程模式[8],大部分信息技术厂商提出的 云 计划 中采用的编程模型,都是采用基于M ap /R educe 的思想开发的编程工具,它特别适用于产生和处理大规模的数据集。其执行过程如图1所示。 图1 M ap /R educe 的具体执行过程 从图1可以看出,M ap /R educe 有6个过程,可分为两个主要阶段。 M ap 阶段 把一个较大的任务通过M ap/R educe 函数分割为M 个较小的子任务,然后配给多个w orker(被分配为执行M ap 操作的wo rker)并行执行,输出处理后的中间文件; 第31卷第1期 2011年1月 计算机应用 Journal o f Computer A pp licati ons V o.l 31N o .1 Jan .2011

混合遗传算法及其应用

混合遗传算法及其应用 辛海涛 （哈尔滨商业大学计算机与信息工程学院，黑龙江哈尔滨150028） 摘 要：给出一种结合梯度法和正交遗传算法的混合算法。实验表明，它通过对问题的解空间交替进行全局和局部 搜索，能更有效地求解函数优化问题。关键词：遗传算法；正交交叉；函数优化中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2010）05－0059－02 0引言 遗传算法是近年来发展起来的一种新型优化算法，是基于 自然选择和遗传学机理的迭代自适应概率性搜索方法。它通过模拟生物进化的途径问题的解域中定向搜索最优解，在组合优化、机器学习、自适应控制、多目标决策等领域中有许多应用。 遗传算法的实现涉及5个主要因素：参数编码、初始群体的设定、评估函数（即适应函数）的设计、遗传操作的设计和算法控制参数的设定。对于传统方法较难求解的一些NP 问题，遗传算法往往能得到更好的结果。但对传统方法已能较好解决的问题（如一般的非线性优化问题），它并没有较强的优势。遗传算法主要采用群体搜索技术，通过对解的不断组合、随机改变以及对候选解的评估和选择来完成求解过程。在达到全局最优解前，它尚存在收敛慢的问题。设计遗传算法时往往需要在其通用性与有效性之间折衷。设计针对问题的特定遗传算子，可以更有效地求解问题，但缺乏通用性。另一种途径是将遗传算法与问题领域中一些传统的寻优方法（如爬山法、模拟退火法、牛顿法等）结合起来，可在保持算法一定的通用性时提高算法的效率。 本文考虑一类非线性函数优化问题，即： minf （x ）x ∈D 其中f （x ）是n 元连续函数，D 是R n 的有界子集。本文探讨将梯度法与遗传算法相结合的算法，梯度法对初始解的构成具有较强的依赖性，算法执行过程中难于发现新的可能存在最优解的区域。通过将它与遗传算法相结合，一方面可以利用其局部搜索能力，另一方面可通过遗传算法来不断“发现”新的更有希望的搜索区域，并动态调整可变多面体法的搜索方向，从而使算法具有更好的灵活性，也使算法更易于并行化。实验表明，对于求解上述非线性优化问题，混合遗传算法具有比传统遗传 算法和梯度法都好的性能。 1 混合遗传算法 1.1 编码方式 编码的实质是在问题的解空间与算法的搜索空间之间建 立一个映射。传统遗传算法一般采用一种将实数空间离散化的二进制编码方式。这种方式存在编码长度影响求解精度、操作费时、不直观等缺点，因而提出了实数的直接编码方式并表明可以获得更好的性能。在实数编码方式下，每个个体用一个n 维的实向量来表示，这种方式具有直观、易操作的优点，且可以针对它设计非传统的交叉算子。本文采用此编码方式。 1.2交叉和选择操作 正交遗传算法在非线性优化问题及其他组合优化问题中 已显示出其有效性，我们的算法采用了正交交叉算子。由两个父本交叉操作产生一组个体，从新个体和两个父本中选择最优的进入下一代群体。由于采用局部选择而不是全局选择，在一定程度上保持了群体的多样性。 1.3变异操作 在实数编码方式下，变异操作对个体X 的每个分量X ［i ］ 作用一个随机偏差量，即： X′［i ］＝X ［i ］＋δ，i＝1，2，…，n 在进化规划和进化策略中，广泛采用了高斯变异算子，用正态分布的随机变量来作为变异操作中的偏差量。 1.4局部搜索 在本文中，我们采用梯度法进行局部搜索，梯度法步骤如下： （1）选定ε＞0为终止限。选定初始点X （0），令k ＝0。（2）计算△f （X （k ））。如果‖△f （X （k ））‖＜ε，迭代停止，取近试 最优解X *＝X （k ），否则，令S （k ）＝－△f （X （k ）），从X （k ）出发沿S （k ）作一 软件导刊 Software Guide 第9卷%第5期 2010年5月Vol.9No.5May.2010 作者简介：辛海涛（1970－），男，黑龙江鹤岗人，硕士，哈尔滨商业大学计算机与信息工程学院副教授，研究方向为算法分析。

遗传算法在生产调度方面的应用

遗传算法在生产调度方面的应用 合肥工业大学吴磊（20080313）陈超峰（20080321）方振中（20080322）周超（20080332）王伦良（20080340） 摘要：生产调度问题是企业生产甚至国际合作的关键问题，但生产调度问题难以精确求解。遗传算法可以很好的解决这一问题，在生产调度、生产规划、任务分配等方面发挥着极其重要的作用。 关键词：生产调度生产调度方式遗传算法 1.遗传算法 遗传算法是模拟生物在自然环境中的进化过程而形成的一种自适应全局优化概率的搜索算法。它使用群体搜索技术，通过对当前群体施加选择交叉变异等一系列遗传操作，从而产生新一代的群体，并按优胜劣汰的机制逐步使群体进化到包含或接近最优解的状态。 1.1遗传算法的基本运算过程 选择：从当前种群中选出优良的个体作为父代个体。 对各染色体v k计算适合度eval（v k）；k=1,2,3，…，m 计算选择概率： 对各染色体v k ， P=eval（v k）/∑eval(v k) 交叉：对群体中的个体进行两两随即配对 对每一对相互配对的个体，随机设置某一基因之后的位置为交叉点 对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的染色体，从而产生出两个新的个体。 变异：遗传算法中的所谓变异运算，是将个体染色体编码串中的某些位置上的基因值用其他等位基因替换，从而形成一个新的个体。 2.生产调度 生产调度就是组织执行生产进度计划的工作，是实现生产进度计划的主要手段。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。 在生产调度的事业上，生产调度有管理和工作之分，也就是生产调度管理和生产调度工作，是两个互为联系有有区别的概念。生产调度的作用是职能作用，生产调度工作的作用是职责作用。具体来说，生产调度管理，是指生产调度的计划、实施、检查、总结的期量循环活动的管理，是指生产调度的计划理论、方法、法规等方面的管理。生产调度工作，则有狭义和广义之分，从狭义上说，生产调度工作是指生产调度的业务工作，也就是生产经营管理方面的技术性工作，其内容是生产调度对生产经营动态的了解、掌握、预防、处理，对关键岗位如主机岗位实行控制，对跨车间和跨部门的电、水、风，产、供、销、运等进行协调平衡，对产量、质量、安全、效益等重点环节实行衔接一致的保证；从广义上说，生产调度部门的行政管理方面的具体事项，如业务上，科技上的研讨活动，在岗人员道德和专业知识的教育，业务能量的具体发挥等，可见广义的生产调度工作，其具体活动事项要比生产调度管理大得多，将生产调度管理等同生产调度工作是不准确的。可以概括的说，生产调度工作是生产调度管理的具体表现，生产调度工作的完成是生产调度管理在实际上完成的具体表现。生产调度的重要意义在于：现代工业企业，生产环节多，协作关系复杂，生产连续性强，情

基于混合遗传算法求解非线性方程组

万方数据

万方数据

万方数据

基于混合遗传算法求解非线性方程组 作者：田巧玉， 古钟璧， 周新志， TIAN Qiao-yu， GU Zhong-bi， ZHOU Xin-zhi 作者单位：四川大学,电子信息学院,四川,成都,610064 刊名： 计算机技术与发展 英文刊名：COMPUTER TECHNOLOGY AND DEVELOPMENT 年，卷(期)：2007，17(3) 被引用次数：6次 参考文献(6条) 1.赵明旺基于牛顿法和遗传算法求解非线性方程组的混合计算智能方法 1997(11) 2.周明.孙树冻遗传算法原理及应用 1999 3.雷英杰.张善文.李续武.周创明MATLAB遗传算法工具箱及应用 2005 4.曾毅浮点遗传算法在非线性方程组求解中的应用[期刊论文]-华东交通大学学报 2005(01) 5.胡小兵.吴树范.江驹一种基于遗传算法的求解代数方程组数值的新方法[期刊论文]-控制理论与应用 2002(04) 6.罗亚中.袁端才.唐国全求解非线性方程组的混合遗传算法[期刊论文]-计算力学学报 2005(01) 相似文献(10条) 1.期刊论文郭海燕.金鑫.胡小兵.Guo Haiyan.Jin Xin.Hu Xiaobing基于微粒群优化的非线性方程组求解研究-计算机工程与应用2006,42(15) 在科学技术和工程应用中经常遇到求解非线性方程组的问题.提出了一种求解非线性方程组的通用数值方法.将非线性方程组的求解问题转化为函数优化问题,通过微粒群优化对其进行求解,最终得到非线性方程组较高精度的解.一系列测试实例显示了该算法在求解非线性方程组时具有简单性、高效性和普适性. 2.学位论文向占宏一类基于区域分裂的演化算法及应用2006 区域分裂法的基本思想是将定义在复杂的大区域上的问题分解成若干小区域上的问题分别求解，然后通过迭代得到整个区域上的解，该方法能分解大型问题为小型问题、复杂区域问题为简单区域问题。 演化算法在求解函数优化问题很有效。长期以来演化算法在应用中主要存在两大缺陷：一是对某些问题演化算法求解速度太慢；二是演化算法容易产生早熟现象，而且对于单峰函数优化问题，目前的演化算法还没有鲁棒性。有研究表明用杂交算子求解实数优化问题时可以得到较好的结果。目前对实数函数优化问题的研究中，很多人致力于研究如何找到一个有效的杂交算子。 本文介绍了演化算法的基本结构和研究现状，给出了演化算法的基本结构，介绍了各种杂交算子，分析了他们的优点和缺陷，详细分析了GT算子及带子空间的GT算法的性能。将GT多父体杂交算子进行改造，应用于求解非线性方程组，提出了求解非线性方程组的GT算法。 分析了常微分方程边值问题及其数值解法、有限元方法和区域分裂法的基本原理，给出了利用区域分裂法、有限元方法在小区域上离散一维常微分方程边值问题具体过程，给出了基于区域分裂和有限元离散的求解常微分方程边值问题的演化算法。 给出了郭涛算法求解非线性方程组的算例以及利用区域分裂法、有限元法和郭涛算法求解常微分方程边值问题的算例并对结果进行了分析。本文改进了求解非线性方程组的GT算法。该算法可以在演化过程中自适应调整搜索空间和种群从而加快收敛，并以它为基础提出了一类新的求解常微分方程边值问题的数值解的演化算法。 3.期刊论文贺春华.张湘伟.吕文阁.HE Chun-hua.ZHANG Xiang-wei.LV Wen-ge竞选优化算法求解非线性方程组的应用研究-计算机工程与应用2010,46(14) 针对非线性方程组的求解在工程上具有广泛的实际意义,经典的数值求解方法存在其收敛性依赖于初值而实际计算中初值难确定的问题,将复杂非线性方程组的求解问题转化为函数优化问题,引入竞选优化算法进行求解.同时竞选优化算法求解时无需关心方程组的具体形式,可方便求解几何约束问题.通过对典型非线性测试方程组和几何约束问题实例的求解,结果表明了竞选优化算法具有较高的精确性和收敛性,是应用于非线性方程组求解的一种可行和有效的算法. 4.学位论文刘丽芳粒子群算法的改进及应用2008 粒子群优化算法是在对鸟群捕食行为模拟的基础上提出的一种群集智能算法，是进化计算领域中一个新的分支。它的主要特点是原理简单、参数少、收敛速度较快、易于实现。因此，该算法一提出就吸引了的广泛关注，逐渐成为一个新的研究热点。目前，粒子群优化算法应用于神经网络的训练、函数优化、多目标优化等领域并取得了较好的效果，有着广阔的应用前景。 论文的主要工作有: (1)对粒子群优化算法的理论基础和研究现状作了简要的介绍，分析了粒子群优化算法的原理及算法流程，对算法参数的选择做了详细的研究，并进行了相应的仿真实验。 (2)分析了粒子群优化算法存在的问题，主要包括:参数设置问题、算法“早熟”问题和算法稳定性问题。在粒子群优化算法中，参数的设置会影响算法优化的结果，因此，如何选择合适的参数达到最好的优化结果是算法需要解决的问题。“早熟”问题是优化算法普遍存在的问题。如果粒子在搜索最优值时过早收敛，就会使算法的寻优停滞在局部最小值，无法找到全局最优解。由于算法中粒子的初始位置、速度和一些参数是被随机初始化的，因此每一次算法运行的结果并不相同，有时结果的差别很大，这样就导致了算法优化结果不稳定。 (3)针对粒子群优化算法存在的问题，论文提出了一种新的改进算法——基于粒子进化的多粒子群优化算法。该算法采用局部版的粒子群优化方法，从“粒子进化”和“多种群”两个方面对标准粒子群算法进行改进。多个粒子群彼此独立地搜索解空间，保持了粒子种群的多样性，从而增强了全局搜索能力；而适当的“粒子进化”可以使陷入局部最优的粒子迅速跳出，有效的避免了算法“早熟”，提高了算法的稳定性。通过对测试函数进行仿真实验，验证了该算法的有效性。 (4)将基于粒子进化的多粒子群优化算法应用于线性瞬时混合的盲源分离。将该算法的仿真实验结果与标准粒子群优化算法的结果相比，前者在分离混合信号时所需要的迭代次数少，算法的稳定性高。 (5)将基于粒子进化的多粒子群优化算法用于求解非线性方程组。该算法求解精度高、收敛速度快，而且克服了一些算法对初值的敏感和需要函数可导的困难，能较快地求出复杂非线性方程组的最优解。数值仿真结果显示了该算法的有效性和可行性，为求解非线性方程组提供了一种实用的方法。

基于遗传算法的任务调度研究

华中师范大学计算机科学系实验报告书 实验题目：基于遗传算法的多任务调度研究课程名称：智能计算 主讲教师：沈显君 辅导教师： 课程编号： 班级： 2011级 实验时间： 2011年11月

基于遗传算法的多任务调度研究 摘要： 本文主要讨论了遗传算法在工程项目中多任务执行优化中的应用，重点对多任务调度 (Resource —constrained project scheduling problem ，RCPSP)问题进行了研究。讨论了资源受限的多任务调度问题，提出了改进的遗传算法优化多任务调度问题的方法，主要从优化算法模型的建立，优化算法设计，算法的实现以及结果分析等几个方面进行了详细论述，并与其它启发式方法进行了对比分析。 关键字：效益最优化；遗传算法；多任务 1．简介 任务调度优化在工程项目管理中是非常重要的，它决定了工程项目利润的高低。遗传算法是一种并行的全局搜索的高效求解问题的方法，本质上就是处理离散优化搜索问题的，它不要求问题空间的连续性，不需要梯度信息，其鲁棒性(Robust)已经得到了证实，在处理大型复杂优化问题上己经取得了显著的成绩，所以在解决多任务调度优化问题时，具有其它方法无法比拟的优势。 2．多任务调度模型的建立 假设存在若干并行任务和一个共享的资源库，包含有若干种可更新资源(renewable resources)，并且所有资源都只有有限的供给量。任务之间除了共享资源外互相独立。为方便对问题进行描述，建立如下的数学模型：多任务调度问题有P 个相互独立的任务，第k 个任务包含n k+1个工作,其中第n k+ 1个任务为任务虚拟的终止工作,不占用资源和时间。这P 个任务共享M 种可更新资源，其中第m 种资源的总量为R m 。用W i 表示第i 个任务的工作集，W ij 表示第i 个任务中的第j 个工作,其工期为d ij ，对第m 种资源的需求量为r ijm ，任务的开始时间标记为S ij ,它的所有紧前任务形成的集合记为P ij 。在时间t 时正在进行的所有任务的集合标记为I t 。考虑到不同任务的重要程度不同,用a k 表示第k 个任务的权重。综合上述假设和采用的符号，资源约束下的多任务调度问题可以描述为公式（1）-(6)： ∑=+? P k n k k k S 1 1,) (*min （1） j i P h d S S t s ij h i h i j i ,,,. .,,,?∈?+≥ （2） .,, ,∑∈?≤t j i I w m ijm t m R r （3）

基于遗传算法的流水车间调度问题

中文摘要 流水车间调度问题是研究多个工件在若干个机器上的加工次序的问题，有效的调度算法对企业提高生产效率有着重要作用。本文使用遗传算法求解流水车间调度问题，把一个染色体编码成若干个自然数，表示相应工件的排序权值；通过简单交换两个父代的若干相同位置的基因，产生能够继承父代优良特性的子代；并且采用均匀变异，更好地保持种群中的基因的多样性。实验表明，该方法能取得较好的效果。 关键字：遗传算法，流水车间调度方法，实数编码，基因链码，群体，适应度。

外文摘要 Abstract: Flow-shop scheduling problem study the problem the processing sequence of A plurality of workpieces on some working machine,and it makes good effects on proving production efficiency to the industries with effective methods.In the case,we deal with flow-shop scheduling problem using a algorithm,the Genetic Algorithm.There is a chromosome we've just coded into some natural numbers to represent the weight order of these workpieces; exchanging simply two fathers' places of some gene to produce new children that carried good feature on two fathers;we also use the Uniform Mutation,and it keeps its diversity of gene on the population.This experiment show this method can achieve good results. Key Words: Genetic Algorithm, Flow-shop scheduling problem，natural number coding，genic bar code,group，fitness.

基于混合遗传算法的图像增强技术

基于混合遗传算法的图像增强技术 摘要：在图像增强中，Tubbs提出了归一不完全β函数表示常用的几种使用的非线性变换函数对图像进行研究增强。但是如何确定beta系数功能仍是一个问题。在图像增强处理和利用遗传算法快速算法的搜索能力进行适应编译和搜索我们提出了一种混合遗传微分进化算法。最后利用仿真实验证明了该方法的有效性。 关键词：图像增强，混合遗传算法，自适应增强。 介绍 在图像形成传递或转换过程，由于其他客观因素，如系统噪声，不足或过度曝光，相对运动等的影响会使图像通常与原图之间有差别（简称退化）。退化图像通常模糊或信息的提取，通过机器后减少甚至是错误的，它必须采取一些改进措施。 图像增强技术是在其目的是为了提高图像的质量这一意义上提出的。模糊图像增强情况是根据图像使用各种特殊技术集锦的一些信息图像，减少或消除不相关的信息，来强调整体或局部特征的目标图像。图像增强方法仍没有统一的理论，图像增强技术可分三类：点运算，与空间频率增强方法增强法。本文介绍了根据图像特征自动调整自适应图像增强法，成为混合遗传算法。为了实现图像的自适应增强它结合了差分进化自适应搜索算法，自动确定的参数值的变换函数。 图像增强技术 图像增强是图像的某些特征，如轮廓，对比，强调或突出的边缘等为了便于检测和进一步的分析处理，增强将不会增加图像中的信息数据，但会选择适当的动态范围的功能的扩展，使得这些特点更容易检测或确定，为后续的分析和处理的检测打下良好的基础。 图像增强方法包括点运算，空间滤波，频域滤波类别。点运算包括对比度拉伸，直方图建模，并限制噪声和图像减影技术。空间滤波包括低通滤波，中值滤波，高通滤波器（锐化）。频率滤波器包括同态滤波，多尺度多分辨率图像增强中的应用。 差分进化算法 差分进化首次提出了强硬的价值，并与其他进化算法进行比较，DE算法具有强大的空间搜索能力，易实现，容易理解。DE算法是一种新型的搜素算法，它首先是在搜索空间中随机产生初始种群，然后计算之间的任何差异向量的两个成员，不同的添加到向量的第三个成员，通过该方法，形成一个新的。如果你发现新的个体成员比原来的好，然后替换原来的