How to implement the "evaluate()" and "successor()" method of the Slope Rise algorithm?

Question

I’m trying to implement the algorithm Hill Climb (Hill Climbing) and this algorithm should return the sequence of cities considered good (with the shortest distance between cities) the problem of the traveling salesman based on an adjacency matrix, however, I’m having difficulty in implementing the methods avaliar() and sucessor(), I don’t know what approach I should take to make these methods work as expected.

The implementation is being in Javascript:

let matrizAdjacente = [
    [0, 1, 2, 3, 4, 5],
    [2, 0, 5, 2, 1, 1],
    [1, 8, 0, 2, 3, 4],
    [2, 2, 1, 0, 6, 3],
    [4, 2, 3, 1, 0, 4],
    [3, 1, 3, 2, 2, 0]
];

let sequenciaCidades = [1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6];

let solucaoInicial = function() {
    return [4, 5, 1, 6, 3, 2];
}

let avaliar = function(estado) {

}

let sucessor = function(atual, novo) {

}

let hillClimbing = function() {
    let novo = null;
    let atual = solucaoInicial();
    let valorAvaliadoAtual = avaliar(atual);
    let valorAvaliadoNovo = 0;

    while (1) {
        novo = sucessor(atual, novo);
        valorAvaliadoNovo = avaliar(novo);

        if (valorAvaliadoNovo < valorAvaliadoAtual) {
            atual = novo;
            valorAvaliadoAtual = valorAvaliadoAtual;
        } else break;
    }

    return atual;
}

This algorithm consists of examining the successors of the current state and proceeding to the first state that is larger than the current one. However, it is necessary to implement the methods avaliar() and sucessor(), the successor method will make an exchange between states and the evaluate method will return a value given a sequence.

Question

So how could I implement the method avaliar() and sucessor() of the Slope Rise algorithm?

Answer 1

If I understand correctly, the method sucessor() gives you a list of cities to be evaluated by the method avaliar(), that should return the cost of your solution, that is, the distance that would be covered if we visit the cities in a given order and if this distance is better than the one we currently have, we will use this new sequence as our optimal solution, that way, everything that avaliar() evaluate need to do is to go through the list summing the distances of the matrix D of distances (or adjacency, as you prefer) and

D[x][y] = distância entre x e y 

Suppose you have the sequence [2,1,3], its total distance is therefore D[2][1]+D[1][3] that is, the cost of going from City 2 to City 1 and from City 1 to City 3, this logic can be implemented with a loop above the list of cities returned by sucessor().

The work of the method sucessor() is to use a previous list of cities to generate a new candidate solution, this can be done in several ways, depending on the specification of the problem, as it is the PCV, the simplest suggestion is to add the first unseen city you find to the bottom of the list as long as it can be reached from the last city, suppose you have 6 city (1 to 6) and your list is something like this: [4,2,3], the next city not visited is the city 1, if in its headquarters D[3][1] > 0 (that is, there is a path of 3 up to 1) your new list would be [4,2,3,1], if there is no city without visiting, you check whether you can return to the first city (problem restriction).