GA.rar_Genetic for route

/* 名称：遗传算法求解二维地图最佳路径 作者：海德光明 qq：542586280 时间：2013.10 */ #include <iostream> #include <vector> #include <time.h> //#include <afxcoll.h> //#pragma comment( lib, "winmm.lib") #define MAP_HEIGHT 10 #define MAP_WIDTH 15 //要产生0~1之间的数，必须(rand()/(RAND_MAX+1.0)) //产生 0~3之间的数 #define RANDGENE (4*(rand()/(RAND_MAX+1.0))) //随机产生的值是a~b之间 #define RandDouble(a,b) (((b-a)*(rand()/(RAND_MAX+1.0)))+a) //产生0~1之间的数 #define RandZtoO (rand()/(RAND_MAX+1.0)) using namespace std; //地图 //数组[纵轴变量0~9][横轴变量0~14] const int map[MAP_HEIGHT][MAP_WIDTH] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 8, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 5, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; const int g_iMapHeight = MAP_HEIGHT; const int g_iMapWidth = MAP_WIDTH; //x轴 y轴从左上角开始 下标从0开始 const int g_iStartX = 0; const int g_iStartY = 2; const int g_iEndX = 14; const int g_iEndY = 7; //遗传算法参数设置 const double g_InheritParent = 0.7;//杂交率 const double g_waveDNA = 0.001;//突变率 #ifndef STRUCTS #define STRUCTS //dna结构体 包含n个基因片段 struct SDNA { //dna中每个基因是一个int型的变量 vector<int> m_vecGene; }; struct SRun { //dna种群 vector<SDNA> m_SDNAS; //适应值保存 vector<double> m_Adaptes;//所有dna的适应值 下标是dna种群的下标 double m_AdaptesAll;//dna适应值总和 使用轮盘选择法 //dna最短基因数 int m_ShortSize; //染色体条数 int m_DnaNum; //找到路径 或暂停标志 bool Stop_Flag; /*******************/ //初始化变量 void IninRun(); //初始化dna种群 DnaNum 种群数目 void InitDna(); //计算整个 及 单个dna适应值 vector<int> Gene单个基因 返回适应值 void CalCulateAdapteDNAS(); double CalCulateAdapte(SDNA sDna); //dna种群 轮盘选择法 选择两个基因 得到两个基因，直到新的种群出现 void GetNewDNAS(); SDNA GetParent();//轮盘法获取一个dna void InheritDNA(SDNA father,SDNA mother,SDNA *baby1,SDNA *baby2); //dna种群 基因变异 void variation(SDNA *baby); //遗传m代 Order次数 void inheritence(int Order); //DnaNum 代表代的次数 //运行线程 //void CreateThreads();//创建线程 //static DWORD WINAPI ThreadProc( LPVOID lpParameter );//线程函数 SRun(int DnaNum); SRun(); ~SRun(); }; #endif /****************/ //函数实现 void SRun::IninRun() { m_ShortSize = 140;//dna长度 m_DnaNum = 100;//染色体种群数量 m_SDNAS.clear();//dna m_Adaptes.clear();//适应值 m_AdaptesAll = 0;//适应总值 Stop_Flag = false; } //随机初始化dna种群 void SRun::InitDna() { //产生DnaNum个dna，并压入dna容器中 int randNum = 0; for( int Num = 0; Num < m_DnaNum; Num++) { //产生一个dna 压入种群中 //第一种方法 /* SDNA *dnaTmp = new SDNA(); m_SDNAS.push_back( *dnaTmp ); int sdnaSize = m_SDNAS.size(); for( int i = 0; i < m_ShortSize; i++) { m_SDNAS[sdnaSize-1].m_vecGene.push_back( RANDGENE ); //cout<<" "<<m_SDNAS[sdnaSize-1].m_vecGene[m_SDNAS[sdnaSize-1].m_vecGene.size()-1]; } //cout<<endl; */ //第二种方法 SDNA dnaTmp; int sdnaSize = m_SDNAS.size(); for( int i = 0; i < m_ShortSize; i++) { dnaTmp.m_vecGene.push_back( RANDGENE ); } m_SDNAS.push_back( dnaTmp ); //输出 //for( int j = 0; j < m_ShortSize; j++) //cout<<" "<<m_SDNAS[sdnaSize].m_vecGene[j]; //cout<<endl; } } //适应值 void SRun::CalCulateAdapteDNAS() { m_Adaptes.clear(); m_AdaptesAll = 0; int DNASize = m_SDNAS.size(); double tmpAdp = 0; for(int i = 0; i < DNASize; i++) { tmpAdp = CalCulateAdapte( m_SDNAS[i] ); m_AdaptesAll += tmpAdp; m_Adaptes.push_back(tmpAdp); //cout<<m_Adaptes[i]<<endl; } cout<<m_AdaptesAll<<" "<<m_Adaptes.size()<<endl; } //计算单个染色体 适应值 double SRun::CalCulateAdapte( SDNA sDna ) { //dna长度 int dnaSize = sDna.m_vecGene.size(); //x,y为机器人的坐标 int x = g_iStartX, y = g_iStartY; //机器人走路 for( int i = 0; i <dnaSize; i++) { //取出基因去走路 int gene = sDna.m_vecGene[i]; if( x == g_iEndX && y == g_iEndY) break; //向下走 y+1 if(gene == 2 && map[y+1][x] == 0) {y += 1;//cout<<"down"<<" "; } //向上走 y-1 if( gene== 0 && map[y-1][x] == 0 && (y>0)) {y -= 1;//cout<<"up"<<" "; } //向右走 x+1 if(gene== 1 && ( (map[y][x+1] == 0)|| (map[y][x+1]==5) )) {x +=1;//cout<<"right"<<" "; } //向左走 x-1 if(gene == 3 && map[y][x-1] == 0 && (x>0)) {x -= 1;//cout<<"left"<<" "; } //cout<<"go"<<" "; }//endfor 走完路 //求适应值 if( x == g_iEndX && y == g_iEndY ) cout<<"OK"<<" "; double dAdpTmp = 0.0; //算数运算符 除法 除法运算符“/”：双目运算具有左结合性。参与运算量均为整型时，结果也为整型，舍去小数。 //如果运算量中有一个是实型，则结果为双精度实型。 dAdpTmp = 1.0/(double)(abs(g_iEndX-x)+abs(g_iEndY-y)+1); //cout<<"Single:"<<" x:"<<x<<" y:"<<y<<" dadptmp:"<<dAdpTmp<<endl; return dAdpTmp; } //获取新染色体 void SRun::GetNewDNAS() { //创建新的dna群 vector<SDNA> SDNASTmp; SDNASTmp.clear(); int NewBabys = 0; while( NewBabys < m_DnaNum ) { //选出两个dna //for(int i= 0; i < baby1.m_vecGene.size(); i++) cout<<baby1.m_vecGene.at(i)<<" ";cout<<endl; //for(int j= 0; j < father->m_vecGene.size(); j++) cout<<father->m_vecGene.at(j)<<" ";cout<<endl; //for(int j= 0; j < mother.m_vecGene.size(); j++) cout<<mother.m_vecGene.at(j)<<" ";cout<<endl; SDNA father,mother,baby1,baby2; father = GetParent( ); mother = GetParent( ); InheritDNA(father,mother,&baby1,&baby2); variation(&baby1); variation(&baby2); SDNASTmp.push_back(father); SDNASTmp.push_back(mother); NewBabys += 2; //cout<<"for"<<NewBabys<<endl; } m_SDNAS.clear(); m_SDNAS = SDNASTmp; } //轮盘法选择父母 SDNA SRun::GetParent() { //cout<<(double)(rand()/(RAND_MAX+1.0))<<endl; //轮盘法转到的位置 double dTmpPoint = m_AdaptesAll*(double)(rand()/(RAND_MAX+1.0)); double tmpCount = 0;//轮盘计数 int adpSize = m_Adaptes.size(); //赌轮选择 int SelectParent = 0;//选择 for(int i = 0; i < adpSize; i++) { tmpCount += m_Adaptes[i]; if( tmpCount >= dTmpPoint ) {SelectParent = i;break;} } //cout<<"tmpCount:"<<tmpCount<<"dTmpPoint:"<<dTmpPoint<<"SelectParent:"<<SelectParent<<"m_Adaptes.size()"<<m_Adaptes.size()<<endl; return m_SDNAS[SelectParent]; } //杂交 void SRun::InheritDNA(SDNA father,SDNA mother,SDNA *baby1,SDNA *baby2) { //如果随机数大于杂交率 或者父母一样 则 则不杂交 if(( RandZtoO >= g_InheritParent ) || (father.m_vecGene == mother.m_vecGene ) ) { *baby1 = father; *baby2 = mother; return; } //基因杂交终点 int GeneEndPos = RandDouble(0, m_ShortSize); for( int i = 0; i < GeneEndPos; i++) { baby1->m_vecGene.push_back( father.m_vecGene[i] ); baby2->m_vecGene.push_back( mother.m_vecGene[i] ); } for( int j = GeneEndPos; j < m_ShortSize; j++) { baby1->m_vecGene.push_back( mother.m_vecGene[j] ); baby2->m_vecGene.push_back( father.m_vecGene[j] ); } } //变异 void SRun::variation(SDNA *baby) { //在突变率之下 if( RandZtoO < g_waveDNA ) { cout<<"突变"<<endl; int GenePos1 = RandDouble(0, m_ShortSize); int GenePos2 = RandDouble(0, m_ShortSize); int StartPos,EndPos; StartPos = ((GenePos1>GenePos2)?GenePos2:GenePos1); EndPos = ((GenePos1>GenePos2)?GenePos1:GenePos2); for(int i = StartPos; i < EndPos; i++) { baby->m_vecGene.at(i) = RANDGENE; } } } //构造函数与析构函数 SRun::SRun(int DnaNum) { //初始化数据 IninRun(); //初始化染色体 InitDna(); for( int i = 0; i< DnaNum; i++) { cout<<"第"<<(i+1)<<"代"<<endl; //计算适应值 CalCulateAdapteDNAS(); //取得新染色体 GetNewDNAS(); } } SRun::SRun() { //初