雷达装备维修器材集装技术研究

多约束条件下的雷达装备维修器材装箱问题是一个复杂的组合优化问题,属于NP完全问题,其求解相当困难.为了解决雷达装备维修器材集装效率低的问题,该文在考虑实际应用的约束条件下,分析并建立了雷达装备维修器材优化装箱问题的模型,采用中间包装,空间分割,空间合并,抽屉分装等策略,提出了一种基于启发式算法的雷达装备维修器材装箱问题的解决方案.仿真实例及实际工作验证了算法的有效性和实用性,较好地解决了雷达装备维修器材的优化装载问题.     

求解单容器矩形装箱问题的混合算法

单容器矩形装箱问题是一个典型的组合优化问题,其在工业界有着广泛的应用。首先提出了一种新的启发式布局算法,即底部匹配算法,该算法在矩形的装入过程中根据五种启发式规则自动选择与装填区域相匹配的下一个矩形。然后将底部匹配算法与遗传算法相结合形成混合算法来求解单容器矩形装箱问题。实验结果表明,与已有算法相比,该文提出的算法更加有效。     

三维装箱问题的偏随机密钥混合遗传算法

考虑实践约束的三维装箱问题属于复杂的组合优化问题,具有典型NP难问题的特点。针对一般遗传算法求解装箱问题易陷入局部最优的缺点,提出使用偏随机密钥遗传算法进行装载序列搜索,结合基于极点的启发式方法实现货物的优化布置,进而通过部分装载物品的位移来改善整体重心分布。经过实例运算和分析,证明提出的方法能快速制定货物优化布置方案,达到装载工具高效利用及货物安全运输的要求。     

基于分层和强化学习的改进路径搜索算法

复杂网络下的路径搜索问题是网络寻优中的一个难点。现有算法主要存在以下问题：一是往往只能侧重于求解效率和求解精度中的一点;二是对动态变化的复杂网络适应性不强,求解效果不佳。因此,本文提出一种基于双分层和优化Q-Learning的改进路径搜索算法。对于求解时间随规模增加而急剧增长的问题,提出k-core和模块度结合的双分层划分网络的策略,以合理有效地减小网络规模。在子网络求解中,引入强化学习机制对网络进行动态感知,针对算法收敛较慢问题,加入自适应学习因子和记忆因子,优化更新公式,提高收敛速度。最后,在不同幂律指数（2~3）和不同规模的复杂网络下,将所提算法与Dijkstra算法、A*算法和Qrouting算法进行实验对比,结果表明该算法在保证较好求解精度的情况下,能有效地改善求解效率。     

创建者序列重建问题MFL模型的改进算法

创建者序列重建问题即根据后代基因信息推断其祖先基因信息,最大片断长度问题(the Maximum Fragment Length problem,MFL)模型是求解该问题的有效模型.Roli提出一种求解MFL模型的构造性启发式算法,该算法通过0、1取值比例来确定创建者序列的取值,且通过引入随机信息来解决0、1等比例的情形,导致求解方案的不确定性.针对该问题,提出一种有效的改进算法I-R-Heric,该算法充分利用重组体和创建者矩阵的列向0、1取值比例的相关性等启发式信息,对随机取值问题做出有效限定.实验结果显示,I-R-Heric算法能快速有效地求解MFL问题,并能获得较改进前算法更少的断点个数和更长的片段平均长度.此外,在重组体序列规模较大的情况下,I-R-Heric仍具有较高的执行效率,有很好的实用价值.     

离散Jaya算法的复杂网络社区发现

社区结构是复杂网络的重要特性之一, 基于模块度的复杂网络社区发现问题是一个NP难度的组合优化问题, 常用启发式算法求解. 最近出现的Jaya算法是求解连续优化问题的一种简单有效的元启发式方法. 本文在遵循Jaya算法按靠近最好解、远离最差解的方式更新种群个体的基础上, 针对复杂网络社区发现问题给出了Jaya算法离散化的策略, 提出一种复杂网络社区发现的离散Jaya算法. 实验表明, 在几个典型真实网络实例和一类人造网络实例上, 与几个经典算法和元启发式算法相比, 本文算法具有求解精度高、能自动确定社区数目等优点.     

基于强化学习的车辆路径规划问题研究

从机器学习的角度理解,车辆路径规划问题(VRP)可转化为单代理有限状态空间的强化学习问题进行研究.针对小规模VRP问题,提出时间差分模型,使用Sarsa和Q-learning算法进行优化.针对大规模VRP问题,构建环境模型,通过蒙特卡洛法优化代理策略和值函数.在公开数据集上的实验结果表明,强化学习能有效求解小规模VRP问题,并在大规模VRP问题上超过一般的启发式算法.     

用神经网络启发式算法求解最大独立集问题

本文提出一种求解最大独立集问题(MIS)的启发式神经网络算法.该算法基于MIS问题的特点,有效地限制神经网络初始点的选择范围,并利用神经网络快速收敛能力获得问题的解.与标准神经网络算法相比,该算法显示了较高的全局优化性态与计算效率.模拟计算实例表明了该算法的有效性.     

基于多起点和Mask策略的深度强化学习算法求解覆盖旅行商问题

覆盖旅行商问题(covering salesman problem, CSP)是旅行商问题的变体,在防灾规划、急救管理中有着广泛应用.由于传统方法求解问题实例耗时严重,近年来深度神经网络被提出用于解决该类组合优化问题,在求解速度和泛化性上有明显的优势.现有基于深度神经网络求解CSP的方法求解质量较低,特别在大规模实例上与传统的启发式方法相比存在较大差距.针对上述问题,提出一种新的基于深度强化学习求解CSP的方法,由编码器对输入特征进行编码,提出新的Mask策略对解码器使用自注意力机制构造解的过程进行约束,并提出多起点策略改善训练过程、提高求解质量.实验结果表明,所提方法对比现有基于深度神经网络的求解方法进一步缩小了最优间隙,同时有着更高的样本效率,在不同规模和不同覆盖类型的CSP中展现出更强的泛化能力,与启发式算法相比在求解速度上有10～40倍的提升.     

用于求解旅行商问题的深度智慧型蚁群优化算法

启发式算法是求解组合优化问题求解的重要手段,其主要特征是能够以可接受的计算代价找到足够好的可行解.然而,设计良好的用于求解组合优化问题的启发式算法需要大量的专业领域知识以及大量的试错工作,且人工设计的启发式算法不能够保证在不同问题集上均具有一致性表现.另一方面,深度学习方法能够通过学习自动设计启发式规则,然而深度学习方法通常缺少在解空间内搜索的能力.为克服以上问题,提出了一种基于蚁群优化和深度强化学习的混合启发式算法框架.在该框架中,蚁群算法能够利用深度强化学习提取的启发式信息,而深度强化学习方法的解空间搜索性能也由于蚁群算法的加入而获得提高.采用经典的TSPLIB中的算例对该算法求解旅行商问题的效能进行了计算验证,结果表明采用深度学习方法能够极大地提升蚁群算法的计算表现,并降低其计算代价.     

带平衡约束矩形布局优化问题的深度强化学习算法

带平衡约束的矩形布局问题源于卫星舱设备布局设计,属于组合优化问题。深度强化学习利用奖赏机制,通过数据训练实现高性能决策优化。针对布局优化问题,提出一种基于深度强化学习的新算法DAR及其扩展算法IDAR。DAR用指针网络输出定位顺序,再利用定位机制给出布局结果,算法的时间复杂度是O（n³）;IDAR算法在DAR的基础上引入迭代机制,算法时间复杂度是O（n⁴）,但能给出更好的结果。测试表明DAR算法具有较好的学习能力,用小型布局问题进行求解训练所获得的模型,能有效应用在大型问题上。在两个大规模典型算例的对照实验中,提出算法分别超出和接近目前最优解,具有时间和质量上的优势。     

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.     

基于深度强化学习的多配送中心车辆路径规划

多配送中心车辆路径规划(multi-depot vehicle routing problem, MDVRP)是现阶段供应链应用较为广泛的问题模型,现有算法多采用启发式方法,其求解速度慢且无法保证解的质量,因此研究快速且有效的求解算法具有重要的学术意义和应用价值.以最小化总车辆路径距离为目标,提出一种基于多智能体深度强化学习的求解模型.首先,定义多配送中心车辆路径问题的多智能体强化学习形式,包括状态、动作、回报以及状态转移函数,使模型能够利用多智能体强化学习训练;然后通过对MDVRP的节点邻居及遮掩机制的定义,基于注意力机制设计由多个智能体网络构成的策略网络模型,并利用策略梯度算法进行训练以获得能够快速求解的模型;接着,利用2-opt局部搜索策略和采样搜索策略改进解的质量;最后,通过对不同规模问题仿真实验以及与其他算法进行对比,验证所提出的多智能体深度强化学习模型及其与搜索策略的结合能够快速获得高质量的解.     

求解三维装箱问题的混合模拟退火算法

提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟退火算法.三维装箱问题要求装载给定箱子集合的一个子集到容器中,使得被装载的箱子总体积最大.文中介绍的混合模拟退火算法基于三个重要算法:(1)复合块生成算法,与传统算法不同的是文中提出的复合块不只包含单一种类的箱子,而是可以在一定的限制条件下包含任意种类的箱子.(2)基础启发式算法,该算法基于块装载,可以按照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础,将装载序列作为可行放置方案的编码,在编码空间中采用模拟退火算法进行搜索以寻找问题的近似最优解.文中采用1500个弱异构和强异构的装箱问题数据对算法进行测试.实验结果表明,混合模拟退火算法的填充率超过了目前已知的优秀算法.     

A least wasted first heuristic algorithm for the rectangular packing problem

The rectangular packing problem is to pack a number of rectangles into a single large rectangular sheet so as to maximize the total area covered by the rectangles packed. The paper first presents a least wasted first strategy which evaluates the positions used by the rectangles. Then a random local search is introduced to improve the results and a least wasted first heuristic algorithm (LWF) is further developed to find a desirable solution. Twenty-one rectangular-packing instances are tested by the algorithm developed, the experimental results show that the presented algorithm can achieve an optimal solution within reasonable time and is fairly efficient for dealing the rectangular packing problem. LWF still performs well when it is extended to solve zero-waste and non-zero-waste strip packing instances.     

A hybrid differential evolution algorithm for multiple container loading problem with heterogeneous containers

We consider a multiple container loading problem, commonly known as the three-dimensional bin packing problem (3D-BPP), which deals with maximizing container space utilization while the containers available for packing are heterogeneous, i.e., varying in size. The problem has wide applications in cargo transportation, warehouse management, medical packaging, and so on. We develop a differential evolution (DE) algorithm hybridized with a novel packing heuristic strategy, best-match-first (BMF), which generates a compact packing solution based on a given box packing sequence and a container loading sequence. The effectiveness of the proposed algorithm is evaluated on a set of industrial instances and randomly generated instances. The results show that the proposed algorithm outperforms existing solution approaches in terms of solution quality.     

面向人机物三元数据的热轧调度问题研究

随着钢铁行业的数字化发展,其订单逐渐趋于多样化和随机化,这对热轧调度模型的适应性和灵活性等提出了新的要求.针对热轧调度问题,当前的主流方法是启发式算法,但其存在两个问题:一是没有考虑数据的组织表示;二是此类算法具有很强的针对性,当问题发生很小的改变就需要进行复杂的参数调整.相比之下,机器学习具有更好的适应性和灵活性,对此,采用本体进行人机物三元数据的组织表示,提出一种指针网络$+$强化学习的热轧调度求解方法.采用指针网络来学习序列到序列的映射,同时为解决指针网络训练困难和性能不高等问题,通过actor-critic网络进行训练,提高模型的准确性和收敛速度.最后,通过设计相应的实验对算法的性能进行仿真并与LK-H的局部搜索算法进行对比,进一步验证了所提出方法的有效性.     

Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

基于知识图谱和Bi-LSTM的推荐算法

目前现有基于模型的推荐算法多是将评分数据输入到深度学习模型中进行训练,得出推荐结果。其缺陷在于无法对预测结果进行可解释性分析。除此之外,无法有效地解决算法的冷启动问题。因此,本文提出一种基于知识图谱和Bi-LSTM的推荐算法,来有效解决算法的可解释性和冷启动问题。首先将获取到的数据集进行预处理,生成预编码向量,根据数据集结点的连接性,构建专业领域知识图谱。其次利用知识图谱的元路径提取技术获取到多条用户-物品路径信息,将其输入到Bi-LSTM中,在路径经过的各结点处加入一层注意力机制,目的是为了模型能够有效地获取到较远结点的信息。最后将多条路径的训练结果输入到平均池化层中,用以区分不同路径的重要程度,利用交叉熵损失函数对模型进行训练,从而得出预测结果。实验结果表明,与传统基于循环神经网络模型的推荐算法相比,该算法可有效地提升算法的可解释性以及预测准确性,并缓解算法的冷启动问题。     

基于改进最低水平线方法与遗传算法的矩形件排样优化算法

传统的最低水平线方法用于矩形件排样时可能产生较多未被利用的空白区域,造 成不必要的材料浪费。针对此缺陷,在搜索过程中引入启发式判断,实现空白区域的填充处理, 提高板材利用率。在应用遗传算法优化矩形件排样顺序时,在进化过程中采用分阶段设置遗传 算子的方法,改善算法的搜索性能与效果。通过改进最低水平线方法与基于分阶段遗传算子的 遗传算法相结合,共同求解矩形件排样问题。排样测试数据表明,所提出的矩形件排样优化算 法能够有效改善排样效果,提高材料利用率。