3TSP/tsp_private.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "tsp.h"
#include "tsp_private.h"

/* 遺伝子型 g から表現型 p への変換 */
/* g[] で与えた巡回表現の遺伝子型を都市の番号にして表現型 p[] に入れる */
void gtype_to_ptype(int g[CITY_NUM], int p[CITY_NUM]) {
	int i, j;
	int count;
	int check[CITY_NUM]; /* 既に表現型に現れたかどうか */

	/* check[] の初期化 */
	for(i = 0; i < CITY_NUM; i++) {
		check[i] = NO;	
	}

	for(i = 0; i < CITY_NUM; i++) {
		/* i 番目の遺伝子を変換 */
		j = 0; /* 全都市のうち何番目か */
		count = 0; /* 残った都市のうち何番目か */
		do {
			if(check[j] == NO) { /* 表現型に現れていない都市である */
				count++;
			}
			if(count > g[i]) { /* 遺伝子型に適合 */
				break;
			}
			j++;
		} while(1);
		p[i] = j; /* p 番目の遺伝子の都市番号は j */
		check[j] = YES; /* 表現型に現れたことをチェック */
	}
};

/* 都市間の距離を計算 */
double distance(Position city1, Position city2)
{
	return sqrt((city1.x - city2.x)*(city1.x - city2.x) +
		(city1.y - city2.y)*(city1.y - city2.y));
};

/* 遺伝子の表す巡回路長の計算 */
double path_length(Position city[CITY_NUM], int gene[CITY_NUM]) 
{
	int i;
	double sum = 0.0;
	int route[CITY_NUM]; /* 巡回路の表現型 */

	gtype_to_ptype(gene, route); /* 遺伝子型から表現型への変換 */

	for(i = 0; i < CITY_NUM; i++) {
		sum += distance(city[route[i%CITY_NUM]], city[route[(i+1)%CITY_NUM]]);
	}

	return sum;
};

/* 遺伝子の表示 */
void print_gene(int gene[CITY_NUM])
{
	int i;

	printf("gene:");
	for(i = 0; i < CITY_NUM; i++) {
		printf("%d.", gene[i]);
	}
	printf("\n");
}

/* 巡回路の表示 */
void print_route(int route[CITY_NUM])
{
	int i;
	printf("route:");
	for(i = 0; i < CITY_NUM; i++) {
		printf("%d->", route[i]);
	}
	printf("%d\n", route[0]);
	
}

/* 遺伝子集団の巡回路長の計算 */
void calculate_length(Gene_set *gene_ptr, Position city[CITY_NUM]) {
	int i;
	for(i = 0; i < GENE_NUM; i++) {
		(gene_ptr + i)->length = path_length(city, (gene_ptr + i)->gene);
	}
}

/* 遺伝子の複写 */
void copy_gene(int gene_to[CITY_NUM], int gene_from[CITY_NUM])
{
	int k;

	for(k = 0; k < CITY_NUM; k++) {
		gene_to[k] = gene_from[k];
	}
}

/* 遺伝子の入れ換え */
void swap_gene_set(Gene_set gene_group[GENE_NUM], int i, int j)
{
	Gene_set gene_swap;

	gene_swap.fitness = gene_group[i].fitness;
	gene_swap.length = gene_group[i].length;
	copy_gene(gene_swap.gene, gene_group[i].gene);

	gene_group[i].fitness = gene_group[j].fitness;
	gene_group[i].length = gene_group[j].length;
	copy_gene(gene_group[i].gene, gene_group[j].gene);

	gene_group[j].fitness = gene_swap.fitness;
	gene_group[j].length = gene_swap.length;
	copy_gene(gene_group[j].gene, gene_swap.gene);
}

/* 現時点の最適遺伝子の番号を得る */
int get_best_gene(Gene_set gene_group[GENE_NUM])
{
	int i, index = 0;

	for(i = 0; i < GENE_NUM; i++) {
		if(gene_group[i].length < gene_group[index].length) {
			index = i;
		}
	}

	return index;
}