Multi-Objective Genetic Algorithms (MOGA) with DEAP

Source : Unsplash

Introduction

Multi-Objective Genetic Algorithms (MOGA) are a subset of evolutionary algorithms specifically designed to address problems involving multiple, often conflicting objectives. These algorithms are based on the principles of natural selection and genetics, drawing from the biological evolution process to solve complex optimization problems. MOGAs work with a population of potential solutions, applying genetic operators such as selection, crossover, and mutation to evolve the population over generations towards better solutions.

The main challenge addressed by MOGA is the presence of multiple objectives that need to be optimized simultaneously. Unlike single-objective optimization problems, where a clear objective guides the search towards an optimal solution, multi-objective problems require a balance between competing objectives. This balance is often represented by a set of solutions known as the Pareto front, named after Vilfredo Pareto. The Pareto front comprises solutions that are non-dominated, meaning no other solution in the set is better in all objectives simultaneously, reflecting the trade-offs between objectives.

MOGA is unique in its ability to provide a diverse set of solutions that represent different trade-offs among the objectives. This diversity is important for decision-makers, as it provides a broader perspective on the possible solutions, enabling them to select the most appropriate solution based on their preferences or constraints. The algorithm’s iterative process of selection, crossover, and mutation follows the survival of the fittest principle, ensuring that over generations, the population evolves towards more optimal solutions.

Convergence to the Pareto front is a key aspect of MOGA, reflecting the algorithm’s effectiveness in exploring and exploiting the search space. Through generations, MOGA refines its population of solutions, gradually moving towards an optimal set of trade-offs among the competing objectives. This convergence is not towards a single solution, but rather towards a set of solutions that represent the best possible compromises, given the multiple objectives involved. The ability to simultaneously consider multiple objectives and provide a set of optimal solutions makes MOGA particularly suited for solving complex, real-world problems where trade-offs between conflicting objectives are unavoidable.

Scenario Let’s examine the application of Multi-Objective Genetic Algorithms (MOGA) in the field of aerospace engineering, particularly in optimizing the design of a spacecraft’s thermal protection system (TPS). The TPS is essential for ensuring the spacecraft can withstand the extreme temperatures encountered during atmospheric re-entry. The optimization of a TPS involves multiple conflicting objectives, making MOGA an appropriate approach for finding the best possible design solutions.

One of the primary objectives in optimizing a TPS is minimizing its weight. A lighter TPS contributes to a lower overall spacecraft weight, which directly impacts the fuel efficiency and cost of the mission. However, reducing the weight of the TPS can compromise its thermal protection capabilities. Therefore, a balance must be achieved between a lightweight design and maintaining adequate protection against the intense heat of re-entry.

The durability of the TPS material under extreme temperatures is another critical objective. The material must not only withstand the initial thermal shock but also maintain its integrity over multiple re-entry cycles for reusable spacecraft. This requirement often conflicts with the goal of minimizing weight, as more durable materials tend to be heavier. MOGA can be employed to explore various material compositions and thicknesses, seeking out designs that offer an optimal balance between durability and weight.

The cost of materials and manufacturing processes is a vital consideration in TPS design. Advanced materials offering exceptional thermal protection and durability often come at a higher cost. The challenge lies in minimizing these costs without compromising the system’s effectiveness or safety. MOGA’s ability to handle multiple objectives simultaneously enables the exploration of various material and process combinations to identify cost-effective solutions that do not sacrifice performance.

By applying MOGA to the design of a spacecraft’s TPS, engineers can efficiently navigate the trade-offs between weight, durability, and cost. The algorithm’s iterative process of selection, crossover, and mutation facilitates the exploration of a vast design space, leading to the identification of a set of Pareto-optimal solutions. These solutions represent the best possible compromises among the competing objectives, providing engineers with a range of options to choose from based on mission-specific requirements and constraints. Thus, MOGA emerges as a powerful tool in the field of aerospace engineering, driving innovation and efficiency in the design of critical systems like the thermal protection system.

Mathematical Model for TPS Optimization

Let’s define our objectives and constraints for the TPS optimization problem. (I edited the model as Markdown in Jupyter Lab so you can understand it better.)

Objective Functions

In this model, we’ve set up three goals (objectives) we want to achieve when designing the thermal coat (TPS) for a spacecraft:

1. Minimize Weight: Our first aim is to ensure that this thermal coat doesn’t weigh too much. A heavy coat means the spacecraft needs more fuel to break free from Earth’s gravity, which can be expensive and limit how much other important equipment we can carry to space. We use the weight formula, `W`, that depends on what the coat is made of (material) and how thick it is (thickness).
2. Maximize Durability: The second goal is about making the coat tough enough to handle the heat when the spacecraft re-enters the Earth’s atmosphere. We don’t want it to wear out after just one trip. The durability formula, `D`, considers the material we’re using and how well it can handle the high temperatures (temperature).
3. Minimize Cost: Lastly, we want this high-quality coat to be affordable. Space missions are already expensive, so if we can save some money on the coat without compromising on quality, that’s a significant advantage. The cost formula, `C`, takes into account the type of material and the process of manufacturing the TPS.

By using these three formulas, we aim to find the best possible materials and design for the TPS that meet these goals. We’re looking for materials that are light, can handle the heat multiple times, and won’t be too expensive. It’s similar to trying to buy a car that’s affordable, fuel-efficient, and still has high performance. With this model, we can test out different combinations to see which one gives us the best balance.

Constraints

Alright, when we’re figuring out the best recipe for our spacecraft’s thermal coat, we’ve got a couple of rules we can’t break:

• It’s Gotta Handle the Heat (Temperature Resistance Constraint): First off, the thermal coat must be able to handle a super high temperature without giving up the ghost. This is the absolute minimum standard it has to meet, no ifs or buts. If it can’t handle the peak heat (Tpeak) it’s back to the drawing board.
• Better Safe Than Sorry (Safety Margin Constraint): We also want a bit of a buffer. It means we design the coat so it’s actually a bit tougher than our minimum needs. This safety margin is like an extra layer of security to make sure the coat can handle a little more than what we expect. Think of it like packing an extra sandwich for a long hike, just in case you get hungrier than planned.

With these two rules in place, we use our objectives to mix and match materials, how thick the coat is, and the way we put it all together (that’s the material, thickness, and process stuff) to come up with a coat that’s light, tough, and not too pricey. But no matter what, it's got to pass those two tests: handling the peak temperature and having that safety buffer. That way, we know we’ve got a coat that’s up for the job and a little extra to boot.

Code Time

import random
from deap import base, creator, tools, algorithms


creator.create("FitnessMulti", base.Fitness, weights=(-1.0, 1.0, -1.0))
creator.create("Individual", list, fitness=creator.FitnessMulti)


toolbox = base.Toolbox()
toolbox.register("attr_material", random.uniform, 0, 100)  
toolbox.register("attr_thickness", random.uniform, 0, 100)  
toolbox.register("attr_process", random.uniform, 0, 100)  

toolbox.register("individual", tools.initCycle, creator.Individual,
                 (toolbox.attr_material, toolbox.attr_thickness, toolbox.attr_process), n=1)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

Import necessary modules

The random module is being imported to generate random numbers. From the deap library, base, creator, tools, and algorithms are imported. These are the core components of DEAP used for creating types, individuals, populations, and running the evolutionary algorithms.

Create fitness and individual classes

creator.create("FitnessMulti", base.Fitness, weights=(-1.0, 1.0, -1.0)): This line defines a new fitness class called FitnessMulti. The weights parameter is a tuple that defines the objectives of the optimization. Here, there are three objectives, with the first and third being minimized (as indicated by the -1.0 weights) and the second being maximized (indicated by the 1.0 weight).

creator.create("Individual", list, fitness=creator.FitnessMulti): This line defines a new class called Individual, which inherits from the Python list type. This class has an additional attribute fitness, which is an instance of the previously defined FitnessMulti class.

Toolbox setup

The toolbox is an instance of base.Toolbox and it's a way to store various functions and create a "toolbox" for evolutionary algorithms.

Attribute functions

toolbox.register("attr_material", random.uniform, 0, 100): Registers a function that will randomly generate a material attribute using a uniform distribution between 0 and 100.

• toolbox.register("attr_thickness", random.uniform, 0, 100): Registers a function to generate a thickness attribute in the same way.
• toolbox.register("attr_process", random.uniform, 0, 100): Registers a function for the process attribute.

Individual and population setup

toolbox.register("individual", tools.initCycle, creator.Individual, (toolbox.attr_material, toolbox.attr_thickness, toolbox.attr_process), n=1): Registers a function named individual that will create an individual by cycling through the attribute generator functions defined earlier (attr_material, attr_thickness, attr_process). The n=1 means that one of each attribute will be used to create an individual.

toolbox.register("population", tools.initRepeat, list, toolbox.individual): Registers a function named population that, when called, will create a list of individuals to form the population for the evolutionary algorithm.

def minimize_weight(individual):
    material, thickness, _ = individual
    return material * thickness * 0.01,  

def maximize_durability(individual):
    material, thickness, _ = individual
    return material + thickness - 50,  

def minimize_cost(individual):
    material, _, process = individual
    return material * process * 0.01,  

def temperature_resistance_constraint(individual):
    _, thickness, _ = individual
    return thickness >= 5  

def safety_margin_constraint(individual):
    _, thickness, _ = individual
    return thickness >= 5.5  

Objective Functions

These are functions that will be used to evaluate the fitness of an individual in the population.

• minimize_weight(individual): This function calculates a value representing the weight of a solution. It is intended to be minimized. The weight is computed by multiplying the material and thickness attributes and then scaling by a factor of 0.01.
• maximize_durability(individual): This function calculates a score for the durability of a solution. It is intended to be maximized. Durability is assessed by adding the material and thickness attributes and subtracting 50.
• minimize_cost(individual): This function evaluates the cost of a solution, which is supposed to be minimized. The cost is calculated by multiplying the material and process attributes and then scaling by 0.01.

Constraint Functions

These are functions that will be used to check if an individual in the population satisfies certain constraints.

• temperature_resistance_constraint(individual): This constraint ensures the thickness of the solution is at least 5 (the units are not specified but would be based on the problem context), implying that solutions not meeting this condition may be considered infeasible or less fit.
• safety_margin_constraint(individual): This constraint is similar to the temperature_resistance_constraint but enforces that the thickness is at least 5.5. It's a slightly stricter requirement than the temperature resistance constraint, likely reflecting a different safety standard or requirement.

def evaluate(individual):
    weight = minimize_weight(individual)[0]
    durability = maximize_durability(individual)[0]
    cost = minimize_cost(individual)[0]

    penalty = 0
    if not temperature_resistance_constraint(individual):
        penalty += 100  
    if not safety_margin_constraint(individual):
        penalty += 100  

  
    return weight + penalty, durability - penalty, cost + penalty

Evaluate Function

• evaluate(individual): This function is the fitness evaluation function that the evolutionary algorithm will use to assess how good each individual solution is. It uses the three objective functions to calculate the weight, durability, and cost for an individual.
• Penalties are introduced for not meeting the constraints. If the temperature_resistance_constraint is not satisfied, 100 units are added to the weight and cost and subtracted from the durability to represent a less favorable outcome. The same penalty is applied if the safety_margin_constraint is not met.
• The fitness values returned by evaluate are the sum of weight and penalties for the weight objective, durability minus penalties for the durability objective, and the sum of cost and penalties for the cost objective. The evolutionary algorithm will use these values to guide the search towards individuals that offer a balance of low weight, high durability, and low cost while satisfying the constraints on thickness.

toolbox.register("evaluate", evaluate)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=20, indpb=0.2)  
toolbox.register("select", tools.selNSGA2)

Each component is crucial for the evolution process, enabling the algorithm to evaluate individuals, combine them to create offspring, introduce variations, and select individuals for the next generation based on their fitness.

Evaluate

• toolbox.register("evaluate", evaluate): This registers the evaluate function to the toolbox under the name "evaluate". The evaluate function, defined earlier, calculates the fitness of an individual based on weight, durability, and cost, including penalties for not meeting constraints.

Mate (Crossover)

• toolbox.register("mate", tools.cxTwoPoint): Registers the two-point crossover function from DEAP's tools as the method for mating individuals. In two-point crossover, two points are selected on the parent chromosomes, and everything between these points is swapped between the two parents, producing offspring with genetic material from both parents.

Mutate

• toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=20, indpb=0.2): Registers the Gaussian mutation function. This mutation adds a value drawn from a Gaussian distribution with mean mu and standard deviation sigma to the individual's traits. The indpb parameter specifies the probability of each attribute being mutated. This method introduces variation into the population, helping the algorithm explore the solution space and avoid local optima.

Select

• toolbox.register("select", tools.selNSGA2): Registers the NSGA-II selection method. NSGA-II (Non-dominated Sorting Genetic Algorithm II) is a popular method for selecting individuals in multi-objective optimization problems. It ranks individuals based on Pareto dominance (non-dominated sorting) and uses a crowding distance to maintain diversity in the selected population. This ensures that the evolution process considers a range of trade-offs among the objectives rather than converging prematurely to a narrow part of the solution space.

POP_SIZE = 300
MAX_GEN = 100
CXPB = 0.7
MUTPB = 0.3

• POP_SIZE: This sets the population size to 300. The population size determines how many individuals exist in the population at any given time. A larger population can provide more genetic diversity, but also requires more computational resources to evaluate.
• MAX_GEN: This sets the maximum number of generations to 100. The maximum number of generations determines how many iterations of the evolutionary cycle (selection, mating, mutation) will be performed. This is essentially the stopping criterion for the algorithm, assuming no other termination conditions are met earlier.
• CXPB: This sets the crossover probability to 0.7 (70%). The crossover probability is the likelihood that two individuals will mate and produce offspring during the evolution process. A high crossover probability promotes the combination of genetic material from different individuals, which can help explore new areas of the solution space.
• MUTPB: This sets the mutation probability to 0.3 (30%). The mutation probability is the chance that an individual will undergo mutation after being selected for the next generation. Mutation introduces random changes to an individual’s traits, providing genetic diversity and enabling the algorithm to search beyond the immediate vicinity of existing solutions.

def main():
    random.seed(64)
    pop = toolbox.population(n=POP_SIZE)
    hof = tools.ParetoFront()

    # Statistics
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean, axis=0)
    stats.register("std", np.std, axis=0)
    stats.register("min", np.min, axis=0)
    stats.register("max", np.max, axis=0)

    # Run the algorithm
    algorithms.eaSimple(pop, toolbox, cxpb=CXPB, mutpb=MUTPB, ngen=MAX_GEN, 
                        stats=stats, halloffame=hof, verbose=True)

    # Return the hall of fame
    return hof

The main function encapsulates the setup and execution of the evolutionary algorithm. Here's a step-by-step breakdown of what it does:

Set a Random Seed

This ensures reproducibility of the results by initializing the random number generator with a fixed seed (64).

Initialize the Population

The population, consisting of POP_SIZE individuals, is created using the toolbox.population method. Each individual represents a potential solution to the problem and is initialized with random attributes.

Create a Pareto Front Hall of Fame:

The tools.ParetoFront object is used to store the best individuals found over the course of the run, based on the principle of Pareto optimality. These individuals are not dominated by any other individual in terms of their fitness values.

Configure Statistics

The tools.Statistics object is configured to keep track of the population's fitness values. The stats.register method is used to compute and record the average, standard deviation, minimum, and maximum of the fitness values across the population for each generation.

Run the Evolutionary Algorithm

The algorithms.eaSimple function executes the evolutionary algorithm. It takes the population, toolbox, crossover probability (cxpb), mutation probability (mutpb), and the number of generations (ngen) as arguments. It also takes the previously configured statistics object and hall of fame to track the evolution progress and the best individuals, respectively. The verbose flag enables the printing of statistical information to the console during the run.

Return the Hall of Fame

After completing the specified number of generations, the function returns the Pareto front hall of fame, which contains the best solutions found during the evolution.

if __name__ == "__main__":
    hof = main()
    print("Best individual(s): ")
    for individual in hof:
        print(individual)

This code snippet checks if the script is executed as the main program and not imported as a module in another script. If it is the main program, it proceeds to execute the defined main function, which runs the evolutionary algorithm:

1. Execute the main Function

When the script is run, it calls the main function. The main function initializes and evolves a population of individuals based on the defined evolutionary algorithm setup, returning the hall of fame individuals that represent the best solutions found during the evolution.

2. Print the Best Individuals

After the evolutionary algorithm completes, the hall of fame (hof) returned by the main function contains the best individual(s) found throughout the evolution process. The script iterates over each individual in the hall of fame and prints their attributes to the console. These individuals are considered the best solutions to the optimization problem according to the criteria set in the fitness evaluation function and considering the Pareto optimality for multi-objective optimization.

A screenshot taken from the outputs (The output is too long, so it is attached as a representation)

After printing the output of the code, you will see a large number of lines and solution sets. I share with you below a small option on how you should evaluate them.

If the goal is to minimize weight:

• Individual with parameters: [-82.91, 232.53, -23.07]

If the goal is to minimize cost:

• Individual with parameters: [175.48, 121.42, -20.76]

If the goal is to maximize durability:

• Individual with parameters: [147.36, 192.97, -24.44]

If the goal is to find a balanced solution between all objectives:

• Individual with parameters: [11.56, 127.17, -69.04]
• Individual with parameters: [133.14, 22.67, -43.81]

Each of these individuals represents a point in the solution space that optimizes for one or a balance of the objectives. You could discuss the trade-offs of each solution in the context of the problem you are addressing. For example, in engineering designs, a balance between weight, cost, and durability is often sought, so the balanced solutions might be particularly relevant.

Conclusion

In this investigation, we examined the world of genetic algorithms (GAs) using DEAP. We constructed a multi-objective optimization scenario aimed at balancing the trade-offs between minimizing weight, maximizing durability, and minimizing cost of a hypothetical product, subject to constraints like temperature resistance and safety margin. By defining fitness functions for each objective, applying constraints, and employing tools like crossover, mutation, and selection strategies, we demonstrated how GAs can evolve a population of solutions towards optimal trade-offs.

The use of Pareto optimality helped in identifying the best solutions that represent a compromise among conflicting objectives. The process highlighted not only the flexibility and power of genetic algorithms in solving complex optimization problems but also illustrated the ease with which they can be implemented and customized using DEAP, making it a valuable approach for tackling real-world challenges in various domains.