微型多目标遗传算法

微型多目标遗传算法（精选九篇）

微型多目标遗传算法 篇1

在实际工程设计中,经常遇到多目标优化问题(multi-objective optimization problem,MOP), 如汽车正面碰撞的结构优化设计中,轻量化与最大吸能为两目标优化问题,两者难以同时达到最优,只能获得 一组无法 进行简单 比较的Pareto解。多目标遗传算法可在无需考虑目标函数和约束函数满足连续性和可导性的条件下,对线性或者非线性目标函数进行有效求解,因而引起了众多学者的关注,并被广泛应用于求解实际工程问题[1,2,3]。Schaffer[4]1985年提出了 向量评估 遗传算法 (vector evaluated genetic algorithm,VEGA),用于解决机器学习的多目标问题。随后,一系列的多 目标遗传 算法被提 出和发展,其中以Deb等[5]的NSGA?Ⅱ (non-dominated sorting GA?Ⅱ)算法和Zitzler等[6]的SPEA2(strength Pareto EA2)算法应用最为广泛。在汽车碰撞安全性设计 中,谢然等[7]将NSGA?Ⅱ 算法用于40%的偏置正面碰撞中,在满足6σ 可靠性、扭转刚度和质量要求的约束条件下,提高了整车的碰撞安全性能。为提高计算效率,刘桂萍等[8,9,10]将微型遗传算法(micro genetic algorithm,μGA)[11]引入多目标优化问题中,提出了微型多目标遗传算法(micro multi-objective GA,μMOGA),该算法在计算效率、解的均匀性和工程实用性等方面具有较好的综合性能。Yang等[12]提出了基于网格支配的进化算法(grid-based evolutionary algorithm,GrEA),利用网格能同时反映收敛性和多样性的特点,使得个体 朝着Pareto最优解方 向迭代。

本文在微型多目标遗传算法μMOGA的基础上结合网格支配的概念,提出了一种具有网格属性的多 目标遗传 算法Gr- MOGA(μMOGA based on grid domination),与现有方法相比,该算法在求解较多目标函数问题时具有较好的收敛性和均匀性,并提高了计算效率。

1多目标优化相关概念

多目标优化广泛存在于实际工程中,其优化目标函数之间可能不一致甚至相互冲突,因此难以获得一个类似于单目标的最优解,而只能获得一组无法进行简单比较的Pareto最优解。一般的MOP被定义为[13]

式中,fk(x)、gi(x)和hj(x)分别为目标函数、不等式约束函数和等式约束函数;m、p和q分别为目标函数、不等式约束和等式 约束函数 的个数;x、xL和xU分别为优 化变量、优化变量的下界和上界。

Pareto最优解的 定义为[13]:设S⊆ Rn为MOP的可行域,f(x)∈Rm为MOP的目标空间, 若有且不存在x ∈S使得,则称为MOP的Pareto最优解。个体xPareto支配个体y(记为y)定义

2Gr-MOGA算法及构造

现有的多目标优化方法大都是针对二维目标函数问题,而对于较多目标函数问题通常难以获得较好的Pareto解。为此,本文构建一种新的基于网格支配的微型多目标遗传算法Gr- MOGA, 用于求解较多目标函数的一类实际工程多目标设计问题。网格支配在文献[12,14]被提出,通过该方法可保证较多目标函数下Pareto解集的计算精度;μMOGA算法由刘桂萍等[9]提出,通过小种群和重启动策略可有效保证多目标优化的计算效率。本文提出的Gr- MOGA算法在求解较多目标函数问题时,将兼具精度和效率的双重优点。

2.1网格的概念及相关参数定义

将各个个体划分在不同的网格内,从而通过网格值的大小决定个体是否继续进行遗传操作。 图1所示为进化种群P在第k个目标函数的网格值,种群P在第k个目标函数的最大值和最小值分别记为fkmax(P)和fkmin(P)。将第k个目标空间根据函数值划分成Dk个子空间,则第k个目标函数值的最小值和最大值bkL和bkU分别为

第k个目标函数的网格间距dk为

则个体x在第k个目标函数空间的网格值Gk(x) 为

其中,floor(·)表示最小取整函数,fk(x)为个体x在第k个目标函数的真实函数值。由式(2)知, 图1中5个个体在第k个目标函数下的网格值Gk(x)从左到右分别为0、1、3、3和4。

个体x在m个目标函数下的网格值之和为

根据个体网 格值,类似地定 义网格支配个体x在m个目标函数下的网格值之和为[12]为

个体x和y在m个目标函数下的网格值之差定义为网格差值,记为GD:

当个体y满足N(x)= {y|GD(x,y)< m} 时,则称个体y为个体x的邻居个体。个体x的网格拥挤距离dGC为

Gr值和dGC值能较好地度量解的收敛性和多样性,但当两者值相等时则无法区分个体,故引入网格坐标点距离,记为dGCP:

式中,dGCP为个体x在超方体中与理想点(超方体中所有目标函数值最小的点)的正则化欧拉距离。

通过Gr、dGC和dGCP值的比较与选择获得精英个体。以两目标函数为例,6个个体在网格中的Gr值和dGC值分别如图2所示。如个体C在网格中的Gr值和dGC值计算式为:Gr(C)=3+3=6, dGC(C)= (2-1)+ (2-1)=2。

2.2算法流程

以NSGA-算法和SPEA2算法为代表的多目标进化算法通常采用大种群计算,计算量大, 效率较低。Gr- MOGA算法采用小种群[9](5~8个个体)结合重启动策略,并基于网格支配进行迭代进化,能提高效率并满足解的收敛性要求,其计算流程如图3所示。

(1)在可行域空间产生5~8个个体形成初始种群P1。设外部种群Pe大小为N,外部种群出现相同的连续代数的次数记为iflag。

(2)网格支配分级。将外部种群Pe和进化种群Pt合并成Rt,将Rt进行网格支配分级(R1,…, Rm)。若Pe=R1,则iflag+1。

(3)当iflag大于设定值M(一般取值为2~9) 时,则采用重启动策略。重新在可行域空间中产生进化种群Pt,并加入Rt中进行网格支配分级,否则进行网格选择机制。

(4)网格选择机制。当|Pt+1|+|Ri|<N时,则将第Ri+1网格支配级根据Gr值、dGC值和dGCP值进行择优筛选 保存到外 部种群,Gr值越小越 优。当Gr值相等时,则根据dGC值选择,dGC值越小越优。当前两者值相等时,则选择dGCP值较小的。若三者值相等,则从中随机选择。若|Pt+1| +|Ri|= N,则直接将前i个网格非支配集加入到外部种群。

(5)当进化代数大于设定的n值时终止进化, 并输出外部种群个体,否则转(6)继续进化。

(6)遗传操作。选择外部种群的精英个体进行交叉、变异等操作,从而生成子代种群Pt+1,转 (2)进行迭代进化。

该算法采用小种群计算效率高的优点并结合重启动策略,避免了早熟收敛的特点,能有效地求解较多目标优化问题。

3测试函数及工程应用

3.1两目标测试函数

选择文献[15]中ZDT1函数和ZDT2函数作为测试函数进行分析:

ZDT1函数为

ZDT2函数为

变量个数n=30,变量xi∈[0,1],i=1,2,…, 30。在Gr- MOGA算法中,其参数设置为:初始种群P1为8,外部种群Pe为100,交叉概率Pc为0.95,变异概率Pm为0.1,外部种群出现相同次数M为3,每个目标空间划分成相等个数的子空间,取Dk为5。采用NSGA?Ⅱ算法作对比分析, 其初始种群P1为50,其余参数 设置与GrμMOGA相同,都采用单点交叉和位变异操作。

理论上,ZDT1函数的Pareto前沿面为,ZDT2函数Pareto前沿面为{(x1,1-x21)|x1∈[0,1]}。图4所示分别为采用NSGA?Ⅱ和Gr-μMOGA算法求解ZDT1和ZDT2函数获得的Pareto解,其中实线表示理论Pareto前沿面。两种算法整体上都能收敛到Pareto前沿面,但采用Gr- MOGA算法在图4a、图4c所示的矩形框内的解(图4b、图4d) 相比采用NSGA?Ⅱ方法相对应的Pareto解(图4a、图4c)分布得更 均匀。而且,Gr- MOGA算法采用小种群迭代,在保证解的均匀性的同时,其计算效率相比于NSGA?Ⅱ算法大约提高了2倍。

3.2三目标测试函数

采用文献 [16]中的DTLZ1函数和DTLZ2函数进行分析,DTLZ1函数为

DTLZ2函数为

式(9)和式(10)中的g(xm)分别为

DTLZ1函数中目 标函数个 数取为m = 3, k=|xm|=5,设计变量个数n= m+k-1=7;其DTLZ1函数的Pareto前沿面为。DTLZ2函数中目 标函数个 数取为m = 3, k=|xm|=10,变量个数n = m +k-1=12;DTLZ2函数的Pareto前沿面。同样使用NSGA?Ⅱ算法及本文提出的算法对上述两个问题进行分析求解,参数设置与前两个算例一致。图5所示分别 为采用NSGA?Ⅱ 和GrMOGA算法求解DTLZ1和DTLZ2函数获得的Pareto解。可以看出,两算法在整体上获得的Pareto解较好地分 布于目标 空间,但采用GrMOGA算法求解DTZL2函数时获得的Pareto解(图5d)相比采用NSGA?Ⅱ方法获得的解(图5c)分布得更均匀。而且,Gr- MOGA算法结合小种群的优点,在保证分布性较好的条件下,相比于NSGA?Ⅱ算法,其计算效率大约提高了2倍。

3.3制动器多目标优化设计

汽车盘式制动器相对鼓式制动器,具有散热能力强、结构简单以及较高的方向稳定性等优点, 被广泛用于现代汽车制动系统中。制动器在汽车制动过程中起着关键性作用,制动器质量、制动时间、制动圆盘半径等设计参数直接决定制动器的制动性能。制动器的啮合力越大,制动时间就越短,则需要更大的质量承受较大的啮合力,故制动器的啮合力、制动时间和总质量为多目标优化问题。本文引入文献[17]中的盘式制动器的优化问题,设计变量为制动器圆盘内径、外径、啮合力、摩擦接触面的个数,其多目标优化模型为

式中,f1(x)为制动器的质量,kg;f2(x)为制动器的制动时间,s;f3(x)为制动器的啮合力,N;x1为制动器圆盘的内半径,mm;x2为制动器圆盘的外半径,mm;x3为制动器的啮合力,N;x4为摩擦接触面的个数。

其几何约束g1(x)和g2(x)为

压力约束g3(x)为

温度约束g4(x)为

扭矩约束g5(x)为

边界约束如下:55mm≤x1≤80mm,75mm ≤ x2≤110mm,1000N ≤x3≤3000N,x4为[2, 20]之间的整数。

将Gr- MOGA算法用于求解制动器多目标优化问题,其Pareto最优解较好地分布于目标空间,如图6所示。表1给出了图6中的部分Pareto解。当设计者偏重于考虑制动器产生的制动力较小时 可以选择 解1。 解6的制动力 为2988.4N,制动时间为2.1s,质量为2.9kg,其制动时间最短,有利于汽车在紧急情况下快速制动。 最终,设计者可以根据不同的设计需求选择相应的Pareto最优解。

3.4汽车高速和低速耐撞性多目标优化设计

制动器具有较好的制动性,能有效地避免汽车发生碰撞。当碰撞无法避免时,其保险杠、防撞梁和吸能盒等相关部件应能最大限度地保护乘员和汽车,降低损伤成本。采用文献[18]中汽车高速和低速耐撞性多目标优化设计模型,其中选取保险杠厚度x1、吸能盒内板厚度x2、吸能盒外板厚度x3、前纵梁内板厚度x4和前纵梁外板厚度x5为优化设计变量,如图7所示。高速碰撞模型为汽车以56km/h的速度100% 正面刚性 壁障碰撞;低速碰撞 模型为RCAR (Research Council for Automobile Repairs)中的正面 偏置碰撞,如图8所示。选取汽车保险杠和前纵梁等部件的轻量化设计与碰撞中座椅点的加速度积分均值为多目标优化问题,其优化模型为[18]

式中,ā(x)为高速碰撞时后排左侧座椅点加速度积分均值,g;M(x)为保险杠、吸能盒和 前纵梁的 质量,kg;E(x) 为低速碰撞时前纵梁内外板吸收能量,J;Iup(x)、Idown(x) 为高速时发动机上 选择的两 点的侵入 量,mm;x = (x1, x2,x3,x4,x5)T,其变量单位都为mm。

式(11)中的目标函数和约束函数采用有限元模型计算得到,其有限元碰撞模型由755个部件、 998 220个节点、977 742个单元构 成。采用本文 的算法对汽车耐撞性优化模型进行计算,获得的Pareto最优前沿面如图9的边界点。加速度积 分均值ā最小可降低至28.82g,其对应的 设计变量 值分别为 (3.00,2.50,2.50,2. 99,1.79)mm;设计变量的总质量最小值为6.82kg,但对应的 加速度积分均值为46.05g,前纵梁等发生了较严重的变形。解5的加速度积分均值为36.43g,总质量为10.28kg,对应的设计变量分别为(2.14,1. 52,2.48,2.76,1.50)mm,其解较好地平衡了总质量和汽车碰撞时的加速度值。最终工程师可根据Pareto最优解结合工程经验和偏好信息,选择某一组解作为最终妥协解。

