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

以上就是本文关于遗传算法冲出迷宫方法实例解析，希望对大家有所帮助。

# java  # 遗传算法  # 遗传算法实例  # Java编写迷宫小游戏  # Java实现走迷宫回溯算法  # Java基于深度优先遍历的随机迷宫生成算法  # java实现单词搜索迷宫游戏  # java图的深度优先遍历实现随机生成迷宫  # 使用栈的迷宫算法java版代码  # Java项目实现寻找迷宫出路  # java寻找迷宫路径的简单实现示例  # java 实现迷宫回溯算法示例详解  # 如何利用JAVA实现走迷宫程序  # 这两个  # 达尔文  # 最优  # 自然选择  # 是一种  # 将会  # 长江后浪推前浪  # 优胜劣汰  # 可以通过  # 解决问题  # 会给  # 它能  # 但不  # 设置为  # 并为  # 一定能  # 指导下  # 画出  # 过程中  # 游戏开发 

相关文章： 网站规划与制作是什么,电子商务网站系统规划的内容及步骤是什么？  建站168自助建站系统：快速模板定制与SEO优化指南  如何制作新型网站程序文件,新型止水鱼鳞网要拆除吗？  如何登录建站主机？访问步骤全解析  C++如何编写函数模板？（泛型编程入门）  独立制作一个网站多少钱,建立网站需要花多少钱？  建站主机数据库如何配置才能提升网站性能？  建站中国官网：模板定制+SEO优化+建站流程一站式指南  如何用免费手机建站系统零基础打造专业网站？  南京做网站制作公司,南京哈发网络有限公司，公司怎么样，做网页美工DIV+CSS待遇怎么样？  如何在阿里云虚拟服务器快速搭建网站？  婚礼视频制作网站,学习*后期制作的网站有哪些？  高防服务器如何保障网站安全无虞？  如何零基础开发自助建站系统？完整教程解析  建站之星代理平台如何选择最佳方案？  建站主机CVM配置优化、SEO策略与性能提升指南  如何用低价快速搭建高质量网站？  如何获取开源自助建站系统免费下载链接？  如何配置WinSCP新建站点的密钥验证步骤？  如何在橙子建站上传落地页？操作指南详解  娃派WAP自助建站：免费模板+移动优化，快速打造专业网站  定制建站模板如何实现SEO优化与智能系统配置？18字教程  网站设计制作公司地址,网站建设比较好的公司都有哪些？  高端云建站费用究竟需要多少预算？  香港服务器建站指南：外贸独立站搭建与跨境电商配置流程  香港服务器网站测试全流程：性能评估、SEO加载与移动适配优化  高端网站建设与定制开发一站式解决方案 中企动力  ,制作一个手机app网站要多少钱？  如何制作一个表白网站视频,关于勇敢表白的小标题？  常州自助建站费用包含哪些项目？  长沙企业网站制作哪家好,长沙水业集团官方网站？  太原网站制作公司有哪些,网约车营运证查询官网？  制作网站的网址是什么,请问后缀为.com和.com.cn还有.cn的这三种网站是分别是什么类型的网站？  免费公司网站制作软件,如何申请免费主页空间做自己的网站？  如何确保FTP站点访问权限与数据传输安全？  高防网站服务器：DDoS防御与BGP线路的AI智能防护方案  企业网站制作费用多少,企业网站空间一般需要多大，费用是多少？  如何在景安服务器上快速搭建个人网站？  微信推文制作网站有哪些,怎么做微信推文，急？  建站之星CMS五站合一模板配置与SEO优化指南  移动端手机网站制作软件,掌上时代，移动端网站的谷歌SEO该如何做？  网页设计与网站制作内容,怎样注册网站？  威客平台建站流程解析：高效搭建教程与设计优化方案  建站之星客服服务时间及联系方式如何？  制作网站的软件免费下载,免费制作app哪个平台好？  如何在香港免费服务器上快速搭建网站？  如何在自有机房高效搭建专业网站？  免费视频制作网站,更新又快又好的免费电影网站？  公司网站制作需要多少钱,找人做公司网站需要多少钱？  如何通过主机屋免费建站教程十分钟搭建网站？