/*
用遺傳算法(GA)解決TSP（旅行商）問題----算法部分
完成時(shí)間:2005.8.5
編譯環(huán)境:VC7.1 (用VC6的話需要修改幾處，要把hash_map改為map)

作者:西南科技大學(xué)   唐坤(sf.tk)
QQ: 226152161
Blog: blog.gameres.com/show.asp?BlogID=1450&column=0
E-mail: starsftk@yahoo.com.cn
*/
#pragma once

#include <ctime>
#include <vector>
#include <hash_map>
#include <algorithm>
using namespace std;

//基因定義(一個(gè)城市)
struct Gene
{	
	int ID;
	hash_map<Gene*,float> linkCost; //該城市到其它城市的路程開銷
};

//染色體定義(到各城市順序的一種組合)
struct Chrom
{
	vector<Gene*> chrom_gene;  //染色體（到各城市去的順序）
	float varible;   //路程總開銷
	float fitness;   //個(gè)體適應(yīng)度	  
};

//種群定義
struct Pop
{
	vector<Chrom> pop_chrom;  //種群里的染色體組
    float sumfitness;    //種群中個(gè)體適應(yīng)度累計(jì)	 
};

//遺傳算法類
class CGA
{
public:	
	CGA(){}  //構(gòu)造函數(shù)
	~CGA(){}; //析構(gòu)函數(shù)
	//遺傳算法啟動(dòng)函數(shù)，由界面調(diào)用,傳入?yún)?shù)依次為 地圖信息，交叉率，變異率，種群大小，最大世代數(shù)，返回最優(yōu)路徑及開銷
	pair<vector<int>,float> start(const vector<vector<float> >& mapDist,float pcross,float pmutation,int popsize,int maxgen);	
    
private:
	Pop oldpop; //當(dāng)前代種群
    Pop newpop; //新一代種群
    vector<Gene> genes;  //保存全部基因

	float pcross;     //交叉率
	float pmutation;  //變異率
	int popsize;      //種群大小
	int lchrom; //染色體長度	
	int maxgen;    //最大世代數(shù)	
	int gen;       //當(dāng)前世代
	float max_var; //路徑最大連接開銷!!
	
    int randomInt(int low,int high);     //產(chǎn)生一個(gè)隨機(jī)整數(shù)(在low和high之間)
	void chromCost(Chrom& chr);    //計(jì)算一條染色體的個(gè)體適應(yīng)度
	void popCost(Pop &pop);        //計(jì)算一個(gè)種群的個(gè)體適應(yīng)度之和
	void initChrom(Chrom& chr);    //隨機(jī)初始化一條染色體
	void initpop(Pop& pop); //隨機(jī)初始化種群
	int selectChrom(const Pop& pop); //輪盤賭選擇,返回種群中被選擇的個(gè)體編號(hào)
	int chooseBest(const Pop& pop); //精英策略，返回最優(yōu)秀的一條染色體

    //染色體交叉操作,由兩個(gè)父代產(chǎn)生兩個(gè)子代( 順序交叉 OX )
    void crossover(Chrom& parent1,Chrom& parent2,Chrom& child1,Chrom& child2);
	//染色體變異操作,隨機(jī)交換兩個(gè)基因
    void mutation(Chrom& chr);
    //世代進(jìn)化(由當(dāng)前種群產(chǎn)生新種群)
    void generation(Pop& oldpop,Pop& newpop);
};