Beispielanalyse eines genetischen Java-Algorithmus zur Realisierung eines Ausbruchs aus dem Labyrinth

In diesem Artikel wird zunächst ausführlich vorgestellt, was ein genetischer Algorithmus ist, und dann wird die Idee eines genetischen Algorithmus verwendet, um genetische Algorithmen zu analysieren und zur Lösung von Labyrinthproblemen zu verwenden.

Genetisch Der Algorithmus ist eine Simulation von Darwins biologischer Evolutionstheorie. Das Computermodell des biologischen Evolutionsprozesses der natürlichen Selektion und genetischer Mechanismen ist eine Methode zur Suche nach optimalen Lösungen durch Simulation des natürlichen Evolutionsprozesses. Es kann viele Probleme lösen, z. B. die Maximal- und Minimalwerte mathematischer Gleichungen, Rucksackprobleme, Mülleimerprobleme usw. Genetische Algorithmen kommen auch in der Spieleentwicklung sehr häufig zum Einsatz und viele Spiele-KIs verwenden genetische Algorithmen zur Codierung.

Soweit ich es verstehe, simuliert der genetische Algorithmus den Evolutionsprozess, der vom magischen Prinzip des „Überlebens des Stärkeren“ in der Natur geleitet wird. Auf diese Weise haben gute Gene mehr Möglichkeiten, sich zu reproduzieren , , biologische Populationen werden sich einem Trend annähern. Genetische Hybridisierung und Mutation im Prozess der biologischen Reproduktion werden bessere genetische Sequenzen für die Bevölkerung liefern. Auf diese Weise wird der Reproduktionstrend der Bevölkerung „die Wellen hinter dem Jangtse-Fluss vorantreiben, und jede Generation wird stärker als die.“ vorherige Generation", anstatt nur durch die Vorfahren begrenzt zu sein. Die besten Gene. Das Programm kann durch Simulation dieses Prozesses die optimale Lösung für das Problem erhalten (dies wird jedoch möglicherweise nicht erreicht). Um das Problem mit diesem Prozess zu lösen, müssen Sie ein anfängliches Genom konstruieren, für jedes Gen einen Fitness-Score (ein Maß dafür, wie gut das Gen ist) initialisieren und dann zwei Elterngene aus dem anfänglichen Genom auswählen ( Entsprechend der Fitness). Basierend auf einer bestimmten Hybridisierungsrate (der Wahrscheinlichkeit der Hybridisierung des Elterngens) und der Mutationsrate (der Mutationswahrscheinlichkeit des untergeordneten Gens) werden diese beiden Elterngene generiert zwei untergeordnete Gene und fügen Sie diese beiden Gene dann in die Population ein, wo eine Reproduktionsgeneration abgeschlossen ist, und der Reproduktionsprozess wird wiederholt, bis die Population konvergiert oder der Fitnesswert das Maximum erreicht.

Als nächstes schauen wir uns ein Beispiel für die Verwendung eines genetischen Algorithmus an, um aus einem Labyrinth auszubrechen.

Der Code lautet wie folgt:

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

Das obige ist der detaillierte Inhalt vonBeispielanalyse eines genetischen Java-Algorithmus zur Realisierung eines Ausbruchs aus dem Labyrinth. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!