注册 留言板
当前位置:首页 > 编程语言 > Java > 正文

遗传算法解决迷宫寻路问题(Java实现)

来源:CSDN   发布时间: 2017-06-19   作者:mynameis121   浏览次数:
摘要: 1.什么是遗传算法? 就个人理解,遗传算法是模拟神奇的大自然中生物“优胜劣汰”原则指导下的进化过程,好的基因有更多的机会...

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

3.下面是运行结果截图
程序运行结果



数据挖掘 遗传算法 迷宫寻路 java
我来说两句
评论内容:
验  证  码:
 
(网友评论仅供其表达个人看法,并不表明本站同意其观点或证实其描述。)
评论列表
已有 0 条评论(查看更多评论)
精彩专题
友情链接:
QQ交流群:①群 155252576 ②群 469193068 ③群 531831996 ④群 243504572
设为首页 - 加入收藏 Copyright @2016 Infocool 版权所有 粤ICP备16000626号