Troubleshooting algorithm for solving assignment problem and its applications

A new troubleshooting algorithm for solving assignment problem based on existing algorithms is proposed, and an analysis on the related theory is given. By applying the new troubleshooting algorithm to the Lagrange relaxation algorithm of the multi-dimensional assignment problem of data association for multi-passive-sensor multi-target location systems, and comparing the simulation results with that of the Hungarian algorithm which is the classical optimal solving algorithm, and the multi-layer ordersearching algorithm which is a sub-optimal solving algorithm, the performance and applying conditions of the new algorithm are summarized. Theory analysis and simulation results prove the effectiveness and superiority of the new algorithm.

FGAs-Based Data Association Algorithm for Multi-sensor Multi-target Tracking

A novel data association algorithm is developed based on fuzzy geneticalgorithms (FGAs). The static part of data association uses one FGA to determine both the lists ofcomposite measurements and the solutions of m-best S-D assignment. In the dynamic part of dataassociation, the results of the m-best S-D assignment are then used in turn, with a Kalman filterstate estimator, in a multi-population FGA-based dynamic 2D assignment algorithm to estimate thestates of the moving targets over time. Such an assignment-based data association algorithm isdemonstrated on a simulated passive sensor track formation and maintenance problem. The simulationresults show its feasibility in multi-sensor multi-target tracking. Moreover, algorithm developmentand real-time problems are briefly discussed.

Polynomial-Time Assignment-Based Cell Association with Generic Utility Functions

Cell association is a significant research issue in future mobile communication systems due to the unacceptably large computational time of traditional schemes.This article proposes a polynomial-time cell association scheme which not only completes the association in polynomial time but also fits for a generic optimization objective function.On the one hand,traditional cell association as a non-deterministic polynomial(NP)hard problem with a generic utility function is heuristically transformed into a 2-dimensional assignment optimization and solved by a certain polynomial-time algorithm,which significantly saves computational time.On the other hand,the scheme jointly considers utility maximization and load balancing among multiple base stations(BSs)by maintaining an experience pool storing a set of weighting factor values and their corresponding performances.When an association optimization is required,a suitable weighting factor value is taken from the pool to calculate a long square utility matrix and a certain polynomial-time algorithm will be applied for the association.Comparing with several representative schemes,the proposed scheme achieves large system capacity and high fairness within a relatively short computational time.

Multiple targets vector miss distance measurement accuracy based on 2-D assignment algorithms

An extension of 2-D assignment approach is proposed for measurement-to-target association for improving multiple targets vector miss distance measurement accuracy. When the multiple targets move so closely, the measurements can not be fully resolved due to finite resolution. The proposed method adopts an auction algorithm to compute the feasible measurement-to-target assignment with unresolved measurements for solving this 2-D assignment problem. Computer simulation results demonstrate the effectiveness and feasibility of this method.

New optimal algorithm of data association for multi-passive-sensor location system

In dense target and false detection scenario of four time difference of arrival （TDOA） for multi-passive-sensor location system, the global optimal data association algorithm has to be adopted. In view of the heavy calculation burden of the traditional optimal assignment algorithm, this paper proposes a new global optimal assignment algorithm and a 2-stage association algorithm based on a statistic test. Compared with the traditional optimal algorithm, the new optimal algorithm avoids the complicated operations for finding the target position before we calculate association cost; hence, much of the procedure time is saved. In the 2-stage association algorithm, a large number of false location points are eliminated from candidate associations in advance. Therefore, the operation is further decreased, and the correct data association probability is improved in varying degrees. Both the complexity analyses and simulation results can verify the effectiveness of the new algorithms.

无源定位系统的多目标数据关联算法

主要研究多目标无源定位系统的数据关联方法。数据关联实质上是求解后验概率的极大值,首先建立两传感器三维空间联合关联概率数学模型,将求解后验概率的极大值问题转化为求解特殊的指派问题。由于漏检和虚警的存在,导致指派个数不确定,提出了一种新的改进单亲遗传算法来求解该问题,该遗传算法将解阵看作一个个体,将矩阵的列看作个体的基因,始终对一个个体进行交叉和变异操作。仿真结果表明,提出的求解方法收敛速度快、关联正确率高,验证了模型和求解方法的正确性和可行性。

多传感器多目标数据互联中的拉格朗日松弛算法研究

拉格朗日松弛算法在现代优化启发式算法中占有重要地位，本文对多维分配问题的拉格朗日松弛算法进行研究，重点研究松弛次序对数据互联结果的影响。研究方法是针对不同测量误差情况下进行计算机仿真实验。结果表明，多传感器多目标数据互联的拉格朗日松弛算法中，松弛探测效果较好的传感器的观测数据，有助于提高目标关联的准确率，且算法的计算量相应减少。该结论使多维分配问题的拉格朗日松弛算法能满足工程上对数据进行实时处理，具有实际应用价值。

雷达与被动传感器数据关联算法研究

异类传感器的信息融合问题是一个重要而又困难的研究课题。针对雷达与ESM(ElectronicSupportMeasurement)的航迹关联问题,提出基于位置和属性单一信息的单目标规划模型,在此基础上,构建基于位置与属性联合信息的多目标规划算法模型,然后将多目标规划问题转化为单目标规划问题进行求解,并将其求解结果与仅根据来自位置或属性单一信息进行数据关联的单目标规划问题的实验结果进行比较。仿真结果表明,新算法的目标正确关联概率明显提高,是雷达与ESM数据关联的一种新的有效算法。

多被动传感器多目标数据互联算法

