이산변수가 포함된 최적화 문제 해결을 위한 근사함수 기반 새로운 탐색방법 알고리즘 개발

Abstract

본 연구에서는 이산변수가 포함된 최적화 문제에 적용이 가능하고 기존의 알고리즘보다 효율적인 탐색기법의 알고리즘을 개발하였다. 이산변수 최적화 문제를 해결하기 위해서는 많은 함수 계산을 요하는 유전알고리즘 (Genetic Algorithm) 이나 모의 담금질 (Simulated Annealing) 등의 메타휴리스틱 알고리즘이 주로 사용되어왔다. 그러나, 실질적인 최적화 문제에서의 함수 계산은 1회 시간이 오래 걸리거나 값비싼 장비나 소프트웨어가 필요하기 때문에 메타휴리스틱 알고리즘을 사용하여 최적화를 수행하기에는 제약이 많다. 본 연구에서 제안하는 탐색기법은 근사함수를 기반으로 탐색하며, 전역탐색, 국부탐색, 그리고 균형탐색으로 탐색방법을 세분화한다. 전역탐색은 현재까지 탐색된 모든 점들을 활용하여 근사함수를 생성하고 근사함수의 해를 찾는다. 국부탐색은 현재까지 찾은 국부최적해를 기준으로 탐색된 점들 중 가까운 점을 추출하여 국부근사함수를 생성하고 근사함수의 값을 찾는다. 다만, 전역탐색과 국부탐색으로 찾은 해가 기존에 탐색된 점이라면 현재의 국부 최적해를 기준으로 random perturbing으로 후보군을 선출하고 국부근사함수를 통해 한 점을 선택한다. 마지막으로 탐색된 모든 점들 사이의 거리를 계산하여 전체 설계 영역에서 탐색이 부족한 부분의 점을 선택한다. 그리고, 각각의 탐색방법으로 선택된 점들은 함수 계산을 진행한다. 또한, 수렴조건을 만족하면 최적화 수행을 마친다. 본 연구에서는 이산변수 최적화 문제로 사용된 9개의 수학적 모델을 통해 알고리즘을 1차 검증하였다. 성능 비교를 위하여 근사함수 기반으로 개발된 최신 알고리즘인 SMDN (two phase Surrogate Model-aware Differential evolution with Neighborhood exploration)과의 비교를 하였다. 기존 SMDN 논문에서 각 문제마다 20번 반복 수행을 하였으므로, 공정한 비교를 위하여 제안한 알고리즘도 각 문제마다 20번 반복 수행을 하였다. 수학적 모델 중 국부최적해가 많은 3 문제의 경우, SMDN은 해를 찾는 확률이 100%가 되지 않았던 반면 제안한 알고리즘은 3 문제 모두에 대해서 최적해를 찾았다. 또한, 두 알고리즘 모두 100% 최적해를 찾은 6 문제에서, 제안한 알고리즘이 SMDN 대비 최소 46.3-96.3 %의 함수 계산량을 줄여 제안한 알고리즘의 효율성을 검증하였다. 그리고, 제안한 알고리즘을 공학 모델에 추가적으로 적용함으로써 실제 공학 문제에의 적용 가능 여부를 확인하였다. 근사함수 기반으로 개발된 SMDN 알고리즘의 경우, 공학 문제에 적용한 예가 없으므로, 공학 문제에 대한 제안된 알고리즘의 성능평가를 위하여 기존의 메타휴리스틱 방법들 중 최근에 개발된 Cuckoo Search, League championship algorithm, Particle Swarm Optimization의 세 알고리즘들과 비교하였다. 비교 결과, Speed Reducer 문제(F10) 에서 제안한 알고리즘은 2000번의 함수 계산으로 6,000-250,000번의 함수 계산을 했던 메타휴리스틱 알고리즘들보다 정확도도 0.034% 개선된 최적해를 찾았다. 그리고, Pressure Vessel 문제(F11)에서 제안한 알고리즘은 2000번 함수 계산으로 7,500-24,000번의 함수 계산을 했던 메타휴리스틱 알고리즘들에서 확보한 최적해보다 0.17% 부족한 최적해를 찾았다. 실제 산업에서 0.17%의 성능 개선을 위해 2.75배 이상의 시간과 자원을 투자하는 것은 낭비 일 수 있다. 즉, 본 연구에서 제안한 알고리즘이 기존 알고리즘에 비해 매우 효율적으로 이산 최적해를 얻을 수 있음을 알 수 있었다.