小玩意,利用遗传算法解决迷宫问题
var core = {start:8,end:5,bits:70,//基因的长度group:[],//基因组数据grouplen:140, //基因组的大小crossrate:0.7,//杂交比例mutationrate:0.001,//变异率startpointer:[0,2],//起点坐标currentpointer:[0,2],//当前位置endpointer:[14,7],//终点坐标mum:"",//杂交时候的目基因dad:"",//杂交时候的父亲基因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],[8,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,5],[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]],older:null,nepoch:1,count:0,sungroup:[],//子代的基因组群体tempMap:[],finished:false,draw:function(data){console.log("线路图为",data);var me = this;me.currentpointer = me.startpointer;var nextpos = null,max_x = me.map[0].length,max_y = me.map.length;//for(var i = 0 ; i < data.length ;i++){var m= 0;var t=setInterval(function(){if(m == data.length){clearInterval(t);return;}var index = m;var code = parseInt(data.charAt(index));var curpos = me.currentpointer,curpos_x = curpos[0],curpos_y = curpos[1];console.log(m);switch(code){case 0 : // 上if(curpos_y != 0){nextpos = [curpos_x,curpos_y-1];}break;case 1 : // 下if(curpos_y != max_y){nextpos = [curpos_x,curpos_y+1];}break;case 2 : // 左if(curpos_x != 0){nextpos = [curpos_x-1,curpos_y];}break;case 3 : // 右if(curpos_x != max_x){nextpos = [curpos_x+1,curpos_y];}break;default:break;}if(nextpos != null && me.map[nextpos[1]][nextpos[0]] == 5){// 走到终点了console.log(nextpos);}if(nextpos != null && me.map[nextpos[1]][nextpos[0]] != 1){ // 可以行走me.currentpointer = nextpos;var ele = document.getElementById("map").getElementsByTagName("div");for(var i = 0 ; i < ele.length ; i++){var obj = ele[i],x = obj.getAttribute("x"),y = obj.getAttribute("y");if(me.currentpointer[0] == x && me.currentpointer[1] == y){me.addClass(obj,"step");}}}else{nextpos = this.currentpointer;}m++;},100);},addClass:function(obj,className){if(this.older){this.older.className = (" "+this.older.className+" ").replace(" "+className+" ","");}var olderclass = " " +obj.className+" ";this.older = obj;if(olderclass.indexOf(className) > -1){return;}else{obj.className += " "+className;}},vecBits:function(){var cbits = [],tmp = [];for(var i = 0 ; i < this.bits ;i++){var rbit = Math.floor(Math.random()*2);tmp.push(rbit);if(i % 2 != 0){cbits.push(parseInt(tmp.join(""),2));tmp = [];}}return "0|"+cbits.join(""); // 0为适应性分数 后面为整个的基因组},newGroup:function(){// 生成一个全新的子代全组this.gruop = [];for(var i = 0 ; i < this.grouplen ; i++){this.group.push(this.vecBits());}},testRoute:function(){// 测试每个路径走了多远,并且更新所有的适应性分数for(var i = 0 ; i < this.group.length ;i++){var vec = this.group[i],str = vec.split("|")[1];this.updateScore(str,i);}},updateScore:function(str,index){// 0 , 1, 2, 3分别表示上下左右// 更新基因组的适应性分数for(var i = 0 ; i < str.length ; i++){var code = parseInt(str.charAt(i)),nextpos = null,curpos = this.currentpointer,curpos_x = curpos[0],curpos_y = curpos[1],max_x = this.map[0].length,max_y = this.map.length;switch(code){case 0 : // 上if(curpos_y != 0){nextpos = [curpos_x,curpos_y-1];}break;case 1 : // 下if(curpos_y != max_y){nextpos = [curpos_x,curpos_y+1];}break;case 2 : // 左if(curpos_x != 0){nextpos = [curpos_x-1,curpos_y];}break;case 3 : // 右if(curpos_x != max_x){nextpos = [curpos_x+1,curpos_y];}break;default:break;}if(nextpos != null && nextpos[1] == 7 && nextpos[0] == 14){this.finished = true;core.draw(this.group[index].split("|")[1].substring(0,i+1));console.log("找到出口",i,this.group[index].split("|")[1],this.group[index].split("|")[1].substring(0,i+1));return;break;}else if(nextpos != null && this.map[nextpos[1]][nextpos[0]] != 1){ // 可以继续走this.currentpointer = nextpos;}else{nextpos = this.currentpointer;}}var arr = this.group[index].split("|");this.group[index] = this.getScore()+"|"+arr[1];},getScore:function(){var diffx = Math.abs(this.currentpointer[0] - this.endpointer[0]);var diffy = Math.abs(this.currentpointer[1] - this.endpointer[1]);this.currentpointer = this.startpointer;return (1/(diffx+diffy+1));},getTotalScore:function(){// 获取当前的所有积分var group = this.group,totalscore = 0;for(var i = 0 ; i < group.length ; i++){var score = group[i].split("|")[0];totalscore += parseFloat(score);}return totalscore;},wheel:function(){//滚轮算法var totalscore = Math.random()*this.getTotalScore(),ctotal = 0,selected = 0;for(var i = 0 ; i < this.grouplen ; i++){var score = this.group[i].split("|")[0];ctotal += parseFloat(score);//console.log(totalscore,ctotal);if(ctotal > totalscore){selected = i;break;}}return this.group[selected];},crossover:function(mum,dad){// num 为字符串 data也为字符串,不带具体的适应分数// 杂交函数if(Math.random() > this.crossrate || mum == dad){// 如果随机数大于杂交率 或者父亲和母亲一直,直接返回return [mum,dad];}var cp = Math.floor(Math.random()*(this.grouplen/2)),child1 = [],child2 = [];for(var i = 0 ; i < cp ;i++){child1.push(mum.charAt(i));child2.push(dad.charAt(i));}for(var i = cp ; i < mum.length ;i++){child1.push(dad.charAt(i));child2.push(mum.charAt(i));}return [child1.join(""),child2.join("")];},mutation:function(bit){// 变异函数var vec = this.toBits(bit).split("");for(var i = 0 ; i < vec.length ; i++){if(Math.random() < this.mutationrate){vec[i] = parseInt(vec[i]) == 0 ? 1 : 0;}}return this.toVec(vec.join(""));},toVec:function(data){var tmp = [],r = [];for(var i = 0 ; i < data.length ; i++){tmp.push(data.charAt(i));if(i%2 != 0){r.push(parseInt(tmp.join(""),2));tmp = [];}}return r.join("");},toBits:function(data){var bits = [];for(var i = 0 ; i < data.length ; i++){var bit = this.toBit(data.charAt(i));bits.push(bit);}return bits.join("");},toBit:function(data){// 转化为二进制switch(parseInt(data)){case 0:return "00";break;case 1:return "01";break;case 2:return "10";break;case 3:return "11";break;default:return "00";break;}},getEl:function(element){return typeof element == "string" ? document.getElementById(element):element;},initmap:function(element){var html = [],map = this.map;for(var i = 0 ; i < map.length ; i++){var row = [];for(var j = 0 ; j < map[i].length ;j++){row.push('<div x='+j+' y='+i+'></div>');}html.push(row.join(""));}//console.log(html);this.getEl(element).innerHTML = html.join("");},pochGroup:function(){},/*** 默认进行几个子代*/start:function(element,epoch){this.initmap(element);this.newGroup();return this;},/***一个时代开始*第一步先更新每个的具体的分数值*第二步渡轮生成新的子代*第三步,新的子代进行杂交和变异*时代结束*/epoch:function(){// 一个时代this.testRoute();if(this.finished){return;}var tmp = [];for(var i = 0 ; i < this.grouplen/2;i++){var mum = this.wheel().split("|")[1],dad = this.wheel().split("|")[1];var a = this.crossover(mum,dad);mum = this.mutation(a[0]);dad = this.mutation(a[1]);tmp.push("0|"+mum);tmp.push("0|"+dad);}this.group = tmp;this.nepoch++;this.count++;console.log("当前时代为"+this.nepoch);//var me = this;if(this.count < 100){core.epoch();}}}core.start("map",1).epoch();?