基因演算法 - 猜數字

by sj82516

JavaScript

/*
*  簡單的基因演算法實踐
*  參考內容：http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3
*  題目：隨機生成 0,1組成的數字列(預設長度為50)，如果採用暴力解需 2的50次方 才能解決，故用基因演算法嘗試在特定時間內找出最佳解
*  		 可打開console看log
*  Warning：這需要大量運算，所以瀏覽器話卡住一段時間
*/

// 單體，也就是個別解
class Individual {
	constructor(size){
    	this.size = size
        // 隨機生成基因列，ex. [1,0,1,....]
        this._genes = Array(size).fill(0).map( _ => + (Math.random()>0.5))
        // 暫存適應度
        this._fitness = 0
    }
    
    getFitness(){
    	if (this._fitness == 0) {
            this._fitness = Fitness.calcFitness(this);
        }
        return this._fitness;
    }
    
    // 設定單個基因
    setGene(pos, val){
    	this._genes[pos] = val
    }
    // 取得定單個基因
    getGene(pos){
    	return this._genes[pos]
    }
    
    // 取得基因長度
    size(){
    	return this._genes.length
    }
}

// 管理全部的individual
class Population {
	// 定義靜態變數
	static get GENE_SIZE() {
    	return 50
    }
    
    // 判斷是否為初始化，如果是則需要隨機產生單體，反之則否
	constructor(size, init){
   		this._size = size
    	this._individualList = Array(size).fill(0).map( _ => init?new Individual(this.constructor.GENE_SIZE):{})
    }
    
    // 找出適應度最好的基因
    getFitnessIndividual(){
    	return this._individualList.reduce(function(a, b) {
      		return a.getFitness() > b.getFitness() ? a:b
        })
    }
    
    size(){
    	return this._size
    }
    
    getIndividual(pos){
    	return this._individualList[pos]
    }
    setIndividual(pos, id){
    	this._individualList[pos] = id
    }
}

// Fintness計算
class Fitness{
    static setSolution(solution){
    	this._solution = solution
    }
    
    static calcFitness(id){
    	let score = 0
        this._solution.forEach((ele, i) => {
        	if(id.getGene(i) == ele) score ++
        })
        return score
    }
}

class GA {
	/* 定義靜態變數 */
    // A/B母體的基因遺傳機率(選A還選B)
	static get UNIFORM_RATE(){
     	return 0.5
    }
    // 基因突變的機率
    static get MUTATION_RATE(){
    	return 0.015
    }
    // 篩選法中的子群體數
   ...