Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Evolutionary Algorithm
Minimum Spanning Tree
Search Space
Skewed Distribution
Spanning Tree
Related Publications
(1)
Generating Random Spanning Trees
Subscribe
Academic
Publications
Initialization is robust in evolutionary algorithms that encode spanning trees as sets of edges
Initialization is robust in evolutionary algorithms that encode spanning trees as sets of edges,10.1145/508791.508898,Bryant A. Julstrom,Günther R. Ra
Edit
Initialization is robust in evolutionary algorithms that encode spanning trees as sets of edges
(
Citations: 12
)
BibTex

RIS

RefWorks
Download
Bryant A. Julstrom
,
Günther R. Raidl
Evolutionary algorithms (EAs) that search spaces of spanning trees can encode candidate trees as sets of edges. In this case, edgesets for an EA's initial population should represent spanning trees chosen with uniform probabilities on the graph that underlies the target problem instance. However, the generation of random spanning trees is not as simple as it might appear. Mechanisms based on Prim's and Kruskal's
minimum spanning tree
algorithms are not uniform, and uniform mechanisms are slow, not guaranteed to terminate, or require that the underlying graph be complete.However, a nonuniform initial population of spanning trees need not harm an EA's performance. Trials of a crossoveronly EA for the OneMaxTree problem, using Primbased, Kruskalbased, and uniform initialization, indicate that the distribution of edges in the initial population is far more important than the distribution of trees. A
skewed distribution
of edges in its initial population damages the EA's performance, but this is remedied by a reasonable amount of mutation.
Conference:
ACM Symposium on Applied Computing  SAC
, pp. 547552, 2002
DOI:
10.1145/508791.508898
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
aragorn.ads.tuwien.ac.at
)
(
www.ads.tuwien.ac.at
)
(
www.ads.tuwien.ac.at
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(9)
...Recent studies have indicated the general usefulness of representing spanning trees directly as lists of their edges and applying operators that always yield feasible trees [23,
27
]...
Isamu Watanabe
,
et al.
A Hybrid Evolutionary Algorithm for Service Restoration in Power Distr...
...The general issue of encoding is of course one of the critical steps in designing an EA approach to any application area, and the progress so far in the area of EAs applied to spanning tree problems can be seen as the continual development of ingenious new encodings (and associated genetic operators) [1], [7], [14], [
19
]‐[21], [23], [34], [38], [40], [45], [58]...
Sangmoon Soak
,
et al.
The EdgeWindowDecoder Representation for TreeBased Problems
...Random spanning tree generation based on Kruskal’s algorithm fills the population with feasible initial solutions [
22
]...
Günther R. Raidl
,
et al.
Biased Mutation Operators for SubgraphSelection Problems
...We can cite the works of Raidl and Julstrom ([
2
],[11],[3]), who use evolutionary algorithms to encode spanning trees in undirected graph problems...
Remy Chevrier
,
et al.
Comparison of three algorithms for solving the convergent demand respo...
...Recent studies have indicated the general usefulness of representing spanning trees directly as lists of their edges and applying operators that always yield feasible trees (e.g., [
13
])...
Isamu Watanabe
,
et al.
A Hybrid Genetic Algorithm for Service Restoration Problems in Power D...
References
(19)
A New Genetic Algorithm for the Optimal Communication Spanning Tree Problem
(
Citations: 27
)
Yu Li
,
Youcef Bouchebaba
Conference:
Artificial Evolution  AE
, pp. 162173, 1999
Neuer Beweis eines Satzes ? uber Permutationen
(
Citations: 53
)
Unknown
Edge sets: an effective evolutionary coding of spanning trees
(
Citations: 112
)
Günther R. Raidl
,
Bryant A. Julstrom
Journal:
IEEE Transactions on Evolutionary Computation  TEC
, vol. 7, no. 3, pp. 225239, 2003
Comparison of Pr¨uferlike codes for labeled trees
(
Citations: 8
)
Narsingh Deo
,
Paulius Micikevicius
Published in 2001.
Shortest connection networks and some generalizations
(
Citations: 1113
)
R. C. Prim
Sort by:
Citations
(12)
A Hybrid Evolutionary Algorithm for Service Restoration in Power Distribution Systems
Isamu Watanabe
,
Ikuo Kurihara
,
Yoshiki Nakachi
Published in 2007.
The EdgeWindowDecoder Representation for TreeBased Problems
(
Citations: 20
)
Sangmoon Soak
,
David. W. Corne
,
Byungha Ahn
Journal:
IEEE Transactions on Evolutionary Computation  TEC
, vol. 10, no. 2, pp. 124144, 2006
Biased Mutation Operators for SubgraphSelection Problems
(
Citations: 7
)
Günther R. Raidl
,
Gabriele Koller
,
Bryant A. Julstrom
Journal:
IEEE Transactions on Evolutionary Computation  TEC
, vol. 10, no. 2, pp. 145156, 2006
Comparison of three algorithms for solving the convergent demand responsive transportation problem
(
Citations: 3
)
Remy Chevrier
,
Philippe Canalda
,
Pascal Chatonnay
,
Didier Josselin
Conference:
International Conference on Intelligent Transportation  ITSC
, 2006
A Hybrid Genetic Algorithm for Service Restoration Problems in Power Distribution Systems
(
Citations: 2
)
Isamu Watanabe
,
Ikuo Kurihara
,
Yoshiki Nakachi
Published in 2006.