Java遺傳算法之沖出迷宮

更新時間：2017年09月13日 10:49:11 投稿：mengwei

這篇文章首先詳細(xì)介紹了什么是遺傳算法，然后通過遺傳算法的思想用實(shí)例解析使用遺傳算法解決迷宮問題,需要的朋友可以參考下

遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。它能解決很多問題，比如數(shù)學(xué)方程的最大最小值，背包問題，裝箱問題等。在游戲開發(fā)中遺傳算法的應(yīng)用也十分頻繁，不少的游戲 AI 都利用遺傳算法進(jìn)行編碼。

就個人理解，遺傳算法是模擬神奇的大自然中生物“優(yōu)勝劣汰”原則指導(dǎo)下的進(jìn)化過程，好的基因有更多的機(jī)會得到繁衍，這樣一來，隨著繁衍的進(jìn)行，生物種群會朝著一個趨勢收斂。而生物繁衍過程中的基因雜交和變異會給種群提供更好的基因序列，這樣種群的繁衍趨勢將會是“長江后浪推前浪，一代更比一代強(qiáng)”，而不會是只受限于祖先的最好基因。而程序可以通過模擬這種過程來獲得問題的最優(yōu)解（但不一定能得到）。要利用該過程來解決問題，受限需要構(gòu)造初始的基因組，并為對每個基因進(jìn)行適應(yīng)性分?jǐn)?shù)（衡量該基因的好壞程度）初始化，接著從初始的基因組中選出兩個父基因（根據(jù)適應(yīng)性分?jǐn)?shù)，采用輪盤算法進(jìn)行選擇）進(jìn)行繁衍，基于一定的雜交率（父基因進(jìn)行雜交的概率）和變異率（子基因變異的概率），這兩個父基因會生成兩個子基因，然后將這兩個基因放入種群中，到這里繁衍一代完成，重復(fù)繁衍的過程直到種群收斂或適應(yīng)性分?jǐn)?shù)達(dá)到最大。

接下來我們就看看用遺傳算法沖出迷宮的實(shí)例。

代碼如下：

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{
 //當(dāng)前基因組
 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;
 //基因組初始個數(shù)
 private static final int POP_SIZE = 140;
 //基因長度
 private static final int CHROMO_LENGTH = 70;
 //最大適應(yīng)性分?jǐn)?shù)的基因
 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){
   //選擇進(jìn)行交配的兩個基因
   int p1 = getParent(geneGroup);
   int p2 = getParent(geneGroup);
   //用輪盤轉(zhuǎn)動法選擇兩個基因進(jìn)行交配,雜交和變異
   mate(p1,p2);
  }
  new MazeProblem().setVisible(true);
 }
 /**
  * 根據(jù)路徑獲得適應(yīng)性分?jǐn)?shù)
  * @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);
  //如果和終點(diǎn)只有一格距離則返回1
  if((x == 1&& y==0) || (x==0&&y==1)){
   return 1;
  }
  //計(jì)算適應(yīng)性分?jǐn)?shù)
  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);
  }
 }
 /**
  * 根據(jù)適應(yīng)性分?jǐn)?shù)隨機(jī)獲得進(jìn)行交配的父類基因下標(biāo)
  * @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;
 }
 /**
  * 獲得全部基因組的適應(yīng)性分?jǐn)?shù)總和
  * @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;
 }
 /**
  * 兩個基因進(jìn)行交配
  * @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];
  }
  //先根據(jù)雜交率決定是否進(jìn)行雜交
  double r = random.nextDouble();
  if(r >= CROSSOVER_RATE){
   //決定雜交起點(diǎn)
   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;
   }
  }
  //根據(jù)變異率決定是否
  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;
 //基因數(shù)組
 private int[] gene;
 //適應(yīng)性分?jǐn)?shù)
 private double score;
 public Gene(int len){
  this.len = len;
  gene = new int[len];
  Random random = new Random();
  //隨機(jī)生成一個基因序列
  for(int i=0;i<len;i++){
   gene[i] = random.nextInt(2);
  }
  //適應(yīng)性分?jǐn)?shù)設(shè)置為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());
 }
}

以上就是本文關(guān)于遺傳算法沖出迷宮方法實(shí)例解析，希望對大家有所幫助。

您可能感興趣的文章: