C++算法之使用遺傳算法解決旅商問題

1、旅商問題

         旅行商問題，即TSP問題（Traveling Salesman Problem）是數學領域中著名問題之一。 

         假設有一個旅行商人要拜訪N個城市，他必須選擇所要走的路徑，路徑的限制是每個城市隻能拜訪一次，而且最後要回到原來出發的城市。 

         路徑的選擇目标是要求得的路徑路程為所有路徑之中的最小值。

2、實作思路

         旅商問題的實質就是遺産思想，每一種周遊順序都是一個解。所有城市順序的全排列合在一起就是這個問題的解集。 我們将每個解都看做一個個體。那麼多個個體放在一起就可以構成一個種群。 大自然每個種群都要經過漫長的自然選擇，也就是優勝劣汰，以及繁殖和變異。 而解所構成的種群也不例外。 顯然，我們可以很明确的對每個個體的優劣性進行評價。本體的條件是總路程最短，根據解得到總路程的大小是很容易的。 評價過後，對于每個個體的優劣我們都已掌握。 那麼殘酷的地方來了，我們要殺死(淘汰)一部分個體。 當然也不能光殺，溫馨的部分也是有的，那就是兩兩個體交叉繁殖，産生後代。 除此之外，還要有一點幸運度，那就是變異了，随機的對某些個體進行一些改變。 上述操作進行完之後，我們已經相當于更新了整個群體。 然後重複的進行此過程，直到得到滿意的(個體)結果。具體思路如圖1-1所示：

3、代碼實作如下：

// GeneticAlgorithm.cpp : 定義控制台應用程式的入口點。
//

#include "stdafx.h"


#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

const int city_num = 10;//城市數量
const int unit_num = 100;//群體規模
int ps = 10;//變異機率
const int genmax = 500;//最大疊代數

					   //城市間距離映射 最優解權值=10
int length_table[10][10] = {

	{ 0,1,1272,2567,1653,2097,1425,1177,3947,1 },

	{ 1,0,1,2511,1633,2077,1369,1157,3961,1518 },

	{ 1272,1,0,1,380,1490,821,856,3660,385 },

	{ 2567,2511,1,0,1,2335,1562,2165,3995,933 },

	{ 1653,1633,380,1,0,1,1041,1135,3870,456 },

	{ 2097,2077,1490,2335,1,0,1,920,2170,1920 },

	{ 1425,1369,821,1562,1041,1,0,1,4290,626 },

	{ 1177,1157,856,2165,1135,920,1,0,1,1290 },

	{ 3947,3961,3660,3995,3870,2170,4290,1,0,1 },

	{ 1,1518,385,993,456,1920,626,1290,1,0 }
};

class Unit
{
public:
	int path[city_num];//個體的路徑資訊
	int length;//個體價值
};

class Group
{
public:
	Unit group[unit_num];
	Unit best;
	int best_gen;

	Group()
	{
		best.length = 0x3f3f3f3f;
		best_gen = 0;
		for (int i = 0; i < unit_num; i++)
		{
			bool flag[city_num] = {};

			for (int j = 0; j < city_num; j++)
			{
				int t_city = rand() % city_num;
				while (flag[t_city])
					t_city = rand() % city_num;
				flag[t_city] = true;
				group[i].path[j] = t_city;
			}
		}
	}

	//對每個個體進行評估
	void assess()
	{
		for (int k = 0; k < unit_num; k++)
		{
			int rel = 0;
			for (int i = 1; i < city_num; i++)
				rel += length_table[group[k].path[i - 1]][group[k].path[i]];
			rel += length_table[group[k].path[city_num - 1]][group[k].path[0]];
			group[k].length = rel;
		}
	}

