Evolutionary algorithm (EA), mimicking biological evolution in nature, is a well-known optimization algorithm for solving a black-box optimization problem. Different from gradient-based methods, EA does not require any prior knowledge about the problem. Different from EA, swarm intelligence (SI), mimicking collective behavior in nature, is another optimization algorithm. Generally, EA and SI start with a randomly distributed population and update the population by reproducing offspring with unique operators. For the performance improvement, additional components are combined with EA and SI or numerous reproduction variants are proposed in EA and SI.
With regard to the additional components, opposition-based learning (OBL), introduced as a new scheme for machine intelligence, has been broadly combined with EA and SI due to the simplicity and adaptability. In OBL, estimates and counter estimates are considered simultaneously to accelerate the search or learning process. Mathematical and experimental proofs show that opposite points are more beneficial than random points.
With regard to the reproduction variants, parameter-oriented reproduction variants which change the search step magnitude and/or direction to take effective steps and individual distribution-oriented reproduction variants which distribute the individuals in the population using distribution center and distribution degree have been proposed. Generally, the former group (parameter-oriented) requires parameters that control the search parameters of the original algorithms, whereas the latter group (individual distribution-oriented) appears to be almost parameter-free.
Also, in many proposed algorithms, randomness is added to the algorithms to accelerate the search process, make the algorithm robust, and escape the local optima. A beta distribution, which is rarely used, is a probability distribution whose characteristic is defined by two parameters. The beta distribution has an advantage over other probability distributions in that its domain is bounded and it provides a variety of shapes depending on its parameters. However, because the existing researches use mean and standard deviation when adopting the beta distribution, there exist some limitations.
Therefore, in this thesis, new parameters are defined to use a beta distribution without limitation and two beta distribution utilizations to control the search magnitude of the algorithm are proposed: one for adding randomness to OBL and the other for individual distribution-oriented reproduction.
The first utilization is OBL using a beta distribution with changes in partial dimensions and selection scheme (BetaCOBL). BetaCOBL controls degree of opposition through various shapes of the beta distribution, changes a subset of dimensions into opposite values, and switches the selection scheme. The second utilization is a beta distribution-based bare bones reproduction (B³R). B³R controls the search magnitude through the beta distribution and mixes the information of the original individual with the reproduced offspring. BetaCOBL and B³R are developed into DE embedding BetaCOBL (BetaCODE) and two-phase B³R optimization (TPBO) respectively. The proposed algorithms are tested on various test functions and two real world applications and compared with other algorithms with respect to the performance criteria. The results indicate that the proposed algorithms outperform or perform comparatively to the comparison group especially in terms of solution accuracy and reliability.
진화 알고리즘 (Evolutionary algorithm)은 자연의 생물학적 진화 과정을 모사하여 주어진 문제에 대한 해답을 찾는 최적화 알고리즘 중 하나로 기울기 기반 기법 (Gradient-based method)과 달리 문제에 대한 어떠한 사전 지식도 필요하지 않다는 장점을 가지고 있다. 군집 지능 (Swarm intelligence)은 자연 속 군집 행동을 모사하는 또 다른 최적화 알고리즘이다. 어떤 특성으로부터 영감을 받았든, 진화 알고리즘이나 군집 지능은 탐색 공간에 무작위로 분포된 개체군 (Population)으로 시작하여, 고유의 방법으로 자손을 생산하여 개체군을 갱신시키며, 성능 개선을 위해 알고리즘에 부가적인 요소를 추가하거나 새로운 자손 생산 방법이 제안되었다.
부가적인 요소로, 인공 지능 (Artificial intelligence) 분야에서 제안된 역기반 학습법(Opposition-based learning)이 널리 쓰여왔는데, 이 역기반 학습은 추정치와 역 추정치를 동시에 고려하여 탐색이나 학습 과정을 가속하는 데 쓰여 왔다. 역기반 학습의 이로움은 이론과 실험을 통해 증명되었다. 최적화 알고리즘의 주된 목적이 적은 계산 자원을 소비하면서 좋은 해를 찾는 것이 목적이므로 진화 알고리즘이나 군집 지능에 결합된 역기반 학습법이 성능 향상에 도움을 줄 수 있다.
새로운 자손 생산법은 크게 파라미터 지향 생산법과 개체 분포 지향 생산법으로 나눌 수 있는데, 전자는 탐색 규모 (Search magnitude)나 탐색 방향 (Search direction)을 파라미터를 통해 바꾸어 유효한 탐색을 이끌어내는 반면 후자는 개체를 분포 중심(Distribution center)과 분포 강도 (Distribution degree)에 따라서 분포시켜 유효한 탐색을 이끌어 낸다. 일반적으로 전자는 파라미터를 조절하는 또 다른 파라미터가 필요한 반면 후자는 파라미터에 구애 받지 않을 수 있다.
제안된 많은 방법에서 탐색 과정을 가속시키고, 알고리즘을 강인하게 만들며, 국소 최적점 (Local optimum)을 피하기 위해 알고리즘에 무작위성 (Randomness)을 집어 넣어왔는데, 주로 가우시안, 코시, 균등 확률 분포 (Gaussian, Cauchy, and uniform distributions)들이 사용되어 왔다. 베타 확률 분포 (Beta distribution)는 가우시안, 코시, 균등 확률 분포에 비해 널리 사용되지는 않았지만, 유계 정의역 (Bounded domain)을 가지고, 파라미터 값에 따라 다양한 모양을 지닌다는 장점을 가지고 있어 이 모양의 변화에 따라 탐색 규모를 제어할 수 있다. 하지만 기존의 베타 확률 분포 활용법은 평균 (Mean)과 표준 편차 (Standard deviation)를 사용하여 몇몇 제약이 존재했다.
따라서 본 논문에서는 베타 확률 분포를 위한 새 파라미터를 정의하고 새 파라미터에 의해 제약 없이 다양한 베타 확률 분포의 모양을 활용할 수 있는 것을 수학적으로 증명한 뒤, 베타 확률 분포를 활용한 두 가지 탐색 규모 조절 방법을 제안하였다. 첫 번째 방법은 역기반 학습에 베타 확률 분포를 접목한 것 (BetaCOBL)으로 베타 확률 분포를 사용하여 역강도 (Degree of opposition)를 조절하며, 선택 방법 전환을 통해 역기반 학습에서 생성된 역점 (Opposite point)이 개체군에 포함되는 방법을 바꾸었으며, 일부 차원에 대해서만 역값 (Opposite value)으로 바꾸어 원래 개체 (Individual)의 유용한 정보가 역점에 포함되어 다음 세대 (Generation)로 전달될 수 있도록 하였다. 두 번째 방법은 베타 확률 분포에 기반한 자손 생성법 (B³R)으로 베타 확률 분포의 분포 중심과 분포 강도를 최빈값 (Mode)과 새로 제안된 파라미터로 조절하여 탐색 영역을 벗어나지 않으면서 유효한 후보 (Candidate)를 생산하고, 원래 개체 (Individual)의 유용한 정보가 자손에 포함되어 다음 세대로 전달될 수 있도록 하였다.
베타 확률 분포에 기반한 역기반 학습은 차등 진화 (Differential evolution)와 결합하여 수렴 속도를 높이면서 탐색 능력 또한 향상시키는 알고리즘 (BetaCODE)으로 발전되었고, 베타 확률 분포에 기반한 자손 생성법은 착취 (Exploitation) 특성을 가지는 다른 자손 생성 방법과 결합한 혼성 알고리즘 (TPBO)으로 발전되었다. 제안된 알고리즘들의 성능을 평가하기 위해 다양한 벤치마크 함수에 적용하여 해의 정밀도, 해를 찾을 확률, 해를 찾는 속도의 3가지 지표로 성능을 평가하여, 제안된 알고리즘이 비교 알고리즘에 비해 특히 해의 정밀도와 해를 찾을 확률에서 유효하다는 것이 입증되었고, 실 세계 적용례로 가우시안 확률 과정 (Gaussian process)을 이용한 로봇 팔의 경로-완만화 (Path-smoothing)와 종적인 질량 중심 (Vertical center of mass) 동작을 가지는 휴머노이드 로봇의 이족 보행에 적용하여 비교 알고리즘과의 성능에서 우위를 점하는 것을 볼 수 있었다.
