熟悉和掌握遺傳算法的原理、流程和編碼策略，并利用遺傳算法求解組合優(yōu)化問(wèn)題，理解求解TSP問(wèn)題的流程并測(cè)試主要參數(shù)對(duì)結(jié)果的影響。

二、實(shí)驗(yàn)原理：

旅行商問(wèn)題，即TSP問(wèn)題（Traveling Salesman Problem）是數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。TSP問(wèn)題是一個(gè)組合優(yōu)化問(wèn)題。該問(wèn)題可以被證明具有NPC計(jì)算復(fù)雜性。因此，任何能使該問(wèn)題的求解得以簡(jiǎn)化的方法，都將受到高度的評(píng)價(jià)和關(guān)注。

遺傳算法的基本原理是通過(guò)作用于染色體上的基因?qū)ふ液玫娜旧w來(lái)求解問(wèn)題，它需要對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)度值來(lái)選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)，在遺傳算法中，通過(guò)隨機(jī)方式產(chǎn)生 若干個(gè)所求解問(wèn)題的數(shù)字編碼，即染色體，形成初始種群；通過(guò)適應(yīng)度函數(shù)給每 個(gè)個(gè)體一個(gè)數(shù)值評(píng)價(jià)，淘汰低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體參加遺傳操作，經(jīng)過(guò)遺產(chǎn)操作后的個(gè)體集合形成下一代新的種群，對(duì)這個(gè)新的種群進(jìn)行下一輪的進(jìn)化。本實(shí)驗(yàn)要求利用遺傳算法求解TSP問(wèn)題的最短路徑。

三、實(shí)驗(yàn)內(nèi)容：

1、參考實(shí)驗(yàn)系統(tǒng)給出的遺傳算法核心代碼，要求在相同的種群規(guī)模、最大迭代步數(shù)、獨(dú)立運(yùn)行次數(shù)下，用遺傳算法求解不同規(guī)模（例如10個(gè)城市，30個(gè)城市，100個(gè)城市）的TSP問(wèn)題，把結(jié)果填入表1。

表1 遺傳算法求解不同規(guī)模的TSP問(wèn)題的結(jié)果

1. 設(shè)置種群規(guī)模為100，交叉概率為0.8，變異概率為0.8，然后增加1種變異策略（例如相鄰兩點(diǎn)互換變異、逆轉(zhuǎn)變異或插入變異等）和1種個(gè)體選擇概率分配策略（例如按線性排序或者按非線性排序分配個(gè)體選擇概率）用于求解30個(gè)城市的TSP問(wèn)題（30個(gè)城市坐標(biāo)如下），把結(jié)果填入表2。

30個(gè)城市坐標(biāo)：

x[0]=41, x[1]=37,x[2]=54,x[3]=25,x[4]=7,x[5]=2,x[6]=68,x[7]=71,x[8]=54,x[9]=83;

y[0]=94,y[1]=84,y[2]=67,y[3]=62,y[4]=64,y[5]=99,y[6]=58,y[7]=44,y[8]=62,y[9]=69;

x[10]=64,x[11]=18,x[12]=22,x[13]=83,x[14]=91,x[15]=25,x[16]=24,x[17]=58,x[18]=71,x[19]=74;

y[10]=60,y[11]=54,y[12]=60,y[13]=46,y[14]=38,y[15]=38,y[16]=42,y[17]=69,y[18]=71,y[19]=78;

x[20]=87,x[21]=18,x[22]=13,x[23]=82,x[24]=62,x[25]=58,x[26]=45,x[27]=41,x[28]=44, x[29]=4;

y[20]=76,y[21]=40,y[22]=40,y[23]=7,y[24]=32,y[25]=35,y[26]=21,y[27]=26,y[28]=35; y[29]=50;

表2 不同的變異策略和個(gè)體選擇概率分配策略的求解結(jié)果

3、現(xiàn)給出中國(guó) 34 個(gè)省會(huì)數(shù)據(jù)，要求基于此數(shù)據(jù)設(shè)計(jì)遺傳算法的改進(jìn)算法解決該 TSP 問(wèn)題。要求給出1）改進(jìn)算法策略及核心代碼，2）改進(jìn)算法的主要參數(shù)設(shè)置（種群規(guī)模、交叉概率、變異概率、最大迭代步數(shù)等），3）改進(jìn)算法最后求得的34 個(gè)省會(huì)的最短路徑值、最優(yōu)個(gè)體和算法運(yùn)行時(shí)間，4）給出在相同的參數(shù)設(shè)置（種群規(guī)模、交叉概率、變異概率、最大迭代步數(shù)等）下，用基本遺傳算法（沒(méi)有使用改進(jìn)策略）求得的34 個(gè)省會(huì)的最短路徑值、最優(yōu)個(gè)體和算法運(yùn)行時(shí)間。

圖 1 ?中國(guó) 34 省會(huì)位置(1295.72)

表3 ?34個(gè)省會(huì)城市及像素坐標(biāo)表

x[0]=100, x[1]=187,x[2]=201,x[3]=187,x[4]=221,x[5]=202,x[6]=258,x[7]=352,x[8]=346,x[9]=336;

y[0]=211,y[1]=265,y[2]=214,y[3]=158,y[4]=142,y[5]=165,y[6]=121,y[7]=66,y[8]=85,y[9]=106;

x[10]=290,x[11]=297,x[12]=278,x[13]=296,x[14]=274,x[15]=265,x[16]=239,x[17]=302,x[18]=316,x[19]=334;

y[10]=127,y[11]=135,y[12]=147,y[13]=158,y[14]=177,y[15]=148,y[16]=182,y[17]=203,y[18]=199,y[19]=206;

x[20]=325,x[21]=293,x[22]=280,x[23]=271,x[24]=221,x[25]=233,x[26]=275,x[27]=322,x[28]=250, x[29]=277;

y[20]=215,y[21]=233,y[22]=216,y[23]=238,y[24]=253,y[25]=287,y[26]=285,y[27]=254,y[28]=315; y[29]=293;

x[30]=286, x[31]=342,x[32]=220,x[33]=104;

y[30]=290,y[31]=263,y[32]=226,y[33]=77;

3.1結(jié)果：

3.1.1這邊放了兩個(gè)實(shí)驗(yàn)結(jié)果，區(qū)別僅是初始起點(diǎn)不同

①繪制路徑如圖2（基于python，起點(diǎn)15）：

圖2 繪圖表示最優(yōu)解

最短路徑長(zhǎng)度1532.3994414550848

路徑表示：[23, 32, 24, 1, 2, 0, 33, 3, 5, 4, 12, 14, 16, 22, 21, 27, 31, 30, 26, 29, 28, 25, 20, 19, 18, 17, 13, 11, 9, 8, 7, 10, 6]

路徑長(zhǎng)度隨著迭代次數(shù)下降：

圖3 迭代次數(shù)和最優(yōu)解關(guān)系

②繪制路徑如圖（基于python，起點(diǎn)32）：

圖4繪圖表示最優(yōu)解

最短路徑長(zhǎng)度 ：1551.0699954694958

路徑表示：[1, 28, 25, 24, 18, 20, 19, 31, 27, 29, 30, 26, 23, 21, 22, 16, 14, 17, 13, 9, 8, 7, 11, 10, 12, 15, 6, 4, 5, 0, 33, 3, 2]

路徑長(zhǎng)度隨著迭代次數(shù)下降：

圖5最優(yōu)解和迭代次數(shù)關(guān)系

3.1.2

若不改進(jìn)，使用原先的程序，參數(shù)設(shè)置如下(基于C++)：

染色體長(zhǎng)度:34

最大迭代步數(shù):500

種群規(guī)模:100

交叉概率:0.5

變異概率0.15

選擇操作：按適應(yīng)度比例分配個(gè)體的選擇概率，輪盤賭選擇個(gè)體

交叉操作：PMX交叉

變異操作：相鄰兩點(diǎn)互換則

結(jié)果如圖6：

圖6結(jié)果

最優(yōu)路徑長(zhǎng)度為： 6246.62

路徑：32-20-18-21-28-29-26-24-13-30-12-10-31-33-2-3-1-7-9-4-15-11-0-5-8-6-17-16-23-25-19-22-27-14

