Performance analysis of swarm optimization approaches for the generalized assignment problem in multi-target tracking applications

Authors: ALİ ÖNDER BOZDOĞAN, ASIM EGEMEN YILMAZ, MURAT EFE

Abstract: The aim of this study is to investigate the suitability of selected swarm optimization algorithms to the generalized assignment problem as encountered in multi-target tracking applications. For this purpose, we have tested variants of particle swarm optimization and ant colony optimization algorithms to solve the 2D generalized assignment problem with simulated dense and sparse measurement/track matrices and compared their performance to that of the auction algorithm. We observed that, although with some modification swarm optimization algorithms provide improvement in terms of speed, they still fall behind the auction algorithm in finding the optimum solution to the problem. Among the investigated colony optimization approaches, the particle swarm optimization algorithm using the proposed 1-opt local search was found to perform better than other modifications. On the other hand, it is assessed that swarm optimization algorithms might be powerful tools for multiple hypothesis target tracking applications at noisy environments, since within single execution they provide a set of numerous good solutions to the assignment problem.

Keywords: Generalized assignment problem, ant colony optimization, particle swarm optimization, data association, target tracking

Full Text: PDF