遗传算法三种交叉算子（OX、PMX、CX）

admin1

#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;
}