单片机中实现遗传算法源码

xavierz

#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#define M1 100
#define M2 100000
#define N 36
#define p0 0.4
#define p1 0.8
#define wm 6.5
#define vk 0.8
#define vm 2.5
#define vc 3074.125//定义不折回的固定费用
#define MIN(a,b) ((a>b)?b:a)
#define MAX(a,b) ((a>b)?a:b)
int x[N]={3,1,5,4,3,0,7,9,10,14,17,14,12,10,19,2,6,11,15,7,17,21,27,15,15,20,21,24,25,28,5,22,25,9,9,30};
int y[N]={2,5,4,7,11,8,9,6,2,0,3,6,9,12,9,16,18,17,12,14,16,0,9,19,14,17,13,20,16,18,12,5,7,20,15,12};
double T[N]={1.5,1.5,0.55,1.2,1.3,0.85,1.2,2.3,1.4,1.5,1.1,2.7,1.8,1.8,1.4,1.5,0.8,1.5,0.8,0.6,1.3,1.8,1.4,1.6,1.6,1,2,1,2.1,1.2,1.9,1.2,1.6,1.2,1.5,1.3};

int d[N][N]={0,3,4,6,9,6,11,10,7,11,15,15,16,17,23,14,19,23,22,16,28,18,31,29,24,32,29,39,36,41,12,22,27,24,19,37,
2,0,4,5,8,3,10,9,9,13,16,14,15,16,22,12,18,22,21,15,27,20,30,28,23,31,28,38,35,40,11,21,26,23,18,36,
0,1,0,3,7,4,7,6,5,9,12,11,12,13,19,12,15,19,18,12,24,16,27,25,20,28,25,35,32,37,8,18,23,20,15,33,
0,0,1,0,4,1,5,5,6,10,13,10,10,11,17,9,13,17,16,10,22,17,25,23,18,26,23,33,30,35,6,18,21,18,13,31,
0,0,2,1,0,0,4,6,7,11,14,11,9,8,16,5,10,14,13,7,19,18,24,20,15,23,20,30,27,32,3,19,22,15,10,28,
3,1,5,4,6,0,8,9,10,14,17,14,13,14,20,10,16,20,19,13,25,21,28,26,21,29,26,36,33,38,9,22,25,21,16,34,
0,0,0,0,2,0,0,2,3,7,10,7,5,6,12,7,9,12,11,5,17,14,20,18,13,21,18,28,25,30,3,15,18,13,8,26,
0,0,0,1,5,2,3,0,1,5,8,5,6,7,13,10,12,13,12,8,18,12,21,19,14,22,19,29,26,31,6,13,17,14,9,27,
0,3,2,5,9,6,7,4,0,4,8,8,9,10,16,14,16,16,15,12,21,11,24,22,17,25,22,32,29,34,10,15,20,18,13,30,
2,5,4,7,11,8,9,6,2,0,6,6,9,12,14,16,18,17,13,14,19,7,22,20,15,23,20,30,27,32,12,13,18,20,15,28,
0,2,1,4,8,5,6,3,0,0,0,3,6,9,8,13,15,14,9,11,13,4,16,16,11,17,14,24,21,26,9,7,12,17,12,22,
0,0,0,1,5,2,3,0,0,0,3,0,3,6,8,10,12,11,7,8,13,7,16,14,9,17,14,24,21,26,6,8,12,14,9,22,
0,0,0,0,2,0,0,0,0,2,5,2,0,3,7,7,9,8,6,5,12,9,15,13,8,16,13,23,20,25,3,10,13,11,6,21,
0,0,0,0,0,0,0,0,0,4,7,4,2,0,9,4,6,6,5,2,11,11,17,12,7,15,12,22,19,24,0,12,15,8,3,20,
0,0,0,0,2,0,0,0,0,0,0,0,0,3,0,7,9,8,3,5,7,2,8,10,5,9,6,16,13,18,3,3,6,11,6,14,
1,0,3,2,1,0,5,7,8,12,15,12,10,8,17,0,6,10,13,5,15,19,25,16,13,19,19,26,23,28,3,20,23,11,7,28,
0,0,0,0,0,0,1,3,4,8,11,8,6,4,13,0,0,5,9,1,11,15,21,10,9,14,15,20,19,22,0,16,19,5,3,24,
0,0,0,0,0,0,0,0,0,3,6,3,1,0,8,0,1,0,4,0,6,10,16,6,4,9,10,16,14,18,0,11,14,3,0,19,
0,0,0,0,0,0,0,0,0,0,2,0,0,0,4,4,6,5,0,2,6,6,12,7,2,10,7,17,14,19,0,7,10,8,3,15,
0,0,0,0,0,0,0,2,3,7,10,7,5,3,12,2,4,7,8,0,12,14,20,13,8,16,14,23,20,25,0,15,18,8,3,23,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,2,1,0,0,0,4,10,3,0,4,4,11,8,13,0,5,8,4,0,13,
2,5,4,7,11,8,9,6,2,0,3,6,9,12,9,16,18,17,12,14,16,0,15,19,14,17,13,23,20,25,12,6,11,20,15,21,
0,0,0,0,2,0,0,0,0,0,0,0,0,3,0,7,9,8,3,5,7,0,0,10,5,8,4,11,7,10,3,0,0,11,6,6,
0,0,0,0,0,0,0,0,0,0,2,0,0,0,4,0,0,0,0,0,2,6,12,0,0,5,6,10,10,13,0,7,10,1,0,15,
0,0,0,0,0,0,0,0,0,0,2,0,0,0,4,2,4,3,0,0,4,6,12,5,0,8,6,15,12,17,0,7,10,6,1,15,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,7,2,0,0,1,7,5,9,0,2,5,3,0,10,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,5,4,0,1,3,0,6,6,1,4,0,10,7,12,0,1,4,7,2,9,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,1,4,0,0,1,0,0,6,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,0,0,0,0,2,3,0,1,0,4,0,5,0,0,0,4,0,5,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,2,0,0,0,0,0,2,0,2,
0,0,0,0,0,0,2,4,5,9,12,9,7,5,14,4,7,11,10,4,16,16,22,17,12,20,17,27,24,29,0,17,20,12,7,25,
0,0,0,2,6,3,4,1,0,0,0,1,4,7,4,11,13,12,7,9,11,0,9,14,9,12,8,17,14,19,7,0,5,15,10,15,
0,0,0,0,4,1,2,0,0,0,0,0,2,5,2,9,11,10,5,7,9,0,4,12,7,10,6,13,9,14,5,0,0,13,8,10,
0,0,0,0,0,0,0,0,1,5,8,5,3,1,10,0,0,2,6,0,8,12,18,6,6,11,12,15,16,19,0,13,16,0,0,21,
0,0,0,0,0,0,0,0,1,5,8,5,3,1,10,1,3,4,6,0,9,12,18,10,6,13,12,20,17,22,0,13,16,5,0,21,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,6,5,0,2,4,0,0,7,2,5,1,8,4,6,0,0,0,8,3,0};

