|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <ctime> #include <cstdlib> using namespace std; const string TARGET = "HELLO WORLD"; const int POPULATION_SIZE = 100; const int STRING_LENGTH = TARGET.length(); const double MUTATION_RATE = 0.01; const int MAX_GENERATIONS = 1000; // Function to generate a random candidate string string generateRandomString() { string result; for (int i = 0; i < STRING_LENGTH; ++i) { result += static_cast<char>(rand() % 26 + 'A'); } return result; } // Function to calculate fitness of a candidate string int calculateFitness(const string& candidate) { int fitness = 0; for (int i = 0; i < STRING_LENGTH; ++i) { if (candidate[i] == TARGET[i]) { ++fitness; } } return fitness; } // Function to perform crossover between two parent strings string crossover(const string& parent1, const string& parent2) { string child; int crossoverPoint = rand() % STRING_LENGTH; for (int i = 0; i < STRING_LENGTH; ++i) { child += (i < crossoverPoint) ? parent1[i] : parent2[i]; } return child; } // Function to perform mutation on a candidate string void mutate(string& candidate) { for (int i = 0; i < STRING_LENGTH; ++i) { if (static_cast<double>(rand()) / RAND_MAX < MUTATION_RATE) { candidate[i] = static_cast<char>(rand() % 26 + 'A'); } } } // Main Genetic Algorithm function void geneticAlgorithm() { vector<string> population(POPULATION_SIZE); vector<int> fitness(POPULATION_SIZE); // Initialize random seed srand(static_cast<unsigned int>(time(nullptr))); // Generate initial population for (int i = 0; i < POPULATION_SIZE; ++i) { population[i] = generateRandomString(); } int generation = 0; while (generation < MAX_GENERATIONS) { // Calculate fitness for the population int bestFitness = 0; string bestCandidate; for (int i = 0; i < POPULATION_SIZE; ++i) { fitness[i] = calculateFitness(population[i]); if (fitness[i] > bestFitness) { bestFitness = fitness[i]; bestCandidate = population[i]; } } // Output the best candidate cout << "Generation " << generation << ": " << bestCandidate << " (Fitness: " << bestFitness << ")" << endl; if (bestFitness == STRING_LENGTH) { cout << "Target string reached!" << endl; break; } // Generate new population vector<string> newPopulation; while (newPopulation.size() < POPULATION_SIZE) { // Select parents int parent1Index = rand() % POPULATION_SIZE; int parent2Index = rand() % POPULATION_SIZE; // Perform crossover and mutation string child = crossover(population[parent1Index], population[parent2Index]); mutate(child); newPopulation.push_back(child); } population = newPopulation; ++generation; } } int main() { geneticAlgorithm(); return 0; } |
Explanation:
- Constants:
TARGET: The target string to be matched by the genetic algorithm.POPULATION_SIZE: Number of candidate strings in each generation.STRING_LENGTH: Length of the target string.MUTATION_RATE: Probability of mutation in each gene (character).MAX_GENERATIONS: Maximum number of generations to run the algorithm.
- Generating Random Strings (
generateRandomString):- Creates a random string of uppercase letters. This represents a candidate solution.
- Calculating Fitness (
calculateFitness):- Measures how close a candidate string is to the target string. Fitness is the number of characters that match the target.
- Crossover (
crossover):- Combines parts of two parent strings to create a child string. A crossover point is randomly chosen to split the parents.
- Mutation (
mutate):- Randomly alters characters in a string based on the mutation rate.
- Genetic Algorithm (
geneticAlgorithm):- Initializes a population of random strings.
- Evaluates fitness and identifies the best candidate in each generation.
- Creates a new population using crossover and mutation.
- Stops if the target string is found or the maximum number of generations is reached.
- Main Function (
main):- Calls the
geneticAlgorithmfunction to start the optimization process.
- Calls the
Possible Enhancements:
- Elitism: Preserve a few of the best candidates from each generation to ensure the best solutions are not lost.
- Diverse Crossover Methods: Experiment with different crossover techniques.
- Enhanced Mutation: Implement more sophisticated mutation strategies.
- User Input: Allow users to specify the target string, population size, and other parameters.