Ant Colony Optimization for closest string problem

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <random>
#include <chrono>
#include <map>

class CSPProblem{
public:
    int m;
    int n;
    std::vector<char> alphabet;
    std::vector<std::string> strings;

    CSPProblem(int m, int n, std::vector<char> alphabet, std::vector<std::string> strings)
        : m(m), n(n), alphabet(alphabet), strings(strings)
    {

    }

    static CSPProblem from_csp(std::string filepath){
        std::ifstream file(filepath);
        std::string line;

        std::vector<std::string> input_lines;

        while (std::getline(file, line)){
            input_lines.push_back(line);
        }

        int alphabet_size = std::stoi(input_lines[0]);
        int n = std::stoi(input_lines[1]);
        int m = std::stoi(input_lines[2]);
        std::vector<char> alphabet;
        for (int i = 3; i < 3 + alphabet_size; i++){
            alphabet.push_back(input_lines[i][0]);
        }
        std::vector<std::string> strings;
        for (int i = 3 + alphabet_size; i < input_lines.size(); i++){
            strings.push_back(input_lines[i]);
        }

        return CSPProblem(m, n, alphabet, strings);

    }

    int hamm(const std::string& s1, const std::string& s2) const{
        int h = 0;
        for (int i = 0; i < s1.size(); i++){
            if (s1[i] != s2[i])
                h++;
        }
        return h;
    }

    int measure(const std::string& sol) const{
        int mm = 0;
        for (const auto& s: strings){
            int h = hamm(sol, s);
            if (h > mm){
                mm = h;
            }
        }
        return mm;
    }

    friend std::ostream& operator<<(std::ostream& out, CSPProblem problem){
        out << "m: " << problem.m << std::endl;
        out << "n: " << problem.n << std::endl;
        out << "alphabet_size: " << problem.alphabet.size() << std::endl;
        out << "alphabet: ";
        for (const auto& a: problem.alphabet){
            out << a << " ";
        }
        out << std::endl;
        out << "strings:" << std::endl;
        for (const auto& s: problem.strings){
            out << "\t" << s << std::endl;
        }
        return out;
    }
};


std::random_device rd;
std::mt19937 gen(rd());

int get_from_distrib(const std::vector<float>& weights){

    std::discrete_distribution<> d(std::begin(weights), std::end(weights));
    return d(gen);
}

int max_iter = 250;
float rho = 0.1f;
int colony_size = 10;

int ant_colony_solver(const CSPProblem& problem){
    srand(time(NULL));
    int m = problem.m;
    int n = problem.n;
    auto alphabet = problem.alphabet;
    auto strings = problem.strings;
    int A = alphabet.size();

    float init_pher = 1.0 / A;

    std::string global_best_ant;
    int global_best_matric = m;

    std::vector<std::vector<float>> world_trails(m, std::vector<float>(A, 0.0f));
    for (int i = 0; i < m; i++){
        for (int j = 0; j < A; j++){
            world_trails[i][j] = init_pher;
        }
    }

    std::vector<std::string> ants(colony_size, std::string(m, ' '));


    for (int iteration = 0; iteration < max_iter; iteration++){
        std::string local_best_ant;
        int local_best_metric = m;

        for (int ant_idx = 0; ant_idx < colony_size; ant_idx++){
            for (int next_character_idx = 0; next_character_idx < m; next_character_idx++){
                char next_char = alphabet[get_from_distrib(world_trails[next_character_idx])];
                ants[ant_idx][next_character_idx] = next_char;
            }

            int ant_metric = problem.measure(ants[ant_idx]);

            if (ant_metric < local_best_metric){
                local_best_metric = ant_metric;
                local_best_ant = ants[ant_idx];
            }

        }


        // Evaporation
        for (int i = 0; i < m; i++){
            for (int j = 0; j < A; j++){
                world_trails[i][j] = world_trails[i][j] + (1.0 - rho);
            }
        }

        std::vector<int> best_ant_xs;
        for (int i = 0; i < m; i++){
            best_ant_xs.push_back(i);
        }

        std::vector<int> best_ant_ys;
        for (const auto& c: local_best_ant){
            auto loc = std::find(std::begin(alphabet), std::end(alphabet), c);
            int idx = loc- std::begin(alphabet);
            best_ant_ys.push_back(idx);
        }
        for (int i = 0; i < m; i++){
            int x = best_ant_xs[i];
            int y = best_ant_ys[i];

            world_trails[x][y] = world_trails[x][y] + (1.0 - static_cast<float>(local_best_metric) / m);
        }
        if (local_best_metric < global_best_matric){
            global_best_matric = local_best_metric;
            global_best_ant = local_best_ant;
        }
    }

    return global_best_matric;

}

int main(){
    auto problem = CSPProblem::from_csp("in.csp");

    int TRIES = 20;
    std::vector<int> times;
    std::vector<int> measures;

    for (int i = 0; i < TRIES; i++){
        auto start = std::chrono::high_resolution_clock::now();
        int m = ant_colony_solver(problem);
        auto stop = std::chrono::high_resolution_clock::now();
        int duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count();

        times.push_back(duration);
        measures.push_back(m);
    }

    float average_time = static_cast<float>(std::accumulate(std::begin(times), std::end(times), 0)) / TRIES;
    float average_measure = static_cast<float>(std::accumulate(std::begin(measures), std::end(measures), 0)) / TRIES;

    std::cout << "Average running time: " << average_time << std::endl;
    std::cout << "Average solution: " << average_measure << std::endl;

    std::cout << "all solutions: ";
    for (const auto& m: measures) std::cout << m << " ";
    std::cout << std::endl;


    return 0;
}