加入收藏 | 设为首页 |

车探险问题的Memetic烟花算法

探险 时间:2020-11-28 浏览:
N-车探险问题来源于吉普探险[], 是一类资源分配问题, 它广泛应用于吉普加油[-]、航天器排列[]、沙漠穿行[]等领域.已有研究表明, 该问题等价于最优置换排序, 一般情形下是NP-hard问题[]. Fine等[]提出了吉普问题, 主要解决单个吉普车在燃油约束下如何在沙漠

N-车探险问题来源于吉普探险[], 是一类资源分配问题, 它广泛应用于吉普加油[-]、航天器排列[]、沙漠穿行[]等领域.已有研究表明, 该问题等价于最优置换排序, 一般情形下是NP-hard问题[].

Fine等[]提出了吉普问题, 主要解决单个吉普车在燃油约束下如何在沙漠中穿行使得往返距离最远[].随后, Phipps[]建立了该问题的动态规划模型, 分析了最优解的结构, 并给出了某些特殊情况下的最优解的单调性. Franklin等[]证明了吉普探险问题与航天器排列问题之间的等价性. Gale[]、Cao等[]和Hausrath等[]推广并研究了具有N辆车的吉普问题, 利用归纳法研究了吉普问题的最优序列及其结构性质. Imada[]则研究了2维吉普问题, 并探讨了learning robot自动求解该问题的可行性. Kuwata等[]在吉普问题基础上提出了一类新的探索问题, 分析了该问题的计算复杂性和近似算法.李晓亚等[]得到了最优车辆行驶顺序的必要条件, 并设计了O(n2)的多项式时间算法.

鉴于直接精确求解的复杂性, 对于一般情形的N-车探险问题, 研究人员主要关注如何设计高效的近似算法和启发式算法求解该问题.例如, Li等[]研究了N-车探险问题的最优结构, 并提出了两种实时贪婪启发式算法.徐扬扬等[]建立了N-车探险问题的非线性混合整数规划模型, 在此基础上提出了-近似算法.更进一步, Xu等[-]研究了一类多任务N-车探险问题的算法复杂度, 结果表明该类问题为NPC问题.李晓亚[]将N-车探险问题转换为动态规划问题, 提出了一种基于启发式解的rollout算法. Wang等[]建立了混合整数规划模型与N-车探险问题的等价性. Liu等[-]分别利用贪婪算法、禁忌搜索等方法求解该问题, 并取得了较好的效果.然而, 目前关于N-车探险问题的研究大都集中在复杂度分析、贪婪算法、近似算法等, 尚未发现应用群智能优化算法求解N-车探险问题的研究工作.

烟花算法(FWA)是受烟花爆炸产生火花的启发而设计的一种群体协同优化算法, 具有操作简单、易于实现、全局搜索能力强等优点[].已有的实验结果表明, 烟花算法在11个测试函数上的性能优于标准PSO和克隆PSO等[-], 先后应用到作物施肥[]、配电网重构[]、桁架结构设计[]、旅行商问题[]、卫星调度[]和生产调度[]等领域.具体而言, Tan等[]研究了求解经典TSP问题的离散烟花算法, 该算法充分结合TSP的问题特征, 设计了2-opt、3-opt、2h-opt等邻域操作, 增强其局部搜索能力. Liu等\cite{25}针对卫星调度问题, 设计了基于插入、交换、反转等邻域操作增强烟花算法的局部搜索能力.曹磊等[]利用最大位置法对置换流水车间调度问题的解进行编码, 设计了锦标赛选择策略和混沌搜索策略增强算法跳出局部最优的能力.从已有研究来看, 应用烟花算法求解离散优化尤其是N-车探险问题的研究工作相对较少; 进一步, 为有效求解离散优化问题, 需结合问题特征设计邻域操作以增强烟花算法的局部搜索能力.

鉴于烟花算法的优点及其离散优化的研究工作较少, 本文提出一种融合局部搜索的Memetic烟花算法求解N-车探险问题.该算法分为两个阶段:

1) 全局搜索阶段, 该阶段对问题进行ROV编码, 引入动态爆炸半径, 使用烟花算法进行全局搜索;

2) 局部搜索阶段, 该阶段结合插入、交换和反转等邻域操作进行局部搜索, 以增强算法的局部搜索能力, 从而获得更优解.

值得一提的是, 本文首次尝试应用烟花算法求解N-车探险问题.

1 N-车探险问题

N-车探险问题是指:假定车辆1, 2, …, n携带燃油a1, a2, …, an, 单位耗油量为b1, b2, …, bn.所有车辆从S0=0出发同向直线行驶, 在行驶途中无法从外界加油, 但可以在途中停止等待, 并将燃油转移给其他车辆.问如何安排车辆行驶顺序, 使得其中一辆行驶最远, 且所有车都回到出发点S0.

参见, 定义行驶顺序π1 π2 … πn, πi πj(i < j)表示前面的车πi给后面的车πj供油.

图 1(Fig. 1)

车探险问题的Memetic烟花算法

图 1 车辆行驶序列π1 π2 … πn[]

记车辆πi的行驶距离为Sπi, 定义Sπ0=0, xπi=Sπi-Sπi-1, i=1, 2, …, n, 则xπi满足

(1)

将式(1)化简, 可知最远行驶距离Sπ=Sπn满足

(2)

因此, N-车探险问题等价于最优置换排列问题:给定数列(a1, b1), (a2, b2), …, (an, bn), 寻找1, 2, …, n的最优置换序列π=(π1, π2, …, πn), 使得式(2)中Sπ的取值达到最大.

显然, N-车探险问题的搜索空间大小为O(n!).对于小规模问题, 可使用暴力穷举法得到最优解; 而对于大规模问题, 则需要设计高效的近似算法[-].

2 求解N-车探险问题的Memetic烟花算法

本节首先介绍烟花算法; 然后给出Memetic烟花算法的编码策略、动态爆炸半径和局部搜索; 最后介绍Memetic烟花算法流程.

2.1 烟花算法概述

烟花算法[]是将每个烟花视为一个可行解, 通过爆炸操作对每个烟花在不同的爆炸半径内产生不同数量的火花实现邻域内的局部搜索, 并通过调整爆炸半径和火花数目实现全局探索和局部搜索的平衡.烟花算法包括爆炸算子、变异算子和选择策略.

2.1.1 爆炸算子

记烟花种群为X=[X1, X2, …, XN], N为种群规模, Xi为烟花i的位置, 适应度值为f(Xi).烟花Xi通过爆炸算子在爆炸半径Ai内产生Si个火花后的位置为

(3)

其中U为取值0或1的D维随机矩阵, D为变量维数.

以最小化问题为例, 根据烟花算法的基本思想, 适应度好的烟花在较小范围内聚集较多的火花, 适应度差的烟花在较大范围内分布较少的火花.因而, 烟花Xi的爆炸半径Ai和火花个数Si满足

(4)

其中: Amax, Ns分别为最大爆炸半径和火花总数, 是为避免分母为0而设置的一个很小的常数.

对于最大化问题, 将式(4)修正为

(5)

为控制爆炸产生过多或者过少的火花个数, 引入如下机制对火花个数进行控制:

(6)

其中: a、b为[0, 1]的常数, round为四舍五入取整函数.

2.1.2 变异算子

烟花算法采取变异算子进行高斯变异, 以增强烟花种群的多样性.在烟花种群中随机选取Ng个烟花, 按下式随机选择若干维数进行高斯变异:

(7)

其中: U为取值0或1的D维随机矩阵, D为变量维数; N(1, 1)为均值和方差均为1的高斯随机数; Zi为烟花i变异后的位置.

2.1.3 选择策略

由烟花、爆炸火花和高斯变异火花共同组成候选集合K, 从中选取N个烟花个体组成下一代烟花种群.最优烟花个体作为精英保留, 其余N-1个个体采用轮盘赌的方式选择, 其被选择的概率为

(8)

2.2 Memetic烟花算法 2.2.1 ROV编码

标准烟花算法用于求解连续优化问题, 而N-车探险问题的解空间是全部置换序列.鉴于此, 借鉴置换流水车间调度问题的编码策略, 采取基于随机键的ROV规则对N-车探险问题的解进行编码[].

如所示, 对于连续变量X=(x1, x2, …, xn), 其升序变量Y满足y1≤ y2≤…≤ yn.对于第i维变量xi, 找到j, 满足xi=yj, 并令πi=j, π=(π1, π2, …, πn)即为置换序列.

表 1(Table 1)

车探险问题的Memetic烟花算法

表 1 ROV编码的一个例子[]

j123

X0.70.20.5

π312

表 1 ROV编码的一个例子[]

在中, X=(0.7, 0.2, 0.5)的升序向量为Y=(0.2, 0.5, 0.7), 满足x1=y3, x2=y1, x3=y2, 可得到置换序列π1=3, π2=1, π3=2, 即置换序列为π=(3, 1, 2).

对于置换序列π=(π1, π2, …, πn), 采用如下方式将其转换为连续变量X=(x1, x2, …, xn)[]:

(9)

其中Xmin, Xmax为变量X的下界和上界.

2.2.2 指数下降的动态爆炸半径

根据式(5), 适应度高的烟花具有较小的爆炸半径和较大的火花个数.对于最优烟花, 其爆炸半径∝, 即产生最多火花的最优烟花的爆炸半径几乎为0, 产生大量相似的火花, 浪费了搜索机会.

直观上看, 爆炸半径Amax过大, 不利于算法的快速收敛; 爆炸半径Amax过小, 则难以更好地执行全局探索.合理的爆炸半径应满足:

1) 进化早期, 较大的爆炸半径能更好地执行全局探索;

2) 进化后期, 较小的爆炸半径促使算法在小范围内进行局部开发.

鉴于此, 本文提出如下动态爆炸半径A(t), 以增强全局探索和局部开发的平衡能力:

(10)

烟花i的爆炸半径更新为

(11)

其中t和T分别为当前迭代次数和最大迭代次数.

2.2.3 局部搜索

借鉴文献[]中Memetic算法的全局搜索和局部搜索互补增强思想, 本文引入中的3种邻域操作来增强烟花算法的局部搜索能力[-, ].

图 2(Fig. 2)