混合模拟退火遗传算法

2024-05-15

混合模拟退火遗传算法(精选7篇)

混合模拟退火遗传算法 第1篇

纵观目前学术界已经提出的路由算法,有相当一部分是基于备选路径集的方法,即首先使用前N条最短路算法或者蚁群算法[1],创建源节点到各个目的节点的备选路径集,把组播路由的数学模型转化为一个非线性整数规划模型,再使用遗传、粒子群、神经网络等算法求解这个模型。虽然这些算法利用了生物进化、群智能等仿生智能,但它们都是在非线性整数规划模型的基础上盲目地搜索,其仿生智能没有与问题特征很好的结合。这限制了其优化性能的充分发挥,而且所得到的组播树有可能包含冗余的环路,还需要破圈算法对结果做进一步调整优化。针对现有的QoS组播路由协议,提出了一种新的QoS组播路由算法ACGSAA,其总体思路是,首先利用现有的先进算法,使用多态蚁群算法创建符合QoS约束的备选路径集[2],然后从备选路径集中任意挑选一条路径,组成一个初始组播树,再使用基于GSAA算法对初始组播树进行优化。新算法相对于遗传、粒子群等算法的搜索方式,智能化程度更高,而且能够破除遗传、粒子群算法不能破除组播树内部闭环的问题,求解成功率更高。

1 协议实现

1.1 数学模型的建立

QoS组播路由问题从本质上讲,属于图论里的Steiner树问题。在网络中,建立一棵以源节点为根,覆盖所有目的节点的费用最小的生成树问题[3]。带时延约束的组播路由问题,就是源节点到目的节点的时延不能超过某一个时延限制的Steiner树问题。把通信网看成一个有向连通图G=〈V,E〉,其中V是节点的集合,E是链路的集合。在不改变问题本质的前提下,把节点的延时和延时抖动全部归并到它的前趋链路中,那么可以使用五个关于链路的赋权邻接矩阵,来完整地描述通信网的参数。这五个矩阵分别是:C(Cost,费用),B(Band Width,带宽),D(Delay,时延),J(Delay Jitter,时延抖动),P(Packet Loss,丢包率)。数学模型可表述如下:

由于备选路径集已经考虑了各种QoS约束条件,因此可以不用再考虑约束条件,适应度函数可以先定义为组播树的费用最小化:

当模型初步建立完毕之后,下面会把工作逐渐细化到每一个环节。

2.2 使用蚁群算法创建备选路径集

在算法的初始化中,所有边都被赋予一定信息素。蚂蚁k(k=1,2,…,m)在运动过程中,根据各条路径上的信息量决定其转移方向。这里用禁忌表tabuk,k(k=1,2,…,m)来记录蚂蚁k当前所走过的节点,集合随着tabuk进化过程作动态调整。在搜索过程中,蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。pkij(t)表示在t时刻蚂蚁k由节点i转移到节点j的状态转移概率[4]。

式(7)中,allowedk={C-tabuk}表示蚂蚁k下一步允许选择的节点;α为信息启发式因子;β为期望启发式因子;ηij(t)为启发函数,其表达式如下

为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完一步或者完成对目的节点的寻路后,要对残留信息进行更新处理。借鉴精英蚂蚁的思想,在每次的搜索迭代过程中,局部地更新信息素,同时,在完成一次循环后,选出全局最优蚂蚁,进行信息素地全局更新。这样,采取全局最优蚂蚁的信息素不断地进行全局更新,增强了正反馈机制,提高蚁群算法的收敛速度;同时,只限制蚂蚁在局部进行探索,加快收敛速度。表达式为:

式(9)中,ρ表示信息素挥发系数,则1-ρ表示信息素残留系数,ρ的取值范围为:ρ∈[0,1);Δτij(t)表示本次循环中路径(i,j)上的信息素增量,一般由Δτkij(t)如下确定:

式(11)中,Q表示信息素强度,它在一定程度上影响算法的收敛程度;Lk表示第k只蚂蚁在本次循环中所走路径的总长度。

蚁群算法中的蚂蚁在指定的源节点s和目的节点t之间寻找大量的可行路径Pst,使得路径的费用最小,同时还需满足在上面模型中提出的QoS约束:(1)Pst的可用带宽不小于带宽要求Breq;(2)Pst的延迟不大于延迟要求Dreq;(3)Pst的延迟抖动不大于延迟抖动要求Jreq;(4)Pst的丢包率不大于丢包率要求Preq。

完全满足这四条QoS约束的路由可能并不存在,这时可以定义一个罚函数Q(Pst),将约束转化为优化目标的一部分。这时,模型转化为无约优化:

需要指出的是,当满足某条QoS约束时,式(14)中罚函数对应的项为零,此外,各系数的取值要合理,以使得各项在数值上处于同一数量级,并且总和要与原目标处于同一数量级。

设网络共M个节点,求得的最短路径长度为K,那么假设使用Dijkstra算法求解备选路径,该算法的复杂度为O(M2),在单次循环里要执行K次Dijkstra算法,每次循环还有排序的算法,其算法复杂度为lg2K,为了找出前N条O(M2)最短路,以上过程要递归地运行N次,因此算法的复杂度为O(M2NKlg2K),使用蚁群算法求解备选路径集的计算复杂度只与三个参数有关,即网络规模n,迭代次数Nc和每次迭代派出的蚂蚁个数m,因此时间复杂度为O(mnNc),其时间复杂度要远小于Dijkstra算法,优越性可见一斑。

2.3 使用遗传模拟退火算法求解最优组播树

种群初始化的方法,就是使用遗传模拟退火算法,对于每一个目的节点,任意随机地选择一个备选的路径,进行选择、交叉、变异、模拟退火等步骤,之后对优化后的路径加入组播树,对组播树进行归并、剪裁,去掉重复的边和局部的环路。

下面是遗传模拟退火算法的流程[5]:

Step1:给定群体规模max pop,k=0;初始温度tk=t0,群体为pop(k);

Step2:若满足停止规则,停止计算;否则,在群体pop(k)中每一个染色体i∈pop(k)的邻域中随机选一状态j∈N(i),按模拟退火中的接受概率

接受或拒绝j,f(i)为状态i的目标值;这一阶段共需max pop次迭代选出新群体newpop1(k+1);

Step3:在newpop1(k+1)中计算适应函数

式(16)中,fmin是newpop1(k+1)中的最小值;由适应函数决定的概率分布从newpop1(k+1)中随机选max pop个染色体形成种群newpop1(k+1);

Step4:按遗传算法的常规方法进行交配得到crosspop(k+1);再经变异得到mutpop(k+1);

Step5:tk+1=d(tk),k=k+1,pop(k)=mutpop(k+1),返回Step2。

算法中包含了交叉算子、变异退火算子以及选择复制算子,下面分别作介绍。

2.3.1 交叉算子

交叉算法采用简单的“双亲双子单点交叉”算法,如图1所示:

具体操作是:对两个父代染色体,随机选取交叉点,然后互换父代的染色体的基因片断,产生两个新的子代,显然,这种交叉产生后代的方式有助于保持父代的优秀基因。

2.3.2 变异退火算子

Step1:产生随机数rand,如果变异概率Pm>rand,执行下面的操作,否则什么也不做;

Step2:计算Pst的评价值f(x);

Step3:在Pst上随机选择两点s'和t',使用随机深度优先搜索算法得到从s'到t'的路径Ps't',将Pst中从s'到t'的子路径用Ps't'替换掉,得到一条新的路由P'st;

