深入理解Java遺傳算法

更新時(shí)間：2016年02月01日 17:14:48 作者：xiaojimanman

這篇文章主要為大家詳細(xì)介紹了Java遺傳算法，本文對基因的編碼采用二進(jìn)制規(guī)則，分享了對Java遺傳算法的理解，感興趣的小伙伴們可以參考一下

關(guān)于遺傳算法的詳細(xì)原理以及具體的定義這里就不多介紹，想了解的可以自行百度，下面就簡單介紹下自己對遺傳算法的理解，本文對基因的編碼采用二進(jìn)制規(guī)則。

算法思想：
遺傳算法參照達(dá)爾文的進(jìn)化論，認(rèn)為物種都是向好的方向去發(fā)展（適者生存），因此可以認(rèn)為到足夠的代數(shù)之后，得到的最值可實(shí)際的最值很接近。

算法步驟：

1）隨機(jī)產(chǎn)生一個(gè)種群；
2）計(jì)算種群的適應(yīng)度、最好適應(yīng)度、最差適應(yīng)度、平均適應(yīng)度等指標(biāo)；
3）驗(yàn)證種群代數(shù)是否達(dá)到自己設(shè)置的閾值，如果達(dá)到結(jié)束計(jì)算，否則繼續(xù)下一步計(jì)算；
4）采用轉(zhuǎn)盤賭法選擇可以產(chǎn)生下一代的父代，產(chǎn)生下一代種群（種群中個(gè)體數(shù)量不變）；
5）種群發(fā)生基因突變；
6）重復(fù)2、3、4、5步。

算法實(shí)現(xiàn)-基因部分
1、種群個(gè)體（這里認(rèn)為是染色體），在個(gè)體中，我們?yōu)檫@個(gè)個(gè)體添加兩個(gè)屬性，個(gè)體的基因和基因?qū)?yīng)的適應(yīng)度（函數(shù)值）。

public class Chromosome { 
  private boolean[] gene;//基因序列 
  private double score;//對應(yīng)的函數(shù)得分 
}

2、隨機(jī)生成基因序列，基因的每一個(gè)位置是0還是1，這里采用完全隨機(jī)的方式實(shí)現(xiàn)。

public Chromosome(int size) { 
  if (size <= 0) { 
    return; 
  } 
  initGeneSize(size); 
  for (int i = 0; i < size; i++) { 
    gene[i] = Math.random() >= 0.5; 
  } 
} 
 
private void initGeneSize(int size) { 
  if (size <= 0) { 
    return; 
  } 
  gene = new boolean[size]; 
}

3、把基因轉(zhuǎn)化為對應(yīng)的值，比如101對應(yīng)的數(shù)字是5，這里采用位運(yùn)算來實(shí)現(xiàn)。

public int getNum() { 
  if (gene == null) { 
    return 0; 
  } 
  int num = 0; 
  for (boolean bool : gene) { 
    num <<= 1; 
    if (bool) { 
      num += 1; 
    } 
  } 
  return num; 
}

4、基因發(fā)生變異，對于變異的位置這里完全采取隨機(jī)的方式實(shí)現(xiàn)，變異原則是由1變?yōu)?，0變?yōu)?。

public void mutation(int num) { 
  //允許變異 
  int size = gene.length; 
  for (int i = 0; i < num; i++) { 
    //尋找變異位置 
    int at = ((int) (Math.random() * size)) % size; 
    //變異后的值 
    boolean bool = !gene[at]; 
    gene[at] = bool; 
  } 
}

5、克隆基因，用于產(chǎn)生下一代，這一步就是將已存在的基因copy一份。

public static Chromosome clone(final Chromosome c) { 
  if (c == null || c.gene == null) { 
    return null; 
  } 
  Chromosome copy = new Chromosome(); 
  copy.initGeneSize(c.gene.length); 
  for (int i = 0; i < c.gene.length; i++) { 
    copy.gene[i] = c.gene[i]; 
  } 
  return copy; 
}

