遗传算法 (100分)

遗传算法 （最好也有模拟退火，禁忌搜索算法）的delphi实现，实在不行c的也可以。
急，今晚就要！！！！
分不够，以后补上

给你看一篇 ：
/************************************************************************
* 简单遗传算法(SGA) *
* 主要算法模块有:选择 交叉 变异 (三个遗传操作) 和 群体更新 *
* 以及 随即数发生器 输入 输出 译码 适应度计算 *
* 选择机制为比例选择 交叉采用单点交叉 变异采用简单的位点变异方式 *
* 多变量编码采用把各个变量染色体基因交替相连的方式,体现在译码模块中 *
************************************************************************/
/* 1999.10.20 增添编码函数,方便输入初值 */
// ------------------------------------------------------
// A Simple Genetic Algorithm - SGA
// (c) Ding Zhen Yu 1998
// ------------------------------------------------------
// All Rights Reserved
// ------------------------------------------------------

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

//#define NeedInputInitialChrom // 如果需要输入初始值,一般是因为上次没有
// 计算完成,可以接着再算
//#define NeedInputData //输入种群中第一个的大小(0~1.0之间)
#undef NeedInputInitialChrom

/*NOTICE:modify varnumber and perchrom for each problem.*/
#define varnumber 32 /* 变量个数 */
#define perchrom 5 /* 单变量染色体长度 */
#define popsize 20 /* 群体规模(应为偶数) */
#define maxgen 5000 /* 遗传世代数 */
#define maxstring varnumber*perchrom /* 多变量总的染色体长度 */
#define pcross 0.80 /* 交叉概率[0.00,1.00] */
#define pmutation 0.001 /* 变异概率[0.00,1.00] */

externdo
uble Obj_func(double *x);

struct pp {
unsigned int chrom[maxstring];
do
uble x[varnumber],fitness;
unsigned int parent1,parent2,xsite;
};

struct pp oldpop[popsize],newpop[popsize],p1[popsize];

unsigned int lchrom,gen,nmutation,ncross,jcross,maxpp,minpp;
double sumfitness,avg,max,min;
double coef;
long seedl[1];
double objfunc(double *);
/* 目标函数,应该是正的,最小问题要化为最大问题 */
void statistics();
/* 群体适应度统计 */
int rselect();
/* 赌轮选择 */
int flip(double);
/* 贝努利测试 */
int crossover();
/* 一点交叉操作 */
int mutation(unsigned int);
/* 变异操作 */
void generation();
/* 世代更新 */
void initialize();
/* 初始化 */
void initpop();

void report();

void initdata();
void initreport();
void decode(unsigned int *,do
uble *);
/* 解码,变量取值在0到1之间 */
void encode(unsigned int *,do
uble *);
/* 编码,输入变量取值在0到1之间 */
double randomd01();
int randomi01();
int randomi(int,int);

/* SGA main program */
/* xx will be ado
uble between 0 and 1.0 */
void sga(double *xx)
{
long int i,gen,k,j;
do
uble oldmax;
int oldmaxpp;

gen=0;
seedl[0]=-9l;
//printf("initializing........../n");
initialize();
for (i=0;
i<popsize;
i++)
{
p1=newpop;
newpop=oldpop;
}
report(gen);
for (i=0;
i<popsize;
i++) newpop=p1;
do
{
gen=gen+1;
oldmax=max;
oldmaxpp=maxpp;
generation();
statistics(newpop);
if (max<oldmax)
{
for (j=0;
j<lchrom;
j++)
newpop[minpp].chrom[j]=oldpop[oldmaxpp].chrom[j];
for (j=0;
j<varnumber;
j++)
newpop[minpp].x[j]=oldpop[oldmaxpp].x[j];

newpop[minpp].fitness=oldpop[oldmaxpp].fitness;
statistics(newpop);
}
report(gen);
for (i=0;
i<popsize;
i++)
{
p1=oldpop;
oldpop=newpop;
newpop=p1;
}
} while (gen<maxgen);
for (i=0;
i<varnumber;
i++)
{
xx=oldpop[maxpp].x;
//printf("xx[%d]=%f ",i,xx);
}
//printf("/n");


return;
}

/* calculate individual fitness */
double objfunc(double *x)
{
do
uble temp;

temp=1.0/Obj_func(x);

return temp;
}

/* statistics of the group fitness */
void statistics(pop)
struct pp *pop;
{
int j;

sumfitness=pop[0].fitness;
min=pop[0].fitness;
max=pop[0].fitness;
maxpp=0;
minpp=0;
for (j=1;j<popsize;j++)
{
sumfitness=sumfitness+pop[j].fitness;
if (pop[j].fitness>max)
{
max=pop[j].fitness;
maxpp=j;
}
if (pop[j].fitness<min)
{
min=pop[j].fitness;
minpp=j;
}
}
avg=sumfitness/(double)popsize;
}

/* new group */
void generation()
{
unsigned int j,mate1,mate2;

j=0;
do
{
mate1=rselect();
mate2=rselect();
crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
decode(newpop[j].chrom,newpop[j].x);
newpop[j].fitness=objfunc(newpop[j].x);
newpop[j].parent1=mate1;
newpop[j].parent2=mate2;
newpop[j].xsite=jcross;
decode(newpop[j+1].chrom,newpop[j+1].x);
newpop[j+1].fitness=objfunc(newpop[j+1].x);
newpop[j+1].parent1=mate1;
newpop[j+1].parent2=mate2;
newpop[j+1].xsite=jcross;
j=j+2;
} while (j<popsize);
}

/* initialize */
void initialize()
{
coef=pow(2.00,perchrom)-1.0;
initdata();
initpop();
statistics(oldpop);
initreport();
}

/* contral parameters input */
void initdata()
{
lchrom=perchrom*varnumber;
nmutation=0;
ncross=0;
}

/* generation of initial group */
/* 按随机方式产生初始解群,或者直接输入前次结束时的染色体,
* 或者按需要输入一个个体 */
void initpop()
{
int i,j,j1;

//printf("initializing populations......../n");
#ifdef NeedInputInitialChrom
printf("input initial chrom:/n");
#endif
for (j=0;j<popsize;j++)
{
//printf("j=%d/n",j);
for (j1=0;j1<lchrom;j1++)
oldpop[j].chrom[j1]=randomi01();
#ifdef NeedInputInitialChrom
for (j1=0;j1<lchrom;j1++)
scanf("%1d",&amp;oldpop[j].chrom[j1]);
printf("%d in %d has been readed./n",j+1,popsize);
#endif
decode(oldpop[j].chrom,oldpop[j].x);
#ifdef NeedInputInitialChrom
for (j1=0;j1<varnumber;j1++)
printf("x[%d]=%f/n",j1,oldpop[j].x[j1]);
#endif
oldpop[j].fitness=objfunc(oldpop[j].x);
oldpop[j].parent1=0;
oldpop[j].parent2=0;
oldpop[j].xsite=0;
}
#ifdef NeedInputData
printf("input %d initial data(0.0~1.0):/n",varnumber);
for (i=0;
i<varnumber;
i++)
scanf("%lf",&amp;oldpop[0].x);
encode(oldpop[0].chrom,oldpop[0].x);
oldpop[0].fitness=objfunc(oldpop[0].x);
oldpop[0].parent1=0;
oldpop[0].parent2=0;
oldpop[0].xsite=0;
#endif
}

/* initialization infomation output */
void initreport()
{
int j,k;

printf("/n--------------------------------------------------------------/n");
printf(" SGA Parameters /n");
printf("--------------------------------------------------------------/n/n");
printf("Population size (popsize) = %d /n",popsize);
printf("Chromosome length (lchrom) = %d /n",lchrom);
printf("Maximum # of generation (maxgen) = %d /n",maxgen);
printf("Crossover probablity (pcross) = %f /n",pcross);
printf("Mutation probablity (pmutation) = %f /n",pmutation);
printf("------------------------------------------/n/n");
printf("Initial Population Maximum Fitness = %f /n",max);
printf("Initial Population Average Fitness = %f /n",avg);
printf("Initial Population Minimum Fitness = %f /n",min);
printf("Initial Population Sum of Fitness = %f /n",sumfitness);
}

/* data output */
void report(int gen)
{
int k,j,i;

for (j=0;
j<79;
j++) printf("*");
printf("/n");
printf("Population Report /n");
printf("Generation %3d /n",gen);

printf("#parents xsite string x fitness /n");
for (j=0;
j<79;
j++) printf("+");
printf("/n");
for (j=0;
j<popsize;
j++)
{
for (k=0;
k<lchrom;
k++)
printf("%d",newpop[j].chrom[k]);
printf("/n");
}
printf("/n");
//for (j=0;
j<popsize;
j++)
j=maxpp;
{
printf("%d %d ",j,newpop[j].parent1);

printf("%d %d ",newpop[j].parent2,newpop[j].xsite);
//for (k=0;
k<lchrom;
k++)
// printf("%d",newpop[j].chrom[k]);

for (i=0;
i<varnumber;
i++)
printf(" %f ",newpop[j].x);
printf("fitness=%f /n",newpop[j].fitness);
}
for (k=0;
k<79;
k++) printf("*");

printf("/n");
printf("RESULT: GEN: %d ",gen);
printf("AVG=%f MIN=%f MAX=%f /n",avg,min,max);
printf("ncross=%d nmutation = %d /n",ncross,nmutation);
}

/* decode */
void decode(unsigned int *pp,double *x)
{
int i,j;
do
uble tt,tt1;

for (i=0;
i<varnumber;
i++)
{
tt1=1.0;
tt=0.0;
for (j=lchrom-1-i;j>-1+(varnumber-i-1);j-=varnumber)
{
if (pp[j]) tt=tt+tt1;
tt1=2.0*tt1;
}
tt=tt/coef;//tt is between 0.0 and 1.0
//change variable's value range
x=0.0001+7.0*tt/10.0;
}
}

