Java遗传算法之冲出迷宫

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它能解决很多问题，比如数学方程的最大最小值，背包问题，装箱问题等。在游戏开发中遗传算法的应用也十分频繁，不少的游戏 AI 都利用遗传算法进行编码。

就个人理解，遗传算法是模拟神奇的大自然中生物“优胜劣汰”原则指导下的进化过程，好的基因有更多的机会得到繁衍，这样一来，随着繁衍的进行，生物种群会朝着一个趋势收敛。而生物繁衍过程中的基因杂交和变异会给种群提供更好的基因序列，这样种群的繁衍趋势将会是“长江后浪推前浪，一代更比一代强”，而不会是只受限于祖先的最好基因。而程序可以通过模拟这种过程来获得问题的最优解（但不一定能得到）。要利用该过程来解决问题，受限需要构造初始的基因组，并为对每个基因进行适应性分数（衡量该基因的好坏程度）初始化，接着从初始的基因组中选出两个父基因（根据适应性分数，采用轮盘算法进行选择）进行繁衍，基于一定的杂交率（父基因进行杂交的概率）和变异率（子基因变异的概率），这两个父基因会生成两个子基因，然后将这两个基因放入种群中，到这里繁衍一代完成，重复繁衍的过程直到种群收敛或适应性分数达到最大。

接下来我们就看看用遗传算法冲出迷宫的实例。

代码如下：

