#include?“Genetic.h“

Genetic::Genetic（int?numOfQueens?int?initialGroupNum）
{
	m_adaptive.resize（initialGroupNum?0）;
	m_accumuAdaptive.resize（initialGroupNum?0）;
	m_QueenNum?=?numOfQueens;
	m_BestAdaptive?=?0;
	m_NotSuccess?=?true;

	for?（int?i?=?numOfQueens?-?1;?i?>=?1;?--i）
	{
		m_BestAdaptive?+=?i;??//?計算最佳適應(yīng)度
	}

	SetPopulation（）;
}

void?Genetic::SetPopulation（）
{
	m_population.clear（）;
	vector?tmpState（m_QueenNum?0）;
	for?（size_t?i?=?0;?i?	{
		for?（size_t?j?=?0;?j?		{
			tmpState[j]?=?rand（）?%?m_QueenNum;
		}
		m_population.push_back（tmpState）;

		m_adaptive[i]?=?CalcuAdaptive（tmpState）;????//?計算新生成種群的適應(yīng)值
	}
}

//?計算適應(yīng)值
double?Genetic::CalcuAdaptive（vector?&state）
{
	size_t?conflict?=?0;
	for?（size_t?i?=?0;?i?	{
		for?（size_t?j?=?i?+?1;?j?		{
			if?（state[i]?==?state[j]?||?abs（state[i]?-?state[j]）?==?j?-?i）
				conflict++;?????????????????//?發(fā)現(xiàn)互相攻擊的皇后對，conflict加一
		}
	}
	if?（conflict?==?0）??//?找到最優(yōu)解
	{
		m_NotSuccess?=?false;
		m_BestOne?=?state;
	}
	return?1.0?/?conflict;
}

//?物競天擇
void?Genetic::Select（）
{
	vector>?NewPopulation;???//?新的種群
	m_accumuAdaptive[0]?=?m_adaptive[0];
	for?（size_t?i?=?1;?i?	{
		m_accumuAdaptive[i]?=?m_accumuAdaptive[i?-?1]?+?m_adaptive[i];
	}
	double?totalAdaptive?=?m_accumuAdaptive[m_accumuAdaptive.size（）?-?1];
	for?（size_t?i?=?0;?i?	{
		int????magnifyTotalAdaptive?=?totalAdaptive?*?100000;??//?先乘以十萬
		size_t?random?=?rand（）*rand（）?%?magnifyTotalAdaptive;??//?%?運算符要求整數(shù)
		double?select?=?（double）random?/?100000;???????????????//?再除以十萬

		vector::iterator?low;
		low?=?lower_bound（m_accumuAdaptive.begin（）?m_accumuAdaptive.end（）?select）;??//?二分法查找
		size_t?j?=?low?-?m_accumuAdaptive.begin（）;??????????//?被選中的種群的下標(biāo)
		NewPopulation.push_back（m_population[j]）;
	}
	//?更新種群
	m_population.clear（）;
	m_population?=?NewPopulation;
}

void?Genetic::Crossover（）
{
	for?（size_t?i?=?0;?i?	{
		//隨機產(chǎn)生一個雜交單點，然后以單點為界，兩個染色體呼喚單點兩側(cè)的
		//優(yōu)質(zhì)的基因片段無法長久遺傳下去，隨機性過強，很容易被切斷
		/*size_t?hybridSpot?=?rand（）?%?m_QueenNum;
		for?（size_t?j?=?0;?j?		{
		swap（m_population[i][j]?m_population[i?+?1][j]）;
		}
		for?（size_t?j?=?hybridSpot;?j?		{
		swap（m_population[i][j]?m_population[i?+?1][j]）;
		}*/

		//以下采用中間段交換，經(jīng)過實驗統(tǒng)計。在8皇后（16個初始種群）時候，此方法比上面一種方法優(yōu)化了38%
		size_t?midA?=?m_QueenNum?/?3;
		size_t?midB?=?m_QueenNum?*?2?/?3;
		for?（size_t?j?=?midA;?j?		{
			swap（m_population[i][j]?m_population[i?+?1][j]）;
		}

		//求解大于10的規(guī)模皇后的時候，把一個狀態(tài)切割成一個小片段，交換
		/*bool?change?=?true;
		size_t?incre?=?4;
		for?（size_t?i?=?0;?i?		{
		if?（change）
		{
		for?（size_t?j?=?i;?j?		{
		swap（m_population[i][

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????1174??2015-11-12?08:21??Genetic.h
?????文件????????3639??2015-11-28?19:09??MinConflict.cpp
?????文件?????????741??2015-11-12?08:21??MinConflict.h
?????文件????????1038??2015-11-12?08:26??NQueensBacktrack.cpp
?????文件?????????448??2015-11-28?19:09??NQueensBacktrack.h
?????文件????????1342??2015-11-14?23:28??main.cpp
?????文件????????4738??2015-11-28?19:09??Genetic.cpp