Step4:计算新路由P'st的评价值f(x'),并计算评价值的差值Δf=f(x')-f(x);

Step5:若f(x')≤f(x),说明P'st优于Pst,P'st替换Pst;若f(x')>f(x),说明P'st劣于Pst,但仍然以概率exp(-Δf/T)替换Pst,但仍记录为替换前的Pst,返回Step1。

2.3.3 含浓度均衡措施的选择复制算子

为了克服传统遗传算法“过早收敛”这样一个缺点,本文设计了“含浓度均衡措施的选择复制算法”。其关键在于调整转轮赌扇区面积,防止个体适应度过分两极分化。操作如下:

Step1:对群体pop(k)中的每一个染色体popi(k),计算其适应度函数:

注意,该适应度函数含当前温度tk,同样起到降温加速适应函数的作用;

Step2:计算转轮赌扇区面积,并经浓度调整系数β校正:

校正后的扇区面积(即选择概率分部)为:

Step3:按照调整后的选择概率从pop(k)中选择M个染色体作为下一代种群pop(k+1)。

2.4 代价函数

对于某个待考察节点,创建其半径为R的广义邻居节点集,计算广义邻居节点集的代价函数分布,得到的一个代价分布向量:

代价函数的计算方法是,将待考察节点移动到某个广义邻居节点,对应的被切断的单播子径使用FLOYD算法进行“接续”,得到一个新的组播树,按照下式计算“势能”。

式(21)中,E1是组播树的费用,E2是QoS约束惩罚函数之和,E为“势能”,即代价函数。

3 仿真与分析

3.1 使用改进salama网络拓扑随机生成算法产生

网络结构

为验证算法的性能,在Matlab下使用改进的Salama拓扑函数生成网络仿真,如图2所示,在区域为1 000×1 000(km2)内生成50个节点,使用该函数的优点在于:(1)使用K均值聚类控制节点分布的疏密,使得产生的网络拓扑连通性和均匀性更好;(2)产生的网络拓扑数据丰富,包括:链路的费用、时延、带宽,节点的费用、时延、时延抖动、丢包率;(3)链路时延等于节点距离除以三分之二光速,更加符合实际情况。

3.2 结果分析

本实验中ACO算法选取的参数为α=2,β=1.5,ρ=0.95,Q=5,δ=3,迭代次数为100次,每次放出60只蚂蚁,所得出的优化路径如图3(a)所示。

然后在蚁群算法的基础上,使用ACGSAA对备选路径进行优化,选取的进化代数,M=150,种群规模N=50,变异概率调节参数Pm=0.15,初始温度t0=10,降温系数α=0.95,同一温度下状态跳转次数k=3,所得出的新的优化路径如图3(b)所示。

从图3上可以看出,后者是在前者的基础上再次进行了优化,ACGSAA获得的路径比ACO更加优秀。如果网络的规模更大,那么所得出的效果就会更加明显。图4中算法在迭代达到40多次的时候达到收敛,如果算法初始时选取的路径不同,那么收敛情况也会有所不同,可能选择迭代100次的话会得到更低的势能,不过相应的要牺牲时间来完成。因此我们在研究过程中,如果需要求取问题的更佳结果,那么就要改变算法的细节来加大迭代次数以延缓算法的收敛速度,这也是在以后对算法进行改进的一个方面。

4 结束语

本文针对现有的QoS组播路由协议,提出了一种新的QoS组播路由算法ACGSAA,通过仿真结果可以看出,新算法对于网络服务质量有更好的支持,大大减短了网络传输在路径上的消耗,同时具有兼容性。把经典算法融合运用,可以有效地克制单一算法本身存在的缺陷,也可以把算法本身优势的地方发挥出来,总的来说达到了预期想要的结果。

摘要:对于网络业务,服务质量(QoS)包括传输的带宽、传送的时延、数据的丢包率等。通过使用蚁群算法的自组织能力自动搜寻得到备选路径集,结合遗传模拟退火算法(GSAA)对产生的这些备选路径进行选择、交叉、变异、模拟退火来产生的一个路由协议综合缩短网络的路径消耗以及提高网络传输的服务质量。

关键词:服务质量,蚁群算法,遗传模拟退火算法,路由协议

参考文献

[1] Wang Ziqiang,Zhang Dexian.A QoS multicast routing algorithm basedon ant colony algorithm.IEEE 1007,2005

[2]贾云富,秦勇,段富,等.蚁群算法及其在路由优化中的应用综述.计算机工程与设计,2009;30(19):4487—4491

[3]郑锋,李胜元,高晔方,等.自组网QoS路由协议综述.计算机应用,2007;26(2):270—273

[4]高尚,杨静宇.群智能算法及其应用.北京:中国水利水电出版社,2006

混合模拟退火遗传算法 第2篇

水电站水库运行能否很好地满足电力系统可靠性和经济性要求,关系着水电站整体的运行效益。调度图是实现水库合理运行的重要手段之一。调度图中上、下基本调度线是在各种设计枯水年的来水条件下,水电站按保证出力工作时,水库在年内各时刻的最高和最低蓄水指示线,是水电站及水库合理运行的基本依据;加大出力区与降低出力区也分别考虑到了丰、特丰以及枯、特枯水年的情况。所以在常规调度中调度图既简明实用又对指导水库长期合理、安全、有效的运行具有极其重要的意义。

目前,按常规计算方法绘制的水库调度图仍然是指导水电站运行最基本的可靠工具,在生产中被广泛采用。由于常规方法在绘制水库调度图中的局限性,编制出来的调度图往往达不到可靠性指标和效益(发电量)指标的优化组合,在实际生产运行中通常还需要对水库调度图进行反复的、经验性的检验和修正,才能得到较好的图线位置。

近年来,遗传算法(GA)和模拟退火算法(SA)已成为应用十分广泛的两种智能优化算法。遗传算法的全局搜索能力强,但却存在易早熟、局部搜索能力不足等缺点;而全局搜索能力较弱的模拟退火算法,其良好的局部搜索能力可以弥补遗传算法的不足,提高最优解的可靠性,有利于得到全局最优解。所以,针对常规方法绘制的水库调度图存在的弱点,本文将遗传算法和模拟退火算法结合起来,建立了适用于水库调度图优化的混合模拟退火遗传算法(SAGA),对常规调度图的各调度线进行优化修正,在满足水电站设计保证率和水库组合利用要求下,使发电量尽可能大,达到了改善水库调度图、提高水电站运行效益的目标。

1 思路及模型

水电站水库调度图的绘制采用等出力计算模型,并要求满足各种严格的边界约束条件。在水库具有年/季调节能力的情况下,以月为单位划分时段,同时假设水库除发电外还必须兼顾灌溉防洪等任务。首先遵循行业规范,按照常规水能计算方法绘制出初始调度图[1],以该初始调度图为依据,以多年平均发电量最大为目标,满足各种严格的边界约束条件,采用SAGA算法对各调度线进行优化计算和修正。根据多年径流资料进行模拟运行,比较调度图优化前后指导水库运行达到的保证率及发电量情况,验证SAGA算法对优化调度图的有效性。

优化调度图的模型如下:

目标函数:

其中:E为年发电量;Nt为时段平均出力;M为划分的时段总数;K为水电站综合出力系数;Q引t为t时段水电站发电引用流量;Ht为t时段发电水头;T为时段计算时长。

完全约束条件:

其中:Zt为t时段的初水位;Zmin、Zmax分别为对应时段的最低和最高控制水位;Nt为t时段的出力;Nmin、N预分别为对应时段的最低限制出力和预想出力;T为时段的时间长度;Vt、Qt、qt和Wt分别对应t时段的初库容、入库流量、下泄流量和损失水量;qmin、qmax分别为允许最小和最大下泄流量。

不完全约束条件:

保证率约束:p'≥p

其中:p'为时段达到的保证率;p为设计保证率。

2 算法分析

2.1 遗传算法

遗传算法(GA)是一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应搜索算法,隐含并行性和对全局信息的有效利用能力是遗传算法的两大显著特点[2]。

遗传算法仿照生物染色体,对优化问题的解进行编码,作为优化问题解的表现形式。后按照优化问题的目标函数构造适应函数,并以适应函数值的大小确定编码的优劣。根据自然选择规律以一定概率淘汰较劣的编码,留下适应值较高的编码,组成新的种群进行下一代繁衍。繁衍的过程同样仿照生物染色体的遗传方法,采用交叉、变异等方式以获取新的编码,即优化问题的新解。如此反复,直至达到一定的代数或找到问题的最优解。

2.2 模拟退火算法

模拟退火算法(SA)是一种模仿金属物理退火过程的特殊局部搜索算法。不同于一般局部搜索,它以一定概率接受领域中的较差解,利于跳出局部最优,从理论上来说,可以称其为一种全局最优算法。具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件限制等优点[3]。

模拟退火算法,模拟了金属温度缓慢降低,由高能无序状态转变为低能有序状态的过程。算法首先任选初始解,并设定初始高温,在初始解邻域内随机产生邻域解。根据目标函数比较两者的函数值,若随机产生的新解优于初始解,则无条件接受新解;若新解的函数值小于初始解,则以一定概率接受新解,也就是不完全抛弃差解[4]。如此循环,直至达到热平衡,即达到设定的循环次数。降低温度,重复以上循环,使函数在逐渐下降的每一个温度下都达到平衡。当温度下降到终止温度时,全部循环结束,得到最终的冷却状态,即目标函数的解。

2.3 混合模拟退火遗传算法

基于模拟退火局部寻优的遗传算法,是在传统遗传算法的基础上,将模拟退火方式作为遗传算法除交叉、变异外的另一算子。以遗传算法流程为主体,融入模拟退火算法,提高算法整体优化能力。SAGA算法的基本思想是:首先随机产生一个初始群体,通过选择、交叉、变异等遗传算子对群体中的个体进行遗传操作,得到一组新的个体,此为遗传算法,侧重于全局搜索。再设定初始高温,对这些个体分别进行模拟退火操作,降温至终止温度,产生一组新的优良的个体,即下一代群体的初始种群。此为模拟退火算法,侧重局部搜索。循环迭代计算,直至到达终止条件,或达到设定的最后一代,整个计算结束。

算法的流程图如图1。

3 优化水库调度图的算法设计

本文涉及变量均采用实数编码,以双精度浮点数表示。一条染色体代表一条调度线,染色体(Vn)上的各基因(Zn)表示水库水位,每条染色体含12个基因位,即水库一个水文年内12个月水位变化序列Vn(Z1,Z2,Z3,…,Z12),在解空间内随机生成[5]。整个遗传空间为问题空间,染色体空间为解空间。在模拟退火操作时,将染色体的单个基因视为金属的高能状态,降温后,变为低能状态,即由初始水位解,经退火操作,得到更优的水位值。

取常规方法绘制的调度图各阶段各调度线的标点值为初始值。优化步骤如下:

(1)参数初始化。确定种群大小pop Size,交叉率pc,变异率pm,遗传代数g,初始温度T0,终止温度Tf。

(2)选择最上方调度线为优化目标。固定其他调度线,随机产生pop Size条染色体,每条含12个基因位,形成一个初始种群。各基因的取值范围在目标调度线的上、下另外两调度线对应标点值之间,最下方调度线取值不得小于死水位,最上方调度线取值不得大于正常蓄水位。另外,由于调度图含有多条调度过程线,在初始化种群时,需针对每条调度线随机产生pop Size个染色体。

(3)令每条染色体分别与其他固定的调度线构成新的调度图,指导水库运行,求出每条染色体的适应度,标记适应度最大的个体。本文以惩罚函数求解染色体适应度。以是否满足设计出力保证率为依据,满足则不惩罚,不满足则惩罚。其表达式可以表示为:

其中:aim NVi为染色体Vi作为某调度线时,全部资料年运行后的适应度;n为有径流资料的总年数;p为保证出力;p′为以调度图指导n年水库运行达到的出力保证率;M为惩罚因子;α为惩罚系数。当p'≥p时不惩罚,M与α均取0;否则,M根据惩罚力度取值,α取1。

(4)对种群进行遗传操作。以轮盘赌的方式选择个体,以凸组合方式[6]按概率pc对染色体两两交叉,并以pm概率选择个体变异。为简化计算,进行交叉的个体,不再被选择变异;已变异的个体,也不再被选择交叉。形成新种群后,评价种群全部个体,令第(3)步标记的最大个体,取代新种群适应度最小的个体。同时再次标记适应度最大的个体,并对其每个基因进行模拟退火操作。

(5)视初始基因为模拟退火的初始高能状态,通过模拟退火操作,得到较低能量状态,即较优解。依次对该染色体的各个基因进行模拟退火操作,得到新的染色体。降温过程依靠T0和Tf来控制。由Metropolis准则exp(-f/T0)≈1可知初温T0要足够大才能在合理的时间里搜索尽可能大的解空间[7];终止温度Tf要足够小才有可能得出高质量的最终解,本文采用Tf=T0 kN来控制,其中k为降温系数,为缓慢降温一般取0.9~0.99,N为总迭代次数。等温过程的迭代次数为C/Tk取整,其中C为常数;Tk为降温过程温度Tk=T0kn;n为第n次降温。该方式下温度越低迭代次数越多,可以弥补退火过程中低温粒子不易被接受的缺点。由于模拟退火会以一定概率接受差解,因此,在整个过程中应标记出现的最好解,以便最后返回最优解。

(6)将退火得到染色体返回给整个种群,取代种群中适应度最小的染色体。

(7)对新的种群重复(3)~(6)过程,直到达到迭代次数。标记适应度最大的染色体,作为所选目标调度线优化后的解,取代原有调度线,形成新的调度图。

(8)向下选择第二条调度线,固定其他调度线包括已优化的调度线。重复(1)~(7)过程,直到所有调度线均得到优化,形成新的调度图。

(9)重复以上步骤,顺次对每一条调度线进行循环优化,直到达到迭代次数。循环结束,得到最终优化调度图[8]。

4 实际应用与有效性分析

本文建立的水库调度图优化方法已经成功地应用于某水库的调度图优化计算中。该水库为年调节水库,以发电为主,兼有防洪、供水和灌溉任务。水库的正常蓄水位为627 m,死水位为555 m,装机容量为300 MW,保证出力为150.3 MW,出力系数为8.3。同时,已知该水库的水位~库容关系曲线下游水位~流量关系曲线、水头~预想出力曲线,以及50年逐月平均入库流量实测资料。

参数的选取是通过多次尝试,反复运算,最终确定为pop Size=50,pc=0.75,pm=0.02,T0=1 000 000Tf=10 000,k=0.9,C=1 000 000,整个调度图迭代次数20次,每条调度线迭代10次。遗传代数g采用变动方式确定,即当两代之间适应值相差小于某固定值时,迭代停止。

用C++语言编程求解各过程。采用常规画法绘制的初始调度图如图2。采用混合遗传模拟退火算法优化的调度图如图3。圆点线为下基本调度线,实线为上基本调度线,虚线为加大出力线。

将水库50年实际入库流量分别按优化前和优化后的调度图指导其运行,计算结果对比分析见表1。

由表1可以看出,采用混合遗传模拟退火方法优化的调度图指导水库运行,年平均发电量提高了近4千万k Wh,升幅达2.17%,效益显著;出力保证率提高了1.5个百分点,达到水库运行出力保证率95%的要求;同时弃水量也有一定幅度的减少,水量利用率得到了提高。由此可见,本文建立的适用于水库调度图优化的混合模拟退火遗传算法(SAGA),对整个调度图的优化是有效的。

5 结语

本文基于遗传算法与模拟退火算法,建立了适用于水库调度图优化的混合模拟退火遗传算法(SAGA),对常规水库调度图直接进行优化修正,效果显著。经过实际生产检验,证明该算法对水库调度图的优化是可行有效的。

在当前确定性优化方法难以直接用于指导水电站实际运行,而随机性优化方法由于其使用的复杂性也难以被生产部门广泛采用的现实情况下,对常规水库调度图的优化修正,不失为一种简单明了,即保留了调度图的实用方便与可靠的优点,又在很大程度上溶入了优化方法的先进性,值得在生产实践中推广的思路和方法。

参考文献

[1]万俊,高仕春,艾学山.水资源开发利用[M].二版.武汉:武汉大学出版社,2008.

[2]刘勇,康立山,陈毓屏.非数值并行算法(2)-遗传算法[M].北京:科学出版社,1995.

[3]康立山.数值并行算法(1)-模拟退火算法[M].北京:科学出版社,1995.

[4]Kirkpatrick S,Gelatt Jr C D,Vecchi M P.Optimization by simulated annealing[J].Science,1983,220:671-680.

[5]Robin Wardlaw,Mohd Sharif.Evaluation of genetic algorithms for optimal reservoir system operation[J].Journal of Water Resources Planning and Management,1999(12):25-33.

[6]汪定伟,王俊伟,王洪峰,等.智能优化方法[M].北京:高等教育出版社,2007.

[7]彭东海.基于模拟退火的混合遗传算法[J].湖南工程学院学报,2005,15(3).PENG Dong-hai.A mixed genetic algorithm based on simulated annealing[J].Journal of Hunan Institute of Engineering,2005,15(3).

混合模拟退火遗传算法 第3篇

关键词:仓库选址,遗传模拟退火算法,模拟退火,遗传算子

各种军用物资是部队战斗力的重要组成部分,及时、准确和不间断地供应各种后勤和装备物资,对维持部队战斗力和持续作战能力,保障战斗和战役的胜利,具有重要作用。

战区军用仓库选址,目的在于增快军用物资的流动速度,方便部队并减少不必要的输送成本,该问题属于最小成本问题,即求解使运输成本、变动处理成本和固定成本等之和为最小的最优化问题。

1 模型构建

战时大部分重要军用物资的筹措由总部组织进行,由军工厂运输抵达战区后,首先进入军用仓库,由军用仓库完成卸载和转运,进而根据作战部队的需求由后勤运力分发运输,对作战部队实施前送保障。

据此,设有i个军工厂,j个军用仓库,r支部队。Cij为物资从第i个军工厂发送到第j个军用仓库的运输单价,Wij为从第i个军工厂发送到第j个军用仓库的物资运输量;C'ij为物资从第j个仓库发送到第r支部队的运输单价,W'ij为物资从第j个军用仓库发送到第r支部队的运输量;如果第j个仓库被选中,则SCj为建设第j个物资仓库的固定费用,SC'j为建设第j个物资仓库的可变费用.建立模型得:

(1)目标函数:

(2)约束条件:

其中Ai为第i个军工厂的供应量,Qr为第r支部队的需求量,式(4)表示供需平衡为最佳情况,但实际情况为不等式条件约束,即供过于求。

2 遗传模拟退火算法的思想和算法设计

2.1 遗传模拟退火算法的思想

本文提出的遗传模拟退火算法,是以遗传算法运算流程为主体流程,把模拟退火机制融入其中,用以进一步调整优化群体。在模拟退火时齐算法中,每两个温度之间的状态点是无关的。从理论上看,随着迭代的步数增加,任何一个温度的马氏链都渐渐不依赖起点状态,且在每一个状态的概率服从平稳分布。遗传算法强调的是两代之间的进化关系,但其交配有可能使最优解遗失。结合这两个算法的特点,构成下面的遗传模拟退火算法。

2.2 遗传模拟退火算法的算法设计

STEP1:给定群体规模MAXPOP,k:=0;初始温度tk:=t0,群体POP(k)。

STEP2:若满足停止规则,停止计算;否则,对群体POP(k)中每一个染色体i∈POP(k)的邻域中随机选择状态j∈N(i),按模拟退火中的接受概率

接受或拒绝j,其中f(i)为状态i的目标值;这一阶段共需MAXPOP次迭代,选出新种群New POP1(k+1)。

STEP3:在New POP1(k+1)中计算适应函数

其中,fmin是New POP1(k+1)中的最小值。由适应函数决定的概率分布从在New POP1(k+1)中随机选MAXPOP个染色体形成种群New POP2(k+1)。

STEP4:按遗传算法的常规方法进行交配得到Cross POP(k+1);再变异得到Mut POP(k+1)。

STEP5:tk+1:=d(tk),k:=k+1,POP(k)=Mut POP(k),返回STEP2

遗传模拟退火算法中,STEP2中的群体选择较遗传算法的选择范围要大,用取代遗传算法中的MAXPOP,但它并不是简单地随机选取,而是采用(7)式。(8)式是一个非常好的加速适应函数,当温度较高时加速性不明显;当温度较低时加速性非常明显。

3 模拟退火遗传算法在仓库选址问题中的具体应用

1)编码设计:对于配送中心选址问题的编码,既可以采用二进制编码,也可以采用顺序表和序值编码。本文采用二进制编码的方式进行,即0,1编码的方式,如(0 1 1 0 0 0 1 1…1)的方式编码,它们在编码中的位数代表仓库,即第i位上的数值为1表示选用第i个仓库,如果为0,则不选用。此进二进制编码串表征为粒子群中每个粒子的位置,粒子位置中所有为1的元素表征需要选用的仓库,其中一个粒子中串的形式表征了一种备选方案,通过对串的操作,包括更新它们的位置、更新它们的速度,选取最佳全局位置、个体位置,最佳全局极值、个体极值来进行逐步选优。初始化粒子群时,随机产生N_Group个粒子,即xi为第i个粒子,其中xi=(0 1 0 1 0…1)的二进制字符串,i=1,2,3,…,N_Group。

