人工智能第二次实验报告 实验题目： 遗传算法的设计与实现 实验目的： 通过人工智能课程的学习，熟悉遗传算法的简单应用。 实验内容 用遗传算法求解f (x) = x2 的最大值，x [0,31]，x取整数。 可以看出该函数比较简单，只要是为了体现遗传算法的思想，在问题选择上，选了一 个比较容易实现的，把主要精力放在遗传算法的实现，以及核心思想体会上。 实验过程： 1. 实现过程 （1）编码 使用二进制编码，随机产生一个初始种群。L 表示编码长度，通常由对问题的求解精度决定，编码长度L 越长，可期望的最优解的精度也就越高，过大的L 会增大运算量。针对该问题进行了简化，因为题设中x [0,31]，所以将二进制长度定为5就够用了； （2）生成初始群体 种群规模表示每一代种群中所含个体数目。随机产生N个初始串结构数据，每个串结构数 据成为一个个体，N个个体组成一个初始群体，N表示种群规模的大小。当N取值较小时， 可提高遗传算法的运算速度，但却降低种群的多样性，容易引起遗传算法早熟，出现假 收敛；而N当取值较大时，又会使得遗传算法效率降低。一般建议的取值范围是20—100。 （3）适应度检测 根据实际标准计算个体的适应度，评判个体的优劣，即该个体所代表的可行解的优劣 。本例中适应度即为所求的目标函数； （4）选择 从当前群体中选择优良（适应度高的）个体，使它们有机会被选中进入下一次迭代过 程，舍弃适应度低的个体。本例中采用轮盘赌的选择方法，即个体被选择的几率与其适 应度值大小成正比； （5）交叉 遗传操作，根据设置的交叉概率对交配池中个体进行基因交叉操作，形成新一代的种 群，新一代中间个体的信息来自父辈个体，体现了信息交换的原则。交叉概率控制着交 叉操作的频率，由于交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率通常 应取较大值；但若过大的话，又可能破坏群体的优良模式。一般取0.4到0.99。 （6）变异 随机选择中间群体中的某个个体，以变异概率大小改变个体某位基因的值。变异为产 生新个体提供了机会。变异概率也是影响新个体产生的一个因素，变异概率小，产生新 个体少；变异概率太大，又会使遗传算法变成随机搜索。一般取变异概率为0.0001—0.1 。 （7）结束条件 当得到的解大于等于900时，结束。从而观看遗传的效率问题。 代码及结果： /*遗传算法设计最大值*/ #include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> #define C 0 //测试 #define CFLAG 4 //测试标记 #define JIAOCHA_RATE 0.5 //交叉概率一般取0.4到0.99 #define BIANYI_RATE 0.09 //变异概率为0.0001-0.1 #define ITER_NUM 1000 //迭代次数 #define POP_NUM 20 //染色体个数 #define GENE_NUM 5 //基因位数 #define FEXP(x) ((x)*(x)) //y=x^2 typedef unsigned int UINT; //染色体 typedef struct{ char geneBit[GENE_NUM]; //基因位 UINT fitValue; //适应值 }Chromosome; //将二进制的基因位转化为十进制 UINT toDec(Chromosome pop){ UINT i; UINT radix = 1; UINT result = 0; for(i=0; i<GENE_NUM; i++) { result += (pop.geneBit[i]-'0')*radix; radix *= 2; } return result; } UINT calcFitValue(UINT x) { return FEXP(x); } void test(Chromosome *pop) { int i; int j; for(i=0; i<POP_NUM; i++) { printf("%d: ", i+1); for(j=0; j<GENE_NUM; j++) printf("%c", pop[i].geneBit[j]); printf(" %4d", toDec(pop[i])); printf(" fixValue=%d\n", calcFitValue(toDec(pop[i]))); } } //变异得到新个体:随机改变基因 void mutation(Chromosome *pop) { UINT randRow, randCol; UINT randValue; randValue=rand
【遗传算法设计与实现】
遗传算法是一种启发式搜索方法，源于生物进化理论，常用于解决优化问题。在本次人工智能实验中，目标是使用遗传算法求解函数 f(x) = x^2 在 x ∈ [0,31] 上的最大值，其中 x 取整数。这个实验旨在让学习者熟悉遗传算法的基本原理和实现步骤。
**1. 编码**
遗传算法的核心是将问题的解编码为一种便于操作的形式。在这个实验中，采用二进制编码方式，因为二进制编码简洁且易于计算机处理。考虑到 x 的范围在 [0,31]，只需要5位二进制数就能表示所有可能的整数值，因此编码长度L被设定为5。
**2. 生成初始群体**
初始群体是由随机生成的个体组成的，这些个体是问题可能解的候选。群体规模N指代每代群体中个体的数量，通常在20到100之间选择，较小的N可能导致算法快速收敛但可能错过全局最优解，而较大的N则会增加计算复杂性。
**3. 适应度检测**
适应度函数衡量了个体解决方案的优劣。在本实验中，适应度直接对应于目标函数f(x)，即个体对应的x值的平方。
**4. 选择**
选择操作基于适应度进行，采用轮盘赌选择法，个体被选择的概率与其适应度成正比，这样优秀的个体更有可能被保留下来。
**5. 交叉**
交叉（或称配对）是遗传算法中创造新个体的主要手段。设定一个交叉概率，如0.5，随机选取两个个体进行基因交叉，生成新的后代。过高或过低的交叉概率可能影响算法性能。
**6. 变异**
变异操作引入了随机性，以防止算法陷入局部最优。每个个体的基因有一定的概率发生变异，通常变异概率在0.0001到0.1之间。过小的变异概率可能导致算法停滞不前，而过大的变异可能导致算法失去稳定性。
**7. 结束条件**
实验在找到解大于等于900时结束，这代表找到一个接近最大值的解。实验还关注算法的效率，即在达到特定解之前需要多少次迭代。
在提供的代码中，可以看到C语言实现的遗传算法框架。`Chromosome`结构体用于存储二进制编码和适应度值，`toDec`函数将二进制编码转换为十进制值，`calcFitValue`计算个体的适应度，而`mutation`函数实现了变异操作。整个算法在`ITER_NUM`迭代次数内运行，并且每次迭代通过选择、交叉和变异操作更新种群。
这个实验为学习者提供了一个基础的人工智能应用实例，帮助他们理解遗传算法的运作机制，并掌握如何在实践中应用这一方法。
