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