Posted on 2007-04-26 21:41
Zou Ang 阅读(7033)
评论(14) 编辑 收藏 所属分类:
最近学习遗传算法,写了这么一个小程序来计算函数 f(x,y,z) = xyz*sin(xyz)的最大值,这段程序经过小小改变就可以适应其他的函数最大值求解问题
首先介绍一下遗传算法,遗传算法就是模拟自然界中物竞天择,适者生存的法则,通过对解空间进行进化从而求得最优方案的方法,遗传算法的好处在于,即使算法中的某些参数不起作用了,整个算法还是可以正常地工作,也就是说,整体种群的走向是越来越好的
遗传算法的关键内容包括:
1. 染色体
首先对优化问题的解进行编码,编码后的一个解被称为一个染色体,组成染色体的元素称为基因。比如对于上面那个函数,我们就可以用24位的2进制串进行编码,首先8位2进制数代表x,中间为y,最后为z,x,y,z都属于[0,255]
2. 交配
将两个染色体进行交叉的操作被称为交配,交配可能提高染色体的适应值,也可能降低其适应值。通常交配是以一定的概率发生的。在程序中,我们通过随机交换两个染色体的一些位来体现。
3. 适应函数
我们需要使用一个函数来表现解的优异程度,这个函数只要可以反映出解的优劣即可,没必要很精确。适应函数就类似我们生存的环境,环境评估我们的生存能力,评估值高的更容易存活。
4. 变异
有时候种群中的某些个体会发生变异的现象,变异一般是以很小的概率发生的,但是变异增加了种群进化的不确定性,也让种群中的个体类型更加丰富。在程序中,我们用随机变化某一位来体现。
算法的流程为:
1.初始化种群
2.进行第一轮评估
3.交配
4.变异
5.评估
6.重新选择种群
7.若未达到结束条件,转3
随机数生成器:
package edu.zsu.zouang.util;

import java.util.Random;


public class Randomizer
{
private int lower;
private int upper;
private static Random random = new Random();

public Randomizer(int lower, int upper)
{

if(upper <= lower)
{
throw new IllegalStateException("Upper is smaller than lower!");
}
this.lower = lower;
this.upper = upper;
}

public Double nextDouble()
{
return Double.valueOf(lower + (upper - lower) * random.nextDouble());
}

public Integer nextInteger()
{
return Integer.valueOf(lower +random.nextInt(upper - lower));
}

public char[] nextBitArray(int length)
{

if(length <= 0)
{
throw new IllegalStateException("Length is less than ZERO!");
}
char[] temp = new char[length];

for(int i = 0; i < length ; i++)
{
temp[i] = random.nextBoolean() ? '1' : '0';
}
return temp;
}
}

染色体:
package edu.zsu.zouang.inheritence;

import java.util.Arrays;

import edu.zsu.zouang.util.Randomizer;


public class Chromosome implements Cloneable
{
private double fitness = -1; //代表未计算适应函数
private double select = -1; // 选择概率
private char[] chromo; //染色体串
private Randomizer random;
private int lower;
private int upper;

public Chromosome(int lower, int upper, int length)
{
this.lower = lower;
this.upper = upper;
random = new Randomizer(lower, upper);
chromo = random.nextBitArray(length);
}


/** *//**
* 克隆一个染色体
*/

public Chromosome clone()
{
Chromosome c = new Chromosome(lower,upper,chromo.length);
char[] temp = new char[c.chromo.length];
System.arraycopy(chromo, 0, temp, 0, chromo.length);
c.setChromo(temp);
return c;
}

public char[] getChromo()
{
return chromo;
}


public void setChromo(char[] chromo)
{
this.chromo = chromo;
}


public double getFitness()
{
return fitness;
}


public void setFitness(double fitness)
{
this.fitness = fitness;
}


public double getSelect()
{
return select;
}


public void setSelect(double select)
{
this.select = select;
}
}

适应函数接口:
package edu.zsu.zouang.inheritence;


public interface FitnessCalculate
{
public double calculate(char[] chromosome);
}

本函数的适应函数,既然是求最大值,干脆用求解的函数来做适应函数
package edu.zsu.zouang.inheritence;


