fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <cmath>
  5. #include <random>
  6. #include <algorithm>
  7.  
  8. struct Customer{
  9.     double x;
  10.     double y;
  11.     double size;
  12. };
  13.  
  14. struct Shop{
  15.     double x;
  16.     double y;
  17.     double cost;
  18.     double capacity;
  19.  
  20. };
  21.  
  22.  
  23. static double distance(const std::pair<double, double> &from, const std::pair<double, double> &to){
  24.     return std::sqrt((from.first - to.first) * (from.first - to.first) + (from.second - to.second) * (from.second - to.second));
  25. }
  26.  
  27. class Population{
  28. public:
  29.  
  30.     Population(size_t population_sz, const std::vector<Customer> &custom, const std::vector<Shop> &sh, const std::vector<std::vector<double>> &d): population_size(population_sz), customer_size(custom.size()), shop_size(sh.size()), shops(sh), customers(custom), dist_matrix(d){
  31.         population.resize(population_sz, std::vector<int>(customer_size));
  32.         std::random_device rnd_device;
  33.         std::mt19937 mersenne_engine {rnd_device()};
  34.         int sz = static_cast<int>(shop_size - 1);
  35.         std::uniform_int_distribution<int> dist {0, sz};
  36.         for (int i = 0; i < population_sz; ++i){
  37.             auto gen = [&dist, &mersenne_engine](){
  38.                 return dist(mersenne_engine);
  39.             };
  40.             std::vector<int> vec(customer_size);
  41.             std::generate(std::begin(vec), std::end(vec), gen);
  42.             population[i] = vec;
  43.         }
  44.         population_candidates = population;
  45.     }
  46.     double count_one_fitness(size_t index){
  47.         double fitness = 0.0;
  48.         std::vector<double> open(shop_size, 0.0);
  49.         for (size_t i = 0; i < customer_size; ++i){
  50.             int shop = population[index][i];
  51.             if (open[shop] < 0.0000001){
  52.                 fitness += shops[shop].cost;
  53.  
  54.             }
  55.             fitness += dist_matrix[shop][i];
  56.             open[shop] += customers[i].size;
  57.         }
  58.         for (size_t i = 0; i < shop_size; ++i){
  59.             double delta = shops[i].capacity - open[i];
  60.             if (delta < 0){
  61.                 fitness += delta * fitness * 0.3;
  62.             }
  63.  
  64.         }
  65.         return fitness;
  66.     }
  67.  
  68.     double one_fitness(std::vector<int>& sol){
  69.         double fitness = 0.0;
  70.         std::vector<double> open(shop_size, 0.0);
  71.         for (size_t i = 0; i < customer_size; ++i){
  72.             int shop = sol[i];
  73.             if (open[shop] < 0.0000001){
  74.                 fitness += shops[shop].cost;
  75.  
  76.             }
  77.             fitness += dist_matrix[shop][i];
  78.             open[shop] += customers[i].size;
  79.         }
  80.         for (size_t i = 0; i < shop_size; ++i){
  81.             double delta = shops[i].capacity - open[i];
  82.             if (delta < 0){
  83.                 fitness += delta * fitness * 0.3;
  84.             }
  85.  
  86.         }
  87.         return fitness;
  88.     }
  89.  
  90.     std::vector<int> breeding_one_iteration(size_t parent1, size_t parent2, const std::vector<size_t> &indexes){
  91.         std::vector<int> children1 = population[parent1];
  92.         std::vector<int> children2 = population[parent2];
  93.         for (unsigned long index : indexes){
  94.             children1[index] = population[parent2][index];
  95.             children2[index] = population[parent1][index];
  96.         }
  97.         double f1 = one_fitness(children1);
  98.         double f2 = one_fitness(children2);
  99.         if (f1 < f2){
  100.             return children1;
  101.         }
  102.         return children2;
  103.  
  104.     }
  105.  
  106.     std::vector<int> mutation_one_iteration(size_t parent, const std::vector<size_t> &indexes, const std::vector<int> &new_meaning) {
  107.         std::vector<int> children = population[parent];
  108.         for (int i = 0; i < indexes.size(); ++i) {
  109.             children[indexes[i]] = new_meaning[i];
  110.         }
  111.  
  112.         return children;
  113.     }
  114.  
  115.     std::vector<std::vector<int>> breeding(size_t number_candidates){
  116.         std::vector<size_t> ind(customer_size);
  117.         for (int i = 0; i < customer_size; ++i){
  118.             ind[i] = i;
  119.         }
  120.  
  121.         std::vector<std::vector<int>> new_population(number_candidates);
  122.         std::random_device rd;
  123.         std::mt19937 gen(rd());
  124.         std::uniform_int_distribution<size_t> distrib(0, population_size - 1);
  125.         for (int i = 0; i < number_candidates; ++i){
  126.             size_t p1 = distrib(gen);
  127.             size_t p2 = distrib(gen);
  128.             std::shuffle(ind.begin(), ind.end(), gen);
  129.             new_population[i] = breeding_one_iteration(p1, p2,  std::vector<size_t> { ind.begin(), ind.begin() + customer_size / 2 + 1 });
  130.         }
  131.         return new_population;
  132.     }
  133.  
  134.     std::vector<std::vector<int>> mutations(size_t number_candidates) {
  135.         std::vector<std::vector<int>> new_population(number_candidates);
  136.         std::random_device rd;
  137.         std::mt19937 gen(rd());
  138.         std::vector<size_t> ind(customer_size);
  139.         for (int i = 0; i < customer_size; ++i){
  140.             ind[i] = i;
  141.         }
  142.         std::mt19937 mersenne_engine {rd()};
  143.         int sz = static_cast<int>(shop_size - 1);
  144.         std::uniform_int_distribution<int> dist {0, sz};
  145.         std::uniform_int_distribution<size_t> distrib(0, population_size - 1);
  146.         for (int i = 0; i < number_candidates; ++i) {
  147.             size_t p = distrib(gen);
  148.             auto gen = [&dist, &mersenne_engine](){
  149.                 return dist(mersenne_engine);
  150.             };
  151.             std::vector<int> vec(customer_size / 4 + 1);
  152.             std::generate(std::begin(vec), std::end(vec), gen);
  153.             new_population[i] = mutation_one_iteration(p, std::vector<size_t> { ind.begin(), ind.begin() + customer_size / 4 + 1}, vec);
  154.         }
  155.         return new_population;
  156.     }
  157.  
  158.  
  159.     void one_iteration_genetic_algorithm(){
  160. //        хочется в каждой итерации генерить разное количество новых кандидатов с помощью селекции/мутации
  161.  
  162.  
  163.     }
  164.  
  165.  
  166. private:
  167.     size_t customer_size;
  168.     size_t shop_size;
  169.     size_t population_size;
  170.     std::vector<std::vector<int>> population;
  171.     std::vector<Shop> shops;
  172.     std::vector<Customer> customers;
  173.     std::vector<std::vector<int>> population_candidates;
  174.     std::vector<std::vector<double>> dist_matrix;
  175. };
  176.  
  177. int main() {
  178.     std::ifstream in;
  179.     int n;
  180.     int m;
  181.     in.open("/home/katfresal/CLionProjects/Facility location/data/");
  182.     in >> n >> m;
  183.     std::vector<Shop> shops(n);
  184.     std::vector<Customer> customers(m);
  185.  
  186.     for (int i = 0; i < n; ++i){
  187.         in >> shops[i].cost >>shops[i].capacity >> shops[i].x >> shops[i].y;
  188.     }
  189.  
  190.     for (int i = 0; i < m; ++i){
  191.         in >> customers[i].size >> customers[i].x >> customers[i].y;
  192.     }
  193.  
  194.     in.close();
  195.     std::vector<std::vector<double>> dist_matrix(n, std::vector<double>(m));
  196.     for (int i = 0; i < n; ++i){
  197.         for (int j = 0; j < m; ++j){
  198.             dist_matrix[i][j] = distance({shops[i].x, shops[i].y}, {customers[j].x, customers[j].y});
  199.         }
  200.     }
  201.  
  202.  
  203. }
  204.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vTqJoB
language:
C++ (gcc 8.3)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!