	//根據評估結果對個體進行排序
	void unit_sort()
	{
		for (int i = 0; i < unit_num; i++)
		{
			for (int j = i + 1; j < unit_num; j++)
			{
				if (group[i].length > group[j].length)
				{
					Unit temp;
					memcpy(&temp, &group[i], sizeof(Unit));
					memcpy(&group[i], &group[j], sizeof(Unit));
					memcpy(&group[j], &temp, sizeof(Unit));
				}
			}
		}
	}

	//交叉
	Unit cross(Unit &father, Unit &mother)
	{
		int l = rand() % city_num;
		int r = rand() % city_num;
		if (l > r)
			swap(l, r);

		bool flag[city_num] = {};
		for (int i = l; i <= r; i++)
			flag[father.path[i]] = true;

		Unit son;
		int pos = 0;

		for (int i = 0; i < l; i++)
		{
			while (flag[mother.path[pos]])
				pos++;
			son.path[i] = mother.path[pos++];
		}
		for (int i = l; i <= r; i++)
			son.path[i] = father.path[i];
		for (int i = r + 1; i < city_num; i++)
		{
			while (flag[mother.path[pos]])
				pos++;
			son.path[i] = mother.path[pos++];
		}

		return son;
	}

	//突變
	void mutation(Unit &t)
	{
		int proport = rand() % 100;

		if (proport > ps)
			return;
		int one = rand() % city_num;
		int two = rand() % city_num;
		while (two != one)
			two = rand() % city_num;
		swap(t.path[one], t.path[two]);
	}

	//輸出資訊
	void print()
	{
		for (int i = 0; i < unit_num; i++)
		{
			printf("第%d個個體，路徑資訊：", i);
			for (int j = 0; j < city_num; j++)
				printf("%d ", group[i].path[j]);

			printf(";總權值：%d;\n", group[i].length);
		}
		printf("最優個體，路徑資訊：");
		for (int j = 0; j < city_num; j++)
			printf("%d ", group[0].path[j]);

		printf(";總權值：%d;\n", group[0].length);
	}

	//種群進化
	void work()
	{
		for (int i = 0; i < genmax; i++)
		{
			//如果進化層數大于20，加大變異的機率
			if (i > 20)
				ps *= 3;

			assess();//評估

			unit_sort();//根據評估結果排序

			if (best.length > group[0].length)
			{
				memcpy(&best, &group[0], sizeof(group[0]));
				best_gen = i;
			}

			for (int j = 0; j + 2 < unit_num; j += 3)
				group[j + 2] = cross(group[j], group[j + 1]);

			for (int j = 0; j < city_num; j++)//變異(從1開始，保留最優)
				mutation(group[j]);
		}
	}

};

Unit group[unit_num];//種群變量
Unit bestone;//記錄最短路徑
int generation_num;//記錄目前達到了第幾代



int main()
{
	srand((int)time(0));

	for (int i = 0; i < 20; i++)
	{
		Group g;
		g.work();
		printf("第%d次求解。路徑：", i + 1);
		for (int j = 0; j < city_num; j++)
			printf("%d ", g.best.path[j]);

		printf(";總權值：%d; 第%d代;\n", g.best.length, g.best_gen);
	}
	return 0;
}
           

程式效果：

       交叉方式有很多種，對于不同的問題，交叉方式的不同對于求解會有一定的影響。 變異同理， 這裡也是最普通最常用的方式。

       父個體：1 2 3 4 9 8 7 6 5 0 母個體：7 8 9 0 1 6 5 4 3 2 那麼随機取兩個值，比如：4和6 将父個體劃分：1 2 3 [4 9] 8 7 6 5 0 則，将劃分區間内的基因賦給子個體 子個體：x x x 4 9 x x x x x 再按照母個體的基因順序指派給子個體 子個體：7 8 0 4 9 1 6 5 3 2。

       個體： 1 2 3 4 9 8 7 6 5 0 還是随機選取兩個值，比如：4和6 那麼，交換位置4和位置6的基因。 新個體：1 2 3 8 9 4 7 6 5 0