c语言遗传算法解决旅行商问题
时间: 2024-01-16 11:04:37 浏览: 76
遗传算法是一种优化算法,可以用于解决旅行商问题。以下是C语言遗传算法解决旅行商问题的步骤:
1.初始化种群:生成一组随机的路径作为初始种群。
2.计算适应度:对于每个个体(路径),计算其总距离作为适应度。
3.选择操作:使用轮盘赌选择算法,根据适应度选择一些个体进行交叉互换和变异操作。
4.交叉互换:随机选择两个个体,选择一个交叉点,将两个个体在交叉点处交叉互换,生成两个新的个体。
5.变异操作:对于每个个体,以一定的概率进行变异操作,例如随机选择两个位置,将它们交换。
6.重复执行2-5步,直到达到预设的迭代次数或找到最优解。
以下是一个简单的C语言遗传算法解决旅行商问题的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define CITY_NUM 10 // 城市数量
#define POP_SIZE 100 // 种群大小
#define ITER_NUM 1000 // 迭代次数
#define CROSS_RATE 0.8 // 交叉概率
#define MUTATE_RATE 0.1 // 变异概率
int g_Distance[CITY_NUM][CITY_NUM]; // 城市之间的距离矩阵
int g_Group[POP_SIZE][CITY_NUM]; // 种群
int g_Fitness[POP_SIZE]; // 适应度
// 计算两个城市之间的距离
int Distance(int city1, int city2) {
return g_Distance[city1][city2];
}
// 计算一条路径的总距离
int PathDistance(int path[]) {
int distance = 0;
for (int i = 0; i < CITY_NUM - 1; i++) {
distance += Distance(path[i], path[i+1]);
}
distance += Distance(path[CITY_NUM-1], path[0]);
return distance;
}
// 初始化种群
void InitGroup() {
for (int i = 0; i < POP_SIZE; i++) {
for (int j = 0; j < CITY_NUM; j++) {
g_Group[i][j] = j;
}
for (int j = 0; j < CITY_NUM; j++) {
int k = rand() % CITY_NUM;
int temp = g_Group[i][j];
g_Group[i][j] = g_Group[i][k];
g_Group[i][k] = temp;
}
g_Fitness[i] = PathDistance(g_Group[i]);
}
}
// 选择操作
void Select() {
int newGroup[POP_SIZE][CITY_NUM];
int newFitness[POP_SIZE];
int sumFitness = 0;
for (int i = 0; i < POP_SIZE; i++) {
sumFitness += g_Fitness[i];
}
for (int i = 0; i < POP_SIZE; i++) {
int r = rand() % sumFitness;
int s = 0;
for (int j = 0; j < POP_SIZE; j++) {
s += g_Fitness[j];
if (s >= r) {
for (int k = 0; k < CITY_NUM; k++) {
newGroup[i][k] = g_Group[j][k];
}
newFitness[i] = g_Fitness[j];
break;
}
}
}
for (int i = 0; i < POP_SIZE; i++) {
for (int j = 0; j < CITY_NUM; j++) {
g_Group[i][j] = newGroup[i][j];
}
g_Fitness[i] = newFitness[i];
}
}
// 交叉互换
void Cross() {
for (int i = 0; i < POP_SIZE; i += 2) {
if ((double)rand() / RAND_MAX < CROSS_RATE) {
int sel1 = rand() % POP_SIZE;
int sel2 = rand() % POP_SIZE;
int pos1 = rand() % CITY_NUM;
int pos2 = rand() % CITY_NUM;
if (pos1 > pos2) {
int temp = pos1;
pos1 = pos2;
pos2 = temp;
}
int child1[CITY_NUM];
int child2[CITY_NUM];
for (int j = 0; j < CITY_NUM; j++) {
child1[j] = -1;
child2[j] = -1;
}
for (int j = pos1; j <= pos2; j++) {
child1[j] = g_Group[sel2][j];
child2[j] = g_Group[sel1][j];
}
int k1 = pos2 + 1;
int k2 = pos2 + 1;
for (int j = 0; j < CITY_NUM; j++) {
if (k1 == CITY_NUM) {
k1 = 0;
}
if (k2 == CITY_NUM) {
k2 = 0;
}
if (child1[k1] == -1) {
int city = g_Group[sel1][j];
int flag = 0;
for (int k = pos1; k <= pos2; k++) {
if (city == child1[k]) {
flag = 1;
break;
}
}
if (!flag) {
child1[k1] = city;
k1++;
}
}
if (child2[k2] == -1) {
int city = g_Group[sel2][j];
int flag = 0;
for (int k = pos1; k <= pos2; k++) {
if (city == child2[k]) {
flag = 1;
break;
}
}
if (!flag) {
child2[k2] = city;
k2++;
}
}
}
for (int j = 0; j < CITY_NUM; j++) {
g_Group[i][j] = child1[j];
g_Group[i+1][j] = child2[j];
}
g_Fitness[i] = PathDistance(child1);
g_Fitness[i+1] = PathDistance(child2);
}
}
}
// 变异操作
void Mutate() {
for (int i = 0; i < POP_SIZE; i++) {
if ((double)rand() / RAND_MAX < MUTATE_RATE) {
int pos1 = rand() % CITY_NUM;
int pos2 = rand() % CITY_NUM;
int temp = g_Group[i][pos1];
g_Group[i][pos1] = g_Group[i][pos2];
g_Group[i][pos2] = temp;
g_Fitness[i] = PathDistance(g_Group[i]);
}
}
}
// 打印最优解
void PrintBest() {
int bestIndex = 0;
for (int i = 1; i < POP_SIZE; i++) {
if (g_Fitness[i] < g_Fitness[bestIndex]) {
bestIndex = i;
}
}
printf("Best path: ");
for (int i = 0; i < CITY_NUM; i++) {
printf("%d ", g_Group[bestIndex][i]);
}
printf("\nBest distance: %d\n", g_Fitness[bestIndex]);
}
int main() {
srand((unsigned)time(NULL));
// 初始化距离矩阵
for (int i = 0; i < CITY_NUM; i++) {
for (int j = 0; j < CITY_NUM; j++) {
if (i == j) {
g_Distance[i][j] = 0;
} else {
g_Distance[i][j] = rand() % 100 + 1;
}
}
}
// 初始化种群
InitGroup();
// 迭代
for (int i = 0; i < ITER_NUM; i++) {
Select();
Cross();
Mutate();
}
// 输出结果
PrintBest();
return 0;
}
```
阅读全文