焼きなまし法(SA)で解くOneMax問題をJavaScriptで書いてみた

※個人の練習用です。アルゴリズムの正確性は担保しません。

焼きなまし法(SA)とは

焼きなまし法（Simulated Annealing, SA）とは、大域的最適化問題への汎用の乱択アルゴリズムである。
詳細は割愛する。

JSで書いてみた

SAは探索アルゴリズムの中でも結構シンプルなものなので、
JSでも簡単にかける。

let width = 100;
let num = 2; 
let maxCount = 100;
let length = Math.pow(num,width);
let start = setValue(num, width);

function getRandom(max){
    return Math.floor(Math.random()*Math.floor(max));
}

function setValue(num, width){
    let result = []
    for(i=0; i< width; i++){
        result.push(getRandom(num));
    };
    return result;
}

function toggle(num){
    return num == 0 ? 1 : 0;
}

function sum(valueArr){
    return valueArr.reduce(function(sum, val){
            return sum + val;
        }, 0);
}

function e(bestSum, newAnsSum, tem){
    res = newAnsSum - bestSum;
    r = Math.random();
    exp =Math.exp(res/tem);
    return r < exp;
}

function find(start){
    console.log("start on:", start);
    let best = start;
    let newAns = Array.from(start);
    for(i=maxCount; i>0;i--){
        let pos = getRandom(4);
        newAns[pos] = toggle(newAns[pos]);
        if(sum(best) < sum(newAns) || e(sum(best), sum(newAns), i)){
            best = Array.from(newAns);
        }else{
            newAns = Array.from(best);
        }
    }
    return best;
}

console.log("the best answer is:",find(start));