Nalazite se na CroRIS probnoj okolini. Ovdje evidentirani podaci neće biti pohranjeni u Informacijskom sustavu znanosti RH. Ako je ovo greška, CroRIS produkcijskoj okolini moguće je pristupi putem poveznice www.croris.hr
izvor podataka: crosbi

Ant inspired Monte Carlo algorithm for minimum feedback arc set (CROSBI ID 259103)

Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija

Kudelić, Robert ; Ivković, Nikola Ant inspired Monte Carlo algorithm for minimum feedback arc set // Expert systems with applications, 122 (2019), 108-117. doi: 10.1016/j.eswa.2018.12.021

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

Poveznice
Indeksiranost