Machine Learning - Annealing of N-Queens problem

Simulated annealing is a probabilistic technique for approximating the global optimum of a given function. It is also one of the basic algorithms used in Artificial Intelligence.This version is based on Ameya Joshi's's solution written in C++.

Here are the more interesting code segments.

function run( maxLength, initialTemp, finalTemp, alpha, stepsPerChange )
{
    _maxLength = maxLength;

    // Annealing Schedule
    initialTemp = initialTemp || 30.0;
    finalTemp = finalTemp || 0.5;
    alpha = alpha || 0.99;
    stepsPerChange = stepsPerChange || 100;

    var timer = 0;
    var step;
    var hasSolution = false;
    var useNew;
    var accepted;
    var temperature = initialTemp;
    var current = createMember( _maxLength, 0.0 );
    var working = createMember( _maxLength, 0.0 );
    var best = createMember( _maxLength, 100.0 );
    var params = [];

    initializeSolution( current );

    computeEnergy( current );

    copySolution( working, current );

    while( temperature > finalTemp )
    {
        accepted = 0;

        // Monte Carlo Step
        for( step = 0; step < stepsPerChange; step++ )
        {
            useNew = 0;

            tweakSolution( working );
            computeEnergy( working );

            if( working.energy <= current.energy )
            {
                useNew = 1;
            }
            else
            {
                var test = random();
                var delta = working.energy - current.energy;
                var calc = Math.exp( -delta / temperature );

                if( calc > test )
                {
                    accepted++;
                    useNew = 1;
                }
            }

            if( useNew )
            {
                useNew = 0;

                copySolution( current, working );

                if( current.energy < best.energy )
                {
                    copySolution( best, current );

                    hasSolution = true;
                }
            }
            else
            {
                copySolution( working, current );
            }
        }

        timer++;

        params.push( { timer: timer, energy: best.energy, temperature: temperature.toFixed( 10 ), accepted: accepted } );

        temperature *= alpha;
    }

    var solution = newArray2D( _maxLength, _maxLength, " " );

    if( hasSolution )
    {
        for( var i = 0; i < _maxLength; i++ )
        {
            solution[ i ][ best.solution[ i ] ] = 'X';
        }
    }

    return { params: params, solution: solution };
};
                    

Calculate the energy of the passed solution. The energy is the the number of conflicts on the board. Note that only diagonals are checked. The encoding ensures that no vertical or horizontal conflicts are possible.

function computeEnergy( member )
{
    var board = newArray2D( _maxLength, _maxLength, " " );
    var dx = [ -1, 1, -1, 1 ];
    var dy = [ -1, 1, 1, -1 ];

    for( var i = 0; i < _maxLength; i++ )
    {
        board[ i ][ member.solution[ i ] ] = 'Q';
    }

    var conflicts = 0;

    for( var j = 0; j < _maxLength; j++ )
    {
        var x = j;
        var y = member.solution[ j ];

        for( var k = 0; k < 4; k++ )
        {
            var tempX = x;
            var tempY = y;

            while( 1 )
            {
                tempX += dx[ k ];
                tempY += dy[ k ];

                if( (tempX < 0) || (tempX >= _maxLength) || (tempY < 0) || (tempY >= _maxLength) )
                {
                    break;
                }

                if( board[ tempX ][ tempY ] == 'Q' )
                {
                    conflicts++;
                }
            }
        }
    }

    member.energy = Number( conflicts );
}