1 //
2 // gasearch_knapsack_example.c
3 //
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <math.h>
8 #include <getopt.h>
9
10 #include "liquid.h"
11
12 #define OUTPUT_FILENAME "gasearch_knapsack_example.m"
13
14 // print usage/help message
usage()15 void usage()
16 {
17 printf("Usage: gasearch_knapsack_example [options]\n");
18 printf(" u/h : print usage\n");
19 printf(" n : number of items available, default: 1000\n");
20 printf(" i : number of iterations (generations) to run, default: 2000\n");
21 printf(" c : knapsack capacity (maximum weight), default: 20\n");
22 printf(" p : ga population size, default: 100\n");
23 printf(" m : ga mutation rate, default: 0.4\n");
24 }
25
26 // knapsack object structure definition
27 struct knapsack_s {
28 unsigned int num_items; // total number of items available
29 float * weight; // weight of each item
30 float * value; // value of each item
31 float capacity; // maximum weight allowable
32 };
33
34 // print knapsack object
35 // _bag : knapsack object pointer
36 // _c : test chromosome
37 void knapsack_print(struct knapsack_s * _bag,
38 chromosome _c);
39
40 // utility callback function
41 // _userdata : knapsack object pointer
42 // _c : test chromosome
43 float knapsack_utility(void * _userdata,
44 chromosome _c);
45
main(int argc,char * argv[])46 int main(int argc, char*argv[])
47 {
48 unsigned int num_items = 1000; // number of items available
49 unsigned int num_iterations = 2000; // number of iterations to run
50 float capacity = 20.0f; // total capacity of the knapsack
51 unsigned int population_size = 100; // number of chromosomes in the population
52 float mutation_rate = 0.40f; // mutation rate of the GA
53
54 int dopt;
55 while((dopt = getopt(argc,argv,"uhn:i:c:p:m:")) != EOF){
56 switch (dopt) {
57 case 'h':
58 case 'u': usage(); return 0;
59 case 'n': num_items = atoi(optarg); break;
60 case 'i': num_iterations = atoi(optarg); break;
61 case 'c': capacity = atof(optarg); break;
62 case 'p': population_size = atoi(optarg); break;
63 case 'm': mutation_rate = atof(optarg); break;
64 default:
65 exit(1);
66 }
67 }
68
69 // validate input
70 if (num_items == 0) {
71 fprintf(stderr,"error: %s, knapsack must have at least 1 item\n", argv[0]);
72 exit(1);
73 } else if (capacity <= 0.0f) {
74 fprintf(stderr,"error: %s, knapsack capacity must be greater than zero\n", argv[0]);
75 exit(1);
76 } else if (population_size <= 0) {
77 fprintf(stderr,"error: %s, ga population size must be greater than zero\n", argv[0]);
78 exit(1);
79 } else if (mutation_rate < 0.0f || mutation_rate > 1.0f) {
80 fprintf(stderr,"error: %s, ga mutation rate must be in [0,1]\n", argv[0]);
81 exit(1);
82 }
83
84 unsigned int i;
85
86 // create knapsack/items (random weight, value)
87 struct knapsack_s bag;
88 bag.num_items = num_items;
89 bag.capacity = capacity;
90 bag.weight = (float*) malloc( bag.num_items*sizeof(float) );
91 bag.value = (float*) malloc( bag.num_items*sizeof(float) );
92 for (i=0; i<num_items; i++) {
93 bag.weight[i] = randf(); // random number in [0,1]
94 bag.value[i] = randf(); // random number in [0,1]
95 }
96
97 // create prototype chromosome (1 bit/item)
98 chromosome prototype = chromosome_create_basic(num_items, 1);
99 //chromosome_init_random(prototype); // initialize to random
100 chromosome_print(prototype);
101
102 // print knapsack
103 knapsack_print(&bag, prototype);
104
105 float optimum_utility;
106
107 // open output file
108 FILE*fid = fopen(OUTPUT_FILENAME,"w");
109 fprintf(fid,"%% %s : auto-generated file\n", OUTPUT_FILENAME);
110 fprintf(fid,"clear all;\n");
111 fprintf(fid,"close all;\n");
112
113 // create gasearch object
114 gasearch ga = gasearch_create_advanced(&knapsack_utility,
115 (void*)&bag,
116 prototype,
117 LIQUID_OPTIM_MAXIMIZE,
118 population_size,
119 mutation_rate);
120
121 // execute search one iteration at a time
122 fprintf(fid,"u = zeros(1,%u);\n", num_iterations);
123 for (i=0; i<num_iterations; i++) {
124 gasearch_evolve(ga);
125
126 gasearch_getopt(ga, prototype, &optimum_utility);
127 if (((i+1)%100)==0)
128 printf(" %4u : %12.8f;\n", i+1, optimum_utility);
129
130 fprintf(fid,"u(%3u) = %12.4e;\n", i+1, optimum_utility);
131 }
132
133 // print results
134 gasearch_getopt(ga, prototype, &optimum_utility);
135 knapsack_print(&bag, prototype);
136
137 fprintf(fid,"figure;\n");
138 //fprintf(fid,"semilogy(u);\n");
139 fprintf(fid,"plot(u);\n");
140 fprintf(fid,"xlabel('iteration');\n");
141 fprintf(fid,"ylabel('utility');\n");
142 fprintf(fid,"title('GA search results');\n");
143 fprintf(fid,"grid on;\n");
144 fclose(fid);
145 printf("results written to %s.\n", OUTPUT_FILENAME);
146
147 // free allocated objects and memory
148 chromosome_destroy(prototype);
149 gasearch_destroy(ga);
150 free(bag.value);
151 free(bag.weight);
152
153 return 0;
154 }
155
156
157 //
158 // knapsack methods
159 //
160
161 // print knapsack object
162 // _bag : knapsack object pointer
163 // _c : test chromosome
knapsack_print(struct knapsack_s * _bag,chromosome _s)164 void knapsack_print(struct knapsack_s * _bag,
165 chromosome _s)
166 {
167 unsigned int i;
168 printf("knapsack: %u items, capacity : %12.8f\n", _bag->num_items, _bag->capacity);
169 for (i=0; i<_bag->num_items; i++) {
170 printf(" %3u : %6.4f @ $%6.4f", i, _bag->weight[i], _bag->value[i]);
171 unsigned int n = chromosome_value(_s, i);
172 if (n != 0) printf(" *\n");
173 else printf("\n");
174 }
175 }
176
177 // utility callback function
178 // _userdata : knapsack object pointer
179 // _c : test chromosome
knapsack_utility(void * _userdata,chromosome _c)180 float knapsack_utility(void * _userdata, chromosome _c)
181 {
182 struct knapsack_s * _bag = (struct knapsack_s *) _userdata;
183
184 // chromosome represents number of each item in knapsack
185 float total_value = 0;
186 float total_weight = 0;
187 unsigned int i;
188 for (i=0; i<_bag->num_items; i++) {
189 if ( chromosome_value(_c,i) == 1 ) {
190 // include this item into knapsack
191 total_value += _bag->value[i];
192 total_weight += _bag->weight[i];
193 }
194 }
195
196 // check for invalid solution, returning distance metric
197 if (total_weight > _bag->capacity)
198 return _bag->capacity - total_weight;
199
200 // return total value of knapsack
201 return total_value;
202 }
203
204