참조 : http://www.aistudy.com/biology/genetic/application_moon.htm#_bookmark_2ac7828
2019-716.유전 알고리즘\응용예1
| 라이브러리, JGAP, Jenetics (0) | 2019.02.11 |
|---|---|
| 머신러닝 - 자기조직화지도(Self-Organizing Map, SOM) (0) | 2019.02.11 |
| 유전 알고리즘(Genetic Algorithm)(3)-MST(java) (0) | 2019.02.10 |
| 유전 알고리즘(Genetic Algorithm)(2)-MST(java) (0) | 2019.02.10 |
| CSP vs BFS vs GA for N-Queen (0) | 2019.02.10 |
참조 : https://jdm.kr/blog/104
1) JGAP: 유전자 알고리즘을 위한 자바 무료 라이브러리
2) Jenetics
http://jenetics.io/
| 응용 예 (0) | 2019.02.12 |
|---|---|
| 머신러닝 - 자기조직화지도(Self-Organizing Map, SOM) (0) | 2019.02.11 |
| 유전 알고리즘(Genetic Algorithm)(3)-MST(java) (0) | 2019.02.10 |
| 유전 알고리즘(Genetic Algorithm)(2)-MST(java) (0) | 2019.02.10 |
| CSP vs BFS vs GA for N-Queen (0) | 2019.02.10 |
참조 : https://twinw.tistory.com/15?category=543725
| 응용 예 (0) | 2019.02.12 |
|---|---|
| 라이브러리, JGAP, Jenetics (0) | 2019.02.11 |
| 유전 알고리즘(Genetic Algorithm)(3)-MST(java) (0) | 2019.02.10 |
| 유전 알고리즘(Genetic Algorithm)(2)-MST(java) (0) | 2019.02.10 |
| CSP vs BFS vs GA for N-Queen (0) | 2019.02.10 |
오늘은 저가 짠 유전 알고리즘 설명 해드리겠습니다.
저가 글을 잘 못써 큰 부분으로 큼지막하게 설명하겠습니다.
먼저 유전알고리즘이 진행 되면서 변경되는 염색체 클레스입니다.
//염색체 클레스이다.private class chromosome implements Comparable<chromosome>{ int order[] = null; int fit=0; int useFit=0; chromosome(int ch_len){ order = new int[ch_len]; } public int compareTo(chromosome ch) { return ch.useFit-this.useFit; // 자기 자신이 기준이 되면 오름차순 } //상대가 기준이면 내림차순 feat.sort public boolean isExist(int data, int currentAt){ for(int i=0;i<ch_len;i++){ if(i!=currentAt){ if (order[i]==data) return true; } } return false; }}염색체의 생성자에는 염색체의 길이를 받아 올 수 있도록 만들었습니다.
다음은 메인 클레스인 GA의 생성자 입니다.
private int[][] dataMatrix; private int ch_len, FG_Num, limitSolution, thresholds_fit, eliteNum, newGenerNum; private chromosome[] generationPool; private chromosome[] elite_Chs; private chromosome bestSolution = null; //데이터 + 염색체 길이 + 염색체 갯수 + 목적치 + th_fit + 엘리트수 + 교배횟수 GA(int[][] m_dataMatrix, int m_ch_len, int m_FG_Num, int m_limitSolution, int m_thresholds_fit, int m_eliteNum, int m_newGenerNum){ this.dataMatrix = m_dataMatrix; this.ch_len = m_ch_len; this.FG_Num = m_FG_Num; this.limitSolution = m_limitSolution; this.thresholds_fit = m_thresholds_fit; this.eliteNum = m_eliteNum; this.newGenerNum = m_newGenerNum; generationPool = new chromosome[FG_Num]; elite_Chs = new chromosome[eliteNum]; for(int i=0; i<FG_Num;i++){ generationPool[i] = new chromosome(ch_len); setFirst_G(generationPool[i]); calFit(generationPool[i]); } elite_Chs = setElite(generationPool); G_printf(generationPool,elite_Chs);//1세대 출력 for(int i=0; i<newGenerNum;i++){ generationPool = nextG(generationPool, elite_Chs); elite_Chs = setElite(generationPool); G_printf(generationPool,elite_Chs); //각 세대 확인 if(elite_Chs[0].fit < limitSolution){//작은게 좋은거 bestSolution = elite_Chs[0]; break; }// if(elite_Chs[0].useFit > limitSolution)//큰게 좋은거// bestSolution = elite_Chs[0];// break; } bestSolution = elite_Chs[0]; }제가 구성한 GA 코드는 생성자에서 모든 계산을 끝냅니다.
생성자를 보시면
generationPool = new chromosome[FG_Num];
elite_Chs = new chromosome[eliteNum];
대표적인 변수인 한 세대의 염색체가 모두 있는 염색체 배열과 엘리트 염색체가 들어가는 염색체 배열입니다.
코드는 크게 2부분으로 보시면 됩니다. 1세대를 초기화 하는 부분과 그 외 세대를 생성하고 fit를 계산하는 부분입니다.
for(int i=0; i<FG_Num;i++){
generationPool[i] = new chromosome(ch_len);
setFirst_G(generationPool[i]);
calFit(generationPool[i]);
}
elite_Chs = setElite(generationPool);
첫 번째 for문에서 1세대를 생성 및 초기화를 합니다. 그리고 생성이 끝나면 그 중에서 Fit가 가장 큰 엘리트를 선별합니다.
다음 for문에서는 nextG 함수로 하여 생성되어 있는
generationPool배열과 elite_Chs 배열을 변경합니다.
이때 생성자 파라메터로 받은 최대 세대나 목적치의 값이 나오면 멈춥니다.
다음은 다음 세대를 구하는 NextG함수 입니다.
private chromosome[] nextG(chromosome[] generationPool, chromosome[] elite_Chs){ chromosome[] newGeneration = new chromosome[FG_Num]; int s_ch1=-1, s_ch2=-1; int allArea = 0; int area[] = new int [FG_Num]; for(int i=0;i<FG_Num;i++) allArea+=generationPool[i].useFit; for(int i=1;i<FG_Num;i++){ area[i]=(int)((float)generationPool[i].useFit/allArea*1000); area[i]+=area[i-1]; } for(int i=0;i<eliteNum;i++) newGeneration[i] = elite_Chs[i]; for(int i=eliteNum;i<FG_Num;i++){ s_ch1=-1; s_ch2=-1; while(s_ch1 == s_ch2){ s_ch1 = ch_Select(area); s_ch2 = ch_Select(area); } //System.out.println("ch1 : "+s_ch1+" ch2 : "+s_ch2); newGeneration[i] = crossover(generationPool[s_ch1],generationPool[s_ch2]); mutation(newGeneration[i]); calFit(newGeneration[i]); } return newGeneration;}NextG 함수는 먼저 이전 세대의 엘리트 염색체를 가져옵니다. 그리고 남은 갯수의 염색체는 2개의 이전 세대의 염색체를 반반 합쳐서 새로운 염색체를 합칩니다. (중복된건 당연히 처리 해야겠죠)
그리고 일정 확률로 염색체에 대해서가 아닌 각각의 세포에 대해 돌연변이를 발생시킵니다. 돌연변이에 대한 정의는 GA알고리즘의 성능에 영향을 끼치는데 저는 특정 세포에서 돌연변이가 발생하면 남은 세포와 자리를 바꾸는 식으로 구현했습니다.
아래는 풀코드입니다.
import java.util.Arrays;import java.util.Arrays;public class GA { private int[][] dataMatrix; private int ch_len, FG_Num, limitSolution, thresholds_fit, eliteNum, newGenerNum; private chromosome[] generationPool; private chromosome[] elite_Chs; private chromosome bestSolution = null; //데이터 + 염색체 길이 + 염색체 갯수 + 목적치 + th_fit + 엘리트수 + 교배횟수 GA(int[][] m_dataMatrix, int m_ch_len, int m_FG_Num, int m_limitSolution, int m_thresholds_fit, int m_eliteNum, int m_newGenerNum){ this.dataMatrix = m_dataMatrix; this.ch_len = m_ch_len; this.FG_Num = m_FG_Num; this.limitSolution = m_limitSolution; this.thresholds_fit = m_thresholds_fit; this.eliteNum = m_eliteNum; this.newGenerNum = m_newGenerNum; generationPool = new chromosome[FG_Num]; elite_Chs = new chromosome[eliteNum]; for(int i=0; i<FG_Num;i++){ generationPool[i] = new chromosome(ch_len); setFirst_G(generationPool[i]); calFit(generationPool[i]); } elite_Chs = setElite(generationPool); G_printf(generationPool,elite_Chs);//1세대 출력 for(int i=0; i<newGenerNum;i++){ generationPool = nextG(generationPool, elite_Chs); elite_Chs = setElite(generationPool); G_printf(generationPool,elite_Chs); //각 세대 확인 if(elite_Chs[0].fit < limitSolution){//작은게 좋은거 System.out.println("결과를 구하였습니다."); bestSolution = elite_Chs[0]; break; }// if(elite_Chs[0].useFit > limitSolution)//큰게 좋은거// System.out.println("설정한 최소값에 대한 결과값을 구하지 못하였습니다.");// bestSolution = elite_Chs[0];// break; } bestSolution = elite_Chs[0]; System.out.println("설정한 최소값에 대한 결과값을 구하지 못하였습니다."); } //외부로부터 최고값 출력 public int getBestCost(){ return bestSolution.fit; } //외부로부터 최고값의 결로 출력 public String getBestPath(){ String path=null; for(int i=0; i<ch_len;i++){ path+=bestSolution.order[i]+" "; } return path; } //첫번째 세대를 만들어 주는 함수 - 상황에 따라 변경 private void setFirst_G(chromosome ch){ int[] tempArr = new int[ch_len]; for(int i=0;i<ch_len;i++) tempArr[i] = i; //셔플부분 int seed; int temp; for(int i=1;i<ch_len;i++){ seed=(int)(Math.random()*(ch_len-1))+1; temp = tempArr[i]; tempArr[i]=tempArr[seed]; tempArr[seed]=temp; } ch.order = tempArr; } //염색체에 대한 적합도를 측정한다. //크기가 작은게 좋은 경우 useFit으로 해서 계산한다. Why 그래야 나중에 계산하기 편함 private void calFit(chromosome ch){ int sumOfcost = 0; for(int i=0;i<ch_len-1;i++){ sumOfcost += dataMatrix[ch.order[i]][ch.order[i+1]]; } ch.fit = sumOfcost; if(thresholds_fit==0)//thresholds_fit이 0이면 Fit값이 큰게 좋은거 ch.useFit = sumOfcost; else //반대로 thresholds_fit값이 있으면 작은게 좋은거 ch.useFit = thresholds_fit-sumOfcost; } //엘리트 염색체를 구한다. private chromosome[] setElite(chromosome[] generationPool){ chromosome temp[] = new chromosome[eliteNum+1]; chromosome result[] = new chromosome[eliteNum]; for(int i=0;i<eliteNum;i++) temp[i] = generationPool[i]; for(int i=eliteNum;i<FG_Num;i++){ temp[eliteNum] = generationPool[i]; Arrays.sort(temp); } for(int i=0;i<eliteNum;i++){ result[i] = temp[i]; } return result; } //다음 세대를 구하는 함수이다. private chromosome[] nextG(chromosome[] generationPool, chromosome[] elite_Chs){ chromosome[] newGeneration = new chromosome[FG_Num]; int s_ch1=-1, s_ch2=-1; int allArea = 0; int area[] = new int [FG_Num]; for(int i=0;i<FG_Num;i++) allArea+=generationPool[i].useFit; for(int i=1;i<FG_Num;i++){ area[i]=(int)((float)generationPool[i].useFit/allArea*1000); area[i]+=area[i-1]; } for(int i=0;i<eliteNum;i++) newGeneration[i] = elite_Chs[i]; for(int i=eliteNum;i<FG_Num;i++){ s_ch1=-1; s_ch2=-1; while(s_ch1 == s_ch2){ s_ch1 = ch_Select(area); s_ch2 = ch_Select(area); } //System.out.println("ch1 : "+s_ch1+" ch2 : "+s_ch2); newGeneration[i] = crossover(generationPool[s_ch1],generationPool[s_ch2]); mutation(newGeneration[i]); calFit(newGeneration[i]); } return newGeneration; } //염색체를 교배하는 함수이다. 이 함수가 알고리즘의 성능을 좌우한다. private chromosome crossover(chromosome ch1, chromosome ch2) { int cutPoint = FG_Num/2; chromosome child_Ch = new chromosome(ch_len); for(int i=0; i<ch_len;i++){ if(i<cutPoint) child_Ch.order[i] = ch1.order[i]; else child_Ch.order[i] = ch2.order[i]; } for(int i=cutPoint; i<ch_len;i++){ if(child_Ch.isExist(ch2.order[i], i)){ for(int j=0; j<cutPoint;j++){ if(!child_Ch.isExist(ch2.order[j], i)){ child_Ch.order[i] = ch2.order[j]; break; } } } } return child_Ch; } //크기에 따라 확률이 다른 선택방법이다. private int ch_Select(int[] area){ int seed; seed=(int)(Math.random()*1000)+1; for(int i=1;i<FG_Num;i++){ if(area[i]>seed){ return i; } } return 0; } //돌연변이 생성 함수이다. private void mutation(chromosome ch){ int seed, changeAt, temp; for(int i=1;i<ch_len;i++){ seed = (int)(Math.random()*1000)+1; if(seed<11){ changeAt = (int)(Math.random()*ch_len-1)+1; temp = ch.order[i]; ch.order[i] = ch.order[changeAt]; ch.order[changeAt] = temp; } } } //한 세대의 염색체를 모두 출력하는 함수이다. private void G_printf(chromosome[] generationPool, chromosome[] elite_Chs){ for(int i=0;i<FG_Num;i++){ System.out.print("["); for(int j=0;j<ch_len;j++){ System.out.print(generationPool[i].order[j]+" "); } System.out.print("] : "); System.out.println(generationPool[i].useFit+" "+generationPool[i].fit); } System.out.println("========elite========"); for(int i=0;i<eliteNum;i++){ System.out.print("["); for(int j=0;j<ch_len;j++){ System.out.print(elite_Chs[i].order[j]+" "); } System.out.print("] : "); System.out.println(elite_Chs[i].useFit+" "+elite_Chs[i].fit); } System.out.println("========================="); } //염색체 클레스이다. private class chromosome implements Comparable<chromosome>{ int order[] = null; int fit=0; int useFit=0; chromosome(int ch_len){ order = new int[ch_len]; } public int compareTo(chromosome ch) { return ch.useFit-this.useFit; // 자기 자신이 기준이 되면 오름차순 } //상대가 기준이면 내림차순 feat.sort public boolean isExist(int data, int currentAt){ for(int i=0;i<ch_len;i++){ if(i!=currentAt){ if (order[i]==data) return true; } } return false; } }}| 라이브러리, JGAP, Jenetics (0) | 2019.02.11 |
|---|---|
| 머신러닝 - 자기조직화지도(Self-Organizing Map, SOM) (0) | 2019.02.11 |
| 유전 알고리즘(Genetic Algorithm)(2)-MST(java) (0) | 2019.02.10 |
| CSP vs BFS vs GA for N-Queen (0) | 2019.02.10 |
| 유전 알고리즘(Genetic Algorithm)(1)-알고리즘 설명 (0) | 2019.02.10 |
출처: https://twinw.tistory.com/2?category=543725 [흰고래의꿈]
앞에서 포스팅한 글에서 예시로 다루었듯이
모든 도시를 최단으로 방분하는 경우
즉 Minimum Spaning Tree를 유전알고리즘으로 하여 구해보도록 하겠습니다.
사용 언어는 나중에 안드로이드 개발에 사용하기 위해 자바로 하였고
오늘 포스팅은 데이터를 외부에서 가져오는 것까지하고
실질적인 유전알고리즘에 대한 코드는 다음 포스팅에서 설명해드리겠습니다.
데이터 파일은 첨부파일에 보시면 됩니다.
유전 알고리즘(JAVA).zipimport java.io.BufferedReader;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;public class MST { public static void main(String[] argv){ String fileName = "input.dat"; int[][] dataMatrix = null; int nodeNum = 0; String temp; try { FileReader Fr = new FileReader(fileName); BufferedReader Br = new BufferedReader(Fr); try { if(Br.ready()){ System.out.println("파일이 로드 되었습니다."); nodeNum = Integer.valueOf(Br.readLine()); dataMatrix = new int [nodeNum][nodeNum]; while((temp=Br.readLine())!=null){ dataMatrix[Integer.valueOf(temp.split(" ")[0])] [Integer.valueOf(temp.split(" ")[1])] = Integer.valueOf(temp.split(" ")[2]); dataMatrix[Integer.valueOf(temp.split(" ")[1])] [Integer.valueOf(temp.split(" ")[0])]= Integer.valueOf(temp.split(" ")[2]); } } } catch (IOException e) { System.err.println("파일 로드를 실패했습니다.."); } } catch (FileNotFoundException e) { System.err.println("다음 파일이 없습니다. : " + fileName); } //입력확인// for(int i=0; i<nodeNum;i++){// for(int j=0; j<nodeNum;j++){// System.out.print(dataMatrix[i][j]+" ");// }// System.out.println();// } //데이터 + 염색체 길이 + 염색체 갯수 + 목적치 + th_fit + 엘리트수 + 교배횟수 GA mGA = new GA(dataMatrix, nodeNum,10,1000,80000,2,10000); }}| 라이브러리, JGAP, Jenetics (0) | 2019.02.11 |
|---|---|
| 머신러닝 - 자기조직화지도(Self-Organizing Map, SOM) (0) | 2019.02.11 |
| 유전 알고리즘(Genetic Algorithm)(3)-MST(java) (0) | 2019.02.10 |
| CSP vs BFS vs GA for N-Queen (0) | 2019.02.10 |
| 유전 알고리즘(Genetic Algorithm)(1)-알고리즘 설명 (0) | 2019.02.10 |
출처: https://redcarrot.tistory.com/49
- Constraint Satisfaction Problem (CSP; 제약 만족 문제)
| CSP | BFS | GA |
| Systematic search | Stochastic search | Stochastic search |
| 체계적으로 Optimal를 찾을 수 있음 (단 존재한다면) | Near optimal를 쉽게 찾을 수 있음 | Near optimal를 쉽게 찾을 수 있음 결과를 못찾을 수도 있음 불필요한 시간이 소요될 수 있음 |
| Constraint에 따라 search space를 filtering 하여 문제를 해결 가능 | 어떤 Heuristic function을 사용했는지에 따라 수행속도가 다름 | Gene을 어떻게 표현하였는지와 operator의 사용에 따라 다름 |
| Constraint 자체가 heuristic | 각 state를 평가할 수 있는 heuristic function | 확률 자체가 heuristic임 병렬 탐색 가능 |
| trace 가능 | trace 가능 | trace 불가능 |
- 각 연산자가 적용되는 모습
| 라이브러리, JGAP, Jenetics (0) | 2019.02.11 |
|---|---|
| 머신러닝 - 자기조직화지도(Self-Organizing Map, SOM) (0) | 2019.02.11 |
| 유전 알고리즘(Genetic Algorithm)(3)-MST(java) (0) | 2019.02.10 |
| 유전 알고리즘(Genetic Algorithm)(2)-MST(java) (0) | 2019.02.10 |
| 유전 알고리즘(Genetic Algorithm)(1)-알고리즘 설명 (0) | 2019.02.10 |
참조 : http://twinw.tistory.com/1
1. 개요
생물의 진화를 모방하여 최적해를 구하는 알고리즘이다.
2. 용어 정의
- 염색체(Chromosome) : 유전정보를 담고 있는 생물학적인 집합을 연속된 문자열로 추상화한 것.
- 유전자(Gene) : 염색체를 구성하는 요소, 예를 들어 염색체가 ABC라면 유전자는 A 또는 B 또는 C를 뜻한다.
- 교차(Crossover) : 두 개의 유전자가 각각의 유전자를 조합하여 새로운 염색체를 생성하는 연산.
- 돌연변이(Mutation) : 교차연산 이후, 확률적으로 유전자의 정보가 바뀌는 것, 생물학적인 돌연변이와 같음.
- 자손(Offspring) : 이전 세대의 염색체로부터 교차, 돌연변이 연산을 통해 생성된 다음 세대 염색체.
3. 추상화 예시
유전 알고리즘을 이용하여 해결할 수 있는 문제 중에는 가장 대표적으로 TSP(Traveling Salesman Problem)이 있다. TSP는 각각의 도시가 있고, 도시 사이를 이동하기 위해서는 비용이 소모된다.
TSP를 해결하는 목적은 가장 비용이 적게 드는 도시 방문 순서를 구하는 것이다. 따라서 유전 알고리즘을 이용하여 TSP를 해결한다면 하나의 염색체는 도시 방문 순서를 나타내고, 하나의 염색체에 포함된 하나의 유전자는 도시를 나타낸다.
4. 알고리즘 구조
유전 알고리즘은 생물의 진화, 교배를 반복하면서 최적해를 구하는 알고리즘으로써 크게 5단계로 나누어진다.
1) 초기 세대 생성
2) 초기 세대 적합도 평가
3) 초기 세대 교배 및 돌연변이 (해당 과정으로 다음 세대가 생성된다)
4) 다음 세대 적합도 평가
5-1) 목표 적합도(TSP에서는 원하는 수준의 적은 비용)을 만족하는 염색체가 존재하면 알고리즘을 종료
5-2) 목표 적합도를 만족하는 염색체가 없다면 다음 과정으로 진행
6) 현재 세대 교배 및 돌연변이 (해당 과정으로 다음 세대가 생성된다)
유전 알고리즘을 설계할 때, 최적해의 정확한 값이나 패턴을 알지 못하기 때문에 목표 적합도를 추정해야한다.
이 과정에서 절대로 나올 수 없는 목표 적합도를 설정하게 되는 경우가 있는데, 이러한 경우에는 알고리즘이 끝나지 않는다. 그래서 매우 복잡한 문제를 풀어야 할 때는 목표 적합도뿐만 아니라, 최대 반복 횟수도 같이 설정해주는 것이 일반적이다.
5. TSP 적용
세일즈맨은 A 도시에서 출발하여 4개의 도시(B, C, D, E)를 방문해야하고, 현재 도시에서 다른 도시로 이동하는데 소모되는 비용은 아래의 표와 같다.
표에서 비용은 이동거리, 톨게이트 비용 등 도시를 이동할 때 소모되는 자원을 추상화하여 모두 더한 값이라고 정의한다.
알고리즘을 설계할 때, 가장 먼저 정해야 하는 것은 한 세대 당 개체 수(염색체의 수)와 목표 적합도 또는 최대 반복 횟수이다.
도시의 수가 적고, 예시를 보이는 문제이기 때문에 한 세대 당 개체 수는 아주 작게 5로 설정하고,
목표 적합도는 1900으로 하겠다. 또한 하나의 염색체가 갖는 유전자의 수는 5개이며, 시작 도시는 A로 고정되었기 때문에 첫번째 유전자의 값은 항상 A이다.
1) 초기 세대 생성
일반적으로 초기 세대는 유전자의 값을 임의로 할당하면서 염색체를 생성한다. 즉, 초기 세대는 일정한 규칙 없이 임의로 생성된다. 임의로 생성된 초기 세대는 아래와 같다.
2) 초기 세대 적합도 평가
유전 알고리즘의 기본 원리는 다윈의 자연선택설과 같다. 목표 적합도에 가장 근사한 적합도를 갖는 염색체가 그렇지 않은 염색체에 비해 생존과 번식이 유리하도록 알고리즘을 설계해야 한다.
여기에서 적합도 함수(Fitness function)을 정의해야 하는데, 적합도 함수는 알고리즘 설계자마다, 문제의 유형마다 정의하는 방식이 모두 다르다. 실제로 해당 분야에서는 적합도 함수와 유전 알고리즘의 성능의 관계에 대한 연구 자료와 논문도 있다. 따라서, 반드시 해당 글에서 정의한 적합도 함수와 같도록 적합도 함수를 정의할 필요는 없다.
이 예제에서는 한 염색체가 나타내는 순서대로 도시를 방문했을 경우 소모되는 비용의 합을 S라고 했을 때, 해당 염색체의 적합도는 3000 - S라고 정의한다. 이제 초기에 생성된 각각의 염색체에 대한 적합도를 계산하면 된다.
첫번째 염색체인 [A B D C E]의 적합도를 계산하면 위의 표에서 A에서 B로 이동할 때 소모되는 비용은 170이고, B에서 D로 이동할 때 소모되는 비용은 150이다. D에서 C로 이동할 때는 600, C에서 E로 이동할 때는 420이므로 [A B D C E]의 순서로 도시를 방문하는 경우에는 총 1340의 비용이 소모된다. 앞에서 정의한 적합도 함수를 통해 해당 염색체의 적합도를 계산하면 3000에서 1340을 뺀 값인 1660이 나온다. 다른 4개의 염색체에 대해서도 같은 과정으로 적합도를 계산하면 아래와 같다.
Fit([A B D C E]) = 1660
Fit([A D E C B]) = 1520
Fit([A D C E B]) = 1350
Fit([A C D E B]) = 1520
Fit([A E C B D]) = 1680
3) 초기 세대 교배 및 돌연변이
이 단계에서는 두 개의 염색체를 선택하여 교차연산을 통해 다음 세대의 유전체를 생성한다.
교차연산은 3번째와 4번째 유전자 사이에서 두 염색체의 유전자를 교차하도록 정의한다.
예를 들어, [A B D C E]와 [A E C B D]가 선택되었다면 교차연산에 의해 생성된 염색체는 [A B D E C]이다. 여기에서 첫번째 염색체의 1~3번째 유전자가 A B D이기 때문에 두번째 염색체의 4~5번째 유전자인 B D와 중복된다. 이러한 경우에는 두번째 염색체의 유전자 순서를 유지하면서 중복되지 않은 값으로 4~5번째를 채워야 하기 때문에 [A B D C E]와 [A E C B D]가 교차되어 [A B D E C]가 생성된 것이다.
다음으로 고려해야 하는 것은 유전 알고리즘에서 가장 중요한 것은 염색체의 다양성을 유지하는 것이다. 따라서 유전 알고리즘에서는 적합도가 가장 좋은 염색체를 선택해서 교배를 하는 것이 아니라,
적합도가 가장 좋은 염색체가 선택될 확률을 가장 높게 설정하고 확률적으로 염색체를 선택하는
몬테카를로 방법(Monte Carlo method)을 이용한다.
따라서 이 예제에서는 초기 세대의 적합도를 모두 더한 값이 7730이므로 첫번째 염색체([A B D C E])가 선택될 확률은 1660을 7730으로 나누고 100을 곱한 값인 21.47%가 된다.
추가적으로 유전 알고리즘의 성능을 향상시키는 방법으로 엘리트주의(elitism)이 있다.
엘리트주의는 이전 세대에서 적합도가 가장 좋은 염색체를 다음 세대에 그대로 보존하는 것으로 몇 개를 보존할지는 알고리즘의 설계에 따라 다르다. 이 예제에서는 적합도가 가장 높은 상위 2개의 염색체를 보존하도록 한다.
그러므로 초기 세대에서 적합도가 가장 높은 [A B D C E]와 [A E C B D]를 다음 세대까지 그대로 보존하도록 한다. 따라서 교배연산에서는 총 3개의 다음 세대 염색체를 생성하면 된다. 임의로 선택된 세 쌍의 염색체쌍은 아래와 같다고 가정한다.
이항연산자 ( + )를 교배연산이라 정의하고, 각각에 교배연산을 적용하여 생성한 다음 세대 염색체는 아래와 같다.
마지막으로 교배연산을 통해 생성된 염색체에서 2~5번째 유전자는 각각 5%의 확률로 돌연변이를 일으켜 알파벳 순서상 그 다음 도시로 변경된다고 알고리즘을 설계한다. 예를 들어 돌연변이가 발생하면 C는 D로, E는 B로 변경된다.
[A D C E B]의 5번째 유전자에서 돌연변이가 발생했다고 가정하면, 염색체는 [A D B E C]로 변경된다.
그러므로 초기 세대 다음인 첫 번째 세대는 아래와 같은 염색체로 구성된다.
4) 다음 세대 적합도 평가
다음으로 초기 세대로부터 생성된 첫 번째 세대의 적합도를 평가한다.
Fit([A B D C E]) = 1660
Fit([A E C B D]) = 1680
Fit([A B D C E]) = 1660
Fit([A E C D B]) = 1430
Fit([A D B E C]) = 1800
5) 목표 적합도 검사
현재 세대의 염색체 중에서 가장 높은 적합도는 1800이므로 목표 적합도인 1900 이상의 적합도를
갖는 염색체가 존재하지 않는다. 그러므로 알고리즘을 계속 진행한다.
6) 교배 및 돌연변이
현재 세대의 염색체를 이용하여 교배 및 돌연변이를 수행한다. 이 과정에서 수행하는 교배 및 돌연변이 연산은 과정 3의 연산과 같다. 새롭게 생성된 염색체들을 유지하면서 과정 4로 이동한다.
출처: https://redcarrot.tistory.com/47
| 라이브러리, JGAP, Jenetics (0) | 2019.02.11 |
|---|---|
| 머신러닝 - 자기조직화지도(Self-Organizing Map, SOM) (0) | 2019.02.11 |
| 유전 알고리즘(Genetic Algorithm)(3)-MST(java) (0) | 2019.02.10 |
| 유전 알고리즘(Genetic Algorithm)(2)-MST(java) (0) | 2019.02.10 |
| CSP vs BFS vs GA for N-Queen (0) | 2019.02.10 |
