混合遗传算法及应用

混合遗传算法及应用（精选八篇）

混合遗传算法及应用 篇1

遗传算法和蚁群算法都是受生物进化论的启发而提出来的一种仿生算法,不同在于遗传算法是模拟基因进化的过程,而蚁群算法模拟的是由简单个体组成的群体行为。两种算法都应用于求解组合优化问题上,并取得了一定的成果。本文将两种算法进行融合并应用于TSP[1]问题,并给出了新的融合方式。通过仿真实验表明,改进后的新遗传蚁群混合算法能在保证一定的收敛速度的基础上有效地改进算法的全局收敛性。

1 TSP问题

TSP[1]问题(即:旅行商问题),就是指给定n个城市和两两城市之间的距离,要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为:给定图G=(V,A),其中V为顶点集,A为各顶点相互连接组成的边集,已知各顶点间的边接距离,要求确定一条长度最短的Hamilton回路,即遍历所有顶点当且仅当一次的最短回路。TSP是典型的组合优化难题,常常用来验证某一算法的有效性,以下算法讨论将应用于TSP问题中,以便于算法之间的比较。

2 蚁群算法基本原理和TSP问题求解

蚁群算法(Ant Colony Algorithm,ACA)由意大利学者Colorni A、Dorigo M和Maniezzo V于1991年首先提出,用蚁群在搜索食物源的搜索过程中所体现出来的寻优能力来解决一些离散系统优化中的困难问题[2]。为讨论问题方便,现作如下符号说明。

设m表示蚁群中蚂蚁的数量,n表示城市数量,τij(t)表示t时刻在边e(i,j)上的信息量。

(1)初始时刻,各条路径上的信息量相等,设τij(0)=C(C为常数),蚂蚁k(k=1,2,…,m)在运动过程中,根据各条路径上以信息量为变量的概率决定转移方向:

式(1)中:ηij表示边e(i,j)的能见度,Pkij(t)表示在t时刻蚂蚁k由位置i转移到位置j的概率,allowedk={0,1,…,m-1}-tabuk表示蚂蚁k下一步允许选择的城市,α表示轨迹的相对重要性,β表示能见度的相对重要性。

(2)当蚂蚁完成一次循环后,各路径上信息量根据以下公式进行更新:

式(2)中:ρ∈(0,1)表示信息素含量τij(t)随时间的推移而衰减的程度,△τij(t)表示本次循环中路径e(i,j)上的信息量增量:

△τij(k)(t)表示蚂蚁k在本次循环中城市i和城市j之间留下的信息量。

式(3)中:Q为常数,表示每只蚂蚁周游一遍留下的信息总量;Lk为蚂蚁k在本次循环中所走路径的长。

(3)循环以上步骤,直到周游次数达到指定次数或在一定时间内没有新的更优解出现。

3 遗传算法基本原理和TSP问题求解

遗传算法[3](Genetic Algorithm,GA)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。其中,选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计、控制参数的设定这5个要素组成了遗传算法的核心内容。通常遗传算法的设计主要有以下步骤:

(1)确定数据编码方案,随机产生一组初始个体构成初始种群。

(2)给出评价个体优劣的适配值函数,并评价每一个体的适配值(适应度)。

式(5)中,d(i,j)表示城市i与城市j之间的距离。适应度越小的个体,该个体的路径越短,该个体则越好。

(3)判断算法是否满足收敛准则,若满足则输出搜索结果,否则执行以下步骤。

(4)根据适配值大小以一定方式执行复制操作。

(5)按交叉概率ρc执行交叉操作,本文采用Davis提出的OX算子。

(6)按变异概率ρm执行交叉操作,本文采用倒置变异。

(7)返回步骤(3)。

4 遗传蚁群混合算法的基本思想

本文采用以遗传算法为主体的混合算法,利用遗传算法的随机搜索、快速性、全局收敛性在大范围内寻找一组粗略解,然后以这组粗略解为蚁群算法的初始路径,利用蚂蚁算法的并行性、正反馈机制以及求解效率高等特性求解出最优解。具体做法如下:

根据遗传算法的执行,得到了一定的路径信息素。另外,为了防止算法过早收敛,陷入局部最优解,这里采用最大-最小蚂蚁系统(MMAS)中的方法,即将各路径信息素初值设为最大值τmax。综合这两部分,信息素的初值τc设置为:

式(5)中:τc是一个常数,相当于MMAS算法中的τmin,τG是遗传算法求解出的最优解所转换的信息素值。本文中遗传算法求解结果转换的信息素值是经过路径加2。

5 混合算法的改进

为了得到更优化的算法,进一步提高算法的全局搜索能力以及搜索速度,避免陷入局部最优等问题,本文对上述混合算法从信息素含量ρ值、变异方式等方面做出改进。改进的具体情况如下:

5.1 路径选择策略的引入

在蚁群算法中,蚂蚁在搜索过程的初始阶段的选路策略是一旦某路径上的信息素大于其他路径上的信息素,它就以较大的概率选择该路径,这就使蚂蚁从搜索一开始就可能以较大的概率集中在几条当前局部长度较短的路径上。为了避免蚂蚁从一开始就失去解的多样性,在路径上信息量的刺激未达到蚂蚁的绝对感觉阈限时,让蚂蚁忽视该刺激物的存在。只有当信息量的刺激趋于阈限时,蚂蚁才在信息量的刺激下趋于信息量较大的路径[6]。

第k只蚂蚁按以下概率从状态i转换到状态j:

式(6)中:ρ0∈(0,1),r是(0,1)中均匀分布的随机数。由此增加了所得解的多样性,一定程度上削弱了混合算法陷入局部最优的趋势。

5.2 ρ取值的改进

当问题规模比较大时,一方面由于在信息量更新公式中采用了信息素挥发系数1-ρ,使得那些从未被搜索到路径上的信息量会逐渐减少到0———该路径将不被搜索,这就降低了算法的全局搜索能力;另一方面,当信息素含量ρ值过大时,随着解的信息量增大,以前搜索过的解被选择的可能性过大,也会影响到算法的全局搜索能力。为此应减小ρ值,从而提高全局搜索能力,但这样又会降低算法的收敛速度。针对上述两方面问题,本文采用自适应地改变ρ值。具体做法是:初始时刻取ρ=0.999,当算法在一定的循环次数内取得的最优值没有明显改变时,ρ值减为:

式(7)中:ρmin为ρ的最小值,这样可以防止ρ过小从而降低算法的收敛速度;rand()为随机函数。这种自适应改变ρ值的方法保证了在一定的搜索速度下能有效地提高混合算法的全局搜索能力。

6 改进的遗传蚁群混合算法在TSP问题上的仿真实验

本文的仿真结果是针对Oliver30问题进行的,改进的混合算法中用遗传算法产生初始最优解以及蚁群算法校正最优解时都设定交叉概率ρc=0.75,变异概率ρm=0.05;在蚁群操作部分中蚁周信息量更新常数Q=1000,路径选择策略中取信息量阈限ρ0=0.001。实验分别在α、β不同的取值下,对不同的ρ、ρmin值,针对遗传蚁群混合算法、改进混合算法分别做仿真实验,实验结果如表一所示。

从图一可见,改进后的混合算法在较少的进化代数下得到最短路径,并在整体上以更短的执行时间以及有限的迭代次数中求得最短路径值。新的混合算法在全局性与收敛速度都有了显著的提高,是一种有效的改进算法。

7 结束语

本文将遗传算法与蚁群算法进行融合,提出一种改进的混合遗传蚁群算法,并应用于TSP问题中。通过仿真实验与基本遗传蚁群混合算法(GAAA)进行分析比较,可知:遗传蚁群混合算法从路径的选择策略、参数的自适应取值方面进行了改进,进一步提高了混合算法的快速全局搜索能力。

未来将继续做以下几个方面的研究工作:

(1)对参数做自适应调整或其它改进策略,以提高算法的性能;

(2)改进的遗传蚁群混合算法在其它典型组合优化问题和连续空间优化等问题上的性能还需要进一步的验证,从而拓宽算法在实际问题领域中的应用研究。

摘要：蚁群算法(ACA)与遗传算法(GA)都属于仿生型优化算法,是解决组合优化问题的强有力工具,并都分别成功应用于旅行商问题(TSP)中。本文将两种算法进行融合,并给出了新的融合方式。实验结果表明,新的遗传蚁群混合算法有效地改进了算法的全局收敛性,并加快了收敛速度。

关键词：蚁群算法,遗传算法,混合算法,旅行商问题

参考文献

[1]李士勇,陈永强,李研.蚁群算法及其应用[M].哈尔滨:哈尔滨工业出版社,2004.

[2]Colorni A,Dorigo M,Maniezzo V.Distributed opti-mization by ant colonies[C].In:The First European conference on Artificial Life,France:Elsevier,1991:134-142.

[3]潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998.

[4]Marcus Randall,Andrew Lewis.A parallel implementa-tion of ant colony optimization[J].Journal of Parallel and Dis-tributed Computing,2002,62(9):1421-1432.

[5]http://www.iwr.uni-heidelberg.de/groups/comopt/soft-ware/TSPLIB95/tsp.

混合遗传算法及应用 篇2

求解作业排序问题的通用混合遗传算法研究

车间作业排序理论是生产管理与组合优化领域的重要研究方向,由于其固有的计算复杂性(NP-Hard),一般无法利用经典方法求出最优解.本文针对一般作业排序问题,将遗传算法与启发式方法相结合,建立了一种混合算法框架,利用遗传算法改进启发式方法的求解性能,同时利用启发式方法引导遗传搜索过程,以提高其搜索效率.通过对完工时间与平均延误时间等不同优化目标的计算分析与比较表明,该方法对不同类型的.排序问题均具有相当满意的求解效果.

作 者：周泓 姬彬 作者单位：北京航空航天大学经济管理学院,刊 名：系统工程理论与实践 ISTIC EI PKU英文刊名：SYSTEMS ENGINEERING――THEORY & PRACTICE年，卷(期)：200121(12)分类号：O223 C931.1关键词：作业排序 遗传算法 启发式

混合遗传算法及应用 篇3

车间调度问题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为:

$\left(\begin{array}{l}2-2,1-1\\ 1-2,2-1\end{array}\right)$

该矩阵表示,在机器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.

混合遗传算法及应用 篇4

内燃机是应用最为广泛的动力机械。其中机动车的动力, 是内燃机的最大用户, 其次是各种各样的工程机械、农业机械和小型移动式机具的动力。内燃机的基本参数, 如平均有效压力、活塞平均速度、转速、气缸直径和活塞行程、气缸数等, 反映了内燃机的工作性能和品质。针对设计任务的要求正确选择这些参数, 才能保证所设计的新产品有生命力。

但是长期以来, 内燃机的设计方法, 同许多工程设计中其他传统方法一样通常采用试凑法, 即在设计时参考一些成熟设计, 凭借经验和判断进行初步设计;然后进行校核计算, 检验其是否符合设计要求, 如果不符合设计要求, 则进行修改并调整设计参数;经再校核、再调整, 如此反复几次一直达到满足设计要求为止。这种传统的设计方法, 所得的仅仅是符合设计要求的可行方案, 而不一定是最优方案。因此对车辆发动机工作参数采用优化设计方法具有重要意义。

虽然现在已经有很多成熟的优化方法程序可供选择, 但传统的优化方法存在着求解过程复杂和寻优过程容易陷入局部最优解的问题。本文在采用混合遗传算法对车辆发动机工作参数气缸直径和行程进行优化, 使寻优过程得到简化, 确保可靠地获得全局最优解。

1 遗传算法基本原理

遗传算法 (geneticalgorithm) 是美国Michigan大学的Holland教授在认真分析了生物界进化发展的规律后, 于1975年提出的。它是一种模拟生物进化过程和基于统计随机理论的优化搜索技术, 在解决一些复杂的全局优化问题方面, 获得了成功的应用。遗传算法的优点是擅长全局搜索且对优化问题的函数特性无特殊要求, 是一种优点较多的优化算法, 目前应用广泛。遗传算法的主要步骤有: (1) 编码。 (2) 初始群体的生成。 (3) 适应性值评估检测, (4) 选择。 (5) 按照一定概率进行交叉操作, 得到新一代个体。 (6) 按照一定概率进行变异操作, 为新个体的产生提供机会。

遗传算法具有如下一些突出特点:

(1) 遗传算法通过目标函数来计算适配值, 不需要其他的推导和辅助信息, 从而对问题的依赖较小。

(2) 遗传算法是从许多初始点开始并行操作, 因而可以有效地防止搜索过程收敛于局部最优, 而且有较大的可能求得全部的最优解。

(3) 遗传算法在解空间内进行的是启发式搜索和并行计算, 其搜索效率往往优于其他方法。

2 车辆发动机工作参数优化设计的数学模型[3]

对一定功率的发动机来说, 当汽缸数、平均有效压力、压缩比等已选定时, 必须根据发动机转速n和气缸工作容积确定气缸直径D和行程S, 以便校核发动机转速n是否符合使用要求。

气缸直径D和行程S是内燃机的重要的结构参数, 对内燃机的经济性和寿命影响较大。它们是根据内燃机的用途、强化程度及有关的指标综合决定的。

