Cultural Algorithm (CA)

The Cultural Algorithm, developed by the Reynolds, can be considered as extension of the conventional genetic algorithm where in addition to the population component there is a knowldege component (belief space). This belief space is divided into distinct categories which represent different domains of knowledge that population has of the search space. After each iteration the belief space is updated by the best individuals of the population. As in standard GA the best individuals are determined based on the output given by the fitness function. The CA has been sucessfully applied to various optimization problems, social simulation, and real-parameter optimization.
There are several belief space categories and these are:

• Normative knowldege - Each individual in the population has desirble value ranges i.e. the acceptable behaviour for indivuals in population.
• Domain specific knowledge - the information about the domain of the cultural algorithm the problem is applied to.
• Situation knowldege - Examples of important events (sucessfull or un-successfull solutions)
• Temporal knowledge - history of the search space. Patterns of the search process.
• Spatial knowledge - Information about the topography of the search space.

The Pseudocode for CA consist of:

1. Create initial population
2. Create the initial belief space (domain specific knowledge, normative value-ranges)
3. Repeat until termination
1. Perform actions of the individuals in the search space
2. Application of the fintess function to each individual to determine its quality.
3. Parents selection for reproduction
4. Genome alteration of the offspring with belief space (application of the influece function)
5. Update belief space by using the accept function. The individuals affect the belief space

Simple example of Cultural Algorithm

In this example we will use SphereFunction as the optimization function which is a standard optimization benchmark. We will create the culture algorithm that will maintain population of solutions, evaluate them using fitness function, and evolve them thorugh 10 generations. In CA the cultural pool will be created which will consist of 20% of population members i.e. population members with their fitness. Regarding the evolution process, the mutations procedure will be created and applied to the cultural pool only. The worst individuals in the population will be replaced with offspring from the cultural pool. At each generation of CA the best fintess value will be shown, and when the solution is found the algorithm will print out the best solution.

What is the sphere function?

The sphere function is one of many test functions used in literature. What is interesting about the sphere function is that sphere function has \(d\) local minimum values and one global minimum value. The function is continuous, convex and unimodal. In general form sphere function can be written as: $$ f(\vec{x}) = \sum_{i=1}^d x_i^2 $$ where \(d\) represented the number of dimensions. This function is usually evaluated on the hypercube $$ x_i \in [-5.12, 5.12]\quad i = 1,...,d. $$ The first step is to load required libraries and in this example we will need random and numpy library.

import random
import numpy as np

The next step is to create sphere function which will be named the Objective function. This function will take the argument x and return sum x**2.

def ObjectiveFunction(x):
    return sum([xi**2 for xi in x])

The CA function must execute the following tasks when called i.e.:

• Initialize population
• In every generation after population initialization
1. Evaluate each population member
2. Sort population by fitness in ascending order
3. Select the top individuals (elite) to form the cultural pool
4. Mutate the cultural pool
5. Replace the worst individuals in the generation
• After final generation is reached, return the best solution

def culture_algorithm(population_size, num_generations, mutation_rate):
    # Initialize population with random solutions
    population = [[random.uniform(-5.12, 5.12) for _ in range(5)] for _ in range(population_size)]

    for generation in range(num_generations):
        # Evaluate the fitness of each individual in the population
        fitness_values = [ObjectiveFunction(individual) for individual in population]
        # Sort population by fitness in ascending order
        sorted_population = [x for _, x in sorted(zip(fitness_values, population))]
        # Select the top individuals (elite) to form the cultural pool
        cultural_pool = sorted_population[:int(0.2 * population_size)]
        # Mutate the cultural pool
        mutated_cultural_pool = []
        for individual in cultural_pool:
            mutated_individual = [gene + random.uniform(-mutation_rate, mutation_rate) for gene in individual]
            mutated_cultural_pool.append(mutated_individual)
        # Replace the worst individuals in the population with mutated cultural pool members
        population[-len(cultural_pool):] = mutated_cultural_pool
        # Print the best fitness value in this generation
        best_fitness = min(fitness_values)
        print(f"Generation {generation}: Best Fitness = {best_fitness}")
    # Return the best solution found
    best_solution = sorted_population[0]
    return best_solution         
        

import random 
import numpy as np
import matplotlib.pyplot as plt 


def ObjectiveFunction(x):
    return sum([xi ** 2 for xi in x])


def culture_algorithm(population_size, num_generations, mutation_rate):
    # Initialize population with random solutions
    population = [[random.uniform(-5.12, 5.12) for _ in range(5)] for _ in range(population_size)]

    for generation in range(num_generations):
        # Evaluate the fitness of each individual in the population
        fitness_values = [ObjectiveFunction(individual) for individual in population]

        # Sort population by fitness in ascending order
        sorted_population = [x for _, x in sorted(zip(fitness_values, population))]

        # Select the top individuals (elite) to form the cultural pool
        cultural_pool = sorted_population[:int(0.2 * population_size)]

        # Mutate the cultural pool
        mutated_cultural_pool = []
        for individual in cultural_pool:
            mutated_individual = [gene + random.uniform(-mutation_rate, mutation_rate) for gene in individual]
            mutated_cultural_pool.append(mutated_individual)

        # Replace the worst individuals in the population with mutated cultural pool members
        population[-len(cultural_pool):] = mutated_cultural_pool

        # Print the best fitness value in this generation
        best_fitness = min(fitness_values)
        print(f"Generation {generation}: Best Fitness = {best_fitness}")

    # Return the best solution found
    best_solution = sorted_population[0]
    return best_solution

if __name__ == "__main__":
    population_size = 10
    num_generations = 50
    mutation_rate = 0.2

    best_solution = culture_algorithm(population_size, num_generations, mutation_rate)
    print(f"Best Solution: {best_solution}")
    print(f"Objective Value: {ObjectiveFunction(best_solution)}")
        

After runnign the previous python script the following output is obtained.

    Best Solution: [0.35661109290376036, 2.466585366674988, 0.20604667178098163, -0.32230058911876297, 2.0542073501743348]
    Objective value: 10.577315580885783
    

Although we had obtained the minimum value it is not a global minimum it is just the minimum value obtained after 50 generations. So CA parameters have to be tuned in order to reach the global minimum. First we will try increasing the population, then number of generations and finline tweak the mutation rate.

Increasing the population size

In this case we will increase the population size from 10 up to 1000. So we will execute the CA with population size 10, 20, 50, 100, 200, 500, and 1000. Meanwhile the number of generation will be equal to 50, and the mutation rate will be kept at 0.2. The results are listed in the following table.

Run	1	2	3	4	5	6	7
Population size	10	20	50	100	200	500	1000
Number of generations	50
Mutation rate	0.2
Lowest Fitness Value	3.946	12.37	9.76	2.789	2.869	0.891	0.272

Increasing the number of generations

Run	1	2	3	4	5	6	7
Number of generations	10	20	50	100	200	500	1000
Population size	1000
Mutation rate	0.2
Lowest Fitness Value	1.873	1.86	0.505	0.416	0.487	0.464	0.246

Increasing the mutation rate

In this case we are ceeping constant number of generations to 1000 and constant population size of 1000 since in previous investigation using those two values generate minimum fintess function value.

Run	1	2	3	4	5	6	7
Mutation rate	0.05	0.1	0.15	0.2	0.25	0.3	0.35
Population size	1000
Number of generations	1000
Lowest Fitness Value	0.69	1.12	0.64	0.286	0.474	0.33	0.17