Solving Minimum Weight Triangulation Problem with Genetic Algorithm
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
Minimum Weight Triangulation (MWT) problem is an optimization problem searching for the triangulation of a given graph with minimum weight. Like many other graph problems this problem is also known to be NP-hard for general graphs. Several heuristic algorithms have been proposed for this problem including simulated annealing and genetic algorithm. In this paper, we propose a new genetic algorithm called GA-FF and show that the performance of the proposed genetic algorithm outperforms the previous one.
Abstract
Minimum Weight Triangulation (MWT) problem is an optimization problem searching for the triangulation of a given graph with minimum weight. Like many other graph problems this problem is also known to be NP-hard for general graphs. Several heuristic algorithms have been proposed for this problem including simulated annealing and genetic algorithm. In this paper, we propose a new genetic algorithm called GA-FF and show that the performance of the proposed genetic algorithm outperforms the previous one.
참고문헌 (12)
- Pinar Heggernes, "Minimal triangulations of graphs: A survey", Discrete Mathematics, 306, pp.297~317 (2006)
- S. Arnborg, "Complexity of finding embeddings in a k-tree", SIAM J. Algebraic Discrete Methods, 8, pp.277~284 (1987)
- M. Yannakakis, "Computing the minimum fill-in is NP- complete", SIAM J. Algebraic Discrete Methods, 2, pp.77~79 (1981)
- Finn V.Jensen, "An introduction to Bayesian networks" (1996), UCL Press
- Wen, W. X, "Optimal decomposition of belief networks", In Uncertainty in Artificial Intelligence, 6, pp.209~224 (1990)
- Pedro Larraňaga, "Decomposing Bayesian networks: triangulation of the moral graphs with genetic algorithm", Statistics and Computing, 7, pp.19~34 (1997)
- D.J. Rose, "Algorithmic aspects of vertex elimination on graphs", SIAM J. Comput, 5, pp.266~283 (1976)
- [URL]
- Triangulation of graphs – Algorithms giving small total state space,Research Report R-90-09, "Uffe Kjaerulff", Department of Computer Science, Aalborg University, ~ (1990)
- Tarjan, Robert Endre, "Maximum Cardinality Search and chordal graphs", Stanford Univ. Unpublished Lecture Notes CS 259.
- Zbigniew Michalewicz, "Genetic Algorithms + Data Structures = Evolution Programs" (1992), Springer-Velag
- De Jong, K. A, "An analysis of the behavior of a class of genetic adaptive systems", Ph.D., pp.1975