Real-Value Genetic Algorithm

release date	archive
2011-07-04	rvga-2011-07-04.zip

이 것은, 가장 간단한 GA중에 하나인 RVGA의 구현이다. 실수값 변수 여러개를 입력받아 하나의 실수값으로 좋고 나쁨을 평가할 수 있다면 사용할 수 있다. python으로 작성되었으며, python 함수또는 실행 파일을 평가함수로 사용할 수 있다.

실행 환경

python 스크립트를 실행하기 위해서 python 실행환경을 갖춰야 한다. python install을 참조하여 설치할 수 있다. 기본적으로 python 2.6만 설치되면 실행 가능하지만, 모든 기능을 사용하기 위해서는 python(x,y)를 설치하는 것이 좋다.

빠른 시작

실행환경을 갖춘 다음, 압축을 해제한다.
rvga.py 파일을 텍스트 에디터로 열고, 파일의 앞부분을 수정하여 파라미터를 수정할 수 있다.
- 기본 상태에서는 다음과 같이 설정되어 있다.
  - sum.exe 파일을 평가함수로 사용한다.
  - (0, 100)인 실수 10개를 하나의 개체로 한다.
  - 집단 크기 10, 교배비율 0.5, 돌연변이 비율 0.01, 20 세대 진화
python rvga.py 를 타이핑하여 실행한다.

GEN:    0 / MaxFitness: 680.272174
GEN:    1 / MaxFitness: 694.871464
GEN:    2 / MaxFitness: 694.871464
GEN:    3 / MaxFitness: 720.167049
GEN:    4 / MaxFitness: 757.140851
GEN:    5 / MaxFitness: 757.140851
GEN:    6 / MaxFitness: 815.760021
GEN:    7 / MaxFitness: 818.133231
GEN:    8 / MaxFitness: 853.637147
GEN:    9 / MaxFitness: 853.637147
GEN:   10 / MaxFitness: 853.637147
GEN:   11 / MaxFitness: 862.580602
GEN:   12 / MaxFitness: 862.580602
GEN:   13 / MaxFitness: 872.378785
GEN:   14 / MaxFitness: 881.322240
GEN:   15 / MaxFitness: 881.322240
GEN:   16 / MaxFitness: 890.264835
GEN:   17 / MaxFitness: 890.264835
GEN:   18 / MaxFitness: 895.879939
GEN:   19 / MaxFitness: 895.879939
MaxFitness:895.879939/ Pamaneters: [100, 69.898705073964294, 93.629331393488172, 90.067970536839951, 93.312467091673639, 90.632952576187847, 100, 100, 67.28110686286935, 91.057405088391306]

개요

구현된 RVGA의 특성

이 구현에서는 bit-string이 아닌 실수 배열을 사용하여 진화연산을 수행한다. 실수 배열을 구성하는 하나의 원소는 (0, 1) 사이의 값으로 정규화 되어 있고 이를 이용하여 평가를 제외한 나머지 연산도 수행한다. 평가 하기 바로 전에 최소/최대값을 이용하여 문제에 적합 한 값으로 변환하여 평가를 수행한다.

교배는 1점 교배를 사용하며, 돌연변이는 선택된 원소에 평균 0, 분산 1의 가우시안 노이즈를 추가한다. 선택은 부모와 자식을 모두 평가하여 상위의 집단만 선택하는 방식이다.

예제문제

이 구현에서 평가할 수 있는 문제는 입력으로 최소값/최대값 경계가 있는 실수 여러개를 받아서, 하나의 실수(적합도)로 좋고 나쁨을 평가할 수 있는 문제이다.

예를 들면, 0에서 100사이의 실수 10개를 입력 받아서, 그 값의 합이 최대가 되는 조합을 찾는 문제를 생각해 보면, 입력은 10개의 실수가 되며, 적합도로 실수의 합을 출력하는 함수로 정의할 수 있다. 이는 다음과 같이 표현할 수 있다.

$fitness = \sum_{i=0}^{10} x_i$

이때, 최대값이 나오는 경우는 모든 입력이 100이 되어 합(적합도)이 1000이 되는 경우이다.

사용 방법

"""
사용자가 평가함수, 파라미터를 여기서 지정한다.
"""
# 평가함수
# C언어로 작성한 함수는 컴파일 하여 exe 파일 형태로 바꾼다.
# python으로 작성한 함수는 import 하여 함수 이름만 지정하면 된다.
func = "sum.exe"    # C언어 예, 실행파일의 이름
#func = sum        # python의 예, 함수의 이름
 
# 최적화 시킬 파라미터
# 파라미터의 최소값, 최대값을 지정한다.
# boundary = [(p1 최대값, p1 최소값), (p2 최대값, p2 최소값), ...] 과 같은 형식으로 한다. 
#     최대값은 최소값 보다 작아야 한다.
boundary = [(100, 0)] * 10     # [(100, 0), (100, 0), (100, 0), ...] 을 100개 나열한 것
# 각종 파라미터를 여기서 설정한다.
params = {
    "popSize": 10,            # 집단 크기
    "xoverRate":0.5,          # 교배 비율
    "mutationRate":0.01,      # 돌연변이 비율
    "generation":20,          # 세대
 
    "plotName":"rvga.png",    # 최대 적합도, 평균 적합도 그래프 파일 이름
    "logName":"history.log",  # 최대 적합도 변화를 기록한 파일 이름
}

rvga.py 스크립트를 텍스트 에디터로 열면 처음 부분이 다음과 같다. 이 부분을 수정하여 평가 함수를 지정해 주거나 GA 파라미터를 지정해 줄 수 있다. 이 아래 부분은 RVGA의 로직을 수정할 것이 아니라면 수정할 필요가 없다.

평가 함수

func 부분을 수정하여 평가함수를 지정할 수 있다. 크게 두가지 방법이 있는데, 파이썬 함수의 이름으로 지정해 주거나, 실행파일의 이름을 문자열로 지정한다.

예로 보인 sum 함수는 파이썬의 내장함수로서 숫자로 구성된 리스트를 모두 합하여 반환하는 함수이다. 파이썬으로 평가함수를 작성할 때도 이와 같이 숫자열 리스트를 입력으로 받아서 실수 하나를 반환하는 함수를 사용해야 한다.

func = “sum.exe”와 같이 실행파일로 지정해 주면, 해당 실행파일을 평가함수로 사용한다. 이는 다른 언어로 구현된 평가함수를 사용할 때 사용한다. 이 실행파일에 입력은 인자로 제공되며, 적합도는 표준 출력 스트림으로 특정 형식으로 출력한다. 예를 들어 C 언어라면, printf 함수를 사용한다. 적합도를 츨력하는 형식은 /FITNESS/{적합도}/형식으로 출력해야 한다. 예를 들면 아래와 같다.

c:/> sum 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0
/FITNESS/55.000000/

예제에 사용된 sum.exe는 압축파일에 포함되어 있다.

실수 배열의 최소/최대 값 경계

boundary 리스트를 [(p1 최대값, p1 최소값), (p2 최대값, p2 최소값), …] 형식으로 초기화 한다. 예를 들면, 입력 변수가 두 개이고, 이것을 첫 번째 변수의 최대값이 100 최소값이 0, 두 번째 변수의 최대값이 50 최소값이 -50 이라면 다음과 같이 초기화 한다.