[brlcad-commits] CVS: brlcad/src/gtools/beset beset.c, 1.20, 1.21 population.c, 1.16, 1.17 beset.h,
Open Source Solid Modeling CAD
Brought to you by:
brlcad
Menu
▾
▴
[brlcad-commits] CVS: brlcad/src/gtools/beset beset.c, 1.20, 1.21 population.c, 1.16, 1.17 beset.h, 1.7, 1.8 fitness.h, 1.11, 1.12 population.h, 1.8, 1.9
|
From: poolio <po...@us...> - 2007-07-31 21:54:53
|
Update of /cvsroot/brlcad/brlcad/src/gtools/beset In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv19049 Modified Files: beset.c population.c beset.h fitness.h population.h Log Message: now able to keep an upper % of population and kill a lower %. general code cleanup. Index: beset.c =================================================================== RCS file: /cvsroot/brlcad/brlcad/src/gtools/beset/beset.c,v retrieving revision 1.20 retrieving revision 1.21 diff -w -u -r1.20 -r1.21 --- beset.c 29 Jul 2007 16:34:59 -0000 1.20 +++ beset.c 31 Jul 2007 21:54:36 -0000 1.21 @@ -57,11 +57,11 @@ static int cmp_ind(const void *p1, const void *p2) { if(((struct individual *)p2)->fitness > ((struct individual *)p1)->fitness) - return 1; + return -1; else if (((struct individual *)p2)->fitness == ((struct individual *)p1)->fitness) return 0; else - return -1; + return 1; } int @@ -89,11 +89,19 @@ case 'r': opts->res = atoi(bu_optarg); continue; + case 'u': + opts->keep_upper = atoi(bu_optarg); + continue; + case 'l': + opts->kill_lower = atoi(bu_optarg); + continue; default: fprintf(stderr, "Unrecognized option: -%c\n", c); usage(); } } + opts->keep_upper *= opts->pop_size/100.0; + opts->kill_lower *= opts->pop_size/100.0; return bu_optind; } @@ -108,7 +116,7 @@ struct fitness_state *fstate; struct population *pop; char dbname[256]; //name of database - struct options opts = {DEFAULT_POP_SIZE, DEFAULT_GENS, DEFAULT_RES}; + struct options opts = {DEFAULT_POP_SIZE, DEFAULT_GENS, DEFAULT_RES, 0, 0}; struct individual *tmp; int ac; @@ -145,33 +153,51 @@ * note: need to calculate outside of main pop * loop because it's needed for pop_wrand_ind()*/ for(i = 0; i < pop->size; i++) { - fit_linDiff(pop->parent[i].id, pop->db_p, fstate); + fit_diff(pop->parent[i].id, pop->db_p, fstate); pop->parent[i].fitness = fstate->fitness; - if(pop->parent[i].fitness > pop->parent[best].fitness) best = i; - if(pop->parent[i].fitness < pop->parent[worst].fitness){ worst = i;} total_fitness += FITNESS; } - //total_fitness =0; - // pop->parent[i].fitness *= (pop->size-i)*(pop->size-i)/pop->size; - printf("Most fit from generation %3d was: %s, fitness of %g\n", g-1, pop->parent[best].id, pop->parent[best].fitness); - printf("%8.6g\t%8.6g\t%8.6g\n", total_fitness/pop->size, pop->parent[worst].fitness, pop->parent[best].fitness); - + /* sort population - used for keeping top N and bottom M% */ qsort(pop->parent, pop->size, sizeof(struct individual), cmp_ind); + /* remove lower % of individuals */ + for(i = 0; i < opts.kill_lower; i++) { + total_fitness -= pop->parent[i].fitness; + } + + + printf("Most fit individual was %s with a fitness of %g\n", pop->parent[pop->size-1].id, pop->parent[pop->size-1].fitness); + printf("%6.8g\t%6.8g\t%6.8g\n", total_fitness/pop->size, pop->parent[0].fitness, pop->parent[pop->size-1].fitness); for(i = 0; i < pop->size; i++){ + snprintf(pop->child[i].id, 256, "gen%.3dind%.3d", g, i); + + /* keep upper % */ + if(i >= pop->size- opts.keep_upper){ + pop_gop(REPRODUCE, pop->parent[i].id, NULL, pop->child[i].id, NULL, + pop->db_p, pop->db_c, &rt_uniresource); + continue; + } + /* Choose a random genetic operation and * a parent which the op will be performed on*/ gop = pop_wrand_gop(); - parent1 = pop_wrand_ind(pop->parent, pop->size, total_fitness); + parent1 = pop_wrand_ind(pop->parent, pop->size, total_fitness, opts.kill_lower); //printf("selected %g\n", pop->parent[parent1].fitness); - snprintf(pop->child[i].id, 256, "gen%.3dind%.3d", g, i); - /* If we're performing crossover, we need a second parent */ - if(gop == CROSSOVER && i < pop->size-1){ + if(gop == CROSSOVER && i >= pop->size-opts.keep_upper-1)gop=REPRODUCE; //cannot cross, so reproduce + if(gop & (REPRODUCE | MUTATE)){ +#ifdef VERBOSE + printf("r(%s)\t ---------------> (%s)\n", pop->parent[parent1].id, pop->child[i].id); +#endif + /* perform the genetic operation and output the child to the child database */ + pop_gop(gop, pop->parent[parent1].id, NULL, pop->child[i].id, NULL, + pop->db_p, pop->db_c, &rt_uniresource); + } else { + //while(parent2 == parent1) -- needed? can crossover be done on same 2 ind? - parent2 = pop_wrand_ind(pop->parent, pop->size, total_fitness); + parent2 = pop_wrand_ind(pop->parent, pop->size, total_fitness, opts.kill_lower); // printf("selected: %g\n", pop->parent[parent2].fitness); snprintf(pop->child[i].id, 256, "gen%.3dind%.3d", g, ++i); //name the child and increase pop count @@ -181,13 +207,6 @@ /* perform the genetic operation and output the children to the cihld database */ pop_gop(gop, pop->parent[parent1].id, pop->parent[parent2].id, pop->child[i-1].id, pop->child[i].id, pop->db_p, pop->db_c, &rt_uniresource); - } else { -#ifdef VERBOSE - printf("r(%s)\t ---------------> (%s)\n", pop->parent[parent1].id, pop->child[i].id); -#endif - /* perform the genetic operation and output the child to the child database */ - pop_gop(REPRODUCE, pop->parent[parent1].id, NULL, pop->child[i].id, NULL, - pop->db_p, pop->db_c, &rt_uniresource); } } Index: population.c =================================================================== RCS file: /cvsroot/brlcad/brlcad/src/gtools/beset/population.c,v retrieving revision 1.16 retrieving revision 1.17 diff -w -u -r1.16 -r1.17 --- population.c 30 Jul 2007 01:21:06 -0000 1.16 +++ population.c 31 Jul 2007 21:54:36 -0000 1.17 @@ -113,10 +113,12 @@ p2[2] = -10+pop_rand()*10; r2 = 1+3*pop_rand(); + /* p3[0] = -10+pop_rand()*10; p3[1] = -10+pop_rand()*10; p3[2] = -10+pop_rand()*10; r3 = 1+3*pop_rand(); + */ /* VSET(p1, -5, -5, -5); VSET(p2, 5, 5, 5); @@ -135,9 +137,11 @@ mk_sph(db_fp, p->parent[i].id, p2, r2); mk_addmember(p->parent[i].id, &wm_hd.l, NULL, WMOP_UNION); + /* snprintf(p->parent[i].id, 256, "gen%.3dind%.3d-%.3d", 0,i,2); mk_sph(db_fp, p->parent[i].id, p3, r3); mk_addmember(p->parent[i].id, &wm_hd.l, NULL, WMOP_UNION); + */ @@ -178,14 +182,13 @@ * P O P _ W R A N D -- weighted random index of parent */ int -pop_wrand_ind(struct individual *i, int size, fastf_t total_fitness) +pop_wrand_ind(struct individual *i, int size, fastf_t total_fitness, int offset) { - int n = 0; + int n = offset; fastf_t rindex, psum = 0; rindex =pop_rand() * total_fitness; - psum = i[n].fitness; - for(n = 1; n < size; n++) { + for(n = offset+1; n < size; n++) { psum += i[n].fitness; if( rindex <= psum ) return n-1; @@ -212,12 +215,15 @@ float i = bn_rand0to1(idx); if(i < 0.1) return REPRODUCE; + if(i < 0.3) + return MUTATE; return CROSSOVER; } int node_idx; int crossover_node; int crossover; +int mutate; int crossover_op; int num_nodes; union tree *crossover_point; @@ -296,6 +302,8 @@ else ++node_idx; } + else if(mutate) + ++node_idx; switch( tp->tr_op ) { @@ -310,6 +318,34 @@ snprintf(shape, 256, "%s-%.3d", name, shape_number++); bu_free(tp->tr_l.tl_name, "bu_strdup"); tp->tr_l.tl_name = bu_strdup(shape); +#define VSCALE_SELF(a,c) { (a)[X] *= (c); (a)[Y] *= (c); (a)[Z]*=(c);} +#define VMUT(a,c){(a)[X] += ((a)[X] == 0)?0:(c); (a)[Y] += ((a)[Y] == 0)?0:(c); (a)[Z]+=((a)[Z]==0)?0:(c);} +#define MUT_STEP .8 + + if(mutate){ + if(node_idx == crossover_node){ + switch(in.idb_minor_type){ + case ID_ELL: + /* + VSCALE_SELF(((struct rt_ell_internal *)in.idb_ptr)->v, .3+2*pop_rand()); + VSCALE_SELF(((struct rt_ell_internal *)in.idb_ptr)->a, .3+2*pop_rand()); + VSCALE_SELF(((struct rt_ell_internal *)in.idb_ptr)->b, .3+2*pop_rand()); + VSCALE_SELF(((struct rt_ell_internal *)in.idb_ptr)->c, .3+2*pop_rand()); + */ + VMUT(((struct rt_ell_internal *)in.idb_ptr)->v, -MUT_STEP/2+MUT_STEP*pop_rand()); + /* + VMUT(((struct rt_ell_internal *)in.idb_ptr)->a, -MUT_STEP/2+MUT_STEP*pop_rand()); + VMUT(((struct rt_ell_internal *)in.idb_ptr)->b, -MUT_STEP/2+MUT_STEP*pop_rand()); + VMUT(((struct rt_ell_internal *)in.idb_ptr)->c, -MUT_STEP/2+MUT_STEP*pop_rand()); + */ + + default: + break; + } + } + } + + if((dp=db_diradd(dbi_c, shape, -1, 0, dp->d_flags, (genptr_t)&dp->d_minor_type)) == DIR_NULL) bu_bomb("Failed to add new object to the database"); @@ -324,6 +360,11 @@ case OP_INTERSECT: case OP_SUBTRACT: case OP_XOR: + if(mutate){ + if(node_idx == crossover_node){ + // tp->tr_op = (int)(2+pop_rand()*3);//FIXME: pop_rand() can be 1! + } + } if(crossover && node_idx == crossover_node) crossover_parent = &tp->tr_b.tb_left; pop_functree( dbi_p, dbi_c, tp->tr_b.tb_left, resp, name); @@ -346,9 +387,9 @@ struct rt_db_internal in1, in2; struct rt_comb_internal *parent1; - struct rt_comb_internal *parent2, *swap; + struct rt_comb_internal *parent2; struct directory *dp; - union tree *cpoint, **tmp, **cross_parent; + union tree *cpoint, **cross_parent; struct node *add; int i = 0; @@ -358,7 +399,7 @@ bu_bomb("Failed to read parent1"); shape_number =num_nodes= 0; parent1 = (struct rt_comb_internal *)in1.idb_ptr; - + mutate = 0; switch(gop){ case REPRODUCE: pop_functree(dbi_p, dbi_c, parent1->tree, resp, child1_id); @@ -441,6 +482,12 @@ break; case MUTATE: + crossover_parent = &parent1->tree; + crossover_node = (int)(pop_rand() * db_count_tree_nodes(parent1->tree, 0)); + node_idx = 0; + mutate = 1; + pop_functree(dbi_p, dbi_c, parent1->tree, resp, child1_id); + mutate = 0; break; /* //random node to mutate Index: beset.h =================================================================== RCS file: /cvsroot/brlcad/brlcad/src/gtools/beset/beset.h,v retrieving revision 1.7 retrieving revision 1.8 diff -w -u -r1.7 -r1.8 --- beset.h 24 Jul 2007 19:41:44 -0000 1.7 +++ beset.h 31 Jul 2007 21:54:36 -0000 1.8 @@ -39,12 +39,14 @@ #define DEFAULT_POP_SIZE 20 #define DEFAULT_GENS 50 #define DEFAULT_RES 10 -#define OPTIONS ":x:p:g:r:" +#define OPTIONS ":x:p:g:r:u:l:" struct options{ int pop_size; int gens; int res; + int kill_lower; + int keep_upper; }; Index: fitness.h =================================================================== RCS file: /cvsroot/brlcad/brlcad/src/gtools/beset/fitness.h,v retrieving revision 1.11 retrieving revision 1.12 diff -w -u -r1.11 -r1.12 --- fitness.h 30 Jul 2007 01:21:06 -0000 1.11 +++ fitness.h 31 Jul 2007 21:54:36 -0000 1.12 @@ -37,8 +37,11 @@ #define STATUS_MP 2 #define STATUS_EMPTY 0 -#define DB_OPEN_FAILURE -1 -#define DB_DIRBUILD_FAILURE -2 +#define SEM_WORK RT_SEM_LAST +#define SEM_DIFF RT_SEM_LAST+1 +#define SEM_SAME RT_SEM_LAST+2 +#define TOTAL_SEMAPHORES SEM_SAME+1 + struct part { struct bu_list l; @@ -48,7 +51,7 @@ struct fitness_state { char *name; - struct part **rays; /* internal representation of raytraced source */ + struct part **ray; /* internal representation of raytraced source */ //struct db_i *db; /* the database the source and population are a part of */ struct rt_i *rtip; /* current objects to be raytraced */ @@ -66,10 +69,9 @@ fastf_t diff; /* linear difference between source and object */ fastf_t same; - fastf_t bbox[3]; /* z-min/max bounding line */ fastf_t mdl_min[3]; fastf_t fitness; - fastf_t norm; + fastf_t volume; }; /* store a ray that hit */ @@ -105,11 +107,11 @@ /* update grid resolution */ void fit_updateRes(int rows, int cols, struct fitness_state *fstate); -/* returns total linear difference between object and source */ -fastf_t fit_linDiff(char *obj, struct db_i *db, struct fitness_state *fstate); +/* calculates difference between object and source */ +void fit_diff(char *obj, struct db_i *db, struct fitness_state *fstate); /* clear the stored rays */ -void rays_clean (struct fitness_state *fstate); +void free_rays (struct fitness_state *fstate); #endif /* __FITNESS_H__ */ Index: population.h =================================================================== RCS file: /cvsroot/brlcad/brlcad/src/gtools/beset/population.h,v retrieving revision 1.8 retrieving revision 1.9 diff -w -u -r1.8 -r1.9 --- population.h 28 Jul 2007 07:14:56 -0000 1.8 +++ population.h 31 Jul 2007 21:54:36 -0000 1.9 @@ -60,7 +60,7 @@ void pop_spawn (struct population *p, struct rt_wdb *db_fp); void pop_clean (struct population *p); void pop_add (struct individual *i, struct rt_wdb *db); -int pop_wrand_ind (struct individual *i, int size, fastf_t total_fitness); +int pop_wrand_ind (struct individual *i, int size, fastf_t total_fitness, int offset); int pop_wrand_gop (void); fastf_t pop_rand (void); int pop_find_nodes(union tree *tp); |