Genetic Algorithm for Optimizing Cabinet Placement

/*

CODE BY IRENEUSZ A.

Program implementuje algorytm genetyczny do rozwiązania problemu optymalnego rozmieszczenia szaf w korytarzu.

Problem:
- Mamy n pokoi ułożonych szeregowo wzdłuż korytarza
- W każdym pokoju należy umieścić jedną szafę (jest n szaf)
- Znana jest częstość przenoszenia dokumentów między szafami (macierz powiązań)
- Celem jest znalezienie takiego układu szaf, który minimalizuje całkowitą drogę do przejścia

Reprezentacja rozwiązania:
- Każde rozwiązanie to ciąg liter (a,b,c,...), gdzie:
  * pozycja litery oznacza numer pokoju (1,2,3,...)
  * litera oznacza konkretną szafę
- Przykład dla 3 pokoi: "abc" oznacza szafę A w pokoju 1, B w pokoju 2, C w pokoju 3

Parametry algorytmu:
- Rozmiar populacji: 100 osobników
- Liczba pokoleń: 1000
- Prawdopodobieństwo mutacji: 0.1
- Prawdopodobieństwo krzyżowania: 0.8

*/

#include <iostream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>
#include <ctime>

class GeneticAlgorithm {
private:
    // Parametry algorytmu
    const int POPULATION_SIZE = 100;
    const int MAX_GENERATIONS = 1000;
    const double MUTATION_RATE = 0.1;
    const double CROSSOVER_RATE = 0.8;
    
    int numCabinets;  // liczba szaf/pokoi
    std::vector<std::vector<int>> frequencyMatrix;  // macierz częstości przenoszenia
    std::vector<std::string> population;  // populacja rozwiązań
    std::mt19937 rng;  // generator liczb losowych

public:
    GeneticAlgorithm(int n, const std::vector<std::vector<int>>& freq) 
        : numCabinets(n), frequencyMatrix(freq) {
        rng.seed(std::time(nullptr));
        initializePopulation();
    }

    // Inicjalizacja początkowej populacji
    void initializePopulation() {
        std::string base;
        for (int i = 0; i < numCabinets; i++) {
            base += ('a' + i);
        }

        for (int i = 0; i < POPULATION_SIZE; i++) {
            std::string solution = base;
            std::shuffle(solution.begin(), solution.end(), rng);
            population.push_back(solution);
        }
    }

    // Obliczanie funkcji przystosowania (fitness) dla danego rozwiązania
    int calculateFitness(const std::string& solution) {
        int totalDistance = 0;
        for (int i = 0; i < numCabinets; i++) {
            for (int j = 0; j < numCabinets; j++) {
                int pos1 = i;
                int pos2 = j;
                int cab1 = solution[i] - 'a';
                int cab2 = solution[j] - 'a';
                totalDistance += frequencyMatrix[cab1][cab2] * abs(pos1 - pos2);
            }
        }
        return -totalDistance;  // ujemna wartość, bo szukamy minimum
    }

    // Selekcja turniejowa
    std::string tournamentSelection() {
        int tournamentSize = 3;
        std::string best = population[rand() % POPULATION_SIZE];
        int bestFitness = calculateFitness(best);

        for (int i = 1; i < tournamentSize; i++) {
            std::string candidate = population[rand() % POPULATION_SIZE];
            int candidateFitness = calculateFitness(candidate);
            if (candidateFitness > bestFitness) {
                best = candidate;
                bestFitness = candidateFitness;
            }
        }
        return best;
    }

    // Krzyżowanie (Order Crossover - OX)
    std::pair<std::string, std::string> crossover(const std::string& parent1, const std::string& parent2) {
        if (static_cast<double>(rand()) / RAND_MAX >= CROSSOVER_RATE) {
            return {parent1, parent2};
        }

        int start = rand() % numCabinets;
        int end = rand() % numCabinets;
        if (start > end) std::swap(start, end);

        std::string child1 = std::string(numCabinets, 'x');
        std::string child2 = std::string(numCabinets, 'x');

        // Kopiowanie środkowej sekcji
        for (int i = start; i <= end; i++) {
            child1[i] = parent1[i];
            child2[i] = parent2[i];
        }

        // Uzupełnianie pozostałych pozycji
        auto fillRemaining = [](const std::string& parent, const std::string& otherParent, 
                              std::string& child, int start, int end) {
            int childPos = (end + 1) % numCabinets;
            int parentPos = (end + 1) % numCabinets;
            
            while (std::count(child.begin(), child.end(), 'x') > 0) {
                if (child[childPos] == 'x') {
                    while (std::find(child.begin(), child.end(), parent[parentPos]) != child.end()) {
                        parentPos = (parentPos + 1) % numCabinets;
                    }
                    child[childPos] = parent[parentPos];
                }
                childPos = (childPos + 1) % numCabinets;
            }
        };

        fillRemaining(parent2, parent1, child1, start, end);
        fillRemaining(parent1, parent2, child2, start, end);

        return {child1, child2};
    }

    // Mutacja przez zamianę
    void mutate(std::string& solution) {
        if (static_cast<double>(rand()) / RAND_MAX < MUTATION_RATE) {
            int pos1 = rand() % numCabinets;
            int pos2 = rand() % numCabinets;
            std::swap(solution[pos1], solution[pos2]);
        }
    }

    // Główna pętla algorytmu
    std::string solve() {
        std::string bestSolution = population[0];
        int bestFitness = calculateFitness(bestSolution);

        for (int generation = 0; generation < MAX_GENERATIONS; generation++) {
            std::vector<std::string> newPopulation;

            while (newPopulation.size() < POPULATION_SIZE) {
                std::string parent1 = tournamentSelection();
                std::string parent2 = tournamentSelection();

                auto [child1, child2] = crossover(parent1, parent2);
                
                mutate(child1);
                mutate(child2);

                newPopulation.push_back(child1);
                if (newPopulation.size() < POPULATION_SIZE) {
                    newPopulation.push_back(child2);
                }
            }

            population = newPopulation;

            // Aktualizacja najlepszego rozwiązania
            for (const auto& solution : population) {
                int fitness = calculateFitness(solution);
                if (fitness > bestFitness) {
                    bestFitness = fitness;
                    bestSolution = solution;
                }
            }
        }

        return bestSolution;
    }
};

// Przykład użycia
int main() {
    // Przykładowa macierz częstości dla 3 szaf
    std::vector<std::vector<int>> frequencyMatrix = {
        {0, 5, 2},
        {5, 0, 3},
        {2, 3, 0}
    };

    GeneticAlgorithm ga(3, frequencyMatrix);
    std::string bestSolution = ga.solve();
    
    std::cout << "Najlepsze znalezione rozwiązanie: " << bestSolution << std::endl;
    return 0;
}