确定气缸直径和行程需要考虑许多因素, 最重要的有三个, 即气缸热负荷、机械负荷和燃烧室及混合气形成。通常, 首先根据设计任务书的要求, 确定好功率、转速, 由强化程度和当前的技术水平选定平均有效压力、行程系数以及气缸数及其排列。从而确定工作容积。然后确定活塞平均速度。最后, 就可以做气缸直径和行程的优化设计。

设计一工程车辆用135系列柴油机:额定转速n=1 500r/min, 气缸工作容积Vh=2×10-3m 3, 压缩比ε=16, 活塞平均速度Vm=7m/s。

2.1 建立目标函数

中、高速内燃机的气缸的散热面积对热效率影响较大, 气缸热负荷可以由单位气缸容积的散热面积来衡量, 所以选取气缸散热面积最小作为目标函数, 即

式 (1) 中D—气缸直径 (m) ;Hc—气缸高度 (m) ;S—活塞工作行程 (m) ;ε—发动机压缩比。

2.2 选取设计变量

在设计气缸直径D和行程S时必须综合考虑对发动机结构和工作性能的影响。内燃机的功率Pe是与D 2成正比的。在平均有效压力、活塞平均速度等参数不变条件下, 内燃机单位功率的质量 (比质量) 与D成正比, 而相对磨损与D成反比。因此当D增大时, 内燃机结构变得笨重, 而寿命可能延长。另外, 当内燃机的功率不变, 气缸直径D增大时, 气缸数可以相应减少。在拓宽发动机系列时常采用略为加大D来提高发动机。这时, 工作过程方面往往不会有什么困难, 而基本尺寸如气缸轴距、连杆长度一般不变, 生产方面麻烦不多, 而内燃机紧凑性会有相当的改善。

另外这里涉及活塞式内燃机的一个重要结构参数, 即行程缸径比S/D。S/D对内燃机有多方面的影响:

2.2.1 S/D对升功率PL的影响

当活塞平均速度vm不变时, S/D减小升功率PL跟着增大, 使内燃机更加紧凑轻巧。

2.2.2 S/D对燃烧室形状的影响

S/D小的短行程内燃机气缸余隙比较扁平, 对压缩比高的柴油机尤其如此, 使燃烧室有效容积比减小, 燃烧过程较难组织。对汽油机来说, 短行程机的燃烧室也显得不紧凑, 燃烧较慢, 且HC排放较高。

2.2.3 S/D对散热的影响

在其他相同的条件下, S/D下降使D增大, 使得传到气缸冷却水套的热量减少, 活塞组零件的温度上升。

2.2.4 S/D对外形尺寸的影响

单列式内燃机的总长度主要决定于i和D, 所以S/D小的短行程内燃机总长度较大。因此, 单列式内燃机应该用较大的S/D。对双列式内燃机来说, 总长度一般决定于曲轴的轴向尺寸, 气缸布置比较宽松, 所以用短行程结构可以减小内燃机的高度和宽度而不牺牲总长度, 获得总体上更好的紧凑性。

综合以上描述, 并由目标函数的表达式知, 选取气缸直径D和行程缸径比S/D为设计变量, 则设计变量为:X=[x1, x2]T=[D, S/D]T,

从而目标函数可写为:

2.3 确定约束条件

2.3.1 边界约束

通常柴油机气缸直径0.08≤D≤0.15

则得

柴油机行程缸径比0.7≤S/D≤1.3。

则得

2.3.2 机械负荷的限制

活塞平均速度vm是表征活塞式内燃机工作强度的重要参数, 对内燃机性能、工作可靠性和使用寿命有很大关系。分析如下:

(1) vm对性能的影响:当其他参数不变时vm与内燃机功率Pe成正比。但是当内燃机结构不变时, 进排气阻力与Vm2成正比, 在内燃机摩擦损失中占最大份额的活塞组的摩擦损失平均压力Pme与vm2成正比。因此, vm的提高导致Pmc下降。 (2) vm对机械应力的影响:内燃机曲柄连杆机构由惯性力引起的机械应力近似与vm2成正比, 对于行程缸径比 (S/D) 相同的内燃机来说, 应力与vm2成正比。 (3) vm对热负荷的影响:内燃机气缸内单位时间所发散的热量与功率Pe成正比, 所以, 气缸的热负荷, 即单位时间、单位面积发散的热量与vm成正比。 (4) vm对磨损和寿命的影响:综合气压力和惯性力引起的磨损速率, 单位时间、单位面积的线性磨损量可认为与vm成正比, 也就是说, 随着vm的提高, 内燃机的寿命可能急剧下降。

本例取活塞平均速度Vm=7m/s, 则

2.3.3 保证燃烧室及混合气形成

为了利于燃烧和燃烧室内混合气的形成, 希望余隙容积VOC尽可能小, 从而保证足够的有效燃烧室容积。燃烧室总容积为:

式中Vk—有效的燃烧室容积, Vm—余隙容积, Vm=δπD 2/4, δ取决于零件的加工误差, 一般δ=0.008m。

2.3.4 满足汽缸容积的限制

要求的气缸工作容积Vh=2×10-3m 3, 即Vh=πD 2S, 转化为等式约束为

3 应用混合遗传算法求解优化数学模型

相对于传统优化算法, 遗传算法的计算复杂度相当高。特别是对于大型工程优化问题, 适应度评估的计算量很大, 因此必须提高遗传算法的搜索效率, 避免一些不必要的计算, 从而节省计算成本, 使得遗传算法能够在可接受的时间内求解这类问题。遗传算法的这个缺点可以通过复合别的基于梯度的局部搜索算法来克服, 因为局部搜索算法有比较快的收敛速度;这种混合遗传算法可以改善计算效率, 并可以避免输入初始点的要求。本文采用遗传算法和序列二次规划法相结合的复合方法来求解汽车主减速器的优化数学模型。

在Matlab 7.0中提供了GeneticAlgorithm and DirectSearch工具箱, 它是针对MATLAB优化处理算法的扩展, 在MATLAB优化工具箱的基础上, 提供了遗传算法和直接搜索的基本功能。

本例针对车辆发动机工作参数优化设计数学模型, 首先编写计算目标函数适值的程序fitnessfun.m和非线性等式与不等式约束函数程序gacon.m, 然后设置最大遗传代数为200, 初始种群数目为20, 采用双矢量编码 (默认) , 交叉概率为0.9, 变异概率为0.08, 采用前向迁移策略, 选择算子为锦标赛选择, 交叉算子为随机交叉, 变异算子为高斯变异, 调用遗传算法解法器函数, 程序如下:

