반응형
배낭문제는 한정된 배낭속에 최대한 값어치 나가게 물건을 담는 경우를 찾아내는 문제이다.
여기서 기술할 문제는 총 무게가 한정되어있을때 얼마나 비싼 값어치를 담아낼수 있느냐의 문제를 해결한다.
사용할 알고리즘은 유전자 알고리즘으로, 교차와 돌연변이를 이용하였다.
배낭문제에 대한 자세한 설명은 위키백과 참조...
아래는 참고용 베타 소스코드.
Mac 10.8.5에서 Xcode Version 5.0.1로 작성한 소스이다.
윈도우에서도 실행은 안해봤지만 기본적으로 C언어를 이용하였으니 크게 문제가 없을듯...
적당히 프로그래밍 한거라서, 여기저기 오류가 있을수도 있고 수정이 필요할듯 하지만 값은 확인가능 함.
최대허용중량이 1000 일때의 계산결과는 아래와 같더라.
Weight 960 Best fitness[1]:8300
최대로 담을수 있는 값은 무게가 960일때 8300이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 | // // main.c // kanpsack problem // // Created by 초인로크 on 2013/11/25. // Copyright (c) 2013年 Rocke. All rights reserved. // #include <stdio.h> #include <stdlib.h> #include <time.h> #define POPULATION 10 //개체수 #define LENGTH 10 //유전자 개체의 길이 #define MAX_WEIGHT 1000 //배낭에 담아낼수 있는 최대무게 #define CROSSOVER 0.7 //교차 확률 #define MUTATION 0.5 //돌연변이 확률 #define PENALTY 15 //값을 구하기위한 페널티 #define GENERATION_NUMBER 10000 //세대수 (계산반복횟수) int object_value[LENGTH]={1000,500,3000,2500,300,1400,100,800,1200,1900}, //각 물건의 값 object_weight[LENGTH]={200,130,300,500,450,100,200,50,210,300}, //각 물건의 무게 object[POPULATION][LENGTH],fitness_save[POPULATION],best_fit=0,worst_fit=0; double rnd(){ return (double)((rand()%RAND_MAX)/(double)RAND_MAX); //0~1까지의 난수생성 } //최대적응도 구하기 int best_fitness(){ int i,j=0; for(i=0;i<LENGTH;i++) if(fitness_save[i]>fitness_save[j]) j=i; return j; } //최소적응도 구하기 int worst_fitness(){ int i,j=0; for(i=0;i<LENGTH;i++) if(fitness_save[i]<fitness_save[j]) j=i; return j; } //적응도 구하기 void fitness(int i){ int j,value=0,weight=0; for(j=0;j<LENGTH;j++){ value+=object[i][j]*object_value[j]; weight+=object[i][j]*object_weight[j]; } if(weight>MAX_WEIGHT){ fitness_save[i]=value+PENALTY*(MAX_WEIGHT-weight); //담아낼수 있는 한계치를 넘은경우 패널티를 부여하여 선택이 되지 않도록 한다. }else{ fitness_save[i]=value; } best_fit = best_fitness(); worst_fit = worst_fitness(); printf(" fitness[%d]:%d Best fitness[%d]:%d\n",i,fitness_save[i],best_fit,fitness_save[best_fit]); } //유전자의 교차 void crossover_func(int i){ int j=0; int rrnd1,rrnd2; rrnd1=(int)rand()%10; rrnd2=(int)rand()%10; for(j=0;j<LENGTH;j++) if(rnd()<=0.5) object[i][j]=object[rrnd1][j]; else object[i][j]=object[rrnd2][j]; fitness(i); } //유전자의 돌연변이 void mutation_func(int i){ int j=0; for(j=0;j<LENGTH;j++) if(rnd()<=0.5) object[i][j]=1; else object[i][j]=0; fitness(i); } //유전자 알고리즘 본체 void ga_main(){ int i,j,wei=0; //랜덤하게 교차와 돌연변이를 계산해줌 for(i=0;i<GENERATION_NUMBER;i++){ if(rnd()>MUTATION) mutation_func(worst_fit); else if(rnd()>CROSSOVER) crossover_func(worst_fit); } best_fit = best_fitness(); for(j=0;j<LENGTH;j++){ wei+=object[best_fit][j]*object_weight[j]; //최적값일때의 총 무게의 계산 } printf(" Weight %d Best fitness[%d]:%d\n",wei,best_fit,fitness_save[best_fit]); } //유전자 표현형의 초기화, 여기서는 0과1을 이용하여서 유전자를 표현하였다. 개체수는 10, 유전자의 길이도 10으로 설정했다. void initialization(){ int i,j; for(i=0;i<POPULATION;i++){ for(j=0;j<LENGTH;j++){ if(rnd()>=0.5) object[i][j]=1; else object[i][j]=0; printf("%d",object[i][j]); } fitness(i); //초기 적응도의 계산 printf("\n"); } } int main(int argc, const char * argv[]) { srand((unsigned int)time(NULL)); //컴퓨터의 난수표가 시간기준으로 변하게 initialization(); //유전자의 초기화 ga_main(); //유전자알고리즘 실행 return 0; } |
반응형