NDLI: Edge sets: an effective evolutionary coding of spanning trees

Please wait, while we are loading the content...

Edge sets: an effective evolutionary coding of spanning trees

Content Provider	IEEE Xplore Digital Library
Author	Raidl, G.R. Julstrom, B.A.
Copyright Year	1997
Abstract	The fundamental design choices in an evolutionary algorithm (EA) are its representation of candidate solutions and the operators that will act on that representation. We propose representing spanning trees in EAs for network design problems directly as sets of their edges and we describe initialization, recombination, and mutation operators for this representation. The operators offer locality, heritability, and computational efficiency. Initialization and recombination depend on an underlying random spanning-tree algorithm. Three choices for this algorithm, based on the minimum spanning-tree algorithms of Prim and Kruskal and on random walks, respectively, are examined analytically and empirically. We demonstrate the usefulness of the edge-set encoding in an EA for the NP-hard degree-constrained minimum spanning-tree problem. The algorithm's operators are easily extended to generate only feasible spanning trees and to incorporate local, problem-specific heuristics. Comparisons of this algorithm to others that encode candidate spanning trees via the Blob Code, with network random keys, and as strings of weights indicate the superiority of the edge-set encoding, particularly on larger instances.
Starting Page	225
Ending Page	239
Page Count	15
File Size	775078
File Format	PDF
ISSN	1089778X
Volume Number	7
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2003-06-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Tree graphs Algorithm design and analysis Evolutionary computation Genetic mutations Encoding Clouds Computational efficiency Polynomials Cost function Computer graphics
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the Bias and Performance of the Edge-Set Encoding

Biased mutation operators for subgraph-selection problems

The edge-window-decoder representation for tree-based problems

An Edge-Set Representation Based on a Spanning Tree for Searching Cut Space

A one-parameter genetic algorithm for the minimum labeling spanning tree problem

The Dandelion Code: A New Coding of Spanning Trees for Genetic Algorithms

From the Dandelion Code to the Rainbow code: a class of bijective spanning tree representations with linear complexity and bounded locality

Partitioning Bispanning Graphs into Spanning Trees

An Improved Ant-Based Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

Edge sets: an effective evolutionary coding of spanning trees

Similar Documents

On the Bias and Performance of the Edge-Set Encoding

Biased mutation operators for subgraph-selection problems

The edge-window-decoder representation for tree-based problems

An Edge-Set Representation Based on a Spanning Tree for Searching Cut Space

A one-parameter genetic algorithm for the minimum labeling spanning tree problem

The Dandelion Code: A New Coding of Spanning Trees for Genetic Algorithms

From the Dandelion Code to the Rainbow code: a class of bijective spanning tree representations with linear complexity and bounded locality

Partitioning Bispanning Graphs into Spanning Trees

An Improved Ant-Based Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

Edge sets: an effective evolutionary coding of spanning trees