Source: methods/Tabu.js

import Result from '../_common/Result.js';
import BufferedReply from '../_common/BufferedReply';

/**
 * Class for solving problems using Tabu Search
 */
export class TabuSolver {
    constructor(workerInterface) {
        this._workerInterface = workerInterface;

        // buffers messages to reduce communication overhead while sending computation progress every cycle
        this._bufferedReply = new BufferedReply(this._workerInterface, 'progressBuffered', 75);
    }

    /**
     * Wrapper for cost function, because Tabu inner cycle starts without a selected state
     * @param  {number} size size of the neighborhood
     * @param  {number} neighborsToCheckRatio > 0 && <= 1 how big part of neighborhood to check
     * @return {array} array with selected neighbors indexes to check
     */
    _getCost(state) {
        if (state === null) return -Infinity;
        return this.problem.evaluateMaximizationCost(state);
    }

    /**
     * Returns neighborhood to check
     * @param  {number} size size of the neighborhood
     * @param  {number} neighborsToCheckRatio > 0 && <= 1 how big part of neighborhood to check
     * @return {array} array with selected neighbors indexes to check
     */
    _generateNeighborhood(size, neighborsToCheckRatio) {
        var nbhSize = Math.round(size * neighborsToCheckRatio);
        var nbh = [];
        for (var i = 0; i < size; i++) {
            nbh.push(i);
        }
        while (nbh.length > nbhSize) {
            var randomIndex = Math.round(Math.random() * (nbh.length - 1));
            nbh.splice(randomIndex, 1);
        }
        return nbh;
    }

    /**
     * Comparison of position in queue
     * @param  {array} queue array with configurations
     * @param  {class} c1 configuration to compare 1
     * @param  {class} c2 configuration to compare 2
     * @return {number} compared indexes of configurations in queue 1: c1 < c2, 2: c2 > c1, 0: not found
     */
    _compareIndexesOf(queue, c1, c2) {
        for (var i in queue) {
            if (queue[i].equals(c1)) return 1;
            if (queue[i].equals(c2)) return -1;
        }
        return 0;
    }

    /**
     * Tabu state check
     * @param  {object} set indexed tabu states
     * @param  {class} configuration instance of a problem configuration
     * @return {boolean} contains
     */
    _containsSearch(set, configuration) {
        if (set[configuration.toString()]) {
            // console.log(this.counter);
            this.tabuCounter++;
        }
        return set[configuration.toString()];
    }

    /**
     * Method contains Tabu Search algorithm
     * @param  {number} iterationLimit number of iterations
     * @param  {number} neighborsToCheckRatio how many of all neighbour states to check
     * @param  {number} tabuSize length of tabu states queue
     * @param  {number} tabuSizeShort length of tabu changes queue
     * @param  {boolean} randomStart starting state is default (false) or random (true)
     * @return {class} final configuration
     */
    _process(iterationLimit, neighborsToCheckRatio, tabuSize, tabuSizeShort, randomStart) {
        var state = this.problem.getConfiguration(randomStart);     // initial state
        var stateCost = this._getCost(state);                       // initial state cost
        var sBest = state;                                          // initial best found state
        var sBestCost = stateCost;                                  // initial best found state cost
        var tabuStates = [];            // Queue
        var tabuStatesSearch = {};      // HashSet
        var tabuChanges = [];           // Queue

        // tabu iterations
        for (var n = 0; n < iterationLimit; n++) {
            this._bufferedReply.addMessageWithAutoFlush(this.problem.transformMaximizationToRealCost(stateCost));

            // init for this loop
            var bestCandidate = null;
            var bestCandidateCost = this._getCost(bestCandidate);
            var bestCandidateIndex = -1;
            var tabuBestCandidate = null;
            var tabuBestCandidateCost = this._getCost(tabuBestCandidate);
            var tabuBestCandidateIndex = -1;

            var neighborhood = this._generateNeighborhood(state.getSize(), neighborsToCheckRatio);

            // checking neighbours
            for (var i = 0; i < neighborhood.length; i++) {
                this.counter++;

                var sCandidate = state.getNeighbour(neighborhood[i]);
                var sCandidateCost = this._getCost(sCandidate);

                // check change for tabu and if it is tabu, check if we dont miss the best found state
                if (tabuChanges.indexOf(i) !== -1 && sCandidateCost < sBestCost) continue;

                // is current candidate better than best candidate in this step?
                if (sCandidateCost >= bestCandidateCost) {
                    // is current candidate tabu?
                    if (!this._containsSearch(tabuStatesSearch, sCandidate)) {
                        bestCandidate = sCandidate;
                        bestCandidateCost = sCandidateCost;
                        bestCandidateIndex = i;
                    }
                    // if it is, remember the least tabu candidate
                    else if (this._compareIndexesOf(tabuStates, sCandidate, tabuBestCandidate) > 0) {
                        tabuBestCandidate = sCandidate;
                        tabuBestCandidateCost = sCandidateCost;
                        tabuBestCandidateIndex = i;
                    }
                }
            }

            // all candidates are tabu
            if (bestCandidateIndex === -1) {
                // there are non even tabu candidates, we have nowhere to go
                if (tabuBestCandidateIndex === -1) {
                    // console.log("-- no candidates --");
                }
                else {
                    state = tabuBestCandidate;
                    stateCost = tabuBestCandidateCost;
                    bestCandidateIndex = tabuBestCandidateIndex;
                }
            }
            else {
                // normal situation, not tabu state
                state = bestCandidate;
                stateCost = bestCandidateCost;
            }

            // keep best state found up to date
            if (stateCost > sBestCost) {
                sBest = state;
                sBestCost = stateCost;
            }

            // update tabu lists
            tabuStates.push(state);
            tabuStatesSearch[state.toString()] = true;
            tabuChanges.push(bestCandidateIndex);

            // remove oldest from tabu if its full
            if (tabuStates.length > tabuSize) {
                delete tabuStatesSearch[tabuStates.shift().toString()];
            }
            if (tabuChanges.length > tabuSizeShort) {
                tabuChanges.shift();
            }
        }
        // added flush to send remaining progress data before terminating
        this._bufferedReply.addMessage(this.problem.transformMaximizationToRealCost(stateCost)).flush();

        return sBest;
    }

    /**
     * Main function method, solves the problem using simulated annealing
     * @param  {Problem} problem problem instance
     * @param  {object} params problem parameters
     * @return {Result} Result class containing data of the run
     */
    solve(problem, {iterationLimit, neighborsToCheck, tabuSize, tabuSizeShort, randomStart}) {
        this.problem = problem;
        this.counter = 0;
        this.tabuCounter = 0;

        // initial message to set up the interface for the computation
        this._workerInterface.reply('init', { numberOfIterations: iterationLimit });

        var best = this._process(iterationLimit, neighborsToCheck / 100, tabuSize, tabuSizeShort, randomStart);

        // console.log('tabu checks:', this.tabuCounter);

        // return Result class managing data format
        return new Result(
            problem.getResult(best), 
            this.problem.transformMaximizationToRealCost(this.problem.evaluateMaximizationCost(best)), 
            this.counter
        );
    }
}