#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define PI 3.142
#define M 18
#define N 15
#define U 20
#define P 200 // 种群数目
#define PC 0.4
#define PA 0.1
#define G 100
#define func(x, y) 21.5+(x)*sin(4*PI*(x))+(y)*sin(20*PI*(y))
int toop = 0;
double function(int polution[M+N])
{
int i;
double x1 = 0, x2 = 0;
for (i=0; i<M; i++)
x1 = x1 + polution[i] * pow(2,i);
x1 = x1 / (pow(2,M)-1) * 15.1 - 3.0;
for (i=M; i<M+N; i++)
x2 = x2 + polution[i] * pow(2,i-M);
x2 = x2 / (pow(2,N)-1) * 1.7 + 4.1;
return func(x1, x2);
}
/*种群初始化*/
void initiate(int (*parents)[M+N])
{
int i, j, sb1, sb2, k, _parents[U][M+N];
double pa1 = 0.98, pa2 = 0.01, p, func1, func2;
/*随即初始化U个Parents*/
srand((unsigned)time(NULL));
for (i=0; i<U; i++)
for (j=0; j<M+N; j++)
*(*(_parents+i)+j) = rand() % 2;
/*逐位精英选择高频变异U个Parents*/
for (i=0; i<U; i++)
{
for (j=0; j<M+N; j++)
{
p = rand() / RAND_MAX;
func1 = function(*(_parents + i));
*(*(_parents + i) + j) = *(*(_parents + i) + j) ^ 1;
func2 = function(*(_parents + i));
if ((func1 < func2) && (p < pa1))
continue;
else if ((func1 > func2) && (p < pa2))
*(*(_parents + i) + j) = *(*(_parents + i) + j) ^ 1;
}
}
/*产生整个种群，保持U个Parents染色体相应基因段*/
for (i=0; i<P; i++)
{
sb1 = rand() % (M+N);
sb2 = rand() % (M+N);
k = rand() % U;
if (sb1 > sb2)
{
sb1 = sb1 ^ sb2;
sb2 = sb2 ^ sb1;
sb1 = sb1 ^ sb2;
}
for (j=0; j<sb1; j++)
*(*(parents + i) + j) = rand() % 2;
for (j=sb1; j<sb2; j++)
*(*(parents + i) + j) = *(*(_parents + k) + j);
for (j=sb2; j<M+N; j++)
*(*(parents + i) + j) = rand() % 2;
}
}
/*种群选择，采用锦标赛选择法,锦标赛规模为2*/
void selection(int (*parents)[M+N])
{
int i, j, sel1, sel2, _parents[P][M+N];
double func1, func2;
for (i=0; i<P; i++)
{
sel1 = rand() % P;
sel2 = rand() % P;
func1 = function(*(parents + sel1));
func2 = function(*(parents + sel2));
if (func1 > func2)
for (j=0; j<M+N; j++)
*(*(_parents + i) + j) = *(*(parents + sel1) + j);
else
for (j=0; j<M+N; j++)
*(*(_parents + i) + j) = *(*(parents + sel2) + j);
}
for (i=0; i<P; i++)
for (j=0; j<M+N; j++)
*(*(parents + i) + j) = *(*(_parents + i) + j);
}
/*交叉操作，采取交叉概率与汉明距离成正比的交叉策略*/
void crossover(int (*parents)[M+N])
{
int i, j, cross1, crossp1, cross2, crossp2, hamming = 0, temp, k;
double func1, func2;
for (i=0; i<P; i++)
{
/*随即选择交叉的子代*/
cross1 = rand() % P;
cross2 = rand() % P;
/*计算hamming距离*/
for (j=0; j<M+N; j++)
if (*(*(parents + cross1) + j) != *(*(parents + cross2) + j))
hamming++;
/*若hammin距离大，则进行交叉；若hamming距离小，则先变异后交叉*/
if (hamming/(M+N) < PC)
{
func1 = function(*(parents + cross1));
func2 = function(*(parents + cross2));
k = rand() % (M+N);
if (func1 < func2)
*(*(parents + cross1) + k) = *(*(parents + cross1) + k) ^ 1;
else
*(*(parents + cross2) + k) = *(*(parents + cross2) + k) ^ 1;
}
/*两点交叉*/
crossp1 = rand() % (M+N);
crossp2 = rand() % (M+N);
if (crossp1 > crossp2)
{
crossp1 = crossp1 ^ crossp2;
crossp2 = crossp2 ^ crossp1;
crossp1 = crossp1 ^ crossp2;
}
for (j=crossp1; j<=crossp2; j++)
{
temp = *(*(parents + cross1) + j);
*(*(parents + cross1) + j) = *(*(parents + cross2) + j);
*(*(parents + cross2) + j) = temp;
}
}
}
/*变异操作*/
void mutation(int (*parents)[M+N])
{
int i, n;
double r;
/*当r<PA时，进行编译*/
for (i=0; i<P; i++)
{
r = rand() / (double)(RAND_MAX);
if (r < PA)
{
n = rand() % (M+N);
*(*(parents+i)+n) = (*(*(parents+i)+n))^1;
}
}
}
/*求最优解*/
int max(int (*parents)[M+N])
{
int i, k;
double max, func;
max = function(*(parents));
k = 0;
for (i=1; i<P; i++)
{
func = function(*(parents + i));
if (func > max)
{
max = func;
k = i;
}
}
return k;
}
/*输出最优解*/
void output(int (*parents)[M+N])
{
int i, k;
k = max(parents);
for (i=0; i<M+N; i++)
{
printf("%d", *(*(parents + k) + i));
}
printf("\ntoop:%d\nmax=%f\n", toop, function(*(parents + k)));
}
void main(void)
{
int sa_parents[P][M+N], i;
int max_k, flag = 0 ;
double max_temp, max_value;
initiate(sa_parents);
max_k = max(sa_parents);
max_value = function(*(sa_parents + max_k));
for (i=0; i<G; i++)
{
selection(sa_parents);
crossover(sa_parents);
mutation(sa_parents);
toop++;
max_temp = max_value;
max_k = max(sa_parents);
max_value = function(*(sa_parents + max_k));
if (max_temp == max_value)
flag++;
if (flag == 10)
break;
}
output(sa_parents);
}
