资源描述:
《免疫算法总结范文.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、免疫算法总结范文 免疫算法总结1介绍Hart和Ross(1998-1999)最早将人工免疫算法引进到解决作业车间调度问题,以优化计算生产调度问题[1-3]。 Aickelin·U将研究扩展到动态调度问题[4]。 Tay·JC和Ho·N·B针对FJSP问题做了一定的尝试。 到xx年,对柔性生产调度问题有了进一步的研究与发展。 在国内,徐震浩为了解决不确定条件下具有零等待的流水车间生产调度问题,借鉴自然界中生物免疫系统的概念和机理,提出了解决此类问题的免疫调度算法 (xx)[5]。 李蓓智构造了面向机床作业的融生物免疫机理和专家系统为
2、一体的生产调度模型[6]。 余建军给出了基于动态评价免疫算法的车间作业调研究[7]。 接着研究者纷纷对柔性生产调度给出了一系列的算法,使得调度的问题不再只有各种理想化的状态,而是越来越再现调度本身的复杂性与不确定性[8-10]。 解决生产调度优化模型主要有整数规划模型、线性规划模型和联络图模型。 求解车间调度问题的方法主要有整数规划法、分支定界法、优先分配规则、拉格朗日松弛法、人工智能、神经网络、转换瓶颈程序、局域搜索方法和免疫算法等[11]。 免疫算法的特性克隆选择、学习、记忆、鲁棒性和适应性。 2解决车间生产调度问题的克隆选择算
3、法2.1目标函数车间调度问题是一种多目标优化问题,它使所有工件的最大完成时间最小,所有设备的利用率最高,即:F1=min(max(makespan(t))),F2=设备利用率 (1)在考虑F2因素的文献当中,公式各异,依据自己的算法所用而定。 f(i)=w1*F1/w2*F2 (2)其中,w1和w2为权重系数。 作业车间调度一般考虑理想化的无等待流水线调度问题。 对于需要考虑延迟时间的,,如文献[12]中,延迟时间τq定义如下:τq=max(0,(cq-dq)) (3)其中,cq是作业q的完工时间;dq为到期日。 这样,最小化延迟
4、时间可以被定义为Minp(q)=n1τ(εq) (4)2.2亲和力计算亲和力亲和力一般都是通过makespan的倒数来确定:Affinity(z)=1/makespan(z) (6)其中,z表示抗体。 另一种方法是采用信息熵[13,14]计算亲和力,熵理论用来评估信息源中样式出现的可能性H(x)=-n1pi*lg(pi) (7)(熵表示物质系统状态的物理量,表示状态可能出现的程度,简单指混乱度。 另一意义离散随机事件出现的概率,是一个数学书抽象的概念,可以理解成某种特定信息出现的概率。 )其中,H(x)为信息熵,X={x1,x2,x
5、3,···xn},pi为质量函数概率。 那么亲和力就用如下公式来计算:其中,k为序列长度,hij=-pij*lg(pij)。 2.3编码方法主要编码编码方式[6]有10种(要找到具体的编码方法)基于工序的编码[10,15]基于工件的编码[16]基于先后表的编码基于工件对关系的编码基于优先规则的编码基于析取图的编码基于完成时间的编码基于操作的编码[17,18]基于机器的编码及随机键编码基于优先调度权值的编码[9]。 2.4初始群体大部分的算法均采用随机产生个体的方法初始化种群。 但随机产生的初始化种群将使调度时间变长,许多学者在初始化种群
6、也做了不是研究。 文献[19]中初始化种群时,随机产生种群(要产生的个体总数为3),文献[20]提出了分别由SPTCH、FTMIH和Johnson的规则[20]产生初始化种群。 文献[21]所提到的快速克隆算法中,初始化种群所用的混沌发生器所产生的初始群体也起到了快速的作用。 (具体规则是什么?)2.5克隆选择克隆的目的是要让较优个体或者是局部最优个体能够占大多数比例,以淘汰掉亲和力最小或者较小的个体。 克隆选择的方法有采用轮盘赌(RouletteWheel)的方法[13,19]和竞赛图法(Tournament)。 (找到这两种方法的
7、具体资料)2.6变异方法(6种)单点变异随机选择个体的一个基因位,对该位的基因进行变异,适用于小步变异。 位交换随机选取个体的两个基因位进行交换,比单点变异的变异步长要稍微长一点[10,13,16]。 反转法:随机产生个体的两个基因位,将这两个基因位之间的序列进行反转得到新的个体,比起单点变异和交换变异,变异范围要大,步长也要大。 三体交叉[13]选择两个个体,与其父代进行基因交换可以继承父代的优良基因。 高斯变异(GM)要求有2个参数μ和标准差σ,由高斯公式N(μ,σ)决定变异的步长。 柯西变异(CM):由柯西随机参数进行大步变异,
8、使得解能迅速跳出局部最优。 一般情况下,反转法的成熟速率要比换位法快,因为它允许大于等于两个工件进行交换顺序。 在算法的早期,由于其离最优解还相差