📄 tsp.h
字号:
using namespace std;
std::vector<double> lpCityDistance;
template <typename T, typename P>
class Csga
{
public:
Csga();
Csga(int times,int GENERATION_AMOUNT,int CITY_AMOUNT); //构造函数
~Csga(); //析构函数
bool fnCreateRandomGene(); //产生随机基因
bool fnGeneAberrance(); //基因变异
bool fnGeneMix(); //基因交叉产生新的个体测试并淘汰适应度低的个体
bool fnEvalAll(); //测试所有基因的适应度
int fnEvalOne(T &Gene); //测试某一个基因的适应度
void Crossover( int nFatherA, int nFatherB);
void fnDispProbability(); //显示每个个体的权值
void fnDispHistoryMin();
private:
bool fnGeneAberranceOne(const int &i, const int &j);//变异某个基因
T m_GenerationGene[MAX_GENERATION_AMOUNT]; //定义每个群体的基因
P m_vProbability; //定义每个群体的适应度
int _TIMES ;
int _GENERATION_AMOUNT;
int _CITY_AMOUNT;
double HistoryMin;
T HistoryMinWay;
T m_GenerationGeneBk[MAX_GENERATION_AMOUNT];
};
//构造函数
template <typename T, typename P>
Csga<T, P>::Csga()
{
}
template <typename T, typename P>
Csga<T, P>::Csga(int times,int GENERATION_AMOUNT,int CITY_AMOUNT)
{
_TIMES=times;
_GENERATION_AMOUNT=GENERATION_AMOUNT;
_CITY_AMOUNT=CITY_AMOUNT;
m_vProbability.reserve(_CITY_AMOUNT);
HistoryMin = _INFINITE;
//cout << _P(lpCityDistance, 3, 2); //调试用
}
//析构函数
template <typename T, typename P>
Csga<T, P>::~Csga()
{
}
//产生随机基因
template <typename T, typename P>
bool Csga<T, P>::fnCreateRandomGene()
{
srand( time(0) ); //初始化随机数
//cout << "\t基因序列" << std::endl; //调试用
//生成随机基因
for(int j, temp, i = 0; i < _GENERATION_AMOUNT; ++i)
{
m_GenerationGene[i].reserve(_CITY_AMOUNT);
for (j = 0; j < _CITY_AMOUNT; ++j)
{
do
{
temp = rand()%_CITY_AMOUNT;
}while (find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp)
!= m_GenerationGene[i].end());
m_GenerationGene[i].push_back(temp);
}//end for
/*copy( m_GenerationGene[i].begin(), m_GenerationGene[i].end(),
std::ostream_iterator<int>(cout," ") );
cout << std::endl; */ //调试用
}
return true;
}
template <typename T, typename P>
bool Csga<T, P>::fnGeneAberrance()
{
int i, j;
int temp;
srand(time(0));
//抽选一代中的某个基因进行变异
for (i = 0; i < _GENERATION_AMOUNT; ++i)
{
for (j = 0; j < _CITY_AMOUNT; ++j)
{
temp = rand()%10000;
if ( temp > 0 && temp <= _P_GENE_ABERRANCE)
{
//随机抽选到的基因进行变异
if(!fnGeneAberranceOne(i, j)) {exit(0);}
}//end if
}//end for j
}//end for i
return true;
}
//变异第i个基因的第j位染色体
template <typename T, typename P>
bool Csga<T, P>::fnGeneAberranceOne(const int &i, const int &j)
{
int temp; //基因变异结果
srand(time(0));
temp=rand()% _CITY_AMOUNT;
T::iterator pos;
//找到变异位与另外一位交换
pos = std::find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp);
if (pos != m_GenerationGene[i].end())
{
*pos= m_GenerationGene[i][j];
m_GenerationGene[i][j] = temp;
return true;
}
return false;
}
inline int fnRndBoundary(int iBegin, int iEnd)
{
return rand()%(iEnd-iBegin) + iBegin;
}
/*********************************************************
Crossover()——两染色体的交叉实现
输入参数： 1、nFatherA 父染色体A
2、nFatherB 父染色体B
3、nMode 交叉方式
返回值： 空
注：
现有交叉方式
1、常规交叉方式，该方式比《现代计算方法》（邢文训等编著）p178给出的
“非常规码的常规交配法”稍复杂些。书中只随机选择一个交配位，两个后代
交配位之前的基因分别继承双亲的交配位之前的基因。本程序中，是随机选择
两个不相同的交配位，后代在这两个交配位之间继承双亲在这两个交配位之间
的基因
如 父A 1 2 3 | 4 5 6 7 | 8 9 10
父B 4 7 8 | 3 2 5 9 | 1 6 10
子A 8 3 2 | 4 5 6 7 | 9 1 10
子B 1 4 6 | 3 2 5 9 | 7 8 10
2、贪心交叉方式（Greedy Crossover），
具体算法可参见 谢胜利,等.求解ＴＳＰ问题的一种改进的遗传算法[Ｊ].计算机工程与应用,2002(8):58～245.
*********************************************************/
template <typename T, typename P>
void Csga<T, P>:: Crossover( int nFatherA, int nFatherB)
{
int nPopSize = _GENERATION_AMOUNT;
if( nFatherA < 0 || nFatherA >= nPopSize ||
nFatherB < 0 || nFatherB >= nPopSize )
return;
std::vector<int> SonA, SonB;
int ncrossoverbegin, ncrossoverend;
while(1)
{
ncrossoverbegin = rand()%(_CITY_AMOUNT-1); //取交叉范围
ncrossoverend = rand()%(_CITY_AMOUNT-1);
if( ncrossoverend > ncrossoverbegin )
break;
else if( ncrossoverend < ncrossoverbegin )
{
std::swap( ncrossoverbegin, ncrossoverend );
break;
}
}
for( int i=ncrossoverbegin;i<=ncrossoverend;i++ )
{
SonA.push_back( m_GenerationGene[nFatherA].at(i) );
SonB.push_back( m_GenerationGene[nFatherB].at(i) );
}
std::vector<int>::iterator iter_father, iter_son;
bool hasCity = false;
int naddbegin = 0;
for( iter_father= m_GenerationGene[nFatherB].begin();
iter_father!= m_GenerationGene[nFatherB].end();
iter_father++ )
{
hasCity = false;
for( iter_son=SonA.begin();iter_son!=SonA.end();iter_son++ )
{
if( *iter_son == *iter_father )
{
hasCity = true;
break;
}
}
if( !hasCity )
{
if( naddbegin < ncrossoverbegin )
{
SonA.insert( SonA.begin()+naddbegin, *iter_father );
naddbegin++;
}
else
SonA.push_back( *iter_father );
}
}
naddbegin = 0;
for( iter_father= m_GenerationGene[nFatherA].begin();
iter_father!= m_GenerationGene[nFatherA].end();
iter_father++ )
{
hasCity = false;
for( iter_son=SonB.begin();iter_son!=SonB.end();iter_son++ )
{
if( *iter_son == *iter_father )
{
hasCity = true;
break;
}
}
if( !hasCity )
{
if( naddbegin < ncrossoverbegin )
{
SonB.insert( SonB.begin()+naddbegin, *iter_father );
naddbegin++;
}
else
SonB.push_back( *iter_father );
}
}
m_GenerationGene[nFatherA].clear();
m_GenerationGene[nFatherB].clear();
m_GenerationGene[nFatherA] = SonA;
m_GenerationGene[nFatherB] = SonB;
m_vProbability[nFatherA] = fnEvalOne(m_GenerationGene[nFatherA]);
m_vProbability[nFatherB] = fnEvalOne(m_GenerationGene[nFatherB]);
}
/*********************************************************
CrossoverPop()——种群交叉
输入参数： 1、nMode 交叉方式
返回值： 空
*********************************************************/
//基因交叉产生新的个体并淘汰适应度低的个体
template <typename T, typename P>
bool Csga<T, P>::fnGeneMix()
{
double fProbability = CROSSOVER_P; //交配概率
std::vector<int> vecCrossoverIndexs;
int nPopSize =_GENERATION_AMOUNT;
double random;
srand( time(0) );
for( int i=0;i<nPopSize;i++ )
{
random = ((double)(rand()%10000))/10000.0;
if( random < fProbability )
vecCrossoverIndexs.push_back( i );
}
int CrossoverNumber = vecCrossoverIndexs.size();
if( CrossoverNumber%2 != 0 )
vecCrossoverIndexs.pop_back();
CrossoverNumber = vecCrossoverIndexs.size();
for( i=0;i<CrossoverNumber;i=i+2)
{
int nFatherA = vecCrossoverIndexs[i];
int nFatherB = vecCrossoverIndexs[i+1];
// CString strTemp1, strTemp2;
// strTemp1 = FormRouterString( vecPop[nFatherA] );
// strTemp2 = FormRouterString( vecPop[nFatherB] );
Crossover( nFatherA, nFatherB);
// strTemp1 = FormRouterString( vecPop[nFatherA] );
// strTemp2 = FormRouterString( vecPop[nFatherB] );
}
return true;
}
//测试基因的适应度
template <typename T, typename P>
bool Csga<T, P>::fnEvalAll()
{
int i, j;
m_vProbability.assign( _GENERATION_AMOUNT, 0);
//cout << "\t基因适应度\n";
//测试每组基因的适应性
for (i = 0; i < _GENERATION_AMOUNT; ++i)
{
for (j = 0; j < _CITY_AMOUNT-1; ++j)
{
m_vProbability[i] +=lpCityDistance[ m_GenerationGene[i][j]* _CITY_AMOUNT+m_GenerationGene[i][j+1]];
}//end for (j = 0; j < _CITY_AMOUNT; ++j);
m_vProbability[i] +=lpCityDistance[ m_GenerationGene[i][_CITY_AMOUNT-1]*_CITY_AMOUNT+m_GenerationGene[i][0]];
if (m_vProbability[i] < HistoryMin)
{
HistoryMin = m_vProbability[i];
HistoryMinWay = m_GenerationGene[i];
}
}//end for (int j, i = 0; i < _GENERATION_AMOUNT; ++i)
//copy (m_vProbability.begin(), m_vProbability.end(), std::ostream_iterator<int>(cout," "));
//cout << std::endl;
//m_vProbability[_GENERATION_AMOUNT-1] = fnEvalOne(m_GenerationGeneBk[_GENERATION_AMOUNT-1]);
return true;
}
//测试某个基因的适应度并返回适应度
template <typename T, typename P>
int Csga<T, P>::fnEvalOne(T &Gene)
{
int iResult = 0;
for (int i = 0; i < _CITY_AMOUNT-1; ++i)
{
iResult +=lpCityDistance[Gene[i]*_CITY_AMOUNT+Gene[i + 1]];
}
return iResult;
}
template <typename T, typename P>
void Csga<T, P>::fnDispProbability()
{
/*cout << "\t个体基因序列" <<std::endl; //调试用
for (int i = 0; i < _GENERATION_AMOUNT; ++i)
{
cout << " 个体" << i+1 << "的基因:";
copy( m_GenerationGene[i].begin(), m_GenerationGene[i].end(),
std::ostream_iterator<int>(cout," ") );
if (i%2 == 1)
cout << std::endl;
}
*/
cout << "\t最小开销为:";
#define _VECT_TEMP std::min_element(m_vProbability.begin(), m_vProbability.end())
cout << *_VECT_TEMP << std::endl;//+_GENERATION_AMOUNT
//cout << "各个方案的路程分别为:" ;
//copy (m_vProbability.begin(), m_vProbability.end(), std::ostream_iterator<int>(cout, " "));
cout << std::endl;
cout << "*******************************************************" << std::endl;
}
template <typename T, typename P>
void Csga<T, P>::fnDispHistoryMin()
{
cout << "历史上最短开销为:"<< HistoryMin << " 路径为:" ;
std::copy (HistoryMinWay.begin(), HistoryMinWay.end(), std::ostream_iterator<int>(cout, " ->"));
cout << *HistoryMinWay.begin();
cout <<std::endl;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -