The minimum feedback vertex set in a directed graph is a NP-hard problem i.e., it is very unlikely that a polynomial algorithm can be found to solve any instances of it. Solutions of the minimum feedback vertex set can find several real world applications. For this reason, it is useful to investigate heuristics that might give near-optimal solutions. Here we present an enhanced genetic algorithm with an ad hoc local search improvement strategy that finds good solutions for any given instance. To prove the effectiveness of the algorithm, we provide an implementation tested against a large variety of test cases. The results we obtain are compared to the results obtained by greedy and randomized algorithms for finding approximate solutions to the problem.

Targeting the minimum vertex set problem with an enhanced genetic algorithm improved with local search strategies

Cutello, Vincenzo;Pappalardo, Francesco
2015

Abstract

The minimum feedback vertex set in a directed graph is a NP-hard problem i.e., it is very unlikely that a polynomial algorithm can be found to solve any instances of it. Solutions of the minimum feedback vertex set can find several real world applications. For this reason, it is useful to investigate heuristics that might give near-optimal solutions. Here we present an enhanced genetic algorithm with an ad hoc local search improvement strategy that finds good solutions for any given instance. To prove the effectiveness of the algorithm, we provide an implementation tested against a large variety of test cases. The results we obtain are compared to the results obtained by greedy and randomized algorithms for finding approximate solutions to the problem.
9783319221793
Artificial intelligence; Genetic algorithms; Graphs; Theoretical Computer Science; Computer Science (all)
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11769/315069
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact