花粉授粉机制在改进粒子群算法研究

2024-03-08曲鹏举

机械与电子 2024年2期

曲鹏举,何雪

(贵州理工学院工程训练中心,贵州贵阳 550025)

0 引言

随着“中国制造2025”概念的提出,柔性化制造对我国创新发展新技术起到了一定的促进作用,而柔性作业中的多目标优化问题也成为研究重点。

很多学者在柔性作业加工多目标优化方面进行了研究。朱光宇等[1]针对紧前工序对机床主件制造车间生产调度的影响,构建考虑运输时间的紧前约束下的四目标柔性作业车间调度模型,设计基于勾股模糊前景值最优觅食算法求解该调度模型;Agel等[2]为解决柔性作业调度问题,提出相较于其他算法更为简单高效的后启发式迭代贪婪算法;唐红涛等[3]针对加工时间不确定的模糊分布式柔性作业车间调度问题,在引入三角模糊数的基础上,提出了一种改进的灰狼优化算法以最小化最大模糊完工时间;李瑞等[4]针对同时考虑最大模糊完工时间和总模糊机器负载的双目标模糊柔性作业车间调度问题,提出了一种改进的基于分解的多目标进化算法;孟磊磊等[5]针对分布式柔性作业车间最小化最大完工时间问题,提出一种混合蛙跳算法;Meng等[6]针对柔性作业调度加工问题提出了一种基于区间决策变量和域滤波算法的高效约束规划(CP)模型。上述文献已经利用改进蚁群算法、贪婪算法、遗传算法等进行了研究,但是还没有粒子群算法结合Logistic与花朵授粉算法对柔性作业多目标优化问题的研究。

针对柔性作业中多目标优化问题,首先构建多目标任务满意度数学模型,该模型以最小加工时间、最低制造成本、最短运输时间为目标,去量纲操作后利用几何平均法求解综合满意度评价值;其次为了解决标准粒子群算法求解过程中收敛性缓慢、稳定性低、易陷入局部最优等缺点,提出一种改进的粒子群算法(Logistic chaotic map and flower pollination mechanism employed in particle swarm optimization,LFPSO),该算法通过改良粒子群算法的惯性权重平衡全局和局部搜索能力;同时,为增加粒子群前期的搜索性能,在惯性权重中加入了Logistic混沌映射丰富粒子多样性;再次,为平衡全局搜索能力与局部搜索能力,引入花粉授粉机制作为全局搜索阈值控制粒子群算法全局搜索和局部搜索的启动时间,最后通过仿真验证了算法的适用性。

1 数学模型构架

1.1 模型描述

柔性作业多目标优化问题定义:已知有n个待加工工件,在m台可用机器设备上进行加工,每个工件有m道工序需要加工,每个工件的加工工序以及加工耗时已知[7],在约束条件下,使加工时间、加工成本、储存成本最低。

表1 柔性作业多目标优化参数及评价指标

加工时间目标函数为

minFmax=min{maxTk}

(1)

式中:maxTk为第k号机器实际运行时间的最大值; minFmax为加工时间目标函数,表示所有设备最小完成时间。

制造成本的目标函数为

(2)

式中: minCT为所有加工工件的全部成本的最小值。

储存成本目标函数为

(3)

式中:minS为工件储存成本最小值。

1.2 满意度评价值构造

为综合考虑多目标加工问题加工满意度,将加工时间、制造成本和储存成本去量纲化操作,消除量纲不同对满意度评价值的影响,从而得到相应的去量纲化比值,计算过程如下:

(4)

(5)

(6)

式中:F0、C0、S0分别为目标函数加工时间、制造成本、储存成本去量纲化后的比值。

利用何平均法求解综合满意度评价值,即

(7)

式中:χ为综合满意度评价值,其大小直接反映了加工时间、制造成本、储存成本情况。

1.3 柔性作业多目标优化问题约束条件

加工约束条件为:

maxχ

(8)

minFmax

(9)

(10)

minCT

(11)

(12)

minS

(13)

S′≥S

(14)

Fijk-Fi(j-1)k≥Cijk

(15)

Cijk>0

(16)

Fabk-Fijm≥Cabk

(17)

Fijm≥Cijk

(18)

式(8)表示求解最大综合满意度评价值;式(9)、式(10)表示所有工件实际完成的时间必须在可接受最大加工时间之内;式(11) 、式(12)表示所有工件实际加工成本必须在可接受最大加工成本之内;式(13) 、式(14)表示实际储存成本必须在可接受最大储存成本之内;式(15)表示任意工序必须在其紧前工序完成之后进行;式(16)表示任意工序持续时间都不为0;式(17)表示任意工序的持续时间不能大于最后一道工序时长;式(18)表示任意工序加工时间都不少于预设定加工时长。

2 改进粒子群算法

2.1 标准粒子群算法

标准粒子群优化算法(particle swarm optimization,PSO)因其实现过程简单、设定参数少等特点在众多领域获得应用。标准的粒子群优化算法位置和速度状态属性为:

(19)

(20)

2.2 Logistic混沌映射改进

Logistic混沌映射具有普遍性和随机性的特点[8],为了增加粒子群算法粒子多样性,在粒子群算法中加入Logistic混沌映射可以丰富粒子种群数量。Logistic混沌映射公式为

αt+1=αt×σ(1-αt)

(21)

式中:αt为Logistic映射函数第t次迭代的值;σ为Logistic映射函数参数,σ∈(0,4)。

σ越小,αt随机性越差,随着迭代次数的增多,αt会逐渐趋于定值;σ越大,αt随机性越强,因此为了保证Logistic映射的随机性和多样性,在取值范围内,σ值越大越好,因此取σ=3.998,α0=1。

2.3 粒子群算法惯性权重幂函数改进

惯性权重ω是粒子群算法的重要参数,直接影响算法的收敛速度,改进惯性权重对算法有重要影响。为改进标准粒子群算法缺陷,提出惯性权重幂函数自适应调节方法,即

(22)

式中:ωmax为惯性权重最大值;ωmin为惯性权重最小值。

当ωmax=0.9,ωmin=0.4时,算法有较好的搜索性能。惯性权重幂函数自适应调节,在粒子群算法运行初期,可以扩大粒子搜索范围,加大粒子发散性;在算法后期惯性权重呈幂函数递减状态,能够快速局部寻优,提升算法效率。

2.4 花朵授粉机制的引进

花朵授粉算法(flower pollination algorithm,FPA)是一种启发式算法,具有全局授粉规则、局部授粉规则2种机制。全局授粉规则和局部授粉规则之间的转换通过FPA算法转换概率规则进行选择。如果转换概率p取值过大,算法长期处于全局搜索阶段,收敛速度过慢[9];如果转换概率p过小,算法过早陷入局部搜索,容易陷入局部最优,影响算法寻优能力[10]。

因此,在粒子群算法中引入花朵授粉算法进行粒子位置更新,同时引入概率转换规则控制粒子群算法的全局搜索和局部搜索之间转换阈值p,全局搜索规则为

(23)

莱维飞行公式为

(24)

转换阈值p为

(25)

式中: rand∈(0,1)为随机数;pmax为最大转换概率,pmin为最小转换概率,pmax=0.8,pmin=0.2;t为当前迭代次数;tmax为最大迭代次数,若rand≤p,则按照式(20)更新粒子位置,若rand>p,则按照式(23)更新粒子位置,通过转换阈值p实现了全局搜索和局部搜索的转换。

LFPSO算法流程如下:

a.通过式(1)～式(18)建立柔性作业多目标综合满意度评价模型。根据约束条件式(8)～式(18),并通过式(1)～式(3)建立目标函数加工时间minFmax、制造成本minCT和储存成本minS,根据式(4)和式(6)对3个目标函数去量纲化操作,在算法进化过程中不断记录3个目标函数及去量纲化比值,建立柔性作业多目标综合满意度评价模型。

b.设定改进粒子群算法参数,包括粒子数N、最大迭代次数tmax等。

