硕士生考查课程考试试卷考试科目：考生姓名：考生学号：学院：专业：考生成绩：任课老师(签名)考试日期：年月日午时至时《MATLAB 教程》试题：A 、利用MATLAB 设计遗传算法程序，寻找下图11个端点最短路径，其中没有连接端点表示没有路径。

要求设计遗传算法对该问题求解。

ae h kB 、设计遗传算法求解f (x)极小值，具体表达式如下：321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =⎧=⎪⎨⎪-≤≤=⎩∑ 要求必须使用m 函数方式设计程序。

C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。

以上四题任选一题进行实验，并写出实验报告。

选择题目：B 、设计遗传算法求解f (x)极小值，具体表达式如下：321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =⎧=⎪⎨⎪-≤≤=⎩∑ 要求必须使用m 函数方式设计程序。

一、问题分析（10分）这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。

实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。

在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。

二、实验原理与数学模型（20分）（1）试验原理：用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。

其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。

每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。

这一过程循环执行，直到满足优化准则为止。

最后，末代个体经解码，生成近似最优解。

基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。

遗传算法是一种现代智能算法，实际上它的功能十分强大，能够用于求解一些难以用常规数学手段进行求解的问题，尤其适用于求解多目标、多约束，且目标函数形式非常复杂的优化问题。

但是遗传算法也有一些缺点，最为关键的一点，即没有任何理论能够证明遗传算法一定能够找到最优解，算法主要是根据概率论的思想来寻找最优解。

因此，遗传算法所得到的解只是一个近似解，而不一定是最优解。

（2）数学模型对于求解该问题遗传算法的构造过程：（1）确定决策变量和约束条件；（2）建立优化模型；（3）确定编码方法：用2个实数分别表示两个决策变量，分别将的定义域离散化为从离散点-5.12到离散点5.12的Size 个实数。

（4）确定个体评价方法：个体的适应度直接取为对应的目标函数值，即123()(,,)F x f x x x 设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子（6）确定遗传算法的运行参数：群体大小M=500，终止进化代数G=200，交叉概率Pc=0.90，采用自适应变异概率即变异概率与适应度有关，适应度越小，变异概率越大。

简化数学模型：基本遗传算法可定义为一个7元组：GA ＝ (M, F, s, c, m, pc, pm )M ——群体大小；F ——个体适应度评价函数；s ——选择操作算于；c ——交叉操作算子：m ——变异操作算于；pc ——交叉概率；pm ——变异概率；三、实验过程记录（含基本步骤、程序代码及异常情况记录等）（60分）================================================================= 基本步骤：第一步：确定决策变量及各种约束条件，即确定出个体的表现型 X 和问题的解空间； 第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型 x 及遗传算法的搜索空间；第四步：确定解码方法，即确定出由个体基因型 x 到个体表现型 X 的对应关系或转换方法；第五步：确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规则；第六步：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子具体操作方法。

第七步：确定遗传算法有关运行参数，即M,G,Pc,Pm等参数。

================================================================= 程序代码：程序1：主程序%%程序源代码%%主程序：用遗传算法求解函数优化问题。

函数名称存储为main.m%% 清空环境clcclear%% 遗传算法参数maxgen=30; %进化代数sizepop=100; %种群规模pcross=[0.6]; %交叉概率pmutation=[0.01]; %变异概率lenchrom=[1 1 1]; %变量字串长度bound=[-5.12 5.12;-5.12 5.12;-5.12 5.12]; %变量范围%% 个体初始化individuals=struct('fitness',zeros(1,sizepop), 'chrom',[]); %个体avgfitness=[]; %种群平均适应度bestfitness=[]; %种群最佳适应度bestchrom=[]; %适应度最好染色体% 初始化种群for i=1:sizepopindividuals.chrom(i,:)=Code(lenchrom,bound); %随机产生个体x=individuals.chrom(i,:);individuals.fitness(i)=fun(x); %个体适应度end%找最好的染色体[bestfitness bestindex]=min(individuals.fitness);bestchrom=individuals.chrom(bestindex,:); %最好的染色体avgfitness=sum(individuals.fitness)/sizepop; %染色体的平均适应度% 记录每一代进化中最好的适应度和平均适应度trace=[];%% 进化开始for i=1:maxgen% 选择操作individuals=Select(individuals,sizepop);avgfitness=sum(individuals.fitness)/sizepop;% 交叉操作individuals.chrom=Cross(pcross,lenchrom,individuals.chrom,sizepop ,bound);% 变异操作individuals.chrom=Mutation(pmutation,lenchrom,individuals.chrom,s izepop,[i maxgen],bound);% 计算适应度for j=1:sizepopx=individuals.chrom(j,:);individuals.fitness(j)=fun(x);end%找到最小和最大适应度的染色体及它们在种群中的位置[newbestfitness,newbestindex]=min(individuals.fitness);[worestfitness,worestindex]=max(individuals.fitness);% 代替上一次进化中最好的染色体if bestfitness>newbestfitnessbestfitness=newbestfitness;bestchrom=individuals.chrom(newbestindex,:);endindividuals.chrom(worestindex,:)=bestchrom;individuals.fitness(worestindex)=bestfitness;avgfitness=sum(individuals.fitness)/sizepop;trace=[trace;avgfitness bestfitness]; %记录每一代进化中最好的适应度%和平均适应度end%进化结束%% 结果显示figure[r c]=size(trace);plot([1:r]',trace(:,1),'r-',[1:r]',trace(:,2),'b-');title(['函数值曲线 ''终止代数＝' num2str(maxgen)],'fontsize',12); xlabel('进化代数','fontsize',12);ylabel('函数值','fontsize',12);legend('各代平均值','各代最佳值','fontsize',12);% 窗口显示bestfitnessbestpop=xgrid on================================================================= 程序2：将编码编码成染色体%子程序：编码操作，函数名称存储为code.mfunction ret=Code(lenchrom,bound)%本函数将变量编码成染色体，用于随机初始化一个种群% lenchrom input : 染色体长度% bound input : 变量的取值范围% ret output: 染色体的编码值flag=0;while flag==0pick=rand(1,length(lenchrom));ret=bound(:,1)'+(bound(:,2)-bound(:,1))'.*pick; %线性插值flag=test(lenchrom,bound,ret); %检验染色体的可行性end================================================================= 程序3：测试操作%子程序：测试操作，函数名称存储为test.mfunction flag=test(lenchrom,bound,code)% lenchrom input : 染色体长度% bound input : 变量的取值范围% code output: 染色体的编码值flag=1;[n,m]=size(code);for i=1:nif code(i)<bound(i,1) || code(i)>bound(i,2)flag=0;endend================================================================= 程序4：对每一代种群进行选择%子程序：选择操作，函数名称存储为Select.mfunction ret=Select(individuals,sizepop)% 本函数对每一代种群中的染色体进行选择，以进行后面的交叉和变异% individuals input : 种群信息% sizepop input : 种群规模% opts input : 选择方法的选择% ret output : 经过选择后的种群individuals.fitness= 1./(individuals.fitness);sumfitness=sum(individuals.fitness);sumf=individuals.fitness./sumfitness;index=[];for i=1:sizepop %转sizepop次轮盘pick=rand;while pick==0pick=rand;endfor j=1:sizepoppick=pick-sumf(j);if pick<0index=[index j];break; %寻找落入的区间，此次转轮盘选中了染色体i；%注意：在转sizepop次轮盘的过程中，有可能会重复选择某些染色体。