Ali Önder BOZDOĞAN, Asım Egemen YILMAZ, Murat EFE

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

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.

Anahtar Kelimeler:

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

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

Keywords:

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

PDF

___

H. Wang, T. Kirubarajan, Y. Bar-Shalom, “Precision large scale air traﬃc surveillance using IMM/assignment estimators”, IEEE Trans. Aerospace and Electronic Systems, Vol. 35, pp. 255 – 266, 1999.
S. Deb, M. Yeddanapudi, K. Pattipati, Y. Bar-Shalom, “A generalized S-D assignment algorithm for multisensor- multitarget state estimation”, IEEE Trans. Aerospace and Electronic Systems, vol. 33, pp. 523 – 538, 1999.
R.L Popp, K.R. Pattipati, Y. Bar-Shalom, “m-best S-D assignment algorithm with application to multitarget tracking”, IEEE Trans. Aerospace and Electronic Systems, Vol. 37, pp. 22–39, 2001.
A. Sinha, T. Kirubarajan, “A randomized heuristic approach for multidimensional association in target tracking”, in Proc. SPIE, Vol. 5428, pp. 202 – 210, 2004.
J. Munkres, ”Algorithms for the Assignment and Transportation Problems”, Journal of the Society of Industrial and Applied Mathematics, Vol. 5, No. 1, pp. 32–38, 1957.
D. P. Bertsekas, “An auction algorithm for shortest paths”, SIAM Journal on Optimization, Vol. 1, pp. 425-447, R. Jonker and A. Volgenant, “A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems”, J. Computing, Vol. 38, pp. 325-340, 1987.
Y. Bar-Shalom, Multitarget/Multisensor Tracking: Applications and Advances – Volume III, Artech House Pub- lishers, Boston, 2000.
J. Kennedy, R. Eberhart, “Particle swarm optimization”, in Proc. IEEE Int. Conf. Neural Networks, Vol. 4, pp. –1948, 1995.
M. Dorigo, T. St¨utzle, Ant Colony Optimization, MIT Press, Cambridge, MA, 2004.
S. Salman, A. Imtiaz, S. Al-Madani, “Discrete particle swarm optimization for heterogeneous task assignment problem”, in CD ROM Proc. World Multiconf. Syst. Cyb. & Inf. (SCI 2001), 2001.
S. Salman, A. Imtiaz, S. Al-Madani, “Particle swarm optimization for task assignment problem”, Microprocess. Microsyst., Vol. 26, No. 8, pp. 363–371, 2002.
M. Clerc, “Particle Swarm Optimization, illustrated by the Traveling Salesman Problem”, New Optimization Techniques in Engineering, Springer Verlag, pp. 219-239, 2004.
K.P. Wang, L. Huang, C.G. Zhou, W. Pang, “Particle swarm optimization for traveling salesman problem”, in: Proc. Int. Conf. Mach. Learning and Cybernetics, pp. 1583–1585, 2003.
L. Cagnina, S. Esquivel, R. Gallard, “Particle swarm optimization for sequencing problem: a case study”, in Proc. IEEE Conf. Evol. Comp., pp. 536–541, 2004.
T.O. Ting, M.V.C. Rao, C.K. Loo, S.S. Ngu, “Solving unit commitment problem using hybrid particle swarm optimization”, J. Heuristics, Vol. 9, No. 6, pp. 507–520, 2003.
H.H. Balcı, J.F. Valenzuela, “Scheduling Electric Power Generators Using Particle Swarm Optimization Combined With The Lagrangian Relaxation Method”, Int. J. Appl. Math. Comput. Sci., Vol. 14, No. 3, pp. 411–421, 2004.
H. Liu, A. Abraham, J. Zhang, “A Particle Swarm Approach to Quadratic Assignment Problems”, A. Saad et al. (Eds.): Soft Computing in Industrial Applications, ASC 39, pp. 213–222, 2007.
T. Gong, A. L. Tuson, “Particle Swarm Optimization for Quadratic Assignment Problems – A Forma Analysis Approach”, Int. J. Comp. Int. Rsrch (IJCIR), Vol. 4, No. 8, pp. 177-185, 2008.
X. Hu, R.C. Eberhart, Y. Shi, “Swarm intelligence for permutation optimization: a case study of n -queens problem”, in Proc. IEEE Swarm Int. Symp., pp. 243-246, 2003.
A.W. Mohemmed, N.C. Sahoo, T.K. Geok, “Solving shortest path problem using particle swarm optimization”, Appl. Soft Comput. J., Vol. 8, No. 4, pp. 1643-1653, 2008.
F. van den Bergh, A.P. Engelbrecht, “A Cooperative approach to particle swarm optimization”, IEEE Trans. Evolutionary Computation, Vol. 8, pp. 225 – 239, 2004.
Y. Shi, R.C. Eberhart, “Parameter selection in particle swarm optimization”, Evolutionary Programming VII, Lecture Notes in Computer Science, Vol. 1447, Springer, New York, pp. 591–600, 1998.
R. C. Eberhart, P. Simpson, R. Dobbins, “Computational Intelligence, PC Tools”, Academic Press International, San Diego, CA, 1996.
T. St¨utzle, H.H. Hoos, “MAX-MIN Ant system”, Future Generat. Comput. Syst., Vol. 16, pp. 889–914, 2000.
C. Blum, “Ant colony optimization: Introduction and recent trends”, Physics of Life Reviews, Vol. 2, No. 4, pp. 373, 2005.