# Steiner Genetic Algorithm - C++ Code

Here follows the guts of my new C++ program for solving Steiner Tree problems with a Genetic Algorithm.

I have eliminated much of the Microsoft Foundation Class support code, focusing mainly on the number-crunching routines. I will be happy to share the complete code with interested parties.

The original FORTRAN version from five years ago is still online at NMSR.

You’ll see that I’ve cleaned up and organized everything quite a bit, and completely re-done the snippet which checks for properly connected solutions.

Dave August 21st, 2006

// SteinerGADlg.cpp : implementation file

#include "stdafx.h"
#include "SteinerGA.h"
#include "Prefs.h"
#include "Geometry.h"
#include "StartDisplay.h"
#include <string.h>
#include <ctype.h>
#include <math.h>

{
m_pixel_rpt = _T("");
m_status = _T("");
m_target = FALSE;
m_drawon = FALSE;
m_statusrpt = _T("");
//} }AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
}

{
if (pRedPen != NULL)
delete 	pRedPen;
if (pBigRedPen != NULL)
delete 	pBigRedPen;
if (pGreenPen != NULL)
delete 	pGreenPen;
if (pBigGreenPen != NULL)
delete 	pBigGreenPen;
if (pBluePen != NULL)
delete 	pBluePen;
if (pBigBluePen != NULL)
delete 	pBigBluePen;
if (pBlackPen != NULL)
delete 	pBlackPen;
if (pBigBlackPen != NULL)
delete 	pBigBlackPen;
if (pWhitePen != NULL)
delete 	pWhitePen;
if (pBigWhitePen != NULL)
delete 	pBigWhitePen;

Cleanup();

}

{
m_npts = m_fixdnodes + m_varbnodes;
m_combs = m_npts*(m_npts-1)/2; // nC2, n things 2 at a time....
m_ndigs = m_varbnodes*3*2; // how many digits are in coord-map...
m_ntot = 2 + m_ndigs + m_combs;

m_xFixd = new double[m_fixdnodes]; // need for other stuff, like geo-entry, before Run.
m_yFixd = new double[m_fixdnodes];
m_xVarb = new double[m_varbnodes];
m_yVarb = new double[m_varbnodes];

m_conmap = new bool[m_combs];
m_got = new bool[m_npts];
m_fitness = new double[m_maxpop];
m_sortids = new int[m_maxpop];

int a;
for (a=0; a<m_fixdnodes; a++)
m_xFixd[a] = m_yFixd[a] = 0.0;
for (a=0; a<m_varbnodes; a++)
m_xVarb[a] = m_yVarb[a] = 0.0;
for (a=0; a<m_combs; a++)
m_conmap[a] = FALSE;
for (a=0; a<m_npts; a++)
m_got[a] = FALSE;
for (a=0; a<m_maxpop; a++)
{
m_fitness[a] = m_death;
m_sortids[a] = -1;
}
}

{
if (m_xFixd != NULL)// data arrays
delete [] m_xFixd;
if (m_yFixd != NULL)// data arrays
delete [] m_yFixd;
if (m_xVarb != NULL)// data arrays
delete [] m_xVarb;
if (m_yVarb != NULL)// data arrays
delete [] m_yVarb;

if (m_conmap != NULL)// data arrays
delete [] m_conmap;
if (m_got != NULL)// data arrays
delete [] m_got;
if (m_fitness != NULL)// data arrays
delete [] m_fitness;
if (m_sortids != NULL)// data arrays
delete [] m_sortids;

m_xFixd = NULL; // need for other stuff, like geo-entry, before Run.
m_yFixd = NULL;
m_xVarb = NULL;
m_yVarb = NULL;

m_conmap = NULL;
m_got = NULL;
m_fitness = NULL;
m_sortids = NULL;
}

/////////////////////////////////////////////////////////////////////////////

{
CDialog::OnInitDialog();

// IDM_ABOUTBOX must be in the system command range.

{
{
}
}

// Set the icon for this dialog.  The framework does this automatically
//  when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE);			// Set big icon
SetIcon(m_hIcon, FALSE);		// Set small icon

// TODO: Add extra initialization here
pRedPen = new CPen(PS_SOLID,1,RGB(255,0,0));
pBigRedPen = new CPen(PS_SOLID,2,RGB(255,0,0));

pGreenPen = new CPen(PS_SOLID,1,RGB(0,255,0));
pBigGreenPen = new CPen(PS_SOLID,2,RGB(0,255,0));

pBluePen = new CPen(PS_SOLID,1,RGB(0,0,255));
pBigBluePen = new CPen(PS_SOLID,2,RGB(0,0,255));

pBlackPen = new CPen(PS_SOLID,1,RGB(0,0,0));
pBigBlackPen = new CPen(PS_SOLID,2,RGB(0,0,0));

pWhitePen = new CPen(PS_SOLID,1,RGB(255,255,255));
pBigWhitePen = new CPen(PS_SOLID,2,RGB(255,255,255));

m_maxgens = 5000;
m_killgens = 1000;
m_maxpop = 1000;

m_death = 100000.0;
m_mutespergen = 50;
m_mutesperorg = 3;
m_bfactor = 1.5;

m_delay = 1; // milliseconds
m_rows = 1; // rows of displayed organisms
m_cols = 1; // cols of displayed organisms
m_elite = 10; // this number kept as-is after Fitness

m_xFixd = NULL; // need for other stuff, like geo-entry, before Run.
m_yFixd = NULL;
m_xVarb = NULL;
m_yVarb = NULL;

m_conmap = NULL;
m_got = NULL;
m_fitness = NULL;
m_sortids = NULL;

m_fixdnodes = 5;
m_varbnodes = 4;

Allocate();

m_xFixd[0] = 350.0;
m_yFixd[0] = 300.0;

m_xFixd[1] = 650.0;
m_yFixd[1] = 300.0;

m_xFixd[2] = 200.0;
m_yFixd[2] = 560.0;

m_xFixd[3] = 800.0;
m_yFixd[3] = 560.0;

m_xFixd[4] = 500.0;
m_yFixd[4] = 733.3;

m_dxmin = 0.0; // DATA limits (user-def'd)
m_dxmax = 1500.0;
m_dymin = 0.0;
m_dymax = 1500.0;

m_xmin = 20; // plot box mins & maxes
m_xmax = 460; // 640;
m_ymin = 20;
m_ymax = 460;

m_running = FALSE;
m_drawon = TRUE;
m_target = FALSE; // for special Fitness test, proximity to given DNA
m_digitizing = FALSE;

UpdateData(FALSE);

// TODO: Add extra initialization here
srand( (unsigned)time( NULL ) ); // random seed
// srand(0); // use for same result every time!!

IMAGE_BITMAP,56,44,LR_DEFAULTCOLOR);

CWnd* pWnd = GetDlgItem(IDC_TARGBMP);
pWnd->PostMessage(BM_SETIMAGE,IMAGE_BITMAP,(long)hBMP);

DrawFixdPoints();

return TRUE;  // return TRUE  unless you set the focus to a control
}

void CSteinerGADlg::Data2Pixel(double xval, double yval, int* x, int* y) // loc to (x,y)
{// scale plot point to m_dxmin, m_dxmax, m_dymin, m_dymax
// m_xmin, m_xmax, m_ymin, m_ymax
double xtemp, ytemp;

xtemp = (double)m_xmin + (double)(m_xmax-m_xmin)*(xval-m_dxmin)/(m_dxmax-m_dxmin);
ytemp = (double)m_ymax + (double)(m_ymin-m_ymax)*(yval-m_dymin)/(m_dymax-m_dymin);

*x = (int)xtemp;
*y = (int)ytemp;
return;
}

void CSteinerGADlg::Pixel2Data(int x, int y, double* xval, double* yval) // (x,y) to Data
{// scale plot point to m_dxmin, m_dxmax, m_dymin, m_dymax
// m_xmin, m_xmax, m_ymin, m_ymax
double xtemp, ytemp;

xtemp = m_dxmin + (double)(x-m_xmin)*(m_dxmax-m_dxmin)/(double)(m_xmax-m_xmin);
ytemp = m_dymin + (double)(y-m_ymax)*(m_dymax-m_dymin)/(m_ymin-m_ymax);

*xval = xtemp;
*yval = ytemp;
return;
}

{
CPoint pt(lParam);
double xt, yt;

if (m_box.PtInRect(pt))
{
Pixel2Data(pt.x, pt.y, &xt, &yt);
xt = (double)((int)xt); // round-off
yt = (double)((int)yt); // round-off
m_pixel_rpt.Format("%d,%d (pix)\n%.0lf,%.0lf (pos)",pt.x, pt.y, xt, yt);
}
else
{
}
UpdateData(FALSE);
}

{
CPrefs dlg;
dlg.m_fixdnodes = m_fixdnodes;
dlg.m_maxgens = m_maxgens;
dlg.m_maxpop = m_maxpop;
dlg.m_varbnodes = m_varbnodes;
dlg.m_death = m_death;
dlg.m_mutespergen = m_mutespergen;
dlg.m_mutesperorg = m_mutesperorg;
dlg.m_bfactor = m_bfactor;
dlg.m_delay = m_delay; // milliseconds
dlg.m_rows = m_rows; // rows of displayed organisms
dlg.m_cols = m_cols; // cols of displayed organisms
dlg.m_elite = m_elite; // this number kept as-is after Fitness
dlg.m_killgens = m_killgens;

int ret = dlg.DoModal();

if (ret == IDOK)
{
if (m_fixdnodes != dlg.m_fixdnodes || m_varbnodes != dlg.m_varbnodes || m_maxpop != dlg.m_maxpop) // need to re-allocate arrays!
{
m_fixdnodes = dlg.m_fixdnodes;
m_varbnodes = dlg.m_varbnodes;
m_maxpop = dlg.m_maxpop;
Cleanup();
Allocate();
}

m_maxgens = dlg.m_maxgens;
m_death = dlg.m_death;
m_mutespergen = dlg.m_mutespergen;
m_mutesperorg = dlg.m_mutesperorg;
m_bfactor = dlg.m_bfactor;
m_delay = dlg.m_delay; // milliseconds
m_rows = dlg.m_rows; // rows of displayed organisms
m_cols = dlg.m_cols; // cols of displayed organisms
m_elite = dlg.m_elite; // this number kept as-is after Fitness
m_killgens = dlg.m_killgens;

m_dxmin = 0.0; // DATA limits (user-def'd)
m_dxmax = 1000.0*(double)m_cols;
m_dymin = 0.0;
m_dymax = 1000.0*(double)m_rows;
}

CString str;
m_status.Format("Parameters Assigned.");
UpdateData(FALSE);

DrawFixdPoints();
}

{
m_pop.RemoveAll();
CString critter;
int a;

for (a=0; a<m_maxpop; a++) // for each organism...
{
critter = CreateOne();
}
m_statusrpt.Format("Pop Created");
UpdateData(FALSE);
}

{
CString critter, temp, str, dbg;
int b, num;
double x;

critter.Empty();
// 1st, # nodes
x = (double)rand() / (double)RAND_MAX;

num = (int)((double)m_varbnodes*x);

num = m_varbnodes; // over-ride!!!

if (num < 10)
temp.Format("0%1d", num);
else
temp.Format("%2d", num);
critter += temp;

// 2nd, the variable node coordinates
for (b=0; b<m_varbnodes*3*2; b++) // for each digit (3 digits*#varbnodes total)...
{
x = (double)rand() / (double)RAND_MAX;
num = (int)(10.0*x); // 0-9
temp.Format("%1d", num);
critter += temp;
}

// 3rd, the connection map
for (b=0; b<m_combs; b++) // for each digit (3 digits*#varbnodes)...
{
x = (double)rand() / (double)RAND_MAX;
temp = (x > 0.5) ? "T" : "F" ; // 50/50 @ >0.5
critter += temp;
}
return (critter);
}

void CSteinerGADlg::OnTest() // implement simple Random Search
{
CString critter, bestCritter;
double fitness, bestLength = m_death;
int a, bestGen;

bestGen = 0;
for (a=0; a<10000000; a++)
{
critter = CreateOne();

fitness = Fitness(critter);
if (fitness < bestLength)
{
bestLength = fitness;
bestCritter = critter;
bestGen = a;
drawOne(bestCritter,bestGen,0);
}
if (a%1000 == 0)
{
m_statusrpt.Format("Random Search # %d", a);
UpdateData(FALSE);
}
}
return;
}

{
// need to fill data arrays m_xVarb and m_yVarb (double);
int a, nnode, pos; // b,
double num;
bool temp;
CString str;

str = critter.Mid(0,2); // 1st 2 digits
nnode = String2Integer(str);

for (a=0; a<nnode; a++) // for each varb. node...
{
pos = 2+a*6;
str = critter.Mid(pos,3); // x coord
num = String2Double(str);
m_xVarb[a] = (double)num;
str = critter.Mid(pos+3,3); // y coord
num = String2Double(str);
m_yVarb[a] = num;
}

for (a=0; a<m_combs; a++) // for each bit of the connections bitmap...
{
pos = 2 + m_ndigs + a;

str = critter.Mid(pos,1); // a T or F bit
temp = (str == "T") ? TRUE : FALSE ;
m_conmap[a] = temp;
}
return(nnode);
}

{
int num;
num = atoi(str);
return(num);
}

{
double num;
num = (double)atoi(str);
return(num);
}

{
m_nextra = Transcribe(critter); // number of variable (Steiner) points

int a,b,i,numseg;
double x1, y1, x2, y2, dx, dy, dr, sum;

if (!Connected())
return(m_death);

numseg = 0;
sum = 0.0;
for (a=0; a<m_npts-1; a++)
{
if (a < m_fixdnodes)
{
x1 = m_xFixd[a];
y1 = m_yFixd[a];
}
else
{
x1 = m_xVarb[a-m_fixdnodes];
y1 = m_yVarb[a-m_fixdnodes];
}
for (b=a+1; b<m_fixdnodes + m_nextra; b++)
{
i = ConMapIndex(a,b);
if (b < m_fixdnodes)
{
x2 = m_xFixd[b];
y2 = m_yFixd[b];
}
else
{
x2 = m_xVarb[b-m_fixdnodes];
y2 = m_yVarb[b-m_fixdnodes];
}
if (m_conmap[i]) // connection is enabled...
{
dx = x2 - x1;
dy = y2 - y1;
dr = sqrt(dx*dx + dy*dy);
sum += dr;
}
}
}

if (m_target) // over-ride fitness test with specified target (= The Kluge)!
sum = Fitness2(critter);

return(sum);
}

double CSteinerGADlg::Fitness2(CString critter) // specific target
{
int a;
double sum = 0.0;
CString ch1, ch2;
// note the following target DNAs are for fixd=5, varb=4
CString target;
// target = "04391498500562650475349474FFFFFFFTFFFFFTFFFFFFTFFFTFFTFFFFFTTF";// the Steiner
target = "04614580132412507588758509TFFTFTFFTFFTFFTFFFFTFFFFFTTFFFFTTFFF"; // the Kluge
for (a=0; a<critter.GetLength(); a++)
{
ch1 = critter.Mid(a,1);
ch2 = target.Mid(a,1);
if (ch1 != ch2) // if character from organism is different from same character in Target, add 1 to distance
sum += 1.0;
}
return (sum);
}

{
int a,b,r;
int npoints = m_fixdnodes + m_nextra; // activated nodes

// general init
for (a=0; a<m_npts; a++)
{
m_got[a] = FALSE;
}

// init point the First
m_got[0] = TRUE;

for (r=0; r<2; r++) // do once, then repeat to catch connections from on high
{
// 1st loop go up....
for (a=0; a<npoints-1; a++)
{
for (b=a+1; b<npoints; b++)
{
if (m_conmap[ConMapIndex(a,b)] && (m_got[a] || m_got[b]))
{
m_got[a] = m_got[b] = TRUE;
}
}
}
// 2nd loop go down....
for (b=npoints-1; b>0; b--)
{
for (a=b-1; a>-1; a--) // note keeping b>a still...
{
if (m_conmap[ConMapIndex(a,b)] && (m_got[a] || m_got[b]))
{
m_got[a] = m_got[b] = TRUE;
}
}
}
}
// now check fixed nodes for connects...
for (a=0; a<m_fixdnodes; a++)
{
if (!m_got[a])
{
return(FALSE);
}
}

return(TRUE);
}

int CSteinerGADlg::ConMapIndex(int a, int b) // returns index into bitmap for pt.a to pt.b
{
int ans = -1 + a*(2*m_npts - a - 3)/2 + b;
return(ans);
}

void CSteinerGADlg::drawOne(CString critter, int gen, int pop)
{
int a, b, i;
double x1,y1,x2,y2;
int xi1,yi1,xi2,yi2;
CString str, str2;

double fitness = Fitness(critter);

CWnd* pWnd = GetDlgItem(IDC_DRAWRING);
CDC* pDC = pWnd->GetDC();

CBrush Brush(RGB(255,255,255)); // white!
CRect bx = m_box;
pDC->FillRect(&bx, &Brush);

// display DNA & fitness
str = critter.Mid(0,2);
str += " ";
for (a=0; a<m_varbnodes; a++)
{
b = 2+a*6;
str2.Format(" (%s,%s)", critter.Mid(b,3), critter.Mid(b+3,3));
str += str2;
}
pDC->TextOut(25,25,str);
str = critter.Mid(2+m_ndigs, m_combs);
pDC->TextOut(25,45,str);
str.Format("%.1lf",fitness);
if (gen > -1 && pop > -1)
str.Format("Gen%d, Org%d, F=%.1lf",gen, pop, fitness);
pDC->TextOut(25,65, str);

// draw fixed points...
pDC->SelectObject(pBluePen);
pDC->SetTextColor(RGB(0,0,255)); // BLUE

for (a=0; a<m_fixdnodes; a++)
{
x1 = m_xFixd[a];
y1 = m_yFixd[a];

Data2Pixel(x1, y1, &xi1, &yi1);

pDC->Ellipse(xi1-3,yi1-3,xi1+3,yi1+3);

str.Format("%d",a+1);
pDC->TextOut(xi1,yi1,str);
}

// draw variable points...
pDC->SetTextColor(RGB(0,255,0)); // GREEN
pDC->SelectObject(pGreenPen);
for (a=0; a<m_nextra; a++)
{
x1 = m_xVarb[a];
y1 = m_yVarb[a];

Data2Pixel(x1, y1, &xi1, &yi1);

pDC->Ellipse(xi1-3,yi1-3,xi1+3,yi1+3);

str.Format("%d",m_fixdnodes+a+1);
pDC->TextOut(xi1,yi1,str);
}

// draw valid connections...
pDC->SetTextColor(RGB(255,0,0)); // RED
pDC->SelectObject(pRedPen);
for (a=0; a<m_npts-1; a++)
{
if (a < m_fixdnodes)
{
x1 = m_xFixd[a];
y1 = m_yFixd[a];
}
else
{
x1 = m_xVarb[a-m_fixdnodes];
y1 = m_yVarb[a-m_fixdnodes];
}

Data2Pixel(x1, y1, &xi1, &yi1);

for (b=a+1; b<m_fixdnodes + m_nextra; b++)
{
i = ConMapIndex(a,b);
if (b < m_fixdnodes)
{
x2 = m_xFixd[b];
y2 = m_yFixd[b];
}
else
{
x2 = m_xVarb[b-m_fixdnodes];
y2 = m_yVarb[b-m_fixdnodes];
}

Data2Pixel(x2, y2, &xi2, &yi2);

if (m_conmap[i]) // connection is enabled...
{
pDC->MoveTo(xi1, yi1);
pDC->LineTo(xi2, yi2);
}
}
}
}

{
int a;
double x,y;
int xi,yi;
CString str;

CWnd* pWnd = GetDlgItem(IDC_DRAWRING);
CDC* pDC = pWnd->GetDC();

CBrush Brush(RGB(255,255,255)); // white!
CRect bx = m_box;
pDC->FillRect(&bx, &Brush);

// draw fixed points...
pDC->SelectObject(pBluePen);
pDC->SetTextColor(RGB(0,0,255)); // BLUE

for (a=0; a<m_fixdnodes; a++)
{
x = m_xFixd[a];
y = m_yFixd[a];

Data2Pixel(x, y, &xi, &yi);

pDC->Ellipse(xi-3,yi-3,xi+3,yi+3);

str.Format("%d",a+1);
pDC->TextOut(xi,yi,str);
}
}

{
int num, pos, a; // a = dbg only
double x, y, z;
CString temp, orig, chr;
CString dbg, str, changes; // for debug only
TCHAR onechar;

orig = critter;

str.Format("-");
for (a=0; a<m_ntot; a++)
{
changes += str;
}
x = (double)rand() / (double)RAND_MAX; // uniform random
if (x < 0.0001) // mutate nodes area - Rare...
{
y = (double)rand() / (double)RAND_MAX; // uniform random
num = (int)((double)(m_varbnodes+1)*y);
if (num < 0 || num > m_varbnodes)
{
num = m_varbnodes;
}
if (num < 10)
{
temp.Format("0");
strcpy(&onechar,temp);
critter.SetAt(0,onechar);
temp.Format("%d", num);
strcpy(&onechar,temp);
critter.SetAt(1,onechar);
changes.SetAt(1,onechar);
}
else
{
temp.Format("%2d", num);
strcpy(&onechar,temp);
critter.SetAt(0,onechar);
changes.SetAt(0,onechar);
}
}
else if (x < 0.5) // mutate coordinates area
{
y = (double)rand() / (double)RAND_MAX;
pos = 2 + (int)((double)(m_ndigs)*y); // position along string
if (pos < 0 || pos > m_ntot-1) // error
{
pos = 2;
}
z = (double)rand() / (double)RAND_MAX;
num = (int)(10.0*z); // digit 0-9
temp.Format("%d", num);
strcpy(&onechar,temp);
critter.SetAt(pos,onechar);
changes.SetAt(pos,onechar);
}
else // mutate connection bitmap area
{
y = (double)rand() / (double)RAND_MAX;
pos = 2 + m_ndigs + (int)((double)(m_combs)*y); // position along string
if (pos < 0 || pos > m_ntot-1) // error
{
pos = m_ndigs + 2;
}

chr = critter.Mid(pos,1);
temp = (chr == "F") ? "T" : "F" ; // strict inversion here...
strcpy(&onechar,temp);
critter.SetAt(pos,onechar);
changes.SetAt(pos,onechar);
}

return(critter);
}

{
int a,b,ilarge,itemp;
double ftemp;

for (a=0; a<m_maxpop-1; a++) // sort the peaks by increasing fitness (so smallest first)
{
ilarge = a;
for (b=a+1; b<m_maxpop; b++)
{
if (m_fitness[b] < m_fitness[ilarge])
ilarge = b;
}
if (ilarge > a)
{
itemp = m_sortids[a];
m_sortids[a] = m_sortids[ilarge];
m_sortids[ilarge] = itemp;

ftemp = m_fitness[a];
m_fitness[a] = m_fitness[ilarge];
m_fitness[ilarge] = ftemp;
}
}
}

{
CString str, critter;
int iorg;
double fitness, sum;
double npop = (double)m_maxpop;
m_popnorm = 0.0;
m_minlgth = 2.0*m_death;
m_maxlgth = 0.0;
sum = 0.0;
for (iorg=0; iorg<m_maxpop; iorg++) // for each organism, calculate its fitness......
{
fitness = m_fitness[m_sortids[iorg]];
if (fitness < m_death)
{
sum += fitness;
if (fitness > m_maxlgth)
{
m_maxlgth = fitness;
}
}
if (fitness < m_minlgth)
m_minlgth = fitness;
}
if (m_maxlgth > m_minlgth)
m_popnorm = (npop*m_maxlgth - sum)/(m_maxlgth - m_minlgth);

return;
}

int CSteinerGADlg::heybabe(void) // selects a population member for Mating ;-)
{
double x, y, z;
double partsum = 0.0;
int iorg = -1;
int a;

x = (double)rand() / (double)RAND_MAX; // x = uniform Rand()

// normal way follows
y = pow(x, m_bfactor)*m_popnorm; // so y = x^m_bfactor, *= m_popnorm

for (a=m_maxpop-1; a>-1; a--) // start at least fit, go down to best fit...
{
if (m_fitness[a] < m_death)
{
z = (m_maxlgth - m_fitness[a])/(m_maxlgth - m_minlgth);
partsum += z;
if (partsum >= y)
{
iorg = a;
return(iorg);
}
}
}

// error - still here?  oh well, return best(0)...
return(0);
}

void CSteinerGADlg::crossover(int boy, int girl, CString* son, CString* daughter)
{
CString strBoy, strGirl, partial1, partial2, baby1, baby2, dbg;
strBoy = m_pop.GetAt(m_sortids[boy]);
strGirl = m_pop.GetAt(m_sortids[girl]);
double x;
int num;

x = (double)rand() / (double)RAND_MAX;
num = (int)((double)m_ntot*x); // pick x-over point

partial1 = strBoy.Mid(0,num); // 1st chunk Boy...
partial2 = strGirl.Mid(num, m_ntot-num); // last chunk Girl...
baby1 = partial1 + partial2;

*son = baby1;

partial1 = strGirl.Mid(0,num); // 1st chunk Girl...
partial2 = strBoy.Mid(num, m_ntot-num); // last chunk Boy...
baby2 = partial1 + partial2;

*daughter = baby2;

return;
}

{
m_target = !m_target;
if (m_target)
{
AfxMessageBox("Switching to Specific Target (Kluge)");
m_fixdnodes = 5;
m_varbnodes = 4;

Cleanup();
Allocate();

m_xFixd[0] = 350.0;
m_yFixd[0] = 300.0;

m_xFixd[1] = 650.0;
m_yFixd[1] = 300.0;

m_xFixd[2] = 200.0;
m_yFixd[2] = 560.0;

m_xFixd[3] = 800.0;
m_yFixd[3] = 560.0;

m_xFixd[4] = 500.0;
m_yFixd[4] = 733.3;

}
UpdateData(FALSE);
}

void CSteinerGADlg::OnTargbmp() // response when you click the Target bitmap button
{
OnCheckTarget();
}

{
UpdateData(TRUE);

CString str, critter, dbg;
int a;

str.Format("Parms: Nodes(fixd=%d,varb=%d), Gens(kill=%d,max=%d), Muts(%d/gen,%d/org) Pop=%d, B=%.3lf, Elite:%d",
m_fixdnodes, m_varbnodes, m_killgens, m_maxgens, m_mutespergen, m_mutesperorg, m_maxpop,
m_bfactor, m_elite);
m_status = str;
UpdateData(FALSE);

// check for geom definition
bool OK = FALSE;
for (a=0; a<m_fixdnodes; a++) // if all coords 0, is FALSE, no-go (not OK)
{
if (m_xFixd[a] != 0.0 || m_yFixd[a] != 0.0)
OK = TRUE;
}

if(!OK)
{
AfxMessageBox("You need to Define a Geometry first!  Click Geometry.");
return;
}

for (a=0; a<m_combs; a++)
{
m_conmap[a] = FALSE;
}
for (a=0; a<m_npts; a++)
{
m_got[a] = FALSE;
}

m_running = TRUE;
CWnd* ownbut = GetDlgItem(IDC_DRAWRING);
GotoDlgCtrl(ownbut);

Create();

m_currentgen = 0;

DoOneGen(m_currentgen);
}

{
// part of allowing Windows Messages to interrupt a long simulation...
if (m_currentgen < m_maxgens && m_running)
DoOneGen(m_currentgen);
return(0L);
}

{
if (m_running)
DoOnePlot();
return(0L);
}

void CSteinerGADlg::DoOnePlot(void) // for run control
{
UpdateWindow();
m_statusrpt.Format("Gen#%d", m_currentgen);
UpdateData(FALSE);

if (!m_running)	// Esc, Q, X = eXit
{
AfxMessageBox("Plot History Display terminated by user.");
return;
}

drawOne(m_critter, m_currentgen, 0);
::Sleep(m_delay);

PlotAbort();

this->PostMessage(IDM_PLOTGEN,0,0);
return;
}

void CSteinerGADlg::PlotAbort(void) // for run control
{
// abort control
MSG				m_peekmsg;

while (::PeekMessage(&m_peekmsg,NULL,WM_KEYFIRST,WM_KEYLAST,PM_REMOVE))
{
if (m_peekmsg.message == WM_KEYDOWN)
{
if (m_peekmsg.wParam == 0x1B)	// ESC
m_running = FALSE;
else if (m_peekmsg.wParam == 0x58)	// X = eXit
m_running = FALSE;
else if (m_peekmsg.wParam == 0x51)	// Q = Quit
m_running = FALSE;
}
}
}

void CSteinerGADlg::DoOneGen(int igen) // for run control
{
CString str, critter, son, daughter, dbg;
double x;
int iorg, imutpop, imutorg, boy, girl, count;

UpdateWindow();
m_statusrpt.Format("Gen#%d", igen);
UpdateData(FALSE);

if (!m_running)	// Esc, Q, X = eXit
{
AfxMessageBox("Run terminated by user.");
return;
}

dbg.Format("************* Starting Generation %d *************", igen);
//TalkToMe(dbg,1);

if (igen%m_killgens == 0) // kill population, start over...
{
Create();
}

// a star goes Nova; excess radiation causes some mutations...

for (imutpop=0; imutpop<m_mutespergen; imutpop++)
{
x = (double)rand() / (double)RAND_MAX; // uniform Rand()
iorg = (int)((double)m_maxpop*x); // so now a typical organism ID#...

critter = m_pop.GetAt(iorg);

for (imutorg=0; imutorg<m_mutesperorg; imutorg++)
{
critter = Mutate(critter);
}

m_pop.SetAt(iorg,critter); // this puts mutated organism back into population
}

for (iorg=0; iorg<m_maxpop; iorg++) // for each organism, calculate its fitness......
{
critter = m_pop.GetAt(iorg);
m_fitness[iorg] = Fitness(critter);
m_sortids[iorg] = iorg;
}

// sort the critters
SortOrgs();

// plot TOP ORGANISM(s)
if (m_drawon)
{
for (iorg=0; iorg<1; iorg++) // for several organisms (only TOP here), get fitness
{
critter = m_pop.GetAt(m_sortids[iorg]);
drawOne(critter, igen, iorg);
::Sleep(m_delay);
}
}

iorg = 0; // best
critter = m_pop.GetAt(m_sortids[iorg]);

// build the next generation as CStringArray m_temp, then replace current array(m_pop)

m_temp.RemoveAll();

// place the Elites;
for (iorg=0; iorg<m_elite; iorg++) //
{
critter = m_pop.GetAt(m_sortids[iorg]);
}

// do breeding for next generation...

// get norms
GetNorms();

count = m_elite;
for (iorg=m_elite; iorg<m_maxpop; iorg++) // now the remaining population...
{
boy = heybabe();
girl = heybabe();
crossover(boy, girl, &son, &daughter);
}

m_pop.RemoveAll();
for (iorg=0; iorg<m_temp.GetSize(); iorg++)
{
critter = m_temp.GetAt(iorg);
}

TrapAbort();
m_currentgen++;

this->PostMessage(IDM_GENERATION,0,0);
return;
}

{
// abort control
MSG				m_peekmsg;
CString critter;

while (::PeekMessage(&m_peekmsg,NULL,WM_KEYFIRST,WM_KEYLAST,PM_REMOVE))
{
if (m_peekmsg.message == WM_KEYDOWN)
{
if (m_peekmsg.wParam == 0x1B)	// ESC
m_running = FALSE;
else if (m_peekmsg.wParam == 0x58)	// X = eXit
m_running = FALSE;
else if (m_peekmsg.wParam == 0x51)	// Q = Quit
m_running = FALSE;
}
}

if (!m_running)
{
AfxMessageBox("Run has been Terminated by user.");
critter = m_pop.GetAt(0);
drawOne(critter, m_currentgen, 0);
}
}