4结语

微型多目标遗传算法 篇2

笔者以捷达轿车后悬减振器结构和性能要求为基本设计条件，提出了一种基于遗传算法的非线性约束多目标优化设计方法，制造出MR减振器样品，进行了试验研究。

1设计目标

当MR减振器装入实车时，从减振性能考虑，希望其提供的阻尼力能够满足各种工况，阻尼力的可调范围越大越好;从可控性能考虑，则希望MR减振器的反应时间越小越好，这样才能保证半主动控制策略有效的工作;而从节能和稳定性考虑，又希望其能耗最小，减少线圈发热，从而保证MRF工作稳定。同时满足上述性能的减振器只是一种理想减振器，而事实上各种性能指标会相互制约，而制约的途径就是MR减振器的结构参数。因此，为了设计出能够令人满意的减振器，就必须综合考虑各目标，并作出适当的折衷。

2设计方案

以一汽大众生产的捷达系列轿车后悬减振器为参考对象，设计MR减振器的活塞结构简图。

MRF须选择零场粘度低、饱和屈服应力高、工作温度范围宽、密度小以及可压缩性小的材料。

由于MRF在温度升高时粘度会降低，影响其正常工作。因此从散热方面考虑，采用单缸结构减振器;为补偿在拉压行程中由活塞两端有效作用面积不等造成的体积差，采用蓄气室充气结构。

使MRF工作在压力驱动模式下，活塞设计为套筒式结构，则工作缸可选用强度较好的材料而不必考虑磁导;为减小漏磁，则选用矫顽力小的软磁材料作活塞;活塞套筒与铁芯在对称的4个点上焊起来;焊点要尽可能小，以保证缝隙内磁场尽可能大。

磁芯填充材料的选择非常重要，要求其具有良好的耐热耐冲击耐腐蚀耐磨损性能，并且要有良好的抗磁性和绝缘性。

线圈导线的选择应尽可能选择内阻小、耐热及耐压性能高的铜漆包线。

3优化设计

3.1设计条件

(1)根据设计方案确定所设计MR减振器结构为单筒式，上安装型式为外螺纹，下安装型式为吊环。

(2)根据捷达轿车后减振器的外型尺寸和布置尺寸确定所设计的MR减振器外型尺寸(包括工作缸内外径D，活塞杆半径Rrod等)和活塞行程S。

(3)采用美国Lord公司产MRF-132LD型磁流变液。根据MRF饱和磁感应强度确定所设计减振器的工作点Bfwork、Hfwork及其对应屈服应力τ，确定其在工作温度和大剪切率下的零场粘度η。

(4)采用DT4A电工纯铁作为活塞铁芯及活塞套筒材料。可以得到铁芯的饱和磁感应强度Bsmax和饱和磁场强度Hsmax。

(5)考虑线圈内阻及绕线等因素，选定铜漆包线型号，确定其标称直径dc和外皮直径do，并结合其安全载流量，设定最大工作电流Imax=1.2A;

(6)确定MR减振器在一定振幅A和频率f的正弦激励下活塞的最大速度Vmax。

3.2适应度函数

适应度函数是评价个体优劣的标准，是群体进化过程的依据。考虑到实际中对各性能侧重程度的不同，采用规格化线性加权将4个目标函数转化为适应度函数M(X)。

3.3优化变量

MR减振器结构设计的独立变量为:环形缝隙径向高度h，活塞套筒内半径R2，活塞环槽内半径R3，有效流通区域长度L和非磁极缝隙长度Lo(而线圈匝数N可以通过其他参数求出，这将在第3.7节中讨论)

3.4约束函数

MR减振器设计的约束条件有线性约束和非线性约束。线性约束一般可表示为A·X=B，其中X呶设计变量向量。非线性约束主要是由MRF以及磁路的非线性导致。

3.5设定遗传算子

MR减振器的多目标设计是借助于Matlab7.5的遗传算法工具箱来完成的。

设定种群类型是双精度向量，种群尺度为100，初始种群的范围是(10-5，1)。

选择参数是在群体中选择生命力强的个体产生新的群体的过程。这里采用剩余选择算子，按照每个个体刻度值的整数部分分配其作为双亲，并随后在剩余的小数部分采用轮盘赌选择方法。

再生参数说明了遗传算法怎样为下一代创建子个体，其中幸存个体数指定将生存到下一代的个体数，这里设置为10。

变异参数说明遗传算法怎样通过小的随机数改变种群中的个体而创建变异的子代。由于存在非线性约束函数，变异函数选为自适应函数，它根据父辈个体的尺度值随机产生个体基因的变异方向和变异量，同时将基因的变异量限定在遗传算法设置范围之内。

交叉参数是模仿生物界自然进化过程，通过将两个同源染色体进行部分基因的交换而重组，产生两个新的染色体。这里采用算术交叉，由双亲的随机算术平均值产生子代，并位于父母间并与其等距的直线上;设定交叉概率为0.8。

3.6实例优化

设定算法收敛条件是300代，得到优化结果。可以看到，经过295代的进化，适应度函数最终收敛于一个最优值Fitnessvalue=1.3086×10-6，而平均适应度与最佳适应度差别较大，这是因为非线性约束条件的存在，在进行交叉变异之后的新个体并不一定满足约束，就需要产生新个体，因此子代个体就比较离散，也就很难趋于同一基因型。

3.7线圈匝数的确定

由第3.3节所确定的优化变量，可以计算得到线圈匝数最小值为286。由于励磁电流和线圈匝数对磁路性能的影响很大，因此对相同最大工作点、不同匝数下的MR减振器性能进行评价。

可知，由于磁路非线性的存在，铁芯线圈的时间常数并非恒值，而是随着电流增大而呈双曲线减小，因此在低电流低输出情况下，系统响应会较慢;随着电流增大，铁芯线圈的功耗呈抛物线增大;当线圈匝数N增大时，对应相同MRF工作点磁感应强度下的最大工作电流减小，工作区域的时间常数增大，而最大功耗减小。最终确定线圈匝数N取300匝。此时验算所设计的MR减振器在2Hz激励，1.2A工作电流下可以达到的性能。

4试验研究

根据第2节得到的结构参数，根据捷达轿车后悬架内减振器的安装尺寸(最长行程650±3mm，最短行程445±3mm，总行程205mm等)，设计并试制了MR减振器样品。其中，充入氮气压力为2MPa，使用MRF体积为120mL，实测摩擦力约40N。

采用清华汽车工程开发研究院与北京华谷减振设备有限公司联合开发的减振器综合性能试验台对试制的MR减振器进行台架试验。试验环境温度20℃，正弦激励振幅±30mm，激振频率分别为0.5Hz、1Hz、1.5Hz、2Hz、2.5Hz和3Hz(对应最高速度分别为0.094m/s、0.189m/s、0.283m/s、0.377m/s、0.471m/s和0.566m/s)，励磁电流分别为0、0.2A、0.4A、0.6A、0.8A、1.0A和1.2A，测得MR减振器在不同电流下的示功值。以2Hz时为例，将各电流下的试验数据减去由充气压力导致的偏置力。

可以看到，不管哪个激振频率下，当励磁电流增大到1.0A以后，减振器阻尼力增长缓慢，这是因为此时磁路已经接近饱和;亦可以看到理论曲线比实测曲线要显得更方一些，这主要是因为理论模型中未考虑MRF的滞环、剪切稀化现象及充气压力滞环等因素;而图中零场(I=0)的实测阻尼力均大于理论值，则主要跟活塞流通缝隙的实际加工误差、摩擦力及活塞组件惯性力等因素有关;随着电流加大，实测阻尼力与理论值逐渐吻合，这是因为随可控阻尼力增大，粘性阻尼力和摩擦力所占比例逐渐减小。当电流I>0.6A，在激振频率f<2.5Hz时，实测值均低于理论值，这主要与减振器温升引起阻尼力衰减有关;但当激振频率大于2.5Hz时，可以发现试验曲线高于仿真曲线，这是因为随激振频率增高，惯性力带来的影响逐渐明显。还可以看到，在设计频率2Hz时，励磁电流1.2A下实测最大阻尼力可以达到1454N，达到目标值;而动态范围只达到了3.86，这是因为摩擦力和温升导致MR减振器工作效能降低。总体来说，理论曲线能够与试验曲线较好的吻合。

5结论

(1)笔者综合考虑了MR减振器实际应用中影响可控性能的多个设计要素，结合Bingham流体模型和电磁理论，提出了基于遗传算法的非线性约束多目标优化设计方法，并运用到实例设计MR减振器过程中。经过实例设计证明该方法能够比传统设计方法更快的获得满足设计目标的尺寸参数。

微型多目标遗传算法 篇3

关键词:量子遗传算法;多目标分配;最优化

中图分类号:TP18 文献标识码:A 文章编号:1674-7712 (2012) 12-0176-01

一、引言

遗传算法不同于传统寻优算法的特点在于:遗传算法在寻优过程中,仅需要得到适应度函数的值作为寻优的依据;同时使用概率性的变换规则,而不是确定性的变换规则;遗传算法适应度函数的计算相对于寻优过程是独立的;算法面对的是参数的编码集合,而并非参数集合本身,通用性强。它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。[1]

目前,GA已经在很多领域得到成功应用,但随着问题规模的不断扩大和搜索空间的更加复杂,GA在求解很多具体问题时往往并不能表现出其优越性。于是,近年来便出现了遗传算法与其它理论相结合的实践,其中遗传算法与量子理论的结合是一个崭新的、极富前景和创意的尝试。

量子遗传算法QGA是量子计算特性与遗传算法相结合的产物。基于量子比特的叠加性和相干性,在遗传算法中借鉴量子比特的概念,引入了量子比特染色体。由于量子比特染色体能够表征叠加态,比传统GA具有更好的种群多样性,同时QGA也会具有更好的收敛性,因此在求解优化问题时,QGA在收敛速度、寻优能力方面比GA都将有较大的提高。QGA的出现结合了量子计算和遗传算法各自的优势,具有很高的理论价值和发展潜力。

本论文提出用量子遗传算法处理和解决多目标分配问题,为多目标问题的解决提供一种新的思路。

二、量子遗传算法

在传统计算机中,信息存储是以二进制来表示,不是“0”就是“1”态,但是在量子计算机中,充当信息存储单元的物质是一个双态量子系统,称为量子比特(qubit),量子比特与比特不同之就在于它可以同时处在两个量子态的叠加态,量子进化算法建立在量子的态矢量表述基础上,将量子比几率幅表示应用于染色体的编码,使得一条染色体可以表示个态的叠加,并利用量子旋转门更新染色体,从而使个体进达到优化目标的目的。

一个 位的量子位染色体就是一个量子位串,其表示如下:

其中 。在多目标优化中,一个量子染色体代表一个决策向量,在量子态中一个 位的量子染色体可以表达 个态,采用这种编码方式使得一个染色体可以同时表达多个态的叠加,使得量子进化算法比传统遗传算法拥有更好的多样性特征。

为了实现个体的进化,经典进化算法中通过染色体的交叉、变异操作推进种群的演化,而对量子进化算法而言,量子染色体的调整主要是通过量子旋转门实现的,算法流程如下:

(1)进化代数初始化: ;

(2)初始化种群 ,生成并评价 ;

(3)保存 中的最优解 ;

(4) ;

(5)由 生成 ;

(6)个体交叉、变异等操作,生成新的 (此步可省评价);

(7)评价 ,得到当前代的最优解 ;

(8)比较 与 得到量子概率门 ,保存最优解于 ;

(9)停机条件 当满足停机条件时,输出当前最优个体,算法结束,否则继续;

(10)以 更新 ,转到4)。

三、基于量子遗传算法的多目标分配应用

如今为了满足市场的需要,很多工厂的生产种类多、生产量大,从而设置了不同的生产车间,根据产品的性质分配生产车间合理与否直接影响工厂的经济收益,这同样可采用遗传算法的目标分配方法进行分配。

模型构建:设工厂有i个生产车间。 为在第i个车间生产第j种产品的收益, 为第j种产品的需求量;如果第j种产品被选中,则 为在第i个车间生产该产品的总收益。由题意知为求解 最大问题。

仿真实例:设有10个生产车间,要生产15种产品,用Matlab程序编程,设定40个粒子,迭代200次,代沟0.9。运行结果如下:

此图表明经200次迭代后的目标分配方案为:第1种产品由第3个车间生产,以此类推,车间5生产第2种产品,车间8生产第3种产品,……。次方案对应的车间总收益值为2.7030e+003,成功进行了多目标分配问题的解决。

四、结论

基于量子遗传算法的多目标分配,为多目标分配突破传统寻优模式找到了一个可行的解决方法。根据这种方法实验,仿真结果可以看出,基本符合要求,并且能够在一定的时间内得到最优的分配方案,因此,本文在探索多目标分配问题上找到了一种新的解决思路。

参考文献:

[1]吉根林.遗传算法研究综述[J].计算机应用与软件,2004,21(2):69-73

[2]肖晓伟,肖迪.多目标优化问题的研究概述[J].计算机应用研究,2011,3,28(3):805-808

[3]原银忠,韩传久.用遗传算法实现防空导弹体系的目标分配[J].火力与指挥控制,2008,3,33(3):80-83

[4]郭张龙,李为民,王刚.基于遗传算法的目标分配问题的研究[J].现代防御技术,2002,6:0172-0180

[5]孙祥,徐流美.matlab7.0基础教程[M].北京:清华大学出版社,2005

基于遗传算法的网络计划多目标优化 篇4

关键词：网络计划,多目标优化,遗传算法

0 引言

网络计划技术作为一种科学的管理方法, 现今已被广泛应用于工程建设各个领域, 且在企业管理、科学研究和国民经济建设中发挥着越来越大的作用。

在工程建设领域, 如何在保证安全的前提下, 能够实现成本最低、工期最短、资源使用最均衡、质量最优, 是学者近年研究的热点。多数情况下, 这些目标不可能同时实现, 某一个子目标的改善就会导致其他子目标的恶化, 故只能对各个子目标进行综合考虑, 使总目标达到最优。

1 遗传算法简介

遗传算法是以达尔文的生物进化论和孟德尔的遗传学说为基础的一种模拟自然选择和遗传机制的寻优方法。基因突变或基因杂交都有可能生成适应环境能力强的后代, 经过自然界优胜劣汰的选择, 适应环境能力强的基因就逐渐保存下来。遗传算法就是引用随机统计原理, 并模仿生物的遗传、进化原理形成的。[1,2]遗传算法的基本求解步骤流程图如图1所示。

2 网络计划多目标优化方法

解决多目标优化问题通常选用层次分析法, ε约束法, 目标规划法, 逐步法, 多目标加权法等, 这些算法的原理都是将多目标转化为单目标处理。[3]本文选择的是多目标加权法, 根据各子目标的重要程度, 相应地赋予权值, 再相加构成新的目标函数, 在原多目标优化问题约束集的基础上对此新的目标函数求最优解。如子目标函数量纲不同, 在求解前需对目标函数预先处理, 再加权求和, 将多目标转化成单目标优化问题, 对应变量的取值就是所求多目标优化问题的近似最优解。

3 实例分析

某工程网络计划图如图2所示, 已知资料列于表1中, 其中包含了工程在正常时间及极限时间下完成各工序的费用和质量相对值。如果提前一天完工, 奖励500元, 间接费为500/天。运用遗传算法对其进行工期-净收益-质量多目标优化。

工期-净收益-质量的多目标模型如下:

上式中, IN———项目的净收益;ti———活动i的实际持续时间;T———实际实现的工期;T+———正常工期;tbi———活动i的最早开始时间;n———网络计划共有的活动数目;TiU———活动i的正常持续时间;TiL———活动i的极限持续时间。

为对各个子目标函数统一量纲, 不受目标值大小的影响, 引入IN′———净收益单目标的最大值。优化步骤:

(1) 确定初始网络计划中各个参数, 包括工期、提前完工单位时间的奖励、各工序持续时间、可压缩时间范围、费率、压缩费用、间接费用、关系矩阵等。建立模型后, 确定多目标适应度函数。

(2) 应用遗传算法进行计算。首先以数组的形式表现网络计划中各个工序持续时间的压缩时间, 生成初始群体。按照遗传算法进行参数的优化设计计算, 得到目标函数值及其对应的各个工序的持续时间和工期。在计算过程中, 运用拒绝算子使得计算过程中的个体均为合法个体。满足终止条件之后, 则结束计算并输出结果。

由表1求出各工序的最大压缩时间、单位时间压缩费用 (费率) 和压缩的工序质量的数学模型, 见表2。

(3) 优化结果分析。利用线性加权和的形式处理此多目标问题, 决策者可根据具体情况确定两个目标的权值大小, 这里取质量和净收益的权值分别为0.4和0.6。采用遗传算法对网络计划多目标进行优化, 运行10次, 最好的一次运行结果见表3。

4 结论

由于目前网络的静态性和工程的复杂性, 编制一项能够达到工期最短、费用最低、资源使用最均衡、质量最优的工程网络计划是不可能实现的。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局概率搜索算法, 全局寻优能力较强, 是一种有效的解决问题的方法。本文将遗传算法用于网络计划的多目标优化问题中, 使得多个目标尽量达到最优, 得到较满意的结果。

参考文献

[1]骆刚, 刘尔烈, 王健.遗传算法在网络计划资源优化中的应用[J].天津大学学报, 2004, 37 (2) :179-183.

[2]张连营, 张金平, 王亮.工程项目资源均衡的遗传算法及其MATLAB实现[J].管理工程学报, 2004, 1:52-55.

[3]李万庆, 孟文清, 等.工程网络计划技术[M].北京:科学出版社, 2009.

微型多目标遗传算法 篇5

一般来说,科学研究与工程实践中许多优化问题大多是多目标优化问题。多目标优化问题中各个目标之间通过决策变量相互制约,因此很难客观地评价多目标问题解的优劣性。1989年Goldberg在其著作中,提出了用遗传算法实现多目标的优化技术,使多目标遗传算法的研究出现了重大转折。近年来,多目标遗传算法引起了许多学者的关注,并涌现出了不少有价值的研究成果。

多亲遗传算法是对传统遗传算法的交叉算子进行了改进,使得新产生的个体能继承多个母体的有效基因,新个体很可能会有更高的适应度函数值,这样能加快算法的收敛速度。本文参考快速排序的思想,给出了一种有效的构造非支配集的算法,最后将多亲遗传算法与多目标优化算法结合起来,给出了一种基于多亲遗传机制的多目标优化算法。

1 多目标问题的描述

给定决策向量X=[x1,x2,…,xn]T,它满足下列约束:

gi(x)≥0 i=1,2,…,p (1)

hi(x)=0 i=1,2,…,q (2)

设有m个优化目标,且这m个优化目标很可能是相互冲突的,总的优化目标可表示为:

f(x)=[f1(x),f2(x),…,fm(x)]T (3)

寻求x*=[x1*,x2*,…,xn*]T,使f(x*)在满足约束条件(1)和(2)下达到最优。

2 基于多亲遗传机制的多目标优化算法

2.1 个体之间的关系

定义1 设X和Y是Pop中的任意两个个体,称X支配Y,则必须满足下列两个条件:

(1) 对所有的子目标,X不比Y差,即fk(Y)≥fk(X),k=1,2,…,r,其中r为子目标的数量。

(2) 至少存在一个子目标,使X比Y好,即∃t∈(1,2,…,r),使得fk(Y)ϕfk(X)。

此时称X为非支配的,Y为被支配的,表示为XϕY,其中ϕ是支配关系。

定义2 ∀X,Y∈Pop,X和Y相关,iff XϕY OR XπY OR X=Y,否则称X和Y不相关。

据定义2有:非支配集中的不同个体之间是彼此不相关的。

2.2 非支配集的构造

构造非支配集是多目标遗传算法(Multi-Objective Genetic Algorithm,MOGA)一个重要的组成部分,它是MOGA保留优秀个体的一种机制,是确保算法收敛于Pareto最优面的一种策略,直接影响MOGA的效率,近年来有不少构造非支配集的算法。这里通过参考快速排序的思想,提出了一种有效的构造非支配集的算法。

算法1 基于快速排序构造非支配集KQS[2,7]:

设集合P的大小为n,子目标的数目为r。

算法2 改进的快速排序构造非支配集:

该算法首先采用快速排序法构造非支配集,当(t+1)代种群Pt+1的大小比种群个数N要小,则随机从(Rt-Pt+1)中选择(N-|Pt+1|)个个体填满Pt+1,当非支配集Pt+1个数大于N时,就对非支配集进行密度集排序,选择前面N个个体构成新的Pt+1,具体算法如下:

其中,密集度定义为:

设群体pop={x1,x2,…,xn}中的个体xi=[x${}_{\text{i}}^{(1)}$,x${}_{\text{i}}^{(2)}$,…,x${}_{\text{i}}^{(\text{l})}$],xj=[x${}_{\text{j}}^{(1)}$,x${}_{\text{j}}^{(2)}$,…,x${}_{\text{j}}^{(\text{L})}$],则个体xi和个体xj之间的相似程度为:

$A{}_{ij}=\frac{1}{L}{\displaystyle \sum _{k=1}^{L}C}{}_k$x${}_i^{(k)}$-x${}_j^{(k)}$i,j∈{1,2,…,n}

其中Ck为对应于基因座k的常数因子。

定义个体P的密集度为与个体P相似的个体在群体中所占比重即:

Crowds(p)=与个体P相似度大于γ的个体总数/n

一般取值为γ∈[0.9,1],设集合P的大小为n,子目标的数目为r。

2.3 基于多亲遗传机制的多目标优化算法

多亲遗传算法对传统遗传算法中的交叉算子作了改进,在大部分单目标问题中表现出了良好的性能,在一定程度上能保持群体的多样性、克服“早熟收敛”问题以及加快收敛速度[4,5,6]。本文将多亲遗传算法与上面所提出的非支配集构造方法相结合,提出了基于多亲遗传机制的多目标优化算法MOGAMC。算法描述如下:

3 算法的性能分析

由快速排序的算法复杂度可知,该算法的时间复杂度接近O(r*n*logn)[2,7],故本文所提出的算法中构造非支配集的方法比文献[1]的O(r*n2)要好。

本文还采用了两个常用的多目标测试函数来测试算法的性能,将实验结果与由Deb提出的算法NSGA2(Non-dominated Sorting GA2)作比较[1],NSGA2采用排序的方法来构造非支配集。

函数1:

