c++ Valgrind: Address 0x0 is not stack'd, malloc'd or (recently) free'd

Question

I am learning a bit of programming and I am trying to code an Ant Colony algorithm for QAP, the problem is that sometimes I get segmentation fault and when I use valgrind it tells me "Address 0x0 is not stack'd, malloc'd or (recently) free'd". This is the code:

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>  //ifstream
#include <string>
#include <sstream>
#include <vector>
#include <utility> //pair
#include <iostream>
#include <algorithm> //shuffle
#include <random> //default_random_engine
#include <chrono> //chrono::system_clock
#include <cstdlib> // rand
#include <unistd.h>
#include <csignal>
using namespace std;

sig_atomic_t volatile done = 0;
void game_over(int) { done = 1; }

int funCosto(int dim,vector<int> sol,vector<int> dist, vector<int> flujo){
    int costo = 0;
    for (int i = 0; i<dim;i++){
        for (int j = i+1; j<dim;j++){
            // El costo es la * del valor de los flujos por la permutacion de las distancias 
            costo += flujo[dim*i+j] * dist[dim*(sol[i]-1) + (sol[j]-1)]; 
        }
    }
    return costo*2; //La matriz es simétrica
}

int buscarLista(vector<int> lista, int elemento, int dim){
    int aux = 0;
    for (int i = 0; i < dim; i++){
        if (lista[i] == elemento){aux = 1;}
    }
    return aux;
}

vector<int> localSearch(int dim,vector<int> sol, vector<int> dist, vector<int> flujo){

    vector<int> solActual(dim), solAux(dim);
    solActual = sol;
    int mejorCosto = funCosto(dim,solActual,dist,flujo);
    int costoActual, mejorCostoAnterior;

    do{
        mejorCostoAnterior = mejorCosto; // para determinar que se llegó a un óptimo local
        for (int i = 0; i < dim; i++){
            for (int j = i+1; j < dim; j++){
                solAux = solActual;
                solAux[i] = solActual[j];
                solAux[j] = solActual[i]; //intercambiamos dos elementos
                /*Importante, hay que optimizar el cálculo del costo de los vecinos*/
                costoActual = funCosto(dim,solAux,dist,flujo);
                if (costoActual<mejorCosto){
                    break;
                }
            }
            if (costoActual < mejorCosto){
                mejorCosto = costoActual; //se actualiza el mejor costo
                solActual = solAux; //se efectua el movimiento
                break; 
            }
        }
    } while (mejorCosto < mejorCostoAnterior); //se detiene cuando ya no hay mejoría

    return solActual;
}

