程序设计及其应用Java实训指导书.doc

程序设计及应用实训指引书
（Java语言）

昆明理工大学信息工程与自动化学院自动化系
张志坤 李勇编
8月

一、题目
题目：运用遗传算法仿真猕猴桃组培苗变异
二、目
（1）掌握Java语言开发环境搭建，掌握Java基本编程知识。
（2）学习遗传算法基本原理，运用遗传算法进行猕猴桃遗传变异模仿。
（3）运用excel进行遗传变异数据分析，掌握数据分析办法
三、指引教师
张志坤、李勇
四、地点
昆明理工大学呈贡校区信自楼445。
五、时间及进度安排
时间：—短学期（8月31日至9月9日）
进度安排：
日 期
环节进程安排摘要
-8-31
布置设计任务及环境搭建
-9-1
程序构造设计
-9-2
程序编写指引
-9-5
查阅资料
-9-6
查阅资料
-9-7
程序编写、分析数据
-9-8
报告书编写及指引
-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.001－0.1。
4、终结条件
当最优个体适应度达到给定阈值，或者最优个体适应度和群体适应度不再上升时，或者迭代次数达到预设代数时，算法终结。预设代数普通设立为100-500代。
（二）、Java开发环境搭建
1、JDK获取
从Oracle公司网站上可以免费获取各种版本JDK，Oracle公司网址.com。注意这次设计实用是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 += chrom[i].toString();
}
str+="\n";
for (int i = 0；i < chrom.length；i++) {
str += chrom[i].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 Chromsome[2];
chrom[0] = new Chromsome();
chrom[1] = new Chromsome();
PhenoType phenoType1=new PhenoType();
phenoType1.setX(x1);
PhenoType phenoType2=new PhenoType();
phenoType2.setX(x2);

chrom[0].phoneType=phenoType1;
chrom[1].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 Gene[scale.geneTypeLength];
Gene[] g2 = new Gene[scale.geneTypeLength];
for(int i=0;i<scale.geneTypeLength;i++){
Gene gene1 =new Gene();
gene1.setAllele(code[i]);
g1[i]=gene1;
Gene gene2 =new Gene();
gene2.setAllele(code[i+scale.geneTypeLength]);
g2[i]=gene2;
}
geneType1.setGene(g1);
geneType2.setGene(g2);
Chromsome chrom1 = new Chromsome();
chrom1.setGeneType(geneType1);
Chromsome chrom2 = new Chromsome();
chrom2.setGeneType(geneType2);
Chromsome[] chrom= new Chromsome[2];
chrom[0]=chrom1;
chrom[1]=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.chrom[0].getPhoneType().getX();
double x2 = indiv.chrom[1].getPhoneType().getX();
Chromsome[] chrom = new Chromsome[2];
chrom[0] = indiv.chrom[0];
GeneType geneType1 = new GeneType();
Gene[] g1 = new Gene[scale.geneTypeLength];
for (int i = 0；i < scale.geneTypeLength；i++) {
Gene gene = new Gene();
gene.setAllele(byLengthSpilt(scale,codingVariable(scale,x1))[i]);
g1[i] = gene;
}
geneType1.setGene(g1);
chrom[0].setGeneType(geneType1);

chrom[1] = indiv.chrom[1];
GeneType geneType2 = new GeneType();
Gene[] g2 = new Gene[scale.geneTypeLength];
for (int i = 0；i < scale.geneTypeLength；i++) {
Gene gene = new Gene();
gene.setAllele(byLengthSpilt(scale,codingVariable(scale,x2))[i]);
g2[i] = gene;
}
geneType2.setGene(g2);
chrom[1].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 String[j];
for (int i = 0；i < j；i++) {
subStr[i] = 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.chrom[0].getGeneType();
GeneType geneType2 = indiv.chrom[1].getGeneType();
for(int i=0;i<geneType1.getGene().length;i++){
code1 = code1+geneType1.getGene()[i].getAllele();
}
for(int i=0;i<geneType2.getGene().length;i++){
code2 = code2+geneType2.getGene()[i].getAllele();
}
double x1 = decodeHandle(scale,code1);
Chromsome[] chrom = new Chromsome[2];
chrom[0] = indiv.chrom[0];
chrom[0].setPhoneType(new PhenoType(x1));
double x2 = decodeHandle(scale,code2);
chrom[1] = indiv.chrom[1];
chrom[1].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.chrom[0].getPhoneType().getX(),
indiv.chrom[1].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;// 当