Genetic Algorithm for Optimizing Cabinet Placement

/*
 * CODE BY FPERSON
 
 * Algorytm genetyczny do optymalizacji rozmieszczenia szaf w korytarzu
 * Program znajduje optymalne rozmieszczenie szaf minimalizujące całkowitą drogę przenoszenia dokumentów
 
 */

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

class GeneticAlgorithm {
private:
    int populationSize;
    int numCabinets;
    std::vector<std::vector<int>> frequencyMatrix;
    std::vector<std::string> population;
    std::mt19937 rng;

    std::string generateRandomSolution() {
        std::string solution;
        for (int i = 0; i < numCabinets; i++) {
            solution += ('a' + i);
        }
        std::shuffle(solution.begin(), solution.end(), rng);
        return solution;
    }

    int calculateFitness(const std::string& solution) {
        int totalDistance = 0;
        for (int i = 0; i < numCabinets; i++) {
            for (int j = 0; j < numCabinets; j++) {
                int freq = frequencyMatrix[i][j];
                if (freq > 0) {
                    int pos1 = solution.find('a' + i);
                    int pos2 = solution.find('a' + j);
                    totalDistance += freq * std::abs(pos1 - pos2);
                }
            }
        }
        return totalDistance;
    }

    std::string crossover(const std::string& parent1, const std::string& parent2) {
        if (static_cast<double>(rand()) / RAND_MAX < 0.5) return parent1;
        
        int start = rand() % numCabinets;
        int end = rand() % numCabinets;
        if (start > end) std::swap(start, end);

        std::string child(numCabinets, ' ');
        std::vector<bool> used(numCabinets, false);

        for (int i = start; i <= end; i++) {
            child[i] = parent1[i];
            used[parent1[i] - 'a'] = true;
        }

        int j = (end + 1) % numCabinets;
        for (int i = 0; i < numCabinets; i++) {
            if (!used[parent2[i] - 'a']) {
                while (child[j] != ' ') {
                    j = (j + 1) % numCabinets;
                }
                child[j] = parent2[i];
                j = (j + 1) % numCabinets;
            }
        }

        return child;
    }

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

public:
    GeneticAlgorithm(int n, const std::vector<std::vector<int>>& matrix) 
        : numCabinets(n), frequencyMatrix(matrix), populationSize(100), 
          rng(std::random_device{}()) {
        for (int i = 0; i < populationSize; i++) {
            population.push_back(generateRandomSolution());
        }
    }

    std::string solve(int generations = 100) {
        for (int gen = 0; gen < generations; gen++) {
            std::sort(population.begin(), population.end(),
                [this](const std::string& a, const std::string& b) {
                    return calculateFitness(a) < calculateFitness(b);
                });

            std::vector<std::string> newPopulation;
            
            int eliteSize = populationSize / 10;
            for (int i = 0; i < eliteSize; i++) {
                newPopulation.push_back(population[i]);
            }

            while (newPopulation.size() < populationSize) {
                int idx1 = rand() % (populationSize / 2);
                int idx2 = rand() % (populationSize / 2);
                
                std::string child = crossover(population[idx1], population[idx2]);
                mutate(child);
                newPopulation.push_back(child);
            }

            population = std::move(newPopulation);
        }

        std::sort(population.begin(), population.end(),
            [this](const std::string& a, const std::string& b) {
                return calculateFitness(a) < calculateFitness(b);
            });
        return population[0];
    }

    void printSolution(const std::string& solution) {
        std::cout << "\nZnalezione rozwiązanie:\n";
        std::cout << "Rozmieszczenie szaf w pokojach (litera = szafa, pozycja = numer pokoju): " << solution << "\n";
        std::cout << "Całkowita droga do przejścia: " << calculateFitness(solution) << "\n";
    }
};

// Funkcja do czyszczenia bufora wejściowego
void clearInputBuffer() {
    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

// Funkcja do bezpiecznego wczytywania liczb całkowitych
int getIntInput(const std::string& prompt, int min, int max) {
    int value;
    while (true) {
        std::cout << prompt;
        if (std::cin >> value) {
            if (value >= min && value <= max) {
                clearInputBuffer();
                return value;
            }
            std::cout << "Wartość musi być między " << min << " a " << max << ".\n";
        } else {
            std::cout << "Nieprawidłowe dane. Proszę wprowadzić liczbę.\n";
            clearInputBuffer();
        }
    }
}

int main() {
    std::cout << "Program do optymalizacji rozmieszczenia szaf w pokojach\n";
    std::cout << "===================================================\n\n";

    // Pobieranie liczby szaf/pokoi
    int n = getIntInput("Podaj liczbę szaf/pokoi (1-26): ", 1, 26);

    // Tworzenie i wypełnianie macierzy częstości
    std::vector<std::vector<int>> frequencyMatrix(n, std::vector<int>(n, 0));
    
    std::cout << "\nWprowadź macierz częstości przenoszenia dokumentów:\n";
    std::cout << "Dla każdej pary szaf (i,j) podaj liczbę przejść między nimi.\n";
    std::cout << "Macierz powinna być symetryczna (przejścia w obie strony).\n\n";

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            char szafa1 = 'A' + i;
            char szafa2 = 'A' + j;
            int freq = getIntInput("Liczba przejść między szafą " + 
                                 std::string(1, szafa1) + " i " + 
                                 std::string(1, szafa2) + ": ", 0, 100);
            frequencyMatrix[i][j] = freq;
            frequencyMatrix[j][i] = freq;  // Macierz symetryczna
        }
    }

    // Wyświetlanie wprowadzonej macierzy
    std::cout << "\nWprowadzona macierz częstości:\n";
    std::cout << "   ";
    for (int i = 0; i < n; i++) {
        std::cout << char('A' + i) << "  ";
    }
    std::cout << "\n";
    
    for (int i = 0; i < n; i++) {
        std::cout << char('A' + i) << "  ";
        for (int j = 0; j < n; j++) {
            std::cout << frequencyMatrix[i][j] << "  ";
        }
        std::cout << "\n";
    }

    // Uruchamianie algorytmu genetycznego
    int generations = getIntInput("\nPodaj liczbę generacji (10-1000): ", 10, 1000);
    
    GeneticAlgorithm ga(n, frequencyMatrix);
    std::string bestSolution = ga.solve(generations);
    ga.printSolution(bestSolution);

    return 0;
}