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

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

/package otherFile;

import javautilRandom;

import tGraphTdcppGraph;

import shuffP;

/

/

@author vaqeteart

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

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

算法步骤：

1、初始化

11、生成初始种群编码

12、计算每个个体的适配值。

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

2、选择和遗传，

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

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

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

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

24、计算每个个体的适配值。

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

26、转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;//22222

//factor = IntegerMAX_VALUE / popNum;//to avoid overflow when select,for every fitness

evolutionTim = 0;/////

evolutionLim = 15;///////

//thistpGraph=new TdcppGraph(tG);

//eliminTim = 0;

//eliminLim

curBestFitness = 0;

//curBestCode = new int[eulerCodelength];

//for(int i = 0; i < curBestCodelength; ++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[eulerCodelength];

iFitness[i] = 0;

}

Systemoutprintln("构造函数,需要填入代码");

}

//initialize the originalpopulation

void initPopulation()

{

//初始化种群

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

//get the initial individual

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

//{

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

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

//}

//ShuffEP s = new ShuffEP(thistpGraph);

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

//{

// sshuff(tmpCode);

// for(int j = 0; j < tmpCodelength; ++j)

// {

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

// }

//}

Systemoutprintln("初始化种群,需要填入代码");

//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 += tpGraphEdge(codes[i][j], codes[i][j + 1])getCost(time);

// }

// iFitness[i] = factor - time;

// if(iFitness[i] < 0)

// {

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

// Systemexit(1);

// }

//}

Systemoutprintln("计算每个个体适应度,需要填入代码");

}

//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 < curBestCodelength; ++i)

// {

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

// }

}

Systemoutprintln("记录最优个体,需要填入代码");

}

//selection and reproduce individual in population

void selIndividual()

{

int tmpiFitness[] = new int[iFitnesslength];

tmpiFitness[0] = iFitness[0];

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

//复制个体

//清除原来的群体

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

//for(int i = 0; i < codeslength; ++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;

// }

//}

Systemoutprintln("复制个体,需要填入代码");

for(int i = 1; i < tmpiFitnesslength; ++i)

{

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

//iFitness[i] = 0;

}

//轮盘赌选择个体

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

{

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

for(int j = 0; j < tmpiFitnesslength; ++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];

//}

Systemoutprintln("选择个体，需要填入代码");

}

//get the copied fitness in iFitness

}

//match every two individual and cross the code

void matchCross()

{

//需要填入代码

Systemoutprintln("配对交叉,需要填入代码");

}

//mutate by a specifical probability

void mutate()

{

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

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

}

//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;

}

}

}

遗传算法是一种进化算法，进化是什么哪？就是种群逐渐适应生存环境，种群中个体不断得到改良的过程。

遗传算法是一种对生物遗传的模拟、在算法中，初始化一个种群，种群中的每个染色体个体都是一种解决方案，我们通过适应性fitness来衡量这个解决方案的好坏。并对它们进行选择、变异、交叉的 *** 作，找到最优的解决方案。

总结一下遗传算法的基本的步骤：

1初始化一个种群，并评估每条染色体所对应个体的适应度。

2选择、交叉、变异，产生新的种群

3再评估每个个体的适应值，如果适应值达到要求或者达到最大循环次数，否则重复2，不断产生新种群。

知道了GA的大致流程之后、来具体分析一下细节，怎么实现吧

我们知道遗传算法起源于生物遗传，因此在种群中每个个体就是一个染色体，那如何对染色体进行编码，让它表示我们的解决方案那（就是把现实要优化的参数用编码表示成一个染色体）。这里就遇到了一个编码、解码的问题，我们将需要优化的目标编码成染色体，然后再解码为我们可以用来计算fitness的解；

一般在进行参数优化时，一般有两种方式：实数编码、二进制编码

实数编码：基因直接用实数进行表示，这样的表示方法比较简单，不用特意解码了，但是在交叉和变异时，容易过早收敛，陷入局部最优。

二进制编码：将基因用二进制的形式表示，将参数的值转化为二进制形式，这样交叉、变异时更好 *** 作，多样性好，但是占用的存储空间大，需要解码。

染色体就称为个体。对于一次实验，个体就是需要优化参数的一种解、许多这样的个体就构成了种群。

在面对群体中那么多个体时，如何判断个体的好坏呢，就是通过适应值函数了，将解带入适应值函数，适应值越大、解越好。

在遗传算法中，我们怎么使得里面的个体变得越来越优秀呢？

核心思想就是：选择优秀的、淘汰不好的，并且为了生成更好的解，我们要尝试交叉、变异，带来新的解。

选择就是从当前的种群中选择出比较好的个体、淘汰不好的个体

常见的选择方法有：轮盘赌选择、锦标赛选择、最佳保留选择等等

轮盘赌选择就是根据每个个体fitness和种群所有fitness之和比较，确定每个个体被选中的概率，然后进行n次选择，选择n个个体构成新种群，是一种放回抽样的方式。

锦标赛就是每次从种群中选择m个个体，选择最优的，放入新种群，重复选择，直到新种群中个体数目达到n。

最佳保留选择就是在轮盘赌的基础上，将fitness个体先加进新种群，因为轮盘赌是一种概率模型，可能存在最优个体没有进入新种群的情况。

在选择之后，就要考虑产生新的、更优秀的解，为种群带来新的血液。遗传算法的思路是交叉两个优秀的解，往往get好的解。

交叉通过在经过选择的种群中，随机选择一对父母，将它们的染色体进行交叉，生成新的个体，替代原来的解。

常用的交叉方法有：单点交叉、多点交叉等等。

交叉就像生物里面，染色体交换基因一样的～但是并不是种群中所有个体都进行交叉的，实现时可以，设置一个交叉率和交叉概率，随机选择种群中两个体、随机一个数，小于交叉率就进行交叉 *** 作，并根据交叉概率判断交叉的程度，从而生成新个体，反之就保留这两个体。

变异也是一种产生新个体的方式，通过改变个体上基因，期望产生更好的解。比如在以二进制编码的个体上，将里面的0、1进行等位变化啥的，就是0变1、1变0这样。同样也要考虑变异率、变异产生的新解是不可控的，可能很好，也可能很坏，不能像交叉一样，确保一定的效果，所以往往变异率设置的比较小。

1 遗传算法实现过程

现实生活中很多问题都可以转换为函数优化问题，所以本文将以函数优化问题作为背景，对GA的实现过程进行探讨。大部分函数优化问题都可以写成求最大值或者最小值的形式，为了不是一般性，我们可以将所有求最优值的情况都转换成求最大值的形式，例如，求函数f(x)的最大值，

clip_image002

若是求函数f(x)的最小值，可以将其转换成g(x)=-f(x)，然后求g(x)的最大值，

clip_image004

这里x可以是一个变量，也可是是一个由k个变量组成的向量, x=(x1, x2, …, xk)。每个xi, i=1,2,…,k, 其定义域为Di，Di=[ai, bi]。

一般规定f(x)在其定义域内只取正值，若不满足，可以将其转换成以下形式，

clip_image006

其中C是一个正常数。

11 编码与解码

要实现遗传算法首先需要弄清楚如何对求解问题进行编码和解码。对于函数优化问题，一般来说，有两种编码方式，一是实数编码，一是二进制编码，两者各有优缺点，二进制编码具有稳定性高、种群多样性大等优点，但是需要的存储空间大，需要解码过程并且难以理解；而实数编码直接用实数表示基因，容易理解并且不要解码过程，但是容易过早收敛，从而陷入局部最优。本文以最常用的二进制编码为例，说明遗传编码的过程。

从遗传算法求解的过程来看，需要处理好两个空间的问题，一个是编码空间，另一个是解空间，如下图所示