将求解指派问题的行列启发式算法应用于求解多传感器多目标数据互联的广义3D分配问题松弛的2D子问题;针对3D分配算法计算量较大的问题提出一种改进算法.仿真结果表明,行列启发式算法不仅实施方便,而且程序运行时间较短.改进的3D分配算法既大幅度降低了3D分配问题的拉格朗日松弛算法的程序运行时间,又可将目标互联准确率提高3%～5%.行列启发式算法与改进的3D分配问题算法联合使用,可进一步减少改进3D分配算法的运算量,使其能更好地适应工程实际应用的需要.

多传感器数据融合中的多目标静态数据关联

本文研究了无杂波和漏检的情况下三种不同类型、不同位置的传感器对数目未知的目标进行检测时的静态数据关联问题.这一问题可以通过对测量划分的联合似然函数的极大化来解决,通常可将其转化为三维匹配问题,但其求解的复杂度是NP的.本文提出了一种基于遗传算法的优化算法,来解决三维匹配问题,实验结果表明这种算法具有很高的关联成功率.

三站无源定位系统数据关联算法

全局最优量测数据关联算法是无源定位技术中的关键问题。针对三站无源定位系统全局最优数据关联的三维(3-D)分配问题,提出一种新的直接求解算法——启发式消元算法。该算法通过直接对代价矩阵的元素进行启发式消元,得到分配问题的最优解。给出算法相关原理的分析和证明以及算法的具体步骤。并将其应用于三部光电被动传感器多目标无源定位系统两级数据关联算法的第二级关联过程中,对启发式消元算法和求解3-D分配问题的近似最优求解算法——拉格朗日松弛算法的算法复杂性进行了分析对比。理论分析和仿真实验均表明,该算法较适合与两级关联算法联合使用。与拉格朗日松弛算法相比,该算法计算量小,便于实现,是一种新的、有效的全局最优数据关联算法。

产品数据管理中任务指派问题的模型和算法

产品数据管理(product data management,PDM)中的任务具有紧前约束、可拆分特性和时间窗.为了使有限的设计资源得到合理利用,建立了产品数据管理中任务指派问题的数学模型,其目标是总项目工期最短,任务拆分次数最少和任务中断时间最短.设计了一种基于贪婪准则的遗传算法对模型进行求解,对遗传算法的染色体编码方案和解码规则,适值函数和遗传算子等进行了详细说明.最后给出了一个应用实例,验证了模型和算法的有效性.

雷达与红外传感器异地配置下的数据关联

为解决异地配置的雷达和红外传感器数据关联问题,建立了数学模型将数据关联问题转化成运筹学中的分配问题。分析了经典的匈牙利算法存在的缺点,结合代价矩阵的特点,提出了求解分配问题的一种新的算法——差额法。该算法在代价矩阵差额最大的行或列中优先寻找最小元素,符合全局优化思想。算法简单易懂,克服了经典的匈牙利解法实现难、处理速度慢等缺点。实际应用表明,本文数据关联模型以及差额法适合于处理背景杂波不太强和目标不太密集情况下的异地多传感器数据关联问题。

基于DNA计算的多维分配数据关联算法①

针对多目标跟踪中的多维分配数据关联这一NP难题，将DNA计算用于数据关联研究，利用DNA分子链生化反应的高度并行性，实现了基于DNA计算的多维分配数据关联算法。该算法利用包含限制性内切酶HaelII回文序列的DNA分子链对观测：视线进行编码，通过连接和退火操作获得所有目标关联组合，然后利用检测DNA发夹结；陶和凝胶电泳技术排除不满足约束条件的目标关联组合，筛选出多维分配数据关联的最优解。分析结果表明：基于DNA计算的多维分配数据关联算法所需的DNA分子链数即空间复杂度为O（nk!／（c-m）!），将多维分配问题的指数级复杂度降低到多项式复杂度O（mn），其中n为传感器数，m为目标数，k为目标定位点数。

基于一维测量的多传感器多目标数据关联

本文在S-D分配算法的基础上,提出一种基于一维测量数据的多基地雷达多目标数据关联的方法。在每个传感器仅能给出目标的一维距离和量测信息,并且同时存在虚警的条件下,该方法首先利用4维组合的冗余信息对各传感器的量测值进行组合筛选,然后由4维分配算法进行多目标的数据关联,仿真结果表明该方法可以有效提高多目标的正确关联概率。

基于多维分配模型的多站时差数据关联

针对多个地面机扫辐射源目标关联问题,提出一种基于多维分配模型的多站时差数据关联方法。通过对辐射源机扫时差特性和多站间时差相关性进行分析,建立多站时差数据关联多维分配模型,利用贪心策略对该模型产生的组合优化问题进行快速求解以获得多目标粗关联关系对,并采用人工免疫算法对粗关联结果进行修正,生成优化后的系统关联关系对。该关联方法可作为电磁信号参数关联方法的有效补充,在辐射源参数存在混叠而难以区分时实现多站间多目标关联,完成同一性确认。仿真结果验证该模型和求解方法的有效性。

求解多维分配问题的排序搜索算法及其应用

提出一种求解多维分配问题的启发式排序搜索算法,给出算法相关理论的证明以及算法的具体步骤。该算法按分配问题的某一维向对应代价面(行、列)编号的不同次序,在满足可行性约束的条件下进行最小元素搜索,在全局范围内寻求分配问题的最优解。针对该算法在一般探测环境下花费时间长的不足,提出一种分层排序搜索算法。所提新算法原理简单、实施方便,具有并行算法特性。通过对该算法及其改进算法以及拉格朗日松弛算法的应用效果分析,验证所提算法的有效性。