E-viri
Recenzirano
-
Silva-Muñoz, Moisés; Contreras-Bolton, Carlos; Rey, Carlos; Parada, Victor
Applied soft computing, September 2023, 2023-09-00, Letnik: 144Journal Article
One of graph optimization’s fundamental and most challenging problems is determining the maximum set of unconnected vertices in a graph, called the maximum independent set problem. This problem consists of finding the largest independent set in a graph, where an independent set is a set of vertices such that no two vertices are adjacent. This paper presents a new artificially generated algorithm for the maximum independent set problem. The new algorithm is generated by the automatic generation of algorithms, a technique that allows the construction of new hybrid algorithms, taking advantage of existing algorithms. Thus, the automatic generation of algorithms combines basic heuristics for the problem, a tabu search method selected from the literature, and an exact method that solves the problem’s mathematical formulation working for a limited computational time. With these components, the space of possible algorithms is traversed by employing genetic programming. Algorithms of small sizes are generated to study their structure and discover new algorithmic combinations. Then, we select the algorithm that finds solutions with the best computational performance among all the generated algorithms. This best algorithm is compared with three state-of-the-art algorithms for the problem, presenting the best computational performance for the 131 instances in the literature. •Artificially generated algorithms for solving the maximum independent set problem.•Algorithms are trained with different groups of instances.•Algorithms generated combine basic heuristics, a tabu search, and an exact method.•An artificial algorithm outperforms all generated ones in computational performance.•The best generated algorithm outperforms the state-of-the-art algorithms.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.