Name
Abstract | ||
|---|---|---|
The goal of linkage learning in evolutionary algorithms is to identify the interactions between variables of a problem. Knowing the linkage information helps search algorithms to find the optimum solution efficiently and reliably in hard problems. This paper presents a simple approach for linkage learning based on the graph theory. A graph is used as the structure to keep the the pairwise dependencies between variables of the problem. We call this graph 'the underlying dependency graph of the problem'. Then maximum spanning tree (MST) of the dependency graph is found. It is shown that MST contains all the necessary linkage if the dependency graph is built upon enough population. In this approach, pairwise dependencies calculated based on a perturbation based identification method, are used as the variable dependencies. The proposed approach has the advantage of being capable of learning the linkage without the need for the costly fit-to-data evaluations for model search. It is parameter-less and the algorithm description is simple. The proposed technique is tested on several benchmark problems and it is shown to be able to compete with similar approaches. Based on the experimental results it can successfully find the linkage groups in polynomial number of fitness evaluations. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2330784.2330970 | GECCO (Companion) |
Keywords | Field | DocType |
hard problem,pairwise dependency,graph theory,benchmark problem,underlying dependency graph,linkage information,dependency graph,necessary linkage,linkage learning,linkage group,cell cycle,evolutionary algorithm,synthetic biology,artificial life,search algorithm,spanning tree | Graph theory,Mathematical optimization,Computer science,Tree decomposition,SPQR tree,Spanning tree,Artificial intelligence,Clique-width,Dependency graph,Machine learning,Moral graph,Graph (abstract data type) | Conference |
Citations | PageRank | References |
1 | 0.38 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| B. Hoda Helmi | 1 | 22 | 4.24 |
| Martin Pelikan | 2 | 1921 | 130.98 |
| Adel Torkaman Rahmani | 3 | 139 | 19.77 |