$EC6\{\begin{array}{l}f{}_1(x)=1-\exp (-4*x{}_1)\sin {}^6(6\pi x{}_1)\\ f{}_2(x)=g\left(1-\left(\frac{f{}_1}{g}\right){}^2\right)\end{array}0\le x{}_i\le 1,i=1,\cdots ,10$

$\text{w}\text{h}\text{e}\text{r}\text{e}g(x)=1+9\left({\displaystyle \sum _{i=2}^{10}\left(\frac{x{}_i}{9}\right)}\right){}^{0.25}$

函数2:

${\rm O}SY\{\begin{array}{l}f{}_1(x)=-(25(x{}_1-2){}^2+(x{}_2-2){}^2+(x{}_3-1){}^2+(x{}_4-4){}^2+(x{}_5-1){}^2)\\ f{}_2(x)=x{}_1^2+x{}_2^2+x{}_3^2+x{}_4^2+x{}_5^2+x{}_6^2\\ \text{s}\text{u}\text{b}\text{j}\text{e}\text{c}\text{t}\text{t}\text{o}\\ c{}_1(x)=x{}_1+x{}_2-2\ge 0\\ c{}_2(x)=6-x{}_1-x{}_2\ge 0\\ c{}_3(x)=2-x{}_2+x{}_1\ge 0\\ c{}_4(x)=2-x{}_1+3x{}_2\ge 0\\ c{}_5(x)=4-(x{}_3-3){}^2-x{}_4\ge 0\\ c{}_6(x)=(x{}_5-3){}^2+x{}_6-4\ge 0\\ 0\le x{}_1‚x{}_2‚x{}_6\le 10‚1\le x{}_3‚x{}_5\le 5‚0\le x{}_4\le 6\end{array}$

以上列出的两个测试函数都是求极小值的多目标函数,实验中,NSGA2和MOGAMC都是采用二进制编码,翻转变异。Popsize为100,Maxgen为500,交叉概率为0.8,变异概率为1/len(len为基因的长度)。在NSGA2中,采用单点交叉,而在MOGAMC中,采用多亲交叉中的扫描交叉(实验中为四亲)。测试结果为10次运行的最优值。实验结果如图1,图2所示,计算时间如表1所示。

上述两个图给出了NSGA2和MOGAMC两个算法在运行了500代以后所能找到的Pareto解集,从图1、2可以看出,在两个算法运行相同代数的情况下,在两个测试函数中,MOGAMC找到的解集比NSGA2找到的解集要更接近最优面,MOGAMC比NSGA2有更强的求解能力。从表1可以看出,MOGAMC与NSGA2相比,由于在每一代中,只求其NDS集,而舍弃DS集,采用了快速排序的思想,所以MOGAMC在运行相同代数的情况下,不但找到的解集比NSGA2要好,而且从效率上也要快得多。

4 结束语

本文参考快速排序的思想,提出了一种有效的构造非支配集的算法,将多亲遗传算法与改进的快速排序构造非支配集的算法相结合,提出了一种基于多亲遗传机制的多目标优化算法。最后,采用了测试函数对本文提出的算法进行了测试,并获得了理想的实验结果,这说明本文所讨论的方法与其它已有的方法相比具有一定的有效性和先进性。

参考文献

[1]Kalyanmoy Deb,Amrit Pratap,Sameer Agrawal,et al.AFast and ElitistMulti-objective Genetic Algorithm:NSGA-II[J].IEEE Transactions onEvolutionary Computation,2002,6(2):182-197.

[2]Zheng Jinhua,Charles X Ling,Shi Zhongzhi,Xie Yong.Some Discus-sions about MOGAs:Individual Relations,Non-dominated Set,and Ap-plication on Automatic Negotiation[A].Congress on Evolutionary Com-putation[C],2004.

[3]Corne D W,Jerran N R,Knowles,Oates MJ.PESA-:Region-based se-lection in evolutionary multibojective optimizition[A].Proceedings ofthe Genetic and Evolutionary Computation Conference(GECCO-2001)[C].Morgan Kaufmann Publishers,2001:283-290.

[4]Schippers C A.Multi-Parent Scanning Crossover and Genetic Drift.A.E.Eiben.Multiparent Recombination in evolutionary computing[J].InGhosh A,Tsutsui S,editors.Advances in Evolutionary Computing,Nat-ural Computing Series,Springer,2002:175-192.

[5]Tsutsui S,Yamamura M,Higuchi T.Multi-parent recombination withsimplex crossover in real-coded genetic algorithms[C].Proc.of theGECCO-99,1999:657-664.

[6]Schippers C A.Multi-Parent Scanning Crossover and Genetic Drift[M].Theoretical Aspects of Evolutionary Computing,Berlin:Springer,2001:307-330.

[7]唐欢容,郑金华,蒋浩.用基于快速排序的MOGA求解MOKP[J].湘潭大学:自然科学学报,2004,26(1):39-42.

微型多目标遗传算法 篇6

带有复杂约束条件的多目标优化问题与实际生活联系紧密, 为众多学者所重视。遗传算法因为采用种群策略, 一下能找到多个Pareto最优解, 是解决多目标优化问题的有效方法。历史上比较经典的算法有:David Schaffer提出的VEGA, Horn和Nafpliotis提出的NPGA。Fonseca和Fleming提出的FFGA, Srinivas和Dab提出的NSGA, Zitzler和Thiele提出的SPEA。解决多目标问题的关键在于妥善处理约束条件。目前, 进化算法用于无约束优化问题的文献居多, 而用于约束优化问题的研究相对较少。对于约束优化问题的处理方法基本上分为两类:基于罚函数的约束处理技术和基于多目标优化技术的约束处理技术。由于罚函数法在使用中不需要约束函数和目标函数的解析性质, 因此经常被应用于约束优化问题, 但该类方法对罚因子有很强的依赖性, 需要根据具体问题平衡罚函数与目标函数, 为了避免复杂罚函数的构造, Verdegay将进化算法中的竞争选择用于约束处理, 并在比较两个解的性能时提出了3个准则。基本多目标优化遗传算法并未限制相同个体或类似个体的数量, 使得群体内各个个体分散程度低, 因而易于生成很多个相似的Pareto最优解, 而难于生成分布较广的Pareto最优解。基于此考虑, 本文拟给出一种基于群体分类的复杂约束多目标遗传算法。

1 多目标优化问题概述

定义1 (约束条件多目标优化问题Constrained Optimization Problem, COP) 约束条件多目标优化问题可描述为下列数学模型:

式中, f (x) 为目标向量, hi (x) , gj (x) 称为约束条件, x= (x1, x2, ..., xn) ∈Rn称为n维决策向量。将满足所有约束条件的解空间S称为 (1) 式的可行域, min表示向量极小化, 即向量目标 (x) =[f1 (x) , f2 (x) , ..., fp (x) ]T在某种约束条件下各个子目标函数都尽可能地极小化。特别是, 当p=1时, 式 (1) 为单目标优化问题, 当p>1时, 式 (1) 为多目标优化问题, 当hi (x) , gj (x) 为线性或非线性函数时, 式 (1) 为带有复杂约束条件的多目标优化问题, 本文主要讨论带有复杂约束条件的多目标优化的问题。

因为对于等式约束hi (x) =0可通过容许误差 (也称容忍度) ε>0将它转换成两个等式约束。

故可仅考虑不等式约束优化问题。

在COP的优化过程中, 各目标往往是相互冲突的, 一个能满足所有约束条件, 并且能够使所有的目标函数达到全局最优的解, 很可能并不存在。所以在定义COP的解集时, Pareto最优解是一个关键概念。

定义2 (Pareto最优解) 解X*= (x1*, x2*, ..., xn*) ∈S是COP的Pareto最优解, 当且仅当不存在y∈S, 使得v軆=f (y) 优于u軋=f (x*) , 即坌i∈{1, ..., p}, 满足ui≤vi, 并且埚i∈{1, ..., p}使得ui刍vi。

2 带复杂约束条件的多目标问题的处理方法

对于解决带复杂约束条件的多目标优化问题, 核心之一就是如何处理约束条件。一般处理约束条件有如下几种方法:

2.1 惩罚函数法

惩罚函数法是处理约束条件最常用的手段。这种方法在生成个体时并不考虑约束条件, 而是在适应函数f (p) 上添加一个惩罚项, 称为惩罚函数, 新适应值函数为:

其中m代表约束条件数目, Φi代表关于第i个约束条件的惩罚项, 为一常数, 称为惩罚因子。若个体所表示的解不满足约束条件, 则惩罚项产生一个负值, 使得个体的适应度降低。这样, 通过建立惩罚函数, 就将原来的约束问题变成了无约束问题, 同时不改变原问题的最优解。

2.2 解码器法和修补法

解码器法通过使用特殊的编码方法来避免产生“非法”个体, 修补法则对“非法”个体进行修正来使之满足约束条件。这两种方法可用于解决约束条件很强的问题, 具有较高的效率, 但并不是所有的约束问题都能够使用这两种方法进行求解。

2.3 算子修正法

算子修正法通过设计专门的遗传算子, 以保证合法个体产生的后代仍然是合法个体, 即这些遗传算子对于可行解空间是封闭的。这样可能导致收敛到局部最优。

以上方法一般都能找到带约束条件的多目标问题的解, 也具有较高的效率。但不可避免存在不足, 比如不能找到分布广泛, 均匀的Pareto最优解。本文给出的方法在一定程度上解决了这个问题。

3 基于群体分类的复杂多目标遗传算法

3.1 将种群分成可行与不可行两类

在遗传算法中, 当种群较大时, 向量的维数是较大的, 向量的比较是麻烦且耗时的, 所以我们可以使用向量范数来度量向量的长度, 将向量的比较转化为向量长度的比较, 采用这种方法不仅行之有效, 而且能大大提高算法的效率。

记约束条件为:

令

ci (x) =max (Gi (x) , 0) i=1, 2, ..., N

得向量

C (x) = (c1 (x) , c2 (x) , ..., cN (x) ) T

令

从这一公式中可以看出, Di0x 0其实反映了每一个体距离可行空间的长度:Di0x 0=0则该个体位于可行空间内, 为一可行解;Di0x 0=Dj0x 0则表示这两个个体具有距离可行空间的相同的长度;而0刍Di0x 0刍Dj0x 0则表示虽然Di0x 0和Dj0x 0为不可行解, 但同i个体相比, j个体距离可行空间较近, 也即j个体优于i个体。这里称D 0x 0为D适应度, 利用D适应度一方面可以实现搜索空间到可行空间的映射, 另一方面可以将整个群体划分为可行群体和不可行群体, 更为重要的是可以将D适应度作为遗传算法的适应度, 通过选择、交叉与变异从而生成大量的可行个体。

图1中D1为可行解, D2和D3虽然是不行解, 但D2优于D3。

这样复杂约束条件多目标优化遗传算法的解可分为不可行解和可行解, 其中不可行解个体集合构成不可行群体, 可行解个体集合构成可行群体。对于一些高度受限的优化问题, 在前几代很可能没有产生或者产生少量的可行解, 如果这时对可行解集合施以Pareto运算以及聚类分析运算, 一方面会降低算法的效率, 另一方面也没有太大的实际意义, 所以本算法的第一步就是要生成大量的可行解, 这时我们使用D适应度作为算法的适应度, 经过选择、交叉、变异操作, 在前几代产生尽可能多的可行解个体, 为后面的Pareto运算打下基础。

3.2 将可行群体划分为可行非Pareto群体与可行Pareto群体

由Pareto最优解定义可知, 如果一个多目标优化问题存在最优解, 那么这个解一定是Pareto最优解, 所以求解多目标优化问题的关键就是求出其所有的Pareto最优解。由于遗传算法是对整个群体所进行的进化运算操作, 它着眼于个体的集合, 而多目标优化问题的Pareto最优解一般也是一个集合, 因此使用遗传算法来求解多目标优化问题的Pareto最优解集合是一种行之有效的手段。在本算法中, 当可行解个体的数量足够多时, 就可以对其进行Pareto运算, 找出所有的Pareto最优解, 从而将可行群体分成可行非Pareto群体与可行Pareto群体。

3.3 将可行Pareto群体划分为聚类Pareto群体与聚类Pare-to最优群体

k-均值聚类。由于遗传算法对相同个体或类似个体的数量并不限制, 于是在可行Pareto群体中可能会出现大量相同或类似的个体, 特别是在算法的后期阶段可行Pareto个体已非常多的情况下, 所以有必要对它们的数量加以限制, 以便能够生成种类较为丰富的不同的Pareto最优解。又, 遗传算法的概率搜索特性与聚类分析的分类结果的不确定性相统一, 本算法使用k-均值聚类分析来实现群体的多样化, 其具体步骤如下:

(1) 在Popsize个个体组成的群体中, 计算各个个体的目标函数值, 依据各个个体的目标函数值随机选择q个个体, 产生q个中心 (q

(2) 在剩余的Popsize-q个体中取出一个个体, 计算它到q个中心的距离, 将其分配到最近的一个中心;

(3) 计算此中心的重心, 作为新的重心;

(4) 依次类推, 直到第Popsize-q个体分配完毕, 于是产生q个聚类群体。

在本算法中, 对可行Pareto群体进行聚类分析运算, 生成了q个聚类群体, 在每一个聚类群体中随机挑选一个个体, 将它们合并为一个群体, 我们称这个群体为聚类Pareto最优群体, 这样可行Pareto群体就可划分为聚类Pareto群体以及聚类Pareto最优群体。

这样整个群体最终分类成4个群体, 即:不可行群体、可行非Pareto群体、聚类Pareto群体以及聚类Pareto最优群体, 关系如下:

3.4 群体R适应度赋值

在以上4个群体中, 不可行群体是整个群体中适应能力最差的群体, 应当降低它们遗传到下一代群体的概率;而聚类Pareto最优群体是从Pareto群体中精心挑选的适应能力最强的精英群体, 应当提高它们遗传到下一代群体的概率。为了达到这一目的, 可以为这4类群体分别赋予R适应度, 它们的关系为:

R (不可行群体) ≤R (可行非Pareto群体) ≤R (聚类Pareto群体) ≤R (聚类Pareto最优群体)

这时可以将R适应度作为算法的适应度, 将它作为遗传算法选择操作的依据。

3.5 算法具体过程

(1) 设置进化代数t←1, 生成M个初始个体组成初始群体p (t) 。

(2) 依据约束条件, 将整个群体划分为不可行群体p (t) 1与可行群体p (t) ′1。

(3) 对于可行群体p (t) ′1, 计算各个个体的适应值, 再进行Pareto运算, 将可行群体划分为可行非Pareto群体p (t) 2与可行Pareto群体p (t) ′2。

(4) 对于可行Pareto群体p (t) ′2, 进行k-均值聚类分析运算, 将可行Pareto群体划分为聚类Pareto群体p (t) 3以及聚类Pareto最优群体p (t) 4, 这是实现群体的多样化的一个重要步骤。

(5) 对p (t) 1、p (t) 2、p (t) 3、p (t) 4这四类子群体, 分别赋予适当的适应值。

(6) 对群体进行比例选择运算。

(7) 对群体进行单点交叉运算。

(8) 对群体进行均匀变异运算。

(9) 终止条件判断。若不满足终止条件, 则更新进化代数记数器t←2, 若满足终止条件, 则输出计算结果, 算法结束。

4 试验结果

为了检验本算法的性能, 利用Matlab编程, 对两组具有复杂约束条件的多目标优化问题进行计算。具体参数为:种群规模Pop Sice=200, 基因长度Chro Length=10, 交叉概率Pc=0.7, 变异概率Pm=0.1, R (不可行群体) =1, R (可行非Pareto群体) =20, R (聚类Pareto群体) =20, R (聚类Pareto最优群体) =100。

问题1:

问题2:

问题1的最优解如图2所示, 问题2的最优解如图3所示:

从图2与图3可以看出, 利用本文提出的算法, 不但计算出的Pareto最优解数量多, 分布广泛、均匀, 而且最优前沿曲线光滑、匀称, 此外, 本文提出的算法进化速度较快, 图2只需进化10代, 图3进化40代即已达到很好的优化效果。

5 结束语

本文提出了一种基于群体分类的复杂约束条件多目标优化遗传算法, 该算法为解决一些高度受限的优化问题提供了有效的途径, 它使用了聚类技术和分类概念, 很大程度上提高了算法性能, 改善了解集的质量。计算机仿真计算表明, 该算法不仅能得到分布广泛、均匀的Pareto最优解, 而且进化速度快, 通常只需10-40代即可达到很好的优化效果。

摘要：对于含复杂约束条件的多目标优化问题, 提出了一种基于群体分类的遗传算法。其分类方法是:首先将种群分为不可行群体和可行群体, 又将可行群体分为可行非Pareto群体和可行Pareto群体, 然后再用k-均值聚类将可行Pareto群体划分为非聚类Pareto群体和聚类Pareto群体, 最后对上述4个群体分别赋以适当的R适应值。数值计算表明, 这种新的算法不仅能得到分布广泛、均匀的Pareto最优解, 而且进化速度很快。

关键词：遗传算法,多目标优化,约束条件,聚类分析

参考文献

[1]SCHAFFER, J.D.Multiple objective optimization with vector evalu-ated genetic algorithms.In J.Grefenstette, ed.Proceedings of an In-ternational Conference on Genetic Algorithms and their Applica-tions, 1985.

[2]HORN J, NAFPLIOTIS N, GOLDBERG D E.A niched Pareto ge-netic algorithm for multiobjective optimization[A].Proceedings of the First IEEE Conference on Evolutionary Computation[C].Piscat-away, 1994:82-87.

[3]FONSECA, C.M.&FLEMING, P.J.Genetic algorithms for multiobjec-tive optimization:formulation, discussion and generalization.Pro-ceeding of the Fifth International Conference on Genetic Algo-rithms.MorganKauffman, 1993.

[4]KALYANMOY DEB, SAMIR AGRAWAL, AMRIT PRATAP, AND T MEYARIVAN.A Fast Elitist Non-Dominated Sorting Genetic Al-gorithm for Multi-Objective Optimization:NSGA-II, KanGAL Re-port No.200001.

[5]Eckart Zitzler and Lothar Thiele, Multiobjective Optimization Using Evolutionary Algorithms-A Comparative Case Study.

[6]JIMENEZ F.and Verdegay J.Evolutionary techniques for constrained optimization problems.In7th European Congress on Intelligent Techniques and Soft Computing (EUFIT'99) , Aachen, Germany.Springer-Verlag, 1999.

[7]王跃宣, 刘连臣.处理带约束的多目标优化进化算法[J].清华大学学报, 2005 (1) .

微型多目标遗传算法 篇7

关键词：多目标组合优化,适应度赋值,局部搜索

0 引 言

现实世界的很多问题常常要考虑多个相互冲突的目标。多目标问题的最优解通常不是单个解,而是一组Pareto最优解。20世纪80年代中期作为关键智能计算技术之一的进化算法开始应用到了多目标优化领域,并逐渐形成了众多的多目标进化算法。其中,遗传算法和局部搜索的混合,常常表现出胜过“纯”遗传算法的较快的收敛速度和较高的全局搜索能力[1,2,3,4,5]。Ishibuchi和Murata在文献[1]中建立了基于随机加权和的多目标遗传局部搜索算法IM-MOGLS(multi-objective genetic local search algorithms),其主要思想是每代随机地产生一组权重,用于进化过程中双亲的选择和局部搜索过程中搜索方向的确定,局部搜索作用于当前群体的每一个个体上。Jaszkiewicz在文献[3]也建立了一种多目标遗传局部搜索算法J-MOGLS,主要做法是根据随机权重确定的标量化函数,从当前群体中选择一定数目的不同个体,构成临时群体,从中选择两个个体交叉,得到的新个体进行局部搜索。本文对Deb等人提出的著名的NSGA-Ⅱ算法[6]加以改进,并与局部搜索相结合,提出了一种不同的多目标遗传局部搜索算法MOGLS。该算法采用基于分散度的精英选择策略和二元赌轮选择操作,并采取非劣解并行局部搜索策略,在改善算法收敛性的同时,保持了群体的多样性。通过对一组多目标flow shop问题的求解,与IM-MOGLS[1]、J-MOGLS[3]、NSGA-Ⅱ[6]算法进行比较,验证了本算法的有效性。

1 问题描述

一般地,多目标组合优化问题可描述如下[7]:

Minimize z=f(x)=(f1(x)=z1,…,fr(x)=zr)

Subject to x∈Ω

其中,f(x)为具有r个分量的目标向量,x是离散的决策向量,Ω是可行解的集合,点z=f(x)是解x∈Ω在目标空间中的像。

如果对任意的j∈{1,2,…,r},有zj≤zj′,并且至少存在一个j,有zj < zj′,则称点z=(z1,…,zr)支配点z′ = (z1 ′,…,zr′)。

如果解x的像支配解x′的像,则称解x支配解x′。

如果不存在x∈Ω使得z=f(x)支配z*=f(x*),则称解x*∈Ω是Pareto最优解(或非劣解)。

Pareto最优解组成的集合称为Pareto最优集。Pareto最优集在目标空间的像称为Pareto前沿(或非劣前沿)。

2 多目标遗传局部搜索算法(MOGLS)

2.1 精英选择策略

本文MOGLS算法使用两个群体:进化群体和外部群体。外部群体用来保存进化过程中产生的所有非劣解。在每次迭代中,从外部群体NDt中随机选择Nelite个精英解,组成精英解集Et,加入到当前群体MPt中,形成联合群体MPt∪Et。让目前所发现的所有非劣解都有机会参与局部搜索,以提高算法的收敛性。

从外部群体NDt中选择Nelite个精英解的过程如下:首先计算外部群体中每个个体与其他个体在目标空间中的欧几里德距离,将其中的最小值作为该个体的分散度。然后选择Nelite个分散度最大的个体,当外部群体中的个体数不足Nelite时,不足的部分再从外部群体中依据分散度由大到小的顺序依次选择。这种策略不但操作简单,而且能够选择密度较小的外部群体中的个体,有利于维持群体多样性。

2.2 个体的适应度赋值和选择

多目标进化算法中,适应度赋值是关键技术之一。本文在NSGA-Ⅱ非劣分级及拥挤距离评估的基础上,提出如下适应度赋值方法:

(1) 采用NSGA-Ⅱ的快速非劣分级技术将当前群体Pt划分为k个子群体,F1,F2,…,Fk;非劣等级分别为1,2,…,k;等级为1的个体为当前群体的非劣解。

(2) 然后使用NSGA-Ⅱ的拥挤距离评估方法对每一等级的非劣前沿上的点E∈f(Fi),i=1,2,…,k,计算拥挤距离dist(E)。

(3) 令等级k+1的最大适应度为0,即maxfitnessk+1=0。

(4) 对等级为j的个体x∈Fj,计算其适应度fitness(x)。

fitness(x)=maxfitnessj+1+dist(f(x))

(5) 计算等级j的最大适应度maxfitnessj。

maxfitnessj=max{fitness(y):y∈Fj}

(6) 如果j≤1则停止,否则j=j-1,返回步骤(4)。

上述适应度赋值过程,是从第k级开始,逐级计算每一等级个体的适应度值,直到第1级的,等级为j的个体的适应度等于其本身拥挤距离与等级为j+1的所有个体的适应度最大值之和。

在基于个体适应度的赌轮选择中,当某个体的适应度过大时,往往使得此个体多次被选择,造成在交配池中过多。为此,本文采用文献[8]的二元赌轮选择方式,即在连续两次的随机采样中指针不复位,从当前群体中选择两个不同个体,进一步保持群体多样性。

2.3 多目标局部搜索

IM-MOGLS和J-MOGLS对进化产生的每一个个体进行局部搜索,但是当个体质量较差时,搜索效率并不高。此外,IM-MOGLS和J-MOGLS对个体进行局部搜索时,只在新个体和目标个体这两个个体间比较后就决定是否接受新个体,这种方式有时会丢弃一些支配其它个体的Pareto最优解。为避免上述问题,本文采取非劣解并行搜索策略,主要做法是:对非劣解集S中的每一个解x,产生一个邻域N(x),对该邻域内的解y,只要y不被S中的解支配,则接受y作为新解,放入集合S′中,S′为搜索过程中产生的不被S支配的邻域解的集合。用S′修正S,即将S′的解添加到S中,同时删除S中被支配的解,这样会得到改善的非劣解集S。再将S作为初始集合,重复上述搜索过程。这种从S出发,并行地勘探解空间的几个区域,能够加强不同区域的搜索,提高搜索效率。具体步骤如下:

(1) 初始化局部搜索的非劣解集合S,并将S加入到NDI中,令迭代次数t=1。

(2) 构建邻域解的集合S′,方法如下:

置S′为空集。对S中每一个解xk,产生xk的邻域N(xk),对y∈N(xk),判断y是否处于受集合NDI支配的区域。若y不被NDI中的任何解支配,且y∉NDI,则将y加入到S′中。

(3) 用S′修正NDI,即将S′的解添加到NDI中,剔除其中受支配的解。

(4) 如果t小于最大迭代数,则S=NDI,t=t+1,返回步骤(2)。

2.4 MOGLS的实现步骤

(1) 算法参数设定

群体规模Npop,交叉概率Pc,变异概率Pm,最大精英数Nelite,局部搜索的最大迭代数Niter。

(2) 初始化

随机产生规模为Npop的初始群体,计算每个个体的r个目标值。初始化外部群体ND1=ϕ,初始化精英解集E1=ϕ。

(3) 群体分级

据Pareto支配关系在目标空间对群体Pt进行非劣分级,确定每个个体的非劣等级。

(4) 修正外部群体NDt

将等级序数为1的个体加入到NDt中,再从NDt中删去被支配的个体

(5) 适应度赋值

对每一等级中个体进行拥挤距离评估,然后按2.2节的方法计算所有个体的适应度。

(6) 选择、交叉和变异

将Pt中的个体按适应度由大到小排序,选择前Npop个个体进入交配池,按二元赌轮选择操作从交配池中选择两个不同的个体,进行交叉和变异,共产生Npop个个体,形成中间群体MPt。

(7) 精英机制

从集合NDt中选出Nelite个个体,存放于集合Et中。

(8) 评价

对联合群体MPt∪Et中的中的Npop+Nelite个个体,计算r个目标值。

(9) 局部搜索

应用2.3节的方法对MPt∪Et的非劣解集S进行局部搜索,得到改善的非劣解集NDI。用NDI修正MPt∪Et,得到下一代群体Pt+1。

(10) 停止准则

若停止条件满足,则输出外部群体,否则Pt=Pt+1,返回步骤(3)。

3 算法测试

3.1 测试问题

Flow shop问题是一种典型的组合优化问题,置换flow shop调度可以描述为n个工件按同一加工顺序在m个机器上进行加工,要求确定使预定目标函数最小的工件加工顺序。此问题是NP难问题,其搜索空间的规模是n!。本文产生8个测试问题[2],包括机器数m为20,工件数n分别为20、40、60、和80,目标数N为2和3,每一问题表示成N×n。对于N=2,优化目标是使制造周期(make span)和最大拖期(maximum tardiness)达到最小,对于N=3,还要使目标总流程时间(total flow time)达到最小。

3.2 性能指标

本文采用Knowles 和Corne[9]提出的基于与参考集(Pareto最优集或近似Pareto最优集)的距离指标D1R来评价解的质量。D1R可同时考察解集的收敛性和多样性。设S*是参考解集,Sj是评价的解集,则D1R定义如下:

$D{}_{1R}(S{}_j)=\frac{1}{\left|S{}^{*}\right|}{\displaystyle \sum _{y\in S{}^{*}}\min }\{d{}_{xy}|x\in S{}_j\}$

其中dxy是解x和参考解y在N维标准化目标空间的距离:

$d{}_{xy}=\sqrt{{\displaystyle \sum _{i=1}^{{\rm N}}(}f{}_i^{*}(y)-f{}_i^{*}(x)){}^2}$

其中f${}_i^{*}$(·)是使用参考集进行标准化的第i个目标值。

D1R不但能评价解集Sj的分布,而且能评价Sj到参考集S*的近似程度。D1R(Sj)越小,解集Sj的质量越好。

3.3 计算结果和比较

本文采用IM-MOGLS、J-MOGLS以及NSGA-Ⅱ作为参考算法,检验本文MOGLS算法的优化性能。所有算法均使用基于工件加工顺序的自然数编码,统一设定参数:群体规模Npop=100,交叉概率Pc=0.9,变异概率Pm=0.3,精英解的数目Nelite=20。对于J-MOGLS,群体的最大规模为Nmax =200,对于MOGLS,局部搜索的最大迭代数Niter=3。所有算法使用相同的进化和局部搜索操作:两点交叉、插入变异、对换邻域且搜索步长为2。计算终止条件均设定为评价100000个解。每种算法在相同的初始条件下独立运行15次,合并各次非劣解集并剔除其中的劣解后,获得各问题的最终非劣解集,作为参考集(非劣前沿)。表1是每种算法产生的非劣解数量以及评价指标D1R的计算结果。从中可以看到,在相同的算法终止条件下,本文的算法能够获得较多的非劣解。还可看到,除问题2×20外,本文算法的D1R指标均好于其他三种算法,反映出本文算法能产生更接近Pareto前沿的近似集。

注:表中斜线“/”前面数字表示非劣解数量,斜线后面的数字表示指标D1R的计算值

4 结束语

本文提出了一种新的多目标遗传局部搜索算法MOGLS。MOGLS基于Pareto支配关系对非劣解进行并行局部搜索,增强不同区域的搜索,采用基于分散度的精英选择策略和二元赌轮选择操作,保持群体的多样性。此外,在群体进化的选择过程中淘汰掉个别最差个体,以加快解的收敛速度。与其它多目标算法比较,结果表明,MOGLS算法能有效地产生数量较多分布较广的近似Pareto最优解。

参考文献

[1]Ishibuchi H,Murata T.A multi-objective genetic local search algorithmand its application to flowshop scheduling[J].IEEE Transactions onSystems Man and Cybernetics,1998,28(3):392 403.

[2]Ishibuchi H,Yoshida T,Murata T.Balance between genetic search andlocal search in memetic algorithms for multiobjective permutation flow-shop scheduling[J].IEEE Transactions on Evolutionary Computation,2003,7(2):204 223.

[3]Jaszkiewicz A.Genetic local search for multi-objective combinatorialoptimization[J].European Journal of Operational Research,2002,137(1):50 71.

[4]Knowles J,Corne D.A memetic algorithm for multiobjective optimiza-tion[C]//Proceedings of the Congress on Evolutionary Computation,Piscataway,NJ,USA:IEEE,2000,325 332.

[5]Jaszkiewicz A.On the Performance of multiple-objective genetic localsearch on the 0/1 knapsack problem:a comparative experiment[J].IEEETransactions on Evolutionary Computation,2002,6(4):402 412.

[6]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective ge-netic algorithm:NSGA-Ⅱ[J].IEEE Transactions on EvolutionaryComputation,2002,6(2):182 197.

[7]Arroyo J E C,Armentano V A.genetic local search for multi-objectiveflowshop scheduling problems[J].European Journal of Operational Re-search,2005,167:717 738.

[8]Elaoud S,Loukil T,TeghemJ.The Pareto fitness gengtic algorithm:Testfunction study[J].European Journal of Operational Research,2007,177(3):1703 1719.

微型多目标遗传算法 篇8

关键词：风电场,无功优化,遗传算法,多目标优化

多机组并网型的风力发电场是大规模利用风能的有效方式。与常规发电厂不同,风力发电机组多采用异步发电机,在发出有功功率的同时要从电网吸收无功功率,再加上风能的随机性使得风力发电系统的运行方式不断改变,很容易造成并网点的电压降落,引起风电场母线电压的波动。因此,为改善和提高风电接入的电力系统电压质量问题,保证系统安全经济运行,必须加强无功和电压管理,进行合理的无功优化。

本文在分析和总结了现有一些主要的含风电场的电力系统无功优化方法[1,2,3,4,5,6]和遗传多目标优化算法[7]的基础上,将非支配排序的群体分级机制、精英保留策略和改进的小生境技术相结合,得到一种改进Pareto遗传多目标优化算法。同时,将改进算法用于含风电场的电力系统无功多目标优化。研究表明该方法不仅可以同时得到多组Pareto最优解,而且可以保证风电场并网点电压在允许范围内。

1 含风电场的电力系统无功优化模型

1.1 异步风力发电机模型

以基于异步发电机的风力发电机组为例,其简化Γ型等值电路如图1所示。图中,xs、xr分别为定、转子绕组的电抗,rr为转子绕组的电阻,xm为励磁电抗,s为转差率。

从图1中可得到异步风力发电机功率关系式[6]为

其中,xk=xs+xr,UG为机端电压。

从而得到有功功率P和无功功率Q为

由式(2)可得发电机转差率为

代入式(3),消去转差率可得:

从式(5)可以看出,当异步风力发电机输出的有功功率P一定时,吸收的无功功率Q与机端电压UG有密切的关系。

由风力发电机组功率传递关系可知,在某一风速下,风力发电机发出的有功功率为

其中,Pmec为发电机输入机械功率,ΔP为功率损耗,ρ为空气密度,A为风轮扫风平面面积,Cp为风能利用系数,v为风速。

对于具有N台风力发电机的风电场,在忽略内部损耗的情况下,假定所有机组具有相同机端电压,并且等于待求的风电场母线电压Uf,则风电场注入电力系统的总功率为

其中,Pf、Qf分别为风电场总的有功、无功功率,Pii、Qii分别为第ii台风电机组注入电网的有功、无功功率。

1.2 无功优化目标函数

风电场的无功优化是要向异步发电机提供所需的部分无功功率,减少电网向风电场提供无功,避免无功功率在电网中流动,降低电能损耗,稳定电网电压。无功优化的目标是降低有功网损和补偿设备的投资费用,增大电压稳定裕度。本文将有功网损最小、负荷节点电压偏移量最小、静态电压裕度最大作为多目标无功优化的目标函数,其模型表示为

其中,Ploss为有功网损,ΔUL为负荷节点电压偏移量,Ustab为系统静态电压稳定裕度,Nb为网络支路总数,NL为负荷节点个数,Gb(i,j)为第b条支路的电导,i、j为支路两端节点号,Ui、Uj分别为节点i、j的电压值,δij为节点i、j的电压相角差,Ul、Ulo、ΔUlmax分别为负荷节点实际电压、期望电压、最大允许电压偏差,λmin为收敛潮流的雅可比矩阵最小奇异值。

1.3 优化约束条件

要实现多目标无功优化,控制量和被控量需要满足相应的约束条件,在规定的范围内变化。约束包括潮流等式约束和变量不等式约束。

a.潮流等式约束

其中,PGi、QGi分别为节点i的有功、无功发电功率,PLi、QLi分别为节点i的有功、无功负荷功率,ΔQCi为补偿节点i的电容器补偿功率,Gij、Bij分别为节点导纳矩阵中第i行第j列对应元素的实部、虚部,Nnode为节点总数。

b.变量不等式约束

其中,UGh、Cr、Tk为控制变量,分别表示发电机机端电压、补偿电容投入步长数、变压器分接头位置;Ui、QGh为状态变量,分别表示节点电压、发电机无功输出;NG、NC、NT分别为系统中发电机台数、无功补偿点数、变压器台数。

2 改进的Pareto遗传多目标优化算法

2.1 多目标优化问题的数学描述

以在一组约束条件下最小化多目标问题为例,多目标优化问题可以描述为下面的形式:

其中,xRn为带有n个决策变量的向量,组成决策空间;YRq为带有q个目标函数的向量,组成目标空间;gjj(x)为不等式约束函数,共有m个,由它们形成可行解区域[8]。

在有多个目标时,由于存在目标之间冲突和无法比较的现象,一个解在某个目标上是最好的,在其他目标上可能是最差的。这些解称为非支配解或Pareto最优解。一组目标函数最优解的集合,称为Pareto最优集。最优集在空间上形成的曲面称为Pareto前沿面。

2.2 非支配排序的群体分级机制

进化寻优过程中,目标函数值有些是非支配的,有些是受支配的,即存在在各个目标上都优于它的解。如何给相同支配程度的解对应的个体分配适应度,使非支配个体继续进化下去,并且使受支配的个体逐渐向Pareto前沿面靠近,是多目标优化的关键问题。文献[9]提出了一种NSGA(Non-dominated Sorting in Genetic Algorithm)算法,对种群中的个体进行非支配排序。首先在目标空间中,根据受支配程度对目标函数值进行非支配排序,划分为若干等级,即对非支配解标记顺序为1;然后从目标空间中移出,在余下的目标值中再寻找非支配解并将其标记为顺序2;依次类推,直到所有目标函数值都完成排序。排序越靠前的目标值,对应的个体非支配程度越强,应当使它们继续进化下去。根据排序的序号,给每一个等级的个体分配一个适应度值,具有相同排序的非支配解分配相同的适应度值,使其获得相同的复制概率。适应度值可按式(13)[10]产生:

其中,ps为选择压差,一般取值范围为[1,2];p为个体在排序种群中的位置;Fit V(p)为p位置上个体的适应度值;M为种群中个体的数量。由于该适应度值仅根据排序序号获得,所以定义为虚拟适应度值。

2.3 最优个体的精英保留策略

由于遗传进化的随机因素,每一代进化获得的优良个体,在进入下一代进化的过程中有可能丢失,使得算法寻找最优解的效率降低。因此,有必要对每一代获得的一些优良个体进行保护,使其能够继续进化下去[11,12,13]。本文基于文献[9]父代与子代群体结合的思想,根据2.2节中非支配排序的结果,认为排序靠前的N1个个体是较为优良的个体,采用精英保留策略,将其作为优秀的非支配解保存在一个外部存储空间中。然后将排序后的群体进行新一轮遗传操作,产生的新种群与外部存储空间中的N1个优秀个体结合,作为下一步遗传操作的新群体。其中优良个体个数N1根据种群的大小进行适当选择。

2.4 改进的小生境技术

小生境技术是遗传算法中避免局部收敛和早熟、维持种群多样性的一种有效的方法[14,15]。在多目标优化中,采用小生境技术,可以获得分布均匀的Pareto前沿面。传统小生境技术的思想是当2个个体距离很近,小于某一个规定值时,根据个体适应度值,对适应度低的个体处以一个惩罚函数,使其在下一轮进化中淘汰,避免进化过程中陷入局部收敛。从2.2节中非支配排序和分配虚拟适应度值的过程可以看出,具有同一排序的非支配个体,其适应度值是相同的,无法按照传统的小生境技术根据适应度值的大小来淘汰个体。因此,本文采用一种向量模适应度函数作为淘汰准则。把目标空间中的目标函数值,看作q维空间中的向量,以向量的模(即与原点的欧氏距离)作为个体适应度函数值:

其中,α表示目标空间中的第α个目标。对于求最小化问题,目标向量的各分量越小越好,相应的向量模适应度函数值越小越好。在同一排序的个体中,若2个个体间距离小于某一规定值,就比较其向量模适应度函数值,对于向量模适应度函数值较大的个体处以惩罚函数,在下一轮进化中淘汰。个体之间的距离采用式(15)[16]计算:

α=1,2,…,M+N1-1;β=α+1,…,M+N1

其中,ξα、ξβ分别表示种群中第α个和第β个个体对应的目标向量。当‖ξα-ξβ‖

3 含风电场的电力系统遗传多目标无功优化

3.1 含风电场的电力系统潮流计算修正

在给定风速时,风电场发出的有功功率即确定,转差率确定,由式(5)可以看出,此时无功功率是风电场电压的函数,即无功功率和电压之间相互耦合,风电场节点不能简单地作为PQ节点或PV节点。在牛顿-拉夫逊法潮流计算中,风电场节点无功增量对电压的偏导数要增加以下量:

UfQfUf=Nii=鄱1鄱x2UfmiiUfxkii+U3fxkii姨U4f-4 Pi2ix2kii鄱Uf(16)

其中,下标ii表示对应第ii台风电机组参数。

3.2 含风电场的电力系统遗传多目标无功优化步骤

多目标算法在电力系统无功优化方面,已有学者进行了相关的研究[17,18]。而针对含有风电场的电力系统,多目标无功优化方面的研究不多。鉴于本文所提出改进算法的有效性,考虑将该方法应用于含风电场的电力系统无功优化,得到一种基于改进的Pareto遗传多目标算法的风电场无功优化方法。下面论述该方法的具体步骤。

a.输入风电场的机组台数、风电机组运行参数、风速参数等。

b.遗传编码和解码。本文UGh、Cr、Tk为控制变量,采用实数和整数混合编码,即[UG1…UGNGC1…CNC T1…TNT],其中UGh采用实数编码,Cr、Tk采用整数编码。实际各控制变量所表示的机端电压uGh、补偿容量QCr、变压器变比tk对应的解码为

其中,ΔqCr和Δtk为补偿电容和变压器的调节步长。

c.初始种群的产生。发电机机端电压的产生为UGh=1+fhrand/10,fh为随机产生的+1或-1,rand为在区间(0,1)上产生的随机数;变压器分接头位置的产生为Tk=rand(-NT,+NT),即在变压器分接头的调节范围(-NT,+NT)内随机产生的整数;补偿电容投入步长数的产生为Cr=rand(-NC,+NC),即在补偿电容调节范围(-NC,+NC)内随机产生的整数。

d.由风速参数确定每台风电机有功功率Pii,由风电机组的转速计算转差率s。

e.由遗传种群中风电场节点对应的机端电压初值根据式(5)计算每台风电机组的无功功率Qii。

f.由式(7)获得风电场注入系统总的有功功率Pf和无功功率Qf。

g.定义目标函数为

对当前初始种群参数进行潮流计算,对获得的各目标函数值,按第2节中介绍的遗传多目标优化算法进行非支配排序、遗传操作和小生境淘汰等运算。

h.校验是否达到最大遗传代数,若达到,结束计算;否则返回步骤e,进行下一轮计算。

4 算例分析

采用IEEE 14节点标准测试系统作为算例系统,某风电场通过变压器和110 k V线路接入测试系统的14号节点,如图2所示。

风电场安装有10台600 k W的异步风力发电机组,机组运行参数[19]为rs=0.001 692 p.u.,xs=0.099 85p.u.,rr=0.003 73 p.u.,xr=0.109 06 p.u.,xm=3.547 08p.u.,额定电压0.69 k V。风力发电机额定风速12 m/s,叶片长度21.5 m,空气密度1.225 kg/m3,齿轮箱变速比为1:34,风电场节点电压范围0.90~1.05 p.u.,补偿电容容量0.15 p.u.,按0.01 p.u.、0.02 p.u.、0.04 p.u.、0.08 p.u.分为4组进行组合。接入变压器变比电抗XT=0.105 p.u.,接入系统线路阻抗0.113 4+j 0.349 5 p.u.。IEEE 14测试系统参数见文献[20]。测试系统中变压器的调节范围0.95~1.05 p.u.,NT=5,调节步长Δt=0.01,无功补偿装置调节步长Δq=0.02。

算例中遗传操作参数设置为种群规模M=100,精英个体N1=50,最大遗传代次kGenmax=100,Nich=0.000 1,m=5,q=3。遗传操作中采用基于排序的随机遍历抽样选择,交叉操作采用单点交叉算子,交叉概率为0.8,变异操作采用实数变异算子,变异概率为0.25。

600 k W风电机组风速与功率特性见表1。

以10 m/s的风速为例,对风电场接入系统进行遗传多目标无功优化,所获得的Pareto非支配解如表2所示,其解空间分布如图3所示。

从表中可以看出Ploss、ΔUL、Ustab(标幺值)这3个目标函数值的相互矛盾性,很难同时兼顾3个目标最小化。因此只能根据系统的实际要求从Pareto最优解集中进行选择:当以系统Ploss最小为主要目标时,可在Ploss较小的方案中进行选择;当以提高Ustab为主要目标时,可在Ustab较大的方案中进行选择等。从表中还可以看出各Pareto解对应的Uf和QC1(标幺值)均没有超出运行范围,其中第2组解的Uf最接近基准值,可以作为选择相对最优解的参考。

与10 m/s风速的计算与选择类似,分别计算风电机组50%、60%、70%、80%、90%、100%负荷率时的多目标无功优化结果,如表3所示。

由表可见,各目标函数值均优于优化前的系统潮流计算值,且优化前风电场并网点电压存在越限,优化后电压保持在允许范围内,保证风电场正常运行。

5 结论

本文提出了一种基于非支配排序思想、精英保留策略和改进小生境技术的遗传多目标优化算法。针对含风电场的电力系统无功优化模型,提出了风电场无功多目标优化的目标函数和约束条件。通过对接入IEEE 14测试系统的某风电场进行算例分析,可得出2点结论。

a.风电场无功优化的多个目标之间存在矛盾性,很难同时兼顾。所提出的改进遗传多目标优化算法可同时得到多组Pareto最优解,给决策者提供了更多的选择,实现了真正意义上的多目标无功优化。

微型多目标遗传算法 篇9

车间作业调度问题(JSSP)是企业生产优化管理中一个重要课题。在工业制造环境中,为了完成一个作业,必须按作业工序在若干台机器上加工处理。如果同时有若干个作业需要完成,管理人员必须根据作业的生产方式和工艺要求设计一个调度表,以获得某种生产指标的最优化。

在经典作业车间调度中约定,n个不同工件,每个工件有m道生产工序,任一工序只能由指定的某台设备加工,即每个工序与每台机器相对应。而在实际应用中,一台机器可能对应多个工序,如多功能机床具有车、钻、铣等功能。当然一道工序也可以由多台功能相同的机器来完成。于是提出柔性作业车间调度(Flexible JSSP),一台机器至少能完成一道工序操作[1,2]。文献[3]中将柔性作业车间调度分为两种情形:一种情形是允许任何工序在任何机器完成,另一种情形是一些工序只在部分特定的机器中完成。

经典车间作业调度大多研究以生产周期为目标的单目标调度优化问题。文献[4]研究了以生产周期、机床闲置时间和工件延误时间为目标的多目标调度优化问题。为了获得多目标优化问题的最优解,通常将多目标问题求解转换为单目标问题求解,便于对候选解的评价与筛选。如文献[5]以生产周期、生产成本和设备利用率为目标,首先对时间和成本进行无量纲的标准化处理,再根据层次分析法对优化目标分别确定加权系数,把多目标的优化问题转化为单目标的优化问题。

然而,权重的选择或多或少取决于决策者的主观偏好,一定程度上影响算法搜索方向和搜索结果。为了尽量减少决策者在权重确定过程中的主观性,本文提出单目标决策下的求解多目标问题的算法,即在多个目标中根据决策者的意愿选择一个目标作为决策目标,用于解的评价和选择,其它目标则作为算法搜索的导向目标,用于引导解的搜索方向。

1 问题描述

在M台机器上加工N种工件,每种工件Wi由Ni 道工序组成,Ni 道工序之间有工艺的先后约束,工件的每道工序可由M台机器中的多台机器加工。Mij 表示第i 种工件的第j道工序可用机器集合Mij⊆{1,2,…,M}; Pijk表示第i种工件的第j道工序在第k个机器上加工需要的时间,即1≤i≤N,1≤j≤Ni,1≤k≤M。

● 约束条件

(1) 所有机器在t=0时刻都可用;

(2) 所有工件在t=0时刻都可被加工;

(3) 所有工件的工序的先后顺序是固定不变的;

(4) 工序在可供选择的机器上的加工时间已确定;

(5) 每个工件在固定时刻只能在一台机器上加工;

(6) 加工是非抢占式的,即给定时刻机器k只能加工一个工件,只有该工件的此工序加工完毕后才能加工别的工件,即工件的加工不允许中断。

● 性能优化指标

(1) Makespan是调度的生产周期,即所有工件的最大完成时间。设第i类工件的最后一个工序完成时间为Ti,则:

$f1=\underset{1\le i\le {\rm N}}{{\displaystyle \max }}({\rm T}{}_i)$

(2) 拖期惩罚成本是指工件晚于交货期完成时,制造商需要提供给客户与拖期时间相关的罚金。设第i类工件的交货期为Ei,单位时间拖期惩罚值为Ai,则:

$f2=\underset{1\le i\le {\rm N}}{{\displaystyle \max }}(\max ({\rm T}{}_i-E{}_i,0)\times A{}_i)$

(3) 生产成本,包含机器运行成本和闲置成本。设机器k的运行费用Bk,闲置费用Ck,则:

$\begin{array}{l}f3={\displaystyle \sum _{k=1}^{{\rm M}}(}({\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}{}_{ijk}\times n{}_i))\times B{}_k+(f1-\\ {\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}{}_{ijk}\times n{}_i))\times C{}_k)\end{array}$

(4) 单台机器最大负荷,按单台机器加工工件的最大时间总和计算。设每类工件加工数量为ni,则:

$f4=\underset{1\le k\le {\rm M}}{{\displaystyle \max }}({\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}{}_{ijk}\times n{}_i))$

(5) 机器总负荷,按所有机器加工工件时间总和计算,则:

$f5={\displaystyle \sum _{k=1}^{{\rm M}}(}{\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}{}_{ijk}\times n{}_i))$

● 调度任务

设车间作业调度为S=(S1,S2,…,SM) ,其中Si=(Ji1,Ji2,…,Jip)是第i台设备p个作业的加工序列。M台设备的加工序列组成一个调度。

调度任务是寻找一个满足约束的调度S,使得目标函数f 2的值趋于最小,并使目标函数f 1、f 3、f 4、f 5的值得到优化。

2 基于遗传算法的调度优化

遗传算法是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则和搜索算法。它从一个种群开始,利用选择、交叉、变异等遗传算子对种群进行不断进化,最后得到全局最优解或近似最优解。为了实现单目标决策下车间作业调度多目标问题的求解,本文对遗传算法的染色体编码、变异算子进行了全新的设计和改进。

2.1 基本概念

定义1 作业:车间生产调度的基本单位,由若干同类工件组成。

定义2 静态作业和动态作业:一个工件加工任务可分解成一个或多个作业,此时生成的作业处于静止状态,称为静态作业。当作业进入某个工序时,作业处于运行状态,此时的作业称为动态作业,用有序对(作业代号,工序号)表示。

定义3 作业规模或批量:一个作业所含的工件数量。

定义4 工作中心:功能相互兼容的设备组。

定义5 设备功能相容:(1) 任意设备k1、k2,若k1∈Mij 且k2∈Mij,k1与k2功能相容,记作k1∝k2 其中Mij是工件i第j道工序能使用的设备集;(2) 相容传递,设k1∝k2,若k1∝k3,则k2∝k3。

2.2 决策函数和导向原则

单目标决策下多目标车间作业调度,首先在诸多目标中选择一个目标作为决策目标,即作为适应度函数,用于评价和选择候选解。按期交货是企业生产管理的重要目标,它关系到企业的信用度。本文选择拖期惩罚函数f 2作为决策目标函数,其它目标则按照下列导向原则实现。

原则1 平衡负荷原则: 在同一工作中心内,将高负荷设备的作业转移到低负荷设备的作业队列中。

定义6 设备负荷驱动的作业迁移:设两台设备Mj、Mk∈WCi, WCi 是第i个工作中心,ψ(Mj) 、ψ(Mk)分别是设备Mj、Mk加工负荷,且ψ(Mj)>ψ(Mk),设Sj、Sk分别是设备Mj、Mk的作业序列,作业J∈Sj,则设备负荷驱动的作业迁移为Sj ←Sj-{J},Sk ←Sk+{J}。

定义7 设ψ′(Mj) 、ψ′(Mk)分别是作业发生迁移后设备Mj、Mk加工负荷,若ψ(Mj)> ψ′(Mk),则作业迁移称为有效迁移。

定理1 设f 4、f 4′是设备负荷驱动的作业迁移前和迁移后单台设备的最大负荷,实施作业有效迁移后,有f 4′≤f 4。

证明: 设pj是作业J在Mj的加工时间,即pj=P(Mj,J),pk=P(Mk,J)。

推论① 对于设备Mj,移去作业J后,ψ′(Mj)= ψ(Mj)- pj,由于pj >0, 则ψ′(Mj)<ψ(Mj)。

推论② 对于设备Mk,添加作业J后,ψ′(Mk)= ψ(Mk)+ pk ,由于pk >0,则ψ′(Mk)>ψ(Mk)。

设E是作业调度的设备全集,令Q={ Mj ,Mk },┐Q=E-Q。根据指标f 4的定义,f 4=max(ψ(E))=max(ψ(Q),ψ(┐Q))= max(ψ(Mj),ψ(Mk),ψ(┐Q));f 4′= max(ψ′(E))=max(ψ′(Q), ψ′(┐Q))= max(ψ′(Mj) ,ψ′(Mk) , ψ′(┐Q))。由于作业迁移仅在Mj、Mk之间进行,其它设备的负荷未发生变化,则ψ′(┐Q)= ψ (┐Q)。故f 4′= max(ψ′(Mj) ,ψ′(Mk) ,ψ (┐Q))。

(1) 若ψ(┐Q) ≥ψ(Mj)

(i) 由发生迁移的条件可知,ψ(Mj)>ψ(Mk), 故ψ(┐Q)>ψ(Mk) f 4= max(ψ(Mj) ,ψ(Mk),ψ(┐Q))=ψ(┐Q);

(ii) 根据推论①:ψ′(Mj)<ψ(Mj),另作业有效迁移的条件:ψ(Mj)> ψ′(Mk),则有ψ(┐Q)> ψ′(Mj), ψ(┐Q) > ψ′(Mk), f 4′ = max(ψ′(Mj) ,ψ′(Mk) , ψ (┐Q))=ψ(┐Q)。

由(i)、(ii)可知 ∴ f 4= f 4′。

(2) 若ψ(┐Q)<ψ(Mj)

(i) 由发生迁移的条件可知,ψ(Mj)>ψ(Mk), f 4= max(ψ(Mj) ,ψ(Mk),ψ(┐Q))= ψ(Mj);

(ii) 根据推论①:ψ′(Mj)<ψ(Mj),另作业有效迁移的条件:ψ(Mj)> ψ′(Mk),则f 4′ = max(ψ′(Mj) ,ψ′(Mk) , ψ (┐Q))< ψ(Mj)。

由(i)、(ii)可知 ∴ f 4′< f 4。

综合(1)、(2),当作业发生设备负荷驱动有效迁移后,f 4′≤f 4。证毕。

由定理1可知,导向原则1将作业从同一工作中心高负荷的设备转移到低负荷的同类设备加工,降低单台设备的最大工作负荷,可实现目标f4的优化。此外,单台设备最大负荷的下降,也一定程度上缩短了单台设备生产周期,间接实现目标f1的优化。

原则2 最小加工时间原则:同一工件的同一工序,如果可在多台设备加工,则尽量选择加工时间最短的设备。

定理2 设作业J,是工件wi的第j道工序。可用设备集Mij={M1,M2,M3,…,Mn},对应的加工时间P(Mt,J),当设备总负荷f 5最小时,当且仅当Pij=min(P(Mt,J)),1≤t≤n。

