Genetic Algorithm for Optimizing Cabinet Placement
user_6919294
c_cpp
2 months ago
7.2 kB
8
Indexable
/* * 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; }
Editor is loading...
Leave a Comment