Scrappy Genetic Algorithm! Visualise Styblinski–Tang
Posted: Tue Feb 09, 2021 7:10 pmScrappy Genetic Algorithm! Visualise solving Styblinski–Tang function
This is the Scrappy GA algo. A quick and dirty GA written to be used for Injecting a Deep NN with Wgt and Topology updates.
It has quite a few functions that arnt used in the demo.
There are 2 functions that are viewable on the Glut interface.
I hope this GA is useful not least for its simplicity
1. random genes for each individual in population
2. select proportional to fitness 2 individuals using roullete or rank
3. Breed with crossover and mutate the offspring using probability
4. Replace parents if offspring is fitter
5. Repeat 2-4
Simple. Ive added some elitest features.
We are using 1 point crossover (look it up its the simplest)
[code]void crossover(int job1, int job2){ //Crossover 2 individuals
int point;
for(int l=0;l<len;l++){
if(getlrand(0,1)<cross){
point = rand()%size_;
for(int i=0;i<point;i++){
ind[job2].gene[l][i]=ind[job1].gene[l][i];
}
for(int j=point;j<size_;j++){
ind[job1].gene[l][j]=ind[job2].gene[l][j];
}
}
}
}[/code]
The bin2dec function is a way to convert a binary string into a decimal
number. (Actually its not a string but an array of 0/1's)
There is a good bin2dec on [url=https://www.w3resource.com/c-programming-exercises/for-loop/c-for-loop-exercises-42.php]ww3[/url]
Ive just added some scaling for each problem.
[code]
void bin2dec(data* dt,double lower,double upper){
double dec=0;
double val;
double sum=0;
for(int i=0;i<size;i++){
sum+=pow(2,i);
}
for(int j=0;j<len;j++){
val =1;
for(int i=size;i>0;i--){
if(gene[j][i] == 1){
dec += val;
}
val *=2;
}
var[j]=dt->wgts[j]=(dec/sum)*(upper-lower)+lower;
dec=0;
} }
[/code]
Here is the Scrappy_GA code:
[code]
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
using namespace std;
/*Wet InSert GA for RLnet By SD*/
/*Slip in change the dynamic ConMat LUT or slip in and update wgts*/
double getlrand(double lower,double upper){
return ((double) rand()/ RAND_MAX) * (upper-lower) + lower;
}
struct data{
double *wgts;
};
data *dat;
class genome
{
public:
//bit array
double fitness;
int size; //Size of Chromosome
int len; //Number of Chromosomes
int **gene;
double *var;
void init(int size_, int len_)
{
size = size_;
len = len_;
var = new double[len];
gene = new int*[len_];
for(int i=0;i<len_;i++){
gene[i] = new int[size_];
for(int j=0;j<size_;j++){
gene[i][j] = ison(); }}
}
int ison(){
return rand()%2;
}
void bin2dec(data* dt,double lower,double upper){
double dec=0;
double val;
double sum=0;
for(int i=0;i<size;i++){
sum+=pow(2,i);
}
for(int j=0;j<len;j++){
val =1;
for(int i=size;i>0;i--){
if(gene[j][i] == 1){
dec += val;
}
val *=2;
}
var[j]=dt->wgts[j]=(dec/sum)*(upper-lower)+lower;
dec=0;
} }
};
class ga
{
public:
int len; //Length chrom
int size_;
int popsize;
double totalfit,upper_,lower_;
genome *ind; //Array of Individual Bit arrays
double cross,mut; //Operators
int fun,conn,ftest; //Switch forc type
double (*get_err4wgt)(double *wgts); //Return error for net pointer to
func
double (*get_err4con)(int *gene); //Return error for net from conmat
LUT
ga(int popsize_,int size,int chrom_len){
cross=0.8;
mut=0.001;
totalfit=0;
ftest=1; //Testing
conn=1; //Default for conmat
fun=0;
size_ = size;
len = chrom_len;
ind = new genome[popsize_];
popsize = popsize_;
dat = new data;
dat->wgts = new double[len];
for(int i=0;i<popsize;i++)
{
ind[i].init(size_,len);
}
}
void print_ind(int job){
for(int j=0;j<len;j++){
cout<<"Chrom :"<<j<<"\n";
for(int i=0;i<size_;i++){
cout<<ind[job].gene[j][i]<<",";
}
}
}
void print_dat(int job){
ind[job].bin2dec(dat,-5,5); //Internalize range
for(int i=0;i<len;i++){
cout<<dat->wgts[i]<<",";
}
}
double get_fit4func(int job,int funtype){
double sum=0;
double t1,t2,t3,t4;
if(funtype==2){ //Beal function only 2 dim
upper_=4.5;
lower_=-4.5;
ind[job].bin2dec(dat,lower_,upper_);
t1 = pow(1.5-dat->wgts[0]+dat->wgts[0]*dat->wgts[1],2);
t2 = pow(2.25-dat->wgts[0]+dat->wgts[0]*pow(dat->wgts[1],2),2);
t3 = pow(2.625-dat->wgts[0]+dat->wgts[0]*pow(dat->wgts[1],3),2);
return 1/(t1+t2+t3);
}
if(funtype==1){
upper_=5;
lower_=-5;
ind[job].bin2dec(dat,lower_,upper_);
for(int i=0;i<len;i++){ //Each chromo is a variable in solution
to
sum+=pow(dat->wgts[i],4)-16*pow(dat->wgts[i],2)+5*dat->wgts[i];
//Styblinski-Tang
}
return -(sum/2); //Return -39*n
}
if(funtype==0){
upper_=5;
lower_=-5;
ind[job].bin2dec(dat,lower_,upper_);
for(int i=0;i<len;i++){ //DeJongs Sphere (Easy)
sum+= pow(dat->wgts[i],2);
}
return 1/sum; //Return zero
}
//ind[job].fitness = 1/(sum/2);
}
double get_fit4wgts(int job){ //Quickly return fitness of Ind
//ind[job].bin2dec(dat,0,1); //Fill wgts array with doubles
return 1/get_err4wgt(dat->wgts); //Send wgts for net for error =
inv fitness
}
double get_fit4con(int job){
return 1/get_err4con(ind[job].gene[0]); //Use 1 dim gene for
connections
}
void crossover(int job1, int job2){ //Crossover 2 individuals
int point;
//int temp[size_];
for(int l=0;l<len;l++){
if(getlrand(0,1)<cross){
point = rand()%size_;
for(int i=0;i<point;i++){
ind[job2].gene[l][i]=ind[job1].gene[l][i];
}
for(int j=point;j<size_;j++){
ind[job1].gene[l][j]=ind[job2].gene[l][j];
}
}
}
}
void mutate(int job){ //mutate individual uing mut operator
for(int l=0;l<len;l++){
for(int i=0;i<size_;i++){
if(getlrand(0,1)<mut){
if(ind[job].gene[l][i] == 1){
ind[job].gene[l][i] = 0;
}else{
ind[job].gene[l][i] = 1;
}
}
}
}
}
int rank_select(int win){ //Get fittest Clone fitest
double best;
if(win){
best=-10000;}else{
best=10000;
}
int select;
for(int i=0;i<popsize;i++){
if(win){
if(ind[i].fitness>best){
best=ind[i].fitness;
select = i;
}
}else{
if(ind[i].fitness<best){
best=ind[i].fitness;
select = i;
}
}
}
return select;
}
void rank(){
int rnk;
int result[popsize];
for(int i=0;i<popsize;i++){
rnk=0;
for(int j=0;j<popsize;j++){
if(ind[j].fitness<ind[i].fitness)
rnk++;
}
result[i]=rnk;
}
for(int i=0;i<popsize;i++){
cout<<result[i]<<" "<<ind[i].fitness<<"\n";
}
}
void sorted(){ //My sorting algo (blck book!)
genome *tmp;
tmp = new genome[popsize];
for(int i=0;i<popsize;i++)
tmp[i].init(size_,len);
int i,j,sorted,array[popsize],c=0,temp;
for(i=0;i<popsize;i++){
array[i]=i;
}
do{
sorted=1;
for(i=0; i<popsize-1; i++){
if (ind[array[i]].fitness > ind[array[i+1]].fitness){
temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
sorted=0;
}
}
} while (sorted==0);
for(int i=0;i<popsize;i++)
tmp[i]=ind[i];
for(int i=0;i<popsize;i++)
ind[i]=tmp[array[i]];
}
int roulette_select(){ //Return individual using roulette
selection
double slice = getlrand(0,totalfit);
double fitsofar=0;
int selected=0;
for(int i=0;i<popsize;i++){ //Needs Ranking
selected = i;
fitsofar+= ind[selected].fitness;
if(slice<fitsofar)break;
}
return selected;
}
void replace(int p1,int p2){ //Replace p2 with p1
for(int l=0;l<len;l++){
for(int i=0;i<size_;i++){
ind[p2].gene[l][i] = ind[p1].gene[l][i];
}
}
}
void genecopy(genome ind1,genome ind2){ //Copy genes clone ind1
to ind2
for(int l=0;l<len;l++){
for(int i=0;i<size_;i++){
ind2.gene[l][i] = ind1.gene[l][i];
//ind2.fitness = ind1.fitness;
}
}
}
void getfit(){ //Measure fitness of pop
for(int i=0;i<popsize;i++){
if(ftest==1){
totalfit+= ind[i].fitness = get_fit4func(i,fun);
}else{
if(conn==1){
totalfit+= ind[i].fitness = get_fit4con(i);
}else{
totalfit+= ind[i].fitness = get_fit4wgts(i);
}
}
}
}
void cycle(){
int p1=0,p2=0,p3=0;
totalfit=0;
double fit1,fit2;
genome temp1;
genome temp2;
temp1.init(size_,len);
temp2.init(size_,len);
for(int i=0;i<popsize;i++){
if(ftest==1){
totalfit+= ind[i].fitness = get_fit4func(i,fun);
}else{
if(conn==1){
totalfit+= ind[i].fitness = get_fit4con(i);
}else{
totalfit+= ind[i].fitness = get_fit4wgts(i);
}
}
}
sorted();
if(1){
if(getlrand(0,1)<0.05){
p1 = rank_select(1);
p2 = rank_select(0);
}else{
p1 = roulette_select();
p2 = roulette_select();
}
genecopy(ind[p1],temp1); //Make a backup of parent 1
genecopy(ind[p2],temp2); //Make a backup of parent 2
fit1 = ind[p1].fitness;
fit2 = ind[p2].fitness;
crossover(p1,p2);
mutate(p1);
mutate(p2);
if(getlrand(0,1)<1){
if(get_fit4func(p1,fun)>fit1){ //If children > parents
//Replace parents
p3 = rank_select(0); //Children into pop
}else{
genecopy(temp1,ind[p1]); //Keep parents Kill children
}
if(get_fit4func(p2,fun)>fit2){
p3 = rank_select(0); //Children into pop
}else{
genecopy(temp2,ind[p2]); //Keep parents Kill children Yum
Yum
} }
}
if(0){ //Switch this on if your
feeling elitist!
p1 = rank_select(1); //Find the winner
p2 = rank_select(0); //Find a loser
//cout<<"----"<<p1<<" "<<p2<<"\n";
replace(p1,p2); //Replace loser with winers dna
}
}
};
[/code]
There is a kickass sorting algo that I borrowed from another job:
[code]
void sorted(){ //My sorting algo (blck book!)
genome *tmp;
tmp = new genome[popsize];
for(int i=0;i<popsize;i++)
tmp[i].init(size_,len);
int i,j,sorted,array[popsize],c=0,temp;
for(i=0;i<popsize;i++){
array[i]=i;
}
do{
sorted=1;
for(i=0; i<popsize-1; i++){
if (ind[array[i]].fitness > ind[array[i+1]].fitness){
temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
sorted=0;
}
}
} while (sorted==0);
for(int i=0;i<popsize;i++)
tmp[i]=ind[i];
for(int i=0;i<popsize;i++)
ind[i]=tmp[array[i]];
}
[/code]
It create an array for the ranking and then uses it to rearrange the
population according to fitness. Soo you dont get in a mess and
roullete needs it.
Here is the Glut interface with main:
[code]
#include <stdlib.h>
#include <stdio.h>
#ifndef WIN32
#include <unistd.h>
#else
#define random rand
#define srandom srand
#endif
#include <math.h>
#include <time.h>
#include <iostream>
#include <GL/glut.h>
#include "Scrappy_GA.cc"
/* Some <math.h> files do not define M_PI... */
#ifndef M_PI
#define M_PI 3.14159265
#endif
#ifndef M_PI_2
#define M_PI_2 1.57079632
#endif
using namespace std;
GLfloat funcpoints[200][200][3];
GLboolean moving = GL_FALSE;
//swarm myswarm(14,3);
ga myga(50,50,2); //50 individuals,12 bin, 300 wgts
double gsize=1; //Problem size
double hgt=1,scl=1,pscl=1; //Position
int res=10.0; //Resolution
int lowres=1;
double scrn = 50; //Screen size
#define MAX_PLANES 14
struct {
float speed; /* zero speed means not flying */
GLfloat red, green, blue;
float theta;
float x, y, z, angle;
} planes[MAX_PLANES];
#define v3f glVertex3f /* v3f was the short IRIS GL name for
glVertex3f */
#define v3d glVertex3d
void loadpoints(void){
double t0,t1,t2,x_,y_,sum=0;
for(int i=0;i<200;i++){
for(int j=0;j<200;j++){
x_ = ((double)i-100)/res;
y_ = ((double)j-100)/res;
if(lowres==1){
x_ = (int)x_;
y_ = (int)y_;
}
double pos[2];
pos[0] = x_;
pos[1] = y_;
if(myga.fun==1){
sum=pow(x_,4)-16*pow(x_,2)+5*x_; //Styblinski-Tang
sum+=pow(y_,4)-16*pow(y_,2)+5*y_;
}
if(myga.fun==0){
sum = pow(x_,2) + pow(y_,2);
}
funcpoints[i][j][0]=x_;
funcpoints[i][j][1]=y_;
funcpoints[i][j][2]=sum/gsize;
}
}
}
void drawlines2buffer(void){
glNewList(1,GL_COMPILE);
glPushMatrix ();
for(int i=0;i<200;i++){
for(int j=0;j<200;j++){
glBegin(GL_LINES);
glColor3f(0.0,1.0,1.0);
if(i<199){
v3d( funcpoints[i][j][0],funcpoints[i][j][1],funcpoints[i][j][2]);
v3d( funcpoints[i+1][j][0],funcpoints[i+1][j][1],funcpoints[i+1]
[j][2]);
}
glEnd();
glBegin(GL_LINES);
glColor3f(0.0,1.0,1.0);
if(j<199){
v3d( funcpoints[i][j][0],funcpoints[i][j][1],funcpoints[i][j][2]);
v3d( funcpoints[i][j+1][0]+0.1,funcpoints[i][j+1][1]
+0.1,funcpoints[i][j+1][2]+0.1);
}
glEnd();
}
}
glPopMatrix ();
glEndList();
}
void
print_bitmap_string(void* font, char* s)
{
if (s && strlen(s)) {
while (*s) {
glutBitmapCharacter(font, *s);
s++;
}
}
}
void
draw(void)
{
GLfloat red, green, blue;
int i,j;
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
/*Text output*/
double x = 15.0;
double y = -5.0;
double ystep = 100.0;
double yild = 20.0;
glColor3f(1.0, 1.0, 1.0);
char string[50];
double myfit=0;
if(myga.fun==0){myfit=1/myga.ind[49].fitness;}
if(myga.fun==1){myfit=-myga.ind[49].fitness/2;}
sprintf(string,"Global Best Solution = %f,%f,%f",myfit,myga.ind
[49].var[0],myga.ind[49].var[1]);
int len = strlen(string);
glRasterPos2f(x, y);
print_bitmap_string(GLUT_BITMAP_TIMES_ROMAN_10, string);
/* draw function in 3d */
glCallList(1);
/* paint planes */
glEnable(GL_DEPTH_TEST);
glShadeModel(GL_FLAT);
for (i = 0; i < MAX_PLANES; i++)
if (planes[i].speed != 0.0) {
glPushMatrix();
glTranslatef(planes[i].x, planes[i].y, planes[i].z);
//glScalef(1.0 / 5, 1.0 / 5, 1.0 / 5);
//glRotatef(290.0, 1.0, 0.0, 0.0);
glRotatef(planes[i].angle, 0.0, 0.0, 1.0);
glScalef(1.0 / 12.0, 1.0 / 16.0, 1.0 / 16.0);
glTranslatef(0.0, -4.0, -1.5);
if(1){
glBegin(GL_TRIANGLE_STRIP);
/* left wing */
v3f(-7.0, 0.0, 2.0);
v3f(-1.0, 0.0, 3.0);
glColor3f(red = planes[i].red, green = planes[i].green,
blue = planes[i].blue);
v3f(-1.0, 7.0, 3.0);
/* left side */
glColor3f(0.6 * red, 0.6 * green, 0.6 * blue);
v3f(0.0, 0.0, 0.0);
v3f(0.0, 8.0, 0.0);
/* right side */
v3f(1.0, 0.0, 3.0);
v3f(1.0, 7.0, 3.0);
/* final tip of right wing */
glColor3f(red, green, blue);
v3f(7.0, 0.0, 2.0);
glEnd();
}
//glColor3f(0, 1, 0);
//glutSolidSphere(7.0,50,50);
glPopMatrix();
}
glutSwapBuffers();
}
void reshape(int w, int h)
{
glViewport(0, 0, (GLsizei) w, (GLsizei) h);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
if (w <= h)
glOrtho(-scrn, scrn, -scrn*(GLfloat)h/(GLfloat)w,
scrn*(GLfloat)h/(GLfloat)w, -scrn, scrn);
else
glOrtho(-scrn*(GLfloat)w/(GLfloat)h,
scrn*(GLfloat)w/(GLfloat)h, -scrn, scrn, -scrn, scrn);
/* Rescale and resize Globally */
glScalef(scl*6.0 / 3.7, scl*6.0 / 3.7, scl*6.0 / 3.7);
glTranslatef(0.0,hgt,0.0);
glRotatef(310,1.0,0.0,0.0);
glRotatef(65,0.0,0.0,1.0);
glRotatef(5,0.0,1.0,0.0);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
}
void
tick_per_plane(int i)
{
//myswarm.mainloop(1);
myga.cycle();
float theta = planes[i].theta += planes[i].speed;
planes[i].z = myga.ind[i].fitness/gsize;
planes[i].x = myga.ind[i].var[0];
planes[i].y = myga.ind[i].var[1];
planes[i].angle = ((atan(2.0) + M_PI_2) * sin(theta) - M_PI_2) * 180
/ M_PI;
if (planes[i].speed < 0.0)
planes[i].angle += 180;
}
void
add_plane(void)
{
int i;
for (i = 0; i < MAX_PLANES; i++)
if (planes[i].speed == 0) {
#define SET_COLOR(r,g,b) \
planes[i].red=r; planes[i].green=g; planes[i].blue=b;
switch (random() % 6) {
case 0:
SET_COLOR(1.0, 0.0, 0.0); /* red */
break;
case 1:
SET_COLOR(1.0, 1.0, 1.0); /* white */
break;
case 2:
SET_COLOR(0.0, 1.0, 0.0); /* green */
break;
case 3:
SET_COLOR(1.0, 0.0, 1.0); /* magenta */
break;
case 4:
SET_COLOR(1.0, 1.0, 0.0); /* yellow */
break;
case 5:
SET_COLOR(0.0, 1.0, 1.0); /* cyan */
break;
}
planes[i].speed = ((float) (random() % 20)) * 0.001 + 0.02;
if (random() & 0x1)
planes[i].speed *= -1;
planes[i].theta = ((float) (random() % 257)) * 0.1111;
tick_per_plane(i);
if (!moving)
glutPostRedisplay();
return;
}
}
void
remove_plane(void)
{
int i;
for (i = MAX_PLANES - 1; i >= 0; i--)
if (planes[i].speed != 0) {
planes[i].speed = 0;
if (!moving)
glutPostRedisplay();
return;
}
}
void
tick(void)
{
int i;
for (i = 0; i < MAX_PLANES; i++)
if (planes[i].speed != 0.0)
tick_per_plane(i);
}
void
animate(void)
{
tick();
glutPostRedisplay();
}
void timer(int value){
/* Set the next timed callback */
glutTimerFunc ( 30, timer, 0 ) ;
drawlines2buffer();
glutPostRedisplay () ;
}
void
visible(int state)
{
if (state == GLUT_VISIBLE) {
if (moving)
glutIdleFunc(animate);
} else {
if (moving)
glutIdleFunc(NULL);
}
}
float horiz=0,vert=0,zoom=4.0;
/* ARGSUSED1 */
void
keyboard(unsigned char ch, int x, int y)
{
switch (ch) {
case 'l':
zoom+=1;
glScalef(1.0/zoom,1.0/zoom,1.0/zoom);
glutPostRedisplay();
break;
case 'k':
zoom-=1;
glScalef(1.0/zoom,1.0/zoom,1.0/zoom);
glutPostRedisplay();
break;
case ',':
vert++;
glRotatef(vert,0.0,1.0,0.0);
glutPostRedisplay();
break;
case '.':
vert++;
glRotatef(vert,1.0,0.0,0.0);
glutPostRedisplay();
break;
case '#':
horiz++;
glRotatef(horiz,0.0,1.0,0.0);
glutPostRedisplay();
break;
case '/':
horiz++;
glRotatef(horiz,1.0,0.0,0.0);
glutPostRedisplay();
break;
case ' ':
if (!moving) {
tick();
glutPostRedisplay();
}
break;
case 27: /* ESC */
exit(0);
break;
}
}
#define ADD_PLANE 1
#define REMOVE_PLANE 2
#define MOTION_ON 3
#define MOTION_OFF 4
#define QUIT 5
#define INCREASE_LRT 6
void
menu(int item)
{
switch (item) {
case ADD_PLANE:
add_plane();
break;
case REMOVE_PLANE:
remove_plane();
break;
case MOTION_ON:
moving = GL_TRUE;
glutChangeToMenuEntry(3, "Motion off", MOTION_OFF);
glutIdleFunc(animate);
break;
case MOTION_OFF:
moving = GL_FALSE;
glutChangeToMenuEntry(3, "Motion", MOTION_ON);
glutIdleFunc(NULL);
break;
case INCREASE_LRT:
myga.cross+=0.1;
break;
case QUIT:
exit(0);
break;
}
}
int
main(int argc, char *argv[])
{
hgt = -4.5;scl =3;pscl=1;gsize = 200;
res = 10;lowres=1;scrn=75;
myga.cross=0.7;
myga.mut=0.001;
myga.fun=1; //Which test function
glutInit(&argc, argv);
/* use multisampling if available */
glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH |
GLUT_MULTISAMPLE);
glutCreateWindow("glutplane");
loadpoints();
drawlines2buffer();
glutDisplayFunc(draw);
glutReshapeFunc(reshape);
//glutTimerFunc(30, timer, 0 );
glutKeyboardFunc(keyboard);
//glutVisibilityFunc(visible);
glutCreateMenu(menu);
glutAddMenuEntry("Add plane", ADD_PLANE);
glutAddMenuEntry("Remove plane", REMOVE_PLANE);
glutAddMenuEntry("Motion", MOTION_ON);
glutAddMenuEntry("Inc Lrt", INCREASE_LRT);
glutAddMenuEntry("Quit", QUIT);
glutAttachMenu(GLUT_RIGHT_BUTTON);
/* setup OpenGL state */
glClearDepth(1.0);
glClearColor(0.0, 0.0, 0.0, 0.0);
glMatrixMode(GL_PROJECTION);
glFrustum(-1.0, 1.0, -1.0, 1.0, 1.0, 20);
glMatrixMode(GL_MODELVIEW);
/* add three initial random planes */
srandom(time(NULL));
for(int i=0;i<14;i++){
add_plane(); }
/* start event processing */
glutMainLoop();
return 0; /* ANSI C requires main to return int. */
}
[/code]
Compile with :
g++ -o glutsga glutsga.cc -lglu32 -lopengl32 -lfreeglut
(NB you have to fiddle with the gsize variable to rescale the problems
to fit on the screen e.g fun=0 requires gscale=2 , fun=1 gscale=200)
This is the Scrappy GA algo. A quick and dirty GA written to be used for Injecting a Deep NN with Wgt and Topology updates.
It has quite a few functions that arnt used in the demo.
There are 2 functions that are viewable on the Glut interface.
I hope this GA is useful not least for its simplicity
1. random genes for each individual in population
2. select proportional to fitness 2 individuals using roullete or rank
3. Breed with crossover and mutate the offspring using probability
4. Replace parents if offspring is fitter
5. Repeat 2-4
Simple. Ive added some elitest features.
We are using 1 point crossover (look it up its the simplest)
[code]void crossover(int job1, int job2){ //Crossover 2 individuals
int point;
for(int l=0;l<len;l++){
if(getlrand(0,1)<cross){
point = rand()%size_;
for(int i=0;i<point;i++){
ind[job2].gene[l][i]=ind[job1].gene[l][i];
}
for(int j=point;j<size_;j++){
ind[job1].gene[l][j]=ind[job2].gene[l][j];
}
}
}
}[/code]
The bin2dec function is a way to convert a binary string into a decimal
number. (Actually its not a string but an array of 0/1's)
There is a good bin2dec on [url=https://www.w3resource.com/c-programming-exercises/for-loop/c-for-loop-exercises-42.php]ww3[/url]
Ive just added some scaling for each problem.
[code]
void bin2dec(data* dt,double lower,double upper){
double dec=0;
double val;
double sum=0;
for(int i=0;i<size;i++){
sum+=pow(2,i);
}
for(int j=0;j<len;j++){
val =1;
for(int i=size;i>0;i--){
if(gene[j][i] == 1){
dec += val;
}
val *=2;
}
var[j]=dt->wgts[j]=(dec/sum)*(upper-lower)+lower;
dec=0;
} }
[/code]
Here is the Scrappy_GA code:
[code]
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
using namespace std;
/*Wet InSert GA for RLnet By SD*/
/*Slip in change the dynamic ConMat LUT or slip in and update wgts*/
double getlrand(double lower,double upper){
return ((double) rand()/ RAND_MAX) * (upper-lower) + lower;
}
struct data{
double *wgts;
};
data *dat;
class genome
{
public:
//bit array
double fitness;
int size; //Size of Chromosome
int len; //Number of Chromosomes
int **gene;
double *var;
void init(int size_, int len_)
{
size = size_;
len = len_;
var = new double[len];
gene = new int*[len_];
for(int i=0;i<len_;i++){
gene[i] = new int[size_];
for(int j=0;j<size_;j++){
gene[i][j] = ison(); }}
}
int ison(){
return rand()%2;
}
void bin2dec(data* dt,double lower,double upper){
double dec=0;
double val;
double sum=0;
for(int i=0;i<size;i++){
sum+=pow(2,i);
}
for(int j=0;j<len;j++){
val =1;
for(int i=size;i>0;i--){
if(gene[j][i] == 1){
dec += val;
}
val *=2;
}
var[j]=dt->wgts[j]=(dec/sum)*(upper-lower)+lower;
dec=0;
} }
};
class ga
{
public:
int len; //Length chrom
int size_;
int popsize;
double totalfit,upper_,lower_;
genome *ind; //Array of Individual Bit arrays
double cross,mut; //Operators
int fun,conn,ftest; //Switch forc type
double (*get_err4wgt)(double *wgts); //Return error for net pointer to
func
double (*get_err4con)(int *gene); //Return error for net from conmat
LUT
ga(int popsize_,int size,int chrom_len){
cross=0.8;
mut=0.001;
totalfit=0;
ftest=1; //Testing
conn=1; //Default for conmat
fun=0;
size_ = size;
len = chrom_len;
ind = new genome[popsize_];
popsize = popsize_;
dat = new data;
dat->wgts = new double[len];
for(int i=0;i<popsize;i++)
{
ind[i].init(size_,len);
}
}
void print_ind(int job){
for(int j=0;j<len;j++){
cout<<"Chrom :"<<j<<"\n";
for(int i=0;i<size_;i++){
cout<<ind[job].gene[j][i]<<",";
}
}
}
void print_dat(int job){
ind[job].bin2dec(dat,-5,5); //Internalize range
for(int i=0;i<len;i++){
cout<<dat->wgts[i]<<",";
}
}
double get_fit4func(int job,int funtype){
double sum=0;
double t1,t2,t3,t4;
if(funtype==2){ //Beal function only 2 dim
upper_=4.5;
lower_=-4.5;
ind[job].bin2dec(dat,lower_,upper_);
t1 = pow(1.5-dat->wgts[0]+dat->wgts[0]*dat->wgts[1],2);
t2 = pow(2.25-dat->wgts[0]+dat->wgts[0]*pow(dat->wgts[1],2),2);
t3 = pow(2.625-dat->wgts[0]+dat->wgts[0]*pow(dat->wgts[1],3),2);
return 1/(t1+t2+t3);
}
if(funtype==1){
upper_=5;
lower_=-5;
ind[job].bin2dec(dat,lower_,upper_);
for(int i=0;i<len;i++){ //Each chromo is a variable in solution
to
sum+=pow(dat->wgts[i],4)-16*pow(dat->wgts[i],2)+5*dat->wgts[i];
//Styblinski-Tang
}
return -(sum/2); //Return -39*n
}
if(funtype==0){
upper_=5;
lower_=-5;
ind[job].bin2dec(dat,lower_,upper_);
for(int i=0;i<len;i++){ //DeJongs Sphere (Easy)
sum+= pow(dat->wgts[i],2);
}
return 1/sum; //Return zero
}
//ind[job].fitness = 1/(sum/2);
}
double get_fit4wgts(int job){ //Quickly return fitness of Ind
//ind[job].bin2dec(dat,0,1); //Fill wgts array with doubles
return 1/get_err4wgt(dat->wgts); //Send wgts for net for error =
inv fitness
}
double get_fit4con(int job){
return 1/get_err4con(ind[job].gene[0]); //Use 1 dim gene for
connections
}
void crossover(int job1, int job2){ //Crossover 2 individuals
int point;
//int temp[size_];
for(int l=0;l<len;l++){
if(getlrand(0,1)<cross){
point = rand()%size_;
for(int i=0;i<point;i++){
ind[job2].gene[l][i]=ind[job1].gene[l][i];
}
for(int j=point;j<size_;j++){
ind[job1].gene[l][j]=ind[job2].gene[l][j];
}
}
}
}
void mutate(int job){ //mutate individual uing mut operator
for(int l=0;l<len;l++){
for(int i=0;i<size_;i++){
if(getlrand(0,1)<mut){
if(ind[job].gene[l][i] == 1){
ind[job].gene[l][i] = 0;
}else{
ind[job].gene[l][i] = 1;
}
}
}
}
}
int rank_select(int win){ //Get fittest Clone fitest
double best;
if(win){
best=-10000;}else{
best=10000;
}
int select;
for(int i=0;i<popsize;i++){
if(win){
if(ind[i].fitness>best){
best=ind[i].fitness;
select = i;
}
}else{
if(ind[i].fitness<best){
best=ind[i].fitness;
select = i;
}
}
}
return select;
}
void rank(){
int rnk;
int result[popsize];
for(int i=0;i<popsize;i++){
rnk=0;
for(int j=0;j<popsize;j++){
if(ind[j].fitness<ind[i].fitness)
rnk++;
}
result[i]=rnk;
}
for(int i=0;i<popsize;i++){
cout<<result[i]<<" "<<ind[i].fitness<<"\n";
}
}
void sorted(){ //My sorting algo (blck book!)
genome *tmp;
tmp = new genome[popsize];
for(int i=0;i<popsize;i++)
tmp[i].init(size_,len);
int i,j,sorted,array[popsize],c=0,temp;
for(i=0;i<popsize;i++){
array[i]=i;
}
do{
sorted=1;
for(i=0; i<popsize-1; i++){
if (ind[array[i]].fitness > ind[array[i+1]].fitness){
temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
sorted=0;
}
}
} while (sorted==0);
for(int i=0;i<popsize;i++)
tmp[i]=ind[i];
for(int i=0;i<popsize;i++)
ind[i]=tmp[array[i]];
}
int roulette_select(){ //Return individual using roulette
selection
double slice = getlrand(0,totalfit);
double fitsofar=0;
int selected=0;
for(int i=0;i<popsize;i++){ //Needs Ranking
selected = i;
fitsofar+= ind[selected].fitness;
if(slice<fitsofar)break;
}
return selected;
}
void replace(int p1,int p2){ //Replace p2 with p1
for(int l=0;l<len;l++){
for(int i=0;i<size_;i++){
ind[p2].gene[l][i] = ind[p1].gene[l][i];
}
}
}
void genecopy(genome ind1,genome ind2){ //Copy genes clone ind1
to ind2
for(int l=0;l<len;l++){
for(int i=0;i<size_;i++){
ind2.gene[l][i] = ind1.gene[l][i];
//ind2.fitness = ind1.fitness;
}
}
}
void getfit(){ //Measure fitness of pop
for(int i=0;i<popsize;i++){
if(ftest==1){
totalfit+= ind[i].fitness = get_fit4func(i,fun);
}else{
if(conn==1){
totalfit+= ind[i].fitness = get_fit4con(i);
}else{
totalfit+= ind[i].fitness = get_fit4wgts(i);
}
}
}
}
void cycle(){
int p1=0,p2=0,p3=0;
totalfit=0;
double fit1,fit2;
genome temp1;
genome temp2;
temp1.init(size_,len);
temp2.init(size_,len);
for(int i=0;i<popsize;i++){
if(ftest==1){
totalfit+= ind[i].fitness = get_fit4func(i,fun);
}else{
if(conn==1){
totalfit+= ind[i].fitness = get_fit4con(i);
}else{
totalfit+= ind[i].fitness = get_fit4wgts(i);
}
}
}
sorted();
if(1){
if(getlrand(0,1)<0.05){
p1 = rank_select(1);
p2 = rank_select(0);
}else{
p1 = roulette_select();
p2 = roulette_select();
}
genecopy(ind[p1],temp1); //Make a backup of parent 1
genecopy(ind[p2],temp2); //Make a backup of parent 2
fit1 = ind[p1].fitness;
fit2 = ind[p2].fitness;
crossover(p1,p2);
mutate(p1);
mutate(p2);
if(getlrand(0,1)<1){
if(get_fit4func(p1,fun)>fit1){ //If children > parents
//Replace parents
p3 = rank_select(0); //Children into pop
}else{
genecopy(temp1,ind[p1]); //Keep parents Kill children
}
if(get_fit4func(p2,fun)>fit2){
p3 = rank_select(0); //Children into pop
}else{
genecopy(temp2,ind[p2]); //Keep parents Kill children Yum
Yum
} }
}
if(0){ //Switch this on if your
feeling elitist!
p1 = rank_select(1); //Find the winner
p2 = rank_select(0); //Find a loser
//cout<<"----"<<p1<<" "<<p2<<"\n";
replace(p1,p2); //Replace loser with winers dna
}
}
};
[/code]
There is a kickass sorting algo that I borrowed from another job:
[code]
void sorted(){ //My sorting algo (blck book!)
genome *tmp;
tmp = new genome[popsize];
for(int i=0;i<popsize;i++)
tmp[i].init(size_,len);
int i,j,sorted,array[popsize],c=0,temp;
for(i=0;i<popsize;i++){
array[i]=i;
}
do{
sorted=1;
for(i=0; i<popsize-1; i++){
if (ind[array[i]].fitness > ind[array[i+1]].fitness){
temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
sorted=0;
}
}
} while (sorted==0);
for(int i=0;i<popsize;i++)
tmp[i]=ind[i];
for(int i=0;i<popsize;i++)
ind[i]=tmp[array[i]];
}
[/code]
It create an array for the ranking and then uses it to rearrange the
population according to fitness. Soo you dont get in a mess and
roullete needs it.
Here is the Glut interface with main:
[code]
#include <stdlib.h>
#include <stdio.h>
#ifndef WIN32
#include <unistd.h>
#else
#define random rand
#define srandom srand
#endif
#include <math.h>
#include <time.h>
#include <iostream>
#include <GL/glut.h>
#include "Scrappy_GA.cc"
/* Some <math.h> files do not define M_PI... */
#ifndef M_PI
#define M_PI 3.14159265
#endif
#ifndef M_PI_2
#define M_PI_2 1.57079632
#endif
using namespace std;
GLfloat funcpoints[200][200][3];
GLboolean moving = GL_FALSE;
//swarm myswarm(14,3);
ga myga(50,50,2); //50 individuals,12 bin, 300 wgts
double gsize=1; //Problem size
double hgt=1,scl=1,pscl=1; //Position
int res=10.0; //Resolution
int lowres=1;
double scrn = 50; //Screen size
#define MAX_PLANES 14
struct {
float speed; /* zero speed means not flying */
GLfloat red, green, blue;
float theta;
float x, y, z, angle;
} planes[MAX_PLANES];
#define v3f glVertex3f /* v3f was the short IRIS GL name for
glVertex3f */
#define v3d glVertex3d
void loadpoints(void){
double t0,t1,t2,x_,y_,sum=0;
for(int i=0;i<200;i++){
for(int j=0;j<200;j++){
x_ = ((double)i-100)/res;
y_ = ((double)j-100)/res;
if(lowres==1){
x_ = (int)x_;
y_ = (int)y_;
}
double pos[2];
pos[0] = x_;
pos[1] = y_;
if(myga.fun==1){
sum=pow(x_,4)-16*pow(x_,2)+5*x_; //Styblinski-Tang
sum+=pow(y_,4)-16*pow(y_,2)+5*y_;
}
if(myga.fun==0){
sum = pow(x_,2) + pow(y_,2);
}
funcpoints[i][j][0]=x_;
funcpoints[i][j][1]=y_;
funcpoints[i][j][2]=sum/gsize;
}
}
}
void drawlines2buffer(void){
glNewList(1,GL_COMPILE);
glPushMatrix ();
for(int i=0;i<200;i++){
for(int j=0;j<200;j++){
glBegin(GL_LINES);
glColor3f(0.0,1.0,1.0);
if(i<199){
v3d( funcpoints[i][j][0],funcpoints[i][j][1],funcpoints[i][j][2]);
v3d( funcpoints[i+1][j][0],funcpoints[i+1][j][1],funcpoints[i+1]
[j][2]);
}
glEnd();
glBegin(GL_LINES);
glColor3f(0.0,1.0,1.0);
if(j<199){
v3d( funcpoints[i][j][0],funcpoints[i][j][1],funcpoints[i][j][2]);
v3d( funcpoints[i][j+1][0]+0.1,funcpoints[i][j+1][1]
+0.1,funcpoints[i][j+1][2]+0.1);
}
glEnd();
}
}
glPopMatrix ();
glEndList();
}
void
print_bitmap_string(void* font, char* s)
{
if (s && strlen(s)) {
while (*s) {
glutBitmapCharacter(font, *s);
s++;
}
}
}
void
draw(void)
{
GLfloat red, green, blue;
int i,j;
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
/*Text output*/
double x = 15.0;
double y = -5.0;
double ystep = 100.0;
double yild = 20.0;
glColor3f(1.0, 1.0, 1.0);
char string[50];
double myfit=0;
if(myga.fun==0){myfit=1/myga.ind[49].fitness;}
if(myga.fun==1){myfit=-myga.ind[49].fitness/2;}
sprintf(string,"Global Best Solution = %f,%f,%f",myfit,myga.ind
[49].var[0],myga.ind[49].var[1]);
int len = strlen(string);
glRasterPos2f(x, y);
print_bitmap_string(GLUT_BITMAP_TIMES_ROMAN_10, string);
/* draw function in 3d */
glCallList(1);
/* paint planes */
glEnable(GL_DEPTH_TEST);
glShadeModel(GL_FLAT);
for (i = 0; i < MAX_PLANES; i++)
if (planes[i].speed != 0.0) {
glPushMatrix();
glTranslatef(planes[i].x, planes[i].y, planes[i].z);
//glScalef(1.0 / 5, 1.0 / 5, 1.0 / 5);
//glRotatef(290.0, 1.0, 0.0, 0.0);
glRotatef(planes[i].angle, 0.0, 0.0, 1.0);
glScalef(1.0 / 12.0, 1.0 / 16.0, 1.0 / 16.0);
glTranslatef(0.0, -4.0, -1.5);
if(1){
glBegin(GL_TRIANGLE_STRIP);
/* left wing */
v3f(-7.0, 0.0, 2.0);
v3f(-1.0, 0.0, 3.0);
glColor3f(red = planes[i].red, green = planes[i].green,
blue = planes[i].blue);
v3f(-1.0, 7.0, 3.0);
/* left side */
glColor3f(0.6 * red, 0.6 * green, 0.6 * blue);
v3f(0.0, 0.0, 0.0);
v3f(0.0, 8.0, 0.0);
/* right side */
v3f(1.0, 0.0, 3.0);
v3f(1.0, 7.0, 3.0);
/* final tip of right wing */
glColor3f(red, green, blue);
v3f(7.0, 0.0, 2.0);
glEnd();
}
//glColor3f(0, 1, 0);
//glutSolidSphere(7.0,50,50);
glPopMatrix();
}
glutSwapBuffers();
}
void reshape(int w, int h)
{
glViewport(0, 0, (GLsizei) w, (GLsizei) h);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
if (w <= h)
glOrtho(-scrn, scrn, -scrn*(GLfloat)h/(GLfloat)w,
scrn*(GLfloat)h/(GLfloat)w, -scrn, scrn);
else
glOrtho(-scrn*(GLfloat)w/(GLfloat)h,
scrn*(GLfloat)w/(GLfloat)h, -scrn, scrn, -scrn, scrn);
/* Rescale and resize Globally */
glScalef(scl*6.0 / 3.7, scl*6.0 / 3.7, scl*6.0 / 3.7);
glTranslatef(0.0,hgt,0.0);
glRotatef(310,1.0,0.0,0.0);
glRotatef(65,0.0,0.0,1.0);
glRotatef(5,0.0,1.0,0.0);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
}
void
tick_per_plane(int i)
{
//myswarm.mainloop(1);
myga.cycle();
float theta = planes[i].theta += planes[i].speed;
planes[i].z = myga.ind[i].fitness/gsize;
planes[i].x = myga.ind[i].var[0];
planes[i].y = myga.ind[i].var[1];
planes[i].angle = ((atan(2.0) + M_PI_2) * sin(theta) - M_PI_2) * 180
/ M_PI;
if (planes[i].speed < 0.0)
planes[i].angle += 180;
}
void
add_plane(void)
{
int i;
for (i = 0; i < MAX_PLANES; i++)
if (planes[i].speed == 0) {
#define SET_COLOR(r,g,b) \
planes[i].red=r; planes[i].green=g; planes[i].blue=b;
switch (random() % 6) {
case 0:
SET_COLOR(1.0, 0.0, 0.0); /* red */
break;
case 1:
SET_COLOR(1.0, 1.0, 1.0); /* white */
break;
case 2:
SET_COLOR(0.0, 1.0, 0.0); /* green */
break;
case 3:
SET_COLOR(1.0, 0.0, 1.0); /* magenta */
break;
case 4:
SET_COLOR(1.0, 1.0, 0.0); /* yellow */
break;
case 5:
SET_COLOR(0.0, 1.0, 1.0); /* cyan */
break;
}
planes[i].speed = ((float) (random() % 20)) * 0.001 + 0.02;
if (random() & 0x1)
planes[i].speed *= -1;
planes[i].theta = ((float) (random() % 257)) * 0.1111;
tick_per_plane(i);
if (!moving)
glutPostRedisplay();
return;
}
}
void
remove_plane(void)
{
int i;
for (i = MAX_PLANES - 1; i >= 0; i--)
if (planes[i].speed != 0) {
planes[i].speed = 0;
if (!moving)
glutPostRedisplay();
return;
}
}
void
tick(void)
{
int i;
for (i = 0; i < MAX_PLANES; i++)
if (planes[i].speed != 0.0)
tick_per_plane(i);
}
void
animate(void)
{
tick();
glutPostRedisplay();
}
void timer(int value){
/* Set the next timed callback */
glutTimerFunc ( 30, timer, 0 ) ;
drawlines2buffer();
glutPostRedisplay () ;
}
void
visible(int state)
{
if (state == GLUT_VISIBLE) {
if (moving)
glutIdleFunc(animate);
} else {
if (moving)
glutIdleFunc(NULL);
}
}
float horiz=0,vert=0,zoom=4.0;
/* ARGSUSED1 */
void
keyboard(unsigned char ch, int x, int y)
{
switch (ch) {
case 'l':
zoom+=1;
glScalef(1.0/zoom,1.0/zoom,1.0/zoom);
glutPostRedisplay();
break;
case 'k':
zoom-=1;
glScalef(1.0/zoom,1.0/zoom,1.0/zoom);
glutPostRedisplay();
break;
case ',':
vert++;
glRotatef(vert,0.0,1.0,0.0);
glutPostRedisplay();
break;
case '.':
vert++;
glRotatef(vert,1.0,0.0,0.0);
glutPostRedisplay();
break;
case '#':
horiz++;
glRotatef(horiz,0.0,1.0,0.0);
glutPostRedisplay();
break;
case '/':
horiz++;
glRotatef(horiz,1.0,0.0,0.0);
glutPostRedisplay();
break;
case ' ':
if (!moving) {
tick();
glutPostRedisplay();
}
break;
case 27: /* ESC */
exit(0);
break;
}
}
#define ADD_PLANE 1
#define REMOVE_PLANE 2
#define MOTION_ON 3
#define MOTION_OFF 4
#define QUIT 5
#define INCREASE_LRT 6
void
menu(int item)
{
switch (item) {
case ADD_PLANE:
add_plane();
break;
case REMOVE_PLANE:
remove_plane();
break;
case MOTION_ON:
moving = GL_TRUE;
glutChangeToMenuEntry(3, "Motion off", MOTION_OFF);
glutIdleFunc(animate);
break;
case MOTION_OFF:
moving = GL_FALSE;
glutChangeToMenuEntry(3, "Motion", MOTION_ON);
glutIdleFunc(NULL);
break;
case INCREASE_LRT:
myga.cross+=0.1;
break;
case QUIT:
exit(0);
break;
}
}
int
main(int argc, char *argv[])
{
hgt = -4.5;scl =3;pscl=1;gsize = 200;
res = 10;lowres=1;scrn=75;
myga.cross=0.7;
myga.mut=0.001;
myga.fun=1; //Which test function
glutInit(&argc, argv);
/* use multisampling if available */
glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH |
GLUT_MULTISAMPLE);
glutCreateWindow("glutplane");
loadpoints();
drawlines2buffer();
glutDisplayFunc(draw);
glutReshapeFunc(reshape);
//glutTimerFunc(30, timer, 0 );
glutKeyboardFunc(keyboard);
//glutVisibilityFunc(visible);
glutCreateMenu(menu);
glutAddMenuEntry("Add plane", ADD_PLANE);
glutAddMenuEntry("Remove plane", REMOVE_PLANE);
glutAddMenuEntry("Motion", MOTION_ON);
glutAddMenuEntry("Inc Lrt", INCREASE_LRT);
glutAddMenuEntry("Quit", QUIT);
glutAttachMenu(GLUT_RIGHT_BUTTON);
/* setup OpenGL state */
glClearDepth(1.0);
glClearColor(0.0, 0.0, 0.0, 0.0);
glMatrixMode(GL_PROJECTION);
glFrustum(-1.0, 1.0, -1.0, 1.0, 1.0, 20);
glMatrixMode(GL_MODELVIEW);
/* add three initial random planes */
srandom(time(NULL));
for(int i=0;i<14;i++){
add_plane(); }
/* start event processing */
glutMainLoop();
return 0; /* ANSI C requires main to return int. */
}
[/code]
Compile with :
g++ -o glutsga glutsga.cc -lglu32 -lopengl32 -lfreeglut
(NB you have to fiddle with the gsize variable to rescale the problems
to fit on the screen e.g fun=0 requires gscale=2 , fun=1 gscale=200)