タブーサーチ(TS)で解くOneMax問題をJavaScriptで書いてみた

※個人の練習用です。アルゴリズムの正確性は担保しません。
ここでいうTSは、タブーサーチ(Tabu Search)のことです。

タブーサーチ(TS)とは

メタヒューリスティックの探索アルゴリズムの一つである。
TSに関する説明はWikiまたはこちらのレビュー論文に割愛する。

JSで書いてみた

TSは探索アルゴリズムの中でも割とシンプルなものなので、
JSでも簡単に書ける。

// タブーリストの長さを設定
const TABU_LIST_MAX_LENGTH = 7;
// One-Max 問題の長さを設定
const ARRAY_WIDTH = 100; //e.g. 4 = [0, 0, 0, 0]
// One-Max なので値は2種類（0,1)
const VALUE_LENGTH = 2; // 0 || 1
// 最大探索回数
const MAX_COUNT = 100;
// 一回あたりの探索区間
const SEARCH_WIDTH = 1;
// 近隣の数
const NEIGHBORS_LENGTH = 10;
// 初期値生成
const INITIAL_VALUE = setValue(VALUE_LENGTH, ARRAY_WIDTH);

console.log("The max width is: ", ARRAY_WIDTH);
console.log("The first value is: ", INITIAL_VALUE);
console.log("The sum of first value is: ", sum(INITIAL_VALUE));

// FIFO
function fifo(tabuList, newAns){
    if(tabuList.length >= TABU_LIST_MAX_LENGTH){
        tabuList.shift() | tabuList.push(newAns);
    }else{
        tabuList.push(newAns);
    }
    console.log("The new tabu list is: ", tabuList);
    return tabuList;
}

function getMaxFromArray(arr){
    return Math.max.apply(null, arr);
}

function getMaxFromNeighborsArr(neighborsArr){
    maxCallback = (max, cur) => Math.max(max , cur);
    return neighborsArr.map(x=>sum(x)).reduce(maxCallback, -Infinity);
}

function getMaxNeighbor(neighbors){
    maxValue = getMaxFromNeighborsArr(neighbors);
    return neighbors.find(neighbor => sum(neighbor) == maxValue);
}

function getBestFromTabuList(tabuList){
    return getMaxFromArray(tabuList);
}

function getWideRandom(max, width){
    let result = [];
    for(let i=width; i>0; i--){
        let num = getRandom(max);
        if(result.includes(num)){
            i++;
        }else{
            result.push(num);
        }
    }
    return result;
}

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

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

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

function wideToggle(newAns, posArr){
    posArr.forEach(pos => {
        newAns[pos] = toggle(newAns[pos]);
    })
    return newAns;
}

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

function pickNeighbors(currentAns, length){
    let neighbors = [];
    for(let i=length; i>0; i--){
        let neighborArr = Array.from(currentAns);
        let posArr = getWideRandom(ARRAY_WIDTH, SEARCH_WIDTH);
        neighborArr = wideToggle(neighborArr, posArr);
        neighbors.push(neighborArr);
    }
    return neighbors;
}

function pickNeighbor(newAns, neighborsLength){
    neighbors = pickNeighbors(newAns, neighborsLength);
    return getMaxNeighbor(neighbors);
}

function hasValueInTabuList(tabuList, newAns){
    return tabuList.includes(answer => answer == newAns) === true;
}

function compareAnswers(oldAnsArr, newAnsArr, tabuList){
    return sum(newAnsArr) > sum(oldAnsArr) && hasValueInTabuList(tabuList, sum(newAnsArr)) === false;
}

// メイン関数
function find(start){
    let tabuList = [sum(start)];
    let latestAns = Array.from(start);

    for(let i=0;i<MAX_COUNT;i++){
        console.log("Count: ", i);
        let tempNeighbor = pickNeighbor(latestAns, NEIGHBORS_LENGTH);
        console.log("The sum of best neighbor's value is: ", sum(tempNeighbor));

        if(compareAnswers(latestAns, tempNeighbor, tabuList)){
            console.log("Add into tabu list cuz NEW VALUE more then OLD VALUE");
            tabuList = fifo(tabuList, sum(tempNeighbor));
            latestAns = Array.from(tempNeighbor);
        }
    }
    return  getBestFromTabuList(tabuList);
}

// 実行
console.log("the best answer is:",find(INITIAL_VALUE));