효율성 향상을 위한 방안으로 최적조합을 찾는 휴리스틱 방법에 관한 연구

A Study on Heuristic Methods to Find the Optimal Combination as a Way to Improve Efficiency

본 연구는 효율성 향상을 위한 방안으로 최적의 조합을 찾는 방법에 관한 연구이다. 효율성 향상을 위한 조합은 출연(연) 기본사업 대상으로 비선형 계획법, 랜덤서치 그리고 그리디 알고리즘(greedy algorithm) 방법을 활용하였다. 수치 실험결과 그리디 알고리즘 방법이 가장 많은 과제 조합을 짧은 시간에 도출할 수 있었다. 랜덤서치는 무작위 생성수가 증가할수록 계산 시간이 길어지는 단점이 있는데 본 연구의 수치실험에서는 무작위 생성수가 1000회 일 때 그리디 알고리즘보다 시간이 더 소요되고 최적조합 생성 성능이 떨어졌다. 비선형 계획법은 가장 많은 시간이 소요되고 최적 조합 생성 성능이 떨어졌기에 실무적으로 활용 가능성이 낮다고 할 수 있다. 정부 R&D과제가 매년 증가하는 상황에서 휴리스틱을 활용하면 다양한 과제의 조합을 보여줄 수 있는 장점과 과제 선정을 위한 의사결정 방안으로 활용을 기대할 수 있다.

This paper explores the optimal combination as a way to improve efficiency. Nonlinear optimization, random search, and greedy algorithm methods were used to find an optimal project combination of projects for government research institutes. According to our numerical experiments, the nonlinear programming method is not computationally efficient (i.e., requiring long computational time) to find an optimal combination. However, the greedy algorithm can produce multiple optimal project combinations in a short time window. Random search can also generates multiple optimal combinations, but it has disadvantage that computational time increases in the number of random generations. By using the proposed greedy method, multiple optimal combination can be quickly found in a situation where the number of R&D projects increases. Therefore, a research institute has a greater flexibility in selecting one among multiple optimal combinations.