天天看點
傳回

基本蟻群算法 - Kermit.Li

基本蟻群算法 

//=====================================================================
//基本蟻群算法源代碼
//使用的城市資料是eil51.tsp
//=====================================================================
// AO.cpp : 定義控制台應用程式的入口點。
#pragma once
#include "stdafx.h"
#include <iostream>
#include <math.h> 
#include <time.h>
//=====================================================================
//常量定義和參數定義
//=====================================================================
const double ALPHA=1.0; //啟發因子，資訊素的重要程度
const double BETA=2.0; //期望因子，城市間距離的重要程度
const double ROU=0.5; //資訊素殘留參數
const int N_ANT_COUNT=34; //螞蟻數量
const int N_IT_COUNT=1000; //疊代次數
const int N_CITY_COUNT=51; //城市數量
const double DBQ=100.0; //總的資訊素
const double DB_MAX=10e9; //一個标志數，10的9次方
double g_Trial[N_CITY_COUNT][N_CITY_COUNT]; //兩兩城市間資訊素，就是環境資訊素
double g_Distance[N_CITY_COUNT][N_CITY_COUNT]; //兩兩城市間距離
//eil51.tsp城市坐标資料
double x_Ary[N_CITY_COUNT]=
{
37,49,52,20,40,21,17,31,52,51,
42,31,5,12,36,52,27,17,13,57,
62,42,16,8,7,27,30,43,58,58,
37,38,46,61,62,63,32,45,59,5,
10,21,5,30,39,32,25,25,48,56,
};

double y_Ary[N_CITY_COUNT]=
{
52,49,64,26,30,47,63,62,33,21,
41,32,25,42,16,41,23,33,13,58,
42,57,57,52,38,68,48,67,48,27,
69,46,10,33,63,69,22,35,15,6,
17,10,64,15,10,39,32,55,28,37,
};
//傳回指定範圍内的随機整數
int rnd(int nLow,int nUpper)
{
return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1);
}
//傳回指定範圍内的随機浮點數
double rnd(double dbLow,double dbUpper)
{
double dbTemp=rand()/((double)RAND_MAX+1.0);
return dbLow+dbTemp*(dbUpper-dbLow);
}
//傳回浮點數四舍五入取整後的浮點數
double ROUND(double dbA)
{
return (double)((int)(dbA+0.5));
}
//=====================================================================
//螞蟻類的定義和實作
//=====================================================================
//定義螞蟻類
class CAnt
{
public:
CAnt(void);
~CAnt(void);
public:
int m_nPath[N_CITY_COUNT]; //螞蟻走的路徑
double m_dbPathLength; //螞蟻走過的路徑長度
int m_nAllowedCity[N_CITY_COUNT]; //沒去過的城市
int m_nCurCityNo; //目前所在城市編号
int m_nMovedCityCount; //已經去過的城市數量
public:
int ChooseNextCity(); //選擇下一個城市
void Init(); //初始化
void Move(); //螞蟻在城市間移動
void Search(); //搜尋路徑
void CalPathLength(); //計算螞蟻走過的路徑長度
};
//構造函數
CAnt::CAnt(void)
{
}
//析構函數
CAnt::~CAnt(void)
{
}
//初始化函數，螞蟻搜尋前調用
void CAnt::Init()
{
for (int i=0;i<N_CITY_COUNT;i++)
{
m_nAllowedCity[i]=1; //設定全部城市為沒有去過
m_nPath[i]=0; //螞蟻走的路徑全部設定為0
}
//螞蟻走過的路徑長度設定為0
m_dbPathLength=0.0; 
//随機選擇一個出發城市
m_nCurCityNo=rnd(0,N_CITY_COUNT);
//把出發城市儲存入路徑數組中
m_nPath[0]=m_nCurCityNo;
//辨別出發城市為已經去過了
m_nAllowedCity[m_nCurCityNo]=0; 
//已經去過的城市數量設定為1
m_nMovedCityCount=1; 
}
//選擇下一個城市
//傳回值 為城市編号
int CAnt::ChooseNextCity()
{
int nSelectedCity=-1; //傳回結果，先暫時把其設定為-1
//==============================================================================
//計算目前城市和沒去過的城市之間的資訊素總和
double dbTotal=0.0; 
double prob[N_CITY_COUNT]; //儲存各個城市被選中的機率
for (int i=0;i<N_CITY_COUNT;i++)
{
if (m_nAllowedCity[i] == 1) //城市沒去過
{
//該城市和目前城市間的資訊素
prob[i]=pow(g_Trial[m_nCurCityNo][i],ALPHA)*pow(1.0/g_Distance[m_nCurCityNo][i],BETA); 
dbTotal=dbTotal+prob[i]; //累加資訊素，得到總和
}
else //如果城市去過了，則其被選中的機率值為0
{
prob[i]=0.0;
}
}
//==============================================================================
//進行輪盤選擇
double dbTemp=0.0;
if (dbTotal > 0.0) //總的資訊素值大于0
{
dbTemp=rnd(0.0,dbTotal); //取一個随機數
for (int i=0;i<N_CITY_COUNT;i++)
{
if (m_nAllowedCity[i] == 1) //城市沒去過
{
printf("dbtemp=%f-i=%d",dbTemp,i);system("pause");
dbTemp=dbTemp-prob[i]; //這個操作相當于轉動輪盤，如果對輪盤選擇不熟悉，仔細考慮一下
if (dbTemp < 0.0) //輪盤停止轉動，記下城市編号，直接跳出循環
{
nSelectedCity=i;
break;
}
}
}
if(dbTemp>0){printf("dbtemp=%d",dbTemp);system("pause");}
}
//==============================================================================
//如果城市間的資訊素非常小 ( 小到比double能夠表示的最小的數字還要小 )
//那麼由于浮點運算的誤差原因，上面計算的機率總和可能為0
//會出現經過上述操作，沒有城市被選擇出來
//出現這種情況，就把第一個沒去過的城市作為傳回結果 
if (nSelectedCity == -1)
{
for (int i=0;i<N_CITY_COUNT;i++)
{
if (m_nAllowedCity[i] == 1) //城市沒去過
{
nSelectedCity=i;
break;
}
}
}
//==============================================================================
//傳回結果，就是城市的編号
return nSelectedCity;
}
//螞蟻在城市間移動
void CAnt::Move()
{
int nCityNo=ChooseNextCity(); //選擇下一個城市
m_nPath[m_nMovedCityCount]=nCityNo; //儲存螞蟻走的路徑
m_nAllowedCity[nCityNo]=0;//把這個城市設定成已經去過了
m_nCurCityNo=nCityNo; //改變目前所在城市為選擇的城市
m_nMovedCityCount++; //已經去過的城市數量加1
}
//螞蟻進行搜尋一次
void CAnt::Search()
{
Init(); //螞蟻搜尋前，先初始化
//如果螞蟻去過的城市數量小于城市數量，就繼續移動
while (m_nMovedCityCount < N_CITY_COUNT)
{
Move();
}
//完成搜尋後計算走過的路徑長度
CalPathLength();
}
//計算螞蟻走過的路徑長度
void CAnt::CalPathLength()
{
m_dbPathLength=0.0; //先把路徑長度置0
int m=0;
int n=0;
for (int i=1;i<N_CITY_COUNT;i++)
{
m=m_nPath[i];
n=m_nPath[i-1];
m_dbPathLength=m_dbPathLength+g_Distance[m][n];
}
//加上從最後城市傳回出發城市的距離
n=m_nPath[0];
m_dbPathLength=m_dbPathLength+g_Distance[m][n]; 
}
//=====================================================================
//TSP類的定義和實作
//=====================================================================
//tsp類
class CTsp
{
public:
CTsp(void);
~CTsp(void);
public:
CAnt m_cAntAry[N_ANT_COUNT]; //螞蟻數組
CAnt m_cBestAnt; //定義一個螞蟻變量，用來儲存搜尋過程中的最優結果
//該螞蟻不參與搜尋，隻是用來儲存最優結果
public:
//初始化資料
void InitData(); 
//開始搜尋
void Search(); 
//更新環境資訊素
void UpdateTrial();
};
//構造函數
CTsp::CTsp(void)
{
}
CTsp::~CTsp(void)
{
}
//初始化資料
void CTsp::InitData() 
{
//先把最優螞蟻的路徑長度設定成一個很大的值
m_cBestAnt.m_dbPathLength=DB_MAX; 
//計算兩兩城市間距離
double dbTemp=0.0;
for (int i=0;i<N_CITY_COUNT;i++)
{
for (int j=0;j<N_CITY_COUNT;j++)
{
dbTemp=(x_Ary[i]-x_Ary[j])*(x_Ary[i]-x_Ary[j])+(y_Ary[i]-y_Ary[j])*(y_Ary[i]-y_Ary[j]);
dbTemp=pow(dbTemp,0.5);
//城市間距離四舍五入取整,eil51.tsp的最短路徑426是距離按四舍五入取整後得到的。
g_Distance[i][j]=ROUND(dbTemp);
}
}
//初始化環境資訊素，先把城市間的資訊素設定成一樣
//這裡設定成1.0，設定成多少對結果影響不是太大，對算法收斂速度有些影響
for (int i=0;i<N_CITY_COUNT;i++)
{
for (int j=0;j<N_CITY_COUNT;j++)
{
g_Trial[i][j]=1.0;
}
}
}
//更新環境資訊素
void CTsp::UpdateTrial()
{
//臨時數組，儲存各隻螞蟻在兩兩城市間新留下的資訊素
double dbTempAry[N_CITY_COUNT][N_CITY_COUNT];
memset(dbTempAry,0,sizeof(dbTempAry)); //先全部設定為0
//計算新增加的資訊素,儲存到臨時數組裡
int m=0;
int n=0;
for (int i=0;i<N_ANT_COUNT;i++) //計算每隻螞蟻留下的資訊素
{
for (int j=1;j<N_CITY_COUNT;j++)
{
m=m_cAntAry[i].m_nPath[j];
n=m_cAntAry[i].m_nPath[j-1];
dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength;
dbTempAry[m][n]=dbTempAry[n][m];
}
//最後城市和開始城市之間的資訊素
n=m_cAntAry[i].m_nPath[0];
dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength;
dbTempAry[m][n]=dbTempAry[n][m];
}
//==================================================================
//更新環境資訊素
for (int i=0;i<N_CITY_COUNT;i++)
{
for (int j=0;j<N_CITY_COUNT;j++)
{
g_Trial[i][j]=g_Trial[i][j]*ROU+dbTempAry[i][j]; //最新的環境資訊素 = 留存的資訊素 + 新留下的資訊素
}
}
}
void CTsp::Search()
{
char cBuf[256]; //列印資訊用
//在疊代次數内進行循環
for (int i=0;i<N_IT_COUNT;i++)
{
//每隻螞蟻搜尋一遍
for (int j=0;j<N_ANT_COUNT;j++)
{
m_cAntAry[j].Search(); 
}
//儲存最佳結果
for (int j=0;j<N_ANT_COUNT;j++)
{
if (m_cAntAry[j].m_dbPathLength < m_cBestAnt.m_dbPathLength)
{
m_cBestAnt=m_cAntAry[j];
}
}
//更新環境資訊素
UpdateTrial();
//輸出目前為止找到的最優路徑的長度
sprintf(cBuf,"\n[%d] %.0f",i+1,m_cBestAnt.m_dbPathLength);
printf(cBuf);
}
}
//=====================================================================
//主程式
//=====================================================================
int main()
{
//用目前時間點初始化随機種子，防止每次運作的結果都相同
time_t tm;
time(&tm);
unsigned int nSeed=(unsigned int)tm;
srand(nSeed);
//開始搜尋
CTsp tsp;
tsp.InitData(); //初始化
tsp.Search(); //開始搜尋
//輸出結果
printf("\nThe best tour is :\n");
char cBuf[128];
for (int i=0;i<N_CITY_COUNT;i++)
{
sprintf(cBuf,"%02d ",tsp.m_cBestAnt.m_nPath[i]+1);
if (i % 20 == 0)
{
printf("\n");
}
printf(cBuf);
}
printf("\n\nPress any key to exit!");
getchar();
return 0;
}

 

轉載：http://www.cnblogs.com/sky-view/p/3281186.html

　　

上一篇: Linux下搭建SVN雲伺服器
下一篇: 蟻群算法的優化和評估