clip_image007

从解空间到编码空间的映射过程成为编码过程；从编码空间到解空间的映射过程成为解码过程。下面就以求解一个简单的一维函数f(x) = -(x-1)^2+4, x的取值范围为[-1,3]最大值为例，来说明编码及解码过程。

编码：

在编码之前需要确定求解的精度，在这里，我们设定求解的精度为小数点后四位，即1e-4。这样可以将每个自变量xi的解空间划分为clip_image011个等分。以上面这个函数为例，即可以将x的解空间划分为(3-(-1))1e+4=40000个等分。使ni满足clip_image013，这里ni表示使上式成立的最小整数，即表示自变量xi的基因串的长度。因为215<40000<216 ，这里ni取16。例如0000110110000101就表示一个解空间中的基因串。表示所有自变量x=(x1, x2, …, xk)的二进制串的总长度称为一个染色体(Chromosome)的长度或者一个个体(Individual)的长度，clip_image015。编码过程一般在实现遗传算法之前需要指定。

解码：

解码即将编码空间中的基因串翻译成解空间中的自变量的实际值的过程。对于二进制编码而言，每个二进制基因串都可以这样翻译成一个十进制实数值，clip_image017。例如基因串0000110110000101，可以翻译为clip_image019，这里二进制基因串转变成十进制是从左至右进行的。

12 初始化种群

在开始遗传算法迭代过程之前，需要对种群进行初始化。设种群大小为pop_size，每个染色体或个体的长度为chromo_size，种群的大小决定了种群的多样性，而染色体的长度则是由前述的编码过程决定的。一般随机生成初始种群，但是如果知道种群的实际分布，也可以按照此分布来生成初始种群。假设生成的初始种群为(v1, v2, …, vpop_size)。

13 选择 *** 作

选择 *** 作即从前代种群中选择个体到下一代种群的过程。一般根据个体适应度的分布来选择个体。以初始种群(v1, v2, …, vpop_size)为例，假设每个个体的适应度为(fitness(v1), fitness(v2),…, fitness(vpop_size))，一般适应度可以按照解码的过程进行计算。以轮盘赌的方式选择个体，如下图

clip_image020

随机转动一下轮盘，当轮盘停止转动时，若指针指向某个个体，则该个体被选中。很明显，具有较高适应度的个体比具有较低适应度的个体更有机会被选中。但是这种选择具有随机性，在选择的过程中可能会丢失掉比较好的个体，所以可以使用精英机制，将前代最优个体直接选到下一代中。

轮盘赌选择具体算法如下（这里假定种群中个体是按照适应度从小到大进行排列的，如果不是，可以按照某种排序算法对种群个体进行重排）：

Selection Algorithm

var pop, pop_new;/pop为前代种群，pop_new为下一代种群/

var fitness_value, fitness_table;/fitness_value为种群的适应度，fitness_table为种群累积适应度/

for i=1:pop_size

r = randfitness_table(pop_size);/随机生成一个随机数，在0和总适应度之间，因为fitness_table(pop_size)为最后一个个体的累积适应度，即为总适应度/

first = 1;

last = pop_size;

mid = round((last+first)/2);

idx = -1;

/下面按照排中法选择个体/

while (first <= last) && (idx == -1)

if r > fitness_table(mid)

first = mid;

elseif r < fitness_table(mid)

last = mid;

else

idx = mid;

break;

end if

mid = round((last+first)/2);

if (last - first) == 1

idx = last;

break;

end if

end while

for j=1:chromo_size

pop_new(i,j)=pop(idx,j);

end for

end for

/是否精英选择/

if elitism

p = pop_size-1;

else

p = pop_size;

end if

for i=1:p

for j=1:chromo_size

pop(i,j) = pop_new(i,j);/若是精英选择，则只将pop_new前pop_size-1个个体赋给pop，最后一个为前代最优个体保留/

end for

end for

13 交叉 *** 作

