遗传算法解决迷宫寻路问题（Java实现）

遗传算法解决迷宫寻路问题（Java实现）。

1.什么是遗传算法？
就个人理解，遗传算法是模拟神奇的大自然中生物“优胜劣汰”原则指导下的进化过程，好的基因有更多的机会得到繁衍，这样一来，随着繁衍的进行，生物种群会朝着一个趋势收敛。而生物繁衍过程中的基因杂交和变异会给种群提供更好的基因序列，这样种群的繁衍趋势将会是“长江后浪推前浪，一代更比一代强”，而不会是只受限于祖先的最好基因。而程序可以通过模拟这种过程来获得问题的最优解（但不一定能得到）。要利用该过程来解决问题，受限需要构造初始的基因组，并为对每个基因进行适应性分数（衡量该基因的好坏程度）初始化，接着从初始的基因组中选出两个父基因（根据适应性分数，采用轮盘算法进行选择）进行繁衍，基于一定的杂交率（父基因进行杂交的概率）和变异率（子基因变异的概率），这两个父基因会生成两个子基因，然后将这两个基因放入种群中，到这里繁衍一代完成，重复繁衍的过程直到种群收敛或适应性分数达到最大。
2.利用遗传算法解决迷宫寻路问题。
代码如下：

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 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 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=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=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 maxGene.getScore()){
                maxGene = gene;
            }
            gene.setScore(score);
            geneGroup.add(gene);
        }
    }

    /**
     * 根据适应性分数随机获得进行交配的父类基因下标
     * @param list
     * @return
     */
    private static int getParent(List list){
        int result  = 0;
        double r = random.nextDouble();
        double score;
        double sum = 0;
        double totalScores = getTotalScores(geneGroup);
        for(int i=0;i= r){
                result = i;
                return result;
            }
        }
        return result;
    }


    /**
     * 获得全部基因组的适应性分数总和
     * @param list
     * @return
     */
    private static double getTotalScores(List list){
        double result = 0;
        for(int i=0;i= CROSSOVER_RATE){
            //决定杂交起点
            int n = random.nextInt(CHROMO_LENGTH);
            for(int i=n;i= 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
3.下面是运行结果截图