一种模糊项目调度问题的变宽Beam Search算法

具有弹性约束和模糊工期的项目调度问题是一类具有实际应用意义但难于解决的问题.传统BS(Beam Search)方法存在常数线宽大小影响求解效果的问题.本文建立了此类项目调度问题的模型,并将序优化理论思想与BS方法结合,提出一种通过计算和改变线宽,兼顾解的质量和求解速度的变宽BS调度算法.仿真计算结果表明,该算法能够在较短时间内得到满意的调度结果,适用于实际模糊项目调度决策.

A New Codebook Design Scheme for Fast Beam Searching in Millimeter-Wave Communications

To overcome imperfection of exhaustive based beam searching scheme in IEEE 802.15.3c and IEEE 802.11 ad and accelerate the beam training process, combined with the fast beam searching algorithm previously proposed, this paper proposed a beam codebook design scheme for phased array to not only satisfy the fast beam searching algorithm's demand, but also make good use of the advantage of the searching algorithm. The simulation results prove that the proposed scheme not only performs well on flexibility and searching time complexity, but also has high success ratio.

A Novel Beam Search to Improve Neural Machine Translation for English-Chinese

Neural Machine Translation(NMT)is an end-to-end learning approach for automated translation,overcoming the weaknesses of conventional phrase-based translation systems.Although NMT based systems have gained their popularity in commercial translation applications,there is still plenty of room for improvement.Being the most popular search algorithm in NMT,beam search is vital to the translation result.However,traditional beam search can produce duplicate or missing translation due to its target sequence selection strategy.Aiming to alleviate this problem,this paper proposed neural machine translation improvements based on a novel beam search evaluation function.And we use reinforcement learning to train a translation evaluation system to select better candidate words for generating translations.In the experiments,we conducted extensive experiments to evaluate our methods.CASIA corpus and the 1,000,000 pairs of bilingual corpora of NiuTrans are used in our experiments.The experiment results prove that the proposed methods can effectively improve the English to Chinese translation quality.

APPLICATION OF BEAM SEARCH FOR THE DECODING OF ONE CLASS OF LDPC CODES

For one class of Low-Density Parity-Check(LDPC)codes with low row weight in theirparity check matrix,a new Syndrome Decoding(SD)based on the heuristic Beam Search(BS),labeledas SD-BS,is put forward to improve the error performance.First,two observations are made andverified by simulation results.One is that in the SNR region of interest,the hard-decision on thecorrupted sequence yields only a handful of erroneous bits.The other is that the true error pattern forthe nonzero syndrome has a high probability to survive the competition in the BS,provided sufficientbeam width.Bearing these two points in mind,the decoding of LDPC codes is transformed into seekingan error pattern with the known decoding syndrome.Secondly,the effectiveness of SD-BS dependsclosely on how to evaluate the bit reliability.Enlightened by a bit-flipping definition in the existingliterature,a new metric is employed in the proposed SD-BS.The strength of SD-BS is demonstrated viaapplying it on the corrupted sequences directly and the decoding failures of the Belief Propagation(BP),respectively.

A Beam Search-based Algorithm for Flexible Manufacturing System Scheduling

A new algorithm is proposed for the flexible manufacturing system (FMS) scheduling problem in this paper. The proposed algorithm is a heuristic based on filtered beam search. It considers the machines and automated guided vehicle (AGV) as the primary resources. It utilizes system constraints and related manufacturing and processing information to generate machines and AGV schedules. The generated schedules can be an entire scheduling horizon as well as various lengths of scheduling periods. The proposed algorithm is also compared with other well-known dispatching rules-based FMS scheduling. The results indicate that the beam search algorithm is a simple, valid and promising algorithm that deserves further research in FMS scheduling field.

基于Beam Search算法的集装箱装载问题研究

针对具有优先装载约束的集装箱装载问题,对Partial Beam Search算法进行了改进。在搜索过程中去除相似中间状态,增加了搜索过程的多样性,提高了算法的搜索效率。实验结果证明了算法的有效性。

Sequence optimization for multiple asteroids rendezvous via cluster analysis and probability-based beam search

It is of great significance to visit multiple asteroids in a space mission.In this paper,the multiple asteroids mission optimization is implemented using cluster analysis and probability-based beam search.Clustering is performed to select the first asteroid to visit.Four cluster algorithms are investigated and affinity propagation is selected.Then four beam search algorithms that are deterministic beam search and three probability-based beam search variants,probabilistic beam search,ant-colony beam search,and evolving beam search,are applied to search for the rendezvous sequence.Deterministic beam search as a heuristic tree search algorithm is widely applied in multitarget sequence optimization,but it has an obvious drawback of the conflict between the number of pruned nodes and the possibility of finding optimal solutions,which can be improved by probability-based beam search.Among three probability-based beam search,the ant-colony beam search has a learning mechanism,and evolving beam search is constructed based on ant-colony beam search and has an evolutionary mechanism.Results show that the introduction of randomness can improve beam search,and beam search variants with the learning and evolutionary mechanism have an excellent performance.

New reference trajectory optimization algorithm for a flight management system inspired in beam search

