巡回セールスマン問題を遺伝的アルゴリズムによりC++で解いてみました。
全部で1000個体の遺伝子集団を作り、足切りライン（Cut Line）を100に設定しています。
足切りラインより上の個体は残すようにして、足切りラインより下の900個体は、足切りラインより上の二つの親個体から作成した子の個体に置き換えます。
そして1000の個体を巡回経路が短い順に並べ替え、足切りラインより上の上位100個体を再び親個体として使用しています。
図1は初期経路であり、図2は最終経路、図3は途中経過です。
GeneticAlgorithm1.cppは一点交叉のプログラムであり、GeneticAlgorithm2.cppは二点交叉のものです。
親の遺伝子はそのまま使用するのではなく、二分の一の確率で逆向きに並べ替え、またランダムに選んだ数だけ遺伝子をシフト（回転）させています。
突然変異にはランダムに選んだ二か所の町の番号の交換を採用しましたが、もっと効率的なものも考えられると思います。
図4で一点交叉と二点交叉の比較を行ってみましたが、二点交叉の方が若干有利な結果でした。初期経路や町の数によっても結果は違ってくると思うので、あくまで参考程度ですが。
なお、私は論文などは特に読んでいないので、アルゴリズムはかなり適当です。
参考にさせていただいたサイト
「最適解を模索する遺伝的アルゴリズム」
http://www6.plala.or.jp/mnagaku/cmag/ac19999/
図1 初期経路（n=100、L=5446.6）
図2 最終経路（一点交叉、n=100、L=791.5）
図3 途中経過（一点交叉）
図4
一点交叉
840.764896544228
809.985133390297
824.479752257734
839.591099139721
804.08590570815
830.25785788914
801.1679438918
791.207287666002
799.970789499639
836.819367465269
平均：817.83
二点交叉
800.236706434746
821.815569751878
792.357286501806
791.207287666002
840.282503832847
819.322260000916
804.769704393913
786.997600141353
804.102703291302
819.064208487228
平均：808.02
GeneticAlgorithm1.cpp
// Ggenetic Algorithm (一点交叉)
#include <iostream>
using namespace std;
#define NUM_TOWN 20 // 町の数
#define AREA_SCALE 100.0 // 町が存在するエリアの大きさ（正方形の一辺の長さ）
#define ITERATION 1000 // 繰り返し回数
double town_map[NUM_TOWN][2]; // 町のx, y座標
int route[NUM_TOWN]; // 巡回経路
double length; // 巡回経路の総距離
// ルートの中の二つの町の行く順番を交換
void swap(int* route1, int i, int j)
{
int tmp = route1[i];
route1[i] = route1[j];
route1[j] = tmp;
}
// 町の座標をランダムに生成
void create_random_map()
{
for (int i = 0; i < NUM_TOWN; i++)
for (int j = 0; j < 2; j++)
town_map[i][j] = AREA_SCALE * (double)rand() / ((double)RAND_MAX + 1);
}
// 都市間の距離を計算
double calc_dist(int i, int j)
{
double dx = town_map[i][0] - town_map[j][0];
double dy = town_map[i][1] - town_map[j][1];
double dist = sqrt(dx * dx + dy * dy);
return dist;
}
// 指定された巡回経路の長さを計算
double calc_length(int route1[])
{
double sum_dist = 0.0;
for (int i = 0; i < NUM_TOWN; i++)
sum_dist += calc_dist(route1[i], route1[(i + 1) % NUM_TOWN]);
return sum_dist;
}
// 巡回経路の初期化
void init_route()
{
// 巡回経路の初期化
for (int i = 0; i < NUM_TOWN; i++)
route[i] = i;
length = calc_length(route);
}
// 巡回経路と総距離の出力
void print_route()
{
for (int i = 0; i < NUM_TOWN; i++)
cout << route[i] + 1 << " ";
cout << endl;
length = calc_length(route);
cout << "Total Distance: " << length << endl;
}
// 町の座標を出力
void print_town_map()
{
for (int i = 0; i < NUM_TOWN; i++) {
cout << route[i] + 1 << " ";
cout << town_map[route[i]][0] << " " << town_map[route[i]][1] << endl;
}
}
int POPULATION_COUNT = 1000; // 集団の大きさ（個体数）
int CUT_LINE = 100; // 足切りライン。この順位以下の個体は淘汰される
double MUTATION_ODDS = 0.05; // 突然変異を起こす確率
// 0より大きく1より小さな乱数の生成
double get_random()
{
return ((double)rand() + 0.5) / ((double)RAND_MAX + 1.0);
}
// 巡回ルートのコピー
void copy_route(int route_dest[], int route_source[])
{
for (int i = 0; i < NUM_TOWN; i++)
route_dest[i] = route_source[i];
}
// INDIVIDUAL：個体データ
// 個体は都市間を移動する経路(pathway)で表現され、その経路から算出される
// 巡回経路長（length）で評価される
class INDIVIDUAL
{
protected:
public:
int* pathway; // 巡回経路[NUM_TOWN]
double length; // 巡回経路の長さ
INDIVIDUAL();
~INDIVIDUAL();
int get_pathway(int); // 巡回経路のtarget番目の町の番号を取得する
void set_length(double); // 巡回経路の長さを設定する
double get_length(); // 巡回経路の長さを取得する
};
// 遺伝的アルゴリズムのクラス
class TSP_GENE
{
protected:
INDIVIDUAL** population; // 対象となる集団の実体
public:
TSP_GENE(); // 初期化を行う関数
~TSP_GENE();
void create_population(); // 遺伝子集団の作成
void delete_population(); // 遺伝子集団の削除
void initialize_population(); // 遺伝子集団の初期化
// 親の遺伝子を1/2の確率で逆回りに並び変える
void reverse_parent(int parent1[], int parent2[]);
// 親の遺伝子をランダムに一定数シフト（回転）させる
void rotate_parent(int parent1[], int parent2[]);
// 遺伝子の一点交叉
void one_point_cross(int route[], int parent1[], int parent2[]);
// 2つの個体から遺伝子の交差によって新しい個体を作成
void cross_over(int route_new[], int parent1[], int parent2[]);
void mutation(int route[]); // 個体の突然変異体を作成
void ga_ranking(); // 各個体の巡回経路長を計算し短い順にソート
double solve(); // 遺伝的アルゴリズムで解く
int* get_route(int i) { return population[i]->pathway; }
};
TSP_GENE* pTspGene = nullptr;
INDIVIDUAL::INDIVIDUAL()
{
// 巡回経路の生成
pathway = new int[NUM_TOWN];
}
INDIVIDUAL::~INDIVIDUAL()
{
if (pathway != nullptr) {
delete []pathway;
pathway = nullptr;
}
}
// 巡回経路のtarget番目の町の番号を取得する
int INDIVIDUAL::get_pathway(int target)
{
return pathway[target];
}
// 巡回経路の長さを設定する
void INDIVIDUAL::set_length(double length1)
{
length = length1;
}
// 巡回経路の長さを取得する
double INDIVIDUAL::get_length()
{
return length;
}
TSP_GENE::TSP_GENE()
{
create_population();
initialize_population();
}
TSP_GENE::~TSP_GENE()
{
delete_population();
}
// 遺伝子集団の作成
void TSP_GENE::create_population()
{
// 遺伝子集団のメモリ領域を確保
population = new INDIVIDUAL*[POPULATION_COUNT];
for (int i = 0; i < POPULATION_COUNT; i++)
population[i] = new INDIVIDUAL;
}
// 遺伝子集団の削除
void TSP_GENE::delete_population()
{
if (population != nullptr) {
for (int i = 0; i < POPULATION_COUNT; i++)
delete population[i];
delete []population;
population = nullptr;
}
}
// 遺伝子集団の初期化
void TSP_GENE::initialize_population()
{
// 遺伝子集団の初期状態を生成する。
for (int i = 0; i < POPULATION_COUNT; i++)
for (int j = 0; j < NUM_TOWN; j++)
population[i]->pathway[j] = j;
// 遺伝子をランダムにシャッフルする
for (int i = 0; i < POPULATION_COUNT; i++) {
for (int j = 0; j < NUM_TOWN; j++) {
int rnd1 = rand() % NUM_TOWN;
int tmp = population[i]->pathway[j];
population[i]->pathway[j] = population[i]->pathway[rnd1];
population[i]->pathway[rnd1] = tmp;
}
}
}
// 親の遺伝子を1/2の確率で逆回りに並び変える
void TSP_GENE::reverse_parent(int parent1[], int parent2[])
{
bool back_reverse1 = (rand() % 2) == 0;
if (back_reverse1 == true) {
int* pa1 = new int[NUM_TOWN];
copy_route(pa1, parent1);
for (int i = 0; i < NUM_TOWN; i++) {
parent1[i] = pa1[NUM_TOWN - 1 - i];
parent1[NUM_TOWN - 1 - i] = pa1[i];
}
delete []pa1;
}
bool back_reverse2 = (rand() % 2) == 0;
if (back_reverse2 == true) {
int* pa2 = new int[NUM_TOWN];
copy_route(pa2, parent2);
for (int i = 0; i < NUM_TOWN; i++) {
parent2[i] = pa2[NUM_TOWN - 1 - i];
parent2[NUM_TOWN - 1 - i] = pa2[i];
}
delete []pa2;
}
}
// 親の遺伝子をランダムに一定数シフト（回転）させる
void TSP_GENE::rotate_parent(int parent1[], int parent2[])
{
int* pa1 = new int[NUM_TOWN];
int* pa2 = new int[NUM_TOWN];
copy_route(pa1, parent1);
copy_route(pa2, parent2);
int rotate1 = rand() % NUM_TOWN;
int rotate2 = rand() % NUM_TOWN;
for (int i = 0; i < NUM_TOWN; i++) {
parent1[i] = pa1[(i + rotate1) % NUM_TOWN];
parent2[i] = pa2[(i + rotate2) % NUM_TOWN];
}
delete []pa1;
delete []pa2;
}
// 遺伝子の一点交叉
void TSP_GENE::one_point_cross(int route[], int parent1[], int parent2[])
{
// 交差位置を乱数で決定
int cross_point = rand() % (NUM_TOWN - 1) + 1;
// 染色体の前半をsource1からコピー
for (int j = 0; j < cross_point; j++)
route[j] = parent1[j];
// 染色体の後半をsource2からコピー
for (int j = cross_point; j < NUM_TOWN; j++)
route[j] = parent2[j];
// 染色体中の都市が重複した場合に重複をなくす
for (int j = cross_point; j < NUM_TOWN; j++) {
bool conflict = true;
while (conflict == true) {
conflict = false;
for (int k = 0; k < cross_point; k++) {
if (route[j] == route[k]) {
route[j] = parent2[k];
conflict = true;
break;
}
}
}
}
}
// 遺伝子の交叉（クロスオーバー）
void TSP_GENE::cross_over(int route_new[], int parent1[], int parent2[])
{
reverse_parent(parent1, parent2);
rotate_parent(parent1, parent2);
one_point_cross(route_new, parent1, parent2);
}
// 個体の突然変異体を作る
void TSP_GENE::mutation(int route[])
{
// 染色体の2ヶ所をランダムに選んで交換
int rnd1 = rand() % NUM_TOWN;
int rnd2 = rand() % NUM_TOWN;
int tmp = route[rnd1];
route[rnd1] = route[rnd2];
route[rnd2] = tmp;
}
// 各個体の巡回経路の長さを計算し短い順に並べ替える
void TSP_GENE::ga_ranking()
{
// 各個体の巡回経路長を計算
for (int i = 0; i < POPULATION_COUNT; i++)
population[i]->length = calc_length(population[i]->pathway);
// 巡回経路長が短い個体ほど上位にくるように並び替える
for (int i = 0; i < POPULATION_COUNT - 1; i++) {
for (int j = i + 1; j < POPULATION_COUNT; j++) {
if (population[i]->length > population[j]->length) {
INDIVIDUAL* tmp = population[i];
population[i] = population[j];
population[j] = tmp;
}
}
}
}
double TSP_GENE::solve()
{
// 親の遺伝子を入れるための配列の作成
int* parent1 = new int[NUM_TOWN];
int* parent2 = new int[NUM_TOWN];
// 集団は順位付けられているものとし、CUT_LINEより上の優秀な
// 個体から親の遺伝子を二つ選び、遺伝子の交差によって子供の個体を生成し
// CUT_LINEより下の個体を置き換える
for (int i = CUT_LINE; i < POPULATION_COUNT; i++) {
int source1 = rand() % CUT_LINE;
int source2 = rand() % CUT_LINE;
copy_route(parent1, population[source1]->pathway); // 親の遺伝子1の作成
copy_route(parent2, population[source2]->pathway); // 親の遺伝子2の作成
cross_over(population[i]->pathway, parent1, parent2); // 遺伝子の交叉
// MUTATION_ODDSの確率で突然変異を起こす
if (get_random() < MUTATION_ODDS)
mutation(population[i]->pathway);
}
ga_ranking(); // 巡回経路の短い順に並び変える
delete []parent1;
delete []parent2;
return population[0]->length;
}
void calc_genetic_algorithm()
{
for (int i = 0; i < ITERATION; i++) {
double length_new = pTspGene->solve();
// 最短の巡回経路長が更新されたら、経路と経路長を保存する
if (length_new < length) {
length = length_new;
copy_route(route, pTspGene->get_route(0));
}
}
}
int main()
{
unsigned int seed = (unsigned)time(NULL);
cout << "Seed = " << seed << endl;
srand(seed);
create_random_map();
init_route();
cout << "Number of town: " << NUM_TOWN << endl;
cout << endl << "Town map" << endl;
print_town_map();
cout << endl << "First root" << endl;
print_route();
pTspGene = new TSP_GENE;
calc_genetic_algorithm();
cout << endl << "Last root" << endl;
print_route();
delete pTspGene;
return 0;
}
GeneticAlgorithm2.cpp
// Ggenetic Algorithm (二点交叉)
#include <iostream>
using namespace std;
#define NUM_TOWN 20 // 町の数
#define AREA_SCALE 100.0 // 町が存在するエリアの大きさ（正方形の一辺の長さ）
#define ITERATION 1000 // 繰り返し回数
double town_map[NUM_TOWN][2]; // 町のx, y座標
int route[NUM_TOWN]; // 巡回経路
double length; // 巡回経路の総距離
// ルートの中の二つの町の行く順番を交換
void swap(int* route1, int i, int j)
{
int tmp = route1[i];
route1[i] = route1[j];
route1[j] = tmp;
}
// 町の座標をランダムに生成
void create_random_map()
{
for (int i = 0; i < NUM_TOWN; i++)
for (int j = 0; j < 2; j++)
town_map[i][j] = AREA_SCALE * (double)rand() / ((double)RAND_MAX + 1);
}
// 都市間の距離を計算
double calc_dist(int i, int j)
{
double dx = town_map[i][0] - town_map[j][0];
double dy = town_map[i][1] - town_map[j][1];
double dist = sqrt(dx * dx + dy * dy);
return dist;
}
// 指定された巡回経路の長さを計算
double calc_length(int route1[])
{
double sum_dist = 0.0;
for (int i = 0; i < NUM_TOWN; i++)
sum_dist += calc_dist(route1[i], route1[(i + 1) % NUM_TOWN]);
return sum_dist;
}
// 巡回経路の初期化
void init_route()
{
// 巡回経路の初期化
for (int i = 0; i < NUM_TOWN; i++)
route[i] = i;
length = calc_length(route);
}
// 巡回経路と総距離の出力
void print_route()
{
for (int i = 0; i < NUM_TOWN; i++)
cout << route[i] + 1 << " ";
cout << endl;
length = calc_length(route);
cout << "Total Distance: " << length << endl;
}
// 町の座標を出力
void print_town_map()
{
for (int i = 0; i < NUM_TOWN; i++) {
cout << route[i] + 1 << " ";
cout << town_map[route[i]][0] << " " << town_map[route[i]][1] << endl;
}
}
int POPULATION_COUNT = 1000; // 集団の大きさ（個体数）
int CUT_LINE = 100; // 足切りライン。この順位以下の個体は淘汰される
double MUTATION_ODDS = 0.05; // 突然変異を起こす確率
// 0より大きく1より小さな乱数の生成
double get_random()
{
return ((double)rand() + 0.5) / ((double)RAND_MAX + 1.0);
}
// 巡回ルートのコピー
void copy_route(int route_dest[], int route_source[])
{
for (int i = 0; i < NUM_TOWN; i++)
route_dest[i] = route_source[i];
}
// INDIVIDUAL：個体データ
// 個体は都市間を移動する経路(pathway)で表現され、その経路から算出される
// 巡回経路長（length）で評価される
class INDIVIDUAL
{
protected:
public:
int* pathway; // 巡回経路[NUM_TOWN]
double length; // 巡回経路の長さ
INDIVIDUAL();
~INDIVIDUAL();
int get_pathway(int); // 巡回経路のtarget番目の町の番号を取得する
void set_length(double); // 巡回経路の長さを設定する
double get_length(); // 巡回経路の長さを取得する
};
// 遺伝的アルゴリズムのクラス
class TSP_GENE
{
protected:
INDIVIDUAL** population; // 対象となる集団の実体
public:
TSP_GENE(); // 初期化を行う関数
~TSP_GENE();
void create_population(); // 遺伝子集団の作成
void delete_population(); // 遺伝子集団の削除
void initialize_population(); // 遺伝子集団の初期化
// 親の遺伝子を1/2の確率で逆回りに並び変える
void reverse_parent(int parent1[], int parent2[]);
// 親の遺伝子をランダムに一定数シフト（回転）させる
void rotate_parent(int parent1[], int parent2[]);
// 遺伝子の二点交叉
void two_point_cross(int route[], int parent1[], int parent2[]);
// 2つの個体から遺伝子の交差によって新しい個体を作成
void cross_over(int route_new[], int parent1[], int parent2[]);
void mutation(int route[]); // 個体の突然変異体を作成
void ga_ranking(); // 各個体の巡回経路長を計算し短い順にソート
double solve(); // 遺伝的アルゴリズムで解く
int* get_route(int i) { return population[i]->pathway; }
};
TSP_GENE* pTspGene = nullptr;
INDIVIDUAL::INDIVIDUAL()
{
// 巡回経路の生成
pathway = new int[NUM_TOWN];
}
INDIVIDUAL::~INDIVIDUAL()
{
if (pathway != nullptr) {
delete []pathway;
pathway = nullptr;
}
}
// 巡回経路のtarget番目の町の番号を取得する
int INDIVIDUAL::get_pathway(int target)
{
return pathway[target];
}
// 巡回経路の長さを設定する
void INDIVIDUAL::set_length(double length1)
{
length = length1;
}
// 巡回経路の長さを取得する
double INDIVIDUAL::get_length()
{
return length;
}
TSP_GENE::TSP_GENE()
{
create_population();
initialize_population();
}
TSP_GENE::~TSP_GENE()
{
delete_population();
}
// 遺伝子集団の作成
void TSP_GENE::create_population()
{
// 遺伝子集団のメモリ領域を確保
population = new INDIVIDUAL*[POPULATION_COUNT];
for (int i = 0; i < POPULATION_COUNT; i++)
population[i] = new INDIVIDUAL;
}
// 遺伝子集団の削除
void TSP_GENE::delete_population()
{
if (population != nullptr) {
for (int i = 0; i < POPULATION_COUNT; i++)
delete population[i];
delete []population;
population = nullptr;
}
}
// 遺伝子集団の初期化
void TSP_GENE::initialize_population()
{
// 遺伝子集団の初期状態を生成する。
for (int i = 0; i < POPULATION_COUNT; i++)
for (int j = 0; j < NUM_TOWN; j++)
population[i]->pathway[j] = j;
// 遺伝子をランダムにシャッフルする
for (int i = 0; i < POPULATION_COUNT; i++) {
for (int j = 0; j < NUM_TOWN; j++) {
int rnd1 = rand() % NUM_TOWN;
int tmp = population[i]->pathway[j];
population[i]->pathway[j] = population[i]->pathway[rnd1];
population[i]->pathway[rnd1] = tmp;
}
}
}
// 親の遺伝子を1/2の確率で逆回りに並び変える
void TSP_GENE::reverse_parent(int parent1[], int parent2[])
{
bool back_reverse1 = (rand() % 2) == 0;
if (back_reverse1 == true) {
int* pa1 = new int[NUM_TOWN];
copy_route(pa1, parent1);
for (int i = 0; i < NUM_TOWN; i++) {
parent1[i] = pa1[NUM_TOWN - 1 - i];
parent1[NUM_TOWN - 1 - i] = pa1[i];
}
delete []pa1;
}
bool back_reverse2 = (rand() % 2) == 0;
if (back_reverse2 == true) {
int* pa2 = new int[NUM_TOWN];
copy_route(pa2, parent2);
for (int i = 0; i < NUM_TOWN; i++) {
parent2[i] = pa2[NUM_TOWN - 1 - i];
parent2[NUM_TOWN - 1 - i] = pa2[i];
}
delete []pa2;
}
}
// 親の遺伝子をランダムに一定数シフト（回転）させる
void TSP_GENE::rotate_parent(int parent1[], int parent2[])
{
int* pa1 = new int[NUM_TOWN];
int* pa2 = new int[NUM_TOWN];
copy_route(pa1, parent1);
copy_route(pa2, parent2);
int rotate1 = rand() % NUM_TOWN;
int rotate2 = rand() % NUM_TOWN;
for (int i = 0; i < NUM_TOWN; i++) {
parent1[i] = pa1[(i + rotate1) % NUM_TOWN];
parent2[i] = pa2[(i + rotate2) % NUM_TOWN];
}
delete []pa1;
delete []pa2;
}
// 遺伝子の二点交叉
void TSP_GENE::two_point_cross(int route[], int parent1[], int parent2[])
{
// 交差位置を乱数で決定
int cross_point1 = rand() % (NUM_TOWN - 3) + 1;
int cross_point2 = cross_point1 + rand() % (NUM_TOWN - 2 - cross_point1) + 1;
// 染色体の前半をsource1からコピー
for (int j = 0; j < cross_point1; j++)
route[j] = parent1[j];
// 染色体の中間をsource2からコピー
for (int j = cross_point1; j < cross_point2; j++)
route[j] = parent2[j];
// 染色体の後半をsource1からコピー
for (int j = cross_point2; j < NUM_TOWN; j++)
route[j] = parent1[j];
// 染色体中の都市が重複した場合に重複をなくす
for (int j = cross_point1; j < cross_point2; j++) {
bool conflict = true;
while (conflict == true) {
conflict = false;
for (int k = 0; k < NUM_TOWN; k++) {
if (k == cross_point1)
k = cross_point2;
if (route[j] == route[k]) {
route[j] = parent2[k];
conflict = true;
break;
}
}
}
}
}
// 遺伝子の交叉（クロスオーバー）
void TSP_GENE::cross_over(int route_new[], int parent1[], int parent2[])
{
reverse_parent(parent1, parent2);
rotate_parent(parent1, parent2);
two_point_cross(route_new, parent1, parent2);
}
// 個体の突然変異体を作る
void TSP_GENE::mutation(int route[])
{
// 染色体の2ヶ所をランダムに選んで交換
int rnd1 = rand() % NUM_TOWN;
int rnd2 = rand() % NUM_TOWN;
int tmp = route[rnd1];
route[rnd1] = route[rnd2];
route[rnd2] = tmp;
}
// 各個体の巡回経路の長さを計算し短い順に並べ替える
void TSP_GENE::ga_ranking()
{
// 各個体の巡回経路長を計算
for (int i = 0; i < POPULATION_COUNT; i++)
population[i]->length = calc_length(population[i]->pathway);
// 巡回経路長が短い個体ほど上位にくるように並び替える
for (int i = 0; i < POPULATION_COUNT - 1; i++) {
for (int j = i + 1; j < POPULATION_COUNT; j++) {
if (population[i]->length > population[j]->length) {
INDIVIDUAL* tmp = population[i];
population[i] = population[j];
population[j] = tmp;
}
}
}
}
double TSP_GENE::solve()
{
// 親の遺伝子を入れるための配列の作成
int* parent1 = new int[NUM_TOWN];
int* parent2 = new int[NUM_TOWN];
// 集団は順位付けられているものとし、CUT_LINEより上の優秀な
// 個体から親の遺伝子を二つ選び、遺伝子の交差によって子供の個体を生成し
// CUT_LINEより下の個体を置き換える
for (int i = CUT_LINE; i < POPULATION_COUNT; i++) {
int source1 = rand() % CUT_LINE; // 親の遺伝子1の番号を選択
int source2 = rand() % CUT_LINE; // 親の遺伝子2の番号を選択
copy_route(parent1, population[source1]->pathway); // 親の遺伝子1の作成
copy_route(parent2, population[source2]->pathway); // 親の遺伝子2の作成
cross_over(population[i]->pathway, parent1, parent2); // 遺伝子の交叉
// MUTATION_ODDSの確率で突然変異を起こす
if (get_random() < MUTATION_ODDS)
mutation(population[i]->pathway);
}
ga_ranking(); // 巡回経路の短い順に並び変える
delete []parent1;
delete []parent2;
return population[0]->length;
}
void calc_genetic_algorithm()
{
for (int i = 0; i < ITERATION; i++) {
double length_new = pTspGene->solve();
// 最短の巡回経路長が更新されたら、経路と経路長を保存する
if (length_new < length) {
length = length_new;
copy_route(route, pTspGene->get_route(0));
}
}
}
int main()
{
unsigned int seed = (unsigned)time(NULL);
cout << "Seed = " << seed << endl;
srand(seed);
create_random_map();
init_route();
cout << "Number of town: " << NUM_TOWN << endl;
cout << endl << "Town map" << endl;
print_town_map();
cout << endl << "First root" << endl;
print_route();
pTspGene = new TSP_GENE;
calc_genetic_algorithm();
cout << endl << "Last root" << endl;
print_route();
delete pTspGene;
return 0;
}
実行結果（一点交叉）
Seed = 1721919795
Number of town: 20
Town map
1 34.2072 85.7819
2 69.342 16.0797
3 96.8628 1.80969
4 64.1632 38.2538
5 4.35181 75.47
6 0.323486 21.8353
7 87.0026 98.6267
8 3.6438 35.1044
9 52.7069 59.3872
10 24.4995 32.8308
11 69.4366 7.00378
12 5.62439 65.4083
13 0.323486 59.1583
14 22.7142 69.4366
15 94.3939 42.2668
16 26.0742 55.3955
17 86.084 5.39856
18 61.3159 57.9865
19 6.6925 98.4711
20 97.2992 64.8102
First root
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Total Distance: 1281.11
Last root
12 5 19 1 7 20 15 3 17 11 2 4 18 9 14 16 10 6 8 13
Total Distance: 446.503