Estimation of Distribution Algorithms (EDA) can build complex models of variables. If problem has high-order building block (BB) such as deceptive trap function and determining optimal structure for molecules, it is hard to solve using conventional genetic algorithms.
One of the successful algorithms of EDA, Extended Compact Genetic Algorithm (ECGA) makes groups among variables, which could determine BBs in the problem. However, ECGA uses greedy search for model building process and greedy search is computationally expensive in the large problems.
We propose a new model building process, called Evolvable Marginal Product Model (EMPM), to reduce time consuming process in ECGA. Over 90% of processing time in ECGA is making Marginal Product Model (MPM). To make MPM, ECGA conducts calculating combined complexity which is composed of model complexity and compressed population complexity.
In EMPM, we build MPM history in the first greedy search. After then, we generate new MPM using MPM history. In this process, we adopt mutation operator in GA to describe subsets` change in each generation. Also, merging operator work with small probability to accelerate convergence.
This algorithm has an advantage to reduce calculating combined complexity criterion (CCC). In comparison with original ECGA, proposed algorithm reduces the number of CCC evaluations at least 3 times in the mk-deceptive trap functions and folded trap functions without loss of accuracy. Compared to ECGA with cache model, proposed algorithm is still faster in the same problem.
Finally, We choosed Icing Spin-Glasses (ISG) problem to verify proposed algorithm`s performance in the real-world problem and EMPM shows good performance in the ISG problem.
변수 간의 확률 분포를 추측하는 알고리즘 (Estimation of Distribution Algorithms, EDA) 들은 변수 사이의 관계를 다양한 방법으로 모델링 할 수 있다. 문제 자체가 복잡한 Building block (BB)을 가진 함정 문제라거나 원자 간의 가장 안정한 배열을 찾는 문제 등은 흔히 알려진 유전자 알고리즘으로는 해결하기가 쉽지 않다.
성공적인 EDA 중 하나로 평가받고 있는 확장형 컴팩트 유전자 알고리즘은 변수들을 관련있는 그룹별로 묶어서 그 그룹이 하나의 BB를 나타내도록 한다. 하지만 확장형 컴팩트 유전자 알고리즘에서 변수 간의 관계를 모델링하기 위해 greedy search를 이용하는데 문제가 커지면 커질수록 컴퓨터 자원을 많이 할애해야 하는 문제가 있다.
본 논문에서는 진화형 한계 곱 모델이라는 개념을 도입하여, 확장형 컴팩트 유전자 알고리즘에서 90\% 이상의 시간이 소요되는 확률 모델링 시간을 줄이고자 한다. 확률 모델을 만들기 위해 확장형 컴팩트 유전자 알고리즘은 모델의 복잡도와 모델의 엔트로피의 합인 복합적 복잡도 기준을 통해 확률 모델을 평가한다.
진화형 한계 곱 모델에서는 확률 모델을 만들기 위해 greedy search를 처음 할 때 만들어지는 모델들을 모델 이력이라는 것에 집어넣고, 이후에는 모델 이력에 있는 각 확률 모델들을 유전자 알고리즘에서 가져온 변이 연산자를 통해 그룹들의 변화를 표현한다. 또한, 그룹 합 연산자를 통해 모델들이 빠르게 수렴하는 것을 돕는다.
이 알고리즘은 확률 모델을 평가하는 복합적 복잡도 기준을 연산하는 횟수를 줄이는 장점을 갖는다. 기존의 확장형 컴팩트 유전자 알고리즘과 비교해 보면 논문에서 사용된 함정 문제의 경우 정확도의 손실 없이 최소 3배 이상 연산 횟수가 줄어드는 것을 알 수 있다. 캐쉬를 이용한 확장된 소형 유전자 알고리즘과 비교해 보더라도 제안된 알고리즘이 약간 빠르다는 것을 확인할 수 있었다.
마지막으로, 실제 현상에 적용해 보기 위해 원자간의 최적 배열을 찾아 가장 낮은 에너지를 갖게 하는 문제에 본 알고리즘을 도입하여 좋은 결과를 얻을 수 있었다.
