Click here to Skip to main content
15,860,943 members
Articles / Desktop Programming / MFC
Article

Genetic Algorithms and the Traveling Salesman Problem using C# and ATL COM

Rate me:
Please Sign up or sign in to vote.
4.17/5 (8 votes)
24 Nov 20023 min read 140.5K   7.5K   42   18
An article on Travelling SalesMen Problem Solving by GA

Sample Image

Introduction

This project is about an application used by the Traveling Salesman, given a finite number of 'cities'(I have choosen cities from 1 to a finite number) along with the distance of travel (distance between two cities is randomly choosen) between each pair of them, The aim is to find the cheapest distance of visiting all the cities and returning to the starting point. Using GA we can get an optimal solution to solve this problem.

This is only an example to look at calling COM Components and accessing SAFEARRAY in C#. I don't know many things about genetic algorithm and please don't take take this code as demonstrating a problem to solve using only genetic algorithms (GA). This is just one approach. The C++ code for GA I got from the Internet.

Background (optional)

Disclaimer: I am not a GA and C# expert. I have reused C++ code to make it into a COM component and my goal was to show some visualisation effects using new kid on the block C#. It's only an example of GA coding.Any comments and criticism you have are most welcome.

Using the code

The main TSP component is written using COM via ATL, and the client application using C#. The TSP GA application will provide the following operations:

  • Set number of cities.
  • Set Population size for each generation.
  • Set Generation Size.
  • Set Cross Over Percentage.
  • Set Mutation rate.
  • Start TSPGA Algorithm.
  • Gets best Distance for each generation.
  • Gets overall best distance for all generations.
  • Gets overall best path traversed.
  • Gets Worst distance.

Design

COM Server

Find below the IDL file for details of methods exposed from interface:

interface ITSPGAAlgorithm : IDispatch
{
   [propput, id(1), helpstring("property SetPopulationSize")] 
                    HRESULT SetPopulationSize([in] short newVal);
   [propput, id(2), helpstring("property GetPopulationSize")] 
                    HRESULT GetPopulationSize([in] short* newVal);
   [propget, id(3), helpstring("property GenerationSize")] 
                    HRESULT GenerationSize([out, retval] short *pVal);
   [propput, id(3), helpstring("property GenerationSize")] 
                    HRESULT GenerationSize([in] short newVal);
   [propget, id(4), helpstring("property Mutate")]
                    HRESULT Mutate([out, retval] double *pVal);
   [propput, id(4), helpstring("property Mutate")]
                    HRESULT Mutate([in] double newVal);
   [propget, id(5), helpstring("property CitySize")]
                    HRESULT CitySize([out, retval] short *pVal);
   [propput, id(5), helpstring("property CitySize")]
                    HRESULT CitySize([in] short newVal);
   [id(6), helpstring("method SetCrossOverRate")] 
                    HRESULT SetCrossOverRate([in] short nCrossOverPercentage);
   [id(7), helpstring("method StartGAForTSP")]
                    HRESULT StartGAForTSP();
   [id(8), helpstring("method GetAllBestDistancesByGenerations")] 
                    HRESULT GetAllBestDistancesByGenerations([out,retval] 
                                                             VARIANT*pAllDistances);
   [id(9), helpstring("method GetBestPathForTSP")] 
                    HRESULT GetBestPathForTSP([out, retval] VARIANT* pPath);
   [propget, id(10), helpstring("property BestOverAll")] 
                    HRESULT BestOverAll([out, retval] short *pVal);
   [propget, id(11), helpstring("property WorstOverAll")] 
                    HRESULT WorstOverAll([out, retval] short *pVal);
};

Starting TSPGA

This is the main piece of code responsible for evolving generations, reproducing solution, mutations etc.

STDMETHODIMP CTSPGAAlgorithm::StartGAForTSP()
{
   // TODO: Add your implementation code here
   pGen = new ga(POP_SIZE,GEN_STOP,PROB_MUT,PROB_CROSS,CITY_COUNT);
   pGen->evolve();

   return S_OK;
}

Returning Distances to client

Use SAFEARRAY to fill the array of distances as a VARIANT pointer as below.

STDMETHODIMP CTSPGAAlgorithm::GetAllBestDistancesByGenerations(VARIANT *pAllDistances)
{
          // TODO: Add your implementation code here
          VariantInit(pAllDistances);
          pAllDistances->vt = VT_ARRAY | VT_I2 ;
          SAFEARRAY * psa;
          SAFEARRAYBOUND bounds = {GEN_STOP,0};
          psa = SafeArrayCreate(VT_I2,1,&bounds);
          int * pDist = NULL;
          pGen->GetDistanceByGen(&pDist);
          short *pDest = (short*)CoTaskMemAlloc(sizeof(short) * GEN_STOP);
          SafeArrayAccessData(psa,reinterpret_cast<void **>(&pDest));
          for(int i = 0 ; i < GEN_STOP ; i++)
                   pDest[i] = pDist[i];
          SafeArrayUnaccessData(psa);
          pAllDistances->parray = psa;

          return S_OK;
}

C# Client

I’m a not an expert in C# programming. It took quite a bit of time to put in all my browsing experience to find one really good article for XY Plot graph, so here is the link http://www.c-sharpcorner.com/Code/2002/Aug/XYPlotControl.asp. This is a nice user control to use in C# which adds nice visual effects to the travelling salesman problem.

Register TSPGAATL.dll using regsvr32

To access this component from C#, from the VisualStudio.NET IDE click on the 'Project' menu. Click 'Add Refernces', and a tabbed dialog should appear. Select the 'COM' tab and browse for 'TSPGAATL.dll', and add it. Now C# knows everything about our COM component.

Find below my code for accessing the COM component from C# and accessing the SAFEARRAY from a method.

// Create the COM component
TSPGAATLLib.ITSPGAAlgorithm comTSPGA = new TSPGAATLLib.TSPGAAlgorithmClass();

// Set All the properties 
comTSPGA.CitySize = System.Convert.ToInt16(this.textBox1.Text);
comTSPGA.SetPopulationSize = System.Convert.ToInt16(this.textBox2.Text);
comTSPGA.GenerationSize = System.Convert.ToInt16(this.textBox3.Text);
comTSPGA.SetCrossOverRate(System.Convert.ToInt16(this.textBox4.Text));
comTSPGA.Mutate = System.Convert.ToDouble(this.textBox5.Text);

// Start the GA TSP Engine 
comTSPGA.StartGAForTSP();

//Reset the User Control Graph 
xyGraphControl1.Reset();
xyGraphControl1.XTickValue = 20;
xyGraphControl1.YTickValue = 20;
xyGraphControl1.XOrigin = 1;
xyGraphControl1.YOrigin = 100;
xyGraphControl1.LabelX = "Generation";
xyGraphControl1.LabelY = "Distance";
 
//TSP gets diifferent best routes he can traverse
//C# handles Variant wrapped safearrays the following way...
//We fill Array with all Generations(say 1000)
//Make sure we convert to respective datatypes(C# complier returns good build errors)

System.Array distAll =(System.Array)comTSPGA.GetAllBestDistancesByGenerations();
for(int i = 0;i < distAll.Length;i++ )  
{
   //Write it to a file..
   distFile += distAll.GetValue(i) + "\n";                   
   //Display the Graph here by extracting the value stored in System.Array variable
   //Add the Distance points for each generation
   xyGraphControl1.AddPoint(System.Convert.ToInt64(i), 
                            System.Convert.ToInt64(distAll.GetValue(i)));            
}
FileStream fs = new FileStream(@"c:\dist.txt" , FileMode.OpenOrCreate, FileAccess.Write); 
StreamWriter m_streamWriter = new StreamWriter(fs); 
// Write to the file using StreamWriter class 
m_streamWriter.BaseStream.Seek(0, SeekOrigin.End);
m_streamWriter.Write(" File Write Operation Starts : "); 
m_streamWriter.Write(distFile);
m_streamWriter.Flush();

//Now help out TS(Travelling SalesMan)and give him this best route.
String outPut = "";
System.Array bestRoute =(System.Array) comTSPGA.GetBestPathForTSP();
for(int i = 0;i < bestRoute.Length;i++ )
{
  outPut += bestRoute.GetValue(i) + "-->";    
}
//Display it in Text Box
this.textBox6.Text = outPut + bestRoute.GetValue(0);
//the best overall ranking distance
this.label9.Text = System.Convert.ToString(comTSPGA.BestOverAll);
//the worst overall ranking system

this.label11.Text = System.Convert.ToString(comTSPGA.WorstOverAll);
xyGraphControl1.Invalidate();

Points of Interest

Accessing SAFEARRAY from C# took some time for me but the way C# handling any kind of datatype is excellent. Initially I was resisting my self to move to C# from my good old Win32, MFC and ATL controls.

C# is a good language to consider.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralNeed Source Code for timetable problem using genetic Algorithm Pin
umar ahmad28-Mar-10 21:15
umar ahmad28-Mar-10 21:15 
QuestionHow can i implement GA for Lab Time Table generator Pin
EiRy12-Oct-09 5:20
EiRy12-Oct-09 5:20 
Generalgenetic algorithm for sotware testing Pin
avkshanthi4-Jun-08 17:50
avkshanthi4-Jun-08 17:50 
Questionfacility layout problem solved by GA Pin
tak seong5-Sep-07 18:27
tak seong5-Sep-07 18:27 
AnswerRe: facility layout problem solved by GA Pin
GAbirkan29-Sep-07 0:44
GAbirkan29-Sep-07 0:44 
QuestionGA Pin
ssann7-Feb-07 2:23
ssann7-Feb-07 2:23 
QuestionHow can i implement GA for School Time Table Management Pin
asmysee1-May-06 19:11
asmysee1-May-06 19:11 
AnswerRe: How can i implement GA for School Time Table Management Pin
suryavas23-Oct-06 20:09
suryavas23-Oct-06 20:09 
AnswerRe: How can i implement GA for School Time Table Management Pin
yashucharabuddi6-Mar-07 3:53
yashucharabuddi6-Mar-07 3:53 
AnswerRe: How can i implement GA for School Time Table Management Pin
GAbirkan8-Aug-07 4:05
GAbirkan8-Aug-07 4:05 
AnswerRe: How can i implement GA for School Time Table Management Pin
brar322-Dec-09 13:24
brar322-Dec-09 13:24 
Generaltsp and vehicle routing problem Pin
shahida@kevin17-Jan-06 16:22
shahida@kevin17-Jan-06 16:22 
Generalproblem when building the project Pin
daftarfree26-Jan-05 19:28
daftarfree26-Jan-05 19:28 
Generalsource code needed Pin
Manyproblem13-Jan-05 23:21
Manyproblem13-Jan-05 23:21 
GeneralObjective Function and constraints Pin
Ramya Narayanaswamy22-Apr-04 8:49
Ramya Narayanaswamy22-Apr-04 8:49 
GeneralGreat Idea Pin
antoine@orchus-tech14-Mar-04 7:33
antoine@orchus-tech14-Mar-04 7:33 
GeneralRe: Great Idea Pin
Kalyan S Dontharaju18-Mar-04 9:31
Kalyan S Dontharaju18-Mar-04 9:31 
GeneralRe: Great Idea Pin
suryavas23-Oct-06 20:24
suryavas23-Oct-06 20:24 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.