/** *//**
* 计算xyz*sin(xyz)最大值的遗传函数适应值
* 2007-4-25
* @author Zou Ang
* Contact <a href ="mailto:richardeee@gmail.com">Zou Ang</a>
*/

public class FunctionFitness implements FitnessCalculate
{


public double calculate(char[] chromosome)
{

/**//*
* x、y、z都用8位来编码,即x,y,z都属于[0,255]
*/
double x = 0;
double y = 0;
double z = 0;

for(int i = 0; i < 8; i++)
{
int j = i + 8;
int k = i + 16;
x = x + Math.pow(2, 7 - i) * (Integer.valueOf(chromosome[i]) - 48);
y = y + Math.pow(2, 7 - i) * (Integer.valueOf(chromosome[j]) - 48);
z = z + Math.pow(2, 7 - i) * (Integer.valueOf(chromosome[k]) - 48);
}
return x * y * z * Math.sin(x*y*z);
}

}
种群详细信息类:
package edu.zsu.zouang.inheritence;


public class GenerationDetail
{
private double averageFitness = 0.0;
private double maxFitness = 0.0;
private double minFitness = 0.0;


public double getAverageFitness()
{
return averageFitness;
}


public void setAverageFitness(double averageFitness)
{
this.averageFitness = averageFitness;
}


public double getMaxFitness()
{
return maxFitness;
}


public void setMaxFitness(double maxFitness)
{
this.maxFitness = maxFitness;
}


public double getMinFitness()
{
return minFitness;
}


public void setMinFitness(double minFitness)
{
this.minFitness = minFitness;
}
}

最后是主类:
package edu.zsu.zouang.inheritence;

import java.util.ArrayList;
import java.util.List;

import edu.zsu.zouang.util.Randomizer;


