1 #ifdef HAVE_STDLIB_H
2 #include <stdlib.h>
3 #endif
4 #include <string.h>
5
6 #include <sys/types.h>
7 #include <math.h>
8 #include <errno.h>
9 #include "yagi.h"
10
11
12
13 typedef struct {
14 int parent1,parent2 ;
15 char *gene ;
16 double fitness ;
17 } GeneRecord ;
18
19
20 int population_size=0 ;
21 int gene_length=0 ;
22 int elite=1 ;
23 int ramp=0 ;
24 int PRINT=1 ;
25 double MX ;
26 /* double pmutate=0.4 ;
27 double pcross=0.6 ;
28 double psimplex=0.4 ;
29 double ptrans=0.2 ; */
30 double pmutate=0.1 ;
31 double pcross=0.9 ;
32 double psimplex=0.5 ;
33 double ptrans=0.03 ;
34 #include <errno.h>
35
36 GeneRecord *Pop1=NULL,*Pop2=NULL ;
37
setprobs(double pm,double pc,double ps,double pt)38 void setprobs(double pm,double pc,double ps,double pt)
39 {
40 pmutate=pm ;
41 pcross=pc ;
42 psimplex=ps;
43 ptrans=pt ;
44 }
45
GA_Free(void)46 int GA_Free(void)
47 {
48 int a ;
49 if (Pop1!=NULL) {
50 for(a=0 ; a<population_size ;a++)
51 if (Pop1[a].gene!=NULL) free(Pop1[a].gene) ;
52 free((char *) Pop1) ;
53 }
54 if (Pop2!=NULL) {
55 for(a=0 ; a<population_size ;a++)
56 if (Pop2[a].gene!=NULL) free(Pop2[a].gene) ;
57 free((char *) Pop2) ;
58 }
59 return(0);
60 }
61
GA_Error(char * ErrorMsg)62 int GA_Error(char *ErrorMsg)
63 {
64 int a ;
65 if (Pop1!=NULL) {
66 for(a=0 ; a<population_size ;a++)
67 if (Pop1[a].gene!=NULL) free(Pop1[a].gene) ;
68 free(Pop1) ;
69 }
70 if (Pop2!=NULL) {
71 for(a=0 ; a<population_size ;a++)
72 if (Pop2[a].gene!=NULL) free(Pop2[a].gene) ;
73 free(Pop2) ;
74 }
75 fprintf(stderr,"GA_LIB Error : %s \n\n",ErrorMsg) ;
76 exit(1) ;
77 }
78
GetMax()79 double GetMax()
80 {
81 return(MX) ;
82 }
83
SetPrint(int a)84 void SetPrint(int a)
85 {
86 PRINT=a;
87 }
dump_pop1(FILE * fd,int generation,double max,double aver)88 void dump_pop1(FILE *fd,int generation,double max,double aver)
89 {
90 int a ;
91
92 if (PRINT==0) return ;
93 fprintf(fd,"Current contents of population: generation %d\n",generation);
94 for(a=0 ; a<gene_length ; a++) fprintf(fd,"-");
95 fprintf(fd,"------------------\n");
96 fprintf(fd,"Par1 Par2 Fitness Code\n");
97 for(a=0 ; a<population_size ; a++)
98 fprintf(fd,"%4d %4d %9.4f %s\n",Pop1[a].parent1,Pop1[a].parent2,Pop1[a].fitness,Pop1[a].gene);
99 fprintf(fd,"\n Maximum %9.4f Average %9.4f\n",max,aver);
100 for(a=0 ; a<gene_length ; a++) fprintf(fd,"-");
101 fprintf(fd,"------------------\n\n");
102 }
103
Initialise(int PopSize,int GeneSize)104 int Initialise(int PopSize, int GeneSize)
105 {
106 int a,b ;
107 char c[2] ;
108
109 c[1]=0 ;
110
111 /* srandom(time(&a)); */
112 ramp=0 ;
113 population_size=PopSize ;
114 gene_length=GeneSize+1 ;
115 /* limit population size */
116 if ((PopSize<20)||(PopSize>1000)) GA_Error("Bad parameters to Initialise") ;
117 /* Allocate memory for population 1 */
118 Pop1=(GeneRecord *)calloc(PopSize,sizeof(GeneRecord)) ;
119 /* Mem alloc error */
120 if (Pop1==NULL) GA_Error((char *)"Memory allocation for population 1") ;
121 /* Blank population array */
122 for (a=0 ; a<population_size ; a++) {
123 Pop1[a].gene=NULL ;
124 Pop1[a].parent1=0 ;
125 Pop1[a].parent2=0 ;
126 Pop1[a].fitness=0.0 ;
127 }
128 /* Allocate memory for genes */
129 for (a=0 ; a<population_size ; a++)
130 if ((Pop1[a].gene=malloc(gene_length))==NULL)
131 GA_Error("Cannot allocate gene in population 1");
132 /* Allocate memory for population 2 */
133 Pop2=(GeneRecord *)calloc(PopSize,sizeof(GeneRecord)) ;
134 /* Mem alloc error */
135 if (Pop2==NULL) GA_Error((char *)"Memory allocation for population 1") ;
136 /* Blank population array */
137 for (a=0 ; a<population_size ; a++) {
138 Pop2[a].gene=NULL ;
139 Pop2[a].parent1=0 ;
140 Pop2[a].parent2=0 ;
141 Pop2[a].fitness=0.0 ;
142 }
143 /* Allocate memory for genes */
144 for (a=0 ; a<population_size ; a++)
145 if ((Pop2[a].gene=malloc(gene_length))==NULL)
146 GA_Error("Cannot allocate gene in population 2");
147 /* Initialise genes */
148 for (a=0 ; a<population_size ; a++) {
149 for (b=0 ; b<GeneSize ; b++)
150 /* Pop1[a].gene[b]=(char)(48+(randint()&1)) ;XXXXXXXX */
151 Pop1[a].gene[b]=(char)(48+(randint()&1)) ;
152 Pop1[a].gene[GeneSize]=0 ;
153 }
154
155 #ifdef DEBUG
156 if(errno)
157 {
158 fprintf(stderr,"Errno =%d in Initialise() of ga_lib.c\n", errno);
159 exit(1);
160 }
161 #endif
162 return (0) ;
163 }
164
crossover(char * s1,char * s2)165 void crossover(char *s1,char *s2)
166 {
167 int point;
168 char duplic ;
169
170 /* only works for strings of same length */
171 if (strlen(s1)!=strlen(s2)) GA_Error((char *)"Gene length mismatch for crossover") ;
172 /* choose a point and swap tails of strings */
173 for (point=(randint()%(strlen(s1)-2))+1 ; point <strlen(s1) ; point++)
174 {
175 duplic=s1[point] ;
176 s1[point]=s2[point] ;
177 s2[point]=duplic ;
178 }
179 }
180
mutate(char * s1)181 void mutate(char *s1)
182 {
183 /* flip a bit in at random point */
184 s1[randint()%strlen(s1)]^=1 ;
185 }
186
ga_simplex(char * s1,char * s2,char * s3)187 int ga_simplex(char *s1,char *s2, char *s3)
188 {
189 int point ;
190 for (point=0 ; point <(strlen(s1)-1) ; point++ )
191 if (s1[point]==s2[point])
192 s3[point]=s1[point] ;
193 else
194 s3[point]=s3[point]^1 ;
195 return(0);
196 }
197
swap(int * x,int * y)198 void swap(int *x,int *y)
199 {
200 int t ;
201 t=*x ;
202 *x=*y ;
203 *y=t ;
204 }
205
Sort()206 void Sort()
207 {
208 GeneRecord T ;
209 int outer,inner,moved;
210
211 for (outer=population_size-1; outer>0 ; outer--)
212 {
213 moved=0 ;
214 for (inner=0 ; inner<outer ; inner++)
215 {
216 if (Pop1[inner].fitness<Pop1[inner+1].fitness)
217 {
218 memcpy((char *) &T,(char *) &Pop1[inner],sizeof(GeneRecord)) ;
219 memcpy((char *) &Pop1[inner],(char *) &Pop1[inner+1],sizeof(GeneRecord)) ;
220 memcpy((char *) &Pop1[inner+1],(char *) &T,sizeof(GeneRecord)) ;
221 moved=1;
222 }
223 }
224 if (moved==0) break ;
225 }
226 }
227
transloc(char * gene)228 void transloc(char *gene)
229 {
230 int a,point,gene_size ;
231 char *dup;
232
233 gene_size=gene_length-1 ;
234 point=randint()%gene_size ;
235 dup=strdup(gene) ;
236 for(a=0 ; a<gene_size ; a++) gene[a]=dup[(a+point)%gene_size] ;
237 free(dup);
238 }
239
Selection(FILE * fd,int gen)240 int Selection(FILE *fd, int gen)
241 {
242 int a,b,c,d ;
243 double sigma ;
244 GeneRecord *temp ;
245 double minfit,maxfit ;
246 sigma=0.0 ;
247 minfit=MAXFLOAT;
248 maxfit=-minfit ;
249 /* minfit=1e308; maxfit=-1e308; XXXXXXXXXXXXXXXXXXXXXX */
250 for(a=0 ; a<population_size ; a++ )
251 {
252 Pop1[a].fitness=Objective(Pop1[a].gene) ;
253 if (Pop1[a].fitness<minfit) minfit=Pop1[a].fitness ;
254 if (Pop1[a].fitness>maxfit) maxfit=Pop1[a].fitness ;
255 sigma+=Pop1[a].fitness ;
256 }
257 MX=maxfit ;
258 Sort() ;
259 dump_pop1(fd,gen,maxfit,sigma/population_size);
260 for(a=0 ; a<population_size ; a++ )
261 {
262 if(minfit!=maxfit)
263 {
264 Pop1[a].fitness=((Pop1[a].fitness-minfit)*99.0/(maxfit-minfit))+1.0 ;
265 }
266 }
267 ramp++ ;
268 sigma=0.0 ;
269 for(a=0 ; a<population_size ; a++ )
270 sigma+=Pop1[a].fitness ;
271 c=0 ;
272 for(a=0 ; a<population_size ; a++ )
273 {
274 b=(int) (Pop1[a].fitness*population_size/sigma) ;
275 for (d=0 ; d<b ; d++)
276 strcpy(Pop2[c++].gene,Pop1[a].gene) ;
277 }
278 for(d=c ; d<population_size ; d++)
279 {
280 b=randint()%population_size ;
281 strcpy(Pop2[d].gene,Pop1[b].gene) ;
282 }
283 for(a=0 ; a<population_size ;a++)
284 {
285 if (randreal()<pmutate) mutate(Pop2[a].gene) ;
286 if (randreal()<ptrans) transloc(Pop2[a].gene) ;
287 }
288 temp=Pop1 ;
289 Pop1=Pop2 ;
290 Pop2=temp ;
291 for(a=2 ; a<population_size ; a+=2 )
292 {
293 b=randint()%population_size ;
294 c=randint()%population_size ;
295 strcpy(Pop2[a].gene,Pop1[b].gene);
296 strcpy(Pop2[a+1].gene,Pop1[c].gene);
297 if (randreal()<pcross)
298 {
299 crossover(Pop2[a].gene,Pop2[a+1].gene) ;
300 Pop2[a].parent2=Pop2[a+1].parent1 ;
301 Pop2[a+1].parent2=Pop2[a].parent1 ;
302 } else {
303 Pop2[a].parent2=Pop2[a].parent1 ;
304 Pop2[a+1].parent2=Pop2[a+1].parent1 ;
305 }
306 }
307 if (randreal()<psimplex) {
308 a=randint()%population_size ;
309 b=randint()%population_size ;
310 c=randint()%population_size ;
311 if (Pop1[a].fitness<Pop1[b].fitness)
312 swap(&a,&b) ;
313 if (Pop1[b].fitness<Pop1[c].fitness)
314 swap(&b,&c) ;
315 if (Pop1[a].fitness<Pop1[b].fitness)
316 swap(&a,&b) ;
317 ga_simplex(Pop1[a].gene,Pop1[b].gene,Pop2[c].gene);
318 }
319 temp=Pop1 ;
320 Pop1=Pop2 ;
321 Pop2=temp ;
322 return 0 ;
323 }
324
325