一种求解IPPS问题的混合遗传迭代邻域搜索优化算法

针对最小化最大完工时间的工艺规划与调度集成问题,设计并研究一种混合遗传-迭代邻域搜索优化算法。首先考虑到兼具工序柔性、序列柔性和加工柔性的问题特质,采用三层染色体编码方式,同时考虑到可行解集过大,运用结合启发式规则分配法的种群初始化方式;其次,考虑遗传算法更侧重于全局优化,引入迭代邻域搜索对遗传算法较优解进行局部搜索,并通过多次迭代后最优解仍保持不变时引入新种群进行竞争的策略,避免陷入局部最优陷阱;最后通过与已有算法对已知案例的求解结果进行比较分析,发现本算法得出最优结果优于绝大多数的优良算法,随后采用某飞机制造公司某工位为背景构建的实际案例进行验证,说明了该算法的有效性。

车辆路径问题的快速多邻域迭代局部搜索算法

对于容量约束的车辆路径问题（ capacitated vehicle routing problem, CVRP）以及容量和最大行驶距离约束的车辆问题（ capacitated and distance constrained vehicle routing problem, CDVRP）,邻域解的评估包含了适应值计算及合法性评估.设计一种可变长编码的可行解表示,提出用于CVRP/CDVRP问题的邻域解合法性快速评估策略.该策略针对交换、插入、2-opt和2-opt？四种常用的局部搜索算子,通过引入前载重、后载重、前向距离和后向距离的概念,实现了邻域解合法性的快速评估.将改进后的局部搜索算子与迭代局部搜索（ iterated local search, ILS）算法相结合,提出用于车辆路径问题的快速多邻域迭代局部搜索（ fast multi-neighborhood ILS, FMNILS）算法.该快速评估策略将评估一个邻域解的时间复杂度由O（ N）降至O（1）,算法仿真结果表明, FMNILS算法运算能力的提高大致与配送路线所服务的客户数成正比；对客户数介于200~500的容量/最大距离约束VRP问题,该算法能在短时间内获得较满意解,平均求解精度1．2%以内,平均耗时约96 s,仅为对比算法的6%或更少.

一种新的博弈树迭代向前剪枝搜索

针对博弈树迭代加深搜索和向前剪枝搜索中误剪最佳分支的弱点,利用向前剪枝搜索与预评估搜索间的双重迭代调用,提出了一种新的博弈树迭代向前剪枝搜索方法.预评估搜索通过节点排序及调整剪枝比率可以更加准确地选取排序在前的最佳分支,进而使迭代向前剪枝搜索实现在预评估所保留的最佳分支方向进行深度搜索,二者迭代相互调用以提高向前剪枝搜索的有效性及效率.定性分析与中国象棋计算机博弈实验结果表明,迭代向前剪枝搜索提高了实时行棋决策的效率和效果,与α-β剪枝搜索相比,提高的搜索效率超过160倍,同时取得了胜负比近7倍的博弈效果.

校车路径问题的改进迭代局部搜索算法

针对考虑站点服务时间、学生最大乘车时间约束的校车路径问题(SBRP),提出一种改进迭代局部搜索(ILS)算法以提升求解质量。该算法使用大规模邻域搜索(LNS)算法作为扰动算子;在解的破坏过程中,设计一组解的破坏因子并赋予一定的选择概率,每隔若干次迭代后根据解的质量自适应更改破坏因子的选择概率,进而调整解的破坏程度。为提升ILS解的多样性,算法采用了基于偏差系数的邻域解接受准则。在国际基准测试案例上进行了测试,测试结果表明在ILS算法中使用自适应调整破坏程度的LNS扰动比常规扰动和其他破坏扰动的求解质量有大幅提升;与蚁群算法的比较结果进一步验证了改进算法的有效性。

选择-验证-过滤:一种迭代的子图包含查询处理机制

近年来,图模型广泛应用于生物信息、计算化学、语义网等领域.目前,"过滤-验证"机制被广泛用于子图包含查询,即首先根据图数据的特征构造索引,然后根据索引产生候选集,最后对候选集中的每一个图进行子图同构验证.在这类算法中,"过滤"阶段是关注的重点,力争过滤掉更多的数据;而"验证"阶段则只是单纯地进行候选图子图同构检测,并没有进一步优化查询性能的可能.因此,提出了一种新的子图包含查询的迭代处理机制:"选择-验证-过滤",可利用从子图同构验证过程中得到的信息,结合数据库中图数据之间的相关关系,进行迭代查询处理.该机制首先选择数据库中的图与查询图进行同构验证,然后根据本次验证得到的信息,结合图数据之间的子图映射关系,进行迭代查询处理.一旦子图同构验证成功则可直接获得查询结果,而若验证不成功,则可以缩小下次迭代的查询搜索空间.为提高验证成功概率,提出了一种基于搜索空间预测的图选择策略.大量实验表明,该算法具有较"过滤-验证"机制更高的查询处理性能.

基于优化迭代的博弈树算法

