aga.txt

采用了保优的选择遗传算法 终止条件的判断是：到达一定的代数。可改进为：相邻若干代的种群平均适应值的变化来判断。若相邻若干代的种群平均适应值为变化或者是变化小于某一阈值

        for(j = 0; j < stop; j++)
        {
            if(tmp&mask)
                printf("1");
            else
                printf("0");
            tmp = tmp>>1;
        }
    }
}

void preselect()//预选函数
{
    int j;
    sumfitness = 0;
    for(j = 0; j < popsize; j++) sumfitness += oldpop[j].fitness;//初始化时第一代的适应值和
}

int select()  // 轮盘赌选择 
{
    extern float randomperc();
    float sum, pick;
    int i;
    pick = randomperc();//一个随机数
    sum = 0;
    if(sumfitness != 0)
    {
        for(i = 0; (sum < pick) && (i < popsize); i++)
            sum += (float)(oldpop[i].fitness/sumfitness);
    }
    else
        i = rnd(1,popsize);//产生一个随机整数
    return(i-1);
}

void statistics(struct individual *pop)  // 计算种群统计数据  
{
    int i, j;
    sumfitness = 0.0;
    min = pop[0].fitness;
    max = pop[0].fitness;
    // 计算最大、最小和累计适应度  
    for(j = 0; j < popsize; j++)
    {
        sumfitness = sumfitness + pop[j].fitness;            
        if(pop[j].fitness > max) max = pop[j].fitness;        
        if(pop[j].fitness < min) min = pop[j].fitness;         
        // new global best-fit individual  
        if(pop[j].fitness > bestfit.fitness)
		{
			for(i = 0; i < chromsize; i++)
				bestfit.chrom[i]      = pop[j].chrom[i];
            bestfit.fitness    = pop[j].fitness;
            bestfit.varible   = pop[j].varible;
            bestfit.generation = gen;
		}
	}
    // 计算平均适应度  
    avg = sumfitness/popsize;
}

void title()
{
	
	printf("SGA Optimizer");
	
	printf("基本遗传算法\n");
}

void repchar (FILE *outfp,char *ch,int repcount)//输出 
{
    int j;
    for (j = 1; j <= repcount; j++) printf("%s", ch);
}

void skip(FILE *outfp,int skipcount)//输出回车
{
    int j;
    for (j = 1; j <= skipcount; j++) printf("\n");
}

void objfunc(struct individual *critter)  // 计算适应度函数值  
{
    unsigned mask=1;
    unsigned bitpos;
    unsigned tp;
    double  bitpow ;
    int j, k, stop;
    critter->varible = 0.0;
    for(k = 0; k < chromsize; k++)
    {
        if(k == (chromsize-1))
            stop = lchrom-(k*(8*sizeof(unsigned)));
        else
            stop =8*sizeof(unsigned);
        tp = critter->chrom[k];
        for(j = 0; j < stop; j++)
        {
            bitpos = j + (8*sizeof(unsigned))*k;
            if((tp&mask) == 1)
            {
                bitpow = pow(2.0,(double) bitpos);
                critter->varible = critter->varible + bitpow;
            }
            tp = tp>>1;
        }
    }
    critter->varible =-1+critter->varible*3/(pow(2.0,(double)lchrom)-1);//变异概率
    critter->fitness =critter->varible*sin(critter->varible*10*atan(1)*4)+2.0;//适应度函数
}

void  mutation(unsigned *child)   //变异操作 
{
    int j, k, stop;
    unsigned mask, temp = 1;//temp是模板
    for(k = 0; k < chromsize; k++)
    {
        mask = 0;
        if(k == (chromsize-1))
            stop = lchrom - (k*(8*sizeof(unsigned)));
        else
            stop = 8*sizeof(unsigned);
        for(j = 0; j < stop; j++)
        {
            if(flip(pmutation))//以pmutation概率产生1，即以此概率变异
            {
                mask = mask|(temp<<j);
                nmutation++;
            }
        }
		if(mask)//将确定要变异的个体（mask=1）与当代最优个体进行逐位比较，相同则赋以较小的变异概率，不同则赋以稍大的概率
		{
			int j1, k1, stop1;
			unsigned mask1 = 1, tmp,tmp1;
			for(k1 = 0; k1 < chromsize; k1++)
			 {
			  tmp =bestfit.chrom[k];
			  tmp1=child[k];
			  if(k1 == (chromsize-1))
			    stop1 = lchrom - (k1*(8*sizeof(unsigned)));
			 else
			    stop1 =8*sizeof(unsigned);
			  for(j1 = 0; j1< stop; j1++)
			  {
			    if(tmp&tmp1)
					pmutation=pm1;
			    else
					pmutation=pm1-(pm1-pm2)*(max-newpop[j].fitness)/(max-avg); 
				 if(flip(pmutation))
					child[k] = child[k]^mask;//^表示次方,变异操作
			    tmp=tmp>>1;
			    tmp1=tmp1>>1;
			  }
			}
		}
        
    }
}

