小玩意，利用遗传算法解决迷宫有关问题
小玩意，利用遗传算法解决迷宫问题
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 class="box'+map[i][j]+'" 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();