運(yùn)行時(shí)間為：214.6s

可見(jiàn)，改進(jìn)算法還是比較很有效的。

3.2改進(jìn)算法策略及核心代碼：

①參數(shù)設(shè)定：
#種群數(shù)

count=300

#改良次數(shù)

improve_count=10000

#進(jìn)化次數(shù)

itter_time=3000

#設(shè)置強(qiáng)者的定義概率，即種群前30%為強(qiáng)者

retain_rate=0.3

#設(shè)置弱者的存活概率

random_select_rate=0.5

#變異率

mutation_rate=0.1

②路徑編碼：

對(duì)城市進(jìn)行編號(hào)0，1，2，3……33，染色體{x1,x2,x3....x33},表示從x1出發(fā)，依次經(jīng)過(guò)x2,x3....x33再回到x1的路徑，起點(diǎn)可任意設(shè)置，本程序中設(shè)為15.

③初始化種群：

為了加快程序的運(yùn)行速度，在初始種群的選取中要選取一些較優(yōu)秀的個(gè)體。先利用經(jīng)典的近似算法—改良圈算法求得一個(gè)較好的初始種群。算法思想是隨機(jī)生成一個(gè)染色體，比如{1，2，……33}，任意交換兩城市順序位置，如果總距離減小，則更新改變?nèi)旧w，如此重復(fù)，直至不能再做修改。

代碼：

#初始化種群

population = []

for i in range(count):

????# 隨機(jī)生成個(gè)體

????x = index.copy()

????random.shuffle(x)

????improve(x)

????population.append(x)

#改良

def improve(x):

????i=0

????distance=get_total_distance(x)

????while i<improve_count:

????????# randint [a,b]

????????u=random.randint(0,len(x)-1)

????????v = random.randint(0, len(x)-1)

????????if u!=v:

????????????new_x=x.copy()

????????????t=new_x[u]

????????????new_x[u]=new_x[v]

????????????new_x[v]=t

????????????new_distance=get_total_distance(new_x)

????????????if new_distance<distance:

????????????????distance=new_distance

????????????????x=new_x.copy()

????????else:

????????????continue

????????i+=1

④選擇策略：

雖然輪盤賭法是使用最多的選擇策略 ,但這種策略可能會(huì)產(chǎn)生較大的抽樣誤差 所以，這采用自然選擇，計(jì)算了每個(gè)城市之間的距離并存入了矩陣中，對(duì)總距離從小到大進(jìn)行排序，選出適應(yīng)性強(qiáng)的染色體，再選出適應(yīng)性不強(qiáng)，但是幸存的染色體（隨機(jī)選擇）。

核心代碼：

# 自然選擇

def selection(population):

????# 對(duì)總距離從小到大進(jìn)行排序

????graded = [[get_total_distance(x), x] for x in population]

????graded = [x[1] for x in sorted(graded)]

????# 選出適應(yīng)性強(qiáng)的染色體

????retain_length = int(len(graded) * retain_rate)

????parents = graded[:retain_length]

????# 選出適應(yīng)性不強(qiáng)，但是幸存的染色體

????for chromosome in graded[retain_length:]:

????????if random.random() < random_select_rate:

????????????parents.append(chromosome)

????return parents

⑤變異策略：

按照給定的變異率，對(duì)選定變異的個(gè)體，隨機(jī)地取三個(gè)整數(shù)，滿足 1<u<v<w<33?，把 v 、u之間（包括u 和v）的基因段插到w后面。替換原來(lái)的相鄰兩點(diǎn)互換變異，和兩點(diǎn)互換的變異策略。?

核心代碼：

#變異

def mutation(children):

????for i in range(len(children)):

????????if random.random() < mutation_rate:

????????????child=children[i]

????????????u=random.randint(1,len(child)-4)

????????????v = random.randint(u+1, len(child)-3)

????????????w= random.randint(v+1, len(child)-2)

????????????child=children[i]

????????????child=child[0:u]+child[v:w]+child[u:v]+child[w:]

4、提交實(shí)驗(yàn)報(bào)告和源程序。

三、實(shí)驗(yàn)結(jié)果：

實(shí)驗(yàn)內(nèi)容1結(jié)果：

表1 遺傳算法求解不同規(guī)模的TSP問(wèn)題的結(jié)果

實(shí)驗(yàn)內(nèi)容2結(jié)果：

表2 不同的變異策略和個(gè)體選擇概率分配策略的求解結(jié)果

實(shí)驗(yàn)內(nèi)容3結(jié)果，位于實(shí)驗(yàn)內(nèi)容3中：

路徑如圖2：

最短路徑長(zhǎng)度1532.3994414550848

路徑表示：[23, 32, 24, 1, 2, 0, 33, 3, 5, 4, 12, 14, 16, 22, 21, 27, 31, 30, 26, 29, 28, 25, 20, 19, 18, 17, 13, 11, 9, 8, 7, 10, 6]

四、實(shí)驗(yàn)思考及體會(huì)：

??1、分析遺傳算法求解不同規(guī)模的TSP問(wèn)題的算法性能。

城市規(guī)模越大，迭代數(shù)越大，搜索最優(yōu)解的時(shí)間也越長(zhǎng)，運(yùn)行等待結(jié)果的時(shí)間越久。

2、增加1種變異策略和1種個(gè)體選擇概率分配策略，比較求解30個(gè)城市的TSP問(wèn)題時(shí)不同變異策略及不同個(gè)體選擇分配策略對(duì)算法結(jié)果的影響。

增加了相鄰兩點(diǎn)變異和線性排序選擇個(gè)體：

變異策略：

void change1(vector<int>& K, int N){//變異策略：相鄰兩點(diǎn)互換變異

int i = next_int() % N;

swap(K[i], K[(i + 1) % N]);

}

個(gè)體選擇策略：

if(make_p==1)//線性排序

????{

????????for(int i=0;i<popsize;i++)

ps[i]=(200-2*i)/popsize*(popsize+1);

}

從實(shí)驗(yàn)結(jié)果看，線性排序較好，隨機(jī)兩點(diǎn)交換策略明顯優(yōu)于相鄰兩點(diǎn)交換策略。

3、比較分析遺傳算法的改進(jìn)策略對(duì)求解34個(gè)城市的TSP問(wèn)題的結(jié)果的影響。

主要是在適應(yīng)值選擇這塊做了比較大的改進(jìn)，優(yōu)先選擇了比較好的個(gè)體，又隨機(jī)選擇一部分差的個(gè)體，通過(guò)對(duì)一些參數(shù)和選擇和變異等方面改進(jìn)代碼，可以使的想要獲得的最優(yōu)解更優(yōu)，若不使用改進(jìn)，最后運(yùn)行可得的最優(yōu)解在7.8千左右，如圖7，精度遠(yuǎn)遠(yuǎn)不夠。

?

圖7 未改進(jìn)運(yùn)行結(jié)果

4.總結(jié)實(shí)驗(yàn)心得體會(huì)：

改進(jìn)策略還有很多，例如：

①使用貪心算法初始化群體，每個(gè)個(gè)體生成的基本思想是:首先隨機(jī)地從n個(gè)城市中選取-?-個(gè)城市ccurrent作為第1個(gè)基因，然后從余下的n-1個(gè)城市中找到城市cnext?(cnext?是距離ccurrent最近的城市)作為第2個(gè)基因，再?gòu)挠嘞碌膎-2個(gè)城市中找到城市cnext+1?(cnext+1?是距離cnext最近的城市)作為第3個(gè)基因，依次類推，直到遍歷n個(gè)城市為止。貪心算法生成的部分種群占比不大，在提高初始種群整體質(zhì)量的同時(shí)，不會(huì)影響初始種群的多樣性，有助于加速尋優(yōu)速度。由于不是很熟悉代碼，沒(méi)能成功改成貪心算法初始化種群。

②還可以把適應(yīng)度適當(dāng)放大，考慮小數(shù)部分，但是從實(shí)驗(yàn)運(yùn)行的結(jié)果看，意義并不大，最優(yōu)解比較的一般，距離還是挺大的。

③改進(jìn)交叉算子：基本遺傳算法常用的雙點(diǎn)交叉算子，這種交叉方式只是對(duì)父?jìng)€(gè)體兩點(diǎn)之間的基因進(jìn)行交叉，兩點(diǎn)區(qū)域外的基因要么不變，要么由于節(jié)點(diǎn)重復(fù)而盲目地改變，父?jìng)€(gè)體的優(yōu)良基因得不到有效繼承?？梢圆捎脙牲c(diǎn)三段隨機(jī)交叉。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-412035.html

未改進(jìn)源碼：

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<time.h>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define PB push_back
#define MP make_pair

int next_int()
{
	return rand()*(RAND_MAX+1)+rand();
}
double next_double()
{
	return (double(rand()*(RAND_MAX+1)+rand()))/((RAND_MAX+1)*RAND_MAX+RAND_MAX);
}
void pmx(VI& a,VI& b,int pointcnt)//PMX交叉
{
	int sa=next_int()%pointcnt,sb=next_int()%pointcnt;//隨機(jī)選擇兩交叉位
	int temp;
	if (sa>sb)
	{
		temp=sa;
		sa=sb;
		sb=temp;
	}//保證交叉位sa<=sb
	VI aa(pointcnt),bb(pointcnt);
	int i;	
	for(i=0;i<pointcnt;i++)
	{
		aa[i]=a[i],bb[i]=b[i];	
	}
	VI m1(pointcnt,-1);
	VI m2(pointcnt,-1);	
	VI v1tov2(pointcnt,-1);
	for(i=sa;i<=sb;i++)
	{   
		m1[aa[i]]=-2;	//m1存放aa非交叉段可代換的基因
		m2[bb[i]]=-2;	//m2存放aa非交叉段可代換的基因
	}	
	for(i=0;i<pointcnt;i++)	{   
		
		if(m2[i]==m1[i])//去掉m1和m2中重復(fù)代換的基因
		{
			m2[i]=-1;
			m1[i]=-1;
		}
	}
	int aaa=0;
	for(i=sa;i<=sb;i++)
	{
		if ((m1[aa[i]]==-2)&&(m2[bb[i]]==-2))
		{
			v1tov2[aa[i]]=bb[i];//v1tov2存放首先可以確定的互換基因
			m1[aa[i]]=-1;
			m2[bb[i]]=-1;
			aaa++;			
		}
	}
	if(aaa!=(sb-sa+1))
	{
		for(i=0;i<pointcnt;i++)	
			if (m1[i]==-2) 
			{
				int aflag=0;
				for(int j=0;j<pointcnt;j++)	
					if( (m2[j]==-2) && (aflag==0))//尋找并確定可以互換的基因
					{
						v1tov2[i]=j; 
						aflag=1;
						aaa++;
						m2[j]=-1;
						m1[i]=-1;					
					}
			}

	}
	for(i=sa;i<=sb;i++)	{	
	
		swap(aa[i],bb[i]);	//交換sa到sb之間的基因串
	}

	for(i=0;i<pointcnt;i++)//查找染色體aa中sa之前和sb之后的基因是否有重復(fù)
	{   
		if ((i<sa)||(i>sb))
			for (int j=sa;j<=sb;j++)
			{
				if(aa[i]==aa[j])  //有重復(fù)基因
				{  
					for(int k=0;k<pointcnt;k++)
						if(aa[i]==v1tov2[k])  
							aa[i]=k;	//進(jìn)行互換			
				
				}
			}
		
	}
		
	for(i=0;i<pointcnt;i++)//查找染色體bb中sa之前和sb之后的基因是否有重復(fù)
	{  
		if ((i<sa)||(i>sb))
			for (int j=sa;j<=sb;j++)
			{	
				if(bb[i]==bb[j]) //有重復(fù)基因			
					bb[i]=v1tov2[bb[i]];	//進(jìn)行互換				
			}
	
	}
	a=aa;
	b=bb;
	
}

vector<double> x,y;
double fitness(const VI& v,int pointcnt)//計(jì)算適應(yīng)度
{
	double r=0;
	for(int i=0;i<pointcnt;i++)
	{
		double dx=x[v[i]]-x[v[(i+1)%pointcnt]];
		double dy=y[v[i]]-y[v[(i+1)%pointcnt]];
		r+=sqrt(dx*dx+dy*dy);//個(gè)體的適應(yīng)度為相鄰兩城市之間的距離平方的平方根和
	}
	return 1.0/r;
}
void change0(vector<int>& K,int N)//變異策略:兩點(diǎn)互換
{
	int i=next_int()%N;
	int d=next_int()%(N-1);
	int j=(i+1+d)%N;
	swap(K[i],K[j]);
}