考虑到当种群规模较大时常规的遗传算法搜索次数太多, 当预先编程设计好的运行精度达到时, 一旦遗传算法正常停止搜索, 将自动调用局部搜索算法类的序列二次规划法继续进行优化模型的求解, 从而减少了迭代搜索次数, 更好的提高了运行精度。

运行结果为:x=0.139 619 475 614 471, 0.935226 844 054 549, fval=0.091 712 925 368 477。

对以上程序运行结果参数进行分析后, 圆整取D=0.140m, S=0.130m。

4 结语

由于遗传算法具有全局搜索的能力, 进行启发式搜索和并行计算, 其搜索效率和精度均较高。这点从遗传算法优化结果可以看出, 常规优化设计的目标函数值是:D=0.135m, S=0.140m, F (x) =0.091 96。采用混合遗传算法改善了发动机的工作参数, 使车辆发动机散热面积得到减少, 另外搜索次数大大减少, 体现了遗传算法和局部搜索算法相结合求解非线性优化问题的优越性。

参考文献

[1]飞思科技产品研发中心.matlab6.5辅助优化计算与设计.北京:电子工业出版社, 2003

[2]谢庆生.机械工程中的神经网络方法.北京:机械工业出版社, 2003

[3]应启光, 王明武.内燃机工程最优化设计技术.北京:人民交通出版社, 1997

[4]孙靖民.机械优化设计.北京:机械工业出版社, 2000

[5]陈连.计算方法与优化程序.北京:兵器工业出版社, 2002

混合遗传算法及应用 篇5

遗传算法和蚁群算法都是受生物进化论的启发而提出来的一种仿生算法,不同在于遗传算法是模拟基因进化的过程,而蚁群算法模拟的是由简单个体组成的群体行为。两种算法都应用于了求解组合优化问题上,并取得了一定的成果。本文将两种算法进行融合并应用于TSP[1]问题,并给出了新的融合方式。仿真实验表明,改进后的混合蚁群算法能在保证一定的收敛速度的基础上改进算法的全局收敛性。

1 TSP问题

TSP[1]问题(即:旅行商问题),就是指给定n个城市和两两城市之间的距离,要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为:给定图G=(V,A),其中V为顶点集,A为各顶点相互连接组成的边集,已知各顶点间的边接距离,要求确定一条长度最短的Hamilton回路,即遍历所有顶点当且仅当一次的最短回路。

2 蚁群算法基本原理和TSP问题求解

蚁群算法(Ant Colony Algorithm,ACA)由意大利学者Colorni A、Dorigo M和Maniezzo V于1991年首先提出,用蚁群在搜索食物源的搜索的过程中所体现出来的寻优能力来解决一些离散系统优化中的困难问题。蚂蚁在觅食的过程中通过一种称之为信息素(Pheromone)的物质相互传递信息[2]。为讨论问题方便,现作如下符号说明。

设m表示蚁群中蚂蚁的数量,n表示城市数量,dij(i,j=1,2,…,n)表示城市i和城市j之间的距离,τij(t)表示t时刻在边e(i,j)上的的信息量。

1)初始时刻,各条路径上的信息量相等,设τij(0)=C(C为常数),蚂蚁k(k=1,2,…,m)在运动过程中,根据各条路径上以信息量为变量的概率决定转移方向:

其中:ηij表示边e(i,j)的能见度,一般取表示在t时刻蚂蚁k由位置i转移到位置j的概率,allowedk={0,1,…,m-1}-tabuk表示蚂蚁k下一步允许选择的城市(tabuk(k=1,2,…,m)表示蚂蚁k已经走过城市的集合),α表示轨迹的相对重要性,β表示能见度的相对重要性。

2)当蚂蚁完成一次循环后,各路径上信息量根据以下公式进行更新:

其中:ρ∈(0,1)表示信息素含量τij(t)随时间的推移而衰减的程度,∆τij表示本次循环中路径e(i,j)上的信息量增量:

∆τij(k)(t)表示蚂蚁k在本次循环中城市i和城市j之间留下的信息量。

其中:Q为常数,表示每只蚂蚁周游一遍留下的信息总量;Lk为蚂蚁k在本次循环中所走路径的长。

3)循环以上步骤,直到周游次数达到指定次数或在一定时间内没有新的更优解出现。

3 遗传算法基本原理和TSP问题求解

遗传算法[3](Genetic Algorithm,GA)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律,是具有“生存+检测”迭代过程的随机化概率搜索算法。其中,选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计、控制参数的设定,这5个要素组成了遗传算法的核心内容。通常遗传算法的设计主要有以下步骤:

1)确定数据编码方案,随机产生一组初始个体构成初始种群。

2)给出评价个体优劣的适配值函数,并评价每一个体的适配值(适应度)。

个体的评价是对每一个体计算其路径的长度,并把该长度作为个体的适应度函数,则规定适应度函数f(x)为:

其中,d(i,j)表示城市i与城市j之间的距离。适应度越小的个体,该个体的路径越短,该个体则越好。

3)判断算法是否满足收敛准则,若满足则输出搜索结果,否则执行以下步骤。

4)根据适配值大小以一定方式执行复制操作。

5)按交叉概率pc执行交叉操作。本文采用Davis提出的OX算子。

6)按变异概率pm执行交叉操作。本文采用倒置变异。

7)返回步骤3)。

4 混合蚁群算法的基本思想

根据遗传算法和蚁群算法两者在混合算法中所处的地位和优势的不同,大体可以划分为两个大类:一类是以蚁群算法为主体的混合算法[4],如文献[5]利用遗传算法GA寻找ACS中参数α、β、ρ的最优组合;另一类是以遗传算法为主体的混合算法。对于前一类混合算法,有两种混合方向,一种是在蚁群算法中嵌入交叉等遗传操作,以产生蚁群算法新路径,提高蚁群算法的全局搜索能力;另一种是首先利用遗传算法的随机搜索、快速性、全局收敛性在大范围内寻找一组粗略解,然后以这组粗略解为蚁群算法的初始路径,利用蚂蚁算法的并行性、正反馈机制以及求解效率高等特性求解出最优解。

当利用遗传算法生成若干组优化解后,根据优化解生成信息素初始分布,具体做法如下:

根据遗传算法的执行,得到了一定的路径信息素。另外,为了防止算法过早收敛,陷入局部最优解,这里采用最大-最小蚂蚁系统(MMAS)中的方法,即将各路径信息素初值设为最大值τmax。综合这两部分,信息素的初值τS设置为:

其中:τC是一个常数,相当于MMAS算法中的τmin,τG是遗传算法求解出的最优解所转换的信息素值。本文中遗传算法求解结果转换的信息素值是经过路径加2。

5 混合算法的改进

