📄 wsgenalogrith.cpp
字号:
#include "StdAfx.h"
#include ".\wsgenalogrith.h"
#include <fstream>
using namespace std;
#define CITENUM_RATE 2
#define FITNESS_ALPHA 0.5
#define MODENUM 3
//#define ALPHA 0.8//被m_CrossProbability取代
WSGeneticAlogrith::WSGeneticAlogrith(void)
{
}
WSGeneticAlogrith::~WSGeneticAlogrith(void)
{
}
/*
功能：比较A、B中两组子排列是否相同
输入：A、B的子排列和排列的长度
输出：TURE-->相同 FALSE-->不同
*/
BOOL WSGeneticAlogrith::EqualVector(PINT _A, PINT _B, INT _VertorLen)
{
for(int i = 0; i < _VertorLen; ++i)
{
if(_A[i] != _B[i]) return FALSE;
}
return TRUE;
}
BOOL WSGeneticAlogrith::Initial(PCHAR _FileName, PCHAR _oFileName, INT _MemberNum, INT _ComputeTime, BOOL _EndInNature,
INT _ComputeGenerates, INT _TimesOfNatureEnd, FLOAT _CrossProbability, FLOAT _VarProbability)
{
if( !MakeBaseCityInfo(_FileName) ) return FALSE;//先生成城市的基本信息
//设定群大小
if(_MemberNum == 0)
m_MemberNum = CITENUM_RATE*m_BaseCityInfo.m_CityNum;
else m_MemberNum = _MemberNum;
m_oFileName = _oFileName;
//设定交叉概率
if(_CrossProbability == 0)
_CrossProbability = 0.8;
else
m_CrossProbability = _CrossProbability,
//设定变异概率
m_VarProbability = _VarProbability;
GenInitialCityInfoOfMembers();
//for(INT i = 0; i < m_MemberNum; ++i) Show(m_pCityInfoOfMembers[i].m_pCityOrder);
m_EndInNature = _EndInNature;
//设定终止准则
if(_ComputeTime == 0)//ComputeTime的单位是秒
{
if(!_EndInNature) m_ComputeGenerates = _ComputeGenerates;
else
{
if(_TimesOfNatureEnd == 0) m_TimesOfNatureEnd = 500;
else m_TimesOfNatureEnd = _TimesOfNatureEnd;
}
}
else
{
m_TimesOfNatureEnd = 0;
m_ComputeGenerates = 0;
m_ComputeTime = _ComputeTime;
}
return TRUE;
}
//MODE=1:限定计算代数
//MODE=2:限定计算时间
//MODE=3:自然终止
BOOL WSGeneticAlogrith::Initial(INT _Mode, PCHAR _FileName, PCHAR _oFileName, INT _Compute_GeneratesORTimeORNatureTimes, INT _MemberNum, FLOAT _CrossProbability, FLOAT _VarProbability)
{
WSRandom::Initial();
switch(_Mode)
{
case 1: return Initial(_FileName, _oFileName, _MemberNum, 0, FALSE, _Compute_GeneratesORTimeORNatureTimes, 0,_CrossProbability, _VarProbability);
case 2: return Initial(_FileName, _oFileName, _MemberNum, _Compute_GeneratesORTimeORNatureTimes, FALSE, 0, 0,_CrossProbability, _VarProbability);
case 3: return Initial(_FileName, _oFileName, _MemberNum, 0, TRUE, 0, _Compute_GeneratesORTimeORNatureTimes,_CrossProbability, _VarProbability);
default:return FALSE;
}
return TRUE;
}
BOOL WSGeneticAlogrith::MakeBaseCityInfo(PCHAR _FileName)
{
return WSTSP::ReadCityInfoFromFile(_FileName, m_BaseCityInfo);
}
/*
注：该函数只能在得到m_BaseCityInfo后使用
用于种群的初始化工作
*/
VOID WSGeneticAlogrith::GenInitialCityInfoOfMembers()
{
CityInfo l_TmpCityInfo;
INT i;
INT **l_ppCitySerial;
INT _ShortestCityNum = MODENUM;
l_ppCitySerial = new INT*[m_BaseCityInfo.m_CityNum];
for(i = 0; i < m_BaseCityInfo.m_CityNum; ++i)
{
l_ppCitySerial[i] = new INT[_ShortestCityNum];
}
WSTSP::MakeCityDistStyle(m_BaseCityInfo, l_ppCitySerial, _ShortestCityNum);
//for(i = 0; i < m_BaseCityInfo.m_CityNum; ++i)
//{
// for(int k = 0; k < _ShortestCityNum; ++k)
// {
// printf("%d--->%d \t", i, l_ppCitySerial[i][k]);
// }
// printf("\n*************************************************\n");
//}
for(i = 0; i < m_MemberNum; ++i) m_pCityInfoOfMembers.push_back(l_TmpCityInfo);
//为适配函数分配地址
m_pAdaptInfo = (PAdaptInfo)malloc(sizeof(AdaptInfo)*m_MemberNum);
for(i = 0; i < m_MemberNum; ++i)
{
m_pCityInfoOfMembers[i].m_CityNum = m_BaseCityInfo.m_CityNum;
m_pCityInfoOfMembers[i].m_pCities = m_BaseCityInfo.m_pCities;
m_pCityInfoOfMembers[i].m_pCityOrder = m_BaseCityInfo.m_pCityOrder;
if(i < m_BaseCityInfo.m_CityNum) WSTSP::MakeStyleCityOrder(m_pCityInfoOfMembers[i], l_ppCitySerial, _ShortestCityNum);
else WSTSP::GenRandCityOrder(m_pCityInfoOfMembers[i].m_pCityOrder);
}
}
VOID WSGeneticAlogrith::CalculateAdapt(INT _Mode)
{
switch( _Mode )
{
case 0:
{
CalculateAdapt_CutTrai();
return ;
}
case 1:
{
CalculateAdapt_WSBetRing();
return ;
}
case 2:
{
CalculateAdapt_BetRing();
return ;
}
case 3:
{
CalculateAdapt_Immigrant();
return ;
}
default: return ;
}
}
/*
注：该函数只能在得到m_BaseCityInfo后使用
用于计算适配值/率
规则：大于平均适配率的全部去掉；相当于取小适配率
*/
VOID WSGeneticAlogrith::CalculateAdapt_CutTrai()
{
INT i;
FLOAT l_TotalValue = 0.0;
//相当于增加了记忆装置
FLOAT l_MinDist = WSTSP::TSPTotalDistance(&(m_pCityInfoOfMembers[0]));
INT l_OptOrder = 0;
for(i = 0; i < m_MemberNum; ++i)
{
m_pAdaptInfo[i].m_DestFunctionValue = WSTSP::TSPTotalDistance(&(m_pCityInfoOfMembers[i]));
l_TotalValue += m_pAdaptInfo[i].m_DestFunctionValue;
if(l_MinDist > m_pAdaptInfo[i].m_DestFunctionValue)
{
l_MinDist = m_pAdaptInfo[i].m_DestFunctionValue;
l_OptOrder = i;
}
}
//排序
//保存最优解
if(l_OptOrder != 0)
{
AdaptInfo l_TmpAdapt = m_pAdaptInfo[0];
m_pAdaptInfo[0] = m_pAdaptInfo[l_OptOrder];
m_pAdaptInfo[l_OptOrder] = l_TmpAdapt;
CityInfo l_TmpCityInfo = m_pCityInfoOfMembers[0];
m_pCityInfoOfMembers[0] = m_pCityInfoOfMembers[l_OptOrder];
m_pCityInfoOfMembers[l_OptOrder] = l_TmpCityInfo;
}
//计算适配率
for(i = 0; i < m_MemberNum; ++i) m_pAdaptInfo[i].m_AdaptProbability = m_pAdaptInfo[i].m_DestFunctionValue/l_TotalValue;
//除掉小于目标的方案
INT j = 0;
for(i = 0; i < m_MemberNum; ++i)
{
if(m_pAdaptInfo[i].m_AdaptProbability > 1.0/m_MemberNum)
{
if(WSRandom::JudgeEven(0.8)) m_pCityInfoOfMembers.erase( m_pCityInfoOfMembers.begin() + j);
else ++j;
}
else ++j;
}
}
/*
CalculateAdapt之模式1:执行自己定义的所谓轮赌法;
采用轮赌法重新选取个体产生新的群体,选取后的种群大小不变.
*/
VOID WSGeneticAlogrith::CalculateAdapt_WSBetRing()
{
INT i, j;
FLOAT l_MinDist;
INT l_OptOrder;
for(i = 0; i < m_MemberNum; ++i)
{
m_pAdaptInfo[i].m_DestFunctionValue = WSTSP::TSPTotalDistance(&(m_pCityInfoOfMembers[i]));
}
//排序:按距离，从小到大
//相当于增加了记忆装置
AdaptInfo l_TmpAdapt;
CityInfo l_TmpCityInfo;
for(i = 0; i < m_MemberNum; ++i)
{
l_MinDist = m_pAdaptInfo[i].m_DestFunctionValue;
l_OptOrder = i;
for(j = i; j < m_MemberNum; ++j)
{
if(l_MinDist > m_pAdaptInfo[j].m_DestFunctionValue)
{
l_MinDist = m_pAdaptInfo[j].m_DestFunctionValue;
l_OptOrder = j;
}
}
//m_pAdaptInfo只是中介作用，故不用严格调整次序
m_pAdaptInfo[l_OptOrder] = m_pAdaptInfo[i];
l_TmpCityInfo = m_pCityInfoOfMembers[i];
m_pCityInfoOfMembers[i] = m_pCityInfoOfMembers[l_OptOrder];
m_pCityInfoOfMembers[l_OptOrder] = l_TmpCityInfo;
}
//保护第一个序列，作为记忆单元
i = 1;
j = 0;
CityInfoOfMembersVector m_TmpVector;
m_TmpVector.push_back(m_pCityInfoOfMembers[0]);
while(j < m_MemberNum)
{
if(WSRandom::JudgeEven( 0.5*m_CrossProbability + 0.5 - 1.0*i/m_MemberNum ) )
{
m_TmpVector.push_back(m_pCityInfoOfMembers[i]);
j ++;
}
i++;
i %= m_MemberNum;
}
m_pCityInfoOfMembers.clear();
m_pCityInfoOfMembers = m_TmpVector;
m_TmpVector.clear();
return ;
}
/*
CalculateAdapt之模式2:执行比较标准的轮赌法;
采用轮赌法重新选取个体产生新的群体,选取后的种群大小不变.
*/
VOID WSGeneticAlogrith::CalculateAdapt_BetRing()
{
INT i, j;
FLOAT l_MinDist;
INT l_OptOrder;
for(i = 0; i < m_MemberNum; ++i)
{
m_pAdaptInfo[i].m_DestFunctionValue = WSTSP::TSPTotalDistance(&(m_pCityInfoOfMembers[i]));
}
//排序:按距离，从小到大
//相当于增加了记忆装置
AdaptInfo l_TmpAdapt;
CityInfo l_TmpCityInfo;
for(i = 0; i < m_MemberNum; ++i)
{
l_MinDist = m_pAdaptInfo[i].m_DestFunctionValue;
l_OptOrder = i;
for(j = i; j < m_MemberNum; ++j)
{
if(l_MinDist > m_pAdaptInfo[j].m_DestFunctionValue)
{
l_MinDist = m_pAdaptInfo[j].m_DestFunctionValue;
l_OptOrder = j;
}
}
//m_pAdaptInfo只是中介作用，故不用严格调整次序
m_pAdaptInfo[l_OptOrder] = m_pAdaptInfo[i];
l_TmpCityInfo = m_pCityInfoOfMembers[i];
m_pCityInfoOfMembers[i] = m_pCityInfoOfMembers[l_OptOrder];
m_pCityInfoOfMembers[l_OptOrder] = l_TmpCityInfo;
}
//保护第一个序列，作为记忆单元
i = 1;
j = 0;
CityInfoOfMembersVector m_TmpVector;
m_TmpVector.push_back(m_pCityInfoOfMembers[0]);
std::vector<double> l_FitnessVect;
for(i = 0; i < m_MemberNum; i ++)
{
l_FitnessVect.push_back(FITNESS_ALPHA*pow(FITNESS_ALPHA,i));
}
l_FitnessVect[0] *= 10000;
for(i = 1; i < m_MemberNum; i ++)
{
l_FitnessVect[i] = l_FitnessVect[i]*10000 + l_FitnessVect[i - 1];
}
int l_RollRange = l_FitnessVect[m_MemberNum -1], l_RollNumber;
for( i = 1; i < m_MemberNum; i++ )
{
l_RollNumber = WSRandom::GenRand(0, l_RollRange);
for( j = 0; j < m_MemberNum; j++)
{
if( l_RollNumber <= l_FitnessVect[j] )
{
m_TmpVector.push_back( m_pCityInfoOfMembers[j]);
break;
}
}
}
m_pCityInfoOfMembers.clear();
m_pCityInfoOfMembers = m_TmpVector;
m_TmpVector.clear();
return ;
}
/*
CalculateAdapt之模式3:加入移民，防止早熟
采用标准轮赌法重新选取个体产生新的群体（限制选取的数目）,然后将不足部分用移民替代；选取后的种群大小不变.
*/
VOID WSGeneticAlogrith::CalculateAdapt_Immigrant()
{
INT i, j;
FLOAT l_MinDist;
INT l_OptOrder;
for(i = 0; i < m_MemberNum; ++i)
{
m_pAdaptInfo[i].m_DestFunctionValue = WSTSP::TSPTotalDistance(&(m_pCityInfoOfMembers[i]));
}
//排序:按距离，从小到大
//相当于增加了记忆装置
AdaptInfo l_TmpAdapt;
CityInfo l_TmpCityInfo;
for(i = 0; i < m_MemberNum; ++i)
{
l_MinDist = m_pAdaptInfo[i].m_DestFunctionValue;
l_OptOrder = i;
for(j = i; j < m_MemberNum; ++j)
{
if(l_MinDist > m_pAdaptInfo[j].m_DestFunctionValue)
{
l_MinDist = m_pAdaptInfo[j].m_DestFunctionValue;
l_OptOrder = j;
}
}
//m_pAdaptInfo只是中介作用，故不用严格调整次序
m_pAdaptInfo[l_OptOrder] = m_pAdaptInfo[i];
l_TmpCityInfo = m_pCityInfoOfMembers[i];
m_pCityInfoOfMembers[i] = m_pCityInfoOfMembers[l_OptOrder];
m_pCityInfoOfMembers[l_OptOrder] = l_TmpCityInfo;
}
//保护第一个序列，作为记忆单元
i = 1;
j = 0;
CityInfoOfMembersVector m_TmpVector;
m_TmpVector.push_back(m_pCityInfoOfMembers[0]);
std::vector<double> l_FitnessVect;
for(i = 0; i < m_MemberNum; i ++)
{
l_FitnessVect.push_back(FITNESS_ALPHA*pow(FITNESS_ALPHA,i));
}
l_FitnessVect[0] *= 10000;
for(i = 1; i < m_MemberNum; i ++)
{
l_FitnessVect[i] = l_FitnessVect[i]*10000 + l_FitnessVect[i - 1];
}
int l_RollRange = l_FitnessVect[m_MemberNum -1], l_RollNumber;
// 2/3的个体由轮赌法决定;1/3的个体由移民组成
INT l_MemberNum = 2.0*m_MemberNum / 3.0;
for( i = 1; i < l_MemberNum; i++ )
{
l_RollNumber = WSRandom::GenRand(0, l_RollRange);
for( j = 0; j < m_MemberNum; j++)
{
if( l_RollNumber <= l_FitnessVect[j] )
{
m_TmpVector.push_back( m_pCityInfoOfMembers[j]);
break;
}
}
}
//////////////////////////////////////////////////////////////////////////////////////
//移民进入
l_TmpCityInfo.m_CityNum = m_BaseCityInfo.m_CityNum;
l_TmpCityInfo.m_pCities = m_BaseCityInfo.m_pCities;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -