关于遗传算法
程序代码：#include <stdio.h>
#include <math.h>
#include <stdlib.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; //染色体结构，用一整型数的后14位作为染色体编码
float suitability; //此染色体所对应的适应度函数值，即表达式的值
};
struct gen gen_group[SUM]; //定义含有20个染色体的种群
struct gen gen_new[SUM]; //定义含有20个染色体的种群，记录交叉产生的子代染色体
struct gen gen_result; //记录上一轮循环中得到的最优的染色体
int result_unchange_time; //当相邻两轮得到的最优值对应的适应度
//之差小于error时其值增1，反之清零
struct log //形成链表，记录每次循环所产生的最优的适应度
{
float suitability;
struct log *next;
}llog, *head, *end;
int log_num; // 链表长度
void initiate(void); //初始化函数，负责产生初始种群
void evaluation(int flag); //评估染色体的适应度，进行排序
void cross(void); //交叉函数
void selection(void); //选择函数
int record(void); //记录每次循环所产生的最优解并判断循环是否终止
void mutation(void); //编译函数
void showresult(int); //显示结果
int randsign(float p); //按概率p随机产生0、1其值为的概率为p
int randbit(int i, int j); //随机产生一个在i，j两个数之间的整数
int randnum(void); //随机产生一个14个基因组成的染色体
int createmask(int a); //用于交叉操作
int convertionD2B(float x); //对现实解空间的可能解x进行二进制编码
float convertionB2D(int x); //将二进制编码x转化为现实解空间的值
void 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);
}
/*函数三个功能：1.初始化随机列表 2.建立规模SUM的初始种群 3.建立log链表头，
其中指针head记录链表头的位置，end始终指向链表的尾部*/
void initiate(void)
{
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内存不够");
exit(1);
}
end->next = NULL;
log_num = 1;
}
void evaluation(int flag)
{
int i, j;
struct gen *genp;
int gentinfo;
float gentsuitability;
float 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++)
{
for(j=i+1; j<SUM; j++)
{
if(genp[i].suitability > genp[j].suitability)
{
gentinfo = genp[i].info;
genp[i].info = genp[j].info;
genp[j].info = gentinfo;
gentsuitability = genp[i].suitability;
genp[i].suitability = genp[j].suitability;
genp[j].suitability = gentsuitability;
}
}
}
}
/*cross由三部分组成：1.随机选择将要进行交叉的染色体对，保证种群中的每一个
染色体都有唯一一次交叉的机会，2.按crossp的概率对选择的染色体对进行交叉操作
3.为进行交叉的染色体直接复制作为子染色体。 首先由ranbit（）进行交叉位
createmask（）返回一个交叉位以右皆为1的二进制数，赋值给mask1，mask2为交叉
以左皆为1的二进制数，它们分别与父染色体gen_group[i].info gen_group[j].info
进行操作，所得的结果的和即为交叉的结果*/
void cross(void)
{
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));
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;
}
}
}
/*函数从父代种群和子代种群中选择最优的染色体组成新的父代种群。由于两个种群
都已进行了排序，因此只需找到子代种群中的第t个个体使其适应度函数值满足：
大于父代中种群中的第NUM-t个个体，并小于父代的第NUM-t+1个个体，然后用子代种群中
的前t个个体代替父代种群的后t个个体即可。*/
void selection(void)
{
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;
}
}
/*两个任务：1.用链表记录各轮循环中的最优值，2.判断是否满足循环停止条件，
当两次循环的适应度的差小于error时，result——unchange-time的值加1，
若result——unchange-time达到20时表示已经搜索到最优值，返回1，若适应度
差大于等于error则将result——unchange——time清零，并记录本轮最优，函数返回0*/
int record(void)
{
float x;
struct log *r;
r = (struct log*)malloc(sizeof(llog));
if(r==NULL)
{
printf("\n内存不够!\n");
exit(1);
}
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(void)
{
int i, j, m;
int gentinfo;
float x;
float cmp;
float gentsuitablitity;
cmp = 1 - pow(i-mp, 11);
for(i=0; i<SUM; i++)
{
if(randsign(cmp)==1)
{
j = randbit(0, 14);
m = 1<< j;
gen_group[i].info = gen_group[i].info^m;
x = convertionB2D(gen_group[i].info);
x = x*(x*(x*(x*(x*(x-10)-26)+344)+193)-1846)-1680;
gen_group[i].suitability = x;
}
}
for(i=0; i<SUM-1; i++)
{
for(j=i+1; j<SUM; j++)
{
if(gen_group[i].suitability > gen_group[j].suitability)
{
gentinfo = gen_group[i].info;
gen_group[i].info = gen_group[j].info;
gen_group[j].info = gentinfo;
gentsuitablitity = gen_group[i].suitability;
gen_group[i].suitability = gen_group[j].suitability;
gen_group[j].suitability = gentsuitablitity;
}
}
}
}
void showresult(int flag)
{
int i, j;
struct log *logfree;
struct log *logprint;
logprint = (struct log *)malloc(sizeof(llog));
if(logprint==NULL)
{
printf("分配内存");
exit(1);
}
logprint = head;
FILE *logf;
if(flag == 0)
printf("\n已到最大搜索次数，搜索失败！\n");
else
{
printf("当取值%f时表达式达到最小值为%f\n",
convertionB2D(gen_result.info), gen_result.suitability);
printf("收敛过程记录与文件log.txt");
if((logf = fopen("log.txt", "w+"))==NULL)
{
printf("Cannot creat/open file");
exit(1);
}
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);
}
getchar();
}
int randsign(float 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(void)
{
int x;
x = rand()/2;
return x;
}
float convertionB2D(int x)
{
float y;
y = x;
y = (y - 8192)/1000;
return y;
}
int convertionD2B(float x)
{
int g;
g = (x*1000) + 8192;
return g;
}
int createmask(int a)
{
int mask;
mask = (1<<(a+1)) - 1;
return mask;
}
高手们帮我看看这个遗传算法哪里出错了？？？
谢谢！！！
