2016-11-29

遗传算法解决01背包问题

遗传算法

let w: number[] = [2, 2, 6, 5, 4];
let p: number[] = [6, 3, 5, 4, 6];
/**
- 返回一个0到a之间整数
- @param {number} a -整数
- /
  function randInt(a:number):number{
  return Math.round(Math.random()(a+1));
  }
  function randClamp(a,b){
  return randInt(a-b)+a;
  }
  let geneLen=5;
  let max=0;
  /*
- -生物圈
  /
  var biosphere={
  all:[],
  initLen:30,
  /*
  - -初始化
  - /
    init:()=>{
    for(let i=0;i<biosphere.initLen;i++){
```
var temp=[];
for(let j=0;j<geneLen;j++){
    if(Math.random()<0.5){
        temp.push(1);
    }else{
        temp.push(0);
    }  
}
biosphere.all.push(new backpack(temp));
```
    }
    },
    /**
  - -轮盘选择法
  - /
    select:(arr)=>{
    let ran=Math.random();
    let psum=0;
    let index=0;
    while(psum<ran){
```
psum+=arr[index].p;
index+=1;
```
    }
    return index-1;
    },
    /**
  - -清除生命为0的
  - /
    clear:()=>{
    biosphere.all=biosphere.all.filter((x)=>{
```
if(x.life==0){
    return false
}else{return true;}
```
    })
    },
    /**
  - -迭代
  - /
    iteration:()=>{
    biosphere.clear();
    let allValue=0;
    biosphere.all.forEach((x)=>{
```
allValue+=x.value;
```
    })
    let temp=0;
    var arr=biosphere.all.map((x)=>{
```
temp+=x.value;
x.p=temp/allValue;
return x;
```
    })
    
    biosphere.all=[];
    for(let i=0;i<arr.length;i=i+1.5){
```
let index=biosphere.select(arr);
let index2=biosphere.select(arr);
backpack.mating(arr[index],arr[index2])
```
    }
    
    // biosphere.clear();
    
    }
    }
  /**-背包类 */
  class backpack
  {
  gene:number[];
  mutationRate:number=0.05;
  value:number=0;
  weight:number=0;
  life=1;
  MaxWeight=10;
  constructor(gene:number[]){
```
this.gene=gene.map((x)=>{
    if(Math.random()<this.mutationRate){
        if(x===1){
            return 0;
        }else{
            return 1;
        }
    }else{return x;}
});
this.gene.forEach((x,index)=>{
    if(x===1){
        this.value+=p[index];
        this.weight+=w[index];
    }
})

if(this.weight>this.MaxWeight){
    this.life=0;
}else{
    if(this.value>max){max=this.value;}
}
```
  }
  /**
  - 交配函数，需要两个backpa类型，生产2个子代
  - @param {backpack} a -backpack类型
  - @param {backpack} b -backpack类型
  - /
    static mating(a:backpack,b:backpack){
    let start=randInt(a.gene.length);
    let end=randInt(a.gene.length);
    if(end<start){
```
let temp;
temp=end;
end=start;
start=temp;
```
    }
    biosphere.all.push(new backpack(a.gene.slice(0,start).concat(b.gene.slice(start,end).concat(a.gene.slice(end,a.gene.length)))));
    biosphere.all.push(new backpack(b.gene.slice(0,start).concat(a.gene.slice(start,end).concat(b.gene.slice(end,b.gene.length)))))
    a.life=0;
    b.life=0;
    }
    }
    biosphere.init();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    biosphere.iteration();
    console.log(biosphere,max)

动态规划

let w: number[] = [2, 2, 6, 5, 4];
let p: number[] = [6, 3, 5, 4, 6];
let maxW = 10;
function run(w, p, maxW) {

let n = w.length;
let res: number[][]=[];
for(let i=0;i<=n;i++){
    res.push([])
}
w.unshift(0);
p.unshift(0);
for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= maxW; j++) {
        if(i==0){
            res[0][j]=0;
        }else{
            if(w[i]>j){
                res[i][j]=res[i-1][j]
            }else{
                res[i][j]=Math.max((res[i-1][j-w[i]]+p[i]),res[i-1][j])
            }

        }
    }
}
console.table(res);

}
run(w, p, maxW)