#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "time.h"
#define Q_NUM 81//3//9//27//81 // 划分子空间的个数
#define POPSIZE 250//100//100//100//250 // 种群的数量
#define NVARS 4//1//2//3//4 // 变量的数量
#define M_SELECT 10 // 选择后的数量
#define GLOBAL_GEN 50000//2000//2000//5000//50000 // 演化代数
#define SUB_GEN 100000//5000//5000//20000//100000 // 子种群演化代数
#define MAX_NUM 10//5//10//10//10 // p的上界
#define MIN_NUM 5//1//3//4//5 // p的下界
#define N1_NUM 150//100//100//100//150 // 子种群的个体数量
#define LBOUND -10.0
#define UBOUND 10.0
#define ANS_NUM 324//3//18//81//324 // 最优解的个数
#define EPSILON_N 0.005//0.5//0.5//0.5//0.005 // p的下界
#define ALPHA 0.05//0.2//0.2//0.2//0.05 // p的下界
// a满足总和固定为1的，每个元素的范围是-0.5~1.5 的系数
double EPSILON = EPSILON_N, A[M_SELECT];
int cur_best, cur_worst; // 当前最好的,当前最差的
double best_fitness, worst_fitness; // 当前最好最坏的适应值
struct genotype
{
double gene[NVARS]; // 基因
double fitness; // 适应度
double upper[NVARS]; // 上边界
double lower[NVARS]; // 下界
};
struct genotype population[POPSIZE]; // 当前种群
struct genotype newpopulation[MAX_NUM]; // p个个体的种群
struct genotype subpopulation[N1_NUM]; // 子种群
struct genotype ansPopulation[ANS_NUM]; // ANS_NUM个最优解
void generateA()
{ // 生成一个和为1固定的随机序列a
double sum = 0, minbound = 0.5, maxbound = 1.5;
for (int i = 0; i < M_SELECT - 1; i++)
{
A[i] =(maxbound - minbound) * rand() / (1.0 * RAND_MAX) + minbound;
sum = sum + A[i];
maxbound = 1.5 < 1.5-sum ? 1.5 : 1.5 - sum;
minbound = -0.5 > (-0.5-sum) ? -0.5 : (-0.5 - sum);
}
A[ M_SELECT - 1] = 1-sum;
}
double calfitness(double *x)
{ // 计算一个基因的适应度，shubert函数值取负
double result = 1.0, tmp = 0.0;
for (int i = 0; i < NVARS; i++)
{
tmp = 0.0;
for (double j = 1.0; j < 6; j++)
tmp += j * cos((j+1) * x[i] + j);
result *= tmp;
}
return -result;
}
void init1Gene(genotype &single, double lower[], double upper[])
{ // 初始化一个个体
for (int i = 0 ; i < NVARS; i++)
{
single.lower[i] = lower[i];
single.upper[i] = upper[i];
single.gene[i] = ((double)(rand() / (1.0*RAND_MAX))) * (upper[i] - lower[i]) + lower[i];
}
single.fitness = calfitness(single.gene);
}
void initialize(double lbound[], double ubound[])
{ // 初始化一个种群
EPSILON = EPSILON_N; // 初始化EPSILON
for (int j = 0; j < POPSIZE; j++)
init1Gene(population[j], lbound, ubound);
}
void keepbestworst(genotype *pops, int sizes)
{ // 确定最好的和最差的个体
best_fitness = -INT_MAX, worst_fitness = INT_MAX;
for (int mem = 0; mem < sizes; mem++)
{
if (pops[mem].fitness < worst_fitness)
{
cur_worst = mem;
worst_fitness = pops[mem].fitness;
}
if (pops[mem].fitness > best_fitness)
{
cur_best = mem;
best_fitness = pops[mem].fitness;
}
}
}
void select(genotype pops[], int sizes)
{ // 从种群中选取 M_SELECT 个个体多父体杂交
genotype single = pops[0];
int selected[M_SELECT] = {0};
for(int i = 0; i < M_SELECT; i ++)
selected[i] = rand() % sizes;
generateA(); // 生成系数 A
for (int i = 0; i < NVARS; i++)
{
double tmp = 0.0;
for (int j = 0; j < M_SELECT; j++)
tmp += pops[selected[j]].gene[i] * A[j];
// 越界处理
if (tmp < single.lower[i]) single.gene[i] = single.lower[i];
else if (tmp > single.upper[i]) single.gene[i] = single.upper[i];
else single.gene[i] = tmp;
}
single.fitness = calfitness(single.gene);
if (single.fitness > worst_fitness)
pops[cur_worst] = single;
}
double dis(double *x, double *y)
{ // 两个个体之间的距离
double sum = 0.0;
for (int i = 0; i < NVARS; i++)
sum += (x[i] - y[i]) * (x[i] - y[i]);
return sqrt(sum);
}
int selectFromglobal()
{ // 从全局演化的种群中选取p个个体
bool isBad[POPSIZE] = {false};
int p = 0, k = 0;
for (int i = 0; i < POPSIZE - 1; i++)
for (int j = i + 1; j < POPSIZE; j++)
if ( !isBad[j] && dis(population[i].gene, population[j].gene) <= EPSILON )
isBad[j] = true;
for (int i = 0; i < POPSIZE; i++)
if (!isBad[i]) p++;
if (p <= MAX_NUM && p >= MIN_NUM)
{ // 程序出口，筛选出了p个满足要求的个体
for (int i = 0; i < POPSIZE; i++)
if (!isBad[i])
newpopulation[k++] = population[i];
return p;
}
else if (p > MAX_NUM)
EPSILON = EPSILON * (1 + ALPHA);
else if (p < MIN_NUM)
EPSILON = EPSILON / (1 + ALPHA);
return selectFromglobal();
}
void initSubpop(genotype single, int p)
{ // 初始化子种群
double lower[NVARS], upper[NVARS];
for (int i = 0; i < N1_NUM; i++)
{
double tmp = EPSILON * (1.0 + 1.0 * i / (p - 1)) / 2.0;
for(int j = 0; j < NVARS; j++)
{
lower[j]= single.gene[j] - tmp < single.lower[j] ? single.lower[j] : single.gene[j] - tmp;
upper[j] = single.gene[j] + tmp > single.upper[j] ? single.upper[j] : single.gene[j] + tmp;
}
init1Gene(subpopulation[i], lower, upper);
}
}
void push_ans(genotype *totalans, int &anssizes, genotype *subans, int sizes)
{ // 采用插入排序
for (int i = 0, j; i < sizes; i++)
{
for(j = anssizes; j > 0 && totalans[ j - 1].fitness < subans[i].fitness; j--);
if (j < ANS_NUM && dis(totalans[j].gene, subans[i].gene) > EPSILON)
{
for(int k = anssizes; k > j; k--)
totalans[ k ] = totalans[ k - 1];
totalans[ j ] = subans[i];
}
if (++anssizes > ANS_NUM) anssizes = ANS_NUM;
}
}
void main(int args, char * argv)
{
srand( (unsigned int)time(0) ); // 随机种子
int totalans = 0;
double ubound[NVARS], lbound[NVARS], lbound_vals[3], ubound_vals[3];
for(int i = 0 ; i < 3; i++)
{
lbound_vals[i] = i / 3.0 * (UBOUND - LBOUND) + LBOUND;
ubound_vals[i] = (i + 1) / 3.0 * (UBOUND - LBOUND) + LBOUND;
}
printf("GLME_DD算法，整个解空间划分为%d个子空间\n", Q_NUM);
clock_t start=clock(), t1;
for (int q = 0; q < Q_NUM; q++)
{
t1 = clock();
printf("在第%d个子空间执行GLME算法\n", q + 1);
for (int i = 0; i < NVARS; i++)
{
lbound[i] = lbound_vals[(int)(q / pow(3.0, i)) % 3];
ubound[i] = ubound_vals[(int)(q / pow(3.0, i)) % 3];
}
printf("\tGLME算法第一步全局演化\n");
initialize(lbound, ubound);
keepbestworst(population, POPSIZE); // 1.1
int generation = 0; // 1.2
while(generation++ < GLOBAL_GEN) //1.3
{
select(population, POPSIZE); // 选择M个个体多父体杂交
keepbestworst(population, POPSIZE);
}
int p = selectFromglobal(); // 这里得到的是 newpopulation
printf("\tGLME算法第二步从全局中选取p=%d个不同的个体\n", p);
printf("\tGLME算法第三步子空间的演化\n");
for (int i = 0; i < p; i++)
{ // 对p个个体分别对每个个体生成一个子空间，并在该子空间中进行演化计算
initSubpop(newpopulation[i], p); // 3.1,3.2
keepbestworst(subpopulation, N1_NUM);
int t = 0;
while(t++ < SUB_GEN && abs(worst_fitness - best_fitness) > 0.00000001) // 3.3
{
select(subpopulation, N1_NUM); // 选择适合的生存下来 3.4
keepbestworst(subpopulation, N1_NUM); //
}
push_ans(ansPopulation, totalans, subpopulation, N1_NUM);
}
printf("\t第%d个子空间耗时：%f秒\n\n", q+1, 1.0*(clock() - t1)/CLOCKS_PER_SEC);
}
double totaltime = (double)(clock() - start)/CLOCKS_PER_SEC;
printf("\n计算结束，结果输出到文件！算法运行时间为%f秒\n", totaltime);
FILE *galog; // 输出到文件
if ( !(galog = fopen("data.txt","w"))) exit(-1);
fprintf(galog, "序号 x[1] x[2] x[3] x[4] <值>");
for (int j = 0; j < ANS_NUM; j++)
{
fprintf (galog,"\n%03d ", j + 1);
for(int k = 0; k < NVARS; k++)
fprintf (galog,"%0.8f ", ansPopulation[j].gene[k]);
fprintf (galog," <%0.12f>", -ansPopulation[j].fitness);
}
fprintf(galog, "\n成功结束运行，算法运行时间为%f秒！\n", totaltime);
fclose(galog);
system("pause");
}
