새로운 코딩 기법과 파라메터 그룹 적응 알고리즘을이용한 DEAS의최적화 성능 개선

Abstract

본논문은메타휴리스틱최적화알고리즘중의하나인DEAS의성능개선을위한방안들을 제시한다. 이 논문은 DEAS의 지역 및 전역 검색 전략에 관한 설명을 제공하고, 최근까지 DEAS의 성능 개선을 위해 수행된 연구와 이들을 실제 문제에 적용한 연구사례들을정리한다. 이논문에서는DEAS성능개선을위한두가지의새로운방 안을제시한다. 그첫번째는새로운이진코딩기법을제안하여복호화함수를변화 시킴으로써, DEAS의지역검색알고리즘의구조를개선하는것이다. 제안된알고리 즘 DEAS 지역 검색의 수렴 성능을 향상 시킨다. 또한 코딩 기법의 개선과 지역 검색 알고리즘의수정을통하여,최적화과정에서생성되는수열의단조감소조건을만족시켰다. 이를 통해 패턴서치(Pattern Search)의 수렴성 증명에 이용된 기법으로 새로 제안된uDEAS의수렴성을증명하였다. 두번째개선방안은mDEAS의변수그룹의설정과 적응에 관련된 알고리즘이다. mDEAS에서 변수의 그룹은 검색 패턴을 결정하여 지역 검색 성능에 영향을 미친다. 기존의 mDEAS 알고리즘은 수작업을 통해서변수 그룹의 구성을 결정하지만, 제안된 알고리즘에서는 지역 검색 동안 얻을 수 있는 정보를 이용한 변수그룹적응기법(Adaptive Parameter Grouping Algorithm)을 이용해 변수그룹의구성을동적으로결정한다. 이방식을이용하여mDEAS의검색패턴을 함수의 형태에 적응시켜 mDEAS의 검색 성능을 향상 시킨다. 제시한 알고리즘들의 성능을 실험을 통해 검증하였다. 이와 더불어 본 논문에서는 기존 연구 과정에서 얻어진 DEAS의 향후 연구 방향을 제시한다. 이들은 DEAS의 복호화 기법과, 추가적인 수렴성 정리와 파라메터 그룹 적응 알고리즘, 그리고 Preliminary Search의 자동화기법,그리고 DEAS의 병렬화와 관련된 부분이다.

This thesis proposes modified algorithms to improve the search performance of one of metaheuristic algorithm family–the dynamic encoding algorithm for searches (DEAS). At first, this thesis provides explanations on the local and global search strategies of DEAS, and surveys previous researches of it and its applications. Then, this thesis proposes two modified algorithms to improve the DEAS search performance. The first proposed DEAS modification is related with the coding rule of binary-codes. By changing the decoding function of binary-codes and the structure of local search algorithm, the local convergence of the modified DEAS was improved. With this modification, the resulting cost sequence of a local search satisfied the simple decrease condition of the convergence of algorithm. Using the convergence condition of pattern search, the convergence of uDEAS with new encoding method was proven. The second proposed DEAS modification in this thesis deals with an automated and adaptive parameter grouping algorithm for mDEAS. The search patternsof mDEAS mainly depend on the parameter group configuration and they affect the optimization performance. The parameter groups of conventional mDEAS were configured bymanual works with preliminary searches. However, the proposed algorithm dynamically adapts the parameter groups to the cost function landscapes by using the information acquired during the local searches. The improvement of the proposed algorithms was verified by experiments. In addition to the proposed algorithms, this thesis also presents the issues for further researches which is collected during the previous researches.