미로 탈출 구현을 위한 자바 유전자 알고리즘 분석 사례

이 글에서는 먼저 유전 알고리즘이 무엇인지 자세히 소개한 후 유전 알고리즘의 개념을 활용하여 유전 알고리즘을 분석하고 활용하여 미로 문제를 해결하는 데 도움이 되는 친구들을 참고할 수 있습니다

유전 알고리즘은 다윈의 생물학적 진화론을 모사한 자연선택과 유전학 메커니즘의 생물학적 진화 과정을 계산하는 모델은 자연의 진화 과정을 모사하여 최적의 해를 찾는 방법이다. 수학 방정식의 최대값과 최소값, 배낭 문제, 빈 포장 문제 등과 같은 많은 문제를 해결할 수 있습니다. 유전 알고리즘은 게임 개발에서도 매우 자주 사용되며, 많은 게임 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());
 }
}

위 내용은 미로 탈출 구현을 위한 자바 유전자 알고리즘 분석 사례의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!