public class GeneticAlgorithm
{
private int generation; //进化代数
private int population; //种群数量
private double crossoverPossibility; //繁殖概率
private double mutationPossibility; //变异概率
private FitnessCalculate calculator = new FunctionFitness(); //适应函数计算
private List<Chromosome> clist = new ArrayList<Chromosome>();
private Randomizer random1; //随机数生成器1,用于生成变异位和交配位
private Randomizer random2 = new Randomizer(0,1); //随机数生成器2,用于生成0-1之间的概率
private GenerationDetail detail = new GenerationDetail();

public GeneticAlgorithm(int population, double sp, double cp, double mp,int length)
{
this.population = population;
this.crossoverPossibility = cp;
this.mutationPossibility = mp;
random1 = new Randomizer(0,length - 1);
generatePopulation(0,255,length); //用24位表示一组x,y,z的值
}

/** *//**
* 生成初始种群
* @param lower
* @param upper
* @param length
*/

private void generatePopulation(int lower, int upper, int length)
{
//随机生成染色体

for(int i = 0; i < population; i ++)
{
clist.add(new Chromosome(lower,upper,length));
}
//计算染色体的适应值
evaluate();
}

/** *//**
* 计算群体的适应值
*/

private void evaluate()
{
double sum = 0.0;
double min = Double.MAX_VALUE;
double max = Double.MIN_VALUE;

for(Chromosome c : clist)
{
double fitness = calculator.calculate(c.getChromo());

if(fitness > max)
{
max = fitness;
}

if(fitness < min)
{
min = fitness;
}
c.setFitness(fitness);
sum += fitness;
}
detail.setMaxFitness(max);
detail.setMinFitness(min);
detail.setAverageFitness(sum/population);

for(Chromosome c : clist)
{
c.setSelect((c.getFitness())/sum); //设置选择概率
}
}

/** *//**
* 在后代中选择新种群
*/

private void selectPopulation()
{
List<Chromosome> tempList = new ArrayList<Chromosome>();

for(Chromosome c : clist)
{
long expectation = Math.round(c.getSelect() * population);

for(int i = 0; i < expectation; i ++)
{
tempList.add(c.clone());
}
}
//如果选择种群数量大于种群规定数量,则淘汰适应值最小的染色体

while(tempList.size() > population)
{
int location = 0;
double min = tempList.get(0).getFitness();

for(int i = 0 ; i < tempList.size(); i ++)
{

if(tempList.get(i).getFitness() < min)
{
location = i;
}
}
tempList.remove(location);
}
//如果选择种群数量小于种群规定数量,则加入适应值最大的染色体

while(tempList.size() < population)
{
int location = 0;
double max = tempList.get(0).getFitness();

for(int i = 0; i < tempList.size(); i++)
{

if(tempList.get(i).getFitness() > max)
{
location = i;
}
}
tempList.add(tempList.get(location).clone());
}
clist = tempList;
}

/** *//**
* 交配两个染色体
* @param c1
* @param c2
* @param location
*/

private void crossover(Chromosome c1, Chromosome c2)
{

if(c1.getChromo().length != c2.getChromo().length)
{
throw new IllegalStateException("染色体长度不同!");
}
//交换染色体上的基因
//随机确定交配位
int location = random1.nextInteger();

for(int i = location ; i < c1.getChromo().length; i ++)
{
char temp;
temp = c1.getChromo()[i];
c1.getChromo()[i] = c2.getChromo()[i];
c2.getChromo()[i] = temp;
}
}

/** *//**
* 交配整个种群,完成一次进化
*
*/

public void crossoverPopulation()
{

for(int j = 0; j < population; j ++)
{

for(int i = 0; i < population - 1; i++)
{
double temp = random2.nextDouble();

if(temp < crossoverPossibility)
{//在交配概率之内
crossover(clist.get(i), clist.get(i + 1));
}
}
double mutation = random2.nextDouble();

if(mutation < mutationPossibility)
{//在变异概率之内
mutation(clist.get(j));
}
}
//重新计算群体适应值
evaluate();
//重新选择种群
selectPopulation();
generation ++;
}
//随机变异一位

private void mutation(Chromosome ch)
{
int location = random1.nextInteger();
char c = ch.getChromo()[location];

if(c == '1')
{
ch.getChromo()[location] = '0';

}else
{
ch.getChromo()[location] = '1';
}
}

public void printDetail()
{
System.out.println("/*****************************************");
System.out.println("* -----遗传算法报告----- ");
System.out.println("* 当前是第" + generation + "代");
System.out.println("* 当前种群平均适应值为: " + detail.getAverageFitness());
System.out.println("* 其中最大适应值为:" + detail.getMaxFitness());
System.out.println("* 其中最小适应值为:" + detail.getMinFitness());
System.out.println("*******************************************/");
}

public static void main(String[] args)
{
//种群数量:30
//选择概率:0.0
//交配概率:0.9
//变异概率: 0.01
GeneticAlgorithm ga = new GeneticAlgorithm(30,0.0,0.9,0.01,24);

for(int i = 0; i < 5; i ++)
{
ga.crossoverPopulation();
}
ga.printDetail();

for(int j = 0; j < 25; j++)
{
ga.crossoverPopulation();
}
ga.printDetail();

for(int k = 0; k < 1000; k++)
{
ga.crossoverPopulation();
}
ga.printDetail();
}
}

输出的结果是

/** *//*****************************************
* -----遗传算法报告-----
* 当前是第5代
* 当前种群平均适应值为: 7592451.0488077225
* 其中最大适应值为:9031331.437029611
* 对应最大适应值的染色体为:111011101101010010111000
* 其中最小适应值为:-1.2521097155031694E7
* 其中对应最小适应值的染色体为111011101101010011111011
*******************************************/

/** *//*****************************************
* -----遗传算法报告-----
* 当前是第30代
* 当前种群平均适应值为: 8785113.746617064
* 其中最大适应值为:9836674.727850026
* 对应最大适应值的染色体为:111111101101010010111000
* 其中最小适应值为:-1.1676031572464054E7
* 其中对应最小适应值的染色体为111011101101010011111000
*******************************************/

/** *//*****************************************
* -----遗传算法报告-----
* 当前是第1030代
* 当前种群平均适应值为: 8763072.724911185
* 其中最大适应值为:9836674.727850026
* 对应最大适应值的染色体为:111111101101010010111000
* 其中最小适应值为:-9580464.117842415
* 其中对应最小适应值的染色体为111101101101010010111000
*******************************************/

示例程序见:
http://www.blogjava.net/richardeee/archive/2007/04/29/114536.html