With the objective of reducing the flight cost and the amount of polluting emissions released in the atmosphere, a new optimization algorithm considering the climb, cruise and descent phases is presented for the reference vertical flight trajectory. The selection of the reference vertical navigation speeds and altitudes was solved as a discrete combinatory problem by means of a graphtree passing through nodes using the beam search optimization technique. To achieve a compromise between the execution time and the algorithm＇s ability to find the global optimal solution, a heuristic methodology introducing a parameter called ‘‘optimism coefficient was used in order to estimate the trajectory＇s flight cost at every node. The optimal trajectory cost obtained with the developed algorithm was compared with the cost of the optimal trajectory provided by a commercial flight management system（FMS）. The global optimal solution was validated against an exhaustive search algorithm（ESA）, other than the proposed algorithm. The developed algorithm takes into account weather effects, step climbs during cruise and air traffic management constraints such as constant altitude segments, constant cruise Mach, and a pre-defined reference lateral navigation route. The aircraft fuel burn was computed using a numerical performance model which was created and validated using flight test experimental data.

Filtered-beam-search-based approach for operating theatre scheduling

To improve the efficiency of operating rooms, reduce the hospital＇ s costs and improve the level of service qualities, a scheduling method is presented based on a filtered-beam-search-based algo- rithm. Firstly, a scheduling problem domain is described. Mathematical programming models are al- so set up with an objective function of minimizing related costs of the system. On the basis of the de= scriptions mentioned above, a solving policy of generating feasible scheduling solutions is estab- lished. Combining with the speeific constraints of operation theatres, a filtered-beam-search-based algorithm is put forward to solve scheduling problems. Finally, simulation experiments are designed. The performance of the proposed algorithm is evaluated and compared with that of other approaches through simulations. Results indicate that the proposed algorithm can reduce costs, and are of prac- ticality and effectiveness.

基于迁移学习的室内波束选择优化方法

使用基于深度学习的室内波束选择方法可以显著提高波束匹配概率和搜索效率,但该方法需要大型数据集来调整其大量可训练参数,导致了额外的系统开销。针对这一不足,结合一种迁移学习技术,使得目标场景神经网络以小数据集方式获得与大数据集相近的匹配精度,从而减小基于深度学习的波束选择方法中数据集大小对匹配结果产生的影响。首先使用大型数据集在一个源场景中对源神经网络进行充分训练,使得网络参数能够充分包含信道状态信息以及环境信息;而后利用源神经网络参数对目标场景中的神经网络进行不同程度初始化,使该神经网络在经过小数据集训练后依然可以获得较好的波束匹配性能。仿真结果表明,针对室内波束选择场景,在数据集有限的情况下,使用迁移学习方法进行波束选择,同样可以获得较高的匹配精度。

GAT-IL:一种基于图注意力网络与模仿学习的服务功能链部署方法

网络功能虚拟化通过将网络功能从专用硬件设备迁移到商用服务器上运行的软件中间盒中,简化了网络服务的配置和管理.在网络功能虚拟化的环境下,由一系列有序的虚拟网络功能组成的服务功能链正在成为承载网络服务的主流形式.将底层物理网络资源分配给服务功能链的需求称为服务功能链部署问题.对于基础设施提供商来说,在有限的资源条件下获得长期高回报是一个重要的挑战.本文形式化定义了服务功能链部署问题,提出了一种基于图注意力网络与模仿学习的服务功能链部署方法(Graph Attention Network and Imitation Learning,GAT-IL).该方法使用图注意力网络评估每个物理服务器的放置潜力,通过蒙特卡洛树搜索方法给出专家示范,并采用模仿学习方法进行智能体的训练,融入集束搜索策略优化解空间.大量的实验结果表明,本文提出的GAT-IL方法在平均收益代价比和接受率的性能指标上均优于现有代表性算法.

全局-局部信息增强的捆绑列表推荐

为解决捆绑列表推荐中会话兴趣表征不充分,以及预构建捆绑包不能根据会话动态兴趣进行个性化推荐的问题,提出一种全局-局部信息增强的捆绑列表生成网络。利用包含相对位置编码的时间加权多头注意力机制提取会话的全局信息,结合设计的多粒度深度可分离卷积融合会话的局部信息,通过自回归捆绑列表生成网络生成多样化的捆绑列表。在亚马逊数据集上进行广泛的实验,对生成捆绑包的大小进行分析,模型效果相比其它最优基准模型平均提升了15.19%。

基于IMGRU-Seq2seq的自动问答方法研究

针对传统问答模型采用循环神经网络带来的梯度消失和网络退化的问题,提出一种基于IMGRU-Seq2seq(Identity Mapping Gated Recurrent Unit-Sequence to Sequence)的自动问答模型。通过TF-IDF方法对文本进行加权词向量表示;以门控循环单元为基础,将批标准化技术和线性整流激活函数相结合并添加恒等映射,从而构建IMGRU模型;将双向IMGRU作为问答模型的语义抽取单元,引入注意力机制和集束搜索算法,实现自动问答。实验结果表明,所提方法比现有方法BLEU、ROUGE-L分别平均提高18.87%、4.35%。

