遗传算法的模拟 数据结构题目

我这里给出了一个简单的模板如果需要编代码填代码的地方已经有提示了

/*package otherFile;

import java.util.Random;

import tGraph.TdcppGraph;

import shuffP.*;

*/

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

*

* @author vaqeteart

* 这里是遗传算法的核心框架遗传算法的步骤：

* 遗传算法核心部分的算法描述

* 算法步骤：

* 1、初始化

* 1.1、生成初始种群编码

* 1.2、计算每个个体的适配值。

* 1.3、记录当前最优适配值和最优个体

* 2、选择和遗传，

* 2.0、若当前最优适配值多次小于已有的最优适配值（或相差不大）很多次，或者进化的次数超过设定的限制，转4。

* 2.1、按照与每个个体的适配值成正比的概率选择个体并复制，复制之后个体的数目和原始种群数目一样。

* 2.2、（最好先打乱复制后种群的个体次序）对复制后个体进行两两配对交叉，生成相同数目的的下一代种群。

* 2.3、对下一代种群按照一定的概率进行变异

* 2.4、计算每个个体的适配值。

* 2.5、记录当前最优适配值和最优个体

* 2.6、转2

* 3、返回当前最优适配值以及其对应的编码，结束。

*

* 注意：

* 1.这里的内容相当于一个模板，编写具体的遗传算法的时候，可以按照这个模板的形式编写。

* 2.应该填写代码的地方都有提示的标记。

*/

public class GAKernel

{

//number of population

int popNum;//set the number to 20 in constructor

//current evolution times

int evolutionTim;

//limit of the evolution times

int evolutionLim;//set the number to 20 in constructor

//unaccepted times

//int eliminTim;

//limit of unaccepted times

//int eliminLim;

//current best euler code

//int curBestCode[];

//current best fitness

int curBestFitness;

//fitness of every individual

int iFitness[];

//fator of compute the fitness

int factor;

//..................other members.............................................

//the graph

//public TdcppGraph tpGraph;

//the eula code group

//int codes[][];

//every population

//

//constructor

GAKernel(TdcppGraph tG,int eulerCode[])

{

popNum = 32;//2*2*2*2*2

//factor = Integer.MAX_VALUE / popNum;//to avoid overflow when select,for every fitness

evolutionTim = 0;/////

evolutionLim = 15;///////

//this.tpGraph=new TdcppGraph(tG);

//eliminTim = 0;

//eliminLim

curBestFitness = 0;

//curBestCode = new int[eulerCode.length];

//for(int i = 0; i < curBestCode.length; ++i)

//{

// curBestCode[i] = eulerCode[i];

//}

//??curBestFitness

iFitness = new int[popNum];

//codes = new int[popNum][];//lines

for(int i = 0; i < popNum; ++i)

{

//codes[i] = new int[eulerCode.length];

iFitness[i] = 0;

}

System.out.println("构造函数,需要填入代码");

}

//initialize the originalpopulation

void initPopulation()

{

//.......................初始化种群........................................

//int tmpCode[] = new int[curBestCode.length];

//get the initial individual

//for(int i = 0; i < curBestCode.length; ++i)

//{

// tmpCode[i] = curBestCode[i];

// codes[0][i] = tmpCode[i];

//}

//ShuffEP s = new ShuffEP(this.tpGraph);

//for(int i = 1; i < popNum; ++i)

//{

// s.shuff(tmpCode);

// for(int j = 0; j < tmpCode.length; ++j)

// {

// codes[i][j] = tmpCode[j];

// }

//}

System.out.println("初始化种群,需要填入代码");

//get the initial fitness to the member iFitness

computeFitness();

//get the initial best individual and fitness

recordBest();

}

//compute the fitness of every individual in current population

void computeFitness()

{

//........................计算每个个体适应度.......................

//int time = 0;

//for(int i = 0; i < popNum; ++i)

//{

// time = 0;

// for(int j = 0; j < codes[i].length - 1; ++j)

// {

// time += tpGraph.Edge(codes[i][j], codes[i][j + 1]).getCost(time);

// }

// iFitness[i] = factor - time;

// if(iFitness[i] < 0)

// {

// System.out.println("错误，某个个体适应度过小使得适配值出现负数");//lkdebug

// System.exit(1);

// }

//}

System.out.println("计算每个个体适应度,需要填入代码");

}

//record the current best fitness and the according individual

void recordBest()

{

int bestIndex = -1;

for(int i = 0; i < popNum; ++i)

{

if(curBestFitness < iFitness[i])

{

curBestFitness = iFitness[i];

bestIndex = i;

}

}

//............................记录最优个体.............................

if(bestIndex > -1)

{

// for(int i = 0; i < curBestCode.length; ++i)

// {

// curBestCode[i] = codes[bestIndex][i];

// }

}

System.out.println("记录最优个体,需要填入代码");

}

//selection and reproduce individual in population

void selIndividual()

{

int tmpiFitness[] = new int[iFitness.length];

tmpiFitness[0] = iFitness[0];

//建立临时群体用于选择交换

//.................................复制个体...............................

//清除原来的群体

//int tmpCode[][] = new int[popNum][];

//for(int i = 0; i < codes.length; ++i)

//{

// tmpCode[i] = new int[codes[i].length];//???

// for(int j = 0; j < codes[i].length; ++j)

// {//copy to tmpCode and reset codes

// tmpCode[i][j] = codes[i][j];

// codes[i][j] = -1;

// }

//}

System.out.println("复制个体,需要填入代码");

for(int i = 1; i < tmpiFitness.length; ++i)

{

tmpiFitness[i] = tmpiFitness[i - 1] + iFitness[i];

//iFitness[i] = 0;

}

//轮盘赌选择个体

for(int i = 0; i < popNum; ++i)

{

int rFit = new Random().nextInt(tmpiFitness[tmpiFitness.length - 1]);

for(int j = 0; j < tmpiFitness.length; ++j)

{

if(rFit < tmpiFitness[j])

{

rFit = j;//record the index of the individual

break;

}

}

if(rFit == 0)

{

iFitness[i] = tmpiFitness[rFit];

}

else

{

iFitness[i] = tmpiFitness[rFit] - tmpiFitness[rFit - 1];//copy fitness

}

//....................................选择个体...........................

//for(int j = 0; j < tmpCode[rFit].length; ++j)

//{

// codes[i][j] =tmpCode[rFit][j];

//}

System.out.println("选择个体，需要填入代码");

}

//get the copied fitness in iFitness

}

//match every two individual and cross the code

void matchCross()

{

//........................需要填入代码................................

System.out.println("配对交叉,需要填入代码");

}

//mutate by a specifical probability

void mutate()

{

//........................按照一定的概率进行变异.......................

System.out.println("按照一定的概率进行变异,需要填入代码");

}

//evolve current population

void evolve()

{

selIndividual();

matchCross();

mutate();

}

//compute the approximative best value by GA

//find approximative best solution by GA

public void compute()

{

initPopulation();

//while((evolutionTim < evolutionLim) && (eliminTim < eliminLim))

while(evolutionTim < evolutionLim)

{

evolve();

//get the initial fitness to the member iFitness

computeFitness();

//get the initial best individual and fitness

recordBest();

++evolutionTim;

}

}

}