/* encode */
void encode(unsigned int *pp,double *x)
{
int i,j,dx;
do
uble fx;

for (i=0;
i<varnumber;
i++)
{
// 注意编码和解码相对应
fx=(x-0.0001)*10.0/7.0;
fx=fx*coef;
dx=(int)(fx);
if ((fx-dx)>0.5) dx+=1;
for (j=lchrom-1-i;j>-1+(varnumber-i-1);
j-=varnumber)
{
if (dx%2==1)
{
pp[j]=1;
//printf("1");
}
else

{
pp[j]=0;
//printf("0");
}
dx=dx/2;
}
}
}

/* select operation */
/*
几种流行的选择机制:
* 1. 赌轮选择(roulette wheel selection)机制;
也叫适应度比例方式(fitness proportional model);
2. 最佳保留(elitist model)选择机制;
3. 期望值模型(expected value model)选择机制;
4. 随机竞争(stochastic tournament)选择机制;
5. 排序(ranking)选择机制;
6. 排挤方法(crowding model);
*/

// 赌轮选择(roulette wheel selection)机制;
int rselect()
{
do
uble rand1,partsum;
int j;

partsum=0.0;
j=0;
rand1=randomd01()*sumfitness;
do
{
partsum=partsum+oldpop[j].fitness;
j=j+1;
} while ((partsum<rand1)&amp;&amp;(j<popsize));
return j-1;
}

/* mutation operation */
int mutation(unsigned int ch)
{
int mutate,j;

mutate=flip(pmutation);
if (mutate)
{
nmutation=nmutation+1;
if (ch) ch=0;
else
ch=1;
}
if (ch)
return 1;
else

return 0;
}

/* crossover operation */
int crossover(unsigned int *parent1,unsigned int *parent2,int k5)
{
int i,j,j1;

if (flip(pcross))
{
jcross=randomi(1,lchrom-1);
ncross=ncross+1;
}
else

jcross=lchrom;
if (jcross!=lchrom)
{
for (j=0;
j<jcross;
j++)
{
newpop[k5].chrom[j]=mutation(parent1[j]);
newpop[k5+1].chrom[j]=mutation(parent2[j]);
}
for (j=jcross;j<lchrom;j++)
{
newpop[k5].chrom[j]=mutation(parent2[j]);
newpop[k5+1].chrom[j]=mutation(parent1[j]);
}
}
else

{
for (j=0;
j<lchrom;
j++)
{
newpop[k5].chrom[j]=mutation(parent1[j]);
newpop[k5+1].chrom[j]=mutation(parent2[j]);
}
}
return 1;
}

/* Bernoulli Trials */
int flip(double probability)
{
do
uble ppp;

ppp=randomd01();
if (ppp<=probability)
return 1;
else

return 0;
}

/* return ado
uble random number between 0.0~1.0 */
double randomd01()
{
int j;
long k;
static long idum2=123456789L;
static long iy=0L;
static long iv[32];
do
uble temp;

if (seedl[0] <= 0L) {
if (-seedl[0] < 1L) seedl[0] = 1L;
else
seedl[0] = -seedl[0];

idum2 = seedl[0];
for (j=32+7;j>=0;j--) {
k = seedl[0]/53668L;
seedl[0] = 40014L * (seedl[0]-k*53668L)-k*12211L;
if (seedl[0] < 0L) seedl[0] += 2147483563L;
if (j < 32) iv[j] = seedl[0];
}
iy=iv[0];
}
k = seedl[0]/53668L;
seedl[0] = 40014L*(seedl[0]-k*53668L)-k*12211L;
if (seedl[0] < 0L) seedl[0] += 2147483563L;
k = idum2/52774L;
idum2 = 40692L*(idum2-k*52774L)-k*3791L;
if (idum2 < 0L) idum2 += 2147483399L;
j = (int)(iy/(1L+2147483562L/32L)) ;
iy = iv[j]-idum2;
iv[j] = seedl[0];
if (iy < 1L) iy += 2147483562L;
if ((temp=(double)(iy)/(double)(2147483563L)) > (1.0-1.2e-7 ))
return (1.0-1.2e-7) ;
else
return temp;
}

/* return a integer random number between 0 and 1 */
int randomi01()
{
if (randomd01()>0.5) return 1;
else
return 0;
}

/* return a interger random number amang 1 and lchrom-1 */
int randomi(int low, int high)
{
int i;

if (low>=high)
i=low;
else

{
i=(int)(randomd01()*lchrom);
if (i>high) i=high;
}
return i;
}

卷起千堆雪tyn,
明天老板要我算个东西，真是急死人了。（都怪平时太贪玩了）
多谢了，有空再聊。