void change1(vector<int>& K, int N){//變異策略：相鄰兩點(diǎn)互換變異 
	int i = next_int() % N;
	swap(K[i], K[(i + 1) % N]);	
}



void mutate(VI& route,int mutate_type,int pointcnt)
{
	
	if(mutate_type==0)//兩點(diǎn)互換
		change0(route,pointcnt);	
	if(mutate_type==1)//相鄰兩點(diǎn)互換變異 
	    change1(route,pointcnt);
}



bool pair_dec(const pair<double,VI*>& a,const pair<double,VI*>& b)
{
	return a>b;
}

class other_population
{
public:
	int popsize,pointcnt;//種群規(guī)模,染色體長(zhǎng)度
	double pc,pm;//交叉概率,變異概率
	vector<pair<double,VI*> >pop;//種群
	pair<double,VI*> bestofpop;//最好個(gè)體
	int cross_type;//交叉類型
	int mutate_type;//變異類型
	int make_p;//個(gè)體概率分配策略類型
	int select_type;//個(gè)體選擇類型
	int toursize;//競(jìng)賽規(guī)模
	double bestp;//最好個(gè)體選擇概率
	other_population(int a,int b,int c,int f,int g,double d,double e,int h,double j,int m)
	{
		popsize=a,pointcnt=b,cross_type=c,mutate_type=f,make_p=g,pc=d,pm=e,toursize=h,bestp=j,select_type=m;
		for(int i=0;i<popsize;i++)//初始化種群
		{
			VI* v=new VI(pointcnt);
			for(int j=0;j<pointcnt;j++)
				(*v)[j]=j;
			random_shuffle(v->begin(),v->end());
			pop.PB(MP(fitness(*v,pointcnt),v));
		}
		sort(pop.begin(),pop.end(),pair_dec);
		bestofpop.first=pop[0].first;//初始時(shí)最好個(gè)體的適應(yīng)度
		bestofpop.second=new VI(*pop[0].second);//初始時(shí)最好個(gè)體的染色體
	}
	~other_population()
	{
		for(int i=0;unsigned(i)<pop.size();i++)
			delete pop[i].second;
		delete bestofpop.second;
	}
	void next()//產(chǎn)生下一代種群
	{
		vector<double> ps(popsize);
		if(make_p==0) //按適應(yīng)度比例分配個(gè)體的選擇概率
		{
			double sum=0;
			for(int i=0;i<popsize;i++)
				sum+=pop[i].first;//計(jì)算種群的適應(yīng)度和
			for(int i=0;i<popsize;i++)
				ps[i]=pop[i].first/sum;
		}	
		
		
		if(make_p==1)//線性排序 
	    {
	        for(int i=0;i<popsize;i++)
			ps[i]=(200-2*i)/popsize*(popsize+1);	
		}
	
		if(select_type==0)//輪盤賭選擇個(gè)體
		{
			vector<pair<double,VI*> > select_res;
			vector<double> addsum(popsize);
			for(int i=0;i<popsize-1;i++)//計(jì)算個(gè)體的累計(jì)概率
			{
				if(i==0)
					addsum[i]=ps[0];
				else
					addsum[i]=addsum[i-1]+ps[i];
			}
			addsum[popsize-1]=1;//1.5;
			for(int i=0;i<popsize;i++)
			{
				double rd=next_double();
				int r=lower_bound(addsum.begin(),addsum.end(),rd)-addsum.begin();
				VI* v=new VI(*pop[r].second);
				select_res.PB(MP(fitness(*v,pointcnt),v));
			}
			for(int i=0;i<popsize;i++)
				delete pop[i].second;
			pop=select_res;
		}		
		for(int cc=0;cc<popsize/2;cc++)//隨機(jī)選擇兩個(gè)個(gè)體,然后進(jìn)行交叉
		{
			int a=next_int()%popsize;
			int b=(a+1+(next_int()%(popsize-1)))%popsize;
			if(next_double()<pc)//隨機(jī)數(shù)小于交叉概率,進(jìn)行交叉
			{
				if(cross_type==0)//pmx交叉
					pmx(*pop[a].second,*pop[b].second,pointcnt);
			
				pop[a].first=fitness(*pop[a].second,pointcnt);//計(jì)算交叉后個(gè)體a的適應(yīng)度
				if(bestofpop.first<pop[a].first)//更新最好個(gè)體
				{
					bestofpop.first=pop[a].first;
					delete bestofpop.second;
					bestofpop.second=new VI(*pop[a].second);
				}
				pop[b].first=fitness(*pop[b].second,pointcnt);//計(jì)算交叉后個(gè)體b的適應(yīng)度
				if(bestofpop.first<pop[b].first)//更新最好個(gè)體
				{
					bestofpop.first=pop[b].first;
					delete bestofpop.second;
					bestofpop.second=new VI(*pop[b].second);
				}
			}
		}
		for(int i=pop.size()-1;i>=0;i--)//進(jìn)行變異
			if(next_double()<pm)//隨機(jī)數(shù)小于變異概率,進(jìn)行變異
			{
				mutate(*pop[i].second,mutate_type,pointcnt);//變異
				pop[i].first=fitness(*pop[i].second,pointcnt);//計(jì)算變異后個(gè)體的適應(yīng)度
			}
		sort(pop.begin(),pop.end(),pair_dec);//從大到小排序
		if(bestofpop.first<pop[0].first)//更新最好個(gè)體
		{
			delete bestofpop.second;
			bestofpop.first=pop[0].first;
			bestofpop.second=new VI(*pop[0].second);
		}
	}
};

int main()
{
	srand((unsigned)time(NULL));
	int CASNUM,POINTCNT,POPSIZE,GENERATIONS;
	//scanf("%d",&CASNUM);//輸入實(shí)驗(yàn)次數(shù)
	CASNUM=10;//輸入實(shí)驗(yàn)次數(shù)
	cout << "實(shí)驗(yàn)次數(shù):" << CASNUM << "次" << endl;
	//scanf("%d%d%d",&POINTCNT,&POPSIZE,&GENERATIONS);//輸入染色體長(zhǎng)度（城市數(shù)），種群規(guī)模，最大迭代步數(shù)
	POINTCNT=30;//輸入染色體長(zhǎng)度（城市數(shù)）
	POPSIZE=100,GENERATIONS=100;//輸入種群規(guī)模，最大迭代步數(shù)
	x.resize(POINTCNT);
	y.resize(POINTCNT);
//	x[0]=0, x[1]=1.1,x[2]=3.5,x[3]=3,x[4]=7,x[5]=8,x[6]=4,x[7]=4.5,x[8]=9,x[9]=2;
	//x[10]=10, x[11]=11.1,x[12]=13.5,x[13]=13,x[14]=17,x[15]=18,x[16]=14,x[17]=14.5,x[18]=19,x[19]=12;
//	y[0]=1.1,y[1]=3,y[2]=2,y[3]=4,y[4]=5.1,y[5]=8,y[6]=4,y[7]=4.5,y[8]=9,y[9]=2;
	//y[10]=11.1,y[11]=13,y[12]=12,y[13]=14,y[14]=15.1,y[15]=18,y[16]=14,y[17]=14.5,y[18]=19,y[19]=12;
	
x[0]=41, x[1]=37,x[2]=54,x[3]=25,x[4]=7,x[5]=2,x[6]=68,x[7]=71,x[8]=54,x[9]=83;
y[0]=94,y[1]=84,y[2]=67,y[3]=62,y[4]=64,y[5]=99,y[6]=58,y[7]=44,y[8]=62,y[9]=69;
x[10]=64,x[11]=18,x[12]=22,x[13]=83,x[14]=91,x[15]=25,x[16]=24,x[17]=58,x[18]=71,x[19]=74;
y[10]=60,y[11]=54,y[12]=60,y[13]=46,y[14]=38,y[15]=38,y[16]=42,y[17]=69,y[18]=71,y[19]=78;
x[20]=87,x[21]=18,x[22]=13,x[23]=82,x[24]=62,x[25]=58,x[26]=45,x[27]=41,x[28]=44, x[29]=4;
y[20]=76,y[21]=40,y[22]=40,y[23]=7,y[24]=32,y[25]=35,y[26]=21,y[27]=26,y[28]=35; y[29]=50;

	
	cout<<"城市數(shù)="<<POINTCNT<<endl;
	cout<<"各城市坐標(biāo):"<<endl;
	//srand((unsigned)time(NULL));
/*	for(int i=10;i<POINTCNT;i++)
	{
		x[i]=next_int()%1000;y[i]=next_int()%1000;
	}*/
	for(int i=0;i<POINTCNT;i++)
	{
		//scanf("%lf%lf",&x[i],&y[i]);//輸入各個(gè)城市的坐標(biāo)		
		cout<<"["<<x[i]<<", "<<y[i]<<"]"<<endl;//輸出各個(gè)城市的坐標(biāo)				
	}
	cout<<"染色體長(zhǎng)度:"<<POINTCNT<<endl;
	cout<<"最大迭代步數(shù):"<<GENERATIONS<<endl;
	cout<<"種群規(guī)模:"<<POPSIZE<<endl;
	int select_type,make_p_type,k,cross_type,mutate_type;
	double q,pc,pm;
	
	select_type=0,make_p_type=1,k=5;//輸入個(gè)體選擇方法類型，個(gè)體選擇概率分配類型，競(jìng)賽規(guī)模
	q=0.5,pc=0.8,pm=0.8;//輸入最好個(gè)體選擇概率，交叉概率，變異概率
	cross_type=0,mutate_type=0;//輸入交叉類型，變異類型
	
	
	cout<<"交叉概率:"<<pc<<endl;
	cout<<"變異概率"<<pm<<endl;
	cout<<"選擇操作：按適應(yīng)度比例分配個(gè)體的選擇概率，輪盤賭選擇個(gè)體"<<endl;
	cout<<"交叉操作：PMX交叉"<<endl;
	cout<<"變異操作：兩點(diǎn)互換"<<endl;
	double best=1e9,worst=0,sum=0;
	VI res;
	clock_t start_time;
	start_time=clock();
	cout << endl;
	cout << "正在計(jì)算中......" << endl;
	for(int cas=0;cas<CASNUM;cas++)//
	{
		other_population gen(POPSIZE,POINTCNT,cross_type,mutate_type,make_p_type,pc,pm,k,q,select_type);
	
		for(int g=0;g<GENERATIONS;g++)//進(jìn)行迭代進(jìn)化
			gen.next();
		if(best>1.0/gen.bestofpop.first)//更新最好適應(yīng)度
		{
			best=1.0/gen.bestofpop.first;
			res=*gen.bestofpop.second;//存放最好個(gè)體的染色體
		}
		if(worst<1.0/gen.bestofpop.first)//更新最差適應(yīng)度
			worst=1.0/gen.bestofpop.first;
		sum+=1.0/gen.bestofpop.first;//計(jì)算各次最好個(gè)體的適應(yīng)度之和
	}
	cout << endl; 
	cout << CASNUM << "次遺傳算法求解的結(jié)果如下：" << endl;
	clock_t	end_time=clock();
	double durTime=double(end_time-start_time);	
	sum/=CASNUM;//計(jì)算平均適應(yīng)度
	cout<<"最好適應(yīng)度："<<best<<"\n"<<"最差適應(yīng)度："<<worst<<"\n"<<"平均適應(yīng)度："<<sum<<"\n";
	cout<<"輸出最好解：";
	for(int i=0;i<POINTCNT;i++)//輸出解
	{
		cout<<res[i];//輸出各城市
		if (i<POINTCNT-1)
			cout<<"-";
	}
	cout<<endl;
	cout<<"平均運(yùn)行時(shí)間："<<durTime/CASNUM<<"s"<<endl;
	cout<<endl;

	return 0;
}

到了這里，關(guān)于人工智能導(dǎo)論——遺傳算法求解TSP問(wèn)題實(shí)驗(yàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！