//类似这样定义：

// Genetic.h: interface for the CGenetic class.

//

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)

#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

//#include"definition.h"

typedef struct mychrom{

double chrom[MAXVARNO];

double fitness;//适应度

}CHROM;

//#include "BpNet.h"

////////

class CGenetic

{

public:

bool IsStoped;

double dblAngle;

CHROM best;

//Mm mData,mResult;

double dblDifference;//差异〉改值的染色体视为不同

double dblCre;//适应度>改值的染色体符合条件

int iBestNum;//符合条件的染色体数目

//CBpNet * bpnet;

//double (* obj_fun)();

double CalFitness(CHROM chrome);//计算适应度函数

long gen;//当前进化代数

void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围

double randxy(double x,double y);//产生x,y之间的随机数

void statistic(CHROM pop[]);

CHROM bestchrom[MAXBESTNUM];//最优染色体

bool begin();//主函数

void generation();//一次进化

int rselect();//轮盘赌选择

CHROM newpop[POPSIZE];//种群

CHROM oldpop[POPSIZE];//种群

double pmutation;//变异概率

double pcross;//交叉概率

long maxgen;//最大进化代数

int iVarNo;//染色体数目

double sumfitness;

CGenetic();

virtual ~CGenetic();

private:

double angle(CHROM ch1,CHROM ch2);

bool IsNew(CHROM ch);//判断是否为符合条件的新染色体

double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别

bool identify(CHROM chrome);//验证是否为合法的染色体

double varminmax[MAXVARNO][2];

void init();//初始化，设置初始染色体

void mutation(CHROM *chrome);//对新染色体进行变异

bool flip(double possibility);//测试

//交叉操作，iPlace指明新染色体位置

void cross(CHROM chrom1,CHROM chrom2,int iPlace);

bool IsSetScope;

};

#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)

代码站有的是....

有难度~太专业了`