Question

请教一道遗传算法的题（要用C++编程解题）

刚开始学遗传算法，理解不够透彻，不太会做题，希望能请高手帮忙。
题目如下：

max = -x1^2 - x2^2
-10<= x1 <=10
-5<=x2<=7

请问这题该如何用C++解决呢？谢谢！
非常感谢这位高手这么详细的回答。不过我的C++不太行，不明白void 要什么时候用，可否能解释一下？每次按compile键之后都会出现 invalid conversion from 'void*' to 'solution'，这个该如何解决。另外就是那一句是cost function呢？第一次看这么长的程序，有很多看不懂，也认不出哪句是定义cost function的。

Answer 1

很简单，例如用基因算法。首先在x1,x2的定义域内随机生成一些解，然后用crossover & mutation，代进你第一个 cost function继续优化就可以了。给你个类似的代码，自己把定义域，costfunction改掉就可以了。对了，这个程序还得检测下得出来的结果是否依然在定义域内，当时忘记弄了

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>

#include <float.h>
#include <time.h>
#include <math.h>

#define MUT_RATE .01
#define MUT_UPER 10
#define MUT_LOWR -10
#define POP_SIZE 100 /* MUST BE EVEN */
#define MAX_ITER 10000
#define SOL_SIZE 30
#define SOL_UPER 500
#define SOL_LOWR -500

/*#define _DEBUG_ 1*/

/*****************************************************************************/

typedef double solution;

/*****************************************************************************/

#if (POP_SIZE % 2) != 0
#error "POP_SIZE must be even!"
#endif

#if (POP_SIZE * MAX_ITER) > 100000000
#warning "Lots of processing!"
#endif

/*****************************************************************************/

void init_population(solution **population, double *sol_fitness);

solution* crossover(solution *A, solution *B);

void mutation(solution *C);

double fitness(solution *s);

void sort_solutions(solution **population, double *sol_fitness);

void perform_step(solution **population, double *sol_fitness);

void debug(char *format, ...);

extern void* xmalloc(size_t size);

/*****************************************************************************/

int
main(int argc, char *argv){

solution **population;
double sol_fitness[POP_SIZE],
best_fit;
int cycle,
best_sol,
i;

setbuf(stderr, NULL);

/* Initialize the random seed */
srand(time(NULL));

debug("srand\n");

/* xmallocate */

population = xmalloc(sizeof(double)*POP_SIZE);
for(i = 0; i < POP_SIZE; i++){
population[i] = xmalloc(sizeof(double)*SOL_SIZE);
}

debug("xmalloc pop\n");

/* Initialize the population */
init_population(population, sol_fitness);
cycle = 0;

debug("init pop\n");

/* Perform a maximum of MAX_ITER iterations */
while(cycle++ < MAX_ITER){
perform_step(population, sol_fitness);
}

debug("perform step\n");

/* Find the best solution */

best_sol = 0;
for(i = 0; i < POP_SIZE; i++){
if(sol_fitness[best_sol] >= sol_fitness[i]){
best_sol = i;
}
}

printf("best solution is: %d\nScore: %f\n", best_sol, sol_fitness[best_sol]);
for(i = 0; i < SOL_SIZE; i++){
printf("%f%s", population[best_sol][i], (i+1) == SOL_SIZE ? "" : ", ");
}
printf("\n\n");

}

/*****************************************************************************/

/* init the population to random values */

void
init_population(solution **population, double *sol_fitness){

int i, j;

for(i = 0; i < POP_SIZE; i++){
for(j = 0; j < SOL_SIZE; j++){
debug("%d, %d\n", i, j);
population[i][j] = (SOL_UPER-SOL_LOWR)*((float)rand()/(float)RAND_MAX)+SOL_LOWR;
}
sol_fitness[i] = fitness(population[i]);
}

}

/*****************************************************************************/

/* Perform a crossover */

solution*
crossover(solution *A, solution *B){

solution *C;
int i;

C = xmalloc(sizeof(solution)*SOL_SIZE);

for(i = 0; i < SOL_SIZE; i++){
C[i] = (i%2 == 0) ? A[i] : B[i];
}

return C;

}
/*****************************************************************************/

/* perform a mutation */

