برنامه الگوریتم ژنتیک
///////////////////////////// Travelling Salesman Problem (TSP) ///////////////////////////////
// TSP is a famous math problem: Given a number of cities and the costs of traveling
// from any city to any other city, what is the cheapest round-trip route that visits
// each city exactly once and then returns to the starting city?
//////////////////////////////////////milano.blogsky.com/////////////////////////////////////////////////////////
///---------------------- Begin CHROMOSOME.CS ----------------------------------------
using System;
using System.Threading;
namespace simga
{
/// <summary>
/// Summary description for Chromosome.
/// </summary>
public class Chromosome
{
public Chromosome()
{
//
// TODO: Add constructor logic here
//
}
// The cost for the fitness of the chromosome
protected double cost;
Random randObj = new Random();
//City myCity = new City();
// The list of cities which are the genes of the chromosome
protected int [] cityList;
// The mutation rate at percentage.
protected double mutationPercent;
// crossover point.
protected int crossoverPoint;
public Chromosome( City [] cities)
{
bool [] taken = new bool[cities.Length];
cityList = new int[cities.Length];
cost = 0.0;
for ( int i=0; i<cityList.Length; i++ ) taken[i] = false;
for ( int i=0; i<cityList.Length-1; i++ )
{
int icandidate;
do
{
icandidate = (int) ( randObj.NextDouble() * (double) cityList.Length );
} while ( taken[icandidate] );
cityList[i] = icandidate;
taken[icandidate] = true;
if ( i == cityList.Length-2 )
{
icandidate = 0;
while ( taken[icandidate] ) icandidate++;
cityList[i+1] = icandidate;
}
}
calculateCost(cities);
crossoverPoint = 1;
}
// fitness calculation
//void calculateCost(myCity cities)
public void calculateCost(City [] cities)
{
cost=0;
for ( int i=0; i<cityList.Length-1; i++ )
{
double dist = cities[cityList[i]].proximity(cities[cityList[i+1]]);
cost += dist;
}
}
public double getCost()
{
return cost;
}
public int getCity(int i)
{
return cityList[i];
}
public void assignCities(int [] list)
{
for ( int i=0; i<cityList.Length; i++ )
{
cityList[i] = list[i];
}
}
public void assignCity(int index, int value)
{
cityList[index] = value;
}
public void assignCut(int cut)
{
crossoverPoint = cut;
}
public void assignMutation(double prob)
{
mutationPercent = prob;
}
public int mate(Chromosome father, Chromosome offspring1, Chromosome offspring2)
{
int crossoverPostion1 = (int) ((randObj.NextDouble())*(double)(cityList.Length-crossoverPoint));
int crossoverPostion2 = crossoverPostion1 + crossoverPoint;
int [] offset1 = new int[cityList.Length];
int [] offset2 = new int[cityList.Length];
bool [] taken1 = new bool[cityList.Length];
bool [] taken2 = new bool[cityList.Length];
for ( int i=0; i<cityList.Length; i++ )
{
taken1[i] = false;
taken2[i] = false;
}
for ( int i=0; i<cityList.Length; i++ )
{
if ( i<crossoverPostion1 || i>= crossoverPostion2 )
{
offset1[i] = -1;
offset2[i] = -1;
}
else
{
int imother = cityList[i];
int ifather = father.getCity(i);
offset1[i] = ifather;
offset2[i] = imother;
taken1[ifather] = true;
taken2[imother] = true;
}
}
for ( int i=0; i<crossoverPostion1; i++ )
{
if ( offset1[i] == -1 )
{
for ( int j=0;j<cityList.Length;j++ )
{
int imother = cityList[j];
if ( !taken1[imother] )
{
offset1[i] = imother;
taken1[imother] = true;
break;
}
}
}
if ( offset2[i] == -1 )
{
for ( int j=0;j<cityList.Length;j++ )
{
int ifather = father.getCity(j);
if ( !taken2[ifather] )
{
offset2[i] = ifather;
taken2[ifather] = true;
break;
}
}
}
}
for ( int i=cityList.Length-1; i>=crossoverPostion2; i-- )
{
if ( offset1[i] == -1 )
{
for ( int j=cityList.Length-1;j>=0;j-- )
{
int imother = cityList[j];
if ( !taken1[imother] )
{
offset1[i] = imother;
taken1[imother] = true;
break;
}
}
}
if ( offset2[i] == -1 )
{
for ( int j=cityList.Length-1;j>=0;j-- )
{
int ifather = father.getCity(j);
if ( !taken2[ifather] )
{
offset2[i] = ifather;
taken2[ifather] = true;
break;
}
}
}
}
offspring1.assignCities(offset1);
offspring2.assignCities(offset2);
int mutate = 0;
int swapPoint1 = 0;
int swapPoint2 = 0;
if ( randObj.NextDouble() < mutationPercent )
{
swapPoint1 = (int) (randObj.NextDouble()*(double)(cityList.Length));
swapPoint2 = (int) (randObj.NextDouble()*(double)cityList.Length);
int i = offset1[swapPoint1];
offset1[swapPoint1] = offset1[swapPoint2];
offset1[swapPoint2] = i;
mutate++;
}
if ( randObj.NextDouble() < mutationPercent )
{
swapPoint1 = (int) (randObj.NextDouble()*(double)(cityList.Length));
swapPoint2 = (int) (randObj.NextDouble()*(double)cityList.Length);
int i = offset2[swapPoint1];
offset2[swapPoint1] = offset2[swapPoint2];
offset2[swapPoint2] = i;
mutate++;
}
return mutate;
}
public void PrintCity(int i, City [] cities)
{
System.Console.WriteLine("City "+i.ToString()+": ("+cities[cityList[i]].getx().ToString()+", "
+ cities[cityList[i]].gety().ToString()+")");
}
// chromosomes -- an array of chromosomes which is sorted
// num -- the number of the chromosome list
public static void sortChromosomes(Chromosome [] chromosomes,int num)
{
bool swapped = true;
Chromosome dummy;
while ( swapped )
{
swapped = false;
for ( int i=0; i<num-1; i++ )
{
if ( chromosomes[i].getCost() > chromosomes[i+1].getCost() )
{
dummy = chromosomes[i];
chromosomes[i] = chromosomes[i+1];
chromosomes[i+1] = dummy;
swapped = true;
}
}
}
}
}
}
//// ---------------------------- end CHROMOSOME.CS -------------------------------
/// ---------------------------- begin GA_TSP.CS --------------------------------------
using System;
using System.Threading;
using System.IO;
namespace simga
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class GA_TSP
{
protected int cityCount;
protected int populationSize;
protected double mutationPercent;
protected int matingPopulationSize;
protected int favoredPopulationSize;
protected int cutLength;
protected int generation;
protected Thread worker = null;
protected bool started = false;
protected City [] cities;
protected Chromosome [] chromosomes;
private string status = "";
public GA_TSP()
{
}
public void Initialization()
{
Random randObj = new Random();
try
{
cityCount = 40;
populationSize = 1000;
mutationPercent = 0.05;
}
catch(Exception e)
{
cityCount = 100;
}
matingPopulationSize = populationSize/2;
favoredPopulationSize = matingPopulationSize/2;
cutLength = cityCount/5;
// create a random list of cities
cities = new City[cityCount];
for ( int i=0;i<cityCount;i++ )
{
cities[i] = new City(
(int)(randObj.NextDouble()*30),(int)(randObj.NextDouble()*15));
}
// create the initial chromosomes
chromosomes = new Chromosome[populationSize];
for ( int i=0;i<populationSize;i++ )
{
chromosomes[i] = new Chromosome(cities);
chromosomes[i].assignCut(cutLength);
chromosomes[i].assignMutation(mutationPercent);
}
Chromosome.sortChromosomes(chromosomes,populationSize);
started = true;
generation = 0;
}
public void TSPCompute()
{
double thisCost = 500.0;
double oldCost = 0.0;
double dcost = 500.0;
int countSame = 0;
Random randObj = new Random();
while(countSame<120)
{
generation++;
int ioffset = matingPopulationSize;
int mutated = 0;
for ( int i=0;i<favoredPopulationSize;i++ )
{
Chromosome cmother = chromosomes[i];
int father = (int) ( randObj.NextDouble()*(double)matingPopulationSize);
Chromosome cfather = chromosomes[father];
mutated += cmother.mate(cfather,chromosomes[ioffset],chromosomes[ioffset+1]);
ioffset += 2;
}
for ( int i=0;i<matingPopulationSize;i++ )
{
chromosomes[i] = chromosomes[i+matingPopulationSize];
chromosomes[i].calculateCost(cities);
}
// Now sort the new population
Chromosome.sortChromosomes(chromosomes,matingPopulationSize);
double cost = chromosomes[0].getCost();
dcost = Math.Abs(cost-thisCost);
thisCost = cost;
double mutationRate = 100.0 * (double) mutated / (double) matingPopulationSize;
System.Console.WriteLine("Generation = "+generation.ToString()+" Cost = "+thisCost.ToString()+" Mutated Rate = "+mutationRate.ToString()+"%");
if ( (int)thisCost == (int)oldCost )
{
countSame++;
}
else
{
countSame = 0;
oldCost = thisCost;
//System.Console.WriteLine("oldCost = " + oldCost.ToString());
}
}
for(int i = 0; i < cities.Length; i++)
{
chromosomes[i].PrintCity(i, cities);
}
}
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
//
// TODO: Add code to start application here
//
GA_TSP tsp = new GA_TSP();
tsp.Initialization();
tsp.TSPCompute();
}
}
public class City
{
public City()
{
//
// TODO: Add constructor logic here
//
}
// The city's x coordinate.
private int xcoord;
// The city's y coordinate.
private int ycoord;
// x -- the city's x coordinate
// y -- the city's y coordinate
public City(int x, int y)
{
xcoord = x;
ycoord = y;
}
public int getx()
{
return xcoord;
}
public int gety()
{
return ycoord;
}
// Returns the distance from the city to another city.
public int proximity(City cother)
{
return proximity(cother.getx(),cother.gety());
}
// x -- the x coordinate
// y -- the y coordinate
// return The distance.
public int proximity(int x, int y)
{
int xdiff = xcoord - x;
int ydiff = ycoord - y;
return(int)Math.Sqrt( xdiff*xdiff + ydiff*ydiff );
}
}
}
////----------------------- end GA_TSP.CS ------------------------------------------------------
سلام .فرنوش هستم از وبسایت احساسات دات کام ! اگه عزیزی رو دارین که می خواین صداتونو به گوشش برسونید بیاید سایت ما . در ضمن می تونید به گمشده هاتون از سایت ما پیام بدین . برای وبلاگتون هم ابزار های جدید و بی همتا آماده کردیم . قربان شما - فرنوش
سلام وبلاگ باحالی داری
امیدوارم روز به روز بهتر شه
به من هم سر بزن
nemidounam chetor azat tashakor konam khodae karet aleye damet garam khoda kheyret bede.man ta hala hichvaght nazar nazashtam to weblog ya site cheze ama to takki
مرسی از لطفت.
سلام دوست عزیز لطفا یه توضیحی در مورد اینن کد بدین چطوره با چه زبانیه من تو سی ++ میزنم ارور میده تورو خدا مکمک اینو نبرم واسه استادم مشروط میشم اگه میشه زود
این برنامه با زبان سی شارپ نوشته شده .
سلام دوباره دادشی ببخشید هی مزاحم میشم داداش میتونی فایل اجرا شده این برنامه واسم بزاری اگه بزاری ممنونت میشم.به خدا میریزم تو c# ارور میده اجرا نمیکنه من زیاد وارد نیستم مهندس
سلام محمد جان ،
برای اجرای این برنامه باید دو تا صفحه ایجاد کنی و کد هر قسمت رو توی اون بنویسی ، اما حالا چون مشکلت خیلی مهمه واست و فرصت هم نداری برو به این لینک ها و دانلودش کن:
http://s1.picofile.com/file/7279412040/tsp_exe.zip.html
http://s2.picofile.com/file/7279413545/tsp.zip.html