Ant inspired Monte Carlo algorithm for minimum feedback arc set (CROSBI ID 259103)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Kudelić, Robert ; Ivković, Nikola
engleski
Ant inspired Monte Carlo algorithm for minimum feedback arc set
It is well known that Minimum Feedback Arc Set is in a general case NP-complete. There are different kinds of exact, heuristic and approximation algorithms for solving this problem, but currently there is only one published Monte Carlo algorithm which solves Minimum Feedback Arc Set in polynomial time with arbitrary probability. To further advance the state of the art we have devised new and improved ant inspired Monte Carlo algorithm which on average has 20% faster empirical running time. Due to a learning mechanism the new algorithm also achieved 511% faster convergence in terms of median and 158% improvement in terms of arithmetic mean. This has been done while at the same time maintaining the ability of the algorithm to find optimal solution with arbitrary probability. In addition, the new and improved ant inspired algorithm has substantially improved convergence consistency. A tighter probability bound has also been calculated for the Monte Carlo algorithm. The aforementioned contributions have their significance in a design and implementation of expert and intelligent system. Considering a wide presence of MFAS in a variety of areas the obtained results are significant in other applications as well.
minimum feedback arc set ; Monte Carlo ; randomization ; ant colony optimization ; arbitrary probability
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
122
2019.
108-117
objavljeno
0957-4174
1873-6793
10.1016/j.eswa.2018.12.021
Povezanost rada
Informacijske i komunikacijske znanosti, Računarstvo