* 공부용의 자유로운 글씨 - 오늘은 없음!😀
『가장 쉬운 독학 알고리즘 첫걸음 - C&자바편』 공부용이다.
11장은 복습의 챕터이므로!
드디어 10장이 마지막이다!
유전 알고리즘 (생물의 유전 현상을 시뮬레이션하여 최적화 문제를 푸는 알고리즘) 으로 배낭 문제를 풀어 보는 것이라고 한다!
진화를 통해서... 여러 세대가 경과한 뒤 적응도가 가장 높은 개체를 정답으로 삼는 구조이다!
유전자가 환경 적응도에 따라 진화하는 모습을 컴퓨터로 시뮬레이션 해 정답을 찾는 것이다.
유전자 개체를 선택하는 패턴/ 선택하지 않는 패턴으로 비유해서 사용하면 된다고 한다...
(일단 책 읽어봄)
(20%정도 이해가 가서 집단지성을 찾아봄)
https://namu.wiki/w/%EC%9C%A0%EC%A0%84%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
: 아! 제일 큰 수 / 제일 작은 수 / 찾을라는 수 / 쓸 때 쓰는 거군요!
적응도!
의사 코드를 보면...
○ main
．키보드로 최대의 세대를 입력한다
．무작위로 1세대 개체를 8개 생성한다
．적응도를 계산한다
．적응도가 큰 순서로 정렬한다
．개체의 내용을 표시한다
．다음 세대로 진행한다
■최대의 세대 이하면 반복한다
│．적응도가 큰 순서로 정렬한다
│．상위 50%의 개체를 하위 50%로 복사한 후 하위 50%를 도태시킨다
│．하위 50%에 복사한 개체를 대상으로 교차시킨다
│．하위 50%에 복사한 개체를 대상으로 돌연변이시킨다
│．적응도를 계산한다
│．적응도가 큰 순서로 정렬한다
│．개체의 내용을 표시한다
■다음 세대로 진행한다
．가장 적응도가 높은 개체를 배낭 문제의 정답으로 표시한다
돌연변이 : 적응도가 높은 유전자 패턴 일부를 임의로 변화시킴
도태 : 적응도가 낮은 유전자 제거
교차 : 적응도가 높은 두 유전자 패턴(배열 요소값)을 부분적으로 교환
ㅇㅋ...
이...이것은 한 라인씩 공부를 해 보았다.
import java.util.Scanner;
public class 공부용_배낭 {
public static final int KNAP_MAX = 6; // 배낭의 최대 무게
public static final int ITEM_NUM = 5; // 물건의 종류
public static final int IND_NUM = 8; // 개체 수
public static final double MUTATE_RATE = 0.1; // 돌연변이 확률(10%) ... <- (-.-)
public static char[] itemName = { 'A', 'B', 'C', 'D', 'E' }; // 물건의 이름
public static int[] itemWeight = { 1, 2, 3, 4, 5 }; // 물건의 무게
public static int[] itemValue = { 100, 300, 350, 500, 650 }; // 물건의 가치
public static int indGeneration; // 개체의 세대
public static int[][] indGene = new int[IND_NUM][ITEM_NUM]; // 개체의 유전자
public static int[] indWeight = new int[IND_NUM]; // 개체의 무게
public static int[] indValue = new int[IND_NUM]; // 개체의 가치
public static int[] indFitness = new int[IND_NUM]; // 개체의 적응도
// 개체를 무작위로 생성하는 메서드
public static void createIndividual() {
//임의로 개체 8개를 무작위로 만들어서 indGene에다가 저장하게 함.
//만약에 반환값이 0.5보다 크면 0이고 아니면 1임 (랜덤!)
int ind, item; // 루프 카운터
// 0 또는 1을 무작위로 저장
for (ind = 0; ind < IND_NUM; ind++) {
for (item = 0; item < ITEM_NUM; item++) {
indGene[ind][item] = Math.random() > 0.5 ? 0 : 1;
}
}
}
// 개체의 무게, 가치, 적응도를 계산하는 메서드
public static void calcIndividual() {
//KNAP_MAX : 6
int ind, item; // 루프 카운터
for (ind = 0; ind < IND_NUM; ind++) {
// 무게와 가치를 계산
indWeight[ind] = 0;
indValue[ind] = 0;
for (item = 0; item < ITEM_NUM; item++) {
if (indGene[ind][item] == 1) {
indWeight[ind] += itemWeight[item];
indValue[ind] += itemValue[item];
}
}
// 적응도를 계산
if (indWeight[ind] <= KNAP_MAX) {
// 최대 무게 이하면 가치를 그대로 적응도로 삼음
indFitness[ind] = indValue[ind];
}
else {
// 최대 무게를 초과하면 적응도를 0으로 함
indFitness[ind] = 0;
}
}
}
// 개체의 정보를 표시하는 메서드
public static void showIndividual() {
int ind, item; // 루프 카운터
// 세대를 표시
System.out.printf("\n<%d세대>\n", indGeneration);
// 유전자, 무게, 가치, 적응도를 표시
System.out.printf("유전자\t\t무게\t가치\t적응도\n");
for (ind = 0; ind < IND_NUM; ind++) {
for (item = 0; item < ITEM_NUM; item++) {
System.out.printf("[%d]", indGene[ind][item]);
}
System.out.printf("\t%2dkg\t%4d원\t%4d\n", indWeight[ind], indValue[ind], indFitness[ind]);
}
System.out.printf("\n");
}
// 적응도가 큰 순서대로 개체를 정렬하는 메서드
public static void sortIndividual() {
int pos; // 삽입할 요소
int ins; // 삽입할 위치
int item; // 루프 카운터
int tmp; // 임시 변수
//삼중 반복문을 써버림 (코딩테스트 판단 알고리즘 : 끔찍!)
// 삽입 정렬로 정렬
for (pos = 1; pos < IND_NUM; pos++) {
ins = pos;
while (ins >= 1 && indFitness[ins - 1] < indFitness[ins]) {
for (item = 0; item < ITEM_NUM; item++) {
tmp = indGene[ins - 1][item];
indGene[ins - 1][item] = indGene[ins][item];
indGene[ins][item] = tmp;
}
tmp = indWeight[ins - 1];
indWeight[ins - 1] = indWeight[ins];
indWeight[ins] = tmp;
tmp = indValue[ins - 1];
indValue[ins - 1] = indValue[ins];
indValue[ins] = tmp;
tmp = indFitness[ins - 1];
indFitness[ins - 1] = indFitness[ins];
indFitness[ins] = tmp;
ins--;
}
}
}
// 도태를 수행하는 메서드
public static void selectIndividual() {
int ind, item; // 루트 카운터
// 적응도 상위 50%를 하위 50%로 복사(하위 50%를 도태시킴)
for (ind = 0; ind < IND_NUM / 2; ind++) {
for (item = 0; item < ITEM_NUM; item++) {
indGene[ind + IND_NUM / 2][item] = indGene[ind][item];
}
}
//대단하다...
System.out.printf("하위 50％를 도태시켰습니다.\n");
}
// 교차를 수행하는 메서드
public static void crossoverIndividual() {
int ind, item; // 루프 카운터
int crossoverPoint; // 교차 수행 위치
int tmp; // 임시 변수
// 하위 50%를 복사한 개체를 대상으로 함
for (ind = IND_NUM / 2; ind < (IND_NUM - 1); ind += 2) {
// 교차할 위치를 임의로 결정
//임의 위치도 랜덤 써버림
crossoverPoint = (int)(Math.random() * 10000) % (ITEM_NUM - 1) + 1;
for (item = crossoverPoint; item < ITEM_NUM; item++) {
// 이웃 개체와 교차 수행
tmp = indGene[ind][item];
indGene[ind][item] = indGene[ind + 1][item];
indGene[ind + 1][item] = tmp;
}
System.out.printf("개체 %d와 %d를 %d의 위치에서 교차했습니다.\n", ind, ind + 1, crossoverPoint);
}
}
// 돌연변이를 만드는 메서드
public static void mutateIndividual() {
int ind, item; // 루프 카운터
//뮤턴트를 만들 확률도 미리 정해져 있음...
//무서운 알고리즘!
// 하위 50%를 복사한 개체를 대상으로 함
for (ind = IND_NUM / 2; ind < IND_NUM; ind++) {
for (item = 0; item < ITEM_NUM; item++) {
// 미리 정해진 확률로 돌연변이 만들기
if (Math.random() <= MUTATE_RATE) {
// 유전자 패턴을 반전함
indGene[ind][item] ^= 1;
System.out.printf("개체 %d의 %d 위치에서 돌연변이를 만들었습니다.\n", ind, item);
}
}
}
}
// 프로그램의 실행의 시작점인 main 메서드
public static void main(String[] args) {
int genMax; // 최대 세대
int item; // 루프 카운터
// 키보드로 최대 세대를 입력
Scanner scn = new Scanner(System.in);
System.out.printf("최대의 세대 = ");
genMax = scn.nextInt();
scn.close();
// 1세대 개체를 생성
indGeneration = 1;
createIndividual();
// 적응도를 계산
calcIndividual();
// 적응도가 큰 순서로 개체를 정렬
sortIndividual();
// 개체를 표시
showIndividual();
// 1세대씩 진화시키기
indGeneration++;
while (indGeneration <= genMax) {
// 적응도가 큰 순서로 개체를 정렬
sortIndividual();
// 도태시킴
selectIndividual();
// 교차시킴
crossoverIndividual();
// 돌연변이시킴
mutateIndividual();
// 적응도를 계산
calcIndividual();
// 적응도가 큰 순서로 개체를 정렬
sortIndividual();
// 개체를 표시
showIndividual();
// 다음 세대로 나아감
indGeneration++;
}
// 적응도가 가장 높은 개체를 정답으로 표시
System.out.printf("<배낭에 들어 있는 물건을 표시합니다.>\n");
for (item = 0; item < ITEM_NUM; item++) {
if (indGene[0][item] == 1) {
System.out.printf("%c, %dkg, %d원\n", itemName[item], itemWeight[item], itemValue[item]);
}
}
System.out.printf("\n<정답을 표시>\n");
System.out.printf("무게의 합계 = %dkg\n", indWeight[0]);
System.out.printf("가치의 최댓값 = %d원\n", indValue[0]);
}
}
최대의 세대 = 3
<1세대>
유전자 무게 가치 적응도
[0][0][0][0][1] 5kg 650원 650
[1][0][0][1][0] 5kg 600원 600
[0][0][0][1][0] 4kg 500원 500
[0][1][0][0][0] 2kg 300원 300
[0][0][0][1][1] 9kg 1150원 0
[0][0][0][0][0] 0kg 0원 0
[0][1][0][0][1] 7kg 950원 0
[1][0][1][1][0] 8kg 950원 0
하위 50％를 도태시켰습니다.
개체 4와 5를 1의 위치에서 교차했습니다.
개체 6와 7를 4의 위치에서 교차했습니다.
개체 4의 3 위치에서 돌연변이를 만들었습니다.
개체 5의 2 위치에서 돌연변이를 만들었습니다.
개체 5의 4 위치에서 돌연변이를 만들었습니다.
개체 7의 0 위치에서 돌연변이를 만들었습니다.
<2세대>
유전자 무게 가치 적응도
[0][0][0][0][1] 5kg 650원 650
[1][0][0][1][0] 5kg 600원 600
[0][0][0][1][0] 4kg 500원 500
[0][0][0][1][0] 4kg 500원 500
[1][0][1][0][0] 4kg 450원 450
[1][1][0][0][0] 3kg 400원 400
[0][1][0][0][0] 2kg 300원 300
[0][0][0][0][0] 0kg 0원 0
하위 50％를 도태시켰습니다.
개체 4와 5를 3의 위치에서 교차했습니다.
개체 6와 7를 1의 위치에서 교차했습니다.
개체 4의 3 위치에서 돌연변이를 만들었습니다.
개체 4의 4 위치에서 돌연변이를 만들었습니다.
개체 7의 4 위치에서 돌연변이를 만들었습니다.
<3세대>
유전자 무게 가치 적응도
[1][0][0][0][1] 6kg 750원 750
[0][0][0][0][1] 5kg 650원 650
[0][0][0][0][1] 5kg 650원 650
[1][0][0][1][0] 5kg 600원 600
[0][0][0][1][0] 4kg 500원 500
[0][0][0][1][0] 4kg 500원 500
[0][0][0][1][0] 4kg 500원 500
[0][0][0][1][1] 9kg 1150원 0
<배낭에 들어 있는 물건을 표시합니다.>
A, 1kg, 100원
E, 5kg, 650원
<정답을 표시>
무게의 합계 = 6kg
가치의 최댓값 = 750원
끔찍한 혼종을 만들어서 최대값을 가지는 혼종을 생성했다!
교재에서 추천하는 코딩 테스트 업체는
1. 정보 올림피아드
2. 백준
3. LeetCode 이다!
나는 programmers랑 codility로 할거지만...★
어쨌든 1장부터 10장까지 풀어보면서 리마인드도 되고, 공부도 많이 되었다
11장은 알고리즘 문제 해결로 실력 확인하기인데,
2문제를 1시간 안에 푸는 것이다!
오늘 해보자!
-> 코드 짜는 것이 목표가 아니라 의사 코드에 대한 답을 맞추는 것이 목표인 듯... (이해도)
* 다음 교재는 Spring Boot 리마인드용으로 초기 설정 포함된 교재로 해보려 한다!
댓글
댓글 쓰기