pair<int,vector<int>> antColony(int numAnts, int dim, vector<int> dist, vector<int> flujo){

    done = 0;
    std::signal(SIGALRM, game_over);
    alarm(300);

    vector<vector<int>> hormigas(numAnts, vector<int>(dim));
    vector<vector<int>> hormigasNuevas(numAnts, vector<int>(dim));
    vector<vector<double>> feromonas(dim, vector<double>(dim));
    vector<int> mejorSol, mejorSolNueva;
    double mejorCosto, mejorCostoNuevo, totalFer, prob, auxProb, probAcum = 0 ;
    int numSwaps = dim/3;  // número de cambios que va a hacer cada hormiga en cada iteración
    random_device rd; // obtener un número aleatorio de hardware
    mt19937 eng(rd()); // semilla para el generador
    uniform_int_distribution<> disInt(0,dim-1);
    uniform_real_distribution<> disReal(0,1);
    int prim, seg, aux, contadorRep, sinMejoria = 0; //indices 
    int inten = 1; //la intensificación está prendida al comienzo

    for (int i = 1; i <= dim; i++){
        hormigas[0][i-1] = i;
    }
    for (int j = 1; j < numAnts; j++){
        hormigas[j] = hormigas[0];
    }
    //obtener una semilla basada en el tiempo
    for (int k = 0; k < numAnts; k++){
        unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
        shuffle(hormigas[k].begin(),hormigas[k].end(), default_random_engine(seed));
    } 

    for (int i = 0; i < numAnts; i++){ //aplica local Search para las soluciones aleatorias
        hormigas[i] = localSearch(dim,hormigas[i],dist,flujo);
    }

    mejorCosto = funCosto(dim,hormigas[0],dist,flujo);
    mejorSol = hormigas[0];
    for (int i = 1; i < numAnts; i++){
        if (funCosto(dim,hormigas[i],dist,flujo) < mejorCosto){
            mejorCosto = funCosto(dim,hormigas[i],dist,flujo);
            mejorSol = hormigas[i];
        }
    }
    for (int i = 0; i<dim; i++){
        for (int j = 0 ; j<dim; j++){
            feromonas[i][j] = 1.0/(100*mejorCosto);
        }
    }

    for (int z = 0; z < 1; z++){ //máximo número de iteraciones

        for (int i = 0; i < numAnts; i++ ){

            hormigasNuevas[i] = hormigas[i];

            for (int j = 0; j < numSwaps; j++){
                prim = disInt(eng);
                auxProb = disReal(eng);
                seg = -1;
                probAcum = 0;
                do{
                    seg++;
                    if (seg == prim){seg++;}
                    totalFer = 0; //limpiamos para esta iteración
                    for (int k = 0; k < dim; k++){
                        if (k != prim){
                            totalFer += feromonas[prim][hormigasNuevas[i][k]-1] + feromonas[k][hormigasNuevas[i][prim]-1];
                        }
                    }    
                    //construimos la probabilidad con la que es aceptado el cambio segun las feromonas
                    prob = (feromonas[prim][hormigasNuevas[i][seg]-1]+feromonas[seg][hormigasNuevas[i][prim]-1]) / totalFer;
                    probAcum += prob;
                }while ((auxProb > probAcum) && (seg < dim));

                if (seg == dim){seg--;}

                aux = hormigasNuevas[i][prim];
                hormigasNuevas[i][prim] = hormigasNuevas[i][seg];
                hormigasNuevas[i][seg] = aux;

            }
            //mejoramos la solución modificada por la hormiga
            hormigasNuevas[i] = localSearch(dim,hormigasNuevas[i],dist,flujo);
        }

        //contadorRep = 0;
        //intensificación
        for (int a = 0; a < numAnts; a++){
            if (inten == 1){
                if (funCosto(dim,hormigasNuevas[a],dist,flujo) < funCosto(dim,hormigas[a],dist,flujo)){
                    hormigas[a] = hormigasNuevas[a];
                }
                else{ contadorRep++;} //para contar cuantas veces se queda con la respuesta anterior
            }
            else{
                hormigas[a] = hormigasNuevas[a];
            }
        }

        //if (contadorRep == numAnts){inten = 0;} //apaga la intensificación

        mejorCostoNuevo = funCosto(dim,hormigas[0],dist,flujo);
        for (int b = 1; b < numAnts; b++){
            if (funCosto(dim,hormigas[b],dist,flujo) < mejorCostoNuevo){
                mejorCostoNuevo = funCosto(dim,hormigas[b],dist,flujo);
                mejorSolNueva = hormigas[b];
            }
        }

        if (mejorCostoNuevo < mejorCosto){
            //si se consigue una mejor solucíón
            mejorCosto = mejorCostoNuevo;
            mejorSol = mejorSolNueva;
            inten = 1;
            sinMejoria = 0;
        }

        //actualiación de la matriz de feromonas
        for (int c = 0; c < dim; c++){
            for (int d = 0; d < dim; d++){ //Evaporación
                feromonas[c][d] = 0.9*feromonas[c][d];
            }
        }

        for (int e = 0; e < dim; e++){//reforzamos la mejor solución
            feromonas[e][mejorSol[e]-1] = feromonas[e][mejorSol[e]-1] + 0.1/mejorCosto;
        }

        //diversificación
        if (sinMejoria > dim/2){

            hormigas[0] = mejorSol; //se queda la mejor solución hasta el momento
            //se vuelve a inicializar las hormigas
            for (int k = 1; k < numAnts; k++){
                unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
                shuffle(hormigas[k].begin(),hormigas[k].end(), default_random_engine(seed));
            } 

            for (int i = 0; i < numAnts; i++){ //aplica local Search para las soluciones aleatorias
                hormigas[i] = localSearch(dim,hormigas[i],dist,flujo);
            }

            mejorCosto = funCosto(dim,hormigas[0],dist,flujo);
            mejorSol = hormigas[0];
            for (int i = 1; i < numAnts; i++){
                if (funCosto(dim,hormigas[i],dist,flujo) < mejorCosto){
                    mejorCosto = funCosto(dim,hormigas[i],dist,flujo);
                    mejorSol = hormigas[i];
                }
            }

            //renovar la matriz de feromonas
            for (int i = 0; i<dim; i++){
                for (int j = 0 ; j<dim; j++){
                    feromonas[i][j] = 1.0/(100*mejorCosto);
                }
            }
        }
        sinMejoria++;
    }

    pair <int,vector<int>> pairSol = make_pair (mejorCosto,mejorSol);
    return pairSol; 

}

