Name
Abstract | ||
|---|---|---|
Various applications of spectral techniques for enhancing graph bisection in genetic algorithms are investigated. Several enhancements to a genetic algorithm for graph bisection are introduced based on spectral decompositions of adjacency matrices of graphs and subpopulation matrices. First, the spectral decompositions give initial populations for the genetic algorithm to start with. Next, spectral techniques are used to engineer new individuals and reorder the schema to strategically group certain sets of vertices together on the chromosome. The operators and techniques are found to be beneficial when added to a plain genetic algorithm and when used in conjunction with other local optimization techniques for graph bisection. In addition, several world record minimum bisections have been obtained from the methods described in this study. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1143997.1144193 | GECCO |
Keywords | Field | DocType |
new individual,group certain set,spectral decomposition,plain genetic algorithm,genetic algorithm,spectral technique,local optimization technique,adjacency matrix,initial population,graph bisection,singular value decomposition,genetics,genetic engineering,graph partitioning | Adjacency matrix,Strength of a graph,Mathematical optimization,Graph energy,Graph power,Computer science,Null graph,Graph bandwidth,Graph partition,Voltage graph | Conference |
ISBN | Citations | PageRank |
1-59593-186-4 | 4 | 0.46 |
References | Authors | |
27 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacob G. Martin | 1 | 26 | 3.79 |