证明:(1) 设$f5={\displaystyle \sum _{k=1}^{{\rm M}}(}{\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}{}_{ijk}\times n{}_i))$最小,且Pij≠min(P(Mt,J)),则∃ P′ij=min(P(Mt,w)),P′ij<Pij。令f 5′=(f 5- Pij)+ P′ij,则f 5′-f 5= P′ij-Pij<0,则与f 5是最小矛盾。故Pij=min(P(Mt,w))。

(2) 令Pij=min(P(Mt,J)),1≤t≤n,则:

$\begin{array}{l}f5={\displaystyle \sum _{k=1}^{{\rm M}}(}{\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}{}_{ijk}\times n{}_i))\\ ={\displaystyle \sum _{k=1}^{{\rm M}}(}{\displaystyle \sum _i{\displaystyle \sum _j(}}\underset{t}{{\displaystyle \min }}({\rm P}({\rm M}{}_t,J)){}_{ijk}\times n{}_i))\\ =\min ({\displaystyle \sum _{k=1}^{{\rm M}}(}{\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}({\rm M}{}_t,J)){}_{ijk}\times n{}_i))\end{array}$

即设备负荷值最小。

由定理2可知该导向原则2可实现目标函数f 5。

定理3 在生产周期f 1一定,设备闲置成本C小于运行成本B的情况下,设备总负荷f 5取小值时,总成本f 3也趋于最小。

证明:根据f 3的定义可知:

$\begin{array}{l}f3={\displaystyle \sum _{k=1}^{{\rm M}}(}({\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}{}_{ijk}\times n{}_i))\times B{}_k+\\ (f1-{\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}{}_{ijk}\times n{}_i))\times C{}_k)\end{array}$

经整理得:

$f3={\displaystyle \sum _{k=1}^{{\rm M}}(}f1\times C{}_k)+{\displaystyle \sum _{k=1}^{{\rm M}}(}({\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}{}_{ijk}\times n{}_i))\times (B{}_k-C{}_k))$

令$d=\underset{k=1}{\overset{{\rm M}}{{\displaystyle \max }}}(B{}_k-C{}_k)$,代入后得:

$\begin{array}{l}f3\le {\displaystyle \sum _{k=1}^{{\rm M}}(}f1\times C{}_k)+{\displaystyle \sum _{k=1}^{{\rm M}}(}({\displaystyle \sum _i{\displaystyle \sum _j(}}{\rm P}{}_{ijk}\times n{}_i))\times d)\\ ={\displaystyle \sum _{k=1}^{{\rm M}}(}f1\times C{}_k)+f5\times d\end{array}$

根据题设条件,f 1不变,${\displaystyle \sum _{k=1}^{{\rm M}}(}f1\times C{}_k)$为常量项,又Bk>Ck,则d>0。显然,当f 5取最小值时,f 3趋于最小。

由定理3可知,导向原则2也间接实现目标函数f 3的优化。

2.3 染色体编码

经典的车间作业调度问题,通常采用基于工序的表达法, 即给所有同一零件的工序指定相同的符号,然后根据它们在给定染色体中出现的顺序来加以解释[6,7,8]。

以3×3的JSP调度问题为例,设有3个作业(工件)、3台实验设备M1、M2 、M3,每个作业有3个工序,下面机器加工序列矩阵则是作业调度的一个可行解:

基于工序表达法的染色体为:

[C]:(1M2,2M2,1M1,3M3,2M3,3M2,1M3,3M1,2M1)。

由于该染色体中,相同作业的前后顺序默认为工序顺序,即首次出现的作业1是第一道工序,第二次出现的作业1是第二道工序,依次类推,故该染色体可显式表示为:

[C]:(1-1M2,2-1M2,1-2M1,3-1M3,2-2M3,3-2M2,1-3M3,3-3M1,2-3M1)。

柔性作业调度问题因每个作业(工件)单道工序可使用的同类功能设备台数≥1,每个作业无需直接分配到设备,可先分配到工作中心(设备组),在工作中心内部进行二次调度。于是,本文对染色体编码方式进行如下改进:

(1) 染色体由2层结构增加4层结构,每个基因对应一个工作中心,由于每个工作中心有多台设备,每个基因分解为若干基因片断,每个基因片断对应一台设备的作业序列。

(2) 染色体结构改变后,作业的排列呈树形非线性关系,作业的工序号不能隐含在染色体的基因序列中,必须在染色体中显式表示。

定义8 基于工作中心染色体编码:作业按照工序分配到工作中心,以工作中心为单位,由每台设备生成一个作业序列的染色体编码方式。具体描述如下:

设有3个作业,3个工作中心WC1、WC2、WC3,其中WC1={M1,M2},WC2={M3},WC3={M4,M5,M6},下面是1条基于工作中心编码的染色体:

[C]:([[1,2,3]M1,2-3M2]WC1,[[1,2,3]M3]WC2,[3-1M4,[1,2,3]M6]WC3)。

2.4 选择操作

本文采用轮盘赌选择的方法。轮盘中不同比例的区域是根据个体适应度大小分配的,适应度高的个体由于在轮盘中占据较大比例的区域,因此被选中的概率较大,得以生存的概率大,相反,适应度较低的个体被淘汰的概率较大。

2.5 交叉操作

交叉是遗传算法中最主要的一种操作。在交叉操作中,首先产生一个随机数,如果小于交叉率(默认为0.7),再产生一个随机数,确定基因交换位置,然后从种群中随机选择两条染色体,交换相同位置的一对基因,即交换不同染色体之间相同工作中心的作业序列。

2.6 变异操作

遗传算法的变异操作的作用是增加解的多样性,防止解过早收敛。本文在变异操作中嵌入了导向原则1和导向原则2,实行诱导性变异,即在增加解的多样性的同时,对解的目标控制起引导作用。

(1) 变异算法I——设备负荷驱动的作业迁移(导向原则1)//在变异率R范围内实现设备负荷驱动的作业迁移

for(i=0;i<Nwc;i++) //Nwc为工作中心的个数

{ for(j=0; j<M && Mj∈ WCi; j++) // WCi为第i个工作中心

{ for(k=j+1; k<M && Mk∈ WCi; k++ )

{ r=rand()%100/100; //取0～1之间随机数

if(r<R) //R为变异率

{ if(Ψ(Mj)> Ψ(Mk))

{ if(Ψ(Mj)> Ψ(Mk)+P(J1,Mk))

{ J1=get(S(Mj); //从Mj作业序列中取出作业J1;

S(Mj)=S(Mj)-J1;

S(Mk)=S(Mk)+J1;

}

}else

{ if(Ψ(Mk)> Ψ(Mj) +P(J2,Mj))

{ J2=get(S(Mk); //从Mk作业序列中取出作业J2;

S(Mk)=S(Mk)-J2;

S(Mj)=S(Mj)+J2;

}

}

}

}

}

}

(2) 变异算法II——加工时间驱动的作业迁移(导向原则2)

// 在变异率R范围内实现最小加工时间驱动的作业迁移

// M(J)是作业J可加工的设备集

// M’(J)是作业J可加工的最小加工时间的设备集,M’(J)⊆M(J)

for(J =0;J<Nj;J++) // Nj为所有作业数,J是作业流水号

{ Mk=get(M(J)); // 从M(J)中分配一台设备Mk为作业J的加工设备

r=rand()%100/100; // 取0～1之间随机数;

if(r<R) //R为变异率

{

Mt=get(M’(J)); // 从M’ (J)中任取一台设备Mt为作业J的加工候选设备

p=P(Mt,J);

if(P(Mk,J)≥p)

{

S(Mk)=S(Mk)-J;

S(Mt)=S(Mt)+J;

}

}

}

}

3 仿真实验

为了便于实验结果分析,本文采用文献[9]和文献[10]中两个算例:

算例1 车间作业计划中,有4种不同类型的工件,每一种工件的加工数量为8,且加工工序都是3道,每道工序均可被多台机床加工,不同类型的机床设备数是6台。4种不同类型工件的加工时间以及每道工序的辅助加工时间信息由加工时间/辅助加工时间表提供,如文献[9]表1所示。

算例2 某泵阀企业零配件制造车间有10台加工设备,某一时段加工8种工件,每种工件加工数量均为10,工件均包含6道工序。设备名称、功能及工作费率、空闲费率见(文献[10]表4)。各种工件加工工艺见(文献[10]表5)。加工工序在可选设备的加工时间见(文献[10]表6)。各种工件的交货期和拖期惩罚见(文献[10]表7)。

在不影响作业计划算法和相关结论的前提下,两个算例均假设设备准备时间与单个工件的工序加工时间相同。

3.1 实验目的

本实验旨在分析变异操作设计中,变异I和变异II对实验结果影响因子,以及本文算法与其它算法所求最优解的比较。

3.2 实验环境

本实验在CPU(Intel Celerol 1.5G),Windows XP,VC++ 6.0环境下进行。

3.3 实验结果

本实验种群规模设为50,选择遗传代数200、交换率为0.7,变异率取0.02,为了分析单目标决策、多目标引导算法对实验结果的影响,本文选取变异I和变异II的变异率作为自变量,确定了四个实验方案:① 变异I和变异II的变异率均为0;② 变异I的变异率为0.02,变异II的变异率为0;③ 变异I的变异率为0,变异II的变异率为0.02;④ 变异I和变异II的变异率均为0.02。每个方案各实验30次,算例1和算例2每个指标的平均值分别见表2和表3所示。

若设表中每列指标最大值的评价指数为1,次大者为2,次小者为3,最小者为4,算例1(表2)中方案①～方案④方案评价指数依次为5,10,16,19;算例2(表3)中方案①～方案④方案评价指数依次为5,11,15,19。则可得出如下结论:

方案①由于未考虑设备负荷平衡和工序优化,变异率均为0,各项指标值偏高,方案评价指数最低;方案②通过则调整了设备之间的负荷的平衡,但未考虑工件工序的优化,单个设备最大负荷得到了改善,并有效改善了多项指标;方案③则注重工件柔性工序的优化,各项指标继续得到了改善,尤其是设备总负荷处于最低水平;方案④综合了方案②和方案③的优势,各项指标均趋向于最优,方案评价指数最高。由此可见,通过变异算子进行决策诱导是有效的。

本文所提出的算法能搜索到的最优解不劣于文献[9]和文献[10]的求解结果。算例1中,文献9的最优解生产周期是87,本文算法的最优解的生产周期则为86;算例2中,由于把f2作为单决策目标,更易搜索到f2目标较低的最低解(见表4所示)。图1是第1个解(132,48,8143,113,738)的甘特图,图中黑色部分为机器的准备时间。

4 结 语

本文根据车间作业调度实际需要,提出了单目标决策、多目标引导的作业调度方案。与传统的多目标决策方案相比,由完全被动选择转向被动选择和适度主导引导相结合,对遗传算法中的染色体编码方案和交换、变异、选择算子进行了重新的设计,提出了基于工作中心(设备组)的染色体的编码方案,染色体交叉运算仅仅是工作中心之间的作业重组,未涉及到工作中心内部作业调整,确保两个可行解的交叉运算结果仍是可行解。工作中心内部作业的调整主要是通过变异算子来实现,变异I是把作业从高负荷的设备调整到低负荷的设备,变异II是在作业柔性工序范围内,将作业从加工时间长的设备调整到到加工时间短的设备,以减轻设备的工作负荷。实验表明,变异I和变异II在变异率范围内能有效提高解的主要指标。与文献的算法[10]相比,虽然最优解的结果并非所有的指标值都达到最优,但避开了如何给定各个指标权重的难题。

鉴于实际车间作业调度,每类加工工件的数量通常都不少于1件,车间作业调度问题必然涉及到作业的批量规则和批量的选择。本文采用的分批方案是将所有工件加工数量10件分为7件和3件两批,至于如何设计分批方案能实现多目标车间作业最优调度,将是我们下一阶段的研究重点。

参考文献

[1]Najid N M,Dauzere-Peres S,Zaidat A.A modified simulated annealingmethod for flexible job shop scheduling problem[C]//IEEE Interna-tional Conference on Systems,Man and Cybernetics,2002,5:6.

[2]Unachak P,Goodman E D.Adaptive representation for flexible job-shopscheduling and rescheduling[C]//GEC Summit 2009:511-516.

[3]Kacem I,Hammadi S,Borne P.Approach by localization and multiob-jective evolutionary optimization for flexible job-shop scheduling prob-lems[J].IEEE Transactions on Systems,Man and Cybernetics,Part C,2002,32(1):408-419.

[4]Ponnambalam S G,Ramkumar V,Jawahar N.A multiobjective geneticalgorithm for job shop Scheduling[J].Production Planning and Con-trol,2001,12(8):764-774.

[5]梁迪,陶泽.多目标柔性作业调度的优化研究[J].计算机工程与应用,2009(15):223-226.

[6]蒋丽雯.基于遗传算法的车间作业调度问题的研究[D].上海交通大学,2007:43-46.

[7]冯红娟.基于遗传算法的车间作业调度问题的研究[D].长春理工大学,2008:29-31.

[8]刘天虎,许维胜,吴启迪.基于遗传算法的生产调度系统建模及优化[J].华东经济管理,2008(2):152-154.

[9]孙志峻,安进,黄卫清.作业车间多工艺路线批量作业计划优化[J].中国机械工程,2008,19(2):183-187.