posts - 32, comments - 153, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

使用遗传算法求解函数 xyz*sin(xyz)的最大值

Posted on 2007-04-26 21:41 Zou Ang 阅读(7022) 评论(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(27 - i) * (Integer.valueOf(chromosome[i]) - 48);
            y 
= y + Math.pow(27 - i) * (Integer.valueOf(chromosome[j]) - 48);
            z 
= z + Math.pow(27 - 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

评论

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2007-04-27 09:50 by 王凌华
第一次听说。请问LZ这东西能用到吗,在我们实际的开发中? 谢谢. :)

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2007-04-27 12:11 by Zou Ang
@王凌华
在实际的开发中,是可以用到的。但是要看具体的情况。比如波音飞机螺旋桨的扇片设计就用到了遗传算法,还有比如求路径最短问题,在非常大的图中寻找最短路径,遗传算法就是非常好的选择了。对于复杂的优化问题,遗传算法都是比较好的选择

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2007-04-28 08:26 by brucelee521
好文章。

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2007-04-28 09:04 by my name
不懂啊 有空看看

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2007-04-28 11:45 by hooooo
没看明白,也没仔细看

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2007-04-28 15:15 by lancey
感觉还不错,有机会看看

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2007-07-27 22:30 by 车萨莉
好专业的页面。。好恐怖。。

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2008-09-15 17:45 by m.dreamfly
double min = Double.MAX_VALUE;
double max = Double.MIN_VALUE;
??

it's right?

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2008-12-26 20:38 by lavender314
要怎么样改改就能编程求 f(x)=x*x x属于[0,31]的最大值呢
改好了麻烦你发到我邮箱吧 lavender314@126.com 谢谢

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值[未登录]  回复  更多评论   

2009-05-13 10:27 by yuan
LZ好啊,能发我一下遗传算法实现的Java代码吗?我正在写用遗传算法解决库存管理方面的论文,万分感谢!!!yuankunbo@sina.com

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2009-12-25 10:15 by huhu
麻烦问下楼主二进制编码串的长度如何确定??谢谢

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值[未登录]  回复  更多评论   

2010-07-08 16:55 by sunny
楼主好文章!我有一点疑问,就是我们在使用遗传算法的时候大都直接随机生成解,如果想要自己生成一个存在规定个数规定解的解空间,应该怎么实现呢?
yangguang760@gmail.com
望不吝赐教

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值  回复  更多评论   

2010-12-14 20:17 by chuanwang66
楼主您好!我每次运行这个程序时都有不同的结果,怎么才能得到一个比较收敛的结果呢?

# re: 使用遗传算法求解函数 xyz*sin(xyz)的最大值[未登录]  回复  更多评论   

2013-05-11 16:35 by fanfan
请问你改好的那个实现了么,同求@lavender314

只有注册用户登录后才能发表评论。


网站导航: