New Ant Colony Optimization Algorithms for Variants of Multidimensional Assignments in d-Partite Graphs
Source abstract
Abstract
This article presents ant algorithms for single- and multi-criteria industrial optimization problems. A common factor in these algorithms is the determination of the set with the maximum number of cliques, which represent the solution to multidimensional assignment problems in d-partite graphs. In the case of weighted incomplete graphs, the goal is to determine the set with the maximum number of cliques and the maximum sum of the weights of their edges. In the case of unweighted incomplete graphs, the goal is to determine the set with the maximum number of maximum cliques. In the case of complete weighted graphs, the goal is to determine all maximum cliques with the minimal sum of their edge weights. These optimization problems are solved using the various ant algorithms proposed in this paper. The proposed algorithms differ not only in terms of the objective function, but also in terms of desirability functions, as previously established, and they achieved a smaller sum of weights for cliques in the case of weighted complete graphs than previous ant algorithms presented in the literature. The same applies to unweighted incomplete graphs. The presented algorithms resulted in a greater number of maximal cliques than previous ant algorithms presented in the literature. This study is the first to propose the presented ant algorithms in the case of weighted incomplete graphs.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Data Management and Algorithms · Graph Theory and Algorithms · Vehicle Routing Optimization Methods
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Faculty of Electrical and Computer Engineering, Cracow University of Technology, 31-155 Cracow, Poland
References (34)
Show source-provided references
1. Performance analysis of swarm optimization approaches for the generalized assignment problem in multi-target tracking applications
2. Bozdogan, A.O., and Efe, M. (2008, January 26–30). Ant Colony Optimization Heuristic for the multidimensional assignment problem in target tracking. Proceedings of the IEEE National Radar Conference 2008, Rome, Italy.10.1109/RADAR.2008.4720822 ↗
3. Improved assignment with ant colony optimization for multi-target tracking10.1016/j.eswa.2011.01.134 ↗
4. Zamojski, W., Mazurkiewicz, J., Sugier, J., Walkowiak, T., and Kacprzyk, J. (2022). Ant Colony Optimization Algorithm for Object Identification in Multi-cameras Video Tracking Systems. New Advances in Dependability of Networks and Systems, Springer. DepCoS-RELCOMEX 2022, Lecture Notes in Networks and Systems.10.1007/978-3-031-06746-4 ↗
5. Ant algorithms for finding weighted and unweighted maximum cliques in d-division graphs10.24425/ijet.2024.149556 ↗
6. Machine Learning Methods for Data Association in Multi-Object Tracking
7. Dehghan, A., Assari, S.M., and Shah, M. (2015, January 7–12). GMMCP tracker: Globally optimal Generalized Maximum Multi Clique problem for multiple object tracking. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Boston, MA, USA.10.1109/CVPR.2015.7299036 ↗
8. Cremers, D., Reid, I., Saito, H., and Yang, M.H. (2014). Multiple Object Tracking by Efficient Graph Partitioning. Computer Vision—ACCV 2014, Springer. Lecture Notes in Computer Science.10.1007/978-3-319-16811-1 ↗
9. Wei, L., and Xingwei, L. (2016, January 13–15). Multiple object tracking based on modified algorithm of GMMCP tracker. Proceedings of the 2016 IEEE International Conference on Signal and Image Processing (ICSIP), Beijing, China.10.1109/SIPROCESS.2016.7888214 ↗
10. Jiang, K., Ma, T., and Hu, Y. (2023, January 17–19). GMMCP Based Multi Target Tracking Algorithm with Missing Measurements. Proceedings of the 9th International Conference on Mechanical and Electronics Engineering (ICMEE), Xi’an, China.10.1109/ICMEE59781.2023.10525461 ↗
11. Finding all k-cliques in k-partite graph, an application in textile engineering10.1016/S0305-0548(00)00053-8 ↗
12. On finding k-cliques in k-partite graphs10.1007/s11590-012-0536-y ↗
13. Exploiting hierarchical dense structures on hyper-graphs for multi-object tracking10.1109/TPAMI.2015.2509979 ↗
14. Precision large scale air traffic surveillance using IMM/assignment estimators10.1109/7.745696 ↗
15. Gabrovsek, B., Novak, T., Povh, J., Rupnik Poklukar, D., and Zerovnik, J. (2020). Multiple Hungarian method for k-assignment problem. Mathematics, 8.10.3390/math8112050 ↗
16. A generalized S-D assignment algorithm for multi-sensor-multitarget state estimation
17. Generalized network design problem10.1016/S0377-2217(02)00404-6 ↗
18. The partial constraint satisfaction problem: Facets and lifting theorems10.1016/S0167-6377(98)00043-1 ↗
19. Zamir, A.R., Dehgan, A., and Shah, M. (2012, January 7–13). GMPC—Tracker: Global Multi-object Tracking Using Generalized Minimum Clique Problem. Proceedings of the Computer Vision—European Conference on Computer Vision 2012, Florence, Italy.
20. Andriyenko, A., and Schindler, K. (2011, January 20–25). Multi-target Tracking by Continuous Energy Minimization. Proceedings of the Conference on Computer Vision and Pattern Recognition 2011, Colorado Springs, CO, USA.10.1109/CVPR.2011.5995311 ↗
21. Andriyenko, A., Schindler, K., and Roth, S. (2012, January 16–21). Discrete-Continuous Optimization for Multi-Target Tracking. Proceedings of the Conference on Computer Vision and Pattern Recognition 2012, Providence, RI, USA.10.1109/CVPR.2012.6247893 ↗
22. Multiple object tracking by reliable tracklets10.1007/s11760-019-01418-3 ↗
23. Multiple object tracking using k-shortest paths optimization10.1109/TPAMI.2011.21 ↗
24. Zhang, L., Li, Y., and Nevatia, R. (2008, January 23–28). Global data association for multi-object tracking using network flows. Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK, USA.
25. Pirsiavash, H., Ramanan, D., and Fowlkes, C.C. (2011, January 20–25). Globally-optimal greedy algorithms for tracking a variable number of objects. Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition, Colorado Springs, CO, USA.10.1109/CVPR.2011.5995604 ↗
26. Lenz, P., Geiger, A., and Urtasun, R. (2015, January 7–13). Follow Me: Efficient online min-cost flow tracking with bounded memory and computation. Proceedings of the IEEE International Conference on Computer Vision (ICCV) 2015, Santiago, Chile.10.1109/ICCV.2015.496 ↗
27. Chari, V., Lacoste-Julien, S., Laptev, I., and Sivic, J. (2015, January 7–12). On pairwise costs for network flow multi-object tracking. Proceedings of the I IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2015, Boston, MA, USA.10.1109/CVPR.2015.7299193 ↗
28. Ristani, E., and Tomasi, C. (2014). Tracking multiple people online and in real time. Asian Conference on Computer Vision, Springer.10.1007/978-3-319-16814-2_29 ↗
29. Tang, S., Andres, B., Andriluka, M., and Schiele, B. (2015, January 7–12). Subgraph Decomposition for Multi-Target Tracking. Proceedings of the Conference on Computer Vision and Pattern Recognition 2015, Boston, MA, USA.10.1109/CVPR.2015.7299138 ↗
30. Application of 0–1 integer programming to multi-target tracking problems10.1109/TAC.1977.1101500 ↗
31. Yoon, K., Kim, D.Y., Yoon, Y.C., and Jeon, M. (2019). Data association for Multi-Object Tracking via Deep Neural Networks. Sensors, 19.10.3390/s19030559 ↗
32. Efficient object detection using convolutional neural network-based hierarchical feature modeling10.1007/s11760-016-0962-x ↗
33. An application of Ant Colony Optimization, Kalman Filter and Artificial Neural Network for Multiple Target Tracking Problems
34. genetic based multi-dimensional data association algorithm for multi sensor multi target tracking10.1016/S0895-7177(97)00144-1 ↗