Java遺傳算法之沖出迷宮
更新時間：2017年09月13日 10:49:11 投稿：mengwei
這篇文章首先詳細介紹了什么是遺傳算法，然后通過遺傳算法的思想用實例解析使用遺傳算法解決迷宮問題,需要的朋友可以參考下
遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。它能解決很多問題，比如數(shù)學方程的最大最小值，背包問題，裝箱問題等。在游戲開發(fā)中遺傳算法的應(yīng)用也十分頻繁，不少的游戲 AI 都利用遺傳算法進行編碼。
就個人理解，遺傳算法是模擬神奇的大自然中生物“優(yōu)勝劣汰”原則指導下的進化過程，好的基因有更多的機會得到繁衍，這樣一來，隨著繁衍的進行，生物種群會朝著一個趨勢收斂。而生物繁衍過程中的基因雜交和變異會給種群提供更好的基因序列，這樣種群的繁衍趨勢將會是“長江后浪推前浪，一代更比一代強”，而不會是只受限于祖先的最好基因。而程序可以通過模擬這種過程來獲得問題的最優(yōu)解（但不一定能得到）。要利用該過程來解決問題，受限需要構(gòu)造初始的基因組，并為對每個基因進行適應(yīng)性分數(shù)（衡量該基因的好壞程度）初始化，接著從初始的基因組中選出兩個父基因（根據(jù)適應(yīng)性分數(shù)，采用輪盤算法進行選擇）進行繁衍，基于一定的雜交率（父基因進行雜交的概率）和變異率（子基因變異的概率），這兩個父基因會生成兩個子基因，然后將這兩個基因放入種群中，到這里繁衍一代完成，重復繁衍的過程直到種群收斂或適應(yīng)性分數(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{
//當前基因組
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)性分數(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){
//選擇進行交配的兩個基因
int p1 = getParent(geneGroup);
int p2 = getParent(geneGroup);
//用輪盤轉(zhuǎn)動法選擇兩個基因進行交配,雜交和變異
mate(p1,p2);
}
new MazeProblem().setVisible(true);
}
/**
* 根據(jù)路徑獲得適應(yīng)性分數(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);
//如果和終點只有一格距離則返回1
if((x == 1&& y==0) || (x==0&&y==1)){
return 1;
}
//計算適應(yīng)性分數(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)性分數(shù)隨機獲得進行交配的父類基因下標
* @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)性分數(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;
}
/**
* 兩個基因進行交配
* @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ù)雜交率決定是否進行雜交
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;
}
}
//根據(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)性分數(shù)
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);
}
//適應(yīng)性分數(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)于遺傳算法沖出迷宮方法實例解析，希望對大家有所幫助。
相關(guān)文章
匿名類是不能有名稱的類，所以沒辦法引用它們,必須在創(chuàng)建時，作為new語句的一部分來聲明它們，需要了解更多的可以參考本文2012-11-11
Java?DelayQueue實現(xiàn)任務(wù)延時示例講解
DelayQueue是一個無界的BlockingQueue的實現(xiàn)類，用于放置實現(xiàn)了Delayed接口的對象，其中的對象只能在其到期時才能從隊列中取走。本文就來利用DelayQueue實現(xiàn)延時任務(wù)，感興趣的可以了解一下2022-09-09
Java購物系統(tǒng)設(shè)計與實現(xiàn)
這篇文章主要為大家詳細介紹了Java購物系統(tǒng)設(shè)計與實現(xiàn)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了Java設(shè)計模式之代理模式詳解,文中有非常詳細的代碼示例,對正在學習java的小伙伴們有很好的幫助,需要的朋友可以參考下2021-05-05
這篇文章主要為大家詳細介紹了java將圖片轉(zhuǎn)為base64返回給前端，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
JAR文件是一種壓縮文件,與常見的ZIP壓縮文件兼容,被稱為JAR包,下面這篇文章主要給大家介紹了關(guān)于使用IDEA打jar包的相關(guān)資料,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2022-08-08
Hadoop實現(xiàn)了一個分布式文件系統(tǒng)（Hadoop?Distributed?File?System），簡稱HDFS，這篇文章給大家介紹Linux下Hadoop?2.7.3?安裝搭建過程，感興趣的朋友跟隨小編一起看看吧2021-11-11
這篇文章主要介紹了Java實現(xiàn)控制臺輸出兩點間距離，涉及了部分編程坐標的問題，具有一定參考價值，需要的朋友可以了解下2017-09-09
spring中@RestController和@Controller的區(qū)別小結(jié)
@RestController和@Controller這兩個注解用于創(chuàng)建Web應(yīng)用程序的控制器類，那么這兩個注解有哪些區(qū)別，本文就來介紹一下，并用示例代碼說明，感興趣的可以了解一下2023-09-09
這篇文章主要介紹了使用maven編譯Java項目實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，,需要的朋友可以參考下2019-06-06