An Efficient and Scalable Problem Decomposition Method for Large-scale Cooperative Coevolutionary Algorithms

Abstract

대규모 협력 공진화 (cooperative coevolutionary; CC) 알고리즘을 위한 다양한 문제 분할 방법들이 제안되었음에도 불구하고, 대규모 전역 최적화 문제들에 대한 효율적이면서도 확장 가능한 분할 방법에 대한 연구는 여전히 충분하지 못한 실정이다. 이에 따라, 본 논문에서는 대규모 CC 알고리즘을 위한 효율적이면서도 확장 가능한 문제 분할 방법인 “EVIID 알고리즘”을 제안한다. 본 연구는 제한된 규모의 문제 분할 방법에 대해서만 집중적으로 다루는 종래의 연구들과는 달리 매우 높은 차원의 최적화 문제들에 대해서도 문제 분할의 정확도를 손상시키지 않으면서 동시에 대규모의 확장성을 갖는 효율적인 문제 분할 방법을 개발하는 것을 목표로 한다. 이를 위해서, 본 논문에서는 먼저 세 가지의 핵심 전략인 binary interdependent variable search algorithm과 dynamic selective memoization algorithm for repeated perturbations, 그리고 pre-variable sorting algorithm을 제안한다. 그 다음에, 이들을 하나의 합성함수로 결합하여 EVIID 알고리즘을 구현한다. 더 나아가, EVIID 알고리즘이 적용된 실제 CC 알고리즘인 “CC-EVIID 알고리즘”을 구현함으로써, 우리의 EVIID 알고리즘이 다양한 CC 알고리즘에 효과적으로 적용될 수 있음을 입증한다. 심층적인 이론적 분석을 통해서 우리는 EVIID 알고리즘이 최악의 경우에 O(nlogn)의 계산 복잡도를 가짐을 확인하였으며, 이는 기존의 최신 문제 분할 방법들과 비교했을 때 가장 효율적인 성능이었다. 이것은 우리의 EVIID 알고리즘이 어떠한 높은 차원의 문제들에 대해서도 과도한 계산적 오버헤드 없이 확장성 높은 문제 분할을 수행할 수 있음을 보여준다. 이와 같은 EVIID 알고리즘의 효율적이면서도 확장 가능한 성능은 앞서 설명한 세 가지 핵심 전략들의 시너지에 의해서 만들어진다. 실제로, 그들의 시너지 효과는 많은 변수들 사이의 상호 종속성들을 식별하기 위해서 수행되는 불필요한 계산들을 효과적으로 가지치기함으로써, 분할 정확도를 손상시키지 않음과 동시에 효율적이면서도 확장성 높은 문제 분할을 가능하게 한다. 종합적인 실험에서, EVIID 알고리즘은 1000 차원부터 10000 차원까지의 모든 벤치마크 문제들을 효율적으로 그리고 정확하게 분할할 수 있었다. 구체적으로, EVIID 알고리즘은 다수의 변수들 사이에 존재하는 복잡한 상호 종속적인 관계들을 식별하는 동안 많은 수의 불필요한 계산들과 수행 시간을 상당히 감소시켰다. 이는 기존의 최신 문제 분할 방법들과 비교할 때 계산적 효율성과 확장성 측면에서 가장 좋은 결과였다. 동시에, 우리의 EVIID 알고리즘은 많은 수의 계산들을 감소시켰음에도 불구하고 안정적으로 높은 수준의 분할 정확도를 유지하였다. 더 나아가, 우리의 CC-EVIID 알고리즘은 다른 문제 분할 방법들이 적용된 CC 알고리즘들보다 더 좋은 최적화 성능과 수렴 속도를 보여주었다. 결과적으로, 본 논문에서는 우리의 EVIID 알고리즘이 어떠한 높은 차원의 대규모 전역 최적화 문제들에 대해서도 강인한 확장성과 높은 분할 정확도를 유지하면서 그들을 효율적으로 분할할 수 있음을 이론적으로 그리고 실험적으로 입증하였다. 또한, 변수들 간의 복잡한 상호 종속성을 식별하는 동안 수행되는 다수의 불필요한 계산들을 EVIID 알고리즘에 의해서 최소화하는 것이 CC 알고리즘에서 최적화 성능을 향상시키는 데 중요하게 기여할 수 있음을 확인하였다. 이에 따라, 우리는 본 논문이 다양한 대규모 전역 최적화 문제들을 효과적으로 다루기 위한 실용적인 CC 알고리즘들을 연구하는 데 있어 핵심적인 역할을 할 것으로 기대한다.; Although many problem decomposition methods for large-scale cooperative coevolutionary (CC) algorithms have been proposed, researches on efficient and scalable decomposition methods for large-scale global optimization (LSGO) problems are still insufficient. Accordingly, in this dissertation, we propose an efficient and scalable problem decomposition method, namely, the EVIID algorithm for large-scale CC algorithms. Different from traditional studies focusing on the limited scale problem decomposition method, our study aims to develop an efficient and scalable problem decomposition method with no loss of decomposition accuracy on extremely high-dimensional optimization problems. For this, in this dissertation, we first propose three core strategies, namely, the binary interdependent variable search algorithm, dynamic selective memoization algorithm for repeated perturbations, and the pre-variable sorting algorithm. Then, we implement the EVIID algorithm by compensatively combining them into one composite function. Moreover, we verify that the EVIID algorithm can effectively be applied into practical CC algorithms by implementing the CC algorithm with the EVIID algorithm, namely, the CC-EVIID algorithm. From in-depth theoretical studies, we found that our EVIID algorithm had O(nlogn) computational complexity in the worst case, which was the best efficient performance when compared to the state-of-the-art problem decomposition methods. It indicates that the EVIID algorithm can perform scalable problem decomposition without excessive computational overhead for any high-dimensional problems. Such efficient and scalable performance of our EVIID algorithm is made by the synergy among the three strategies. Actually, their synergy enables efficient and scalable problem decomposition without damaging the decomposition accuracy by effectively pruning the redundant computations performed to identify interdependencies among a number of variables. In comprehensive experiments, our EVIID algorithm could efficiently and accurately decompose all benchmark problems from 1000 to 10000 dimensions. In detail, it significantly reduced many unnecessary computations and improved its execution time while identifying complicated interdependent relationships among the variables, which was the best efficient and scalable result when compared against the existing problem decomposition methods. Simultaneously, the EVIID algorithm stably maintained high decomposition accuracy despite of reducing many computations. Besides, our CC-EVIID algorithm achieved better optimization performance and faster convergence than those of other CC algorithms with the existing problem decomposition methods. Hence, we verified that our EVIID algorithm could efficiently decompose any high-dimensional LSGO problems with robust computational scalability and high decomposition accuracy. Moreover, we found that minimizing the redundant computations while identifying the interdependencies among them could significantly contribute to improving the optimization performance in the CC algorithms. Accordingly, we expect that this dissertation will play a key role in studying practical CC algorithms to effectively address various LSGO problems.