티스토리 뷰
위키 백과 참조.
개요:
유전 알고리즘은 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 낸다.
구성:
1)요구조건 :
유전 알고리즘을 어떤 문제에 적용하기 위해서는 해를 유전자형식으로 표현이 가능해야한다.
2)흐름:
- 초기집단은 랜덤을 이용하여 구성할수 있다.
- 적합도가 높은해를 이용하여 다음세대로 적합도가 높은 유전자 특성을 물려받게 하여 최적해에 가까워 지도록 한다.
- 교배 이외에도 변이를 통하여 최적해에 가까워 질수 있다.
연산:
1) 선택:
한 세대에서 다음 세대로 전해지는 해의 후보가 되는 해들을 선택한다. 선택 방법에는 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있다.
2)교차:
실제 생명체의 염색체가 재조합되는 과정에서 부모 염색체의 일부분이 특정 위치를 기준으로 서로 바뀌어 결합되는 경우가 있는데, 이 현상을 교차라고 한다
3)변이:
일반 생명체에서, 유전자의 교배 뿐 아니라, 하나의 유전자가 직접적으로 변이를 일으켜서 주어진 환경에서 살아남을 확률 역시 존재한다.
4)대치:
교차·변이 등을 거쳐서 만들어진 새로운 해를 해집단에 추가하고, 기존 해 중 열등한 해를 가려내 서 제외시키는 연산이다.
예:
{1, 5, 6, 8, 3, 7, 3, 5, 9, 0} 중 3개를 골라서 20으로 만드는 문제가 있다고 하자. 여기서 유전체는 각 숫자이며, 각 해의 유전자는 (1,5,3)와 같이 유전체 3개의 집합으로 이루어진다. 적합도 함수를 20 과 얼마나 가까운지를 나타내는 값으로 둔다면, (1,5,3)에 대한 적합도는 f( (1,5,3) ) = 11이 된다.
먼저 첫 세대를 아무렇게나 생성한다. 첫 세대가 만약 { (1,5,3) (8,0,9) (9,9,8) (3,7,5) } 으로 형성되 었다고 하자. 각각의 적합도를 구하면, { 11, 3, 6, 5 }이 되며, 이 값이 높을수록 20에서 멀기 때문에 해로서 부적당하다는 것을 의미하며, 따라서 세대를 거침에 따라 살아남을 확률이 낮게 된다.
다음 세대를 형성하기 위해, 이 세대의 개체중 2개의 유전자를 선택한다. 이때 선택은 적합도를 기준으로 확률적으로 선택한다. (룰렛 알고리즘이 자주 쓰인다) 위의 예에서 적합도가 3인 (8,0,9)는 적합도가 6인 (9,9,8)에 비해 훨씬 높은 선택 기회를 가진다. 선택된 2개의 유전자의 유전체는 랜덤한 위치에서 교환되어 새로운 세대가 형성된다. 예로 (8,0,9), (9,9,8) 이 선택되었고 교배위치가 2번째 자리로 무작위로 결정되었다면 다음 세대의 개체는 (8,9,8), (9,0,9)가 되며, 각각의 적합도는 5, 2가 된다.
-- 자바로 위에 예를 코딩해보았다.--
{1, 5, 6, 8, 3, 7, 3, 5, 9, 0} 중에 3개의 램덤위치에서 숫자를 선택해서
3개의 유전체를 가진 5개의 유전자를 후보를 두었다.
세대변화할때에는 최적의해를 가진 2개의 유전자를 5개로 복사하고
복사한 1,2,번 유전자는 1번째 유전체를 서로 교환하고
복사한 3,4,번 유전자는 2번쨰 유전체를 서로 교환하고
마지막 5번 유전자는 3번째 유전체를 원본 2번 유전자의 유전체와 교환하였다.
--- 결과 ---
최적의 해가 3세대부터 통일하게 나오는 것을 볼수있다.
이게 제대로 한건지 확실하지 않지만 내가 원하는 결과는 나왔다.
--코드--
import java.util.ArrayList;
import java.util.List;
public class number {
static int generation =1;
public static void main(String args[]) {
List generationList = new ArrayList();
int[] dielectrics = {1,5,6,8,3,7,3,5,9,0};
Gene[] gene = initGene(dielectrics);
nextGeneration(gene,5);
}
static Gene[] initGene(int[] dielectrics){
Gene[] gene = new Gene[5];
for(int i = 0 ; i < 5;i++){
int[] dielectric = new int[3];
for(int j = 0 ; j <3;j++){
dielectric[j] = dielectrics[(int)Math.floor((Math.random() *10))];
}
gene[i] = new Gene(dielectric);
}
printGene(gene);
return gene;
}
static void BubbleSort(Gene[] gene){
for(int i = gene.length -1 ; i >0 ; i--){
for(int j = 0 ; j gene[j+1].getFitness()){
Gene tmp = gene[j];
gene[j] = gene[j+1];
gene[j+1] = tmp;
}
}
}
}
static Gene[] nextGeneration(Gene[] gene,int loop) {
Gene[] newGene = new Gene[5];
BubbleSort(gene);
try{
for(int i= 0 ; i < 5; i++)
newGene[i] = (Gene) gene[i%2].clone();
}catch(CloneNotSupportedException cnse){
System.out.println("객체 복사 에러" +cnse.getMessage());
}
newGene[0].changeGene(0, gene[1].getGene()[0]);
newGene[1].changeGene(0, gene[0].getGene()[0]);
newGene[2].changeGene(1, gene[1].getGene()[1]);
newGene[3].changeGene(1, gene[0].getGene()[1]);
newGene[4].changeGene(2, gene[1].getGene()[2]);
generation++;
printGene(newGene);
loop--;
if(loop !=0){
nextGeneration(newGene, loop);
}
return newGene;
}
static void printGene(Gene[] gene){
System.out.println("-----------------"+generation+"세대------------------");
for(int i=0 ; i < 5 ;i++){
System.out.print((i+1)+"번 유전자");
for(int j=0;j<3;j++){
System.out.print(":"+gene[i].getGene()[j]);
}
System.out.println(" 적합도 :"+gene[i].getFitness());
}
}
}
public class Gene implements Cloneable{
private int[] gene = new int[3];
private int fitness = 0;
public Gene(int[] gene){
for(int i =0 ; i < gene.length ; i++ )
this.gene[i] = gene[i];
setFitness();
}
public int[] getGene() {
return gene;
}
public int getFitness() {
return fitness;
}
public void setFitness(){
int sum =0;
for(int i=0 ;i < 3; i++){
sum += gene[i];
}
this.fitness=Math.abs(20-sum);
}
public void changeGene(int index,int value){
this.gene[index] = value;
this.setFitness();
}
@Override
protected Object clone() throws CloneNotSupportedException {
Gene gene = (Gene) super.clone();
gene.gene = (int[])this.gene.clone();
return gene;
}
}