Java遗传算法之冲出迷宫

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 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_;
 private static int MAP_;
 private List 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=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=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 maxGene.getScore()){
    maxGene = gene;
   }
   gene.setScore(score);
   geneGroup.add(gene);
  }
 }
 /**
  * 根据适应性分数随机获得进行交配的父类基因下标
  * @param list
  * @return
  */
 private static int getParent(List list){
  int result = 0;
  double r = random.nextDouble();
  double score;
  double sum = 0;
  double totalScores = getTotalScores(geneGroup);
  for(int i=0;i= r){
    result = i;
    return result;
   }
  }
  return result;
 }
 /**
  * 获得全部基因组的适应性分数总和
  * @param list
  * @return
  */
 private static double getTotalScores(List list){
  double result = 0;
  for(int i=0;i= CROSSOVER_RATE){
   //决定杂交起点
   int n = random.nextInt(CHROMO_LENGTH);
   for(int i=n;i= 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