TSP问题 遗传算法的实现
发布时间
阅读量：
阅读量
遗传算法由群体集合和3个主要操作组成
主要操作：
1. 选择
2. 交叉
3. 变异
4. 增殖
其中选择操作将群体中的优良个体选择出来，而交叉操作和变异操作则根据交叉概率pc和变异概率pm对选择出的个体进行不同的操作(遗传算法的核心) ，最后使用增殖操作使得种群数量保持稳定。
采用C++面向对象思想进行设计
1.城市的数据结构
class City{
public:
double x, y;
City(int nx, int ny){
x = nx;
y = ny;
}
};
2.地图的数据结构
class Map{
int _cityNum;
vector<City> _citySet;
public:
Map(){
_cityNum = 0;
}
//插入城市
void insertCity(City c){
_citySet.push_back(c);
_cityNum++;
}
//返回城市数量
const int getCityNum(){
return _cityNum;
}
//获得指定下标的城市
const City getCity(int i){
return _citySet[i];
}
};
3.解的数据结构
class Solution{
int _length; //解的长度 比城市数量多1(首尾均为0)
vector<int> _solution; //解 记录城市下标
Map _map;
//计算两个城市的距离
const double _calculateDistance(const City &a, const City &b){
return ((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
};
public:
Solution(Map &map){
_map = map;
_length = _map.getCityNum() + 1;
for(int i = 0; i < _length - 1; i++) {
_solution.push_back(i);
}
_solution.push_back(0); //回到原点
randomSolution();
}
//初始化 使解随机
void randomSolution(){
for(int i = 1; i < _length - 2; i++){
int index = rand()%(_length - 2) + 1;
if(i != index) swap(_solution[i], _solution[index]);
}
}
void printSolution(){
for(int i = 0; i < _length; i++){
cout << _solution[i] << " ";
}
cout << endl;
}
//计算解的值
const double evalute(){
double sumOfDistance = 0;
City preCity = _map.getCity(_solution[0]);
for(int i = 1; i < _length; i++){
City nowCity = _map.getCity(_solution[i]);
double dis = _calculateDistance(preCity, nowCity);
sumOfDistance += dis;
preCity = nowCity;
}
return sumOfDistance;
}
};
4.遗传算法主体
/*
以轮盘赌方式计算适应度
*/
class GA{
vector<Solution> _solutionSet;
public:
double pc = 0.5; //杂交概率
double pm = 0.5; //变异概率
GA(vector<Solution> solutionSet, Map m){
_solutionSet = solutionSet;
}
void selection(){
//wait for implememt
}
void crossover(){
//wait for implememt
}
void mutation(){
//wait for implememt
}
};
全部评论 (0)
还没有任何评论哟~