|
|
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
unsigned seed = (unsigned)time(NULL);
void Chrom_out(int r[],int u)//染色体输出函数
{
int l;
for (l = 0; l < u-1; l++)
{
cout << r[l] << "--";
}
cout << r[u-1] << endl;
}
/*************OX程序*************/
bool check_point(int p[], int m, int x1, int x2)//检测节点是否再某条染色体中
{
int i;
for (i = x1; i <= x2; i++)
{
if (m == p[i])
return true;
}
return false;
}
void GA_OX(int f1[],int f2[]) //这里只产生了一个子代
{
int i;
int x1, x2;
int s[10] = { 0 };
srand(seed);
x1 = rand() % 10;
srand(seed);
x2 = rand() % (9 - x1 + 1) + x1;
for (i = x1; i <= x2; i++)
{
s[i] = f1[i];
}
int t = (x2 + 1) % 10;
int j = 0;
for (i = t; i < t + 10; i++)
{
if (check_point(s, f2[i % 10], x1, x2) == false)
{
j += 1;
s[(x2 + j) % 10] = f2[i % 10];
}
}
cout << "交叉位置：" << x1 << "," << x2 << endl;
cout << "OX结果：" << endl;
Chrom_out(s, 10);
}
/*************OX程序*************/
/*************PMX程序*************/
int judgment(int y,int x1,int x2,int s[])//判断节点是否在某染色体中，如果在则返回对应指数，否则返回一个较大的值（例如：100）
{
int n;
for (n = x1; n <= x2; n++)
{
if (y == s[n])
return n;
}
return 100;
}
void GA_PMX(int f1[], int f2[])
{
int i, j;
int x1, x2;
int s1[10], s2[10];
int trans_1[10] = { 0 }, trans_2[10] = { 0 };
for (i = 0; i <= 9; i++)//复制到子代，等待后续交叉操作
{
s1[i] = f1[i];
s2[i] = f2[i];
}
srand(seed);
x1 = rand() % 9;
srand(seed);
x2 = rand() % (9 - x1) + x1 + 1;//截取交叉片段
int status;
int t = 0;
for (i = x1; i <= x2; i++)
{
status = judgment(s1[i], x1, x2, s2);
if (status==100)
{
trans_1[t] = s1[i];
j = i;
bool flag = true;
do
{
status = judgment(s2[j], x1, x2, s1);
if (status == 100)
{
trans_2[t] = s2[j]; t = t + 1; break;
}
else
j = status;
} while (flag);
}
}
int temp;
for (j = 0; j < t; j++)
{
for (i = 0; i <= 9; i++)
{
if (s1[i] == trans_2[j])
{
status = judgment(trans_1[j], 0, 9, s2);
temp = s1[i];
s1[i] = s2[status];
s2[status] = temp; break;
}
}
}
for (i = x1; i <= x2; i++)
{
s1[i] = f2[i];
s2[i] = f1[i];
}
cout << "交叉位置：" << x1 << "," << x2 << endl;
cout << "PMX结果：" << endl;
Chrom_out(s1, 10);
Chrom_out(s2, 10);
}
/*************PMX程序*************/
/*************CX程序*************/
int find_position(int y, int m, int s[])//找出节点在某染色体的位置并返回
{
int n;
for (n = 0; n <= m; n++)
{
if (y == s[n])
return n;
}
}
void GA_CX(int f1[], int f2[])
{
int h, k;
int s1[10] = { 0 }, s2[10] = { 0 };
int temp[10] = { 0 };
int cycle_position[10][11] = { 0 };//记录环的各节点的位置，cycle_position[cycle_num][10]：记录环中节点数目
int cycle_num = 0;//记录环的个数
int position_num;
int c;
bool sign;
for (k = 0; k <= 9; k++)//复制到子代，等待后续交叉操作
{
s1[k] = f1[k];
s2[k] = f2[k];
}
for (k = 0; k <= 9; k++)
{
sign = true;
for (h = 0; h <= 9; h++)//判断目前检测的节点是否已经检测过，若没有被检测过则找到该节点所在的环
{
if (s1[k] == temp[h])
sign = false;
}
if (sign)
{
position_num = 0;//记录回环中节点数
c = k;//记录目前检测的节点的位置
cycle_position[cycle_num][0] = k;
temp[0] = s1[c];
bool flag = true;
do
{
if (s2[c] == s1[k])
{
cycle_position[cycle_num][10] = position_num;
cycle_num += 1;
break;
}
else
{
position_num += 1;
temp[position_num] = s2[c];
cycle_position[cycle_num][position_num]= find_position(s2[c], 10, s1);
c = cycle_position[cycle_num][position_num];
}
} while (flag);
}
}
int z;
int p;
int trans;
srand(seed);
p = rand() % cycle_num;
cout << "交叉回路：" << endl;
for (z = 0; z <= cycle_position[p][10]; z++)//染色体交叉，并输出完成交换的环
{
cout << s1[cycle_position[p][z]] << "<-->" << s2[cycle_position[p][z]] << " ";
trans = s1[cycle_position[p][z]];
s1[cycle_position[p][z]] = s2[cycle_position[p][z]];
s2[cycle_position[p][z]] = trans;
}
cout << endl << "CX结果：" << endl; //结果输出
Chrom_out(s1, 10);
Chrom_out(s2, 10);
}
/*************CX程序*************/
int main()
{
int F_1[10] = { 1,5,8,6,9,3,4,7,2,10 };
int F_2[10] = { 10,5,9,4,3,2,6,7,1,8 };//示例染色体
cout << "父代染色体：" << endl;
Chrom_out(F_1, 10);
Chrom_out(F_2, 10);
/*函数调用*/
GA_OX(F_1, F_2);
GA_PMX(F_1, F_2);
GA_CX(F_1, F_2);
return 0;
} |
|
发表于 2024-6-22 09:46:18