交叉 *** 作是对任意两个个体进行的（在这里我们实现的算法是直接对相邻的两个个体进行的）。随机选择两个个体，如下图所示

clip_image001

然后随机生成一个实数0<=r<=1, 如果r<cross_rate， 0<cross_rate<1为交叉概率，则对这两个个体进行交叉，否则则不进行。如果需要进行交叉，再随机选择交叉位置(randchromo_size)，如果等于0或者1，将不进行交叉。否则将交叉位置以后的二进制串进行对换（包括交叉位置）。（注意：有时候还可以进行多点交叉，但是这里只讨论单点交叉的情况）

单点交叉具体算法如下：

Crossover algorithm

for i=1:2:pop_size

if(rand < cross_rate)/cross_rate为交叉概率/

cross_pos = round(rand chromo_size);/交叉位置/

if or (cross_pos == 0, cross_pos == 1)

continue;/若交叉位置为0或1，则不进行交叉/

end if

for j=cross_pos:chromo_size

pop(i,j)<->pop(i+1,j);/交换/

end for

end if

end for

14 变异 *** 作

变异 *** 作是对单个个体进行的。首先生成一个随机实数0<=r<=1, 如果r<mutate_rate，则对此个体进行变异 *** 作， 0<mutate_rate<1为变异概率，一般为一个比较小的实数。对每一个个体，进行变异 *** 作，如下图所示

clip_image001[4]

如个体需要进行变异 *** 作，首先需要确定变异位置(randchromo_size)，若为0则不进行变异，否则则对该位置的二进制数字进行变异：1变成0, 0变成1（当然也可以选择多点进行变异）

单点变异的具体算法描述如下：

Mutation algorithm

for i=1:pop_size

if rand < mutate_rate/mutate_rate为变异概率/

mutate_pos = round(randchromo_size);/变异位置/

if mutate_pos == 0

continue;/若变异位置为0，则不进行变异/

end if

pop(i,mutate_pos) = 1 - pop(i, mutate_pos);/将变异位置上的数字至反/

end if

end for

15 遗传算法流程

遗传算法计算流程图如下图所示

clip_image001[6]

16 MATLAB程序实现

初始化：

%初始化种群

%pop_size: 种群大小

%chromo_size: 染色体长度

function initilize(pop_size, chromo_size)

global pop;

for i=1:pop_size

for j=1:chromo_size

pop(i,j) = round(rand);

end

end

clear i;

clear j;

计算适应度：（该函数应该根据具体问题进行修改，这里优化的函数是前述的一维函数）

%计算种群个体适应度，对不同的优化目标，此处需要改写

%pop_size: 种群大小

%chromo_size: 染色体长度

function fitness(pop_size, chromo_size)

global fitness_value;

global pop;

global G;

for i=1:pop_size

fitness_value(i) = 0;

end

for i=1:pop_size

for j=1:chromo_size

if pop(i,j) == 1

fitness_value(i) = fitness_value(i)+2^(j-1);

end

end

fitness_value(i) = -1+fitness_value(i)(3-(-1))/(2^chromo_size-1);

fitness_value(i) = -(fitness_value(i)-1)^2+4;

end

clear i;

clear j;

对个体按照适应度大小进行排序：

%对个体按适应度大小进行排序，并且保存最佳个体

%pop_size: 种群大小

%chromo_size: 染色体长度

function rank(pop_size, chromo_size)

global fitness_value;

global fitness_table;

global fitness_avg;

global best_fitness;

global best_individual;

global best_generation;

global pop;

global G;

for i=1:pop_size

fitness_table(i) = 0;

end

min = 1;

temp = 1;

temp1(chromo_size)=0;

for i=1:pop_size

min = i;

for j = i+1:pop_size

if fitness_value(j)<fitness_value(min);

min = j;

end

end

if min~=i

temp = fitness_value(i);

fitness_value(i) = fitness_value(min);

fitness_value(min) = temp;