为了得到更优化的算法,进一步提高算法的全局搜索能力以及搜索速度,避免陷入局部最优等问题,本论文对上述混合算法从信息素含量ρ值,变异方式等方面做出改进,改进的具体情况如下:

5.1 路径选择策略的引入

在蚁群算法中,蚂蚁在搜索过程的初始阶段,有的路径上有蚂蚁走过,有的路径还未来得及被走过,而蚂蚁选路的策略是一旦某路径上的信息素大于其他路径上的信息素,它就以较大的概率选择该路径,这就使蚂蚁从搜索一开始就可能以较大的概率集中在几条当前局部长度较短的路径上。为了避免蚂蚁从一开始就失去解的多样性,在路径上信息量的刺激未达到蚂蚁的绝对感觉阈限时,让蚂蚁忽视该刺激物的存在,只有当信息量的刺激趋于阈限为时,蚂蚁才在信息量的刺激下趋于信息量较大的路径。这样蚂蚁在初始阶段可选择较多的不同路径,以获得多样性的解[6]。

第k只蚂蚁按以下概率从状态i转换到状态j:

其中:ρ∈(0,1),r是(0,1)中均匀分布的随机数,由此增加了所得解的多样性,一定程度上削弱了混合算法陷入局部最优的趋势。

5.2 ρ取值的改进

当问题规模比较大时,一方面由于在信息量更新公式中采用了信息素挥发系数1-ρ,使得那些从未被搜索到路径上的信息量会逐渐减少到0——该路径将不被搜索,这就降低了算法的全局搜索能力;另一方面,当信息素含量ρ值过大时,随着解的信息量增大,以前搜索过的解被选择的可能性过大,也会影响到算法的全局搜索能力,为此应减小ρ值,从而提高全局搜索能力,但这样又会降低算法的收敛速度。针对上述两方面问题,本文采用自适应地改变ρ值,具体做法是:初始时刻取ρ=0.999;当算法在一定的循环次数内取得的最优值没有明显改变时,ρ值减为:

其中:ρmin为ρ的最小值,这样可以防止ρ过小从而降低算法的收敛速度;rand()为是随机函数。这种自适应改变ρ值的方法保证了在一定的搜索速度下有效的提高了混合算法的全局搜索能力。

6 改进的混合蚁群算法在TSP问题上的仿真实验

本文的仿真结果是针对Oliver30问题进行的,改进的混合算法中用遗传算法产生初始最优解以及蚁群算法校正最优解时都设定交叉概率pc=0.75,变异概率pm=0.05;在蚁群操作部分中蚁周信息量更新常数Q=1000,路径选择策略中取信息量阈限ρ0=0.001。实验分别在α、β不同的取值下,对不同的ρ、ρmin值,针对遗传蚁群混合算法、改进混合算法分别做仿真实验,实验结果如表1所示。

仿真实验表明,改进后的混合算法在较少的进化代数下得到最短路径,通过两种算法获得最好解的进化曲线图,如图1所示,可见改进后的混合算法在一开始就能获得较好的路径值,从而减少了每代计算最短路径的运算,使混合算法在整体上以更短的执行时间在有限的迭代次数中求得最短路径值。

7 结束语

论文将遗传算法与蚁群算法进行融合,提出一种改进的混合蚁群算法,并应用于TSP问题中,通过仿真实验与基本遗传蚁群混合算法进行分析比较,可知:改进的混合蚁群算法从路径的选择策略、参数的自适应取值方面进行了改进,进一步提高了混合算法的快速全局搜索能力。

参考文献

[1]李士勇,陈永强,李研.蚁群算法及其应用[M].哈尔滨:哈尔滨工业出版社,2004.

[2]Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[C].In:The First European conference on Artificial Life,France:Elsevier,1991:134-142.

[3]潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998.

[4]Marcus Randall,Andrew Lewis.A parallel implementation of ant colony optimization[J].Journal of Parallel and Distributed Computing,2002,62(9):1421-1432.

[5]Tony white,Bernard Pagurek,Franz Oppacher.ASGA:Imroving the Ant System by Integration with Genetic Algorithms[C].In:Proc.3rd Genetic programming Conf.July 1998:610-617.

混合遗传算法及应用 篇6

电力的生产、传输和使用依赖于发电系统、输电系统和配电系统。配电系统处于电网末端,是连接输电网和用户的中间环节[1,2]。用户很多且相当分散,检修的任务重,一旦检修,很容易直接引起用户停电,而且配电网检修计划需配合上级输电网检修计划[3,4,5]。随着配电网的发展,其自身的检修及优化问题也逐渐受到重视。

配电网检修计划优化是1个多目标多约束的优化问题。许多智能算法,如遗传算法(Genetic Algorithm,GA)和模拟退火算法(Simulation Annealing Algorithm,SA)等均能应用于配电网检修优化,但在实际运用中却发现它们都存在着一定的局限性:遗传算法虽然有很强的全局寻优能力,但其精细局部寻优能力却较差。而模拟退火算法具有较强局部搜索能力,并能使搜索过程避免陷入局部最优解,但模拟退火算法却对整个搜索空间的状况了解不多,不便于使搜索过程进入最有希望的搜索区域,从而使模拟退火算法运算效率不高[6]。

本文根据配电网检修计划优化的思想,在考虑多种约束条件的基础上,建立了以降低供电企业停电损失为目标的优化模型。利用Lin Feng-tse等提出的混合遗传-模拟退火算法[7](Hybrid Genetic/SimulationAnnealing Algorithm,HGSA)对配网检修计划进行优化调整,并与遗传算法和模拟退火算法的优化结果进行比较,证明了所提出HGSA算法的有效性。

1 配电网检修计划优化模型

结合实际工作,综合考虑系统安全和协调检修等多种约束条件,建立以降低供电企业停电损失为目标的优化模型。

1.1 目标函数

配电网检修计划优化的目标:在满足各种约束条件下,尽量减少停电损失。数学描述为:

式中:Pt为第t时段的单位电价;Uti为第t时段停电第i个负荷的容量(以配电变压器为负荷点);为变压器的容载比;T为检修的所有时间段;N为第t个时间段停电的所有变压器数量。

1.2 约束条件

约束条件包括协同约束和互斥约束,主要体现在目标函数的第t个时间段的N中。

(1)协同约束:当停运某台设备,其他设备将跟着停运时,这些设备应该同时检修。

式中:Xi为第i个设备的开始检修时间;Xj为第j个设备的开始检修时间。

(2)互斥约束:当2台设备互为备用时,在1个时间段内只能检修1台。

式中:Dj为第j台设备检修的持续时间。

(3)检修资源约束:检修的设备总数应该少于等于拥有的资源数。

(4)潮流约束:。