博弈是诸如下棋、打牌、战争等一类竞争性智能活动的通称。通过对机器博弈的研究衍生了大量实用的研究成果。分析当今国际上主流的加快博弈树搜索效率的算法,根据它们的优缺点建立一种基于优化迭代的新算法,并且通过实验数据证明算法的优势。

凸二次规划的一种宽邻域预估-校正算法

Zhao对线性规划提出了一种基于邻近度量函数最小值的宽邻域预估-校正算法,并证明了算法的多项式复杂性。基于他的思路,将此方法拓展到凸二次规划,设计了一种新的基于邻近度量函数最小值的宽邻域预估-校正算法。由于新算法的迭代方向向量Δx,Δs不再满足正交性,因此算法的收敛性分析不同于线性规划的情形,同时也证明了新算法具有已知的最好迭代复杂性O (n^(1/2)ln〔((x0)Ts0/ε)〕,初步数值实验验证了算法的有效性。

单调线性互补问题的宽邻域预估-校正内点算法

基于邻近度量函数的最小值,对单调线性互补问题提出了一种新的宽邻域预估-校正算法,在较一般的条件下,证明了算法的迭代复杂性为O(n^(1/2)log(x0)Ts0/ε).该算法可视为最近Zhao提出的线性规划基于邻近度量函数最小值的宽邻域内点算法的推广.

考虑转炉容量和宽度的炉次计划混合优化方法

炉次计划是炼钢-连铸批量计划的关键计划之一,主要功能是考虑如何充分利用转炉容量及板坯属性使用最少的炉次组织生产,其编制的好坏直接影响后续计划制定及各工序生产节奏.基于目前炉次计划模型存在无法分辨板坯宽度区间相交程度、炉容量利用效率及炉次内板坯间关系的不足及一维装箱理论没有考虑剩余箱子容量及箱子内物品间关系的问题,将炉次计划归结为考虑炉次剩余容量及板坯间关系的一维装箱问题,并建立数学规划模型.基于炉次计划模型解矩阵的特点及迭代局部搜索(iterated local search,ILS)和变邻域搜索(variable neighborhood search,VNS)的优点,提出了将VNS算法作为ILS算法中局部搜索的混合算法.最后利用现场实际数据对模型和算法的有效性进行了对比验证,结果表明炉次计划模型及混合算法是有效的.

大规模无等待流水调度问题的邻域迭代搜索算法

在分析大规模无等待流水调度问题特点的基础上,提出了利用相邻工件间完工时间距离求最小化完工时间的方法;通过研究工件插入和工件对的交换对最小化完工时间的影响,提出一种邻域迭代搜索算法,该算法降低了求解完工时间的时间复杂度,大大提高了算法效率;为避免算法在邻域搜索过程中陷入局部最优,将变邻域结构算法的思想应用于其中.仿真结果表明,所提出的算法能高效率解决大规模无等待流水调度问题,所得结果令人满意.

工业钣金件视觉检测中的一种2D-3D自动定位算法

利用图像计算目标物体空间方位一直是计算机视觉领域的重要任务。利用单幅图像结合CAD三维模型实现钣金零件空间方位的2D-3D自动定位。沿CAD三维模型在影像上投影的外轮廓统计影像边缘特征点的数目,根据极值位置确定零件方位的初始参数;提出基于广义点理论的最邻近直线迭代的算法求取零件方位的精确值。为加快轮廓跟踪速度,也对经典的8-领域轮廓跟踪串行算法进行了并行优化。

多目标中间包计划模型及混合优化算法

中间包计划是重要的炼钢-连铸批量计划之一,其功能是在给定的炉次计划中,根据炼钢-连铸生产能力及下游工序生产所需材料的数量,挑选出待生产的炉次并制定出合理的中间包使用数量及每个中间包内生产的炉次.在对中间包计划问题描述的基础上及现有文献中未考虑中间包利用率及中间包内炉次宽度差异性,建立了多目标中间包计划数学模型.为了求解模型将模型分解为两个子模型,并针对两个子模型设计了迭代局部搜索算法(iterated local search,ILS)及变邻域搜索算法(variable neighborhood search,VNS)相结合的双层混合算法,考虑到中间包利用率及多目标权重对解的影响,在算法中加入了可调整模型参数的方法,最后用实际生产数据对模型及算法进行验证.

基于多主体收益的电-气综合能源系统协调规划研究

随着我国各种异质能源系统的发展建设以及对综合能源系统规划研究的深入,根据不同能源间多能互补的优势和特点研究最合理的综合能源系统规划方案,对于我国综合能源系统规划建设及可持续发展具有重要意义。提出了一种市场环境下计及多主体收益的电-气综合能源系统协调规划方法。首先,分别基于电力系统和天然气系统的特点及网络约束,构建相应的收益模型,进而结合电-气综合能源系统中的异质能源间的耦合机理分析,充分考虑各能源主体间的博弈关系,构建计及多主体收益的电力系统和天然气系统协调规划模型;然后,利用迭代搜索法求解该模型;最后,利用仿真算例对所提方法的正确性和有效性进行验证。

基于IVNS-ASPSO算法激增需求下第四方物流网络设计

近年来各大电商平台的不定期优惠活动导致需求激增的现象出现,激增需求下的网络设计问题成为了第四方物流(4PL)运作模式下一个新的挑战性问题。针对这一问题,基于对激增需求的刻画,建立了激增需求下4PL网络设计的数学模型。由于该问题的NPhard特性,采用自适应策略粒子群算法进行求解。并针对粒子群算法后期局部搜索能力不足,提出了迭代变邻域搜索策略,进而提出了嵌入迭代变邻域搜索的自适应策略粒子群算法,最后采用三组不同规模的算例进行仿真实验,验证了所提算法的有效性和优越性。

基于混合策略改进的贪心算法PSS订单调度研究

对于产品服务系统调度问题,本文提出了基于改进迭代贪心算法的PSS订单调度混合策略求解模型,大幅度缩短了所有订单的交付时间。运用NEH初始化方法对最早授权服务时间进行排序,引进随机邻域搜索算法,同时在贪心算法破坏和重建阶段进行优化,最后基于轮盘赌的比例筛选策略提出新的判断准则。通过仿真实验表明,本文所设计的混合改进策略对于求解订单调度问题的效果显著,求解速度更快,并表现出更好的鲁棒性。

考虑轮灌方式下的树状管网布局优化问题

农业用水短缺和用水粗放共存,水资源利用率亟待提高。灌溉管道网络是节水灌溉的重要发展趋势,但灌溉管网系统在设计时存在诸多难点。因此,对灌溉工程进行科学合理的规划设计,在满足灌溉需水量和各种液压条件下寻求管网总投资最小的方案,是提高灌溉效率和农业水资源利用率的重要手段。在轮灌方式下的管网布局优化问题中,轮灌组划分方式从根本上决定管网中的流量分布,从而影响管网布置、管网设计和管网总成本。考虑轮灌组容量限制、管道流量流速、工作压力水头等约束,以灌溉系统管道成本和电力成本之和最小作为目标函数,建立了同时考虑灌溉管道网络布置和管网设计的数学模型,并根据模型特点设计一种基于迭代邻域搜索的混合启发式算法进行求解。对一个实际灌溉工程进行优化,设置120、150和190 m^(3)/h三种不同轮灌组容量上限。结果表明,在工作方式方面,由于轮灌组的划分,导致灌溉网络系统工作时的总流量减少,降低管道管径和水源处泵站扬程,从而降低管道成本和电力成本;对于同一算例,灌溉管网的成本也会因轮灌组容量限制不同而存在差异;灌溉系统管道成本和电力成本之间存在效益背反。在管网设计时,需要根据灌区地形和节点分布特点,合理设定轮灌组容量上限和轮灌组划分方式,选择最为经济的管网设计方案。

零空闲流水车间问题中启发式规则的研究与改进

在流水车间问题中,通过启发式规则获得初始解的优劣是影响整体算法性能的重要因素。但目前被广泛使用的有效启发式规则(如NEH、FRB5等)都不能在获得初始解的质量和消耗CPU时间上取得平衡,在对这2种启发式规则研究后,改进了获得初始解时的邻域搜索,使改进的启发式规则在获得较好初始解的同时减少了CPU消耗时间,嵌入到迭代贪婪算法后提升了整体算法的性能。

基于准时制思想的炼钢—连铸生产动态调度算法

通过对炼钢—连铸生产动态调度问题的分析,建立了基于准时制思想的炼钢—连铸生产动态调度模型.提出了一种基于多个邻域结构和种群进化策略的进化迭代局部搜索算法,用于求解该模型.基于实际生产数据的仿真试验证明了所提出模型和算法的有效性.

车辆数限制的多车型校车路径问题模型及算法研究

为适应校车路径规划中校车有多种车型且每种车型数量受限的需求,建立车辆数限制的多车型校车路径问题(HFSBRP)的数学模型,并提出一种迭代局部搜索算法进行求解。该算法借助邻域随机选择的变邻域下降搜索(VND)算法完成局部提升。局部提升过程中,首先调整车型,然后再混合使用缩减路径数和提高车辆利用率的邻域解接受策略以提高算法的寻优能力,为保证解的多样性,允许接受一定偏差范围内的邻域解。此外,为避免算法过早陷入局部最优,设计了多点交换和移动的扰动规则。基于国际基准测试案例进行模型验证和算法测试,实验结果表明了模型的正确性和算法的有效性。

一种求解反应式项目调度问题的启发式方法

资源受限项目调度中的加权提前-拖期惩罚问题(weighted earliness-tardiness RCPSP,WET-RCPSP)存在于即时生产计划和反应式调度领域。考虑随机调度中的不确定性和随机性特征,采用符合问题特点的调度生成方案(schedule generation scheme,SGS),提出了求解随机环境中加权提前-拖期惩罚调度问题的基于迭代局部搜索(Iterated Local Search,ILS)的启发式方法,并将该方法应用于项目控制阶段的反应式调度过程。通过改变调度顺序和直接干预执行时间两种方式设计了4种局部搜索方法,并设计2种摄动方法跳出局部最优。通过对随机生成的问题实例的仿真实验对方法进行了验证。