Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 1

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  Blob Code
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

Codings and operators in two genetic algorithms for the leaf-constrained minimum spanning tree problem

100%
Julstrom B. A.
International Journal of Applied Mathematics and Computer Science
|
2004
|
tom 14
|
nr 3
385-396
EN
The features of an evolutionary algorithm that most determine its performance are the coding by which its chromosomes represent candidate solutions to its target problem and the operators that act on that coding. Also, when a problem involves constraints, a coding that represents only valid solutions and operators that preserve that validity represent a smaller search space and result in a more effective search. Two genetic algorithms for the leaf-constrained minimum spanning tree problem illustrate these observations. Given a connected, weighted, undirected graph G with n vertices and a bound l, this problem seeks a spanning tree on G with at l least leaves and minimum weight among all such trees. A greedy heuristic for the problem begins with an unconstrained minimum spanning tree on G, then economically turns interior vertices into leaves until their number reaches l. One genetic algorithm encodes candidate trees with Prüfer strings decoded via the Blob Code. The second GA uses strings of length n−l that specify trees’ interior vertices. Both GAs apply operators that generate only valid chromosomes. The latter represents and searches a much smaller space. In tests on 65 instances of the problem, both Euclidean and with weights chosen randomly, the Blob-Coded GA cannot compete with the greedy heuristic, but the subset-coded GA consistently identifies leaf-constrained spanning trees of lower weight than the greedy heuristic does, particularly on the random instances.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.