Next: Module: Backpropagation
Up: Source Code
Previous: Module: Standard Network
Contents
Subsections
1
2 /* Declarations of general genetic algorithms */
3
4 #ifndef GEN_H
5 #define GEN_H 1
6
7 #include "defs.h"
8
9 char *GenOptStr();
10 char *GenUsage();
11 char GenParamStr[256];
12
13 /* CONSTANTS */
14
15 int Pcopy; /* % of indiv. to copy per gen. */
16 int Pmutate; /* % of indiv. to mutate per gen.*/
17 int Pcrossover; /* % of indiv. to crossover per gen. */
18
19 int Ncopy; /* no. of indiv. to copy per gen. */
20 int Nmutate; /* no. of indiv. to mutate per gen.*/
21 int Ncrossover; /* no. of indiv. to crossover per gen. */
22
23 int Decimation; /* initial decimation factor */
24 float DecErrMin;
25 float DecErrAvg;
26
27 int HashLen; /* lenth of hashkey 9n bits */
28 int HashSize; /* size of hashtable */
29
30 /* Variables set by calcerr */
31
32 int Nunique; /* no. of different indiv. */
33 int Nredundant; /* no. of redundant indiv. */
34 int Nmismatch; /* no. of mismatches */
35
36 float ErrMin;
37 float ErrAvg;
38 int TopInd;
39
40 /* Arrays */
41
42 ind *Pop; /* Poulation */
43 errtyp *Err; /* errorlist of Populaton */
44
45 /* Procedures */
46
47 int handleGenOpt(char opt,char* arg);
48 int initGen(int popsize,int popmem);
49 void randomPop(int popsize);
50
51 int hashfct(ind x);
52 void clearerrtab();
53
54 errtyp geterr(int n);
55 void mutate(ind x0,ind x1);
56 void crossover(ind x0,ind y0,ind x1,ind y1);
57 void copy(ind x0,ind x1);
58 void calcerrors(int popsize);
59 void selection(int popsize);
60
61 #endif
1
2 /* Implementation of general genetic algorithms */
3
4 #include "defs.h"
5 #include "gen.h"
6 #include "ind.h"
7
8 /* Parameter Handling */
9
10 #define DEFMUTATE 60
11 #define DEFNMUTATE AUTO
12 #define DEFCOPY 0
13 #define DEFDECIMATION 0
14 #define DEFHASH AUTO
15
16 char *GenOptStr() {return "m:n:c:u:d:h:\0";}
17
18 char *GenUsage() {return
19 "Genetic Parameters:\n"
20 "-m <percentage of mutations>: 60\n"
21 "-n <n for 1..n point mutations>: auto\n"
22 "-c <percentage of copies>: 0\n"
23 "-u <perc. of uniform selections>: 0\n"
24 "-d <initial decimation factor>: 0\n"
25 "-h <size of hashtable (0=off)>: auto\n\0";}
26
27 /* set default values */
28
29 int Pcopy =DEFCOPY; /* % of indiv. to copy per gen. */
30 int Pmutate =DEFMUTATE; /* % of indiv. to mutate per gen.*/
31 int Puniform =0; /* % of indiv. for uniform selection */
32 int Nmutate =DEFNMUTATE; /* 1..Nmutate point mutations */
33 int Decimation =DEFDECIMATION; /* initial decimation factor */
34 int HashLen =DEFHASH; /* lenth of hashkey 9n bits */
35 int HashSize =0; /* size of hashtable */
36 int Nunique =UNDEF; /* no. of different indiv. */
37 int Nredundant =UNDEF; /* no. of redundant indiv. */
38 int Nmismatch =UNDEF; /* no. of mismatches */
39
40 ind *OldPop; /* old population */
41 int HashMask; /* HashSize-1 */
42 int *HashTab;
43 int Nuniform;
44
45 int handleGenOpt(char opt,char* arg)
46 {
47 switch(opt)
48 {
49 case 'm': return (Pmutate =getint(arg,0,100))<0;
50 case 'n': return (Nmutate =getint(arg,1,1000))<0;
51 case 'c': return (Pcopy =getint(arg,0,100))<0;
52 case 'u': return (Puniform =getint(arg,0,100))<0;
53 case 'd': return (Decimation=getint(arg,0,100))<0;
54 case 'h': return (HashLen =getint(arg,0,16))<0;
55 default: return 1;
56 };
57 }
58
59 int initGen(int popsize,int popmem)
60 {
61 int i,j,k,n,h,t;
62 word *p;
63 ind* pop;
64 char s[128];
65 errtyp e,m;
66
67 GenCalcs=0;
68 Pcrossover=100-Pmutate-Pcopy;
69 if(Pcrossover<0) return 1;
70 Nuniform=Puniform*(MAXRANDOM/100);
71
72 if(HashLen==AUTO) HashLen=Pmutate>50 ? 0 : duallog(popsize)+1;
73 if(HashLen)
74 {
75 if(popsize>(1<<HashLen)) return 1;
76 HashSize=1 << HashLen;
77 HashMask=HashSize-1;
78 HashTab=(int*)malloc(HashSize*WORDLEN);
79 };
80 if(!(Pop=(ind*)malloc(popmem*INDLEN))) return 1;
81 if(!(p=(word*)malloc(popmem*CrWords*WORDLEN))) return 1;
82 for(i=0;i<popmem;i++) Pop[i]=p+i*CrWords;
83 if(!(OldPop=(ind*)malloc(popmem*INDLEN))) return 1;
84 if(!(p=(word*)malloc(popmem*CrWords*WORDLEN))) return 1;
85 for(i=0;i<popmem;i++) OldPop[i]=p+i*CrWords;
86 if(!(Err=(errtyp*)malloc(popmem*ERRLEN))) return 1;
87 if(Decimation<=1) Decimation=0;
88 if(Decimation)
89 {
90 h=HashLen; HashLen=0;
91 DecErrAvg=0; DecErrMin=MAXERROR;
92 k=(popsize-1)/Decimation+1; n=0;
93 while(n<popsize)
94 {
95 randomPop(popsize);
96 calcerrors(popsize);
97 if(DecErrMin>ErrMin) DecErrMin=ErrMin;
98 DecErrAvg+=ErrAvg;
99 for(i=0;i<k && n<popsize;i++)
100 {
101 t=0;
102 for(j=1;j<popsize;j++)
103 if(Err[j]<Err[t]) t=j;
104 copy(Pop[t],OldPop[n++]);
105 Err[t]=MAXERROR;
106 };
107 };
108 pop=Pop; Pop=OldPop; OldPop=pop;
109 DecErrAvg/=Decimation;
110 HashLen=h;
111 } else {
112 randomPop(popsize);
113 };
114 if(Nmutate==AUTO) Nmutate=CrBits/50+1;
115
116 s[0]=0;
117 if(HashLen) sprintf(s,", HashSize = %d",HashSize);
118 sprintf(GenParamStr,
119 "Genetic: Pcopy = %d %%, Pmutate(1..%d pt.) = %d %%, "
120 "Pcrossover = %d %%%s\n"
121 " Selection %d %% linear, %d %% uniform\n",
122 Pcopy,Nmutate,Pmutate,Pcrossover,s,100-Puniform,Puniform);
123 if(Decimation)
124 {
125 sprintf(s,"Decimation: Factor = %d, PopSize = %d, "
126 "MinErr=%6.2f, AvgErr=%6.2f\n",
127 Decimation,popmem*Decimation,DecErrMin,DecErrAvg);
128 strcat(GenParamStr,s);
129 };
130 return 0;
131 }
132
133 void randomPop(int popsize)
134 {
135 int i,j;
136 word m;
137 byte *p;
138
139 p=(byte*)Pop[0];
140 for(i=0;i<popsize*CrWords*WORDLEN;i++) p[i]=getrand() & 0xff;
141 j=CrBits % (8*WORDLEN);
142 if(CrBits%(WORDLEN*8))
143 {
144 m=(1<<j)-1;
145 for(i=0;i<popsize;i++)
146 Pop[i][CrWords-1] &= m;
147 };
148 }
149
150 void clearerrtab()
151 {
152 int i;
153
154 for(i=0;i<HashSize;i++) HashTab[i]=NOENTRY;
155 Nunique=Nredundant=Nmismatch=0;
156 }
157
158 int hashfct(ind x)
159 {
160 int i;
161 word w=0;
162
163 for(i=0;i<CrWords;i++) w+=x[i];
164 w+=w>>HashLen;
165 w+=w>>HashLen;
166 w+=w>>HashLen;
167 return (int)(w & HashMask);
168 }
169
170 errtyp geterr(int n)
171 {
172 int i,j,h,k;
173 word w;
174 errtyp e;
175
176 h=hashfct(Pop[n]);
177 mismatch:
178 k=HashTab[h];
179 if(k==NOENTRY)
180 {
181 e=Err[n]=calcerr(Pop[n]);
182 HashTab[h]=n;
183 Nunique++;
184 return e;
185 } else {
186 for(i=0;i<CrWords;i++)
187 if(Pop[n][i]!=Pop[k][i])
188 {
189 h=(h+1)&HashMask;
190 Nmismatch++;
191 goto mismatch;
192 };
193 e=Err[n]=Err[k];
194 Nredundant++;
195 return e;
196 };
197 }
198
199 void mutate(ind x0,ind x1)
200 {
201 int i,k,m;
202 for(i=0;i<CrWords;i++) x1[i]=x0[i];
203 m=getrand()%Nmutate;
204 for(i=0;i<=m;i++)
205 {
206 k=getrand()%CrBits;
207 x1[wordoffs(k)]^=1<<bitoffs(k);
208 };
209 }
210
211 void crossover(ind x0,ind y0,ind x1,ind y1)
212 {
213 int n,i,k;
214 word w,m,xx0,xx1,yy0,yy1;
215
216 n=getrand()%CrBits; n=67;
217 k=wordoffs(n);
218 for(i=0;i<k;i++)
219 {
220 x1[i]=y0[i]; y1[i]=x0[i];
221 };
222 m=(1<<bitoffs(n))-1;
223
224 xx0=m & (x0[k]); xx1=(~m) & (x0[k]);
225 yy0=m & (y0[k]); yy1=(~m) & (y0[k]);
226
227 x1[k]=yy0|xx1;
228 y1[k]=xx0|yy1;
229
230 for(i=k+1;i<CrWords;i++)
231 {
232 x1[i]=x0[i]; y1[i]=y0[i];
233 };
234
235 }
236
237 void copy(ind x0,ind x1)
238 {
239 int i;
240
241 for(i=0;i<CrWords;i++) x1[i]=x0[i];
242 }
243
244 void calcerrors(int popsize)
245 {
246 int i;
247 errtyp e,sum,min;
248
249 sum=0; min=MAXERROR;
250 if(HashLen)
251 {
252 clearerrtab();
253 for(i=0;i<popsize;i++)
254 {
255 e=geterr(i);
256 sum+=e;
257 if(e<min) { min=e; TopInd=i; };
258 };
259 } else {
260 for(i=0;i<popsize;i++)
261 {
262 e=Err[i]=calcerr(Pop[i]);
263 sum+=e;
264 if(e<min) { min=e; TopInd=i; };
265 };
266 };
267 ErrMin=(float)min;
268 ErrAvg=((float)sum)/((float)popsize);
269 }
270
271 ind selectind(int popsize)
272 {
273 int p,q,n;
274
275 if(getrand()>=Nuniform)
276 {
277 p=getrand()%popsize;
278 q=getrand()%popsize;
279 return (Err[p]<=Err[q]) ? OldPop[p] : OldPop[q];
280 } else {
281 return OldPop[getrand()%popsize];
282 };
283 }
284
285 void selection(int popsize)
286 {
287 int n,i,j;
288 ind *p;
289
290 int ncopy,nmutate,ncrossover;
291
292 ncopy=(popsize*Pcopy)/100;
293 nmutate=(popsize*Pmutate)/100;
294 ncrossover=popsize-ncopy-nmutate;
295 if(ncopy==0)
296 {
297 ncopy=1;
298 if(nmutate) nmutate--; else ncrossover--;
299 }
300 if(ncrossover&1) { ncrossover--; nmutate++; };
301
302 p=Pop; Pop=OldPop; OldPop=p; i=0;
303 copy(OldPop[TopInd],Pop[i++]);
304 for(j=1;j<ncopy;j++)
305 copy(selectind(popsize),Pop[i++]);
306 for(j=0;j<ncrossover;j+=2)
307 crossover(selectind(popsize),selectind(popsize),Pop[i++],Pop[i++]);
308 while(i<popsize)
309 mutate(selectind(popsize),Pop[i++]);
310 }
311
(c) Bernhard Ömer - oemer@tph.tuwien.ac.at - http://tph.tuwien.ac.at/~oemer/