void
mutation(solution *C){

int i;

for(i = 0; i < SOL_SIZE; i++){
if(((float)rand()/(float)RAND_MAX) < MUT_RATE){
C[i] += (MUT_UPER-MUT_LOWR)*(float)rand()/(float)RAND_MAX - MUT_LOWR;
}
}

}

/*****************************************************************************/

/* determine the fitness of a solution */

double
fitness(solution *s){

int i;
double fit;

fit = 0.0;

for(i = 0; i < 30; i++){
fit -= s[i]*sin(sqrt(abs(s[i])));
}

return fit;

}

/*****************************************************************************/

void
sort_solutions(solution **population, double *sol_fitness){

int i,j;
double backup_sol_fitness;
solution *backup_sol;

for(i = 0; i < POP_SIZE; i++){
for(j = 1; j < POP_SIZE; j++){
if(sol_fitness[i] > sol_fitness[j]){
backup_sol_fitness = sol_fitness[i];
backup_sol = population[i];
population[i] = population[j];
sol_fitness[i] = sol_fitness[j];
population[j] = backup_sol;
sol_fitness[j] = backup_sol_fitness;
}
}
}

}

/*****************************************************************************/

/* perform a single step */

void
perform_step(solution **population, double *sol_fitness){

int i;
solution *child1,
*child2;

/* We choose (µ,L), because it is good for multimodal landscapes,
* I assume that the function defined is very multimodal
*/

sort_solutions(population, sol_fitness);

for(i = 0; i < POP_SIZE; i += 2){
debug("iter: %d\n", i);
child1 = crossover(population[i], population[i+1]);
child2 = crossover(population[i+1], population[i]);

debug("perform_step: crossover\n");

free(population[i]);
free(population[i+1]);
debug("perform_step: free'ing\n");
population[i] = child1;
population[i+1] = child2;
debug("perform_step: set children\n");
}

debug("perform_step: Crossovers done\n");

for(i = 0; i < POP_SIZE; i++){
mutation(population[i]);
debug("perform_step: Mutation\n");
sol_fitness[i] = fitness(population[i]);
}

}

/*****************************************************************************/

#ifdef _DEBUG_
void
debug(char *format, ...){

va_list args;

va_start(args, format);
vfprintf(stderr, format, args);
va_end(args);

}
#else
void debug(char *format, ...){}
#endif

/*****************************************************************************/

void*
xmalloc(size_t size){

void *mem;

if(!size){
debug("Can not allocate memory of this size: %d\n", size);
exit(1);
}

mem = NULL;
mem = malloc(size);

if(!mem){
debug("Unable to allocate memory\n");
exit(1);
}

return mem;

}

/*****************************************************************************/

这个是求最小值的，你只要把 costfunction设置成-f(x)就可以求最大值

Answer 2

void 是空类型，你可以把函数参数或者返回值定义为void型，以此不需要输入参数或返回值；也可以定义void*类型的指针，来表示这个类型是不属于任何类型的，你可以用static_cast将它转变成原有的类型，通常在调用一些操作系统api时会用到。楼主出现的问题应该是类型转换的问题，C++是强类型的语言，必须类型匹配，或者实现了隐式的构造函数或赋值函数，void*是一个DWORD或LONG型的地址指针，而solution应该是楼主自定义的类型，可以尝试static_cast<solution*>([你传入的指针，就是那个(void*)类型的])，试试看吧，也不知道对不对

Answer 3

#include<iostream>
using namespace std;

int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
int max(int a, int b, int c)
{
if(a>b&&a>c)
return a;
if(b>c)
return b;
else
return c;
}
double max(double a,double b)
{
if(a-b>0.00001)
return a;
else
return b;
}
double max(double a, double b, double c)
{
if(a-b>0.00001&&a-c>0.00001)
return a;
if(b-c>0.00001)
return b;
else
return c;
}
void main()
{
int a=2, b=5, c=6;
double a1=2.14,b1=3.14,c1=5.5;

cout<<max(a,b)<<endl;
cout<<max(a,b,c)<<endl;
cout<<max(a1,b1)<<endl;
cout<<max(a1,b1,c1)<<endl;
}

Answer 4

max=0