Instead of the genetic operators such as crossover and mutation, compact genetic algorithms (CGAs) use a probability vector (PV) for the current population to reproduce offsprings of the next generation. Therefore, the original CGA can be easily implemented with no parameter tuning of the genetic operators and with reducing memory requirements. Many researchers have suggested their own schemes to improve the performance of the CGA, such as quality of solutions and convergence speed. However, these researches mainly have given fast convergence to the original CGA. They still have the premature convergence problem resulting in the low quality of solutions. Besides, the additional control parameters such as $\eta$ of neCGA are even required for several CGAs.
In order to tackle these challenges of CGA, we employ two bayesian concepts: belief vectors (BVs) and parameter learning method used in augmented byaesian networks. First, we propose two new schemes using BVs, called CGABV (an acronym for CGA using belief vectors) and CGABVE (an acronym for CGABV with elitism), in order to improve the performance of conventional CGAs by maintaining the diversity of individuals. For this purpose, the proposed algorithms use a BV instead of a PV. Each element of the BV has a probability distribution with a mean and a variance, whereas each element of a PV has a singular probability value. Accordingly, the proposed BV enables to affect the performances by controlling the genetic diversity of each generation. In addition, we also propose two variants of the proposed CGABV and CGABVE, Var1 and Var2, employing the entropy-driven parameter control scheme in order to avoid the difficulty of designing the control parameter ($\lambda$). Experimental results show that the proposed variants of CGAs outperform the conventional CGAs. For investigating the diversity of each CGA, the entropy is employed and calculated at each generation. Finally, we discuss the effect of $\lambda$ related to the variances of the BV through the additional experiment.
After then, we also present a bayesian-based compact genetic algorithm (bCGA) employing a new update strategy of the probability vector (PV) based on bayesian networks. Even if the update of the PV is a core in the CGA, the PV is heuristically updated by a static population size in the most previous works. In this dissertation, we try to improve the updating scheme not using the population size, but using the bayesian information given by the previous generations. For this purpose, we utilize the parameter learning scheme of an ABN. In order to resolve the diversity problem still remaining, we employ the `PV reset` approach. Moreover, the usefulness of the proposed probabilistic approach is empirically investigated by comparing with the original CGA and other CGAs. For this purpose, 63 selective benchmark functions are considered as test functions for a comparative study. In addition, the proposed bCGAs are implemented in the sensor deployment problem.
최근 통신 기술과 반도체 기술의 발달과 함께 임베디드 시스템에 대한 관심이 높아지고 있다. 이 임베디드 시스템은 과거 중앙 집중적인 시스템이 갖고 있던 많은 문제점을 해소할 수 있는 방법론으로 대두 되고 있기 때문이다. 임베디드 모듈은 점점 더 소형화 되며 서버로 전송할 데이터를 자체 가공하는 기술 또한 요구 되고 있다. 이러한 임베디드 시스템을 구성하는데도 마찬가지로 최적화 기법을 필요로 한다. 이때 여기에 추가되는 최적화 알고리즘은 주기적으로 짧은 시간 안에 임베디드 시스템이 수행하던 기능을 계속 유지하면서 수행되어야 한다. 최근 최적화 기법 가운데 성능 면에서 가장 널리 사용되고 있는 진화 연산 기법의 경우, 이전 세대에서 다음 세대의 자손들을 생성하기 위해 많은 양의 연산을 필요로 한다. 이는 임베디드 시스템의 기본 주기를 넘어서 시스템의 오동작을 유발할 수 있어, 일반적으로 임베디드 환경에 어울리지 않는다고 알려져 있다. 하지만 소형 유전자 알고리즘의 경우 세대 사이에 많은 연산을 필요로 하지 않으며 제한된 메모리 환경에서도 잘 동작한다는 것이 알려지며 주목을 받고 있다.
이러한 동기에서 본 논문은 소형 유전자 알고리즘 자체를 개선하려는 시도를 하였다. 기존의 관련 연구들은 대부분 소형 유전자 알고리즘의 기본 틀을 유지한 채 응용 분야에 특화된 알고리즘을 개발하는 쪽으로 초점이 맞춰져 있다. 하지만 응용 연구 이전에 알고리즘 측면에서 개선이 필요하다고 생각되어 본 연구를 진행하였다. 본 논문에서는 소형 유전자 알고리즘의 핵심인 확률 벡터 (Probability vector)의 각 요소에 단일 값이 아닌 확률 분포 개념을 추가하여 새로운 형태의 소형 유전자 알고리즘을 제안하였다. 이를 위해 2가지 개념을 도입하였는데, 하나는 신뢰 벡터 (Belief vector) 개념이며 또 다른 하나는 베이지안 네트워크 개념이다.
제안된 각 알고리즘들의 성능을 검증하기 위해 63개의 다양한 벤치마크 문제들에 적용하였으며 그 결과 탐색 공간이 납작한 계곡 모양을 하고 있는 몇가지 특정 문제들에 취약한 모습을 보이기는 하나 63개 중 거의 대부분의 문제에서 제안된 베이지안 기반의 소형 유전자 알고리즘이 가장 좋은 성능을 보여 주였다. 실제 DSP TMS320F2812 기반한 임베디드 시스템에서 각 소형 유전자 알고리즘을 비교한 결과, 메모리 소모 측면에서나 연산 량 측면에서 기존의 소형 유전자 알고리즘과 동일한 수준을 유지하는 것을 볼 수 있었다. 즉 다시 말해서 제안된 베이지안 기반 소형 유전자 알고리즘의 경우 일반적인 소형 유전자 알고리즘 만의 장점을 잘 유지하면서 기존의 소형 유전자 알고리즘들 보다 나은 탐색 성능을 얻을 수 있었다.
이러한 결과를 바탕으로 실제 임베디드 환경에서 센서 배치 문제를 해결하는 실험을 진행하였다. 상용 RFID 시스템으로 부터 얻은 데이터들을 이용하였다. 또한 실제 맵 정보를 가져다가 실험을 진행하였으며 사용가능한 센서의 개수가 갑자기 달라지는 다양한 상황을 가정하여 실험을 진행하였다. 여러 실험 결과 제안된 기법이 다른 소형 유전자 기법들보다 이 문제에서는 보다 나은 성능을 보여주는 것을 볼 수 있었다.
