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

Differential Evolution (DE)

Differential Evolution (DE) is a powerful and versatile optimization algorithm that belongs to the family of evolutionary algorithms. Developed by Storn and Price in the mid-1990s, DE is designed to solve continuous optimization problems where the objective is to find the optimal or near-optimal values of a set of real-valued parameters. Its simplicity, efficiency, and effectiveness have led to its widespread adoption in various fields, including engineering, economics, data science, and machine learning.

Differential Evolution draws its inspiration from the principles of natural selection and survival of the fittest. The algorithm employs a population-based approach, where a group of candidate solutions, represented as vectors of real-valued parameters, evolves over multiple generations to converge towards the optimal solution. DE is particularly well-suited for problems with complex and multimodal solution spaces, where traditional optimization methods might struggle.

Key Components of Differential Evolution are Population Initialization, Objective Function Evaluation, Mutation, Crossover, and Selection.

1. Population Initialization - DE begins by creating a population of potential solutions. Each solution is represented as a vector of real-valued parameters, which corresponds to a potential solution to the optimization problem. The size of the population is a user-defined parameter.


2. Objective Function Evaluation - Each solution in the population is evaluated using the objective function, which quantifies how well the solution performs with respect to the optimization goal. The objective function's output serves as the fitness value of the solution.


3. Crossover - The crossover operation combines the information from the mutant vector with the original solution vector to create a trial solution. The crossover process introduces the possibility of exploiting the knowledge from the current generation while exploring new solutions.


4. Mutation - The mutation operation is a fundamental aspect of DE. It introduces diversity into the population by creating new candidate solutions that are based on the differences between existing solutions. For each solution in the population, a set of other solutions is selected (determined by user-defined parameters), and their differences are scaled by a mutation factor to generate a mutant vector.


5. Selection - The trial solutions produced through mutation and crossover are compared with their corresponding target solutions (original solutions). The trial solution is selected if it has a better fitness value than the target solution, ensuring that the population's fitness improves over generations.

Algorithm Steps and Variants

Over the years several variations of DE were developed. Some of the mostly used DE variations are DE/rand/1, DE/best/1, DE/rand/1, and DE/current-to-best/1. The aforementioned DE variations are described below.

1. DE/rand/1: This is one of the most basic variants of Differential Evolution. It selects three distinct solutions randomly from the population to create a mutant vector and then combines it with the original solution through crossover.
2. DE/best/1: In this variant, one of the best solutions (with the lowest fitness value) is used as a reference for creating the mutant vector. This enhances the algorithm's ability to exploit promising regions of the solution space.
3. DE/rand/2: Similar to DE/rand/1, this variant uses two mutants to create a more diverse mutant vector, potentially leading to better exploration.
4. DE/current-to-best/1: This variant combines elements of both the current solution and the best solution to generate the mutant vector, striking a balance between exploitation and exploration.

Advantages and Applications of Differential Evolution

Some advantages of using DE are simplicity and ease of implementation, global and local search, efficient exploration of solution space, robustness to noise, no gradient dependency, parallelization, and applications in various fields.

Simplicity and Ease of Implementation - DE's straightforward implementation and minimal parameters make it accessible to a wide range of users, including those with limited optimization experience.

Global and Local Search DE is capable of both global exploration and local exploitation, making it suitable for problems with complex landscapes.

Efficient Exploration of Solution Space The mutation operation's ability to introduce diversity enables DE to efficiently explore different regions of the solution space.

Robustness to Noise DE can handle noisy objective functions or black-box optimization problems, where the true fitness landscape is obscured or uncertain.

No Gradient Dependency Unlike gradient-based optimization methods, DE does not rely on gradient information, making it applicable to non-differentiable and discontinuous problems.

Parallelization DE can be parallelized, allowing multiple solutions to be evaluated simultaneously and speeding up the optimization process.

Applications in Various Fields DE has been successfully applied to various real-world problems, including parameter tuning in machine learning algorithms, optimization in engineering design, parameter estimation in scientific models, and more.

Disadvantages of Differential Evolution

The main disadvantages of DE are: population size, parameter tuning, slow convergence in higher dimensions, and premature convergence.

1. Population Size: The performance of DE can be sensitive to the choice of the population size. A smaller population size might lead to slower convergence, while a larger population size increases computational complexity.



2. Parameter Tuning: Although DE is relatively easy to implement, selecting appropriate parameters such as the mutation factor and crossover probability can affect its performance. Parameter tuning often requires experimentation and domain knowledge.



3. Slow Convergence in High Dimensions: In high-dimensional optimization problems, DE may struggle with slow convergence due to the curse of dimensionality.



4. Premature Convergence: DE can converge prematurely to suboptimal solutions if the mutation factor or crossover probability is not well-tuned.

Differential Evolution is a versatile optimization algorithm that leverages the principles of natural selection to tackle complex optimization challenges. Its population-based approach, mutation, crossover, and selection operations enable it to explore and exploit solution spaces efficiently. DE's adaptability, robustness, and ease of implementation have made it a popular choice for solving a wide variety of optimization problems in diverse fields. As computational power and optimization techniques continue to advance, Differential Evolution remains a valuable tool in the optimization toolbox, contributing to advancements in science, engineering, and decision-making.