http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
조합적 최적화 문제를 위한 네 가지 반복적 알고리즘의 비교 분석
황인재 ( In Jae Hwang ) 충북대학교 과학교육연구소 2010 과학교육연구논총 Vol.25 No.2
There are several different ways to cope with combinatorial optimiaztion problems that were proven to be NP-hard. When the size of the given problem is small enough to apply exhaustive search, finding an optimal solution is feasible. If this is not the case, heuristic algorithms are developed to find near optimal solutions. Most of the heuristic algorithms are problem specific, and they are easy to fall into a trap. There are also probabilistic algorithms that asymptotically converge to an optimal solution, while general enough to be applied to most of the problems. In this paper, we review four such algorithms, and perform experiments to observe their performance on three different combinatorial optimization problems.
황인재 ( In Jae Hwang ) 충북대학교 과학교육연구소 2005 과학교육연구논총 Vol.21 No.2
본 논문에서는 신경망 모델중 하나인 볼츠만 머신을 이용하여 파일 이동문제의 해를 제공한다. 파일이동문제는 분산처리 시스템에서 서비스 요청빈도에 따라 파일을 재배치하는 문제로 정확한 해를 구하려면 지나치게 많은 계산을 요하는 전형적인 문제로 알려져 있다. 신경망은 그 자체가 대규모의 병렬성을 가지고 있으므로 이러한 문제에 대한 해를 적절한 시간내에 제공해줄 수 있는 가능성이 있다. 본 논문에서는 주어진 파일이동문제를 볼츠만머신에 매핑하여 볼츠만머신의 목적함수와 파일이동문제의 목적함수가 비례하도록 신경망 연결 강도를 조절하였다. 컴퓨터 모의실험을 통한 해의 정확도 검증도 함께 시행하였다.
황인재,Hwang In-Jae 한국융합신호처리학회 2005 융합신호처리학회 논문지 (JISPS) Vol.6 No.1
스케줄링은 CDFG 내의 각 연산에 우선순위 관계를 유지하면서 연산이 수행될 제어스텝을 할당하는 과정으로 합성된 하드웨어의 성능에 직접적인 영향을 미치는 중요한 단계이다. 본 논문에서는 자원제한 스케줄링 알고리즘을 제안한다. 제안된 알고리즘은 주어진 그래프를 분석하여 연산유닛의 개수를 결정하고 이에 따라 각 연산을 제어스텝에 할당한다. 스케줄링 과정 중에 상대적으로 부족한 연산유닛과 여유 있는 연산유닛을 구별하여 연산유닛의 수를 조절한 후 반복적으로 성능개선을 시도하게 된다. 제안된 알고리즘의 성능을 평가하기 위하여 모의실험을 수행하였고 그 결과는 기존의 방법들에 비해 우수함을 알 수 있었다. Scheduling for digital system synthesis is assigning each operation in a control/data flow graph(CDFG) to a specific control step without violating precedence relation. It is one of the most important tasks due to its direct influence on the performance of the hardware synthesized. In this paper, we propose a resource-constrained scheduling algorithm. Our algorithm first analyzes the given CDFG to determine the number of functional units of each type, then assigns each operation to a control step while satisfying the constraints. It also tries to improve the solution iteratively by adjusting the number of functional units using the results collected from the previous scheduling. Experiments were performed to test the performance of the proposed algorithm, and results are presented
황인재,Hwang, In-Jae 한국융합신호처리학회 2006 융합신호처리학회 논문지 (JISPS) Vol.7 No.4
유전자 알고리즘은 공학 분야에서 필요한 여러 가지 최적화 문제에 대하여 최적에 가까운 해를 제공해주는 반복적 알고리즘으로 알려져 있다. 본 논문에서는 특정 교배방법에서 유전자의 배열순서가 적합도가 높은 스키마의 길이에 미치는 영향을 고찰하였다. 또한 이에 따른 유전자 알고리즘의 성능 변화를 두 개의 예제를 이용한 실험을 통하여 관찰하였다. 예제로 사용된 그래프 분할과 knapsack 문제를 위해 몇 가지 유전자 재배열 방법을 제시하였다. 실험결과에 따르면 유전자 재배열 방법마다 서로 다른 유전자 알고리즘 성능을 보여주었으며, 적합도가 높은 스키마의 길이를 고려한 재배열 방법이 재배열을 하지 않았을 때 보다 유전자 알고리즘의 성능을 향상시켜 주는 것을 관찰하였다. 따라서 주어진 문제에 적합한 유전자 재배열 방법을 찾는 것이 대단히 중요함을 확인하였다. Genetic Algorithms have been known to provide near optimal solutions for various optimization problems in engineering. In this paper, we study the effect of gene order in genetic algorithms on the defining length of the schema with high fitness values. Its effect on the performance of genetic algorithms was also analyzed through two well known problems. A few gene reordering methods were proposed for graph partitioning and knapsack problems. Experimental results showed that genetic algorithms with gene reordering could find solutions of better qualities compared to the ones without gene reordering. It is very important to find proper reordering method for a given problem to improve the performance of genetic algorithms.