Example Analysis of Java Genetic Algorithm to Realize Breaking out of the Maze

This article first introduces in detail what a genetic algorithm is, and then uses the genetic algorithm to solve the maze problem through the example analysis of the idea of ​​the genetic algorithm. Friends in need can refer to it

The genetic algorithm is a simulation of Darwin's biological evolution theory The computational model of the biological evolution process of natural selection and genetic mechanisms is a method of searching for optimal solutions by simulating the natural evolution process. It can solve many problems, such as the maximum and minimum values ​​of mathematical equations, knapsack problems, bin packing problems, etc. Genetic algorithms are also used very frequently in game development, and many game AIs use genetic algorithms for coding.

As far as I understand it, the genetic algorithm simulates the evolutionary process guided by the magical principle of "survival of the fittest" in nature. Good genes have more opportunities to reproduce. In this way, as reproduction proceeds, , biological populations will converge toward a trend. Genetic hybridization and mutation in the process of biological reproduction will provide better genetic sequences for the population. In this way, the reproduction trend of the population will be "the waves behind the Yangtze River push the waves ahead, and each generation becomes stronger than the previous generation", instead of being limited only by the ancestors. The best genes. The program can obtain the optimal solution to the problem by simulating this process (but it may not be obtained). To use this process to solve the problem, you need to construct an initial genome, initialize a fitness score (a measure of how good the gene is) for each gene, and then select two parent genes from the initial genome ( According to the fitness score, the * algorithm is used to select) for reproduction. Based on a certain hybridization rate (the probability of hybridization of the parent gene) and the mutation rate (the probability of mutation of the child gene), these two parent genes will generate two child genes, and then Put these two genes into the population, where one generation of reproduction is completed, and the reproduction process is repeated until the population converges or the fitness score reaches the maximum.

Next let’s look at an example of using genetic algorithms to break out of a maze.

The code is as follows:

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());
 }
}

The above is the detailed content of Example Analysis of Java Genetic Algorithm to Realize Breaking out of the Maze. For more information, please follow other related articles on the PHP Chinese website!