基于优化的文档频和Beam搜索的特征选择方法

在文本分类中,特征空间的维数通常高达几万,甚至远远超出训练样本的个数,这是一种十分普遍现象。为了提高文本挖掘算法的运行速度,降低占用的内存空间,过滤掉不相关或相关程度低的特征,必须使用特征选择算法。首先给出了一个基于最小词频的文档频方法,然后把粗糙集引入进来并提出了一个基于Beam搜索的属性约简算法,最后把该属性约简算法同基于最小词频的文档频方法结合起来,提出了一个综合的特征选择算法。该算法首先利用基于最小词频的文档频方法进行特征选择,然后利用所提属性约简算法消除冗余,从而获得较具代表性的特征子集。实验结果表明该算法是有效的。

前向Beam搜索粗糙集属性约简算法

从属性集互信息的角度分析了粗糙集理论的属性约简问题。粗糙集属性约简通常采用 Best-first 启发式搜索。本文运用属性集互信息作为属性约简度量,提出了前向 Beam 搜索粗糙集属性约简算法。实验表明,属性约简算法具有良好的运行效果。

石英振梁加速度计温度自补偿方法

石英振梁加速度计在温变环境中存在输出漂移,文中采用一种新型软件补偿方法抑制温度漂移。该方法利用石英振梁自身谐振频率表征参考温度,并建立温度补偿模型。较于以温度传感器输出作为参考温度,该方法没有测温误差。在补偿算法上,提出一种基于麻雀搜索算法优化BP神经网络的温度补偿模型,能够克服BP神经网络易陷入局部最优的问题和提升补偿准确性。通过多次温度实验进行建模,对比补偿前后的输出值,零偏稳定性从392.8μg下降至65.5μg,证明该补偿方法的有效性。

面向薄壁复合梁结构的数据驱动计算均匀化方法研究

面向薄壁复合梁结构开展了数据驱动计算均匀化方法研究,构建了基于模型缩减技术的高效数据驱动多尺度模型.首先,在宏细观关联计算方面,基于数据驱动计算均匀化方法,解耦了传统计算均匀化框架中相互嵌套的宏微观尺度计算,取而代之的是“细观离线-宏观在线”的计算方案,即离线生成细观代表体元的应力-应变等效数据库,以驱动宏观模型在线计算,从而提升在线计算效率.其次,在宏观模型方面,基于Carrera统一理论构造薄壁复合梁结构的宏观降维缩减模型,以减少宏观模型的自由度数和积分点数.最后,在数据搜索方面,采用分层数据搜索方案替换遍历式数据搜索方式,以减少单次搜索的数据量.研究显示,结合模型缩减技术的数据驱动计算均匀化方法,可在保证精度的情况下提高数据驱动计算的效率,为快速预测薄壁复合梁结构多尺度力学行为提供了高效可靠的工具.

Beam-PSO优化算法在多行程车辆路径问题的应用

针对城市物流配送系统,研究了一类带时间窗和释放时间约束的多行程车辆路径问题。首先,对该运输调度问题进行了描述,构建了以总配送时长最小化为目标的数学模型。其次,为了快速获得问题的满意解,提出了Beam-PSO优化算法。在算法设计中,结合该问题的性质,构建了基于随机键的编解码方法,以克服标准粒子群算法无法直接适用于求解离散问题的不足。同时,设计了基于Beam search优化技术的局部搜索流程,用于强化算法的优化性能。最后,进行了仿真实验,实验结果表明了Beam-PSO优化算法的可行性和有效性。

Novel cued search strategy based on information gain for phased array radar

A search strategy based on the maximal information gain principle is presented for the cued search of phased array radars. First, the method for the determination of the cued search region, arrangement of beam positions, and the calculation of the prior probability distribution of each beam position is discussed. And then, two search algorithms based on information gain are proposed using Shannon entropy and Kullback-Leibler entropy, respectively. With the proposed strategy, the information gain of each beam position is predicted before the radar detection, and the observation is made in the beam position with the maximal information gain. Compared with the conventional method of sequential search and confirm search, simulation results show that the proposed search strategy can distinctly improve the search performance and save radar time resources with the same given detection probability.

基于规则集定向搜索算法的装船翻箱问题

集装箱码头的自动化与智能化是港口物流发展新趋势,其中箱区自动化与智能化是其中的重点。自动化集装箱码头纵向大箱区布局模式使其翻箱问题成为制约码头效率提升的一个重要因素。针对自动化码头大箱区的贝内装船翻箱问题,提出基于规则集快速求解方法,并基于该方法构建相应的分支定界算法和定向搜索算法,同时分析了3种算法的时间复杂度。分支定界算法可求得该问题理论最优解,定向搜索算法能在短时内获得接近理论最优解。算例分析表明,基于规则集定向搜索算法和分支定界算法在小规模算例中都能高效求解该问题。在大规模算例中,基于规则集定向搜索算法仍然具有很高计算效率,同时优化结果接近理论最优解。通过与现有文献的数据对比分析,表明本文提出的基于规则集定向搜索算法在求解集装箱装船翻箱问题时具有更好的优化效果和更高的计算效率。