一般复合均匀凸优化的强和稳定对偶

在广义凸共轭理论的基础和可分离的局部凸空间的条件下,利用扰动方法和c—共轭方法得到一般复合均匀凸优化问题的对偶问题,并在原问题的基础上再扰动一个连续线性泛函得到其稳定对偶问题.进而在一定的假设条件下,结合函数的均匀凸性,给出保证强对偶和稳定强对偶成立的正则条件.

基于有效限制邻域结构的禁忌搜索求解预算最大覆盖问题

针对预算最大覆盖问题,设计出一种基于有效限制邻域结构的禁忌搜索算法(Effectively Restricted Neighborhood Structure Based Tabu Search,ERNSBTS)对其求解。该算法主要由动态初始化、基于策略限制邻域结构和动态随机扰动重新初始化三部分组成。首先,提出构建剩余利润和剩余价值密度来生成好的初始解。然后,引入计数器G来记录当前解下元素覆盖次数,设计相对置空率和相对增益率两种策略来得到最有期望子集来限制邻域结构。最后,设计扰动程序,将贪婪与启发式思想相结合,考虑全局和局部的凸组合,以增加初始解的多样性。在数值实验中,分析了ERNSBTS算法参数设置,同时将其与近似算法、PLTS和VDLS算法的结果进行比较分析,证实了ERNSBTS算法在求解质量、计算效率和鲁棒性方面的高竞争力。

基于动态缩减机制的多策略单亲遗传算法求解CVRP问题

针对传统遗传算法求解带容量约束的车辆路径问题(CVRP)时存在易早熟、收敛速度慢、精度低等问题,提出一种基于动态缩减机制的多策略单亲遗传算法。基于同类个体实现对寻优空间的划分,采用模拟退火准则对最低类别子空间进行淘汰或更新,构成寻优空间的缩减和移动机制;基于单亲遗传算法,综合设计了组内、组间、整体搜索,以及扰动与跳跃的多种遗传进化策略;为适应度函数设计了基于个体发展、种群进化、整体收敛3个罚因子的自适应罚函数分量,对不可行解作出更有效惩罚。通过对3组CVRP问题实例进行仿真实验分析,结果表明:该算法在种群质量、全局与局部寻优能力、求解精度和收敛速度等方面均得到改善和提升。

多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

针对多车场带时间窗车辆路径问题(MDVRPTW),提出一种改良自适应大邻域搜索算法(IALNS)。首先,在构造初始解阶段改进一种路径分割算法;其次,在优化阶段利用设计的移除和修复启发式算子相互竞争择优选取算子,为各算子引入评分机制,采用轮盘赌方式选取启发式算子;同时,将迭代周期分段,动态调整各周期内的算子权重信息,有效避免算法陷入局部最优;最后,采取模拟退火机制作为解的接受准则。在Cordeau规范算例上进行实验,确定IALNS的相关参数,将所提算法求解结果与该领域其他代表性研究成果对比。实验结果表明,所提算法与变邻域搜索(VNS)算法的求解误差不超过0.8%,在某些算例上甚至更优;与多相位改进的蛙跳算法相比,算法的平均耗时减少12.8%,所提算法在绝大多数算例上运行时间更短。因此,验证了所提算法是求解MDVRPTW的有效算法。

求解逆变分不等式的二阶动力系统方法

在强单调和Lipschitz连续性的条件下,在Euclidean空间中提出了一种新的求解逆变分不等式的二阶动力系统方法。首先,给出了逆变分不等式解的存在性和唯一性。进一步地,改进了Vuong等构建的二阶动力系统,并以此来求解逆变分不等式,而且在Lipschitz连续性的条件下,该动力系统具有唯一强全局解。最后,利用在强单调和Lipschitz连续性的假设下逆变分不等式唯一解的误差界,来证明此条件下该动力系统的唯一强全局解是指数收敛的。

改进萤火虫算法求解多目标柔性作业车间调度

针对多目标柔性作业车间调度问题,以最小化最大完工时间、最小化机器总负荷、最小化机器最大负荷为目标,提出一种改进邻域结构的离散萤火虫算法。首先,采用多种策略相结合的方式初始化种群,提高算法初始解质量以及种群多样性;其次,通过改进关键路径的邻域结构并设计离散萤火虫算法的位置更新公式,以增强算法全局搜索和局部搜索能力;最后,将该算法应用于标准数据集,并将求解结果与其他算法进行对比,验证了所提算法的有效性。

改进蜉蝣算法求解工艺规划与调度集成问题

针对工艺规划与调度集成问题(IPPS),基于AND/OR析取图和“组合”的概念以最小化最大完工时间为优化目标建立数学模型;设计一种整数编码方案,该方案无需预先为工件生成加工路径,可同时处理工艺规划与调度问题,由于初始解对算法的寻优能力的影响,在种群初始化时考虑机器的负荷以提高初始种群的质量;解码时采用插空的方法生成活跃调度,以缩短工件整体的加工时间;离散蜉蝣算法实现求解IPPS,采用Metropolis准则接收较差的解,引入自适应因子提高算法的收敛速度,设计局部搜索算法提高算法的精度。最后通过大规模基准算例进行实验并与其他算法对比分析,验证该算法有较好寻优性能。

基于多态变异的单亲遗传算法解CVRP问题

针对遗传算法求解带容量约束的车辆路径规划问题(CVRP)时存在收敛速度慢、易早熟等问题,提出一种基于多态变异的单亲遗传算法(PM-PGA).将多种算子分组构成局部搜索、整体搜索和随机移动三种策略,使种群发生多态变异,增强种群多样性,提高寻优能力;采用个体浓度控制和Metropolis准则相结合的混合跳跃策略,避免陷入局部最优;为提高解的质量,设计了基于迭代次数和车辆超载量的自适应罚函数.选取CVRP问题算例进行仿真实验,结果表明PM-PGA算法在收敛速度和求解精度方面得到明显改善和增强.

改进最近邻算法求解多车场车辆路径问题

论文提出了一种改进最近邻算法用于求解多车场车辆路径问题(multi-depot vehicle routing problem,MDVRP)。为了求解问题解空间得到有效控制,融合最近邻算法与K-means算法的优势对客户进行较为合理的车场分配,将多车场车辆路径问题分解成多个单车场车辆路径子问题。在子问题的求解阶段,提出一种编解码规则,基于车辆装载量利用率得到提高,减少车场车辆路径长度,设计了全局优化策略,基于车辆内部客户访问顺序及车辆间客户改变导致路径长度变化,设计了局部优化策略,提出了随车辆服务客户数变化而变化的搜索策略,提高了算法的运行效率。在不同规模的问题和仿真实验上验证了所提算法的有效性。

近邻域搜索算法求解带容量约束的选址-路径问题

针对遗传算法求解选址-路径问题存在收敛速度慢、易早熟等缺点,提出了一种近邻域搜索算法(Nearest Neighbor Search algorithm,NNS)。首先,在构造初始解阶段利用贪婪策略产生初始种群,提高初始解的质量;其次,在交叉阶段采用复制交叉的方式,增强算法的全局搜索;最后,在突变阶段使用近邻域局部搜索过程。此外,还设计了种群管理方案,以促进遗传算法种群多样性。在2个基准集上进行了试验,结果表明,与GRASP、MAPM、LRGTS等算法相比,该算法不仅显著提高了收敛速度,而且具有较强的寻优能力。

求解多维背包问题的双决策交互差异算法

针对传统多维背包问题的求解算法存在的修复方式单一、种群动态适应性差等问题,提出一种双决策交互差异算法(DDEA)。融合自主学习思想,设计多维加权价值密度和相对价值概率指标,双重决策确定物品选择顺序,制定相应解的修复优化策略。采用双种群交互差异进化算法,设置主群和辅助群2个种群,种群间进行信息交互,提高种群多样性,避免陷入局部最优,提高算法寻优能力。主群实施差异进化机制,依照个体优劣依次划分为3个子群,分别按照特定方式进化,并在进化过程中完成与辅助群的交互,增强算法群智能性。引入刺激-响应机制,平衡算法的全局和局部搜索能力,并加入精英库协同寻优,加快算法收敛速度。仿真结果表明,DDEA算法可求出全部最优解,平均相对误差率为3.04×10-5,相比于同类算法降低2个数量级,有效提升了多维背包问题的求解精度、效率和稳定性。

一类拟单调变分不等式的惯性投影算法

2020年,Liu和Yang在Hilbert空间中提出了一种求解拟单调变分不等式的投影算法.该文介绍了一种新的惯性系数来加速Liu和Yang文中的算法,并在相同的假设条件下得到了算法的全局弱收敛性.数值实验表明适当选取参数后的惯性方法比Liu和Yang文中的算法有更少的迭代步数和计算机耗时.

一种求解非单调均衡问题的改进外梯度投影算法

在实Hilbert空间中提出了一种新的投影算法来求解非单调均衡问题.该算法所生成序列的全局弱收敛性不需要二元函数满足任何单调性条件,只需要相关的Minty均衡问题的解集非空.新算法节省了同类算法(简记为DHF)在下一迭代点的计算成本.并在与DHF相同的假设下证明了新算法所生成的序列具有全局弱收敛性.数值实验表明,从CPU时间的角度来看新算法比DHF算法效率更高.