tspga.cpp

旅行商问题求解 旅行商问题求解 旅行商问题求解 旅行商问题求解

/*
  个体编码方案：
  						个体为经过所有城市的一条路径
						以string存储
						形式如"ABCDEFGHIJ"
  交配方法：
  						采用常规交配法,将交配位之后的城市顺序改变
						例：
						"ABCDE"与"EDCBA"交配
						随机产生的交配位为3,则
						"ABCDE"->"ABCED"
						"EDCBA"->"EDCAB"
  变异方法：
  						采用逆序交换法，交换随机两位间的城市
						例：
						"ABCDEFGHIJ"变异
						随机产生两个数是3和6,则
					 	"ABCDEFGHIJ"->"ABFEDCGHIJ"
  新种群构成的方法：
  						采用确定性选择方式
						根据课件的方法，求出每个个体的期望次数
						先选择期望次数向下取整次
						再按(期望次数 - 期望次数向下取整)从大到小的顺序选满下一代种群

  算法结束的条件：
  				   		连续(int)minCountToStop代不产生更优结果则退出
						繁衍到(int) maxLoopCycle代则停止

  NOTE 1：
						在对算法性能不断改进过程中，我发现
						为了使得收敛的速度更快，需要引入父代与子代竞争被选择名额的机制
						即父代经过交配或变异后，不直接被产生的子代替换
						而是二者经过竞争，获得下一轮被选择的机会
  NOTE 2：
                        根据《人工智能基础》，蔡自兴，高等教育出版社，2005，p.89
                        交叉和变异的概率根据问题不同而应有不同的设定
                        针对TSP问题及我所选取的交配、变异方式
                        变异比交配更有效率
                        于是在实际计算中，交配概率仅有0.05
                        而变异概率高达0.95
  NOTE 3:
                        关于参数的选取

                   			  对于minCountToStop
                        			  根据测试，取8倍城市数基本上可以保证最优解出现概率接近1
                    		  对于maxLoopCycle
                        			  根据测试，20城市繁衍到2000代出现最优解的概率接近1
                        			  (事实上，在几千次的测试中，最优解往往在繁衍到第500~700代时就已经出现过minCountToStop次了)
                              对于groupSize
									  groupSize我开始选择的是200
									  后来发现100比200快
									  70比100快
									  50比70满
                                      ……

                                      再经过改进交配和变异的方式
                                      引入代间竞争
                                      发现种群很小的时候也能快速收敛到最优解

                                      groupSize = 40时最优解出现概率在0.98左右，计算500次耗时约45s
									  groupSize = 30时最优解出现概率在0.97左右，计算500次耗时约36s
									  groupSize = 20时最优解出现概率在0.946左右，计算500次耗时约25s
                                      最终我选择了groupSize = 30;

  NOTE 3:
                        编译器差别
                        在mac下用eclipse编译代码运行时发现速度明显比VS2008生成的代码快
                        于是win下改用Dev-C++

                        用Dev-C++自带的gcc编译出来的代码运行速度比用VS2008编译出来的debug、release代码速度快很多（数量级差别）
                        而VS2008的release神奇地比debug慢一些……

*/


#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <string>
//#include "myTimer.h"


using namespace std;

const int repeatTimes = 30;
const bool saveDetails = false;


int cityCount;
char cities[21];							//城市名数组
double pos_x[20], pos_y[20];				//城市坐标
double dist[20][20];						//城市间距离

//以下变量初始化数值见 void Reset();
double deltaDistance;
double minDistance;
int minCount;
string minPath;

const int groupSize = 30;					//种群大小
const double crossGenRate = 0.05;			//交叉概率
const double selfGenRate = 0.95;			//变异概率
int minCountToStop;		             		//当前最短路径出现minCountToStop次则停止
const int maxLoopCycle = 2000;             	//最多繁衍到第maxLoopCycle代

string groupMember[groupSize];				//种群
double groupF[groupSize];					//适应度值
double groupPossibility[groupSize];			//选择概率
double expectedSelectedTimes[groupSize];	//期望次数
double selectedTimes[groupSize];			//选中次数
double deltaSel[groupSize];					//期望次数-选中次数
int generation;


bool loadCities ( char infile[20], int& cityCount, char* cities, double* pos_x, double* pos_y );//读入城市数据
void printCities ( int& cityCount, char* cities, double* pos_x, double* pos_y );//输出城市数据 for debug only
void calcDist ( int& cityCount, double* pos_x, double* pos_y );					//计算城市距离
double getDistanceOf ( char city1, char city2 );								//计算两个城市间距离
double getTotalDistance ( string curOrder );									//计算curPath回路长度
void Reset();                                                                   //结果存储变量清零
void initializeGroup();															//初始化种群
string randomPath();															//产生随机路径
void printCurGroup();															//输出当代种群
void calcGroupF();																//计算种群每个个体适应度值
void printCurGroupWithF();														//输出当代种群及适应度值
void printBestMember();															//输出当代最优解
void getBestMember ( double& bestF, int& bestId );                              //获取当代最优路径长度bestF及对应个体编号bestId
void selectMember();															//选择进入下一代的路径
void printCurGroupWithSelTimes();												//输出当代种群及选中次数
void crossGen();																//交叉
void selfGen();																	//变异
void clearUnselected();                                                         //更新种群
void saveGenerationDetails();                                                   //向文件写入种群繁衍细节
void saveCurGroupWithF();														//文件写入当代种群及适应度值
void saveBestMember();															//文件写入当代最优解


ofstream fout;

int main ( int argc, char *argv[] ) {
    srand ( ( unsigned ) time ( 0 ) );

    cout << "Please specify the input filename:";
    char infile[20];// = "tsp20.txt";
    cin >> infile;						//输入文件名

    fout.open ( "generationDetails.txt" );

    //MyTimer timer;
    //MyTimer totalTimer;

    //totalTimer.Start();

    double results[repeatTimes];
    double bestResult = ( double ) ( INT_MAX );
    int bestResultCount = 0;


    for ( int runtimes = 0; runtimes < repeatTimes; runtimes++ ) {
        //timer.Reset();
        //timer.Start();

        Reset();

        if ( !loadCities ( infile, cityCount, cities, pos_x, pos_y ) ) {		//读入文件
            cout << "Error load cities!! Please check the input file!" << endl;
            system ( "PAUSE" );
            exit ( 1 );
        }

        minCountToStop = cityCount * 8;

        //minCountToStop = 100000;

        calcDist ( cityCount, pos_x, pos_y );									//计算距离矩阵

        //printCities(cityCount,cities, pos_x, pos_y);

        //初始化种群
        initializeGroup();

        //printCurGroup();

        while ( true ) {
            //计算种群上每个个体的适应度值
            calcGroupF();

            //写入种群详细信息

            if ( saveDetails )	saveGenerationDetails();

            //按照个体适应度值选择进入下一代的个体
            selectMember();

            //printCurGroupWithSelTimes();
            clearUnselected();

            //交叉
            crossGen();

            //变异
            selfGen();

            //判断是否停止
            double curBest;

            int curBestId;

            getBestMember ( curBest, curBestId );

            //printBestMember();

            if ( curBest < minDistance ) {
                minDistance = curBest;
                minCount = 1;
                minPath = groupMember[curBestId];

            } else if ( ( curBest - minDistance ) < 0.00001 ) {
                minCount++;
            }

            if ( minCount > minCountToStop )
                break;
            else if ( generation >= maxLoopCycle )
                break;

            generation++;
        };

        //得到估计的最优解
        //timer.End();

        cout << "============================================================" << endl;

        cout << "Result No." << runtimes + 1 << endl;

        cout << "The shortest path is " << minPath << endl;

        cout << "The total distance of the shortest path is " << sqrt ( minDistance ) << endl;

        cout << "Loop stoped at the " << generation << "th generation." << endl;

        //cout << "Time elapsed for this single result is " << timer.costTime << " micro seconds" << endl;

        results[runtimes] = sqrt ( minDistance );
    }


    for ( int i = 0;i < repeatTimes;i++ ) {
        if ( results[i] < bestResult ) {
            bestResult = results[i];
        }
    }

    bestResultCount = 0;

    for ( int i = 0;i < repeatTimes;i++ ) {
        if ( ( results[i] - bestResult ) < 0.00001 ) {
            bestResultCount++;
        }
    }

    //totalTimer.End();

    cout << "============================================================" << endl;
    cout << "Algorithm repeated " << repeatTimes << " times." << endl;
    cout << "The shortest path is " << bestResult << endl;
    cout << "The percentage of the appearance of the best result is " << ( double ) ( bestResultCount ) / ( double ) ( repeatTimes ) << endl;
    //cout << "Total time elapsed is " << totalTimer.costTime << " micro seconds" << endl;
    cout << "============================================================" << endl;


    system ( "PAUSE" );
    return EXIT_SUCCESS;
}

bool loadCities ( char infile[20], int& cityCount, char* cities, double* pos_x, double* pos_y ) {

    ifstream inputFile;
    inputFile.open ( infile );				//打开输入文件

    if ( inputFile.fail() ) {
        return false;
    }

    inputFile >> cityCount;				//读入城市数

    for ( int i = 0;i < cityCount;i++ ) {		//读入城市名、城市坐标
        inputFile >> cities[i] >> pos_x[i] >> pos_y[i];
    }

    return true;
}

void printCities ( int& cityCount, char* cities, double* pos_x, double* pos_y ) {
    cout << cityCount << endl;

    for ( int i = 0;i < cityCount;i++ )
        cout << cities[i] << "\t" << pos_x[i] << "\t" << pos_y[i] << endl;
}

void calcDist ( int& cityCount, double* pos_x, double* pos_y ) {
    for ( int i = 0; i < cityCount; i++ )
        for ( int j = i; j < cityCount; j++ ) {
            dist[i][j] = sqrt ( ( pos_x[i] - pos_x[j] ) * ( pos_x[i] - pos_x[j] ) + ( pos_y[i] - pos_y[j] ) * ( pos_y[i] - pos_y[j] ) );
        }
}


double getTotalDistance ( string curOrder ) {
    double tDist = 0;

    for ( int i = 0; i < cityCount - 1; i++ )
        tDist += getDistanceOf ( curOrder[i], curOrder[i+1] );

    if ( cityCount > 0 )
        tDist += getDistanceOf ( curOrder[0], curOrder[cityCount-1] );

    return tDist;
}

double getDistanceOf ( char city1, char city2 ) {
    int c1 = city1 - cities[0];
    int c2 = city2 - cities[0];

    if ( c1 > c2 )
        return getDistanceOf ( city2, city1 );
    else
        return dist[c1][c2];
}

void Reset() {
    deltaDistance = 0;
    minDistance = ( double ) ( INT_MAX );
    minCount = 0;
    generation = 0;
}

void initializeGroup() {
    for ( int id = 0;id < groupSize; id++ ) {
        groupMember[id] = randomPath();
    }