GA - 쓰임새와 흐름도

유전자 알고리즘은 뜻밖에 여러 곳에 쓰일 수 있습니다. 각 개체의 적응도(Fitness)를 어떻게 정하느냐에 따라 많은 곳에 사용할 수 있습니다.

1. AI : 이것은 각 개체의 적응도를 AI의 효율성으로 정할 경우 최적의 AI를 만들기 위해 쓰일수 있습니다. 이를테면 미로를 통과하는 AI의 경우, 출구에서 얼마나 가까이 접근했는가, 또는 쉬운 미로부터 시작해서 몇개의 미로를 통과했는가 등을 적응도의 척도로 삼을 수 있습니다.
그러나 이 경우에는, 유전자 알고리즘을 실행하는 환경과, 그 결과물을 실제로 적용해야 할 환경이 정확하게 같을 필요가 있습니다. 그렇지 않으면, 오작동이 일어날 가능성이 매우 높아집니다.

2. 최적의 조합 찾기 : 간단한 보기로 이런 문제가 있을 수 있습니다.

100개의 보석이 있다. 모두 무게와 가치가 다르다. 그 보석들 중에서 100g만 가지고 나갈 수 있다. 100g의 한계 안에서 최대가치의 보석을 가지고 나가려면 어떤 보석들을 가지고 나가야 할까?

이런 문제는 각 개체가 가지고 있는 보석의 총 가치를 적응도로 설정해서 유전자 알고리즘을 돌릴 수 있습니다.

3. 최적의 연결 찾기 : 회로도 등을 설계할때 적용되는 기술입니다. 기판 위에 각종 전자부품을 배열하고 그들끼리 연결을 해야 합니다. 이 연결선은 최소한의 길이, 최소한의 겹침을 필요로 합니다. 이 경우에도 각 연결선의 길이의 합, 겹침수 등을 적응도로 설정할 수 있습니다.

대부분의 경우에 유전자알고리즘의 순서도는 다음과 같습니다.

begin
.. declear Creature creature[GenerationNo] // GenerationNo만큼의 Creature 생성
.. for i := 0, GenerationNo do
..... call GeneInit(creature[i]) // 각각의 creature들의 유전자 초기화
.. end

.. while(1) do
..... for i := 0, GenerationNo do // 모든 creature들에 대해 적응도 계산
........ call TestReady(creature[i]) // i번째 creature가 시험받을 준비(score 초기화)
........ call FitnessCalc(creature[i])// i번째 creature의 적응도 계산
..... end

..... if(endcondition) // 만족할만한 creature가 나왔으면 끝냄
........ break

..... declear Creature nextgeneration[GenerationNo] // 다음세대 creature를 만들 버퍼
..... while(not fill nextgeneration) do // nextgeneration이 채워질 동안 반복
........ Creature a, b
........ while 1 do
........... a := SelectParent() // 적응도에 의해 재생산할 creature 선택
........... b := SelectParent() // a, b에 선택된 것의 복사본 만듦
........... if a != b then // 다른 Creature간의 유전자 혼합을 위해
.............. break
........... end
........ end
........ call CrossOver(a, b) // a, b의 유전자를 섞음
........ call Mutantation(a) // a, b에 적당한 돌연변이 가함
........ call Mutantation(b)
........ store a, b to nextgeneration // a, b를 다음 세대 버퍼에 넣음
..... end
..... creature := nextgeneration // 새로 만들어진 creature들로 계속 실행
.. end
end