src/main.cc
/*
 * ACS with the Selective Pheromone Memory version
 */
ACS with the Selective Pheromone Memory version
ACS with the Selective Pheromone Memory version
static std::map<std::string, pj> 
run_acs_spm(const vector<vector<double>> &dist_matrix,
             const vector<vector<double>> &heuristic_matrix,
             const vector<vector<uint32_t>> &nn_lists,
             mt19937 &rng,
             ACSParams &params,
             StopCondition *stop_cond,
             uint32_t bucket_size) {
    assert(params.initial_pheromone_ > 0.0);
    const uint32_t dimension = dist_matrix.size();
    const bool is_symmetric = true;
    SelectivePheromoneMemory pheromone_memory(dimension + 1, bucket_size, is_symmetric);
    pheromone_memory.set_all(params.initial_pheromone_);
    double total_sol_calc_time = 0;
    Ant global_best;
    global_best.value_ = numeric_limits<double>::max();
    auto start = std::chrono::steady_clock::now();
    uint32_t best_found_iteration = 0; 
    for (stop_cond->init(); !stop_cond->is_reached(); stop_cond->next_iteration()) {
        vector<Ant> ants{ params.ants_count_ };
        std::uniform_int_distribution<> random_node(0, (int)dimension-1);
        for (auto &ant : ants) {
            ant_init(ant, dimension, (uint32_t)random_node(rng));
        }
        auto sol_calc_start = std::chrono::steady_clock::now();
        for (uint32_t j = 0; j+1 < dimension; ++j) {
            for (auto &ant : ants) {
                auto node = acs_calc_move(ant, heuristic_matrix, heuristic_matrix, nn_lists, params.q0_, rng, &pheromone_memory);
                ant_move_to(ant, node);
                local_pheromone_update(pheromone_memory, dist_matrix,
                                       params.beta_,
                                       ant, j, params.phi_, params.initial_pheromone_);
            }
        }
        auto sol_calc_end = std::chrono::steady_clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(sol_calc_end - sol_calc_start);
        total_sol_calc_time += elapsed.count();
        for (auto &ant : ants) {
            assert(is_valid_route(ant.visited_, dimension));
            ant.value_ = eval_route(dist_matrix, ant.visited_);
        }
        uint32_t best_index = 0;
        for (uint32_t j = 1; j < ants.size(); ++j) {
            if (ants[j].value_ < ants[best_index].value_) {
                best_index = j;
            }
        }
        auto &local_best = ants[best_index];
        if (global_best.value_ > local_best.value_) {
            global_best = local_best;
            best_found_iteration = stop_cond->get_iteration();
        }
        global_pheromone_update(pheromone_memory, dist_matrix, params.beta_, global_best, params.rho_);
    }
    auto end = std::chrono::steady_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    auto total_calc_time = elapsed.count() / 1.0e6;
    cout << "Global best ant: " << global_best << endl;
    std::map<std::string, pj> out;
    out["iterations_made"] = pj( (int64_t)stop_cond->get_iteration() );
    out["best_value"] = pj( global_best.value_ );
    out["best_solution"] = pj( sequence_to_string(global_best.visited_.begin(),
                                                  global_best.visited_.end()) );
    out["best_found_iteration"] = pj( (int64_t)best_found_iteration );
    out["sol_calc_time_msec"] = pj( total_sol_calc_time / (1000.0 * stop_cond->get_iteration()) );
    out["total_sol_calc_time"] = pj( total_calc_time );
    out["spm_mem_hits"] = pj( (int64_t)pheromone_memory.get_mem_hits() );
    out["spm_mem_misses"] = pj( (int64_t)pheromone_memory.get_mem_misses() );
    return out;
}
static std :: map < std :: string , pj > run_acs_spm ( const vector < vector < double > > & dist_matrix , const vector < vector < double > > & heuristic_matrix , const vector < vector < uint32_t > > & nn_lists , mt19937 & rng , ACSParams & params , StopCondition * stop_cond , uint32_t bucket_size ) { assert ( params . initial_pheromone_ > 0.0 ) ; const uint32_t dimension = dist_matrix . size ( ) ; const bool is_symmetric = true ; SelectivePheromoneMemory pheromone_memory ( dimension + 1 , bucket_size , is_symmetric ) ; pheromone_memory . set_all ( params . initial_pheromone_ ) ; double total_sol_calc_time = 0 ; Ant global_best ; global_best . value_ = numeric_limits < double > :: max ( ) ; auto start = std :: chrono :: steady_clock :: now ( ) ; uint32_t best_found_iteration = 0 ; for ( stop_cond -> init ( ) ; ! stop_cond -> is_reached ( ) ; stop_cond -> next_iteration ( ) ) { vector < Ant > ants { params . ants_count_ } ; std :: uniform_int_distribution < > random_node ( 0 , ( int ) dimension - 1 ) ; for ( auto & ant : ants ) { ant_init ( ant , dimension , ( uint32_t ) random_node ( rng ) ) ; } auto sol_calc_start = std :: chrono :: steady_clock :: now ( ) ; for ( uint32_t j = 0 ; j + 1 < dimension ; ++ j ) { for ( auto & ant : ants ) { auto node = acs_calc_move ( ant , heuristic_matrix , heuristic_matrix , nn_lists , params . q0_ , rng , & pheromone_memory ) ; ant_move_to ( ant , node ) ; local_pheromone_update ( pheromone_memory , dist_matrix , params . beta_ , ant , j , params . phi_ , params . initial_pheromone_ ) ; } } auto sol_calc_end = std :: chrono :: steady_clock :: now ( ) ; auto elapsed = std :: chrono :: duration_cast < std :: chrono :: microseconds > ( sol_calc_end - sol_calc_start ) ; total_sol_calc_time += elapsed . count ( ) ; for ( auto & ant : ants ) { assert ( is_valid_route ( ant . visited_ , dimension ) ) ; ant . value_ = eval_route ( dist_matrix , ant . visited_ ) ; } uint32_t best_index = 0 ; for ( uint32_t j = 1 ; j < ants . size ( ) ; ++ j ) { if ( ants [ j ] . value_ < ants [ best_index ] . value_ ) { best_index = j ; } } auto & local_best = ants [ best_index ] ; if ( global_best . value_ > local_best . value_ ) { global_best = local_best ; best_found_iteration = stop_cond -> get_iteration ( ) ; } global_pheromone_update ( pheromone_memory , dist_matrix , params . beta_ , global_best , params . rho_ ) ; } auto end = std :: chrono :: steady_clock :: now ( ) ; auto elapsed = std :: chrono :: duration_cast < std :: chrono :: microseconds > ( end - start ) ; auto total_calc_time = elapsed . count ( ) / 1.0e6 ; cout << " " << global_best << endl ; std :: map < std :: string , pj > out ; out [ " " ] = pj ( ( int64_t ) stop_cond -> get_iteration ( ) ) ; out [ " " ] = pj ( global_best . value_ ) ; out [ " " ] = pj ( sequence_to_string ( global_best . visited_ . begin ( ) , global_best . visited_ . end ( ) ) ) ; out [ " " ] = pj ( ( int64_t ) best_found_iteration ) ; out [ " " ] = pj ( total_sol_calc_time / ( 1000.0 * stop_cond -> get_iteration ( ) ) ) ; out [ " " ] = pj ( total_calc_time ) ; out [ " " ] = pj ( ( int64_t ) pheromone_memory . get_mem_hits ( ) ) ; out [ " " ] = pj ( ( int64_t ) pheromone_memory . get_mem_misses ( ) ) ; return out ; }
ACS with the Selective Pheromone Memory version
ACS with the Selective Pheromone Memory version
// Calc time for all iterations /**
         * Calc time needed to create single solution by each ant
         * Count also local pheromone update because it is calculated
         * similarly in the GPU version of the algorithm.
         */