c.根据式(21)在粒子群算法前期引入Logistic混沌映射。

d.根据式(22)改进粒子群算法惯性权重。

e.根据式(25),计算转换阈值p,并与rand进行比较,若rand>p,则粒子群算法按照式(23)进行全局搜索,若rand≤p,则按照式(20)进行局部搜索。

f.计算新解的适应度,并与当前解进行比较。

g.判定是否达到最大迭代次数,若t=tmax,输出当前最优解,并作为全局最优解;若t

LFPSO算法流程如图1所示。

图1 LFPSO算法流程

3 仿真验证

由于LFPSO算法为随机优化算法,为验证LFPSO算法的性能,对比LFPSO算法与经典PSO算法[11]、花朵授粉算法(FPA)[12]、惯性权重余弦自适应调节粒子群算法(CPSO)[13]和一维编码粒子群算法(HRPSO)[14]在求解6个测试函数与6个不同规模加工作业算例的表现。设备参数为Win10 64位Inter(R) Core (TM) i5-9400 @2.90 GHz RAM 8 GB MATLAB2014b。

3.1 求解测试函数

选取6个有代表性的测试函数,种群规模均为N=40,维度D=50,测试函数均是fmin=0时取得最优。测试函数信息如表2所示,结果如表3所示。

表2 测试函数信息表

表3 测试函数结果平均值

由表3可知,在6个测试函数的结果平均值中,LFPSO算法在4个测试函数f2、f4、f5和f6中都取得了最好的结果,HRPSO算法在f1和f4测试函数中取得了最优,CPSO算法在f3测试函数中取得了最优值,而PSO和FPA算法在6个测试函数中求得的最优值个数均为0。与其他4种算法相比,LFPSO算法在3个多峰函数中都求得最优结果,证明其在求解多峰函数问题上性能较好。

3.2 求解不同规模加工作业算例

选取6个不同规模加工作业算例,用LFPSO与其他算法求解对比,种群规模N=50,最大迭代次数tmax=500,不同规模加工信息对比结果如表4所示。

表4 不同规模加工信息对比

在6个不同规模的加工任务中,PSO算法在加工时间、制造成本、储存成本3个优化目标中都是最多的,其次是FPA算法,LFPSO算法在加工工件数和机器数较少的任务1和任务2中并没有体现出较大的优势,CPSO和HRPSO算法在任务1和任务2中优势比较明显,综合满意度值比较高;随着加工工件数和机器数的增多,在任务3～任务6中,LFPSO算法优势体现了出来,加工时间、制造成本、储存成本3个优化目标均为最优,综合满意度值也最高。

随着工件数和机器数的增多,加工任务规模增大,各算法求解时长不断增长,任务1中,求解时长最大的算法为PSO算法(8.6 s),最短的是HRPSO算法(8.0 s)和LFPSO算法(8.0 s),时间差率(时间差率=(最大求解时长-最小求解时长)/ 最大求解时长)为6.98%;任务2中,求解时长最长的算法为PSO算法(15.7 s),最短的是LFPSO算法(14.2 s),时间差率为9.55%;任务3中,求解时长最长的算法为PSO算法(24.3 s),最短的是LFPSO算法(19.6 s),时间差率为19.34%;任务4中,求解时长最长的算法为PSO算法(49.7 s),最短的是LFPSO算法(37.7 s),时间差率为24.14%;任务5中,求解时长最长的算法为PSO算法(77.3 s),最短的是LFPSO算法(60.9 s),时间差率为23.80%;任务6中,求解时长最长的算法为PSO算法(139.7 s),最短的是LFPSO算法(106.8 s),时间差率为23.55%。

在综合满意度和求解时长的分析中,任务1和任务2中LFPSO算法优势没有体现出来可能是因为LFPSO算法采用了Logistic混沌映射,粒子发散性多样性比较好,在加工任务数量少的时候,启动耗时较多,而随着加工任务的增多,算法运行时间显著增加,LFPSO算法在求解柔性作业多目标优化问题的优势体现出来。综合满意度值和迭代次数如图2所示。