2)模拟退火操作:模拟退火中的接受概率为,用它来决定是接受或拒绝第i状态邻域中的某一个状态,tk为当前的退火温度。适应度函数是遗传算法中决定解集好坏的依据,仓库选址模型的目的是使仓库运营和建造总成本最低,适应度函数如下:

3)遗传算子的实现:本文借鉴遗传算法中的交叉及变异方式,使粒子群在搜索过程中以此种方式进行速度及位置更新,不断增加解的多样性,拓展新的搜索空间,而减少过早陷入局部最优的概率。

交叉算子(Crossover):交叉算子将被选中的两个个体的基因链按概率进行交叉,生成两个新的个体,交叉位置是随机的。其示意图如图1。

变异算子(Mutation):变异算子将新个体的基因链的各位按概率进行变异,对二值基因链(0,1编码)来说即是取反。其示意图如图2。

4)仿真实例:设有20支部队,有12个备选仓库,有15个军工厂对备选仓库进行物资的供应。其中备选仓库与部队之间的距离大约为60km,军工厂与备选仓库之间的距离约为90km,部队的总的需求量为600个单位,军工厂的总存储量约为1200个单位,备选仓库的提供量约为3000个单位。用Matlab程序编程,设定50个粒子,迭代100次,于92代时达到最优值,其最优为:35.421万元。其示意图如图3。

