유전자 알고리즘을 이용한 OPKFDD의 최적화 = Optimization of OPKFDDs using Genetic Algorithms

국문 초록 (Abstract)

OPKFDD(Ordered Pseudo-Kronecker Functional Decision Diagram)는 각 노드에서 다양한 확장방법(decomposition)을 취할 수 있는 Ordered-DD(Decision Diagram)의 한 종류로서 각 노드마다 Shannon, positive Davio, negative Davio 확장중의 하나를 사용하도록 하며 다른 종류의 DD와 비교해서 작은 수의 노드로 함수를 표현할 수 있다. 그러나 각 노드마다 각기 다른 확장 방법을 선택할 수 있는 특징 때문에 입력 노드에 대한 확장 방법과 입력 변수 순서의 결정에 의해서 OPKFDD의 크기가 좌우되며 최소의 노드 수를 갖는 OPKFDD의 구성은 매우 어려운 문제로 알려져 있다. 즉, OPKFDD에서의 입력변수와 각 노드의 확장 방법을 병행해서 최적의 해를 구하기 위해서는 n개의 입력변수에 대해서 n! · 3^(2^n - 1) 의 경우의 수를 고려해야 한다. 따라서 본 논문에서는 주어진 불리안 함수를 OPKFDD의 최적화 표현을 위해 노드 수를 기준으로 하여 입력변수 순서와 각 노드의 확장 방법을 함께 고려하는 혼용 유전자 알고리즘을 제안하며 최소의 노드 수를 갖는 OPKFDD를 생성하기 위해서 다양한 파라미터 값에 따른 실험결과를 제시한다.

다국어 초록 (Multilingual Abstract)

OPKFDD(Ordered Pseudo-Kronecker Functional Decision Diagram) is one of ordered-DDs(Decision Diagrams) in which each node can take one of three decomposition types: Shannon, positive Davio and negative Davio decompositions. Whereas OBDD(Ordered Binary Decision Diagram) uses only the Shannon decomposition in each node, OPKFDD uses the three decompositions and generates representations of functions with smaller number of nodes than other DDs. However, this leads to the extreme difficulty of getting an optimal solution for the minimization of OPKFDD. Since an appropriate decomposition type has to be chosen for each node, the size of the representation is decided by the selection of the decomposition type as well as the variable ordering of the diagram. In an exhaustive method, n! · 3^(2^n - 1) cases should be considered to get an optimal solution, where n is the number of input variables. To get an optimal solution in such a large solution space, this paper presents a hybrid genetic algorithm for the optimization of OPKFDD and experimental results are given with various parameter values.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련연구
• 3. 유전자 알고리즘을 이용한 OPKFDD의 최소화
• 4. 구현 및 실험결과
• 5. 결론 및 연구방향
• 참고문헌
• 저자소개