int main (int argc, char* argv[]) {

    vector<int> resultados(10);
    for (int i = 0; i < 10; i++){

        clock_t startTime = clock();
        ifstream file(argv[1]);
        int dim;  //dimensiones de las matrices
        file >> dim;
        vector<int> suc(dim*dim); //matriz con los flujos entre las sucursales
        vector<int> loc(dim*dim); //matriz con las distancias de las localidades
        pair <int,vector<int>> pairSol; //tiene el costo de la busqueda y la permutación

        //guardar la matriz de distancia
        for (int i = 0; i < dim; i++){ 
            for (int j = 0; j < dim; j++) {
                file >> suc[dim*i+j];
            }
        }

        //guardar la matriz de flujos
        for (int i = 0; i < dim; i++){ 
            for (int j = 0; j < dim; j++) {
                file >> loc[dim*i+j];
            }
        }

        pairSol = antColony(10,dim,loc,suc);
        resultados[i] = pairSol.first;
        cout << pairSol.first << endl;

        for (int i = 0; i < dim; i++){
            cout << pairSol.second[i] << " ";
        }
        cout << endl;

        cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;
    }

    int total = 0;
    for (int j = 0; j<10; j++){
        total += resultados[j];
    }

    cout << endl << "El promedio de de las soluciones es: " <<endl;
    cout << total/10 << endl;

    return 0;
} 

Valgrind gives me this:

Invalid read of size 4 at 0x804B331: main (antColony.cpp:269) Address 0x0 is not stack'd, malloc'd or (recently) free'd

Process terminating with default action of signal 11 (SIGSEGV) Access not within mapped region at address 0x0 at 0x804B331: main (antColony.cpp:269)

I am using this file:

20

 0 87 14  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
87  0  0 82 57  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
14  0  0  0  0 68  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0 82  0  0  0  0 19 18 38 47  0  0  0  0  0  0  0  0  0  0
 0 57  0  0  0  0  0  0  0  0 91  0  0  0  0  0  0  0  0  0
 0  0 68  0  0  0  0  0  0  0  0 77  0  0  0  0  0  0  0  0
 0  0  0 19  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0 18  0  0  0  0  0  0  0  0  6  0  0  0  0  0  0  0
 0  0  0 38  0  0  0  0  0  0  0  0  0 75  0  0  0  0  0  0
 0  0  0 47  0  0  0  0  0  0  0  0  0  0 73 52  0  0  0  0
 0  0  0  0 91  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0 77  0  0  0  0  0  0  0  0  0  0 51  0  0  0
 0  0  0  0  0  0  0  6  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0 75  0  0  0  0  0  0  0  0 93  0  0
 0  0  0  0  0  0  0  0  0 73  0  0  0  0  0  0  0  0 84  0
 0  0  0  0  0  0  0  0  0 52  0  0  0  0  0  0  0  0  0 40
 0  0  0  0  0  0  0  0  0  0  0 51  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0 93  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0 84  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 40  0  0  0  0