4 结束语

模拟退火遗传算法在收敛速度及跳出局部极值的能力诸方面也明显优于标准的遗传算法和模拟退火算法。算法加入遗传算法中的交叉和变异方法,以模拟退火方式接受新的粒子,并进行了代间择优保留的策略,增强了算法的鲁棒性。实例验证充分说明了算法的可行性,可靠性及快速性,而且基于Matlab实现的程序具有简单易操作性,更加增强了实现的简便性。

参考文献

[1]邢文训,谢金星.现代优化计算算法[M].北京:清华大学出版社,2005.

[2]任春玉,王晓博.基于模拟退火遗传算法和AHP的选址研究[J].哈尔滨商业大学学报,2006,2(22):58-61.

混合模拟退火遗传算法 第4篇

随着校园网络对系统应用的深入和应用范围的日渐扩大,在使用的过程会逐渐暴露出一些问题。目前学校网络优化及升级改造不但要解决目前校园网中存在的问题对于校园网中可能存在的一些特殊的应用,怎样建设与维护一个高效率平稳运行的控制网络?本文出于实用性的考虑,提出了这样一个网络优化应用问题。

遗传算法以其基本思想简单、便于实现和并行搜索的优点赢得了众多学者和工程人员的青睐,是目前应用最广的优化搜索算法之一,遗传算法已被成功运用于网络优化问题,前人针对网络拓扑设计的研究很多,如Dengiz、Altiparmark和Smith的解决网络可靠性优化的问题。Krommenacker等提出了采用频谱方法和遗传算法的优化方案。王瑞琪针对多目标遗传算法存在的缺陷,提出了基于改进混沌优化的多目标遗传算法。通过引入基于改进Tent映射的自适应变尺度混沌优化方法细化搜索空间和高效寻优,结合非支配排序的群体分级机制和精英保留等多目标优化策略,保持种群多样性的同时保证了进化向Pareto最优解集的方向进行。张聚梅根据遗传算法和模拟退火算法各自的优缺点,提出将遗传算法和模拟退火算法相结合的方法用在曲线拟合上,在B样条曲线拟合过程中设计了新的适应度函数和遗传算子,有效地解决了用遗传算法进行B样条曲线拟合时局部效果好、整体效果不好的问题。邵星提出了基于模拟退火遗传算法的网络编码优化方案SAGAS。张奇智,唐幼纯等使用遗传算法划分交换式工业以太网网络优化问题,无论是设计期优化问题还是运行期优化问题,都属于多参数,多约束条件的NP完全问题。在使用遗传算法进行寻优过程中,在种群里找到令人“满意”的解或无法进一步优化的解的概率很大,这就加快了算法的收敛速度,从而有效地缓解了因网络规模增大带来的”计算爆炸”问题。

本文采用改进的混合模拟退火遗传算法,以降低全网通信负荷和网络延迟为目标,对树形交换式以太网进行网络划分,对网络设备基于通信关系将它们划分到所设计的拓扑中去,进行最优确定,就可使网络在现有设备条件下达到最优,减轻管理上频繁操作带来的不稳定性,从而带来较大的效率和效益改善。

2 问题描述

本文在设计遗传算法优化网络划分时,考虑了一般的通信情况:节点间的通信量可以有不同的权值,同时也考虑了控制器的存在以及现场设备通信的单向性。由于控制区域的存在,控制中心可以有不止一个。网络设计如图1所示。

全网为二级树型结构,圆形叶节点为现场设备,方框节点为交换机,交换机之间使用树型连接。控制器与交换机一一对应,用高速信道相连接,因而可以把交换机与控制器视为一体而简化运算。这样,每一个子树在网络中就是一个控制区域。网络划分的主要依据是任意两个节点间的通信量。如果用编号i={1,2,…,n}代表现场设备和控制器,则通信矩阵可以构建为:

式中:aij—矩阵元素,由源节点i发往目的节点j的通信量权值。

考虑到设备通信的单向性,一般aij≠aji。

用k代表子网数,即交换机数,定义k×k阶的矩阵来表示交换机之间的连接:

定义k×n阶的矩阵定义现场设备与交换机之间的从属关系:

网络设计的目标主要有两个:

(1)减低网络信道上总的通信负荷:

(2)降低总时延:

最终的结果应是每个子网和子网间通信都接近平衡的网络。在此基础上,假设每多经过一重路由,通信时延就增加一倍。

3 模拟退火遗传算法设计及方案论证

3.1 编码方案

模拟退火算法是一种改进的迭代算法,它可以解决大规模组合优化问题,遗传表示是用来表示问题候选解的一种数据结构。不同的问题采用不同的数据结构和遗传表示。问题表述中已确定网络具体连接方式由X1、X2两个矩阵表示网络拓扑结构,中心节点即X1的编码方案,叶节点即X2的编码方案。确定了基本网络拓扑结构之后,意识到网络整体成树形,并且明显地分为中心结点和叶节点上下两层。进一步观察,X1、X2都是k行的矩阵,于是可合并为一个k×(k+n)的矩阵X=[X1,X2]。

如图1所示的8个现场设备和4个中心结点的网络,对应X为:

将分别表示X1和X2的编码连接起来,对应的X编码则为:

3.2 模拟退火遗传算法

在准备运用遗传算法求解问题时,要完成以下四个步骤:(1)确定表示方案。遗传算法在执行开始时,通过检测在搜索空间中随机选取的某些点来尽量学习相关的信息。(2)确定适应度度量。在遗传算法中,每一代群体中的个体都要在未知环境中进行检测以得到它们的适应值,可以是获利、效用、目标函数值得分或其他的一些函数值。(3)确定控制算法的参数和变量。控制遗传算法的主要参数有群体规模N和算法执行的最大代数目M,次要参数有选择概率Ps、杂交概率Pc和变异概率Pm等参数。(4)确定指定结果的方法和停止运行的准则。经过反复运用遗传算子得出的结果还需要经过解码才是实际的解。本方案在遗传算法运行中融入模拟退火算子,实现了模拟退火的良好局部搜索能力与遗传算法的全局搜索能力的结合。算法基本思想:

(1)初始化:初始温度T,初始解状态S,每个T值的迭代次数L;

(2)对k=1,……,L做第(3)至第6步:

(3)产生新解S′;

(4)计算增量t′=C(S′)-C(S),其中C(S)为评价函数;

(5)若t′<0则接受S′作为新的当前解,否则以概率exp(-t′/T)接受S′作为新的当前解;

(6)如果满足终止条件则输出当前解作为最优解,结束程序。

终止条件通常取为连续若干个新解都没有被接受时终止算法。

(7)T逐渐减少,且T->0,然后转第2步。

流程图如下图2所示:

4 小规模网络实验测试

Matlab是Math Works公司开发的、目前国际上最流行、应用最广泛的科学与工程计算软件,广泛应用于各行各业,Matlab能实现基本的遗传算法功能,具有强大的可视化功能,便于算法间对比和调试。设共有k=4个中心结点,n=8个现场设备,gi=3,通信矩阵A为:

设定popsize=100,max_gen=500,Pc=0.3,Pm=0.1,试验20次,混合遗传算法my GA和简单遗传算法GA找到的Pareto最优解用图表显示如下图3所示:

当选择网络划分问题的最终解时,必须在全网的总通信负荷和通信延迟之间进行折衷。综合对小规模网络问题的仿真结果可以看出,相对于标准遗传算法,在解的质量上,本方案的分布比较优秀。模拟退火遗传算法在收敛速度及跳出局部极值的能力诸方面明显优于标准的遗传算法和模拟退火算法。

参考文献

[1]Bergy Paul K,Ragsdale Cliff T,Hoskote Mangesh.A Simulated Annealing Gennetic Algorithm for the Electrical Districting Problem[J].Annals of Operations Research,2003(121):33-35.

[2]Krommenacker N,Divoux T,Rondeau E.U sing Genetic Algorithms to Design Switched Ethernet Industrial Networds[A].Proceedings of the 2002 IEEE International Symposium[C].France:Vandoeuvre les Nancy,2002.152-157.

[3]王瑞琪.基于改进混沌优化的多目标遗传算法[J].控制与决策,2011(9).

[4]邵星.基于模拟退火遗传算法的网络编码优化研究[J].南京邮电大学学报(自然科学版),2013(4).

[5]张聚梅.基于遗传算法和模拟退火算法的B样条曲线拟合[J].计算机工程与科学,2011(3).

[6]邓亮,赵进,王新.基于遗传算法的网络编码优化[J].软件学报,2009,20(8):2269-2279.

[7]武兆慧,张桂娟,刘希玉.基于模拟退火遗传算法的关联规则挖掘[J]计算机应用,2005,25(5):1009-1.

混合模拟退火遗传算法 第5篇

目前计算机辅助考试系统所采用的最多的算法是遗传算法,由于遗传算法具有自适应寻优和良好的搜索特性,得到了众多学者的青睐。学者们通过理论推导和实践运用,发现遗传算法的收敛速度是非常快的,同时寻优的效率也非常高。遗传算法在许多领域内的应用都取得了卓越的成果[1,2],在遗传算法的改进和理论研究方面也出现了许多成功的探索。

组卷算法的设计与实现是影响组卷效率和组卷质量的核心[3,4,5],如何通过建立全新的数学模型,设置不同组卷的指标,从而使组卷模型具有较好的通用性;以及在该模型的基础上构造新的遗传算法编码方法,在避免出现适应值的重复计算和解码过程的复杂过度运算,提高运算效率方面达到良好的组卷效果,该文将给出具体的解决方法。

1 智能组卷的数学模型

智能组卷的核心问题是如何实现对带约束条件的组合进行优化的问题,也就是说,如果在一定数量的题库中检索出一套符合组卷要求的试题组合,从而使自动组卷的问题变成具有多重约束条件的问题,可以通过定义一组约束条件和一个目标函数的组合来描述该问题。

1.1 约束条件

组卷中的一份试卷,实际上就是一个m×n的目标矩阵。其中,n是试卷中的题目总数,m是约束条件,也表示m个重要的属性,用户自行设定具体的约束条件。矩阵中每行元素的值表示每套试题中的m个属性值,矩阵如下:

目标矩阵的主要约束条件有:

1)试卷总分约束

设定试卷中包含试题的分值为矩阵H的第一列,同时满足约束:

其中S表示试卷总分,其最终数值将由用户给出。

2)试卷难度约束

设定试卷的难度分为三个等级:容易、中等、较难,难度由矩阵H的第二列表示,同时满足约束:

其中xi,2=j时,yj=1,否则yj=0,Sj为第j个难度级别试题对应的总分,由用户指定。

3)题型约束

设定试题的题型为选择题、填空题、判断题等,题型由矩阵H的第三列表示,而每类试题所占的分数则由用户自行制定,同时满足约束:

当xi,3=j时,yj=1,否则yj=0,Tj为第j种类型试题的总分。

4)知识范围约束

设定各章节的试题所占的分数比列,该比列由教学大纲确定,同时试卷考查的内容要包含所有的知识点章节,试题所处的章节通过矩阵H的第四列来表示,同时满足约束:

当xi,4=j时,yj=1,否则yj=0,Wj为第j章试题的总分,由用户指定。

5)答题时间约束

设定试题预计完成的时间由矩阵H的第五列表示,同时满足约束:

其中第i道试题的预计完成时间表示为xi,5,Q表示预计完成全卷的总时间。

与组卷相关的属性还有很多,如果组卷过程有其他的特殊要求,还可以通过加入期望值、区分度等相关属性来实现,但是,太多的指标将会降低组卷的成功率,同时组卷的结果将会变得较为单一。所有组卷的成功与否与试题库是否合理有密切的关系,这就要求我们在建立试题库时一定要考虑充分。

1.2 智能组卷的目标函数

试卷的总体要求通过矩阵H的列元素的分布来表示,试题的总分数,不同难度试题的比列、不同章节分数的比例、不同教学层次的试题分数的比例、不同题型分数的比例以及试卷的区分度和估值等约束条件都应该和用户的要求相同或者接近于用户的要求,且误差率尽可能地小。

实际应用中,反应上述约束和用户要求的误差可以用f来表示。根据不同试题的重要程度,决定整套试卷的误差f应该为m个约束的加权和。为了能够正常反应试卷的误差,防止试卷的各个误差相互抵消,这m个约束与用户的误差都通过绝对值来取值,目标函数可以表示为:

fi表示第i个约束与用户要求的误差的绝对值;wi是第i个约束条件的权重。

2 遗传模拟退火算法

2.1 基因库的构造

为了减少遗传算法的迭代次数同时加快遗产算法的收敛,应根据试卷题型的比例和总分的要求,从初始化后并且包含知识点约束属性的试题库中随机产生试卷的初始试题,这样不仅能够满足试卷题型和总分的要求,同时也能够满足试卷对知识点的要求。基因库的具体构造步骤如下:

1)构造试题库的多个不同子集。子集中应该包含试题的知识点、题型和难度要求相关的属性,知识点、题型和难度相同或者相近的试题应该划在同一个子集中;