double f(int a[],int road[][N],int length[],double wx[])//a[]为整体排序,road[N]为第i辆车的路线,length为第i条路线经过的点数,wx为第i辆车载重量
{
    int i=0,j=0,k=0,imid=0,jmid=0;
    double w=0,v=0;
    i=a[0];
    w=T;
    v=vk*(x+y);
    for(i=0;i<N;i++)
        length=0;
    for(k=0,i=0;k<N-1;k++)
    {
        imid=a[k];
        jmid=a[k+1];
        v+=2*vm*w*d[imid][jmid];
        w+=T[jmid];
        road[j++]=a[k];
        length[i+1]++;
        if(w>wm)
        {
            wx=w-T[jmid];
            v=v-2*vm*wx*d[imid][jmid];
            v+=vk*(x[jmid]+y[jmid]);
            w=T[jmid];
            i++;
            length[0]++;
            j=0;
        }
        if(k==N-2)
        {
            wx=w;
            road[j]=a[jmid];
            length[0]++;
            length[i+1]++;
        }
    }
    return (vc+v);
}
double fuc(int road[][N],int length[],double wx[])
{
    int i=0,j=0,k=0,imid=0,jmid=0;
    double v=0,w=0;
    for(i=0;i<length[0];i++)
        for(j=0,k=road[0],w=T[k],v+=vk*(x[k]+y[k]);j<length[i+1]-1;j++)
        {
            imid=road[j];
            jmid=road[j+1];
            v+=2*vm*w*d[imid][jmid];
            w+=T[jmid];
            if(j==length[i+1]-2)
                wx=w;
        }
    return (vc+v);
}

int judge(int a[],int length)//判断是否超载
{
    int i=0,j=0;
    double w=0;
    for(i=0;i<length;i++)
    {
        j=a;
        w+=T[j];
    }
    if(w>wm) return 0;
    else return 1;
}

void change(int a[],int b[],int m,int n)//数组部分交换
{
    int i,c,m1,n1;
    m1=MIN(m,n);
    n1=MAX(m,n);
    for(i=m1;i<=n1;i++)
    {
        c=a;
        a=b;
        b=c;
    }
}
void zcopy(int road0[][N],int road[][N],int length[])//二维数组复制
{
    int i=0,j=0,k=0;
    for(i=0;i<length[0];i++)
        for(j=0;j<length[i+1];j++)
            road0[j]=road[j];
}

void RandomSort(int a[])//随机生成序列
{
    int i,j,temp1;
    double b[N],temp0;
    for(i=0;i<N;i++)
    {
        a=i;
        b=rand()*1.0/RAND_MAX;
    }
    for(i=0;i<N-1;i++)
        for(j=0;j<N-1-i;j++)
            if(b[j]>b[j+1])
            {
                temp0=b[j];
                temp1=a[j];
                b[j]=b[j+1];
                a[j]=a[j+1];
                b[j+1]=temp0;
                a[j+1]=temp1;
            }
}

void variation(int a[],int roadx[][N],int lengthx[])//遗传变异操作
{
    int a0[N]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35};
    int a1[N],road0[N][N],road[N][N],length[N];
    long i=0,j=0,k=0,t,r,r0,r1,h0,h1;
    double wx[N],v0=0,v1=0;
    for(i=0;i<M1;i++)//寻找优秀亲代
    {
        RandomSort(a1);
        if(f(a1,road,length,wx)<f(a0,road,length,wx))
            for(j=0;j<N;j++)
                a0[j]=a1[j];
    }
    v0=f(a0,road,length,wx);
    for(i=0;i<M2;i++)//开始变异
    {
        if(rand()*1.0/RAND_MAX<p0)//局部基因重组
        {
            h0=rand()%length[0];//随机选取行数
            h1=rand()%length[0];
             if(h0==h1) continue;
            r0=length[h0+1];//第h0行的元素个数
            r1=length[h1+1];
            r=MIN(r0,r1);
            r0=rand()%r;//随机选取列数
            r1=rand()%r;
            zcopy(road0,road,length);
            change(&road0[h0][0],&road0[h1][0],r0,r1);
            if(judge(&road0[h0][0],length[h0+1])&&judge(&road0[h1][0],length[h1+1]))
            {
                if(fuc(road0,length,wx)<fuc(road,length,wx))
                zcopy(road,road0,length);
                continue;
            }
            else continue;
        }
        else if(rand()*1.0/RAND_MAX>p1) //基因突变
        {
            h0=rand()%length[0];//随机选取行数
            h1=rand()%length[0];
            r0=rand()%length[h0+1];//随机选取列数
            r1=rand()%length[h1+1];
            if(h0==h1&&r0==r1) continue;
            zcopy(road0,road,length);
            t=road0[h0][r0];
            road0[h0][r0]=road0[h1][r1];
            road0[h1][r1]=t;
            if(judge(&road0[h0][0],length[h0+1])&&judge(&road0[h1][0],length[h1+1]))
            {
                if(fuc(road0,length,wx)<fuc(road,length,wx))
                zcopy(road,road0,length);
                continue;
            }
            else continue;
        }
        else //染色体变异
        {
            h0=rand()%length[0];//随机选取行数
            h1=rand()%length[0];
             if(h0==h1) continue;
            r=MAX(length[h0+1],length[h1+1]);
            change(&road[h0][0],&road[h1][0],0,r);
            t=length[h0+1];
            length[h0+1]=length[h1+1];
            length[h1+1]=t;
        }
    }
    for(i=0;i<N;i++)
        a=a0;
    for(i=0;i<N;i++)
        lengthx=length;
    zcopy(roadx,road,length);
}

void sort(int a[])//一般排序
{
    int i,j,min,temp;
    for(i=0;i<N-1;i++)
    {
        min=i;
        for(j=i+1;j<N;j++)
            if(a[j]<a[min]) min=j;
        temp=a;
        a=a[min];
        a[min]=temp;
    }
}
int *test(int z[][N],int length[])
{
    int i=0,j=0,k=0,a[N];
    for(i=0;i<length[0];i++)
        for(j=0;j<length[i+1];j++)
            a[k++]=z[j];
    sort(a);
    return a;
}
main()
{
    double wx[N],value=0;
    int a[N];//={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35};
    int n=2,i,j,road[10][N];
    int k=0,length[N],error=0;
    clock_t start,end;
    start=clock();
    //f(a,road,length,wx);
    /*for(i=0;i<N;i++)
        for(j=0;j<N;j++)
        {
            if(x>=x[j]&&y>=y[j]) d[j]=0;
            else if(x>=x[j]&&y<=y[j]) d[j]=y[j]-y;
            else if(x<=x[j]&&y<=y[j]) d[j]=y[j]-y+x[j]-x;
            else if(x<=x[j]&&y>=y[j]) d[j]=x[j]-x;
        }
    for(i=0;i<N;i++)
        value+=vm*T*(x+y);
    printf("value=%.3lf\n",value);*/
    variation(a,road,length);
    value=fuc(road,length,wx);
    for(i=0,j=0;i<N;i++)
        if(test(road,length)!=i)  
        {
            error=1;
            printf("Error !\n");
            printf("The reduplicate number is %d\n\n",test(road,length));//检查是否有因硬件延时造成的错误
            break;
        }
    if(error==0)
    {
        printf("The number of roads are\n");
        printf("%d\n\n",length[0]);
        printf("The roads are\n");
        for(i=0;i<length[0];i++)
        {
           for(j=0;j<length[i+1];j++)
            printf("%d,",road[j]+1);
           printf("[37]\n");
        }
        printf("\nThe weight of each road is\n");
        for(i=0;i<length[0];i++)
           printf("%.2lf,",wx);
        printf("\n");
        printf("\nThe value is\n");
        printf("%.3lf\n",value-vc);
        end=clock();
        printf("\nRun time = %.3f seconds\n\n",(end-start)/1000.0);
    }
    else
        printf(&quotlease reset the number of M1 !\n");
}

会飞的鱼589

看看

hbjsss

auv

什么是遗传算法？