式中:Si为通过设备i的潮流值;为设备i允许通过的潮流限制。

(5)电压约束:。

式中:Vi为第i个节点电压;和为节点i允许的最低及最高电压。

由上述数学模型可见,配电网检修优化是1个复杂的离散非线性优化问题,也可以看作是大规模的组合优化问题[8],若用传统的优化方法求解存在很大的困难。研究人员大多数都开始采用现代的智能优化方法求解,这些智能方法大体包括遗传算法以及模拟退火法等。但配电网设备众多检修优化又存在大量约束条件,所以即使现代的智能优化方法运用到配电网检修优化时也存在大量问题。所以本文采取了遗传与模拟退火结合的混合算法。

2 混合遗传-模拟退火优化算法

与传统的遗传算法和模拟退火算法相比,混合遗传-模拟退火算法主要有以下特点:

(1) HGSA在遗传算法中引入模拟退火思想,有效缓解了遗传算法的选择压力,并对基因操作产生的新个体实施概率接受策略,不但增强了算法的全局收敛性,并且使算法在优化后期有较强的爬山性能,加快了进化后期的收敛速度。

(2) HGSA在模拟退火算法中引入遗传算法的群体操作思想,使算法在解空间展开多处的局部搜索,既加快了算法的搜索速度,又能有效地提高模拟退火算法处理局部收敛问题的能力。

(3) HGSA以遗传算法控制寻优方向,从而加快搜索进程,用模拟退火算法解决局部收敛问题,以提高搜索精度。充分发挥了遗传算法的快速全局搜索性能和模拟退火算法的局部搜索能力,具有较高的效率和广泛的适用性。

遗传-模拟退火混合算法的流程如图1所示。

在优化检修计划时,HGSA可能会产生一些适用性问题,如寻优速度较慢、运算时间较长和收敛精度较差等,针对这些问题,本文采取了如下改进措施:1)在编码方式上改进了传统的二进制编码,直接采用整实数编码,且直接反映检修计划,大大减少了搜索空间;2)构造适应度函数时,加入了反映约束条件的惩罚项;3)在选择方式上,除采用按比例的适应度分配法分配个体的选择概率外,还采用稳态繁殖的选择方法,即在每次迭代中,父种群中2个个体繁殖的新个体直接替代父种群中适应度较差的个体,并与父个体一起参与繁殖下一代,加快寻优速度;4)交叉算子采用一点交叉,为避免杂交后得到的解超出起始时间的上下限范围,杂交的位置必须是介于2个相邻的子分量之间;5)变异算子以一定的概率采用实值变异。因为用的是十进制编码,所以变异不能和二进制编码一样直接将某位或某些位的状态取反,而是按随机方式进行变异;6)为了兼顾计算时间和精度要求,群规模取60,并通过HGSA的概率接受准则解决可能出现的局部收敛问题;7)以最优个体最少保留代数与最大遗传代数相结合作为终止进化的判据,从而避免单因素控制准则的缺陷。

3 算例分析

广灵供电支公司隶属于山西省电力公司,辖有广灵110 kV变电站、东台110 kV变电站、罗疃35 kV变电站和南村35 kV变电站。其中广灵110 kV变电站出线有10 kV加斗线、10 kV宜兴线、10 kV斗泉线、10 kV作疃线、10 kV广百线、10 kV城水线、10 kV广疃线、10 kV微波线、10 kV城一线、10 kV城二线;东台110 kV变电站出线有10 kV东城一线、10 kV东城二线、10 kV东纸线、10 kV东王线、10 kV东蕉线;罗疃35 kV变电站出线10kV罗蕉线、10 kV罗水一线、10 kV罗水二线、10 kV罗一线、10 kV罗锰线10 kV罗化一线、10 kV罗化二线;南村35 kV变电站出线10 kV南村线、10 kV南海线、10 kV南梁线、10 kV南望线。

用本文建立的配电网检修优化模型,分别用遗传算法、模拟退火算法和遗传-模拟退火混合算法对广灵供电公司2009年3月份的检修计划进行优化。其中遗传算法的种群规模为60,交叉率为0.6,变异率为0.01,最大迭代次数为300。模拟退火算法的初始温度t0=K(fmax-fmin),K为初始温度系数取100,fmax为初始种群最大适应度值,fmin为初始种群最小适应度值,退温函数为tk-1=αtk,α为退温系数取0.8。

3 种算法的迭代收敛过程如图2所示。由图2可看出,模拟退火算法在迭代一定次数之后能够到达较优的解,遗传算法因局部参数空间内集中搜索机制薄弱,最优解的更新缓慢,HGSA方法的收敛速度相对最快、寻优结果相对最优。

检修计划优化之前的负荷损失为20.304 MW,各算法优化后的负荷损失及减少的负荷损失如表1所示。

4 结论

本文采用遗传-模拟退火混合算法,通过算法的匹配克服了各自的缺陷,综合了两者的优点,使算法既具有遗传算法的全局性和并行性,又具有模拟退火算法的局部搜索能力和退火特征。计算结果表明该混合算法既加快了收敛速度又减少了负荷损失,最大限度地避免重复停电,更适合配电网检修优化问题。

摘要：从配电网设备检修计划编制的实际需要出发,在考虑多种约束条件的基础上,建立了以配电网经济性最好为目标的优化模型。针对该模型的特点,采用1种新型混合遗传-模拟退火算法(HGSA)对配电网检修计划进行优化调整。该算法综合了遗传算法和模拟退火算法的优点,使其既具有遗传算法的全局性和并行性,又具有模拟退火算法的局部搜索能力和退火特征。通过遗传算法、模拟退火算法对实际检修计划优化结果的比较,证明了所提出HGSA算法的有效性。

关键词：电力系统,配电网检修计划,遗传算法,模拟退火算法,混合遗传模拟算法

参考文献

[1]朱新菊,王毅,万明明.配电网检修计划优化问题的研究[J].陕西电力,2009,37(1):28-31.

[2]李红蕾,戚伟,陈昌伟.智能电网模式下的配网调控一体化研究[J].陕西电力,2010,38(5):91-93.

[3]董雷,鲍海,齐郑,等.一种供电系统检修计划自动制定系统的设计方法[J].现代电力,2001,18(3):58-60.

[4]于尔铿,刘广一,周京阳.能量管理系统[M].北京:科学出版社,2001.

[5]左郑敏,吴耀武,熊信艮.机组检修计划问题的GA&SA组合算法[J].水电能源科学,2001,19(4):64-66.

[6]陈少华,杨澎.遗传算法在火力发电机组计划检修中的应用[J].武汉水利电力大学学报,1999 32(5):23-28.

[7]王凌,郑大钟.一种GASA混合优化策略[J].控制理论与应用,2001,18(4):552-554.

混合遗传算法及应用 篇7

关键词：遗传算法,混合装配线,负荷平衡

1 引 言

装配线的平衡问题是指在作业先后顺序的约束下, 将作业任务分派到工作站中, 以使得各个工作站内负荷尽量接近节拍 (即处于繁忙状态) , 且各个工作站间负荷尽量均衡, 从而确保整条装配线的总闲置时间最少。装配线平衡问题实质上就是组合优化问题, 其受到由产品设计工艺和制造过程技术所决定的作业任务之间先后关系的约束而变得异常复杂。实际中, 装配线的负荷平衡有着特别重要的意义:一方面, 装配生产线的平衡程度不仅直接反映了装配生产线的效率, 而且影响到产品的质量, 如果各工位负荷不均衡, 劳动强度大的工人就有可能为了赶上装配线的运行节拍而匆忙操作, 常常忽视了产品质量。另一方面, 一条负荷不均衡的装配线会给工人不公平的感觉, 易生厌烦和抵触情绪, 进而影响整个装配线的生产效率。

混合装配线能够连续且同时在一条装配线上组装结构相似、工艺接近的不同品种产品, 与单一装配线相比, 其生产过程中产品种类多, 工序复杂。对此本文提出将混装线上不同产品利用虚作业任务整合为一种产品, 即将混装线平衡问题转化成单一装配线平衡优化问题, 之后采用自适应遗传算法进行基于作业任务的平衡优化。

2 问题分析与数学模型建立

本文研究的是第一类的装配线平衡问题, 即给定生产节拍, 在满足工序优先关系的前提下最小化工作站数。生产节拍是根据市场需求预测和企业生产能力计算得出的。问题可由下面的数学模型描述:已知工序集合P={1, 2, …, n}, 给定生产节拍为CT, 完成第i道工序所需标准时间Ti (i=1, 2, …, n) , 并可知工序优先关系矩阵A= (Aij) n×n, 如果Aij=1, 则第i道工序优于第j道工序完成。此关系矩阵即对应于工序约束图的矩阵。设问题的有序工作站集合为G={1, 2, …, m}。定义Vk为各个工序在满足优先关系矩阵A的条件下划分到第k个工作站上的工序集合。则整条装配线工序集合V={Vk|k=1, 2, …, m}。优化目标即是各工作站内外部均衡情况下的最少工作站数, 并求得此时工序集合V的一个最佳组合。

3 遗传算法设计

3.1 编码与解码

本文根据混合装配线平衡问题的特点, 设计了实数编码的方法。首先, 按照装配的先后顺序将各个工序连接成一个实数串, 构成一个染色体。如按规则编码后的一种染色体基因型为142378569。表示先完成操作1, 再完成操作4, 依此类推。染色体的基因型表示了加工顺序, 但不反映工位划分的情况。之后, 需要对染色体进行工序分割, 将各个工序划分到相应的工位。其操作方法是, 按照染色体基因型上操作的排列顺序, 依次逐个将操作分配到工位中, 当安排某操作至某工位内时, 该工位分配的工序总加工时间超过节拍时间, 则将此工序连同后面的工序安排至下一工位, 保证各工位内操作时间总和不超过节拍, 依此类推, 直至将所有工序分配到相应工位中。

3.2 初始种群的产生

初始种群的产生要保证其随机性, 但同时还需要满足装配先后顺序的约束。首先, 依据工序优先关系产生可选工序集合, 之后, 在可选工序集合中随机选定一个工序, 排入染色体基因位, 如此重复, 产生一条染色体。

3.3 选择算子

采用最优保存策略的方法, 首先, 将父代中的最优个体直接复制到下一代, 对于其他个体, 采用锦标赛选择法, 设定锦标赛规模为2, 从父代中随机地选择两个个体, 比较其适应度值, 将较优的个体复制为新代个体, 如此重复, 直至新代个体数目达到种群数量。

3.4 交叉算子

为保证交叉操作后工序先后顺序不被打乱, 采用如下方法:随机从种群中选出两个染色体作为父代双亲, 在其中一条染色体上随机地选取一段基因, 其子代在这段基因里的作业按照另一父代染色体的顺序排列, 其余部分的排列顺序不变, 组成两个新子代染色体。因为双亲都是可行解, 故通过这样的方法产生的子代也必然是可行解。

3.5 变异算子

变异操作采用移位变异法:在父代中任意选择一个染色体, 随机选择一个基因位进行变异。先找出其满足约束关系的可行区间, 然后将变异基因插入可行区间中任意一个位置。

3.6 适应度函数设计

平衡度较好的装配线既要满足各个工位间负荷尽量均衡, 又要满足工位内负荷饱满, 节拍内空闲时间接近于零。以此为目标设计适应度函数, 数学表达式为:

f (Ui) =w1 (PZmax-PZi/ PZmax) +w2 (KCmax-KCi/ KCmax)

其中:KC=[m*max (Ti) -∑Ti]/ m×max (Ti) ;PZ=[∑ (CT-Ti) 2/m]1/2。w1和w2为权重系数, PZ表示装配线上各个工作站间的负荷均衡状况, PZ越小表示生产线工作站的负荷越平衡, KC表示由于生产线上工作站之间作业分配不均而导致的空程时间比率, KC值越大表示工作站损失时间越多。CT为生产节拍, Ti为每个工作站的加工时间, m为总工作站数。

3.7 交叉概率与变异概率设置

本文在遗传概率设置上采用自适应技术, 使交叉概率和变异概率在运算过程中进行动态调整, 一方面, 在运算初期增强算法的搜索能力, 避免陷入局部收敛, 另一方面, 在运算末期增强对优良个体的保存, 利于运算快速收敛于最优解, 交叉概率Pc和变异概率Pm做如下设置:

undefined

式中:fmax——种群中最大的适应度值;

favg——每代种群的平均适应度值;

f′——要交叉的两个个体中较大的适应度值;

f——要变异个体的适应度值;

Pc1、Pc2、Pm1、Pm2——取 (0, 1) 区间的值。

4 算 例

某实验仪器制造工厂, 生产A和B两种仪器, 预测得知两产品的日需求量分别为160、80件。每天有效工作时间为7.5小时。由需求量 (产量) 确定其投产比例为A∶B=160∶80=2∶1, 则在其最小生产循环中, 生产两个A产品, 一个B产品, 计算得平均组节拍为CT=337s, 理论最小工作站数为8 (7.51取整数) 。其混合装配作业优先关系图 (含作业时间) 如图1所示。

使用Matlab-R2008a软件, 设计开发了基于遗传算法的装配线平衡系统, 设置种群规模Ps=10, 设置计算代数为40代, 计算的结果如下表所示:

