程序设计及应用(Java)实训指导书

程序设计及应用实训指导书 （Java语言） 昆明理工大学信息工程与自动化学院自动化系 张志坤 李勇编 2016年8月 75 / 75下载文档可编辑 一、题目 题目：利用遗传算法仿真猕猴桃组培苗变异 二、目的 （1）掌握Java语言开发环境的搭建，掌握Java基础编程知识。 （2）学习遗传算法的基本原理，利用遗传算法进行猕猴桃遗传变异模拟。 （3）利用excel进行遗传变异数据分析，掌握数据分析方法 三、指导教师 张志坤、李勇 四、地点 昆明理工大学呈贡校区信自楼445。 五、时间及进度安排 时间：20152016学年短学期（2016年8月31日至2016年9月9日） 进度安排： 日 期 环节进程安排摘要 2016-8-31 布置设计任务及环境搭建 2016-9-1 程序结构设计 2016-9-2 程序编写指导 2016-9-5 查阅资料 2016-9-6 查阅资料 2016-9-7 程序编写、分析数据 2016-9-8 报告书编写及指导 2016-9-9 程序、报告检查及成绩评定 六、设备及器材 设备器材：计算机 软件：（1）JDK 1.7及以上；（2）Eclipse-standard-luna； 七、成果要求 实训同学要求完成（一）、（二）、（三）、（四）、（七） 程序设计及应用同学要求完成（一）、（二）、（三）、（四）、（五）、（六）、（七） （一）、遗传算法的基本原理 遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域，是现代有关智能计算中的关键技术。 遗传算法的基本运算过程如下： （1）初始化：设置进化代数计数器t=0，设置最大进化代数T，使用M个个体作为初始群体P(0)。 （2）个体评价：计算群体P(t)中各个个体的适应度。 （3）选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上，利用轮盘赌进行选择。 （4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。 （5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。 （6）终止条件判断：若t=T ，则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。 确定实际问题参数集 对参数集进行编码 初始种群 满足停止规则？ 遗传操作 产生新一代种群 结束 1位串编码的参数 2计算目标函数值 3函数值向适应度值映射 4适应度值调整 评价种群 三个基本算子 1选择 2交叉 3变异 图1 遗传算法解决问题的步骤 遗传算法进行问题求解的实质是，在解的空间中不断遗传，而遗传过程中通过适应度值，选择更适应问题的解作为幸存者和后代，逐步逼近最优解。 1、选择： 从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子(reproduction operator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种：适应度比例方法、随机遍历抽样法、局部选择法等。其中轮盘赌选择法 （roulette wheel selection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个0，1之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。 2、交叉 在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法： 1)实值重组（real valued recombination） 2)离散重组（discrete recombination） 3)中间重组（intermediate recombination） 4)线性重组（linear recombination） 5)扩展线性重组（extended linear recombination）。 6)二进制交叉（binary valued crossover） 7)单点交叉（single-point crossover） 8)多点交叉（multiple-point crossover） 9)均匀交叉（uniform crossover） 10)洗牌交叉（shuffle crossover） 11)缩小代理交叉（crossover with reduced surrogate）。 最常用的交叉算子为单点交叉(one-point crossover)。具体操作是:在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子： 个体A：1 0 0 1 1 1 1 1 0 0 1 0 0 0 新个体 个体B：0 0 1 1 0 0 0 0 0 1 1 1 1 1 新个体 3、变异 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法： a)实值变异 b)二进制变异。 一般来说，变异算子操作的基本步骤如下： a)对群中所有个体以事先设定的变异概率判断是否进行变异 b)对进行变异的个体随机选择变异位进行变异。 遗传算法引入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。 遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合.是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。 基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动(以变异概率P.做变动)，(0，1)二值码串中的基本变异操作如下： 基因位下方标有*号的基因发生变异。 变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值，一般取0.0010.1。 4、终止条件 当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。 （二）、Java开发环境搭建 1、JDK的获取 从Oracle公司的网站上可以免费获取各种版本的JDK，Oracle公司的网址。注意这次设计实用的是JDK 1.7 2、JDK的安装及环境变量的配置 JDK有安装版和直接解压版。 安装版安装方法如下： （1）找到下载的安装包，双击运行。注意：如果是32位系统运行jdk-7u60-windows-i586.exe，64位操作系统运行jdk-7u60-windows-x64.exe。 （2）按照系统提示安装JDK，需注意的是再安装时安装路径尽量不要再C盘，并且安装路径不要包含空格和中文。 （3）环境变量配置 Windows XP：在桌面右击“我的电脑”，然后单击“属性”，在“系统属性”对话框中选择“高级”选项卡，然后单击“环境变量”按钮，打开“环境变量”对话框，找到“系统变量”中名为Path的行，单击编辑，将JDK中bin目录的安装路径加入到环境变量中。为了编程方便可以新建一个classpath的环境变量，并将JDK中lib目录的安装路径加入到该环境变量中。 Windows 7，windows 8，windows 8.1：在桌面右击“我的电脑”，然后单击“属性”，在“系统”对话框中选择“高级系统配置”，在打开的“系统属性”对话框中选择“高级”选项卡，然后单击“环境变量”按钮，打开“环境变量”对话框，找到“系统变量”中名为Path的行，单击编辑，将JDK中bin目录的安装路径加入到环境变量中。为了编程方便可以新建一个classpath的环境变量，并将JDK中lib目录的安装路径加入到该环境变量中。 3、Eclipse的获取与安装 Eclipse是IBM的开源项目，可以从Eclipse官方网站（ ）免费获取。 将下载的压缩包解压至一个不包含中文字符的目录下，即完成安装。 双击eclipse.exe打开eclipse。 （三）、遗传算法编写指导 采用4位DNA编码，M条基因，交叉2带的计算。采用四进制编码。0,1,2,3分别代表G，A，T，C即：。用编码随机产生一个小数，进过筛选适应度后，进行交叉、变异计算后输出计算结果 要求学生根据下面的指导的内容，配置下面的代码，并能够正确运行，阅读并理解下面代码的含义。 1、包的定义 package geneTest; 2、基因类（Gene） public class Gene implements Cloneable protected String allele;/ 等位片段 public String getAllele() return allele; public void setAllele(String allele) this.allele = allele; Override public Object clone() throws CloneNotSupportedException Gene g = null; try g = (Gene)super.clone(); g.allele = new String(allele); catch(CloneNotSupportedException e ) System.out.println(e.getMessage(); return g; 3、基因型类（GeneType） public class GeneType implements Cloneable protected Gene gene;/ 基因序列片段 public Gene getGene() return gene; public void setGene(Gene gene) this.gene = gene; public GeneType(GeneType geneType) super(); this.gene = geneType.getGene(); public GeneType() Override public Object clone() throws CloneNotSupportedException GeneType g = null; try g = (GeneType)super.clone(); g.gene = gene.clone(); catch(CloneNotSupportedException e ) System.out.println(e.getMessage(); return g; 4、表现型类（PhenoType） public class PhenoType implements Cloneable protected double x;/ 表现对应的数值 public double getX() return x; public void setX(double x) this.x = x; public PhenoType(PhenoType phoneType) this.x=phoneType.getX(); public PhenoType() public PhenoType(double x) this.x = x; Override public Object clone() throws CloneNotSupportedException PhenoType g = null; try g = (PhenoType)super.clone(); catch(CloneNotSupportedException e ) System.out.println(e.getMessage(); return g; 5、染色体类（Chromsome） public class Chromsome implements Cloneable protected GeneType geneType;/ 基因型 protected PhenoType phoneType;/ 表现型 public GeneType getGeneType() return geneType; public void setGeneType(GeneType geneType) this.geneType = geneType; public PhenoType getPhoneType() return phoneType; public void setPhoneType(PhenoType phoneType) this.phoneType = phoneType; Override public Object clone() throws CloneNotSupportedException Chromsome g = null; try g = (Chromsome)super.clone(); g.geneType = new GeneType(geneType); g.phoneType = new PhenoType(phoneType); catch(CloneNotSupportedException e ) System.out.println(e.getMessage(); return g; public String toString() String str=; for(int i = 0 ; i geneType.gene.length ; i+) str += geneType.getGene()i.getAllele()+ ; return str; 6、个体类（抽象Individual，具体类RosenbrockIndividual） public abstract class Individual implements Cloneable protected Chromsome chrom;/ 染色体序列 protected double fitness;/ 适应度 protected double relativeFitness; / 相对适应度 protected double targetValue;/ 目标函数值 public Chromsome getChrom() return chrom; public void setChrom(Chromsome chrom) this.chrom = chrom; public double getFitness() return fitness; public void setFitness(double fitness) this.fitness = fitness; public double getRelativeFitness() return relativeFitness; public void setRelativeFitness(double relativeFitness) this.relativeFitness = relativeFitness; public double getTargetValue() return targetValue; public void setTargetValue(double targetValue) this.targetValue = targetValue; /抽象方法 public abstract Individual randomlyGeneratIndividual(CodeScale scale);/ 随机生成个体 public abstract Individual generateIndividualByCode(CodeScale scale,String code);/ 根据编码序列生成个体 public abstract Individual coding(CodeScale scale,Individual indiv);/ 对个体进行编码 public abstract Individual decode(CodeScale scale,Individual indiv);/ 对个体进行解码 public abstract Individual calFitness(Individual indiv);/ 计算适应度 public abstract Individual calTargetValue(Individual indiv);/ 计算目标函数 Override public Object clone() throws CloneNotSupportedException Individual g = null; try g = (Individual)super.clone(); g.chrom = chrom.clone(); catch(CloneNotSupportedException e ) System.out.println(e.getMessage(); return g; public String toString() String str = ; for (int i = 0; i chrom.length; i+) str += chromi.toString(); str+=n; for (int i = 0; i chrom.length; i+) str += chromi.getPhoneType().getX()+ ; str+=fitness+ +relativeFitness+n; return str; public class RosenbrockIndividual extends Individual implements Cloneable Override public Individual randomlyGeneratIndividual(CodeScale scale) double x1 = Math.random() * 4.096 - 2.048; double x2 = Math.random() * 4.096 - 2.048; Individual indiv=new RosenbrockIndividual(); Chromsome chrom = new Chromsome2; chrom0 = new Chromsome(); chrom1 = new Chromsome(); PhenoType phenoType1=new PhenoType(); phenoType1.setX(x1); PhenoType phenoType2=new PhenoType(); phenoType2.setX(x2); chrom0.phoneType=phenoType1; chrom1.phoneType=phenoType2; indiv.setChrom(chrom); indiv = indiv.coding(scale, indiv); return indiv; Override public Individual generateIndividualByCode(CodeScale scale, String code) /一个香蕉个体有两个染色体，需要对两个染色体进行编码 GeneType geneType1 = new GeneType(); GeneType geneType2 =new GeneType(); Gene g1 = new Genescale.geneTypeLength; Gene g2 = new Genescale.geneTypeLength; for(int i=0;iscale.geneTypeLength;i+) Gene gene1 =new Gene(); gene1.setAllele(codei); g1i=gene1; Gene gene2 =new Gene(); gene2.setAllele(codei+scale.geneTypeLength); g2i=gene2; geneType1.setGene(g1); geneType2.setGene(g2); Chromsome chrom1 = new Chromsome(); chrom1.setGeneType(geneType1); Chromsome chrom2 = new Chromsome(); chrom2.setGeneType(geneType2); Chromsome chrom= new Chromsome2; chrom0=chrom1; chrom1=chrom2; Individual indiv=new RosenbrockIndividual(); indiv.setChrom(chrom); indiv = decode(scale,indiv); return indiv; Override public Individual coding(CodeScale scale, Individual indiv) /一个香蕉个体有两个染色体，需要对两个染色体进行编码 double x1 = indiv.chrom0.getPhoneType().getX(); double x2 = indiv.chrom1.getPhoneType().getX(); Chromsome chrom = new Chromsome2; chrom0 = indiv.chrom0; GeneType geneType1 = new GeneType(); Gene g1 = new Genescale.geneTypeLength; for (int i = 0; i scale.geneTypeLength; i+) Gene gene = new Gene(); gene.setAllele(byLengthSpilt(scale,codingVariable(scale,x1)i); g1i = gene; geneType1.setGene(g1); chrom0.setGeneType(geneType1); chrom1 = indiv.chrom1; GeneType geneType2 = new GeneType(); Gene g2 = new Genescale.geneTypeLength; for (int i = 0; i scale.geneTypeLength; i+) Gene gene = new Gene(); gene.setAllele(byLengthSpilt(scale,codingVariable(scale,x2)i); g2i = gene; geneType2.setGene(g2); chrom1.setGeneType(geneType2); Individual individual = new RosenbrockIndividual(); individual = indiv; individual.setChrom(chrom); return individual; private String codingVariable(CodeScale scale,double x) double length =(double) scale.geneTypeLength*scale.geneLength; double y = (x + 2.048) * (Math.pow(2.0, length) - 1.0) / 4.096); String code = Integer.toBinaryString(int) y); for (int i = code.length(); i length; i+) code = 0 + code; return code; public static String byLengthSpilt(CodeScale scale,String str) int j = (int) str.length() / scale.geneLength; String subStr = new Stringj; for (int i = 0; i j; i+) subStri = str.substring(i * scale.geneLength, i * scale.geneLength + scale.geneLength); return subStr; Override public Individual decode(CodeScale scale, Individual indiv) /一个香蕉个体有两个染色体，需要对两个染色体进行解码 String code1 = ; String code2 = ; GeneType geneType1 = indiv.chrom0.getGeneType(); GeneType geneType2 = indiv.chrom1.getGeneType(); for(int i=0;igeneType1.getGene().length;i+) code1 = code1+geneType1.getGene()i.getAllele(); for(int i=0;igeneType2.getGene().length;i+) code2 = code2+geneType2.getGene()i.getAllele(); double x1 = decodeHandle(scale,code1); Chromsome chrom = new Chromsome2; chrom0 = indiv.chrom0; chrom0.setPhoneType(new PhenoType(x1); double x2 = decodeHandle(scale,code2); chrom1 = indiv.chrom1; chrom1.setPhoneType(new PhenoType(x2); Individual individual = new RosenbrockIndividual(); individual = indiv; individual.setChrom(chrom); return individual; public double decodeHandle(CodeScale scale,String code) double y = (double) Integer.parseInt(code, 2); double length =(double) scale.geneTypeLength*scale.geneLength; double x = (4.096 * y / (Math.pow(2.0, length) - 1.0) - 2.048; return x; Override public Individual calFitness(Individual indiv) Individual individual = new RosenbrockIndividual(); individual = indiv; individual = calTargetValue(indiv); individual.setFitness(individual.getTargetValue(); return individual; Override public Individual calTargetValue(Individual indiv) Individual individual = new RosenbrockIndividual(); individual = indiv; double targetValue = rosenbrock(indiv.chrom0.getPhoneType().getX(), indiv.chrom1.getPhoneType().getX(); individual.setTargetValue(targetValue); return individual; public static double rosenbrock(double x1, double x2) double fun; fun = 100 * Math.pow(x1 * x1 - x2), 2) + Math.pow(1 - x1), 2); return fun; Override public Object clone() throws CloneNotSupportedException RosenbrockIndividual g = null; try g = (RosenbrockIndividual)super.clone(); catch(CloneNotSupportedException e ) System.out.println(e.getMessage(); return g; 7、种群类（抽象类Population，具体类RosenbrockPopulation） public abstract class Population implements Cloneable protected int generationId; / 种群的代数 protected Individual pop; / 种群 protected double averageFitness; / 平均适应度 protected double totalFitness; / 平均适应度 protected Individual bestIndividual;/ 当前代适应度最好的个体 protected int bestIndex;/ 当前代适应度最好的个体对应的下标 protected Individual worstIndividual;/ 当前代适应度最差的个体 protected Individual currentBesIndividual;/ 目前适应度最好的个体 public int getBestIndex() return bestIndex; public void setBestIndex(int bestIndex) this.bestIndex = bestIndex; public int getGenerationId() return generationId; public void setGenerationId(int generationId) this.generationId = generationId; public Individual getPop() return pop; public void setPop(Individual pop) this.pop = pop; public double getAverageFitness() return averageFitness; public void setAverageFitness(double averageFitness) this.averageFitness = averageFitness; public double getTotalFitness() return totalFitness; public void setTotalFitness(double totalFitness) this.totalFitness = totalFitness; public Individual getBestIndividual() return bestIndividual; public void setBestIndividual(Individual bestIndividual) this.bestIndividual = bestIndividual; public Individual getWorstIndividual() return worstIndividual; public void setWorstIndividual(Individual worstIndividual) this.worstIndividual = worstIndividual; public Individual getCurrentBesIndividual() return currentBesIndividual; public void setCurrentBesIndividual(Individual currentBesIndividual) this.currentBesIndividual = currentBesIndividual; / 抽象方法 public abstract Population evaluate(CodeScale scale, Population p);/ 评估种群 public abstract Population calTotalFitness(CodeScale scale, Population p);/ 计算总适应度 public abstract Population calAverageFitness(CodeScale scale, Population p);/ 计算平均适应度 public abstract Population calRelativeFitness(CodeScale scale, Population p);/ 计算相对适应度 public abstract Population findBestAndWorstIndividual(CodeScale scale, Population p);/ 寻找当前种群中的最优个体和最差个体,寻找目前的最优个体 public abstract Population randomlyInitPopulation(CodeScale scale);/ 随机初始化种群 Override public Object clone() throws CloneNotSupportedException Population g = null; try g = (Population) super.clone(); g.pop = pop.clone(); catch (CloneNotSupportedException e) System.out.println(e.getMessage(); return g; public String toString() String str = ; for (int i = 0; i pop.length; i+) str += popi.toString(); return str; public class RosenbrockPopulation extends Population implements Cloneable Override public Population evaluate(CodeScale scale, Population p) / 计算总适应度 Population pop = new RosenbrockPopulation(); pop = calTotalFitness(scale, p); / 计算平均适应度 pop = calAverageFitness(scale, p); / 计算相对适应度 pop = calRelativeFitness(scale, p); / 寻找最优个体、最差、当前代最优个体 pop = findBestAndWorstIndividual(scale, p); return pop; Override public Population calTotalFitness(CodeScale scale, Population p) double totalFitness = 0.0; for (int i = 0; i scale.populationSize; i+) totalFitness = totalFitness + p.getPop()i.getFitness(); Population pop = new RosenbrockPopulation(); pop = p; pop.setTotalFitness(totalFitness); return pop; Override public Population calAverageFitness(CodeScale scale, Population p) double averageFitness = p.totalFitness / scale.populationSize; Population pop = new RosenbrockPopulation(); pop = p; pop.setAverageFitness(averageFitness); return pop; Override public Population calRelativeFitness(CodeScale scale, Population p) Individual individual = new Individualscale.populationS