6、父母雙方產(chǎn)生下一代，這里兩個(gè)個(gè)體產(chǎn)生兩個(gè)個(gè)體子代，具體哪段基因差生交叉，完全隨機(jī)。

public static List<Chromosome> genetic(Chromosome p1, Chromosome p2) { 
  if (p1 == null || p2 == null) { //染色體有一個(gè)為空，不產(chǎn)生下一代 
    return null; 
  } 
  if (p1.gene == null || p2.gene == null) { //染色體有一個(gè)沒有基因序列，不產(chǎn)生下一代 
    return null; 
  } 
  if (p1.gene.length != p2.gene.length) { //染色體基因序列長度不同，不產(chǎn)生下一代 
    return null; 
  } 
  Chromosome c1 = clone(p1); 
  Chromosome c2 = clone(p2); 
  //隨機(jī)產(chǎn)生交叉互換位置 
  int size = c1.gene.length; 
  int a = ((int) (Math.random() * size)) % size; 
  int b = ((int) (Math.random() * size)) % size; 
  int min = a > b ? b : a; 
  int max = a > b ? a : b; 
  //對位置上的基因進(jìn)行交叉互換 
  for (int i = min; i <= max; i++) { 
    boolean t = c1.gene[i]; 
    c1.gene[i] = c2.gene[i]; 
    c2.gene[i] = t; 
  } 
  List<Chromosome> list = new ArrayList<Chromosome>(); 
  list.add(c1); 
  list.add(c2); 
  return list; 
}

算法實(shí)現(xiàn)-遺傳算法
1、對于遺傳算法，我們需要有對應(yīng)的種群以及我們需要設(shè)置的一些常量：種群數(shù)量、基因長度、基因突變個(gè)數(shù)、基因突變率等，具體參照如下代碼：

public abstract class GeneticAlgorithm { 
  private List<Chromosome> population = new ArrayList<Chromosome>();//種群 
  private int popSize = 100;//種群數(shù)量 
  private int geneSize;//基因最大長度 
  private int maxIterNum = 500;//最大迭代次數(shù) 
  private double mutationRate = 0.01;//基因變異的概率 
  private int maxMutationNum = 3;//最大變異步長 
   
  private int generation = 1;//當(dāng)前遺傳到第幾代 
   
  private double bestScore;//最好得分 
  private double worstScore;//最壞得分 
  private double totalScore;//總得分 
  private double averageScore;//平均得分 
   
  private double x; //記錄歷史種群中最好的X值 
  private double y; //記錄歷史種群中最好的Y值 
  private int geneI;//x y所在代數(shù) 
}

2、初始化種群，在遺傳算法開始時(shí)，我們需要初始化一個(gè)原始種群，這就是原始的第一代。

private void init() { 
  for (int i = 0; i < popSize; i++) { 
    population = new ArrayList<Chromosome>(); 
    Chromosome chro = new Chromosome(geneSize); 
    population.add(chro); 
  } 
  caculteScore(); 
}

3、在初始種群存在后，我們需要計(jì)算種群的適應(yīng)度以及最好適應(yīng)度、最壞適應(yīng)度和平均適應(yīng)度等。

private void caculteScore() { 
  setChromosomeScore(population.get(0)); 
  bestScore = population.get(0).getScore(); 
  worstScore = population.get(0).getScore(); 
  totalScore = 0; 
  for (Chromosome chro : population) { 
    setChromosomeScore(chro); 
    if (chro.getScore() > bestScore) { //設(shè)置最好基因值 
      bestScore = chro.getScore(); 
      if (y < bestScore) { 
        x = changeX(chro); 
        y = bestScore; 
        geneI = generation; 
      } 
    } 
    if (chro.getScore() < worstScore) { //設(shè)置最壞基因值 
      worstScore = chro.getScore(); 
    } 
    totalScore += chro.getScore(); 
  } 
  averageScore = totalScore / popSize; 
  //因?yàn)榫葐栴}導(dǎo)致的平均值大于最好值，將平均值設(shè)置成最好值 
  averageScore = averageScore > bestScore ? bestScore : averageScore; 
}

4、在計(jì)算個(gè)體適應(yīng)度的時(shí)候，我們需要根據(jù)基因計(jì)算對應(yīng)的Y值，這里我們設(shè)置兩個(gè)抽象方法，具體實(shí)現(xiàn)由類的實(shí)現(xiàn)去實(shí)現(xiàn)。

private void setChromosomeScore(Chromosome chro) { 
  if (chro == null) { 
    return; 
  } 
  double x = changeX(chro); 
  double y = caculateY(x); 
  chro.setScore(y); 
 
} 
 
/** 
 * @param chro 
 * @return 
 * @Description: 將二進(jìn)制轉(zhuǎn)化為對應(yīng)的X 
 */ 
public abstract double changeX(Chromosome chro); 
 
 
/** 
 * @param x 
 * @return 
 * @Description: 根據(jù)X計(jì)算Y值 Y=F(X) 
 */ 
public abstract double caculateY(double x);

5、在計(jì)算完種群適應(yīng)度之后，我們需要使用轉(zhuǎn)盤賭法選取可以產(chǎn)生下一代的個(gè)體，這里有個(gè)條件就是只有個(gè)人的適應(yīng)度不小于平均適應(yīng)度才會(huì)長生下一代（適者生存）。

private Chromosome getParentChromosome (){ 
  double slice = Math.random() * totalScore; 
  double sum = 0; 
  for (Chromosome chro : population) { 
    sum += chro.getScore(); 
    //轉(zhuǎn)到對應(yīng)的位置并且適應(yīng)度不小于平均適應(yīng)度 
    if (sum > slice && chro.getScore() >= averageScore) { 
      return chro; 
    } 
  } 
  return null; 
}

6、選擇可以產(chǎn)生下一代的個(gè)體之后，就要交配產(chǎn)生下一代。

private void evolve() { 
  List<Chromosome> childPopulation = new ArrayList<Chromosome>(); 
  //生成下一代種群 
  while (childPopulation.size() < popSize) { 
    Chromosome p1 = getParentChromosome(); 
    Chromosome p2 = getParentChromosome(); 
    List<Chromosome> children = Chromosome.genetic(p1, p2); 
    if (children != null) { 
      for (Chromosome chro : children) { 
        childPopulation.add(chro); 
      } 
    }  
  } 
  //新種群替換舊種群 
  List<Chromosome> t = population; 
  population = childPopulation; 
  t.clear(); 
  t = null; 
  //基因突變 
  mutation(); 
  //計(jì)算新種群的適應(yīng)度 
  caculteScore(); 
}

7、在產(chǎn)生下一代的過程中，可能會(huì)發(fā)生基因變異。

private void mutation() { 
  for (Chromosome chro : population) { 
    if (Math.random() < mutationRate) { //發(fā)生基因突變 
      int mutationNum = (int) (Math.random() * maxMutationNum); 
      chro.mutation(mutationNum); 
    } 
  } 
}

8、將上述步驟一代一代的重復(fù)執(zhí)行。

public void caculte() { 
  //初始化種群 
  generation = 1; 
  init(); 
  while (generation < maxIterNum) { 
    //種群遺傳 
    evolve(); 
    print(); 
    generation++; 
  } 
}

編寫實(shí)現(xiàn)類

由于上述遺傳算法的類是一個(gè)抽象類，因此我們需要針對特定的事例編寫實(shí)現(xiàn)類，假設(shè)我們計(jì)算 Y=100-log(X)在[6,106]上的最值。

1、我們假設(shè)基因的長度為24（基因的長度由要求結(jié)果的有效長度確定），因此對應(yīng)的二進(jìn)制最大值為 1<< 24，我們做如下設(shè)置

public class GeneticAlgorithmTest extends GeneticAlgorithm{ 
   
  public static final int NUM = 1 << 24; 
 
  public GeneticAlgorithmTest() { 
    super(24);  
  } 
}

2、對X值的抽象方法進(jìn)行實(shí)現(xiàn)

@Override 
public double changeX(Chromosome chro) { 
  // TODO Auto-generated method stub  
  return ((1.0 * chro.getNum() / NUM) * 100) + 6; 
}

3、對Y的抽象方法進(jìn)行實(shí)現(xiàn)

@Override 
public double caculateY(double x) { 
  // TODO Auto-generated method stub  
  return 100 - Math.log(x); 
}

運(yùn)行結(jié)果

遺傳算法思考
自己看了很多遺傳算法的介紹，上面提到的最優(yōu)解都是最后一代的最值，自己就有一個(gè)疑問了，為什么我知道前面所有帶中的最值，也就是程序中的X Y值，為什么不能用X Y值做遺傳算法最后的結(jié)果值呢？

完整代碼

1、Chromosome類

 /**  
 *@Description: 基因遺傳染色體  
 */  
package com.lulei.genetic.algorithm;  
 
import java.util.ArrayList; 
import java.util.List; 
 
public class Chromosome { 
  private boolean[] gene;//基因序列 
  private double score;//對應(yīng)的函數(shù)得分 
   
  public double getScore() { 
    return score; 
  } 
 
  public void setScore(double score) { 
    this.score = score; 
  } 
 
  /** 
   * @param size 
   * 隨機(jī)生成基因序列 
   */ 
  public Chromosome(int size) { 
    if (size <= 0) { 
      return; 
    } 
    initGeneSize(size); 
    for (int i = 0; i < size; i++) { 
      gene[i] = Math.random() >= 0.5; 
    } 
  } 
   
  /** 
   * 生成一個(gè)新基因 
   */ 
  public Chromosome() { 
     
  } 
   
  /** 
   * @param c 
   * @return  
   * @Description: 克隆基因 
   */ 
  public static Chromosome clone(final Chromosome c) { 
    if (c == null || c.gene == null) { 
      return null; 
    } 
    Chromosome copy = new Chromosome(); 
    copy.initGeneSize(c.gene.length); 
    for (int i = 0; i < c.gene.length; i++) { 
      copy.gene[i] = c.gene[i]; 
    } 
    return copy; 
  } 
   
  /** 
   * @param size  
   * @Description: 初始化基因長度 
   */ 
  private void initGeneSize(int size) { 
    if (size <= 0) { 
      return; 
    } 
    gene = new boolean[size]; 
  } 
   
   
  /** 
   * @param c1 
   * @param c2  
   * @Description: 遺傳產(chǎn)生下一代 
   */ 
  public static List<Chromosome> genetic(Chromosome p1, Chromosome p2) { 
    if (p1 == null || p2 == null) { //染色體有一個(gè)為空，不產(chǎn)生下一代 
      return null; 
    } 
    if (p1.gene == null || p2.gene == null) { //染色體有一個(gè)沒有基因序列，不產(chǎn)生下一代 
      return null; 
    } 
    if (p1.gene.length != p2.gene.length) { //染色體基因序列長度不同，不產(chǎn)生下一代 
      return null; 
    } 
    Chromosome c1 = clone(p1); 
    Chromosome c2 = clone(p2); 
    //隨機(jī)產(chǎn)生交叉互換位置 
    int size = c1.gene.length; 
    int a = ((int) (Math.random() * size)) % size; 
    int b = ((int) (Math.random() * size)) % size; 
    int min = a > b ? b : a; 
    int max = a > b ? a : b; 
    //對位置上的基因進(jìn)行交叉互換 
    for (int i = min; i <= max; i++) { 
      boolean t = c1.gene[i]; 
      c1.gene[i] = c2.gene[i]; 
      c2.gene[i] = t; 
    } 
    List<Chromosome> list = new ArrayList<Chromosome>(); 
    list.add(c1); 
    list.add(c2); 
    return list; 
  } 
   
  /** 
   * @param num  
   * @Description: 基因num個(gè)位置發(fā)生變異 
   */ 
  public void mutation(int num) { 
    //允許變異 
    int size = gene.length; 
    for (int i = 0; i < num; i++) { 
      //尋找變異位置 
      int at = ((int) (Math.random() * size)) % size; 
      //變異后的值 
      boolean bool = !gene[at]; 
      gene[at] = bool; 
    } 
  } 
   
  /** 
   * @return  
   * @Description: 將基因轉(zhuǎn)化為對應(yīng)的數(shù)字 
   */ 
  public int getNum() { 
    if (gene == null) { 
      return 0; 
    } 
    int num = 0; 
    for (boolean bool : gene) { 
      num <<= 1; 
      if (bool) { 
        num += 1; 
      } 
    } 
    return num; 
  } 
}

2、GeneticAlgorithm類

 /**  
 *@Description:   
 */  
package com.lulei.genetic.algorithm;  
 
import java.util.ArrayList; 
import java.util.List; 
 
  
public abstract class GeneticAlgorithm { 
  private List<Chromosome> population = new ArrayList<Chromosome>(); 
  private int popSize = 100;//種群數(shù)量 
  private int geneSize;//基因最大長度 
  private int maxIterNum = 500;//最大迭代次數(shù) 
  private double mutationRate = 0.01;//基因變異的概率 
  private int maxMutationNum = 3;//最大變異步長 
   
  private int generation = 1;//當(dāng)前遺傳到第幾代 
   
  private double bestScore;//最好得分 
  private double worstScore;//最壞得分 
  private double totalScore;//總得分 
  private double averageScore;//平均得分 
   
  private double x; //記錄歷史種群中最好的X值 
  private double y; //記錄歷史種群中最好的Y值 
  private int geneI;//x y所在代數(shù) 
   
  public GeneticAlgorithm(int geneSize) { 
    this.geneSize = geneSize; 
  } 
   
  public void caculte() { 
    //初始化種群 
    generation = 1; 
    init(); 
    while (generation < maxIterNum) { 
      //種群遺傳 
      evolve(); 
      print(); 
      generation++; 
    } 
  } 
   
  /** 
   * @Description: 輸出結(jié)果 
   */ 
  private void print() { 
    System.out.println("--------------------------------"); 
    System.out.println("the generation is:" + generation); 
    System.out.println("the best y is:" + bestScore); 
    System.out.println("the worst fitness is:" + worstScore); 
    System.out.println("the average fitness is:" + averageScore); 
    System.out.println("the total fitness is:" + totalScore); 
    System.out.println("geneI:" + geneI + "\tx:" + x + "\ty:" + y); 
  } 
   
   
  /**  
   * @Description: 初始化種群 
   */ 
  private void init() { 
    for (int i = 0; i < popSize; i++) { 
      population = new ArrayList<Chromosome>(); 
      Chromosome chro = new Chromosome(geneSize); 
      population.add(chro); 
    } 
    caculteScore(); 
  } 
   
  /** 
   * @Author:lulei  
   * @Description:種群進(jìn)行遺傳 
   */ 
  private void evolve() { 
    List<Chromosome> childPopulation = new ArrayList<Chromosome>(); 
    //生成下一代種群 
    while (childPopulation.size() < popSize) { 
      Chromosome p1 = getParentChromosome(); 
      Chromosome p2 = getParentChromosome(); 
      List<Chromosome> children = Chromosome.genetic(p1, p2); 
      if (children != null) { 
        for (Chromosome chro : children) { 
          childPopulation.add(chro); 
        } 
      }  
    } 
    //新種群替換舊種群 
    List<Chromosome> t = population; 
    population = childPopulation; 
    t.clear(); 
    t = null; 
    //基因突變 
    mutation(); 
    //計(jì)算新種群的適應(yīng)度 
    caculteScore(); 
  } 
   
  /** 
   * @return  
   * @Description: 輪盤賭法選擇可以遺傳下一代的染色體 
   */ 
  private Chromosome getParentChromosome (){ 
    double slice = Math.random() * totalScore; 
    double sum = 0; 
    for (Chromosome chro : population) { 
      sum += chro.getScore(); 
      if (sum > slice && chro.getScore() >= averageScore) { 
        return chro; 
      } 
    } 
    return null; 
  } 
   
  /**  
   * @Description: 計(jì)算種群適應(yīng)度 
   */ 
  private void caculteScore() { 
    setChromosomeScore(population.get(0)); 
    bestScore = population.get(0).getScore(); 
    worstScore = population.get(0).getScore(); 
    totalScore = 0; 
    for (Chromosome chro : population) { 
      setChromosomeScore(chro); 
      if (chro.getScore() > bestScore) { //設(shè)置最好基因值 
        bestScore = chro.getScore(); 
        if (y < bestScore) { 
          x = changeX(chro); 
          y = bestScore; 
          geneI = generation; 
        } 
      } 
      if (chro.getScore() < worstScore) { //設(shè)置最壞基因值 
        worstScore = chro.getScore(); 
      } 
      totalScore += chro.getScore(); 
    } 
    averageScore = totalScore / popSize; 
    //因?yàn)榫葐栴}導(dǎo)致的平均值大于最好值，將平均值設(shè)置成最好值 
    averageScore = averageScore > bestScore ? bestScore : averageScore; 
  } 
   
  /** 
   * 基因突變 
   */ 
  private void mutation() { 
    for (Chromosome chro : population) { 
      if (Math.random() < mutationRate) { //發(fā)生基因突變 
        int mutationNum = (int) (Math.random() * maxMutationNum); 
        chro.mutation(mutationNum); 
      } 
    } 
  } 
   
  /** 
   * @param chro 
   * @Description: 設(shè)置染色體得分 
   */ 
  private void setChromosomeScore(Chromosome chro) { 
    if (chro == null) { 
      return; 
    } 
    double x = changeX(chro); 
    double y = caculateY(x); 
    chro.setScore(y); 
 
  } 
   
  /** 
   * @param chro 
   * @return 
   * @Description: 將二進(jìn)制轉(zhuǎn)化為對應(yīng)的X 
   */ 
  public abstract double changeX(Chromosome chro); 
   
   
  /** 
   * @param x 
   * @return 
   * @Description: 根據(jù)X計(jì)算Y值 Y=F(X) 
   */ 
  public abstract double caculateY(double x); 
 
  public void setPopulation(List<Chromosome> population) { 
    this.population = population; 
  } 
 
  public void setPopSize(int popSize) { 
    this.popSize = popSize; 
  } 
 
  public void setGeneSize(int geneSize) { 
    this.geneSize = geneSize; 
  } 
 
  public void setMaxIterNum(int maxIterNum) { 
    this.maxIterNum = maxIterNum; 
  } 
 
  public void setMutationRate(double mutationRate) { 
    this.mutationRate = mutationRate; 
  } 
 
  public void setMaxMutationNum(int maxMutationNum) { 
    this.maxMutationNum = maxMutationNum; 
  } 
 
  public double getBestScore() { 
    return bestScore; 
  } 
 
  public double getWorstScore() { 
    return worstScore; 
  } 
 
  public double getTotalScore() { 
    return totalScore; 
  } 
 
  public double getAverageScore() { 
    return averageScore; 
  } 
 
  public double getX() { 
    return x; 
  } 
 
  public double getY() { 
    return y; 
  } 
}

3、GeneticAlgorithmTest類

 /**  
 *@Description:   
 */  
package com.lulei.genetic.algorithm;  
  
public class GeneticAlgorithmTest extends GeneticAlgorithm{ 
   
  public static final int NUM = 1 << 24; 
 
  public GeneticAlgorithmTest() { 
    super(24);  
  } 
   
  @Override 
  public double changeX(Chromosome chro) { 
    // TODO Auto-generated method stub  
    return ((1.0 * chro.getNum() / NUM) * 100) + 6; 
  } 
 
  @Override 
  public double caculateY(double x) { 
    // TODO Auto-generated method stub  
    return 100 - Math.log(x); 
  } 
 
  public static void main(String[] args) { 
    GeneticAlgorithmTest test = new GeneticAlgorithmTest(); 
    test.caculte(); 
  } 
}

以上就是關(guān)于Java遺傳算法的詳細(xì)介紹，希望對大家學(xué)習(xí)Java遺傳算法有所幫助。

您可能感興趣的文章: