SavedAdd your journal

Journals / Turkish Journal of Electrical Engineering and Computer Science / 2010 / Cilt: 18 - Sayı: 6

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

Ali Önder BOZDOĞAN
Asım Egemen YILMAZ
Murat EFE
Pages
1059–1078
Publication Date
2010-06-01
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

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.

📌 3 Key Takeaways

🎯
Objective & Hypothesis: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.
📊
Key Findings & Data: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.
💡
Conclusion & Impact: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.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Generalized assignment problem · ant colony optimization · particle swarm optimization

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.

Özet

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.

🔖

Cite This Article

BOZDOĞAN, A. Ö., YILMAZ, A. E., EFE, M. (2010). Performance analysis of swarm optimization approaches for the generalized assignment problem in multi-target tracking applications. Turkish Journal of Electrical Engineering and Computer Science, Cilt: 18 - Sayı: 6, 1059–1078. https://ajindex.com/articles/188808

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (13)

  1. H. Wang, T. Kirubarajan, Y. Bar-Shalom, “Precision large scale air traffic surveillance using IMM/assignment estimators”, IEEE Trans. Aerospace and Electronic Systems, Vol. 35, pp. 255 – 266, 1999.
  2. 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.
  3. 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.
  4. 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.
  5. Y. Bar-Shalom, Multitarget/Multisensor Tracking: Applications and Advances – Volume III, Artech House Pub- lishers, Boston, 2000.
  6. J. Kennedy, R. Eberhart, “Particle swarm optimization”, in Proc. IEEE Int. Conf. Neural Networks, Vol. 4, pp. –1948, 1995.
  7. M. Dorigo, T. St¨utzle, Ant Colony Optimization, MIT Press,
  8. Cambridge, MA, 2004.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. T.O. Ting, M.V.C. Rao, C.K. Loo, S.S. Ngu, “Solving unit commitment problem using hybrid particle swarm optimization”, J. H