遗传算法求交通问题

遗传算法求交通问题

.
遗传算法作为一种快速有效的寻优算法，在工业控制、经济决策和交通规划等居多领域得到广泛应用。其特点就是其不同于传统的搜索寻优方式而是模拟自然界生物进化过程，通过基因的变异交叉重组使整体得到进化，不断的进化最终得到最优的组群，即最优解。

下面是一个具体实例，是小可在别人程序的基础上改写优化而成。这里首先要建立数学模型，即问题的数学公式描述，数学建模是一门对数学能力有相当要求的课程，一个人的数学能力往往决定其从事工作的层次。下面的程序是求多项式y=x^6-10x^5-26x^4+344x^3+193x^2-1846x-1680在区间[-8,8]的最小值，误差不超过0.001。对于这个复杂的多项式，可先用matlab绘制函数的大概曲线，确认函数的最小值大概处于[-8,8]之间，再用本程序求出精确解。

程序已在Dev-c++下运行通过，结果正确。

如有什么疑问，给我消息。



#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <time.h>



#define SUM 20

#define MAXloop 1200

#define error 0.01

#define crossp 0.7

#define mp 0.04



struct gen

{

int info;

double suitability;

};

struct gen gen_group[SUM];

struct gen gen_new[SUM];



struct gen gen_result;

int result_unchange_time;



struct log

{

double suitability;

struct log *next;

}llog,*head,*end;

int log_num;



void initiate();

void evaluation(int flag);

void cross();

void selection();

int record();

void mutation();

void showresult(int);



int randsign(double p);

int randbit(int i,int j);

int randnum();

int convertionD2B(double x);

double convertionB2D(int x);

int createmask(int a);



int main()

{

int i,flag;

flag=0;

initiate();

evaluation( 0 );

for( i = 0 ; i < MAXloop ; i++ )

{

cross();

evaluation( 1 );

selection();

if( record() == 1 )

{

flag = 1;

break;

}

mutation();

}

showresult( flag );

system("pause");

return 0

}



void initiate()

{

int i , stime;

long ltime;

ltime=time(NULL);

stime=(unsigned)ltime/2;

srand(stime);

for( i = 0 ; i < SUM ; i++ )

{

gen_group[i].info = randnum();

}

gen_result.suitability=1000;

result_unchange_time=0;

head=end=(struct log *)malloc(sizeof(llog));

if(head==NULL)

{

printf("\n内存不够！\n");

exit(0);

}

end->next = NULL;

log_num = 1;

}



void evaluation(int flag)

{

int i,j,k;

struct gen *genp;

int gentinfo;

double gentsuitability;

double x;

if( flag == 0 )

genp = gen_group;

else genp = gen_new;

for(i = 0 ; i < SUM ; i++)

{

x = convertionB2D( genp[i].info );

genp[i].suitability = x*(x*(x*(x*(x*(x-10)-26)+344)+193)-1846)-1680;

}

for(i = 0 ; i < SUM - 1 ; i++)

{ k=i;

for(j = i + 1 ; j < SUM ; j++)

if( genp[i].suitability > genp[j].suitability ) k=j;

if( k!=i )

{

gentinfo = genp[i].info;

genp[i].info = genp[k].info;

genp[k].info = gentinfo;



gentsuitability = genp[i].suitability;

genp[i].suitability = genp[k].suitability;

genp[k].suitability = gentsuitability;

}

}

}



void cross()

{

int i , j , k ;

int mask1 , mask2;

int a[SUM];

for(i = 0 ; i < SUM ; i++) a[i] = 0;

k = 0;

for(i = 0 ; i < SUM ; i++)

{

if( a[i] == 0)

{

for( ; ; )

{

j = randbit(i + 1 , SUM - 1);

if( a[j] == 0) break;

}

if(randsign(crossp) == 1)

{

mask1 = createmask(randbit(0 , 14-1));

mask2 = ~mask1;

gen_new[k].info = (gen_group[i].info) & mask1 + (gen_group[j].info) & mask2;

gen_new[k+1].info=(gen_group[i].info) & mask2 + (gen_group[j].info) & mask1;

k = k + 2;

}

else

{

gen_new[k].info=gen_group[i].info;

gen_new[k+1].info=gen_group[j].info;

k=k+2;

}

a[i] = a[j] = 1;

}

}

}



void selection()

{

int i , j , k;

j = 0;

i = SUM/2-1;

if(gen_group[i].suitability < gen_new[i].suitability)

{

for(j = 1 ; j < SUM / 2 ; j++)

{

if(gen_group[i+j].suitability > gen_new[i-j].suitability)

break;

}

}

else

if(gen_group[i].suitability>gen_new[i].suitability)

{

for(j=-1;j>-SUM/2;j--)

{

if(gen_group[i+j].suitability<=gen_new[i-j].suitability)

break;

}

}

for(k=j;k<SUM/2+1;k++)

{

gen_group[i+k].info = gen_new[i-k].info;

gen_group[i+k].suitability = gen_new[i-k].suitability;

}

}



int record()

{

double x;

struct log *r;

r=(struct log *)malloc(sizeof(llog));

if(r==NULL)

{

printf("\n内存不够！\n");

exit(0);

}

r->next = NULL;

end->suitability = gen_group[0].suitability;

end->next = r;

end = r;

log_num++;



x = gen_result.suitability - gen_group[0].suitability;

if(x < 0)x = -x;

if(x < error)

{

result_unchange_time++;

if(result_unchange_time >= 20)return 1;

}

else

{

gen_result.info = gen_group[0].info;

gen_result.suitability = gen_group[0].suitability;

result_unchange_time=0;

}

return 0;

}



void mutation()

{

int i , j , k, m;

double x;

double gmp;

int gentinfo;

double gentsuitability;

gmp = 1 - pow(1 - mp , 11);

for(i = 0 ; i < SUM ; i++)

{

if(randsign(gmp) == 1)

{

j = randbit(0 , 14);

m = 1 << j;

gen_group[i].info = gen_group[i].info^m;

x = convertionB2D(gen_group[i].info);

gen_group[i].suitability = x*(x*(x*(x*(x*(x-10)-26)+344)+193)-1846)-1680;

}

}

for(i = 0 ; i < SUM - 1 ; i++)

{ k=i;

for(j = i + 1 ; j < SUM ; j++)

if(gen_group[i].suitability > gen_group[j].suitability) k=j;

if(k!=i)

{

gentinfo = gen_group[i].info;

gen_group[i].info = gen_group[k].info;

gen_group[k].info = gentinfo;



gentsuitability = gen_group[i].suitability;

gen_group[i].suitability = gen_group[k].suitability;

gen_group[k].suitability = gentsuitability;

}

}

}



void showresult(int flag)

{

int i , j;

struct log *logprint,*logfree;

FILE *logf;

if(flag == 0)

printf("已到最大搜索次数，搜索失败！");

else

{

printf("当取值%f时表达式达到最小值为%f\n",convertionB2D(gen_result.info),gen_result.suitability);

printf("收敛过程记录于文件log.txt");

if((logf = fopen("log.txt" , "w+")) == NULL)

{

printf("Cannot create/open file");

exit(1);

}

logprint=head;

for(i = 0 ; i < log_num ; i = i + 5)

{

for(j = 0 ; (j < 5) & ((i + j) < log_num-1) ; j++)

{

fprintf(logf , "%20f" , logprint->suitability);

logprint=logprint->next;

}

fprintf(logf,"\n\n");

}

}

for(i = 0 ; i< log_num ; i++)

{

logfree=head;

head=head->next;

free(logfree);

}

fclose(logf);

getch();

}



int randsign(double p)

{

if(rand() > (p * 32768))

return 0;

else return 1;

}

int randbit(int i, int j)

{

int a , l;

l = j - i + 1;

a = i + rand() * l / 32768;

return a;

}

int randnum()

{

int x;

x = rand() / 2;

return x;

}

double convertionB2D(int x)

{

double y;

y = x;

y = (y - 8192) / 1000;

return y;



}

int convertionD2B(double x)

{

int g;

g = (x * 1000) + 8192;

return g;

}

int createmask(int a)

{

int mask;

mask=(1 << a) - 1;

return mask;

}