for k = 1:chromo_size

temp1(k) = pop(i,k);

pop(i,k) = pop(min,k);

pop(min,k) = temp1(k);

end

end

end

for i=1:pop_size

if i==1

fitness_table(i) = fitness_table(i) + fitness_value(i);

else

fitness_table(i) = fitness_table(i-1) + fitness_value(i);

end

end

fitness_table

fitness_avg(G) = fitness_table(pop_size)/pop_size;

if fitness_value(pop_size) > best_fitness

best_fitness = fitness_value(pop_size);

best_generation = G;

for j=1:chromo_size

best_individual(j) = pop(pop_size,j);

end

end

clear i;

clear j;

clear k;

clear min;

clear temp;

clear temp1;

选择 *** 作：

%轮盘赌选择 *** 作

%pop_size: 种群大小

%chromo_size: 染色体长度

%cross_rate: 是否精英选择

function selection(pop_size, chromo_size, elitism)

global pop;

global fitness_table;

for i=1:pop_size

r = rand fitness_table(pop_size);

first = 1;

last = pop_size;

mid = round((last+first)/2);

idx = -1;

while (first <= last) && (idx == -1)

if r > fitness_table(mid)

first = mid;

elseif r < fitness_table(mid)

last = mid;

else

idx = mid;

break;

end

mid = round((last+first)/2);

if (last - first) == 1

idx = last;

break;

end

end

for j=1:chromo_size

pop_new(i,j)=pop(idx,j);

end

end

if elitism

p = pop_size-1;

else

p = pop_size;

end

for i=1:p

for j=1:chromo_size

pop(i,j) = pop_new(i,j);

end

end

clear i;

clear j;

clear pop_new;

clear first;

clear last;

clear idx;

clear mid;

交叉 *** 作：

%单点交叉 *** 作

%pop_size: 种群大小

%chromo_size: 染色体长度

%cross_rate: 交叉概率

function crossover(pop_size, chromo_size, cross_rate)

global pop;

for i=1:2:pop_size

if(rand < cross_rate)

cross_pos = round(rand chromo_size);

if or (cross_pos == 0, cross_pos == 1)

continue;

end

for j=cross_pos:chromo_size

temp = pop(i,j);

pop(i,j) = pop(i+1,j);

pop(i+1,j) = temp;

end

end

end

clear i;

clear j;

clear temp;

clear cross_pos;

变异 *** 作：

%单点变异 *** 作

%pop_size: 种群大小

%chromo_size: 染色体长度

%cross_rate: 变异概率

function mutation(pop_size, chromo_size, mutate_rate)

global pop;

for i=1:pop_size

if rand < mutate_rate

mutate_pos = round(randchromo_size);

if mutate_pos == 0

continue;

end

pop(i,mutate_pos) = 1 - pop(i, mutate_pos);

end

end

clear i;

clear mutate_pos;

打印算法迭代过程：

%打印算法迭代过程

%generation_size: 迭代次数

function plotGA(generation_size)

global fitness_avg;

x = 1:1:generation_size;

y = fitness_avg;

plot(x,y)

算法主函数：

%遗传算法主函数

%pop_size: 输入种群大小

%chromo_size: 输入染色体长度

%generation_size: 输入迭代次数

%cross_rate: 输入交叉概率

%cross_rate: 输入变异概率

%elitism: 输入是否精英选择

%m: 输出最佳个体

%n: 输出最佳适应度

%p: 输出最佳个体出现代

%q: 输出最佳个体自变量值

function [m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate, elitism)

global G ; %当前代

global fitness_value;%当前代适应度矩阵

global best_fitness;%历代最佳适应值

global fitness_avg;%历代平均适应值矩阵

global best_individual;%历代最佳个体

global best_generation;%最佳个体出现代

fitness_avg = zeros(generation_size,1);

disp "hhee"

fitness_value(pop_size) = 0;

best_fitness = 0;

best_generation = 0;

