Java遗传算法之冲出迷宫
遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它能解决很多问题，比如数学方程的最大最小值，背包问题，装箱问题等。在游戏开发中遗传算法的应用也十分频繁，不少的游戏AI 都利用遗传算法进行编码。
就个人理解，遗传算法是模拟神奇的大自然中生物“优胜劣汰”原则指导下的进化过程，好的基因有更多的机会得到繁衍，这样一来，随着繁衍的进行，生物种群会朝着一个趋势收敛。而生物繁衍过程中的基因杂交和变异会给种群提供更好的基因序列，这样种群的繁衍趋势将会是“长江后浪推前浪，一代更比一代强”，而不会是只受限于祖先的最好基因。而程序可以通过模拟这种过程来获得问题的最优解（但不一定能得到）。要利用该过程来解决问题，受限需要构造初始的基因组，并为对每个基因进行适应性分数（衡量该基因的好坏程度）初始化，接着从初始的基因组中选出两个父基因（根据适应性分数，采用轮盘算法进行选择）进行繁衍，基于一定的杂交率（父基因进行杂交的概率）和变异率（子基因变异的概率），这两个父基因会生成两个子基因，然后将这两个基因放入种群中，到这里繁衍一代完成，重复繁衍的过程直到种群收敛或适应性分数达到最大。
接下来我们就看看用遗传算法冲出迷宫的实例。
代码如下：
importjava.awt.Color;
importjava.awt.Graphics;
importjava.awt.GridLayout;
importjava.util.ArrayList;
importjava.util.List;
importjava.util.Random;
importjavax.swing.JFrame;
importjavax.swing.JLabel;
importjavax.swing.JPanel;
@SuppressWarnings("serial")
publicclassMazeProblemextendsJFrame{
//当前基因组
privatestaticListgeneGroup=newArrayList<>();
privatestaticRandomrandom=newRandom();
privatestaticintstartX=2;
privatestaticintstartY=0;
privatestaticintendX=7;
privatestaticintendY=14;
//杂交率
privatestaticfinaldoubleCROSSOVER_RATE=0.7;
//变异率
privatestaticfinaldoubleMUTATION_RATE=0.0001;
//基因组初始个数
privatestaticfinalintPOP_SIZE=140;
//基因长度
privatestaticfinalintCHROMO_LENGTH=70;
//最大适应性分数的基因
privatestaticGenemaxGene=newGene(CHROMO_LENGTH);
//迷宫地图
privatestaticint[][]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}};
privatestaticintMAP_WIDTH=15;
privatestaticintMAP_HEIGHT=10;
privateListlabels=newArrayList<>();
publicMazeProblem(){
//初始化
setSize(700,700);
setDefaultCloseOperation(DISPOSE_ON_CLOSE);
setResizable(false);
getContentPane().setLayout(null);
JPanelpanel=newJPanel();
panel.setLayout(newGridLayout(MAP_HEIGHT,MAP_WIDTH));
panel.setBounds(10,10,MAP_WIDTH*40,MAP_HEIGHT*40);
getContentPane().add(panel);
for(inti=0;i=1&&map[curX-1][curY]==0){
curX--;
}
}
//下
elseif(gene[i]==0&&gene[i+1]==1){
if(curX<=MAP_HEIGHT-1&&map[curX+1][curY]==0){
curX++;
}
}
//左
elseif(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);
}
}
publicstaticvoidmain(String[]args){
//初始化基因组
init();
while(maxGene.getScore()<1){
//选择进行交配的两个基因
intp1=getParent(geneGroup);
intp2=getParent(geneGroup);
//用轮盘转动法选择两个基因进行交配,杂交和变异
mate(p1,p2);
}
newMazeProblem().setVisible(true);
}
/**
*根据路径获得适应性分数
*@parampath
*@return
*/
privatestaticdoublegetScore(int[]gene){
doubleresult=0;
intcurX=startX;
intcurY=startY;
for(inti=0;i=1&&map[curX-1][curY]==0){
curX--;
}
}
//下
elseif(gene[i]==0&&gene[i+1]==1){
if(curX<=MAP_HEIGHT-1&&map[curX+1][curY]==0){
curX++;
}
}
//左
elseif(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++;
}
}
}
doublex=Math.abs(curX-endX);
doubley=Math.abs(curY-endY);
//如果和终点只有一格距离则返回1
if((x==1&&y==0)||(x==0&&y==1)){
return1;
}
//计算适应性分数
result=1/(x+y+1);
returnresult;
}
/**
*基因初始化
*/
privatestaticvoidinit(){
for(inti=0;imaxGene.getScore()){
maxGene=gene;
}
gene.setScore(score);
geneGroup.add(gene);
}
}
/**
*根据适应性分数随机获得进行交配的父类基因下标
*@paramlist
*@return
*/
privatestaticintgetParent(Listlist){
intresult=0;
doubler=random.nextDouble();
doublescore;
doublesum=0;
doubletotalScores=getTotalScores(geneGroup);
for(inti=0;i=r){
result=i;
returnresult;
}
}
returnresult;
}
/**
*获得全部基因组的适应性分数总和
*@paramlist
*@return
*/
privatestaticdoublegetTotalScores(Listlist){
doubleresult=0;
for(inti=0;i=CROSSOVER_RATE){
//决定杂交起点
intn=random.nextInt(CHROMO_LENGTH);
for(inti=n;i=MUTATION_RATE){
//选择变异位置
intn=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);
doublescore1=getScore(c1.getGene());
doublescore2=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);
}
}
/**
*基因
*@authorZZF
*
*/
classGene{
//染色体长度
privateintlen;
//基因数组
privateint[]gene;
//适应性分数
privatedoublescore;
publicGene(intlen){
this.len=len;
gene=newint[len];
Randomrandom=newRandom();
//随机生成一个基因序列
for(inti=0;i
以上就是本文关于遗传算法冲出迷宫方法实例解析，希望对大家有所帮助。