ga.h

一个遗传算法的VC版本

/*
用遗传算法(GA)解决TSP（旅行商）问题----算法部分
完成时间:2005.8.5
编译环境:VC7.1 (用VC6的话需要修改几处，要把hash_map改为map)

作者:西南科技大学   唐坤(sf.tk)
QQ: 226152161
Blog: blog.gameres.com/show.asp?BlogID=1450&column=0
E-mail: [e-mail]
*/
#pragma once
#include "head.h"

//基因定义(一个城市)
struct Gene
{	
	int ID;
	hash_map<Gene*,float> linkCost; //该城市到其它城市的路程开销
};

//染色体定义(到各城市顺序的一种组合)
struct Chrom
{
	vector<Gene*> chrom_gene;  //染色体（到各城市去的顺序）
	float varible;   //路程总开销
	float fitness;   //个体适应度	  
};

//种群定义
struct Pop
{
	vector<Chrom> pop_chrom;  //种群里的染色体组
    float sumfitness;    //种群中个体适应度累计	 
};

//遗传算法类
class CGA
{
public:	
	CGA(){}  //构造函数
	~CGA(){}; //析构函数
	//参数设置函数，传入参数依次为 地图信息，交叉率，变异率，种群大小，最大世代数，进化方案
	void preSet(const vector<vector<int > >& mapDist,float pcross,float pmutation,int popsize,int maxgen,int evolveWay = 1);
	//遗传算法启动函数，由界面调用，返回最优路径及开销
	pair<vector<int>,int> start();	
    
private:
	Pop oldpop; //当前代种群
    Pop newpop; //新一代种群
    vector<Gene> genes;  //保存全部基因

	float pcross;     //交叉率
	float pmutation;  //变异率
	int popsize;      //种群大小
	int lchrom; //染色体长度	
	int maxgen;    //最大世代数	
	int gen;       //当前世代
	float max_var; //路径最大连接开销!!
	int evolveWay;
	
    int randomInt(int low,int high);     //产生一个随机整数(在low和high之间)
	void chromCost(Chrom& chr);    //计算一条染色体的个体适应度
	void popCost(Pop &pop);        //计算一个种群的个体适应度之和
	void initChrom(Chrom& chr);    //随机初始化一条染色体
	void initpop(Pop& pop); //随机初始化种群
	int selectChrom(const Pop& pop); //轮盘赌选择,返回种群中被选择的个体编号
	int chooseBest(const Pop& pop); //精英策略，返回最优秀的一条染色体

    //染色体交叉操作,由两个父代产生两个子代( 顺序交叉 OX )
    void crossover(Chrom& parent1,Chrom& parent2,Chrom& child1,Chrom& child2);
	//染色体变异操作,随机交换两个基因
    void mutation(Chrom& chr);
    //世代进化(由当前种群产生新种群)
    void generation(Pop& oldpop,Pop& newpop);
};