/*
GASample - Sample of Genetic Algorithm
Copyright (C) 2004 youjin lee(justbear@naver.com)
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
/**
* Organism(생물체) 클래스는 개개의 생물 개체를 나타냅니다.
* 각 생물체는 염색체(chromosome)를 가지고 있으며 유전을 할때 부모의 염색체가
* 서로 꼬여서(crossover) 새로운 유전자 정보를 가진 자식을 만들어 냅니다.
* @author justbear
*/
class Organism {
/**
* 생물체의 염색체(chromosome)를 나타내며, 유전자 알고리즘(Genetic Algorithm)에 사용할
* 파라미터 배열로 사용합니다.
* int 타입으로 고정합니다.
*/
int[] chromosome;
/**
* fitness 값을 저장하는데 사용합니다. fitness란 구하고자 하는 해답과 얼마나 적정한가를
* 나타내는 지표로 여기 예에서는 숫자가 0에 가까울수록 해답과 가까운 값이 됩니다.
*/
int fitness;
/**
* 생성자로써 GASample.CHROMOSOME_SIZE 개수만큼 int 배열을 생성합니다.
* CHROMOSOME_SIZE란 개개의 생물체가 가지는 염색체의 개수를 나타냅니다.
*/
public Organism() {
chromosome = new int[GASample.CHROMOSOME_SIZE];
}
}
/**
* OrganismComparator 클래스는 인구(Population, 생물체의 모임)을 정렬할때
* 사용합니다. Comparator의 사용법은 JDK API 문서를 참조하세요.
* @author justbear
*/
class OrganismComparator implements Comparator {
public int compare(Object o1, Object o2) {
Organism c1 = (Organism) o1;
Organism c2 = (Organism) o2;
return c1.fitness - c2.fitness;
}
}
/**
* 이 예제는 유전자 알고리즘으로 방정식의 인수 값을 구하는 방법을 보여줍니다.
* 방정식은 a+2b+3c+4d+5e=100 으로 이 식에 적당한 a, b, c, d, e 값을 구합니다.
* 이 식은 calculateFitness() 메소드에서 보실 수 있습니다.
* @author justbear
*/
public class GASample {
/**
* 유전자 알고리즘에 사용할 Organism의 전체 개수
*/
private int POPULATIONS_SIZE = 2048;
/**
* 유전자 알고리즘에서는 새로운 세대(Generation)가 나타날 때마다 뛰어난 형질을 가진
* 생물체는 계속 생존하여 그 형질을 자손에서 유전시키게 됩니다. ELITISM_SIZE는 전체
* 인구(Population, 생물체의 모임) 중에서 자신의 형질을 계속 유전할 객체의 개수를
* 나타냅니다. 즉, 전체 생물체 중 ELITISM_SIZE 개수만큼의 뛰어난 생물체는 그 유전자
* 정보를 변화시키지 않은 부모 그대로의 자식을 생성합니다.
*/
private int ELITISM_SIZE = 100;
/**
* 한 염색체(chromosome)가 가지는 최대값
*/
private int MAX_CHROMOSOME_DATA = 100;
/**
* 생물체(Organism)가 가지는 염색체(chromosome)의 개수
*/
public static int CHROMOSOME_SIZE = 5;
/**
* 인구(Population, 생물체의 모임)을 나타내는 변수
*/
private LinkedList populations;
/**
* 유전자 알고리즘 계산에서 사용하는 인구(Population, 생물체의 모임) 변수의 버퍼
*/
private LinkedList buffer;
/**
* GASample 생성자
*/
public GASample() {
doGA();
}
/**
* 유전자 알고리즘을 실행
*/
public void doGA() {
initPopulations();
// 끝나는 조건이 맞을 때까지 반복합니다.
while (true) {
evaluate();
sortPopulations();
printOrganism(0);
checkFinish();
elitism();
crossover();
mutate();
swap();
}
}
/**
* 인구(Population, 생물체의 모임)을 초기화함
*/
public void initPopulations() {
populations = new LinkedList();
buffer = new LinkedList();
for (int i = 0; i < POPULATIONS_SIZE; i++) {
populations.add(initOrganism());
}
}
/**
* 인구(Population, 생물체의 모임)의 각 생물체의 fitness 값을 설정합니다.
*/
public void evaluate() {
for (int i = 0; i < POPULATIONS_SIZE; i++) {
Organism c = (Organism) populations.get(i);
c.fitness = calculateFitness(c.chromosome);
}
}
/**
* 인구(Population, 생물체의 모임)의 각 생물체(Organism)를 fitness가 낮은 순으로
* 정렬합니다. fitness 값이 낮을 수록 더 뛰어난, 즉 찾고자 하는 해답과 유사한
* 생물체(Organism) 입니다.
*/
public void sortPopulations() {
// 매번 정렬을 할때마다 OrganismComparator 객체를 생성하는 것은 좋지 않습니다.
// 처음에 하나 생성해서 계속 사용하는 것이 좋습니다. 설명을 위하여 간단히 합니다.
Collections.sort(populations, new OrganismComparator());
}
/**
* 반복을 중단하는지를 확인합니다. 반복을 중단하는 것은 유전자 알고리즘에서 더이상 새로운
* 세대(Generation)를 생성하지 않는 것을 의미합니다. 첫번째 생물체(Organism)의 fitness 값이
* 0인 경우 프로그램을 중단합니다.
*/
public void checkFinish() {
Organism c = (Organism) populations.get(0);
if (c.fitness == 0)
System.exit(0);
}
/**
* 인구(Population, 생물체의 모임) 중에서 뛰어난 유전자를 지닌 생물체(Organism)를
* ELITISM_SIZE 개수만큼 인구(Population, 생물체의 모임) 버퍼에 저장합니다.
*/
public void elitism() {
for (int i = 0; i < ELITISM_SIZE; i++) {
Organism c = new Organism();
c.chromosome = ((Organism) populations.get(i)).chromosome;
c.fitness = ((Organism) populations.get(i)).fitness;
buffer.add(c);
}
}
/**
* 인구(Population, 생물체의 모임) 중에서 임의의 두 생물체(Organism)를 교배(crossover)시켜
* 새로운 자식 생물체(Organism)를 만들고 인구(Population, 생물체의 모임) 버퍼에 저장합니다.
*/
public void crossover() {
for (int i = 0; i < POPULATIONS_SIZE - ELITISM_SIZE; i++) {
// getRandomPopulation()의 값이 똑같은지 확인하는 작업이 필요합니다.
// 간단히 하기 위하여 그 과정을 생략합니다.
Organism c1 = (Organism) populations.get(getRandomPopulation());
Organism c2 = (Organism) populations.get(getRandomPopulation());
// getRandomPositionOfPopulation()의 값이 0인지 확인할 필요가 있습니다.
// 간단히 하기 위하여 그 과정을 생략합니다.
int position = getRandomChromosomePosition();
Organism c = new Organism();
System.arraycopy(c1.chromosome, 0, c.chromosome, 0, position);
System.arraycopy(c2.chromosome, 0, c.chromosome, position, CHROMOSOME_SIZE
- position);
buffer.add(c);
}
}
/**
* 인구(Population, 생물체의 모임) 중에서 임의의 한 생물체를 돌연변이(mutate) 시킵니다.
* 돌연변이(mutate)를 시키는 이유는 교배(crossover)만 시키는 경우보다 더 random한 값을
* 생성하여 알고리즘의 효율을 높이기 위해서입니다.
*/
public void mutate() {
Organism c = (Organism) buffer.get(getRandomPopulation());
int position = getRandomChromosomePosition();
c.chromosome[position] = (int) (Math.random() + MAX_CHROMOSOME_DATA);
}
/**
* 인구(Population, 생물체의 모임) 버퍼의 값을 원래 인구(Population, 생물체의 모임) 변수에
* 복사합니다. 즉 새로운 세대(New Generation)를 만듭니다.
*/
public void swap() {
for (int i = 0; i < POPULATIONS_SIZE; i++) {
populations.remove(0);
}
for (int i = 0; i < POPULATIONS_SIZE; i++) {
populations.add(buffer.remove(0));
}
}
/**
* 초기화된 Organism 객체를 반환합니다. Organism의 chromosome 변수 배열들의 초기값은
* MAX_CHROMOSOME_DATA 값을 초과하지 않습니다.
*
* @return 초기화된 Organism 객체
*/
public Organism initOrganism() {
Organism c = new Organism();
for (int i = 0; i < CHROMOSOME_SIZE; i++)
c.chromosome[i] = (int) (Math.random() * MAX_CHROMOSOME_DATA);
return c;
}
/**
* 한 생물체(Organism)의 염색체(Chromosome) 중에서 임의의 위치를 반환합니다.
* @return 염색체(Chromosome) 중 임의의 위치
*/
public int getRandomChromosomePosition() {
return (int) (Math.random() * CHROMOSOME_SIZE);
}
/**
* 인구(Population, 생물체의 모임) 중에서 임의의 생물체(Organism)의 위치를 반환합니다.
* @return 인구(Population, 생물체의 모임) 중에서 임의의 생물체(Organism)의 위치
*/
public int getRandomPopulation() {
return (int) (Math.random() * POPULATIONS_SIZE);
}
/**
* 인구(Population, 생물체의 모임) 중의 각각의 생물체(Organism)에 대하여 fitness 값을
* 계산합니다. fitness 값은 절대값으로 나타냅니다.
* @return fitness 값
*/
public int calculateFitness(int[] values) {
return Math.abs(values[0] + 2 * values[1] + 3 * values[2] + 4
* values[3] + 5 * values[4] - 100);
}
/**
* 인구(Population, 생물체의 모임) 중에서 입력받은 위치의 생물체(Organism)의 값을
* 출력합니다. 생물체(Organism)의 염색체(chromosome) 배열을 중간에 스페이스를 두어
* 출력하고, '['와 ']' 사이에 fitness 값을 출력합니다.
* @param 인구(Population, 생물체의 모임) 중에서 출력할 생물체(Organism)의 위치
*/
public void printOrganism(int row) {
Organism c = (Organism) populations.get(row);
for (int i = 0; i < CHROMOSOME_SIZE; i++)
System.out.print(c.chromosome[i] + " ");
System.out.println("[" + c.fitness + "]");
}
/**
* 인구(Population, 생물체의 모임)의 전체 생물체(Organism)의 값을 출력합니다.
* 생물체(Organism)의 염색체(chromosome) 배열을 중간에 스페이스를 두어 출력하고,
* '['와 ']' 사이에 fitness 값을 출력합니다.
*/
public void printOrganisms() {
for (int i = 0; i < POPULATIONS_SIZE; i++)
printOrganism(i);
}
/**
* 실행하기 위한 main 메소드
*/
public static void main(String[] args) {
new GASample();
}
}