int crossover (unsigned *parent1, unsigned *parent2, unsigned *child1, unsigned *child2)
// 由两个父个体交叉产生两个子个体  
{
    int j, jcross, k;
    unsigned mask, temp;
	//自适应交叉概率  
	double fp_fitness   =   0; //用来确定交叉概率的适应度值
	if(gen!=0) 
	{ 
		if(oldpop[temp_mate1].fitness>=oldpop[temp_mate2].fitness) 
			fp_fitness   =   oldpop[temp_mate1].fitness; 
		else 
			fp_fitness   =   oldpop[temp_mate2].fitness; 
		if(fp_fitness>=avg) //若此时适应度值大于平均适应度值，则减小交叉概率
			pcross   =   pc1-(pc1-pc2)*(fp_fitness-avg)/(max-avg); 
		else //否则不变
			pcross   =   pc2; 
	} 
	
    if(flip(pcross))//以pcross概率产生0或1
    {
        jcross = rnd(1 ,(lchrom - 1));// 产生交叉位
        ncross++;
        for(k = 1; k <= chromsize; k++)
        {
            if(jcross >= (k*32))//32=(k*(8*sizeof(unsigned)))，即交叉位为最后一位
            {
                child1[k-1] = parent1[k-1];//直接复制
                child2[k-1] = parent2[k-1];
            }
            else if((jcross < (k*32)) && (jcross > ((k-1)*32)))
            {
                mask = 1;
                for(j = 1; j <= (jcross-1-((k-1)*32)); j++)
                {
                    temp = 1;
                    mask = mask<<1;
                    mask = mask|temp;
                }
				//交叉最后不到一个字节的基因
                child1[k-1] = (parent1[k-1]&mask)|(parent2[k-1]&(~mask));
                child2[k-1] = (parent1[k-1]&(~mask))|(parent2[k-1]&mask);
            }
            else
            {
                child1[k-1] = parent2[k-1];
                child2[k-1] = parent1[k-1];
            }
        }
    }
    else     //交叉
    {
        for(k = 0; k < chromsize; k++)
        {
            child1[k] = parent1[k];
            child2[k] = parent2[k];
        }
        jcross = 0;
    }
    return(jcross);
}

void advance_random()  // 产生55个随机数  
{
    int j1;
    double new_random;
    for(j1 = 0; j1 < 24; j1++)
    {
        new_random = oldrand[j1] - oldrand[j1+31];
        if(new_random < 0.0) new_random = new_random + 1.0;//矫正
        oldrand[j1] = new_random;
    }
    for(j1 = 24; j1 < 55; j1++)
    {
        new_random = oldrand [j1] - oldrand [j1-24];
        if(new_random < 0.0) new_random = new_random + 1.0;
        oldrand[j1] = new_random;
    }
}

int flip(double prob) // 以一定概率产生0或1  
{
    float randomperc();
    if(randomperc() <= prob)
        return(1);
    else
        return(0);
}

void randomize()  // 设定随机数种子并初始化随机数发生器  
{
    float randomseed;
    int j1;
    for(j1=0; j1<=54; j1++)
		oldrand[j1] = 0.0;
    jrand=0;
	//do
	//  {            
	printf("随机数种子[0-1]:");
	scanf("%f", &randomseed);
	//   }
	//   while((randomseed < 0.0) || (randomseed > 1.0));
    warmup_random(randomseed);
}

double randomnormaldeviate() // 产生随机标准差  
{
    //double sqrt(), log(), sin(), cos();
    float randomperc();
    double t, rndx1;
    if(rndcalcflag)
    {   rndx1 = sqrt(- 2.0*log((double) randomperc()));
	t = 6.2831853072 * (double) randomperc();
	rndx2 = rndx1 * sin(t);
	rndcalcflag = 0;
	return(rndx1 * cos(t));
    }
    else
    {
        rndcalcflag = 1;
        return(rndx2);
    }
}

float randomperc() //与库函数random()作用相同, 产生[0,1]之间一个随机数  
{
    jrand++;
    if(jrand >= 55)
    {
        jrand = 1;
        advance_random();
    }
    return((float) oldrand[jrand]);
}

int rnd(int low, int high) //在整数low和high之间产生一个随机整数 
{
    int i;
    float randomperc();
    if(low >= high)
        i = low;
    else
    {
        i =(int)((randomperc() * (high - low + 1)) + low);
        if(i > high) i = high;
    }
    return(i);
}


void warmup_random(float random_seed)  // 初始化随机数发生器 
{
    int j1, ii;
    double new_random, prev_random;
	
    oldrand[54] = random_seed;
    new_random = 0.000000001;
    prev_random = random_seed;
    for(j1 = 1 ; j1 <= 54; j1++)
    {
        ii = (21*j1)%54;
        oldrand[ii] = new_random;
        new_random = prev_random-new_random;//新一代的随机数概率要小于前代
        if(new_random<0.0) new_random = new_random + 1.0;
        prev_random = oldrand[ii];
    }
	//多次调用随机数函数，使得随机数更加随机
    advance_random();
    advance_random();
    advance_random();
    jrand = 0;
}


void main(int argc,char *argv[])    //  主程序   

{
    struct individual *temp;
	
	title();
	printf("输入遗传算法执行次数(1-5):");
	scanf("%d",&maxruns);
	for(run=1; run<=maxruns; run++)
    {
        initialize();
        for(gen=0; gen<maxgen; gen++)
        {
			printf("\n第 %d / %d 次运行: 当前代为 %d, 共 %d 代\n", run,maxruns,gen,maxgen);
            // 产生新一代  
            generation();
            // 计算新一代种群的适应度统计数据  
            statistics(newpop);
            // 输出新一代统计数据  
            report();
            temp = oldpop;
            oldpop = newpop;
            newpop = temp;
        }
        freeall();
    }
}