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

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

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.

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.

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.

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

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

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.

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 algorithm.Firstly,a scheduling problem domain is described.Mathematical programming models are also set up with an objective function of minimizing related costs of the system.On the basis of the descriptions mentioned above,a solving policy of generating feasible scheduling solutions is established.Combining with the specific 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 practicality and effectiveness.

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

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

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

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

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

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

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种算法的时间复杂度。分支定界算法可求得该问题理论最优解,定向搜索算法能在短时内获得接近理论最优解。算例分析表明,基于规则集定向搜索算法和分支定界算法在小规模算例中都能高效求解该问题。在大规模算例中,基于规则集定向搜索算法仍然具有很高计算效率,同时优化结果接近理论最优解。通过与现有文献的数据对比分析,表明本文提出的基于规则集定向搜索算法在求解集装箱装船翻箱问题时具有更好的优化效果和更高的计算效率。

5G NR同频多beam检测方法

5G NR与LTE有诸多方面的不同,较突出的变化就是SSB内PSS序列和SSS序列设计与LTE明显不同,而且在每个SSB突发内会有多个SSB,多个SSB的出现增加了小区搜索的难度。由于频谱资源匮乏,所以采用同频方式组网,但因此相邻小区之间也会产生干扰,影响检测效率。同频检测技术就是专门解决小区间干扰问题的一种技术。5G NR的小区搜索方法不可能同LTE一样,现有的小区搜索技术无法解决5G NR的小区搜索问题。为了解决这一问题,本文优化了传统的小区搜索算法,设计并实现了一种5G NR同频多beam检测算法,较好的满足了小区搜索高性能和实时性的需求。仿真结果表明,在AWGN信道环境下,该算法的性能良好,同频多beam检测能力很强。

An Efficient Character-Level Adversarial Attack Inspired by Textual Variations in Online Social Media Platforms

In recent years,the growing popularity of social media platforms has led to several interesting natural language processing(NLP)applications.However,these social media-based NLP applications are subject to different types of adversarial attacks due to the vulnerabilities of machine learning(ML)and NLP techniques.This work presents a new low-level adversarial attack recipe inspired by textual variations in online social media communication.These variations are generated to convey the message using out-of-vocabulary words based on visual and phonetic similarities of characters and words in the shortest possible form.The intuition of the proposed scheme is to generate adversarial examples influenced by human cognition in text generation on social media platforms while preserving human robustness in text understanding with the fewest possible perturbations.The intentional textual variations introduced by users in online communication motivate us to replicate such trends in attacking text to see the effects of such widely used textual variations on the deep learning classifiers.In this work,the four most commonly used textual variations are chosen to generate adversarial examples.Moreover,this article introduced a word importance ranking-based beam search algorithm as a searching method for the best possible perturbation selection.The effectiveness of the proposed adversarial attacks has been demonstrated on four benchmark datasets in an extensive experimental setup.

基于transformer的维汉神经机器翻译

神经机器翻译在许多任务上已取得了不错的效果,然而在低资源语种上的效果并不理想。针对这一问题,该文提出一种基于transformer的维汉机器翻译模型,该模型在transformer的基础上引入了循环机制和时间编码,使模型具有更好的泛化性和计算效率,同时在模型的输出端采用了beam search优化,针对模型的输出存在谐音字、混淆音字等问题采用了字粒度的语言模型困惑度进行评判。实验采用BLEU作为评价指标,实验表明,在少量维语与汉语的平行语料库的基础上,该文提出的改进transformer维汉机器翻译模型能够取得更好的效果,BLUE值提升了0.93%。

一种基于多任务学习的代码补全方法

针对基于语言模型的代码补全方法忽略源代码中结构信息和命名信息而导致补全准确率偏低的问题,提出一种基于多任务学习的代码补全方法(multi-task learning code completion, MTLCC)。MTLCC对源代码数据集进行数据清洗和预处理,通过抽象语法树(abstract syntax tree, AST)提取源代码中的结构信息和命名信息;构建基于Transformer的多任务学习网络,采用软参数共享学习方式分别对源代码的节点类型预测、节点值预测和语句预测进行训练;利用集束搜索对模型推理结果进行后期处理生成代码补全建议列表。实验结果表明,与Pointer network、LSTM+TransformerXL和CodeGPT中最好的模型相比,MTLCC在节点类型预测和节点值预测任务中的准确率分别提升了2.5%和1.7%、MRR分别提升了3.7%和2.4%,在语句预测任务中的ROUGE-L分数(L@4)提升了0.055。

面向5G毫米波通信中基于深度图搜索的波束干扰协调

在毫米波(Millimeter Wave,mmWave)通信中,波束成形(Beam Forming,BF)技术使得小区间的干扰模型不同于工作在低频带的情况,小区间干扰(Inter-Cell Interference,ICI)的影响随着小区密度的增加而增加.为了解决毫米波小区间波束干扰研究中较多的信道状态信息反馈的开销和较高的计算复杂度问题,以时隙调度波束为基础设计了多个小区的波束调度算法.首先针对相邻的毫米波小区在同一时隙向同一边缘用户进行服务会产生较差的传输质量这一特征,构建了波束冲突矩阵.其次充分考虑用户需求的不同服务时隙数量,不同的小区波数数量,小区链路数有限等限制条件,提出了一种基于深度图搜索的波束干扰协调算法.仿真结果表明:所提算法能够明显降低波束碰撞的数量,提高信噪比,改善网络和速率.