求解VRPBTW的变邻域搜索算法

以电子商务环境下物流配送为背景,建立了带有时间窗和回程载货约束的车辆路径问题优化模型,设计了改进的变邻域搜索求解算法.该算法采用改进的Braysy顺序插入法生成问题初始解,再根据变邻域搜索算法机制应用4种不同搜索范围的局域搜索算子对初始解进行改进.通过对多个算例的求解实验,并与采用一般流程的变邻域搜索算法进行比较,结果表明所提出的变邻域搜索算法的求解效果明显优于采用一般流程的变邻域搜索算法,是求解该类问题的有效算法.     

两级选址--路径问题的大规模邻域搜索模拟退火算法

针对目前越来越普遍的多级配送模式,建立以总成本最小为目标函数的两级选址-路径问题模型,并提出了大规模邻域搜索模拟退火算法进行求解.在模拟退火算法框架中,嵌入大规模邻域搜索过程,包含破坏、重组和局部搜索方法,从而进一步提高算法在解空间中构建邻域的范围.采用两级选址-路径问题标准算例对算法求解效果进行验证,并与标准模拟退火算法和国际已知最优解进行对比.结果显示,所建模型和算法正确有效,并且在求解大规模问题时算法能够取得相对更好的优化结果.     

非单调线性互补问题的宽邻域算法复杂度分析

研究非单调线性互补问题的宽邻域不可行内点算法.为减小算法的理论复杂度,通过两个牛顿方程分别计算两个搜索方向,再通过这两个搜索方向的凸组合,获得该算法的搜索方向.通过分析,该算法的复杂度与当前最好的宽邻域不可行算法的复杂度一致.     

基于VNS-EM混合算法的两阶段装配流水车间调度

针对以最小化工件提前期和拖期惩罚费用加权和为目标的两阶段装配流水车间调度问题,证明了工件之间的最优排序性质,并将其嵌入优化算法中.由于该问题的NP难性,提出了一种变邻域类电磁机制(VNS-EM)混合算法.该混合算法在类电磁机制(EM)算法的每一次迭代过程中嵌入改进的变邻域搜索(VNS)算法,利用其较好的局部搜索能力对每代最优个体的邻域进行精细搜索,从而提高解的质量.仿真结果表明了算法的有效性.与VNS算法和EM算法相比较,提出的VNS-EM混合算法能更好地兼顾算法的精度和求解速度.     

融合正域及边界质量的实域属性约简方法

基于邻域关系提出一种综合考虑正域和边界数据的属性约简方法.该方法利用邻域关系对数据进行离散化处理,通过定义基于邻域的正域属性重要度、边界属性重要度和邻域综合属性重要度概念,设计一种新的启发式属性简约算法.该算法从空约简集出发,利用邻域属性重要度启发式搜索属性空间以扩展约简属性集,理论分析和实验表明该算法有效可行.     

用和声搜索算法求解技术站列车解编方案

确定到达列车的解体顺序和出发列车的编组顺序(即列车解编方案)是技术站编组调机运用计划的核心问题.本文为解决该问题,构建相应的优化模型,利用结合邻域搜索的和声搜索算法进行求解,采用目标函数值评价新的和声,邻域搜索策略用于获取新的和声.最后利用算例对所设计算法的求解效率进行分析验证,表明:算法收敛速度较快,而与邻域搜索策略的结合,有利于扩展其搜索范围与提升全局搜索能力,降低对选择概率的依赖.通过对不同参数条件下计算时间的测试说明,所设计算法能够满足技术站编组列车解编方案编制的要求.     

交叉粒子群算法及其在天线设计中的应用

目的 为了求解解析性质差的复杂优化问题,提出了一种新的交叉粒子群算法.方法 该算法将全局邻域粒子群算法与局部邻域粒子群算法交叉使用,并采用适应度距离比确定局部邻域粒子群算法的速度更新策略.结果 提高了粒子群算法粒子的搜索能力.结论 该算法用来解决六边形阵列天线问题,取得了满意的效果.     

基于混合变邻域遗传算法的柔性车间调度研究

针对柔性作业车间调度的问题，以最大完工时间为目标建立数学模型，提出一种混合变邻域遗传算法。采用三种初始化方法保证初始解的质量，用遗传算法进行初步搜索，将搜索的结果通过迭代贪婪策略进一步搜索，以提高解的质量，再对关键路径进行邻域搜索，设计“跨机器工序搜索邻域”、“同机器工序搜索邻域”、“次优工序搜索邻域”三种邻域结构，加强局部搜索能力。引入迭代贪婪策略和改进的邻域结构可显著提高算法的稳定性与迭代速度。通过对国际通用的柔性作业车间调度基准算例进行测试，实验结果表明所提改进算法能够有效求解柔性作业车间调度问题。     

基于文化基因算法的集成工艺规划与调度研究

建立了与工艺规划集成的调度问题的数学模型.以最大完工时间为目标,设计一种混合文化基因算法求解该问题.在提出算法中,设计了新型编码和主动解码方案,使用变邻域搜索(VNS)算法进行局部搜索,引入了高效的邻域结构以强化算法的局部搜索能力,并提出了一种个体扰动方法,以避免群体多样性趋于单一,使得提出算法在分散搜索和集中搜索之间达到更合理的平衡.为测试算法的性能,对现有的基准问题进行了测试,有21个实例达到了下界或得到改进,成为当前新的最优解.对比已有的最优结果可见:提出的算法可高效地求解工艺规划与车间调度集成问题且优于其他算法.     

基于邻域分类AUC的属性选择方法

为了提升邻域分类器的分类性能,提出了一种利用邻域AUC作为分类性能度量指标的启发式是属性选择算法.首先,利用邻域分类器得到邻域AUC,然后在此基础上,借助贪心搜索策略,逐步加入使得邻域AUC尽可能大的属性,当邻域AUC不再增大时,算法终止.在7个UCI数据集上的实验结果表明,使用邻域AUC属性选择算法,可以在使用较少属性个数的基础上,有效地提升邻域分类器的分类性能.     

线性规划基于修正牛顿方向的宽邻域内点算法

通过修正经典宽邻域算法的搜索方向, 提出一种新的求解线性规划问题的宽邻域内点算法, 并对算法进行收敛性分析, 证明了该算法具有经典宽邻域算法的迭代复杂性界O(nL). 数值实验表明算法是有效的.     

基于差分进化算法的FMS中机器与AGV同时调度方法

针对柔性制造系统中机器与AGV（automated guided vehicle）同时调度问题，提出一种混合变邻域搜索的改进离散差分进化算法。以最大完工时间最小为优化目标，考虑机器与AGV双资源约束，建立相应的数学模型。为了同时调度机器与AGV，采用基于工序、机器、AGV的3层编码结构。通过改进差分进化（differential evolution，DE）算法的变异、交叉算子产生新个体以提高算法的全局搜索能力，并引入模拟退火算法中解的接受准则选择下一代。同时，为了增强算法的局部搜索能力，对算法每次迭代的最优个体进行变邻域搜索。通过算例计算和对比，证明了提出的改进DE算法的有效性、稳定性和优越性。     

求解流水车间调度问题的一种混合式遗传算法

讨论了如何将邻域搜索与遗传算法相结合求解流水车间调度问题,提出了一种邻域结构,使之更适合求解流水车间问题,设计了一种基于扩展采样空间的混合式遗传算法的框架,并通过计算机模拟验证其有效性。     

弧搜索内点算法

利用弧搜索内点算法对线性规划问题进行求解, 得到该算法的多项式复杂度为O(n^3/4L). 该算法在中心路径的一个宽邻域内, 沿椭圆近似寻找线性规划的最优解. 数值实验表明了该算法的有效性.     

求解非光滑优化问题的改进大洪水算法

应用启发式算法求解非光滑优化问题,解决基于次梯度信息的确定性算法在求解时困难较大的问题.首先分析了基本大洪水算法的优化机理及特征并给出其求解步骤,然后针对无约束及盒子约束问题分别设计了改进的大洪水算法,将基本大洪水算法所依赖的参数up省去.对于无约束情形,提出了进行邻域搜索的随机行走法;对于盒子约束情形,提出了选择初始可行点的方法和进行邻域搜索的混沌优化算法.最后通过算例进行测试并与其他算法进行对比,测试结果表明了改进的大洪水算法在求解非光滑优化问题时的有效性与优越性,故其可作为求解非光滑优化问题的一种实用方法.     

P*(κ)线性互补问题的预估-校正内点算法

通过修正大邻域跟踪算法的搜索方向, 提出一种新的求解P*(κ)线性互补问题(LCP)的不可行预估-校正内点算法, 并对算法进行了收敛性分析, 证明了该算法具有目前最好的理论复杂度O((1+κ)^5/2nL). 数值结果验证了算法的有效性.     

平面选址问题的萤火虫算法

平面选址问题是工程设计、线路布置、项目选址等工作中经常碰到的典型组合优化难题,根据群集智能优化原理,给出一种基于人工萤火虫群优化算法的求解方法,并针对平面选址问题进行求解.为避免算法陷入局部极值,将一种邻域搜索的局部搜索方法引入萤火虫算法中.通过对典型平面选址问题的仿真实验和与其它算法的比较,表明算法可行有效,且具良好的全局优化能力.     

一个改进的变邻域搜索方法求解k-card问题

本文将变邻域搜索算法应用到k-card问题求解中,重新定义了一种邻域结构,改进了算法,使得邻域内可行解的搜索速度得以加快,并提高了近似解的质量。对几个实际问题进行了数值实验,并与现有邻域结构的变邻域搜索算法进行了对比,实验结果证明了改进变邻域搜索算法对k-card问题的有效性。