Genetic Algorithm Simulation Gaming Project in C++

Projects Inventory

3 months ago

#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;
}

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 geneticAlgorithm function to start the optimization process.

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.

Explanation:

Possible Enhancements:

Related Posts: