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 "SteinerGADlg.h"
#include "Prefs.h"
#include "Geometry.h"
#include "StartDisplay.h"
#include
#include
#include
// CSteinerGADlg dialog
CSteinerGADlg::CSteinerGADlg(CWnd* pParent /*=NULL*/)
: CDialog(CSteinerGADlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CSteinerGADlg)
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
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
CSteinerGADlg::~CSteinerGADlg(void) // destructor
{
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();
}
void CSteinerGADlg::Allocate(void)
{
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; aAppendMenu(MF_SEPARATOR);
pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
}
}
// 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!!
HBITMAP hBMP = (HBITMAP)::LoadImage(AfxGetApp()->m_hInstance,MAKEINTRESOURCE(IDB_TARGET),
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;
}
void CSteinerGADlg::Report(LPARAM lParam)
{
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
{
m_pixel_rpt.Format("Ready"); // .Empty();
::SetCursor(AfxGetApp()->LoadStandardCursor(IDC_ARROW));
}
UpdateData(FALSE);
}
void CSteinerGADlg::OnGetPrefs()
{
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();
}
void CSteinerGADlg::Create(void)
{
m_pop.RemoveAll();
CString critter;
int a;
for (a=0; a 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;
}
int CSteinerGADlg::Transcribe(CString critter)
{
// 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; a0; 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; aGetDC();
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; aTextOut(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; aEllipse(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; aEllipse(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; aMoveTo(xi1, yi1);
pDC->LineTo(xi2, yi2);
}
}
}
}
void CSteinerGADlg::DrawFixdPoints(void)
{
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; aEllipse(xi-3,yi-3,xi+3,yi+3);
str.Format("%d",a+1);
pDC->TextOut(xi,yi,str);
}
}
CString CSteinerGADlg::Mutate(CString critter) // mutation
{
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_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);
}
void CSteinerGADlg::SortOrgs(void)
{
int a,b,ilarge,itemp;
double ftemp;
for (a=0; a 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;
}
}
}
void CSteinerGADlg::GetNorms(void)
{
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_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;
}
void CSteinerGADlg::OnCheckTarget()
{
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();
}
void CSteinerGADlg::OnStartrun(void)
{
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; aPostMessage(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; imutpopPostMessage(IDM_GENERATION,0,0);
return;
}
void CSteinerGADlg::TrapAbort(void)
{
// 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);
}
}
No comments were recorded for this post.