2)计算各题型包含的题目数以及在整套试卷中所占的分数比例。题目数应该满足用户对总分的要求、对题型覆盖情况的要求以及标准化题库中同种题型的试题分数是否相同的特点;

3)计算已经生成的试卷中是否需要同种难度题型的试题以及试题的数量,可以将此试题的数量设定为R;

4)去掉已经存在的试题,保证数据存储对象的低冗余性;

5)检查试题是否满足限制条件,试题需要随机地从各个子集中抽取,以保证不同知识点和难度的试题出现在生成的试卷中;

6)删除不满足限制条件的试题,转到5)继续;

7)将满足条件的试题插入到试卷中,并使R减1;

8)判断当前章节中的试题是否能够加入到当前的试卷中,如果能够加入到当前的试卷中,说明当前的知识点试题已经存在,需要从数据对象中全部删除,然后转到5)继续;如果该章节已经不能够加入试题了,说明该章节中的试题数量已经达到了试卷要求的最大值,则删除对应章节的全部试题,然后转到6)继续;

9)退出循环。退出循环的条件是R为0或者数据存储对象中的试题数量已经不能满足试卷的要求,当R为0时,表示生成试卷成功,否则表示生成试卷不成功。

经过上述步骤,将会生成数量适中的初始试题,并且初始试题在整个解空间上的分布将会非常均匀,试题组合运算的复杂度将会有效地减少,同时随机产生的各套试题之间将会有明显地差距,从而保证了初始群体的丰富性,增强了搜索收敛于全局最优解的可能性。

2.2 编码

本文采用的编码方式为实数串的编码方式,每一道试题均由一条染色体表示,也是试题库中的一个个体。需要考察的知识点的总量由染色体的基因长度表示。

2.3 退火变异算子

退火变异算子是遗传算法和模拟退火算法的关键集成点,退火变异算子的具体描述如下:

1)产生随机数因子,如果变异概率Pm>因子,然后执行以下操作,否则什么也不做;

2)根据(2)式和(3)计算的评估值f;

3)任意改变一个基因,得到一个新的个体;

4)根据(2)(3),得到一个新的评估值计算f(x'),并且计算评估值Δf=f(x')-f(x)之间的差异;

5)如果f(x')>f(x),说明新个体优于旧个体,并且用新个体取代旧个体;如果f(x')≤f(x),新个体比就个体还要差,但仍取代旧个体的概率为(Δf/T)。

3 模拟和分析

3.1 实验参数

通过测试混合遗传模拟退火算法的性能,给出了两个具体问题的实验结果。实验环境是Math Lab7.0模拟器和奔腾四2.8G512M配置的电脑。在遗传模拟退火算法实验中,我们设置的最大遗传代数50,交叉概率为0.85,变异概率为0.005,惩罚因子1.2,退火初始温度是1,温度系数K为0.95。

3.2 实验数据

作为遗传算法的控制参数之一,群体规模的大小将影响遗传算法的性能。我们在实验中设置的群体规模为:10,20,30,40,50,6070,80,90,100,120,150,180和200。相应地,我们进行了多次实验。其中两次实验结果如图1、图2和图3所示。图表中的数据分别为10次试验的平均值。

遗传模拟退火算法中,染色体的长度主要取决于解决问题的精度要求。更高的精度和更长的染色体,搜索空间更大。从这些数字中,我们可以看到,问题数量增加,但搜索空间变得更大,而所耗费的时间是有限的。仿真结果表明,遗传模拟退火算法的收敛速度快,可以采取。

4 结束语

该文主要研究组卷生成算法的使用。通过对测试文件中的每个约束条件进行仔细分析后,给出了一个新的基于遗传模拟退火算法的智能组卷问题的数学模型。试验结果证明,在论文中的算法是正确的,并为实际问题提供了妥善解决的方法,它可广泛应用于教学活动。

摘要:考试数据库中的智能测试组卷是在一定约束条件下的多目标参数优化问题。通过应用传统的数学方法,很难解决这个问题。该文给了一个数学模型,并提出了一种新的遗传模拟退火算法来解决这个问题。通过对该算法的测试表明,新算法能够很好地提高组卷的成功率,并且在组卷的收敛速度和防止早收敛方面有了很明显地改善。

关键词:智能组卷,多目标参数,遗传模拟,退火算法

参考文献

[1]李枚毅,蔡自兴,孙国荣.自适应遗传算法与多样性制导的突变和其全局收敛性(英文)[J].中南大学学报:英文版,2004,11(3):323-327.

[2]袁晓辉,曹玲,夏良正.具有成熟前收敛判断的自适应遗传算法(英文)[J].东南大学学报(英文版),2003,19(1):40-43.

[3]RudolPh G.Convergence analysis of canonical genetic algorithms[J].IEEE Transactions on Neural Networks,1994(4):4-12.

[4]Liaw CF.Hybrid genetic algorithm for the open shop scheduling problem[J].European Uournal of Operational,2001,124(1):28-42.

混合模拟退火遗传算法 第6篇

随着科学技术的发展,人们对汽车的乘坐舒适性要求越来越高。发动机的振动噪声是车内振动噪声的主要来源之一,其特点是多振源、宽频带、形态复杂,因而对隔离发动机振动向车内传递的关键部件——动力总成悬置系统的设计要求越来越高。实质性地改善发动机悬置系统特性,是解决隔离发动机振动向车内传递的关键[1]。

动力总成悬置系统解耦优化目标和悬置参数之间的函数关系非常复杂,存在着多个局部最优解,因此选择合适的算法来避开最优解显得尤为重要。传统算法依赖于梯度,且往往从一个初始点开始搜索,容易陷于局部最优解。遗传算法由多个初始点开始搜索,而且不需要梯度,全局优化能力强,但实际应用时容易出现早熟和局部寻优能力差的问题。模拟退火算法模拟高温金属降温的热力学过程,其局部寻优能力强,并可使搜索过程免于陷入局部最优解,但不便于搜索过程进入最有希望的搜索区域,且效率低。遗传模拟退火算法将两者结合起来,让二者优势互补,既发挥了遗传算法的全局寻优能力和模拟退火算法局部寻优能力强的优点,又克服了遗传算法局部寻优能力差和早熟,以及模拟退火算法效率低下和全局寻优能力差的缺点。本文通过动态调节交叉概率Pc和变异概率Pm来克服遗传算法的早熟问题,并将改进后的遗传模拟退火算法应用于发动机悬置系统的优化计算。

1 动力总成悬置系统模型

根据具体的动力总成悬置系统和悬置数目,同时考虑悬置系统的刚体固有频率远低于发动机的弹性体固有频率,动力总成悬置系统的简化模型如图1所示。动力总成悬置系统通过四个三维的黏弹性悬置元件支承在车架上,具有六个自由度[2]。动力总成的坐标系原点选在总成质心处,X轴平行于曲轴中心线,指向发动机前端,Z轴平行于气缸中心线,指向发动机缸盖,Y轴根据正交坐标系的右手定则确定。图中1、2、3、4为四个悬置布置点。

由拉格朗日定理可建立动力总成橡胶悬置系统六自由度振动微分方程:

式中,M为系统质量矩阵;K为系统刚度矩阵;C为系统阻尼矩阵;q为六个广义坐标列向量,q=(x,y,z,θx,θy,θz);F(t)为系统所受激励力向量,F(t)=(fx,fy,fz,fθx,fθy,fθz)。

2 能量解耦法优化设计

在设计悬置系统时,应尽量使其具有较高的振动解耦程度,采用的方法通常为能量解耦法[3]。其计算方法为:通过对数学模型的微分方程的计算,可以求出各阶主振动时的能量分布,将它写成矩阵形式,定义为能量百分比矩阵。当系统以第j阶模态振动时,此矩阵的第k行的l列元素为

k,l,j=1,2,…,6

式中,φ(k,j)、φ(l,j)分别为第j阶振型的第k个和第l个元素;M(k,l)为系统质量矩阵的第k行、第l列元素;ωj为第j阶固有频率。

当系统以第j阶模态振动时,第k个广义坐标分配的能量占系统总能量的百分比为

式(3)的计算值越高,解耦度也越高,当其值达到100%时,系统作第j阶模态振动时能量全部集中在第k个广义坐标上,即该阶模态振动完全解耦。

2.1 目标函数

由于实际布置空间的限制,要实现动力总成完全解耦是很困难的,对于本文研究的四缸机来说,二阶惯性力和二阶转矩是悬置系统的主要激振力,故本文主要考虑沿Z方向和绕X轴的解耦状况[4]。其目标函数为

式中,Ez、Eθx分别为Z向能量百分比和绕X轴方向能量百分比。

2.2 设计变量

由于动力总成的位置受到车架和其他器件的限制[5],悬置的角度可变动的范围也很小,因此以前后左右四个悬置的主刚度值Ki(i=1,2,…,12)为设计变量。

2.3 约束条件

2.3.1 频率约束条件

为保证悬置的使用寿命,系统各阶频率一般都要大于5Hz[6],而从系统隔振理论来说,当系统固有频率小于激励力频率的1/槡2时才能达到隔振效果[7],本文研究的发动机怠速转速为800r/min,则其怠速下点火脉冲频率为f=Nqn/(30C)=26.6Hz(Nq为汽缸数,n为转速,C为冲程数),因此该悬置系统的固有频率应满足5Hz≤fi≤18.8Hz(i=1,2,…,6)。另外,为保证悬置系统各阶模态不发生共振,一般要求各阶固有频率的最小差值在1Hz左右;由于人体对垂直振动最敏感的频率范围在4~6Hz,所以悬置系统的垂直固有频率最好不要在这个范围内[8]。

2.3.2 刚度约束条件

悬置位移不能过大,过大的位移既容易使悬置剪切破坏,又会降低使用寿命,因而悬置主刚度不能过小,悬置刚度约束为

为方便优化计算,所有约束条件均转换成gi(x)≤0(i=1,2,…,42)形式。

2.4 改进遗传模拟退火算法优化设计

改进后的遗传模拟退火算法流程如图2所示。

针对遗传算法的早熟问题,本文使用早熟判定标志ε来动态调节交叉概率Pc和变异概率Pm。

2.4.1 编码与解码方式[9]

由于悬置主刚度值很大,可以达到106 N/m,为得出悬置参数的较准确值,一般用15位左右的二进制编码串分别表示各变量。将所有变量的二进制编码串起来,组成15s位的二进制串,这就构成了函数优化问题的染色体编码方法,使解空间和遗传算法的搜索空间具有一一对应的关系。而解码时,将15s位二进制编码串截断为s个二进制编码串,分别将它们转换成对应的二进制整数代码,分别记为xi(i=1,2,…,s),将之转换为s个变量的解码公式为

2.4.2 初始化

确定种群大小N,最大进化代数G,退火初始温度T,温度冷却系数C,初始交叉概率Pc和初始变异概率Pm。初始种群中的N个染色体个体在各个基因的取值范围内随机产生。

2.4.3 适应度计算

作为对环境的适应度,以决定该个体是否繁殖。适应度公式为

式中,J(x)为目标函数;R为惩罚因子;gi(x)为约束函数。

2.4.4 计算交叉概率Pc和变异概率Pm

为防止早熟,引入早熟判定标志ε来调节Pc和Pm,第l代种群适应度平均值为

式中,L为t代种群规模;F(l)i为第l代第i个体适应度。

设早熟判定标志为ε,则

式中,Fmax(l)为第l代种群中最优个体适应度;FGmax为适应度大于平均值的个体平均值。

交叉概率Pc和变异概率Pm的计算式为

式中,α1、α2为大于0的常数。

由式(10)、式(11)可知,当α1、α2增大时,Pc和Pm会随之下降,从而可以动态调节Pc和Pm,防止早熟。

2.4.5 遗传操作

按照计算出的适应度值及Pc和Pm,对各个体进行选择、交叉和变异等遗传操作,其中Pc和Pm的确认方式为:若ε≥ε*,则用上步计算出的Pc和Pm计算,否则使用初始值计算。这样的遗传操作会倾向于产生更好的解。

2.4.6 退火操作

假设遗传到l代时,第i个设计向量X(l)i对应的罚函数值为H(l)i,通过遗传操作将X(l)i演化为X(l′)i,对应的罚函数值为H(l′)i,按Metropolis接受准则接受新值:

式中,Pi为接受概率,Pi=exp[(F(l)i-F(l′)i)/T];r为[0,1]的随机数。

如此迭代到最大遗传代数时,返回最优结果。

2.5 优化算例

优化对象为某国产动力总成悬置系统。算法参数设置为:种群大小N=500,最大进化代数G=800,初始交叉概率Pc=0.6,初始变异概率Pm=0.06,冷却系数C=0.6,初始退火温度T=100 000,ε*=0.1,悬置系统的各项数据及优化前后的固有属性如表1~表5所示。

从表3中可以看出Z向的固有频率为6.36Hz,很接近人体对垂直振动最敏感的频率;Z方向的解耦率为90.79%,绕X方向的解耦率为45.51%,与Y方向振动有很高的耦合。很明显,Z方向固有频率和绕X方向的解耦率需要改进。

从表5中可以看到:与优化前的结果相比,系统的固有频率都达到了要求,Z向的固有频率提高到了9.26Hz,远离了人体的敏感频率;Z方向的解耦率和绕X方向的解耦率也分别提高到了96.89%和94.06%,优化结果很符合要求。

3 优化结果的蒙特卡罗法稳健性分析

以上的优化结果都是确定性的结果,但在实际生产中,会有很多不确定因素和随机扰动,如材料参数、运行环境、加工误差等,使得悬置的主刚度并不能精确达到优化结果所要求的值,而是在一个较大的范围内波动,从而引起系统解耦度以及静变形的变化。因此,有必要对优化结果进行稳健性设计。

本文采用蒙特卡罗方法对悬置主刚度进行稳健性分析。蒙特卡罗方法又称为统计试验法,通过产生服从一定分布的随机变量,计算响应值的分布情况,以确定变量的变化对响应值的影响[10]。本文取±10%为悬置刚度的变化范围(分布为正态分布)进行稳健性分析。从图3、图4所示可以看出,在悬置刚度有一定波动范围的情况下,两个方向的振动解耦率基本都能保持在90%以上,且集中分布在98%、94%左右。因此,系统的解耦度能够满足稳健性要求。

4 结束语

本文通过计算表明,改进的遗传模拟退火算法能有效应用于动力总成悬置系统的优化;优化结果的可靠性分析表明,计算出的优化结果符合对动力总成优化结果的要求。

参考文献

[1]梁天也,史文库,唐明祥.发动机悬置研究综述[J].噪声与振动控制,2007,27(1):6-10.

[2]Zou Chunping,Hong Xing.Modal Synthesis[J].Jour-nal of Sound and Vibration,2002,80(32):105-112.

[3]梁天也,史文库,洪泽浩,等.发动机悬置系统优化设计[J].噪声与振动控制,2007,27(8):44-46.

[4]黄鼎友,吉向东.动力总成悬置系统建模及振动仿真[J].江苏大学学报(自然科学版),2005,26(3):222-226.

[5]John B.Optimization of Engine Mounting Systemsto Minimize Vechile Vibration[C]//Noise&Vibra-tion Conference&Exposition.Traverse City:SAE,1993:632-636.

[6]Seonho C.Configuration and Sizing Design Optimiza-tion of Powertrain Mounting Systems[J].InternationalJournal of Vehicle Design,2000,24(1):35-47.

[7]庞剑,谌刚,何华.汽车噪声与振动—理论与应用[M].北京:北京理工大学出版社,2006.

[8]侯勇,赵涛.动力总成悬置系统解耦设计[J].汽车工程,2007,29(12):1094-1097.

[9]夏海,高立新,陈剑.基于伪并行遗传算法的发动机悬置系统解耦优化[J].汽车工程,2008,30(12):1087-1090.

混合模拟退火遗传算法 第7篇

Job-shop调度是制造企业中的核心问题,在生产实际中有着广泛的应用并且占有重要的地位。研究表明[1],制造业中总的运作花费的10%~20%与加工顺序有关,适当的设施布置可以节省加工运费与时间,缩短生产周期,加快流动资金周转,从而降低企业运作成本和提高生产率。因此一直以来,Job-shop调度问题吸引着众多学者为之探索。

1 自动化制造最小完工时间调度

最小完工时间调度问题是Job-shop调度问题中的关键问题。在制造业中,最小完工时间调度是指在工作流程满足一定约束的条件下,确定在多个不同的机器上的最适宜的加工顺序,使得任务完工的总时间达到最短。这是一个典型的NP难问题,即没有多项式时间复杂度的确定性算法求解[2]。目前针对该问题已经有很多学者投入了很多关注,典型的方法就是采用贪婪的思想设计一些启发式算法,求出NP难组合优化问题的近似解。但是,这类方法仅能找到问题的次最优解。采用穷尽搜索的方法能够找到最优解,但由于计算量大,只适用于设施数较小(一般≤15)的情况。因此关于Job--shop调度的求解,也可以分为最佳算法和次最佳算法两类。最佳算法是能够找到最优解的算法,如分支定界法(Branch and bound)、割平面法(Cutting plane algorithm)等;次最佳算法能在有效时间内找到一个问题的满意解,例如传统启发式算法如新建法(Construction methods)、改进法(Improvement methods)、混合法(Hybrid methods)、图论法(Graph theoretic methods)等。

人工智能技术为NP问题提供了一些寻求满意解或次最优解的有效方法。这些方法一般都具有快速的计算模式,因此可以同时得到多个备选解;此外,在迭代求解的过程中引入了允许更优解出现的机制,所以能够逃逸出一些局部极值点,如模拟退火法SA(Simulated Annealing)[3]、禁忌搜索TS(Tabu search)、神经网络(Neural network)、遗传算法GA(Genetic Algorithm)[4]等等。SA是一种基于物理学中固体退火原理的随机迭代优化算法,其运行机理是:算法从一个初始状态点出发,以结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,在当前步中以一定的概率接收目标函数值不太好的状态,多次迭代后最终达到一个系统的内能最小的状态。因此算法具有有效避免陷入局部极小的特点。

其缺点是SA是一个串行的算法,在退火降温的过程比较慢,求解的质量也取决于问题的规模。遗传算法是一种具有内在的并行性的全局优化方法,它不需要目标函数具有连续性的假设,能够利用所设计的一系列进化算子迭代收敛到一个全局最优解。但是,基本的遗传算法存早熟的间题,进化操作的参数难以选择等问题。因此本文将遗传算法和模拟退火算法结合,提出采用退火算法遗传算法(SAGA)来解决最小化制造时间的Job--shop调度算法。该算法同时具有遗传算法的全局搜索能力、内在并行性,以及模拟退火算法强大的局部搜索能力,比单纯的遗传算法或模拟退火算法具有更好的优化性能。

实际中最小化制造时间的Job--shop调度是个复杂的NP问题,难以建立一个简单的数学规划模型来求解此问题,因此在实际求解中常常采用各种各样的调度简化模型进行近似求解。假设待加工的产品有n个,N={1,2,…,n}为产品集合,可加工产品的机器设备有m台,M={l,2,…,m}为机器设备的集合,产品与产品之间相互独立,m台机器可加工产品的类型各不相同。如果每个产品只有一道工序,即只能由m台机器中的某一台来完成加工任务,我们的目标就是在最小化制造时间的约束下寻找一个最优Job--shop调度,假设每个时刻每台机器仅能生产一个产品,并且一个产品一旦被某机器生产就不能中断,即确定某产品在各个机器上的加工顺序,使生产完任务后总的完工时间最短。

记所有能生产产品i的机器集合为这里表示产品i由机器j生产所用的生产时间,则最小完工时间调度的目标为:

则最小完工时间调度问题就是要寻求一个调度方案使得G最小。

2 基于模拟退火遗传算法的自动化制造最小完工时间调度优化

2.1 编码

作为一个组合佳化问题,最小完工时间调度问题包含两个要素:变量和目标函数。首先考虑对待求的变量进行编码,可以选择的编码方式有二进制编码、实数编码等。在如果直接对变量采用二进制编码的方法,则所得到的个体或染色体的长度则为n·m位,这无疑增大了解空间的规模。为此本文根据问题的特征,采用实数编码。它存在的问题就是在每代将产生大量的非法解,这里采用额外的检查操作来消除非法解。

2.2 算法原理

模拟退火遗传算法(SAGA)将遗传算法的全局搜索能力、内在并行性和模拟退火算法的强大的局部搜索能力有效的进行整合,从而弥补了单纯的遗传算法或模拟退火算法的缺点,获得了高效快速的搜索。两种算法的结合有三种方式:以GA为主线,将SA嵌入到GA中执行,或以SA为主线,将GA嵌入到SA中执行,或者二者互相嵌入实现。本文采用的是第三种策略。算法原理如下:首先,GA进行若干代数的进化,获得一个最有解;其次,SA设置某一个较高的初始温度,将GA得到的最优解作为其初始解,伴随温度参数的不断下降,结合概率突跳特性以随机的方式在解空间中随机寻找目标函数的最优解;第三步,将SA得到的解作为优良个体种子注入到GA的进化种群中,再进行进化。依次执行该过程,直到算法满足终止条件。

为了加快算法的收敛速度,我们采用了并行的算法实现方式。目前进化算法的多处理器并行实现得到了许多学者的广泛关注。根据多处理器的连接拓扑结构进行区别,可以分为主从式(Master-slave)多处理器并行化方法、粗粒度模型(Coarse-grained)多处理器并行化方法、细粒度模型(Fine-gained)多处理器并行化方法等三个主要的类型[5]。在本文算法中,我们所采用的是一种基于粗粒度模型的并行模拟退火遗传算法。粗粒度模型的基本思想是:将算法中全部的进化群体剖分为多个含有较少个体的子群体,每个子群体尅执行单独的进化,该进化过程在一个处理器上实现,各个子种群的进化以并行的方式独立的实现。同时,各个子种群之间互相交换最优个体,在设定好的若干代数之后,各个子种群所获得的最佳染色体就会互相迁移,并形成新的子种群。其中迁移的方式取决于各个子种群连接的邻域结构,在有邻域连接的两个种群之间可以交换最佳染色体,而没有连接的子群体之间不进行交流。

2.3 交叉

目前文献中对组合优化问题多采用的是Goldberg和Lingle提出的PMX(部分映射交叉)方法,它执行简单的两点交叉之后再用特别的修复程序来解决简单两点交叉引起的非法性,即修复个体。本文算法中采用直接的一点交叉方法来达到父代个体之间信息交换的目的。其中,交叉点由均匀分布随机产生,然后将交叉点至尾部的子串交换后分别插入到两个原父本个体编码串的前端,再分别删除原父本中与添加部分相同的分量即得到新的个体

2.4 变异与选择

这里采用单点突变的方式,随机选择两个变异点,交换基因。对于选择操作,在每一次进化中,从每一代种群中随机选择一定数目的精华解组成一个临时最优解集合,该集合可以不断地被更新和保存。它可以作为一个外部的存储而独立存在,也可以在选择过程中通过引入其中的成员而被包含到选择过程中。本文中,我们采用如下方案:保留1-5%的精英组成一个临时最优解集合,用它替代种群中适应度函数排在最后1-5%的个体。

2.5 并行模拟退火遗传算法步骤

1)随机产生一个初始种群,种群中个体数目为MN。将种群划分为N个具有M个个体的子群体Pi(i=1,2,…,N),为子群体定义一个邻域结构,以实现种群之间的交流。

2)对每个子群体执行步骤3和4。

3)对子群体Pi执行SAGA算法。

(1)评价种群的适应度函数;

(2)判断终止条件,满足的话,记录最佳个体,算法停止,否则继续;

(3)对种群进行选择;

(4)对种群进行交叉;

(5)对种群进行变异;

(6)对种群中的每个个体用SA进行搜索;

(7)采用仿真退火算法产生新的个体;

(8)以一定的概率接受新个体;

(9)判断是否达到SA的稳定状态,是的话进行降温,转到(1),否则转到(7);

4)对在邻域结构中有连接的多个子处理器间进行最佳染色体的迁移,更新所有的子群体;

5)判断算法终止条件,如果满足,转到6,如果不满足,则转到2);

6)结束。

3 基于粗粒度模型的并行模拟退火遗传算法的优点

模拟退火遗传算法(SAGA)将遗传算法的全局搜索能力、内在并行性和模拟退火算法的强大的局部搜索能力有效的进行整合,在算法中两类方法互相嵌入,实现了双重准则下得搜索行为,从而弥补了单纯的遗传算法或模拟退火算法的缺点,获得了高效快速的搜索。此外,我们还给出了模拟退火遗传算法的一种粗颗粒多处理器并行实现方式,每个处理器中的SAGA是一个两层并行搜索结构。因此一方面,利用了双重准则的SAGA算法的搜索行为是可控的。另一方面,粗粒度的平行算法不仅能够提高搜索的效率,而且通过个体迁移和相邻的子群体交换最佳个体信息,从某种程度上也加快了算法的搜索速度。

参考文献

[1]Kusiak,A.(1990).Intelligent manufacturing systems.NewJersey:Prentice-Hall International Inc.

[2]Tami B,Michal P,Gideon W(2001).scheduling jobs withsome identical or similar job[J].Journal ofScheduling.4(4):177-199.

[3]Tavakkoli-Moghaddam,R.,Javadian,N.,Javadi,B.,&Safaei,N.(2007).Design of a facility layout problem in cellularmanufacturing systems with stochastic demands.AppliedMathematics and Computation,184(2):721–728.

[4]S.Koakutsu,and H.Hirata.(1992).Genetic Simulated Annea-ling for Floorplan Design,Chiba University,Japan.

上一篇:社会资本商务环境论文下一篇:岗、课、证