import java.awt.Color;
import java.awt.Graphics;
import java.awt.GridLayout;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
@SuppressWarnings("serial")
public class MazeProblem extends JFrame{
//当前基因组
private static List<Gene> geneGroup = new ArrayList<>();
private static Random random = new Random();
private static int startX = 2;
private static int startY = 0;
private static int endX = 7;
private static int endY = 14;
//杂交率
private static final double CROSSOVER_RATE = 0.7;
//变异率
private static final double MUTATION_RATE = 0.0001;
//基因组初始个数
private static final int POP_SIZE = 140;
//基因长度
private static final int CHROMO_LENGTH = 70;
//最大适应性分数的基因
private static Gene maxGene = new Gene(CHROMO_LENGTH);
//迷宫地图
private static int[][] map = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
      {1,0,1,0,0,0,0,0,1,1,1,0,0,0,1},
      {5,0,0,0,0,0,0,0,1,1,1,0,0,0,1},
      {1,0,0,0,1,1,1,0,0,1,0,0,0,0,1},
      {1,0,0,0,1,1,1,0,0,0,0,0,1,0,1},
      {1,1,0,0,1,1,1,0,0,0,0,0,1,0,1},
      {1,0,0,0,0,1,0,0,0,0,1,1,1,0,1},
      {1,0,1,1,0,0,0,1,0,0,0,0,0,0,8},
      {1,0,1,1,0,0,0,1,0,0,0,0,0,0,1},
      {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
private static int MAP_WIDTH = 15;
private static int MAP_HEIGHT = 10;
private List<JLabel> labels = new ArrayList<>();
public MazeProblem(){
 // 初始化
 setSize(700, 700);
 setDefaultCloseOperation(DISPOSE_ON_CLOSE);
 setResizable(false);
 getContentPane().setLayout(null);
 JPanel panel = new JPanel();
 panel.setLayout(new GridLayout(MAP_HEIGHT,MAP_WIDTH));
 panel.setBounds(10, 10, MAP_WIDTH*40, MAP_HEIGHT*40);
 getContentPane().add(panel);
 for(int i=0;i<MAP_HEIGHT;i++){
  for(int j=0;j<MAP_WIDTH;j++){
   JLabel label = new JLabel();
   Color color = null;
   if(map[i][j] == 1){
    color = Color.black;
   }
   if(map[i][j] == 0){
    color = Color.GRAY;
   }
   if(map[i][j] == 5 || map[i][j] ==8){
    color = Color.red;
   }
   label.setBackground(color);
   label.setOpaque(true);
   panel.add(label);
   labels.add(label);
  }
 }
}
@Override
public void paint(Graphics g) {
 super.paint(g);
 //画出路径
 int[] gene = maxGene.getGene();
 int curX = startX;
 int curY = startY;
 for(int i=0;i<gene.length;i+=2){
  //上
  if(gene[i] == 0 && gene[i+1] == 0){
   if(curX >=1 && map[curX-1][curY] == 0){
    curX --;
   }
  }
  //下
  else if(gene[i] == 0 && gene[i+1] == 1){
   if(curX <=MAP_HEIGHT-1 && map[curX+1][curY] == 0){
    curX ++;
   }
  }
  //左
  else if(gene[i] == 1 && gene[i+1] == 0){
   if(curY >=1 && map[curX][curY-1] == 0){
    curY --;
   }
  }
  //右
  else{
   if(curY <= MAP_WIDTH-1 && map[curX][curY+1] == 0){
    curY ++;
   }
  }
  labels.get(curX*MAP_WIDTH+curY).setBackground(Color.BLUE);
 }
}
public static void main(String[] args) {
 //初始化基因组
 init();
 while(maxGene.getScore() < 1){
  //选择进行交配的两个基因
  int p1 = getParent(geneGroup);
  int p2 = getParent(geneGroup);
  //用轮盘转动法选择两个基因进行交配,杂交和变异
  mate(p1,p2);
 }
 new MazeProblem().setVisible(true);
}
/**
 * 根据路径获得适应性分数
 * @param path
 * @return
 */
private static double getScore(int[] gene){
 double result = 0;
 int curX = startX;
 int curY = startY;
 for(int i=0;i<gene.length;i+=2){
  //上
  if(gene[i] == 0 && gene[i+1] == 0){
   if(curX >=1 && map[curX-1][curY] == 0){
    curX --;
   }
  }
  //下
  else if(gene[i] == 0 && gene[i+1] == 1){
   if(curX <=MAP_HEIGHT-1 && map[curX+1][curY] == 0){
    curX ++;
   }
  }
  //左
  else if(gene[i] == 1 && gene[i+1] == 0){
   if(curY >=1 && map[curX][curY-1] == 0){
    curY --;
   }
  }
  //右
  else{
   if(curY <= MAP_WIDTH-1 && map[curX][curY+1] == 0){
    curY ++;
   }
  }
 }
 double x = Math.abs(curX - endX);
 double y = Math.abs(curY - endY);
 //如果和终点只有一格距离则返回1
 if((x == 1&& y==0) || (x==0&&y==1)){
  return 1;
 }
 //计算适应性分数
 result = 1/(x+y+1);
 return result;
}
/**
 * 基因初始化
 */
private static void init(){
 for(int i=0;i<POP_SIZE;i++){
  Gene gene = new Gene(CHROMO_LENGTH);
  double score = getScore(gene.getGene());
  if(score > maxGene.getScore()){
   maxGene = gene;
  }
  gene.setScore(score);
  geneGroup.add(gene);
 }
}
/**
 * 根据适应性分数随机获得进行交配的父类基因下标
 * @param list
 * @return
 */
private static int getParent(List<Gene> list){
 int result = 0;
 double r = random.nextDouble();
 double score;
 double sum = 0;
 double totalScores = getTotalScores(geneGroup);
 for(int i=0;i<list.size();i++){
  Gene gene = list.get(i);
  score = gene.getScore();
  sum += score/totalScores;
  if(sum >= r){
   result = i;
   return result;
  }
 }
 return result;
}
/**
 * 获得全部基因组的适应性分数总和
 * @param list
 * @return
 */
private static double getTotalScores(List<Gene> list){
 double result = 0;
 for(int i=0;i<list.size();i++){
  result += list.get(i).getScore();
 }
 return result;
}
/**
 * 两个基因进行交配
 * @param p1
 * @param p2
 */
private static void mate(int n1,int n2){
 Gene p1 = geneGroup.get(n1);
 Gene p2 = geneGroup.get(n2);
 Gene c1 = new Gene(CHROMO_LENGTH);
 Gene c2 = new Gene(CHROMO_LENGTH);
 int[] gene1 = new int[CHROMO_LENGTH];
 int[] gene2 = new int[CHROMO_LENGTH];
 for(int i=0;i<CHROMO_LENGTH;i++){
  gene1[i] = p1.getGene()[i];
  gene2[i] = p2.getGene()[i];
 }
 //先根据杂交率决定是否进行杂交
 double r = random.nextDouble();
 if(r >= CROSSOVER_RATE){
  //决定杂交起点
  int n = random.nextInt(CHROMO_LENGTH);
  for(int i=n;i<CHROMO_LENGTH;i++){
   int tmp = gene1[i];
   gene1[i] = gene2[i];
   gene2[i] = tmp;
  }
 }
 //根据变异率决定是否
 r = random.nextDouble();
 if(r >= MUTATION_RATE){
  //选择变异位置
  int n = random.nextInt(CHROMO_LENGTH);
  if(gene1[n] == 0){
   gene1[n] = 1;
  }
  else{
   gene1[n] = 0;
  }
  if(gene2[n] == 0){
   gene2[n] = 1;
  }
  else{
   gene2[n] = 0;
  }
 }
 c1.setGene(gene1);
 c2.setGene(gene2);
 double score1 = getScore(c1.getGene());
 double score2 = getScore(c2.getGene());
 if(score1 >maxGene.getScore()){
  maxGene = c1;
 }
 if(score2 >maxGene.getScore()){
  maxGene = c2;
 }
 c1.setScore(score1);
 c2.setScore(score2);
 geneGroup.add(c1);
 geneGroup.add(c2);
}
}
/**
* 基因
* @author ZZF
*
*/
class Gene{
//染色体长度
private int len;
//基因数组
private int[] gene;
//适应性分数
private double score;
public Gene(int len){
 this.len = len;
 gene = new int[len];
 Random random = new Random();
 //随机生成一个基因序列
 for(int i=0;i<len;i++){
  gene[i] = random.nextInt(2);
 }
 //适应性分数设置为0
 this.score = 0;
}
public int getLen() {
 return len;
}
public void setLen(int len) {
 this.len = len;
}
public int[] getGene() {
 return gene;
}
public void setGene(int[] gene) {
 this.gene = gene;
}
public double getScore() {
 return score;
}
public void setScore(double score) {
 this.score = score;
}
public void print(){
 StringBuilder sb = new StringBuilder();
 for(int i=0;i<gene.length;i+=2){
  if(gene[i] == 0 && gene[i+1] == 0){
   sb.append("上");
  }
  //下
  else if(gene[i] == 0 && gene[i+1] == 1){
   sb.append("下");
  }
  //左
  else if(gene[i] == 1 && gene[i+1] == 0){
   sb.append("左");
  }
  //右
  else{
   sb.append("右");
  }
 }
 System.out.println(sb.toString());
}
}

来源：https://www.2cto.com/kf/201706/649186.html