initilize(pop_size, chromo_size);%初始化

for G=1:generation_size

fitness(pop_size, chromo_size); %计算适应度

rank(pop_size, chromo_size); %对个体按适应度大小进行排序

selection(pop_size, chromo_size, elitism);%选择 *** 作

crossover(pop_size, chromo_size, cross_rate);%交叉 *** 作

mutation(pop_size, chromo_size, mutate_rate);%变异 *** 作

end

plotGA(generation_size);%打印算法迭代过程

m = best_individual;%获得最佳个体

n = best_fitness;%获得最佳适应度

p = best_generation;%获得最佳个体出现代

%获得最佳个体变量值，对不同的优化目标，此处需要改写

q = 0;

for j=1:chromo_size

if best_individual(j) == 1

q = q+2^(j-1);

end

end

q = -1+q(3-(-1))/(2^chromo_size-1);

clear i;

clear j;

2 案例研究

对上一节中的函数进行优化，设置遗传算法相关参数，程序如下

function run_ga()

elitism = true;%选择精英 *** 作

pop_size = 20;%种群大小

chromo_size = 16;%染色体大小

generation_size = 200;%迭代次数

cross_rate = 06;%交叉概率

mutate_rate = 001;%变异概率

[m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate,elitism);

disp "最优个体"

m

disp "最优适应度"

n

disp "最优个体对应自变量值"

q

disp "得到最优结果的代数"

p

clear;

结果如下：

"最优个体"

m =

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

"最优适应度"

n =

40000

"最优个体对应自变量值"

q =

10000

"得到最优结果的代数"

p =

74

此结果非常准确。

遗传算法有相当大的引用。遗传算法在游戏中应用的现状在遗传编码时, 一般将瓦片的坐标作为基因进行实数编码, 染色体的第一个基因为起点坐标, 最后一个基因为终点坐标, 中间的基因为路径经过的每一个瓦片的坐标。在生成染色体时, 由起点出发, 随机选择当前结点的邻居节点中的可通过节点, 将其坐标加入染色体, 依此循环, 直到找到目标点为止, 生成了一条染色体。重复上述 *** 作, 直到达到指定的种群规模。遗传算法的优点：1、遗传算法是以决策变量的编码作为运算对象，可以直接对集合、序列、矩阵、树、图等结构对象进行 *** 作。这样的方式一方面有助于模拟生物的基因、染色体和遗传进化的过程，方便遗传 *** 作算子的运用。另一方面也使得遗传算法具有广泛的应用领域，如函数优化、生产调度、自动控制、图像处理、机器学习、数据挖掘等领域。2、遗传算法直接以目标函数值作为搜索信息。它仅仅使用适应度函数值来度量个体的优良程度，不涉及目标函数值求导求微分的过程。因为在现实中很多目标函数是很难求导的，甚至是不存在导数的，所以这一点也使得遗传算法显示出高度的优越性。3、遗传算法具有群体搜索的特性。它的搜索过程是从一个具有多个个体的初始群体P(0)开始的，一方面可以有效地避免搜索一些不必搜索的点。另一方面由于传统的单点搜索方法在对多峰分布的搜索空间进行搜索时很容易陷入局部某个单峰的极值点，而遗传算法的群体搜索特性却可以避免这样的问题，因而可以体现出遗传算法的并行化和较好的全局搜索性。4、遗传算法基于概率规则，而不是确定性规则。这使得搜索更为灵活，参数对其搜索效果的影响也尽可能的小。5、遗传算法具有可扩展性，易于与其他技术混合使用。以上几点便是遗传算法作为优化算法所具备的优点。遗传算法的缺点：遗传算法在进行编码时容易出现不规范不准确的问题。

以上就是关于遗传算法的模拟 数据结构题目全部的内容，包括:遗传算法的模拟 数据结构题目、遗传算法理解、求基于遗传算法的TPS的matlab程序，坐标手动输入等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！