通过以上实例分析, 算法在进行到第16代以后, 收敛于最优结果, 将所有工序划为8个工作站。计算结果与理论最小工作站数相一致。

5 总 结

混合装配线平衡问题是一个NP-hard问题, 本文通过对不同产品作业任务的整合, 将混合装配线平衡问题转化为单一装配线平衡问题, 进而采用了自适应技术改进遗传算法, 使得交叉概率和变异概率在运算过程中动态调整, 使得算法在运算初期增强了搜索能力, 能够有效避免过早收敛和陷入局部最优解。而运算后期能够很大程度保存最优解, 加快收敛速度。算例结果显示, 算法取得了很好的优化结果, 有效解决了工序分配的问题, 能够为装配线平衡优化提供有力支持。

参考文献

[1]肖中华.基于改进遗传算法的汽车装配线平衡问题研究[D].武汉:武汉科技大学, 2010.

[2]凌文曙.基于遗传算法的混流装配线工作站平衡研究[J].合肥工业大学学报, 2008, 31.

遗传算法与粒子群算法的混合策略 篇8

标准的粒子群算法[1]在进化的过程中, 只是考虑了粒子的个体极值和全局极值, 易陷入局部最优, 进化后期收敛精度不高。本文借鉴了遗传算法[2]的思想, 将粒子群与遗传算法结合起来, 通过计算实例说明, 这两种算法的结合策略能有效解决标准粒子群优化算法[3,4]存在的不足, 可以使得粒子群算法避免陷入局部最优的能力和收敛解的稳定性都有一定的提高。

1 遗传算法和粒子群算法的混合策略

1.1 原理和步骤

GA虽然较PSO算法复杂, 但有其算法上的优势和特点, 为改进粒子群算法[5、6]的性能, 本文仅将GA的交叉操作引入PSO算法中, 主体还是以PSO的算法结构为主, 而又由于粒子的随机性较大, 容易陷入局部最优, 因此为克服混合算法的这个缺点, 本文又加入灾变操作, 对进化过程中的种群施加一个较大的扰动, 使其脱离局部最优点, 开始新的搜索。

算法的主要步骤可归纳为:

1) 初始化粒子群。随机产生N个粒子的位置和速度。数据结构用矩阵A表示。

2) 计算每个粒子的适应度值, 并对每个粒子的适应度进行排序。

3) 将适应度值低即排序在前的一半粒子N/2个粒子直接进入下一代操作, 而后一半粒子进行遗传算法中的遗传选择和交叉操作。

4) 随机产生一个交叉位置进行交叉操作, 交叉结束后, 种群更新。

5) 选择最好的N/2个粒子进入下一代。

6) 根据粒子群算法进行迭代, 由公式 (1) 、 (2) 更新粒子的速度和位置。

7) 如果达到结束条件 (足够好的位置或最大迭代次数) 则结束;否则, 转步骤2) 。这里结束条件为最大迭代次数。

带交叉操作的粒子群算法流程图如图1。

当算法在连续若干代的最优个体都保持不变时, 说明算法已经陷入了局部极值, 需要采取措施使其跳出局部极值的束缚, 就需要进行群体灾变。在本文算法中的灾变想法是只保留最优个体, 其余个体重新生成, 根据上述PSO-GA算法的仿真将灾变条件设置为10代。

带灾变的粒子群遗传算法流程如图2。

灾变操作可以看作是自然界中种族濒临灭绝后的再生情况的一种模拟, 采用灾变操作并非使种族退化, 而是使算法尽快摆脱进化迟钝状态, 开始新搜索的有效手段。

1.2 计算实例

为进行比较, 使用如下三个经典的基准函数对算法进行测试。这三个基准函数具有不同的特点, 可以充分考察新型算法对不同类型问题的优化性能。

(1) De Jong函数[7]

(2) Rosenbrock函数[7]

(3) Rastrigin函数[7]

对于每个基准函数, 设置数据的维数大小为10, 20和30, 相应的迭代次数为500, 100和1500。对每个基准函数都使用了不同粒子数进行测试, 依次为20, 40和80。第一代种群采用随机初始化的方法, 加速因子c1=c2=1.4962, 惯性权重w取0.7298, 结束条件为最大迭代次数, 每个设置重复运行20次。

其他参数如表1。

图3、图4、图5分别是用标准PSO算法, 带交叉操作的PSOGA混合算法以及带灾变操作的混合CPSOGA算法三种方法测试上述三种函数仿真得到的最佳适应度曲线比较, 通过比较可知PSOGA混合算法和CPSOGA混合算法在求解三个基准函数时性能较好, 且灾变操作可以避免算法陷入局部极值, 增加了算法的寻优能力。

2 总结

基本粒子群算法的特点是收敛速度快, 但是易早熟, 针对此缺点, 本文讨论了一种带交叉操作的混合粒子群遗传算法策略, 它既保持了基本粒子群优化算法结构简单、收敛速度快的特点, 同时提高了种群的多样性, 扩大了搜索空间, 且计算复杂度并不高。在此基础上, 进一步探讨了一种带灾变操作的粒子群遗传混合算法CPSOGA, 并将这两种算法与标准粒子群优化算法对三个常用的基准测试函数进行了优化, 对比计算实例结果说明, PSOGA在优化精度方面要优于基本的粒子群算法, 且CPSOGA要更优于PSOGA, 能防止PSOGA陷入局部最优。

摘要：基于对粒子群优化算法原理的分析, 本文讨论了一种带交叉操作的混合粒子群遗传算法以及在此基础上加入了灾变操作的混合粒子群遗传算法。通过三个不同类型的基准函数实例的计算, 混合算法比标准粒子群算法的性能更好。

关键词：粒子群算法,遗传算法,灾变

参考文献

[1]李爱国, 覃征, 鲍复民, 贺升平.粒子群优化算法[J].计算机工程与应用, 2002, 38 (21) :1~3.

[2]周明, 孙树栋.遗传算法原理及应用[M].北京:国防工业出版社, 2001.

[3]Kennedy J, Eberhart R.C.Particle swarm optimization[A].Proceedings of the IEEE International Conference on NeuralNetworks[C].1995:1942~1948.

[4]Eberhart R.C, Kennedy J.A new optimizer using Partieleswarm theory.Proeeedings of the sixth international symposiumon miero maehine and human seienee[J].IEEE service center, Piseataway, NJ, Nagoya, Japan, 1995:39~43.

[5]何庆元, 韩传久.带有扰动项的改进粒子群算法[J].计算机工程与应用, 2007, 43 (7) :84~86.

[6]张建科.几类改进的粒子群算法[D].西安:西安电子科技大学, 2007