0 4 7 7 4 6 3 7 1 7 8 7 2 9 8 2 9 3 4 3
4 0 8 1 7 9 8 7 6 5 1 3 1 4 4 2 7 6 3 5
7 8 0 5 7 9 1 6 3 2 9 8 4 8 7 7 4 3 7 1
7 1 5 0 3 1 9 9 7 1 6 6 1 1 2 2 4 2 7 8
4 7 7 3 0 9 9 6 9 4 1 8 2 9 8 6 1 9 2 6
6 9 9 1 9 0 7 6 9 2 3 1 4 1 9 5 3 3 7 3
3 8 1 9 9 7 0 3 7 3 5 1 9 4 6 4 7 4 9 6
7 7 6 9 6 6 3 0 7 1 6 7 3 9 4 1 8 4 9 1
1 6 3 7 9 9 7 7 0 6 1 5 7 6 5 3 4 9 8 1
7 5 2 1 4 2 3 1 6 0 6 3 9 3 3 6 4 1 8 6
8 1 9 6 1 3 5 6 1 6 0 6 3 8 2 4 8 1 9 6
7 3 8 6 8 1 1 7 5 3 6 0 8 2 7 6 4 5 4 1
2 1 4 1 2 4 9 3 7 9 3 8 0 4 4 2 5 6 4 9
9 4 8 1 9 1 4 9 6 3 8 2 4 0 3 2 8 7 2 8
8 4 7 2 8 9 6 4 5 3 2 7 4 3 0 4 3 3 8 4
2 2 7 2 6 5 4 1 3 6 4 6 2 2 4 0 8 5 9 9
9 7 4 4 1 3 7 8 4 4 8 4 5 8 3 8 0 1 2 7
3 6 3 2 9 3 4 4 9 1 1 5 6 7 3 5 1 0 1 1
4 3 7 7 2 7 9 9 8 8 9 4 4 2 8 9 2 1 0 4
3 5 1 8 6 3 6 1 1 6 6 1 9 8 4 9 7 1 4 0

The error comes from this lines near the end:

    for (int i = 0; i < dim; i++){
        cout << pairSol.second[i] << " ";
    }

Where I am trying to print the solution vector.

I don't understand the problem with the memory this is generating. This is more confusing because sometimes it works perfectly. If someone could explain it to me I would be grateful.

Thanks in anticipation for your help!

Answer 1

It looks like problem in this part of the code:

mejorCostoNuevo = funCosto(dim,hormigas[0],dist,flujo);
for (int b = 1; b < numAnts; b++){
    if (funCosto(dim,hormigas[b],dist,flujo) < mejorCostoNuevo){
        mejorCostoNuevo = funCosto(dim,hormigas[b],dist,flujo);
        mejorSolNueva = hormigas[b];
    }
}

if (mejorCostoNuevo < mejorCosto){
    //si se consigue una mejor solucíón
    mejorCosto = mejorCostoNuevo;
    mejorSol = mejorSolNueva;
    inten = 1;
    sinMejoria = 0;
}

In the loop you have condition

    if (funCosto(dim,hormigas[b],dist,flujo) < mejorCostoNuevo){

And next after it you have

if (mejorCostoNuevo < mejorCosto){

mejorSol gets assigned when mejorCostoNuevo is greater than result of funCosto. But then you are checking if mejorCostoNuevo is less than mejorCosto. Shouldn't these two conditions be in correspondednce?
Changing second condition to

if (mejorCostoNuevo > mejorCosto){

stopped producing errors for me. Anyway if condition in for loop is not true and it mejorCostoNuevo is less than mejorCosto, then you have mejorSol of zero size and thus the error.

Answer 2

I have debugged your program a bit, and found that when the error happens, the pairSol.second is actually empty.

The only way I see this could happen is if mejorSolNueva is never assigned a value, but then assignment mejorSol = mejorSolNueva happens.