Study on the Hungarian algorithm for the maximum likelihood data association problem

A specialized Hungarian algorithm was developed here for the maximum likelihood data association problem with two implementation versions due to presence of false alarms and missed detections. The maximum likelihood data association problem is formulated as a bipartite weighted matching problem. Its duality and the optimality conditions are given. The Hungarian algorithm with its computational steps, data structure and computational complexity is presented. The two implementation versions, Hungarian forest （HF） algorithm and Hungarian tree （HT） algorithm, and their combination with the naYve auction initialization are discussed. The computational results show that HT algorithm is slightly faster than HF algorithm and they are both superior to the classic Munkres algorithm.

Improved Hungarian algorithm for assignment problems of serial-parallel systems

In order to overcome the shortcoming of the classical Hungarian algorithm that it can only solve the problems where the total cost is the sum of that of each job, an improved Hungarian algorithm is proposed and used to solve the assignment problem of serial-parallel systems. First of all, by replacing parallel jobs with virtual jobs, the proposed algorithm converts the serial-parallel system into a pure serial system, where the classical Hungarian algorithm can be used to generate a temporal assignment plan via optimization. Afterwards, the assignment plan is validated by checking whether the virtual jobs can be realized by real jobs through local searching. If the assignment plan is not valid, the converted system will be adapted by adjusting the parameters of virtual jobs, and then be optimized again. Through iterative searching, the valid optimal assignment plan can eventually be obtained.To evaluate the proposed algorithm, the valid optimal assignment plan is applied to labor allocation of a manufacturing system which is a typical serial-parallel system.

Multi-Objective Optimization of Time-Cost-Quality Using Hungarian Algorithm

In this paper, we propose an algorithm for solving multi-objective assignment problem (MOAP) through Hungarian Algorithm, and this approach emphasizes on optimal solution of each objective function by minimizing the resource. To illustrate the algorithm a numerical example (Sec. 4;Table 1) is presented.

An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem

In this paper we applicate the Hungarian algorithm for assignment problem to solve traveling salesman problem. Tree examples of application of algorithm are included.

激光雷达和相机的决策级融合目标检测方法

【目的】激光雷达与相机这两类传感器检测数据格式不统一、分辨率不同,且数据级和特征级的融合计算复杂度高,故提出一种决策级的目标融合检测方法。【方法】对激光雷达与相机的安装位置进行联合标定,实现这两类传感器检测结果的坐标系转换;利用匈牙利算法将激光雷达点云检测目标框和相机图像检测目标框进行匹配,设定目标框重合面积阈值,检测获得目标物的位置、类型等。【结果】实车测试结果表明,根据检测目标检测框长宽比选取不同交并比阈值的方法使得车辆和行人的目标识别准确率分别提升了3.3%和5.3%。利用公开数据集KITTI对所提融合方法进行验证,结果表明,在3种不同难度等级场景下,所提融合方法的检测精度分别达到了75.42%、69.71%、63.71%,与现有常用的融合方法相比,检测精度均有所提升。【结论】这两类传感器的检测目标框重合面积阈值对决策级融合检测结果影响较大,根据检测目标检测框长宽比选取不同阈值可有效提升车辆和行人的目标识别准确率。决策级融合方法能准确匹配雷达和相机的检测目标,有效提升目标检测精度。

协同上下行链路的频谱资源分配方案

传统蜂窝网络采用固定的频谱资源分配方式,导致频谱利用率低且无法满足用户高速和高质量通信需求。针对这种局限性提出了一种将分布式天线系统(Distributed Antenna System,DAS)与终端直通(Device to Device,D2D)通信技术相结合的策略。首先,该方案提出协同上下行链路(Uplink and Downlink Collaboration,UADC)的资源分配算法,并构建了以最大化系统总效率为目标的非线性规划问题。然后,将该问题分为最佳功率选择和信道分配2个子问题,同时利用匈牙利算法为D2D对选择最佳信道。最后,在MATLAB仿真平台进行实验。仿真结果表明,相比于仅复用上行链路的和仅使用DAS系统的方法,所提方案的频谱效率更高。

利用改进匈牙利算法求解旅行商问题

针对传统的匈牙利算法在求解旅行商问题(travelling salesman problem,TSP)时会导致多回路闭合的问题,提出了破环机制,设计了破环匈牙利算法。通过采用分配问题的描述方法对旅行商问题进行建模,并建立二者之间的转换关系,论证了TSP可行解的充分必要条件是对应分配问题的可行解与辅助边结合后仅包含一个环路,对6个标准旅行商进行测试和对比分析,验证算法的有效性。实验结果表明:在不同的数据集中,改进匈牙利算法能有效求出TSP问题的解。

基于红外图像处理的移动目标识别跟踪算法

为解决红外热像仪在战场环境多变、背景复杂、目标运动速度过快等情况下难以对目标进行识别与跟踪的问题,本文提出了一种基于红外图像处理的移动目标识别跟踪算法。该算法主要分为移动目标的检测和跟踪两部分。首先采用高斯背景建模方法来提取运动目标,其次应用Kalman滤波来进行运动目标的定位与跟踪,最后通过匈牙利算法来判定目标点的归属。实验结果表明,在MOT基准挑战中的评价指标上,本文算法相比于Sort跟踪器将MOTA提升了1.4%,MT提升了11.9%,ML降低了6.5%,IDs降低了33.3%,FN降低了13.6%,提高了跟踪准确性,成功实现了对多个移动目标的跟踪。本文算法在军事领域具有广泛的应用前景。

改进关联策略的三维多目标跟踪算法

为提高基于激光雷达的三维多目标跟踪准确度,提出一种基于检测的3D多目标跟踪算法。使用深度神经网络从激光点云中获取目标的位置信息后,对目标跟踪算法中的关联策略进行了优化。首先,估计出目标的速度信息,与位置信息一同纳入观测值,在BEV视角下使用卡尔曼滤波器对目标的状态进行预测与更新;然后,基于目标与激光雷达的距离来评估目标位置的不确定度,用于修正观测模型中的协方差矩阵;最后,在马氏距离中添加对目标测量的不确定性加权项,使用匈牙利算法进行数据关联。在大规模自动驾驶数据集Nuscenes上对所提算法进行了测试,得出其跟踪精度超过了现有的基线方法。消融实验结果表明,所提出的改进措施能有效提高三维多目标跟踪的性能。

车联网中基于进化策略算法与匈牙利算法的资源分配策略

为了提高车联网中高清地图下载业务的吞吐量和降低车队行驶业务的传输时延,提出一种基于进化策略算法和匈牙利算法(Evolutionary Strategy Algorithm and Hungarian Algorithm,ES-HA)的网络切片资源分配策略。构建增强型移动带宽(Enhanced Mobile Broadband,eMBB)切片和高可靠低时延(Ultra Reliable&Low Latency Communication,uRLLC)切片,根据eMBB用户和uRLLC用户功率之间的函数关系求得最佳功率,采用ES算法获得两种用户的最佳带宽,并使用HA实现最佳信道匹配。仿真结果表明,与基于集群的资源块共享和功率分配(Cluster-based Resource Block Sharing and Power Allocation,CROWN)算法、基于基准算法的资源分配策略在总吞吐量、传输任务时延、链路容量及最小吞吐量方面进行对比,该策略在满足车到基础设施(Vehicle to Infrastructure,V2I)链路用户高容量需求的同时,能够提高下载业务的吞吐量和降低车队行驶业务的传输时延。

基于加权窗口特征的多目标火力集中分配和动态调整算法

针对现有的火力打击规划方法在战前筹划时存在局部收敛性和全局优化能力差、缺乏对战中调整的临机处理和时效性考虑等问题,提出了基于加权窗口特征的火力集中分配和动态调整算法。首先,建立了基于加权窗口特征的分配模型以量化打击效益和资源代价,从而适应对不同作战需求的火力分配;然后,针对算法参数敏感和先验知识缺失的问题,提出了一种自适应参数的基于密度的聚类算法,可自适应寻优参数选择;最后,考虑到战中调整的实时性需求,提出了改进匈牙利算法以减少代价矩阵的迭代次数。试验表明,该算法能够有效解决战前规划和战中调整问题,且在大规模数据集上表现出比其他方法更加优越的性能,验证了该算法的有效性和灵活性。

单机流式货架系统中双命令操作的生成方法

单机流式货架系统作为经典流式货架系统的一种,具有高存储密度、高空间利用率等特点。其存储单元被设计成狭窄的U型,使得入库端和出库端位于同一个工作面彼此相邻的位置。存取机可以采用单命令模式和双命令模式执行入库作业和出库作业。文章根据匈牙利算法,为单机流式货架系统生成双命令操作序列,并通过仿真实验验证匈牙利算法生成双命令操作的有效性。

基于需求密度预测的网约车集约化调度方法

为提升网约车接单率和利润率、实现全局供需平衡,提出一种基于需求密度预测的网约车集约化调度方法。首先,根据历史数据设计基于多层混合感知野的深度时空残差感知网络结构,该网络基于需求频度划分历史时空数据,并通过卷积指数线性网络及残差单元对不同时空数据进行差异化处理。结合基于门控机制的融合及求和融合方法动态聚合时间、空间和外部特征,实现了对需求密度的准确预测,从而预估网约车需求密度集群效益。其次,基于网约车经济效益和需求密度集群效益,建立调度数学模型,设计传感邻域限制调度范围,提升搜索效率。将遗传算法与匈牙利算法相结合,提高算法寻优能力,避免基因缺失,通过改进选择和变异算子,增强遗传算法的局部随机搜索能力,规避早熟风险,从而得到网约车与乘客的最佳匹配结果,保证了全局供需平衡和总体盈利能力。最后,基于大规模真实数据集对预测模型的性能和调度算法的有效性进行验证,实验结果表明,预测模型精度可达到97%,调度算法的求解质量可达最优解的99%,可为网约车平台提供调度策略,保障交通系统稳定。

匈牙利算法在多目标分配中的应用

在多目标攻击决策中 ,根据 Harold提出的目标优势函数 ,分析了使所有目标机的总优势函数为指派问题 ,运用匈牙利算法对 n对 n的最优目标分配指派问题进行求解 ,并把它推广至 n对 m的多目标分配中。仿真结果表明匈牙利算法对于此类多目标分配指派问题的求解是十分有效的。

求解指派问题的一次性分配算法

匈牙利算法是求解指派问题的全局最优求解算法,但是经典的匈牙利算法存在着实现难、处理速度慢等不足。提出了一种改进匈牙利算法,对匈牙利算法寻找独立零的次序进行了改进,从而避免了匈牙利算法通常需要进行多次试分配的不足。针对改进前后两种算法的复杂度、运算时间、精确度等进行了对比分析,结果表明,改进的算法是一种高精度的近似最优求解算法;与匈牙利算法相比,改进的算法易于编程实现,且时间花费较低,是一种适用于工程实时应用的有效求解算法。

图像分割的谱聚类集成算法

针对谱聚类算法对尺度参数敏感的问题,利用集成学习算法良好的鲁棒性和泛化能力,提出了一种无监督集成学习算法——谱聚类集成算法.该算法先利用谱聚类的内在特性产生集成学习所需的多个聚类个体,再采用Hungarian算法对生成的聚类个体进行重新标记,计算每个样本点关于每一个类别所占的比例,得到一个成分向量,然后运用对数比变换将所得的成分向量映射到另一个空间,去除成分数据的不适定性,最后对映射后的数据进行聚类,从而得到最终的集成结果.通过对UCI数据集和纹理图像的仿真实验表明,所提算法的聚类准确率与常用的共识函数具有一定的可比性,且运算代价较小,所需时间大约为MCLA算法的一半,同时避免了精确选择谱聚类算法的尺度参数.

基于模糊关系的人力资源管理工作分配算法

工作分配是人力资源管理的一项重要职能,经典的工作分配算法建立在考核明确和任务性质相同的基础上,正因为如此所以限制了其实际工作中的应用。基于模糊关系的工作分配算法对经典的工作分配算法进行了扩展,通过建立工作满意程度的模糊集和员工个体能力矩阵,应用匈牙利法求解工作分配方案。

基于本体和二部图的网格服务发现算法研究

为了提高网格服务发现的查全率、查准率和效率,论文设计了一个基于本体和二部图的网格服务发现算法OGSDA-BG。该算法把请求服务和发布服务的属性集分别作为二部图顶点集,所有匹配属性之间的连线为边,边权是属性匹配度,把问题转换为二部图的最优完全匹配。实验结果表明该算法的查全率和查准率较以前的算法提高了10%￣50%,尽管服务发现的效率降低10%左右,但是在可接受范围之内。

基于改进匈牙利算法和模糊逻辑控制的Interbay物料运输系统调度方法

为了满足晶圆制造Interbay物料运输调度的多目标和实时性要求,提出了一种基于改进匈牙利算法和模糊逻辑控制的智能调度方法.首先对晶圆工件的运输时间、等待时间、交货期以及加工特性这4个参数进行加权求和,建立晶圆工件的多目标运输成本模型;然后基于模糊逻辑控制的权重参数调节模型对各个权重参数进行动态调整,进而实时地计算晶圆工件的运输成本;最后以最小化运输成本为目标,采用改进匈牙利算法求取晶圆工件和运输小车的最优匹配方案.仿真实验结果表明,与传统的几种单一启发式规则比较,提出的调度方法能够有效减少晶圆工件的平均搬运时间和平均加工周期,具有较好的综合调度性能.

基于投资方角度的项目融资风险分配研究

从风险分担问题的博弈分析出发,探讨项目融资风险分配的最优原则。分析项目融资的风险类别和利益相关者,利用模糊层次分析法,建立项目融资各参与方的风险矩阵,按照风险最优分配原则,使用匈牙利法对风险矩阵求解,为各类风险确定最优承担者。