scikit-opt is a Python codebase that encapsulates a variety of heuristic algorithms that can be used to solve optimization problems. scikit-opt official repository see:scikit-opt, scikit-opt official website documentation see:scikit-opt-doc。
The scikit-opt installation code is as follows:
pip install scikit-opt
# call scikit-opt and check the version
import sko
sko.__version__
'0.6.6'
0 Background
Introduction to heuristic algorithms
A heuristic algorithm, as the name suggests, is an algorithm that solves a problem based on intuition or experience. Instead of exhausting all possibilities step by step like traditional algorithms, it quickly finds a feasible solution through some heuristic rules or strategies. Let's say, if you drive to an unfamiliar place without a navigator. The heuristic algorithm is like asking for directions, which can be asked from passers-by or based on the roadside signs and signboards to determine the direction. Although this approach is not guaranteed to find the optimal route, it is usually able to find a feasible route in a shorter period of time.
Heuristic algorithms usually have the following characteristics:
- Fast: Heuristic algorithms are usually able to find a feasible solution in a relatively short time, especially when faced with complex problems.
- Robustness: Heuristic algorithms are insensitive to the details of the problem and can find a reasonable solution even if the problem inputs change.
- Validity: Heuristic algorithms usually find high quality solutions and perform well in many practical applications.
Of course, heuristic algorithms have some drawbacks:
- Approximation: Heuristic algorithms are not guaranteed to find an optimal solution, only a better approximation.
- Empirical: The performance of heuristic algorithms depends heavily on experience or the design of the rules, and different heuristics may have different effects.
- Limitations: Heuristic algorithms are usually designed for specific problems and are difficult to apply to other problems.
Despite some drawbacks, heuristic algorithms are still a very effective way of solving problems, especially when faced with complex problems or when real-time decision-making is required. Heuristic algorithms have applications in many fields, for example:
- Artificial Intelligence: Heuristic algorithms are widely used in the field of Artificial Intelligence, e.g., machine learning, robotics, gaming, and so on.
- Operations Optimization: Heuristic algorithms are used to solve a variety of operations optimization problems, such as the traveler's problem, scheduling problems, resource allocation problems, and so on.
- Computer Graphics: Heuristic algorithms are used to solve various problems in computer graphics, such as path planning, image segmentation, texture generation, etc.
Heuristic algorithms in scikit-opt
Heuristic algorithms supported by scikit-opt include:
- Differential Evolution: An optimization algorithm based on population search to find the optimal solution by simulating the process of biological evolution.
- Genetic Algorithm (Genetic Algorithm): simulates the mechanisms of natural selection and heredity to optimize a problem through variation, crossover and selection of individuals in a population.
- Particle Swarm Optimization: Simulates the group behavior of individuals in a flock of birds or a school of fish, and searches for an optimal solution by sharing information among individuals.
- Simulated Annealing: Inspired by the process of metal annealing, the Simulated Annealing algorithm jumps to a local optimum in the search space by accepting the probability of a solution with a reduced state.
- Ant Colony Optimization (ACO): simulates the behavior of ants searching for food, finding an optimized path through pheromone deposition and evaporation.
- Immune Optimization Algorithm (IOA): based on the evolutionary process of the immune system, the problem is optimized by simulating the production of antibodies and the immune response.
- Artificial Fish-Swarm Algorithm (AFSA): simulates the foraging behavior of a school of fish and searches for an optimal solution through positional adjustment and information sharing among individuals.
These algorithms belong to the category of heuristic algorithms for complex optimization problems, such as function optimization, parameter tuning, etc. scikit-opt provides Python implementations of these algorithms, and often includes support for adaptation to different problems and optimization parameters, making it easier for users to apply these algorithms to problem solving.
The following table contains the advantages and disadvantages of these algorithms and the context in which they are applied:
| Algorithm name | vantage | drawbacks | Applicable environment |
|---|---|---|---|
| differential evolutionary algorithm | Robust for a wide range of optimization problems with fast convergence speeds | The parameter settings have a large impact on the performance of the algorithm, and it is easy to fall into a local optimum | Continuous optimization problems, especially in high-dimensional spaces |
| genetic algorithm | Global search capability for complex optimization problems | Complex parameterization and slow convergence rate | Combinatorial optimization problems, e.g., traveler's problem, scheduling problem, etc. |
| particle swarm algorithm | Simple implementation and fast convergence for multimodal optimization problems | Easy to fall into local optimization, parameter settings have a large impact on the performance of the algorithm | Continuous optimization problems, especially multimodal optimization problems |
| simulated annealing algorithm | Ability to jump out of local optima for complex optimization problems | Complex parameterization and slow convergence rate | Combinatorial optimization problems such as circuit design, image processing, etc. |
| ACO algorithm | Applicable to discrete optimization problems with distributed computation | Complex parameterization and slow convergence rate | Combinatorial optimization problems, e.g., traveler's problem, vehicle path problem, etc. |
| Immuno-optimization algorithms | Strong robustness and adaptivity for dynamic optimization problems | Higher algorithm complexity and more difficult parameterization | Combinatorial optimization problems such as feature selection, data classification, etc. |
| fish swarm algorithm | Simple implementation with good parallelism for multi-objective optimization problems | Easy to fall into local optimization, parameter settings have a large impact on the performance of the algorithm | Sequential optimization problems, especially multi-objective optimization problems |
1 Algorithm use
1.1 Differential Evolutionary Algorithm
Differential Evolution (DE) is a population-based heuristic optimization algorithm, whose core idea is to find the optimal or near-optimal solution of a problem by simulating the mutation and natural selection mechanism in the process of biological evolution and continuously exploring and improving the solution. This process can be simply compared to an exploratory trip:
- Expedition Team Formation: Before the expedition begins, a team is formed that consists of multiple explorers, each representing a possible solution. Armed with maps and equipment, these explorers are ready to set out to explore the unknown.
- Differential: During an expedition, each explorer observes their surroundings and exchanges information with other explorers. Differential can be understood here as the exchange of information between explorers, who compare each other's maps and equipment to find out which is the more effective strategy. In the DE algorithm, differencing means generating new exploration directions by calculating the difference between two randomly selected explorers (solutions).
- Evolution: As the exploration progresses, the explorer will continuously adjust his route and strategy based on the information collected. In DE algorithms, evolution means combining the new exploration direction with the current solution through the crossover operation to generate a new candidate solution. This process is similar to natural selection, where excellent strategies are retained and maladaptive strategies are eliminated.
- Fitness evaluation: explorers constantly evaluate the effectiveness of their routes during exploration, such as whether they are closer to the goal or whether they avoid dangerous areas. In DE algorithms, fitness evaluation refers to evaluating the performance of each candidate solution according to the specific objective of the optimization problem.
- Iterative update: The explorer updates its strategy after each evaluation based on the results. In the DE algorithm, this means evolving and improving by choosing to keep or replace the current solution based on the results of the fitness evaluation.
- Goal attainment: eventually, the explorer will find an optimal path to the goal. In the DE algorithm, this means that a candidate solution close to the optimal solution is found.
The above analogy may not be entirely accurate; see Differential Evolutionary Algorithms for a detailed understanding:Basic concepts and principles of differential evolutionary algorithms。
The DE class in the scikit-opt library is used to implement the Differential Evolutionary Algorithm algorithm, and the DE class construction parameters are described below:
| parameters | default value | significance |
|---|---|---|
| func | - | Functions to optimize |
| n_dim | - | Number of independent variables included in the objective function |
| size_pop | 50 | Population size, the larger the population size, the wider the range of exploration, but also the greater the computational effort |
| max_iter | 200 | Maximum number of iterations for the algorithm to run |
| prob_mut | 0.001 | probability of variation, the higher the probability of variation, the greater the diversity of the population, but it may also lead to trapping in localized solutions |
| F | 0.5 | Coefficient of variation, the greater the coefficient of variation, the greater the magnitude of variation and the greater the range of exploration of the population |
| lb | -1 | Minimum value of each independent variable |
| ub | 1 | Maximum value of each independent variable |
| constraint_eq | empty tuple | equational constraint |
| constraint_ueq | empty tuple | Inequality constraints of the form less than or equal to 0 |
Differential evolution algorithms are sensitive to parameter settings and need to be adapted to the specific problem. examples of DE class usage in scikit-opt are as follows:
Defining the Optimization Problem
The optimization issues are as follows:
min f(x1, x2, x3) = x1 + x2^2 + x3^3
.
x1*x2 >= 1
x1*x2 <= 5
x2 + x3 = 1
0 <= x1, x2, x3 <= 5
This is a nonlinear programming problem with constraints. In this problem, the objective is to find a set of variables\(x_1, x_2, x_3\) values such that the objective function\(f(x_1, x_2, x_3) = x_1 + x_2^2 + x_3^3\) reaches a minimum value while satisfying a given set of constraints.
Objective Function:
- \(f(x_1, x_2, x_3) = x_1 + x_2^2 + x_3^3\)
Constraints:
- \(x_1 \cdot x_2 \geq 1\) (This is a nonlinear constraint that ensures that the\(x_1\) respond in singing\(x_2\) (the product of which is not less than 1)
- \(x_1 \cdot x_2 \leq 5\) (again, a nonlinear constraint restricting\(x_1\) respond in singing\(x_2\) (the product of which is not greater than 5)
- \(x_2 + x_3 = 1\) (This is a linear equation constraint, denoted\(x_2\) cap (a poem)\(x_3\) (the sum of which must be 1)
- \(0 \leq x_1, x_2, x_3 \leq 5\) (This is a variable boundary constraint that restricts\(x_1, x_2, x_3\) (the value of which ranges from 0 to 5)
sample code (computing)
# Define the constrained optimization problem
def obj_func(p).
# Give the inputs
x1, x2, x3 = p
# Return the objective function values, the goal is to minimize the objective function values
return x1 + x2 ** 2 + x3 ** 3
# Define the third constraint
constraint_eq = [
lambda x: 1 - x[1] - x[2]
]
# Define the first and second constraints
constraint_ueq = [
lambda x: 1 - x[0] * x[1],
lambda x: x[0] * x[1] - 5
]
# Call the differential evolution algorithm to solve the problem
from import DE
# lb and ub define the fourth constraint
de = DE(func=obj_func, n_dim=3, size_pop=50, max_iter=100, lb=[0, 0, 0], ub=[5, 5, 5], constraint_eq=constraint_eq, constraint_ueq=constraint_ueq)
constraint_eq=constraint_eq, constraint_ueq=constraint_ueq)
# The variable values of the optimal solution and the objective function value will be returned
# The goal is to minimize the objective function value
best_x, best_y = ()
print('best_x:', best_x, '\n', 'best_y:', best_y)
best_x: [1.60211276 0.73970843 0.26021027]
best_y: [2.16689999]
The values of the variables brought into the optimal solution into the objective function are calculated to be equal to best_y:
best_x[0]+best_x[1]**2+best_x[2]**3
2.1668999924186294
function (math.)
# optimal function value for each iteration
res = de.generation_best_Y
# Length of max_iter
len(res)
100
# Input value corresponding to the optimal function value for each iteration
res = de.generation_best_X
# Length of max_iter
len(res)
100
# Function values for all individuals in the population at each iteration
res = de.all_history_Y
# length(max_iter)
# len(res)
# Return value is size_pop, which is the number of populations
len(res[0])
50
1.2 Genetic algorithms
1.2.1 Basic genetic algorithms
Genetic Algorithm (GA) is a search and optimization algorithm that simulates natural selection and genetic mechanisms. It solves optimization problems by simulating natural phenomena such as inheritance, mutation, crossover and selection in the process of biological evolution. The core idea of genetic algorithm is illustrated in layman's terms through the example of treasure digging:
- Define the problem (where is the treasure): Suppose you are looking for a treasure in a vast area. The area can be thought of as a huge map, and the treasure could be hidden in any location.
- Initialize the population (randomly selected starting points): At the beginning, you don't know the exact location of the treasure, so you randomly select some starting points, which can be regarded as "individuals" in the "population". Each individual represents a possible treasure location.
- Fitness assessment (assessment of treasure location): Each individual (treasure location) needs to be assessed for its "fitness". In the example of digging for treasure, fitness can be defined as the distance to the real location of the treasure. The closer to the location of the treasure, the higher the fitness.
- Selection (elimination of unsuitable individuals): selecting those closer to the treasure into the next generation based on adaptation. This is like natural selection in which organisms that are more adapted to their environment are more likely to survive and reproduce.
- Crossover (generating new treasure locations): Selected individuals are "crossovered" (similar to the mating of organisms). In genetic algorithms, this is usually achieved by exchanging certain characteristics between individuals. For example, the coordinates of two treasure locations can be exchanged to produce a new treasure location.
- Mutation (introduction of new treasure locations): some random changes (mutations) are introduced in order to increase the diversity of the population. This is like a biological genetic mutation that may produce new treasure locations.
- Repeat iterations (keep trying): Repeat the above process until the treasure is found or a certain number of iterations are reached. Each iteration generates a new population that gradually approaches the true location of the treasure.
- Convergence (finding the treasure): eventually, through continuous iteration and optimization, individuals in the population will get closer and closer to the true location of the treasure until it is found.
The above analogy may not be entirely accurate; see Genetic Algorithms for a detailed understanding:Understanding Genetic Algorithms in 10 Minutes。
The GA class in the scikit-opt library is used to implement the genetic algorithm, and the constructor parameters of the GA class are described below:
| parameters | default value | significance |
|---|---|---|
| func | - | objective function |
| n_dim | - | Dimension of the objective function |
| size_pop | 50 | population size |
| max_iter | 200 | Maximum number of iterations |
| prob_mut | 0.001 | probability of mutation |
| lb | -1 | Minimum value of each independent variable |
| ub | 1 | Maximum value of each independent variable |
| constraint_eq | empty tuple | equational constraint |
| constraint_ueq | empty tuple | inequality constraint |
| precision | 1e-7 | Precision, int/float or a list of them |
Case 1
The following code demonstrates the use of genetic algorithm to solve the schaffer function:
import numpy as np
# The schaffer function is a standard benchmark function for optimization algorithm testing
def schaffer(p).
'''
The function has many local minima and strong oscillations.
The global minimum occurs at (0,0) and its function value is 0.
'''
# Unwrap the incoming argument p, where p is a tuple or array of two elements
x1, x2 = p
# Calculate the sum of the squares of x1 and x2
x = (x1) + (x2)
# Calculate the value of the schaffer function
# Here the sine and square functions are used and the complexity of the function is increased by a denominator term
return 0.5 + (((x)) - 0.5) / (1 + 0.001 * x)
# Import the genetic algorithm module
from import GA
# Initialize the genetic algorithm
ga = GA(
func=schaffer, # Objective function to be optimized, return
n_dim=2, # Dimension of decision variables
size_pop=30, # Population size
max_iter=100, # Maximum number of iterations
prob_mut=0.001, # Mutation probability
lb=[-1, -1], # Lower bound of the decision variable
ub=[1, 1], # Upper bound for decision variable
precision=1e-7 # Algorithmic precision
)
# The values of the variables and the objective function of the optimal solution will be returned.
# The goal is to minimize the objective function values
best_x, best_y = ()
# Output the decision variables and objective function values of the optimal solution
# You can see that the values of the two variables in best_x are close to 0
print('best_x:', best_x, '\n', 'best_y:', best_y)
best_x: [-0.0001221 0.0074937]
best_y: [5.9325642e-08]
# import pandas and libraries for data processing and plotting
import pandas as pd
import as plt
# Convert the function value history of all individuals during the genetic algorithm to a DataFrame
# ga.all_history_Y is the function value for all individuals in the population at each iteration
# Y_history shape is (max_iter,size_pop)
Y_history = (ga.all_history_Y)
# Create a graph with two subgraphs
fig, ax = (2, 1)
# Plot the history of function values in the first subgraph
ax[0].plot(y_history.index, y_history.values, '.' , color='red')
# Plot the function minima of the various clusters for each iteration in the second subplot
Y_history.min(axis=1).cummin().plot(kind='line')
# Display the graph
()
The GA class also provides other functional functions:
ga.generation_best_Y # optimal function value for each generation
ga.generation_best_X # Input value corresponding to the optimal function value for each generation
ga.all_history_FitV # Fitness of each individual for each generation
ga.all_history_Y # Function value per individual per generation
Case 2
The following code demonstrates the use of the precision parameter to control the precision of a variable. When the precision parameter is set to an integer, the system automatically activates the integer planning mode so that the variable values strictly follow the integer constraints. In the integer planning mode, in order to achieve the best convergence speed and effect, the recommended number of possible values of the variables is as follows\(2^n\)The form of the
from import GA
demo_func = lambda x: (x[0] - 1) ** 2 + (x[1] - 0.05) ** 2 + x[2] ** 2
ga = GA(func=demo_func, n_dim=3, max_iter=500, lb=[-1, -1, -1], ub=[5, 1, 1], precision=[1, 2, 1e-7])
best_x, best_y = ()
print('best_x:', best_x, '\n', 'best_y:', best_y)
best_x: [1.00000000e+00 1.00000000e+00 2.98023233e-08]
best_y: [0.9025]
Case 3
The following code demonstrates curve fitting using a genetic algorithm:
import numpy as np
# Import for plotting
import as plt
# Import the genetic algorithm module from the sko library
from import GA
# Create data points x_true ranging from -1.2 to 1.2, 20 points in total
x_true = (-1.2, 1.2, 20)
# Calculate the corresponding y_true value as a cubic polynomial value plus random noise
y_true = x_true ** 3 - x_true + 0.4 * (20)
# Define the cubic polynomial function f_fun, with arguments consisting of x-values and coefficients a, b, c, d
def f_fun(x, a, b, c, d).
return a * x ** 3 + b * x ** 2 + c * x + d
# Define the fitness function obj_fun for the genetic algorithm to compute the sum of squares of the residuals of a polynomial fit
def obj_fun(p).
a, b, c, d = p # unwrap the parameters
# Calculate the sum of squares of the residuals of the fitted polynomial with respect to the original data points
residuals = (f_fun(x_true, a, b, c, d) - y_true).sum()
return residuals # return residuals sum of squares
# Initialize the genetic algorithm, set the fitness function, dimension, population size, number of iterations, parameter bounds
ga = GA(func=obj_fun, n_dim=4, size_pop=100, max_iter=500,
lb=[-2] * 4, ub=[2] * 4)
# Run the genetic algorithm to get the optimal parameters and corresponding residuals
best_params, residuals = ()
# Print the best parameters and residuals
print('best_x:', best_params, '\n', 'best_y:', residuals)
# Calculate the predicted y value using the best parameters
y_predict = f_fun(x_true, *best_params)
# Create drawing window and axes
fig, ax = ()
# Plot raw data points and predicted curves on the same axes
(x_true, y_true, 'o')
(x_true, y_predict, '-')
# Show the plotting window
()
best_x: [ 0.82131277 -0.01955447 -0.86175541 0.16721198]
best_y: [0.21969302]
1.2.2 Genetic algorithms for solving the traveler problem
scikit-opt provides the GA_TSP module to a genetic algorithm specifically designed to solve the Traveling Salesman Problem (TSP). It adapts to the characteristics of the TSP problem by overloading specific parts of the problem, such as crossover and mutation operations. To use GA_TSP, you first need to define the coordinates and distance matrix of the problem, then create a GA_TSP object and call the run method to execute the algorithm, and finally get the shortest path and the corresponding total distance.
The so-called TSP problem a classical combinatorial optimization problem, usually described as: given a set of cities and the distances between the cities, solve for a shortest path that visits each city once and returns to the starting city. This problem is well known in computer science and operations research and is one of the representatives of the NP-hard problem, implying that the computational complexity of finding the optimal solution increases exponentially as the number of cities increases.The solution of the TSP is not limited to the optimization of routes for business travelling salesmen, but can also be applied to a wide variety of real-life path-planning problems, such as the production of circuit boards, DNA sequencing, and so on.
The input parameters of GA_TSP are as follows, with fewer controllable parameters than the GA algorithm:
| parameters | default value | significance |
|---|---|---|
| func | - | objective function |
| n_dim | - | Number of cities |
| size_pop | 50 | population size |
| max_iter | 200 | Maximum number of iterations |
| prob_mut | 0.001 | probability of mutation |
Case 1
Here is a simple example of using the GA_TSP class in scikit-opt to solve the TSP problem:
import numpy as np
from scipy import spatial # Import the spatial module from the scipy library for calculating spatial distances.
import as plt
# Set the number of points
num_points = 20
# Generate random point coordinates
points_coordinate = (num_points, 2) # Generate an array of num_points x 2 containing random coordinates
# Calculate the distance matrix between points, using Euclidean distance
distance_matrix = (points_coordinate, points_coordinate, metric='euclidean')
# Define the objective function that calculates the total distance for a given route
def cal_total_distance(routine).
'''
Objective function. Input a route (route) and return a total distance.
The route is a one-dimensional array representing the order of the access points
'''
num_points, = # Get the length of the array of routes
# Calculate the total distance using list derivatives and the distance matrix
# Iterate over each pair of points in the route, calculate the distance between neighboring points and sum them up
return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])
# Import the Genetic Algorithm (GA) class for solving the Traveler's Problem (TSP) from the sko library
from import GA_TSP
# Initialize the GA_TSP object
ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=100, prob_mut=1)
# Run the genetic algorithm to get the optimal solution
best_points, best_distance = ga_tsp.run()
print(best_points)
print(best_distance) # minimum distance
[13 15 1 11 16 7 3 9 5 12 14 19 6 17 2 10 8 18 4 0]
[3.91036766]
The visualization code is as follows:
# Plot to show the results
fig, ax = (1, 2) # Create a graph with two subgraphs
# Plot the optimal route
best_points_ = ([best_points, [best_points[0]]]) # Add the start point to the end point to form a closed loop
best_points_coordinate = points_coordinate[best_points_, :] # Get the coordinates of the points on the optimal route
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r') # plot the optimal route
# Add arrows to indicate the direction of the route
for i in range(num_points).
ax[0].annotate('', xy=best_points_coordinate[i + 1], xytext=best_points_coordinate[i],
arrowprops=dict(arrowstyle='->', color='green'))
ax[0].plot(best_points_coordinate[0, 0], best_points_coordinate[0, 1], 'gs') # use green squares to mark the starting point
# Plot the change in the optimal solution during the iteration of the algorithm
ax[1].plot(ga_tsp.generation_best_Y) # generation_best_Y stores the optimal solution for each generation
() # Display the graph
Case 2
The following example demonstrates a method for fixing the start and end points in a genetic TSP problem. Assuming that the coordinates of the start and end points are specified as (0, 0) and (1, 1) respectively, consider a total of n+2 points, and the optimization objective is the middle n points, while the start and end points are fixed and not involved in the optimization. The objective function is the total distance of the actual path:
import numpy as np
from scipy import spatial # Import the spatial module from the scipy library for calculating spatial distances.
import as plt
# Set the number of points
num_points = 15
# Generate random point coordinates
points_coordinate = (num_points, 2) # Generate an array of num_points x 2 containing random coordinates
start_point=[[0,0]] # start point
end_point=[[1,1]] # end point
points_coordinate = ([points_coordinate,start_point,end_point])
# Calculate the distance matrix between points, using Euclidean distance
distance_matrix = (points_coordinate, points_coordinate, metric='euclidean')
# Define the objective function that calculates the total distance for a given route
def cal_total_distance(routine).
'''
Objective function. Input a route (route) and return a total distance.
The route is a one-dimensional array representing the order of the access points
'''
num_points, =
# start_point,end_point itself is not involved in the optimization. Given a fixed value, it participates in the calculation of the total route
# num_points, num_points+1 is the label for start_point,end_point
routine = ([[num_points], routine, [num_points+1]])
# Iterate over each pair of points in the route, compute the distance between neighboring points and sum them
return sum([distance_matrix[routine[i], routine[i + 1]] for i in range(num_points+2-1)])
# Import the Genetic Algorithm (GA) class for solving the Traveler's Problem (TSP) from the sko library
from import GA_TSP
# Initialize the GA_TSP object
ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=100, prob_mut=1)
# Run the genetic algorithm to get the optimal solution
best_points, best_distance = ga_tsp.run()
# Plot the results
fig, ax = (1, 2) # create a graph with two subgraphs
# Plot the optimal route
best_points_ = ([best_points, [best_points[0]]]) # Add start points to end points to close the loop
best_points_coordinate = points_coordinate[best_points_, :] # Get the coordinates of the points on the optimal route
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r') # plot the optimal route
# Add arrows to indicate the direction of the route
for i in range(num_points).
ax[0].annotate('', xy=best_points_coordinate[i + 1], xytext=best_points_coordinate[i],
arrowprops=dict(arrowstyle='->', color='green'))
ax[0].plot(best_points_coordinate[0, 0], best_points_coordinate[0, 1], 'gs') # use green squares to mark the starting point
# Plot the change in the optimal solution during the iteration of the algorithm
ax[1].plot(ga_tsp.generation_best_Y) # generation_best_Y stores the optimal solution for each generation
() # Display the graph
1.3 Particle Swarm Algorithm
Particle Swarm Optimization (PSO) is an optimization algorithm that simulates the foraging behavior of a flock of birds. Imagine a flock of birds searching for food in the vast sky, they observe each other's position and moving direction to find the place with the most food. The Particle Swarm algorithm is based on a similar principle, and its core concept is explained in layman's terms by the following example of an adventure:
- Explorer: In a particle swarm algorithm, each "particle" can be thought of as an explorer. Each member of the team has a certain position and represents a possible solution.
- Position and Speed: Each expedition member has their current position (solution) and speed (direction and speed of movement towards the goal).
- PERSONAL EXPERIENCE: Every expedition member remembers the best location they've ever reached, the richest food source they've personally found.
- Group experience: in addition to individual experience, expedition members share the best position found by the whole group, which is the consensus of the whole group and represents a superior solution.
- Explore and Utilize: Expeditioners will consider both individual experience (the best place they have found on their own) and group experience (the best place the whole group has found) as they move. They will adjust their speed and direction based on these two factors, both exploring new places and utilizing known information.
- Update Position: Depending on the speed and direction, expedition members update their position and continue to search for a better solution.
- Iterative process: this process is repeated over and over again, with each iteration being a new exploration where the expedition members update their individual experience and the group experience based on the new location.
- Convergence: over time, the explorers will gradually converge to the place with the most treasure, which means the algorithm has found the optimal solution or a location close to the optimal solution.
The above analogy may not be entirely accurate; see Particle Swarm Algorithms for a detailed understanding:Detailed explanation of particle swarm optimization algorithms。
The PSO class in the scikit-opt library is used to implement the particle swarm optimization algorithm, and the constructor parameters of the PSO class are described as follows:
| parameters | default value | significance |
|---|---|---|
| func | - | objective function |
| n_dim | - | Dimension of the objective function |
| size_pop | 50 | population size |
| max_iter | 200 | Maximum number of iterations |
| lb | None | Minimum value for each parameter |
| ub | None | Maximum value for each parameter |
| w | 0.8 | Inertia weights, which control how much the velocity of the particle's motion affects the last velocity. the larger the value of w, the better the particle remembers its historical velocity, and the better the global searching ability is |
| c1 | 0.5 | Individual memory, which controls the extent to which a particle moves toward its historical optimal position. c1 values are larger, the more the particle tends to move toward its historical optimal position |
| c2 | 0.5 | Collective memory, which controls the extent to which particles move toward the global optimum. the larger the value of c2, the more particles tend to move toward the global optimum |
| constraint_ueq | empty tuple | Inequality constraints of the form less than or equal to 0 |
Case 1
The following code shows a simple usage example of the PSO class:
# Define the problem
def demo_func(x).
"""
Target function.
Input:
x: a list of three elements representing the three variables of the problem.
Output:
Objective function value: optimization objective lieutenant minimize this value
"""
x1, x2, x3 = x # unwrap list x into three variables
return x1 ** 2 + (x2 - 0.01) ** 2 + x3 ** 2 # Calculate the objective function value
# Call the particle swarm algorithm
from import PSO
pso = PSO(
func=demo_func, # objective function
n_dim=3, # Dimension of the problem (number of variables)
pop=40, # Population size (number of particles)
max_iter=150, # Maximum number of iterations
lb=[0, -1, 0.2], # Lower bound for variables
ub=[1, 1, 1], # Upper bound for variable
w=0.8, # Inertia weights
c1=0.5, # Individual learning factor
c2=0.5 # collective learning factor
)
() # Run the particle swarm algorithm
print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y) # Print the optimal solution
import as plt
(pso.gbest_y_hist) # Plot the change in the value of the objective function with the number of iterations
()
best_x is [0. 0.01 0.2 ] best_y is [0.04]
Case 2
The following code shows the PSO class with nonlinear constraints using the example and visualization code (note that the code takes a long time to run):
import numpy as np
from import PSO
def demo_func(x):
x1, x2 = x
return x1 ** 2 + (x2 - 0.05) ** 2
# Define nonlinear constraints
constraint_ueq = (
lambda x: (x[0] - 1) ** 2 + (x[1] - 0) ** 2 - 0.5 ** 2
,
)
# Set the maximum number of iterations for the particle swarm optimization algorithm
max_iter = 50
# Create an instance of PSO, set the objective function, dimension, population size, number of iterations, variable range, and nonlinear constraints
pso = PSO(func=demo_func, n_dim=2, pop=40, max_iter=max_iter, lb=[-2, -2], ub=[2, 2],
constraint_ueq=constraint_ueq)
# Enable record mode for subsequent dynamic plotting
pso.record_mode = True
# Run the PSO algorithm
()
# Print the location and value of the optimal solution
print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y)
# Import the matplotlib library for plotting
import as plt
from import FuncAnimation
# Get the data from the PSO record
record_value = pso.record_value
X_list, V_list = record_value['X'], record_value['V']
# Create the graph and axes
fig, ax = (1, 1)
ax.set_title('title', loc='center') # set title temporarily, update later
line = ([], [], 'b.') # draw the initial null point
# Create the grid and compute the objective function values
X_grid, Y_grid = ((-2.0, 2.0, 40), (-2.0, 2.0, 40))
Z_grid = demo_func((X_grid, Y_grid))
(X_grid, Y_grid, Z_grid, 30) # plot contour map
# Set the axis range
ax.set_xlim(-2, 2)
ax.set_ylim(-2, 2)
# Draw the boundary of the circular constraint
t = (0, 2 * , 40)
(0.5 * (t) + 1, 0.5 * (t), color='r')
# Define the function that updates the scatter plot
def update_scatter(frame).
# Calculate the number of iterations and subframes corresponding to the current frame.
i, j = frame // 10, frame % 10
# Update the title
ax.set_title('iter = ' + str(i))
# Calculate current particle position (taking into account speed and iteration)
X_tmp = X_list[i] + V_list[i] * j / 10.0
# Update the data in the scatterplot
(line, 'xdata', X_tmp[:, 0], 'ydata', X_tmp[:, 1])
return line
# Create the animation
ani = FuncAnimation(fig, update_scatter, blit=True, interval=25, frames=max_iter * 10)
# Save the animation as a gif
('', writer='pillow')
best_x is [0.50070802 0.02494922] best_y is [0.25133606]
1.4 Simulated annealing algorithm
1.4.1 Basic simulated annealing algorithm
The Simulated Annealing algorithm (SA) is derived from the annealing process in metallurgy, which is a method of reducing internal defects in a metal by heating and slowly cooling it. In the algorithm, this process is used to find an optimal solution to the problem. The core idea can be illustrated in layman's terms with an adventure:
- Random Departure: Imagine you're an explorer and you start out standing in an unknown forest, not knowing where the treasure is.
- Explore the perimeter: you start walking around randomly and exploring the area around you, which is like an algorithm randomly selecting candidate solutions in the solution space.
- Accepting the good and the bad: In an adventure, you may come across good places (closer to the treasure) or bad places (further away from the treasure). The simulated annealing algorithm allows you to accept good and bad solutions at an early stage, which is like deciding to try a certain direction even though you know that it might not be the best path to take, in order to explore the unknown.
- Lower Temperature: As the adventure progresses, you will gradually reduce the scope of your exploration and become more cautious. In algorithms, this is equivalent to lowering the "temperature parameter", meaning that the algorithm becomes more selective in choosing new solutions.
- Optimal solution: eventually you may find a treasure, or at least a relatively good place. The algorithm gradually converges to the optimal or near-optimal solution of the problem in this way.
- End the adventure: when the temperature drops low enough that you barely move anymore and the algorithm stops searching, the location you are at that point is the solution the algorithm finds.
The key feature of the simulated annealing algorithm is its ability to accept suboptimal solutions during the search process, which helps the algorithm to go beyond the local optimum to have a better chance of finding the global optimum. As the "temperature" decreases, the algorithm gradually becomes more focused on finding better solutions until it finally converges.
The above analogy may not be entirely accurate; see Simulated Annealing Algorithm for a detailed understanding of the algorithm:Simulated Annealing Algorithm ExplainedThe SA class in the scikit-opt library is used to implement the simulated annealing algorithm, and the constructor parameters of the SA class are described below:
| parameters | default value | significance |
|---|---|---|
| func | - | objective function |
| x0 | - | Iteration initial point, the initial independent variable value when the algorithm starts searching |
| T_max | 100 | The maximum temperature, the initial temperature in the simulated annealing algorithm, is usually set to a higher value to allow for a larger solution space to be explored |
| T_min | 1e-7 | Minimum temperature degree, the temperature threshold at which the algorithm stops when the temperature drops below this value |
| L | 300 | Chain length, the number of steps or length of the chain in the simulated annealing algorithm |
| max_stay_counter | 150 | Cooling time consuming, when this number of times is reached, the temperature is lowered and the search continues whether or not a better solution is found |
| lb | Minimum value of each independent variable | |
| ub | Maximum value of each independent variable |
Case 1
The following code shows how the simulated annealing algorithm can be used for multivariate function optimization:
demo_func = lambda x: x[0] ** 2 + (x[1] - 0.02) ** 2 + x[2] ** 2
from import SA
sa = SA(func=demo_func, x0=[1, 1, 1], T_max=1, T_min=1e-9, L=300, max_stay_counter=10)
best_x, best_y = ()
print('best_x:', best_x, 'best_y', best_y)
import as plt
import pandas as pd
# de.generation_best_Y Optimal function values for each generation
# de.generation_best_X Optimal function values for each generation对应的输入值
((sa.best_y_history).cummin(axis=0))
()
best_x: [7.21355253e-06 2.00035659e-02 1.69597500e-05] best_y 3.5238375871831515e-10
Case 2
The SA module of the scikit-opt library also includes three different temperature descent strategies or probability distributions, "Fast", "Cauchy" and "Boltzmann". For a detailed description of these SA algorithms, please refer to:From simulated annealing to annealing evolutionary algorithmsThe SA class of the SA module uses the "Fast" version of the algorithm by default. The SA class of the SA module uses the "Fast" version of the algorithm by default.
Fast, Cauchy and Boltzmann each have different strengths and weaknesses:
- Fast:
- Advantage: fast cooling allows for lower temperatures to be reached in a shorter period of time, resulting in rapid convergence to a solution.
- Disadvantage: Due to the fast cooling rate, it may cause the algorithm to fall into the local optimal solution too early and fail to explore the global optimal solution.
- Cauchy (Cauchy distribution):
- Advantage: using the Cauchy distribution as a probability distribution for selecting a new solution allows better avoidance of local optimality because the heavier tail of the Cauchy distribution helps to explore more distant solution spaces.
- Cons: Due to the nature of the Cauchy distribution, the algorithm may in some cases concentrate too much on certain regions, resulting in a less efficient search.
- Boltzmann (Boltzmann distribution):
- Pros: using the Boltzmann distribution as a probability distribution balances the relationship between exploration and exploitation, and the algorithm is progressively biased towards selecting a better solution as the temperature decreases.
- Cons: The temperature descent strategy needs to be carefully designed to avoid too fast or too slow cooling, which may affect the performance of the algorithm.
Each of the above three strategies has its applicable scenarios and problem types. For example, for problems that need to obtain a solution quickly, the Fast strategy may be more appropriate; while for problems that need to avoid falling into local optimality, the Cauchy or Boltzmann strategy may be more advantageous. In practice, the decision of which strategy to choose often needs to be based on the characteristics and requirements of the specific problem. The example code is as follows:
# Define an anonymous function that computes the value of the objective function
# This function takes a list x as an argument and returns the sum of the squares of the elements in x
demo_func = lambda x: x[0] ** 2 + (x[1] - 0.02) ** 2 + x[2] ** 2
# Import the SAFast class from the module for fast simulated annealing algorithms
from import SAFast
# Create an instance of SAFast class sa_fast for performing simulated annealing algorithm
# Parameter description:
# func: objective function
# x0: initial solution
# T_max: maximum temperature
# T_min: minimum temperature
# q: temperature decay factor
# L: number of neighborhood searches
# lb: lower bound list
# ub: upper bound list
# max_stay_counter: maximum number of stays
# SA is equivalent to calling the SAFast function
sa_fast = SAFast(func=demo_func, x0=[1, 1, 1], T_max=1, T_min=1e-9, q=0.99, L=300, max_stay_counter=150,
lb=[-1, 1, -1], ub=[2, 3, 4])
# Run the simulated annealing algorithm
sa_fast.run()
# Print the best solution found by the algorithm and the corresponding objective function value
print('Fast Simulated Annealing: best_x is ', sa_fast.best_x, 'best_y is ', sa_fast.best_y)
# Import the SABoltzmann class from the module for the Boltzmann Simulated Annealing algorithm.
from import SABoltzmann
# Create an instance of the SABoltzmann class sa_boltzmann for use in the Boltzmann simulated annealing algorithm.
# The rest of the parameters are similar to SAFast, but use a different temperature update strategy
sa_boltzmann = SABoltzmann(func=demo_func, x0=[1, 1, 1], T_max=1, T_min=1e-9, q=0.99, L=300, max_stay_counter=150,
lb=-1, ub=[2, 3, 4])
# Print the best solution found by the algorithm and the corresponding objective function value. Note that the best_y printed here should be sa_boltzmann.best_y and not sa_fast.best_y.
print('Boltzmann Simulated Annealing: best_x is ', sa_boltzmann.best_x, 'best_y is ', sa_boltzmann.best_y)
# Import the SACauchy class from the module for the Cauchy simulated annealing algorithm.
from import SACauchy
# Create an instance of the SACauchy class, sa_cauchy, to perform the Cauchy simulated annealing algorithm.
# The rest of the parameters are similar to SABoltzmann, but with a different acceptance criterion
sa_cauchy = SACauchy(func=demo_func, x0=[1, 1, 1], T_max=1, T_min=1e-9, q=0.99, L=300, max_stay_counter=150,
lb=[-1, 1, -1], ub=[2, 3, 4])
sa_cauchy.run()
# Print the best solution found by the algorithm and the corresponding objective function value
print('Cauchy Simulated Annealing: best_x is ', sa_cauchy.best_x, 'best_y is ', sa_cauchy.best_y)
Fast Simulated Annealing: best_x is [2.58236441e-06 1.00000000e+00 2.91945906e-06] best_y is 0.9604000000151918
Boltzmann Simulated Annealing: best_x is [1 1 1] best_y is 2.9604
Cauchy Simulated Annealing: best_x is [-7.75482132e-04 1.00000000e+00 4.41811491e-05] best_y is 0.9604006033245103
1.4.2 Simulated Annealing Algorithm for Solving the Traveler's Problem
scikit-opt provides the SA_TSP module for genetic algorithms specifically designed to solve the Traveling Salesman Problem (TSP).The input parameters of SA_TSP are as follows, with fewer controllable parameters than the SA class:
| parameters | default value | significance |
|---|---|---|
| func | - | objective function |
| x0 | - | Iteration initial point |
| T_max | 100 | Maximum temperature |
| T_min | 1e-7 | minimum temperature |
| L | 300 | chain length |
| max_stay_counter | 150 | Cooling time |
The sample code is as follows:
import numpy as np
# Import the spatial module of the scipy library for calculating spatial distances
from scipy import spatial
import as plt
# Set the number of points
num_points = 15
# Generate random point coordinates, generate an array of num_points x 2 containing random x and y coordinates
points_coordinate = (num_points, 2)
# Define the coordinates of the start and end points
start_point = [[0,0]] # coordinates of the start point
end_point = [[1,1]] # End point coordinates
# Combine the start point, random point coordinates and end point into one array
points_coordinate = ([points_coordinate, start_point, end_point])
# Calculate the distance matrix between points, using Euclidean distance
distance_matrix = (points_coordinate, points_coordinate, metric='euclidean')
# Define the objective function that calculates the total distance for a given route
def cal_total_distance(routine).
'''
Objective function. Input a route (route) and return a total distance.
The route is a one-dimensional array representing the order of the access points.
'''
num_points, = # Get the number of points in the route
# Add the indexes of the start and end points to the route array
routine = ([[num_points], routine, [num_points+1]])
# Calculate the distance between neighboring points in the route and sum to get the total distance
return sum([distance_matrix[routine[i], routine[i + 1]] for i in range(num_points + 1)])
# Import the TSP solver for the simulated annealing algorithm
from import SA_TSP
# Initialize the simulated annealing TSP solver
sa_tsp = SA_TSP(func=cal_total_distance, x0=range(num_points), T_max=100, T_min=1, L=10 * num_points)
# Run the solver to find the best route and the corresponding total distance
best_points, best_distance = sa_tsp.run()
# Print the best route and the corresponding total distance
print(best_points, best_distance, cal_total_distance(best_points))
# Prepare the plot
from import FormatStrFormatter
# Create a 1x2 subplot
fig, ax = (1, 2, figsize=(12,6))
# Extend the point index of the best route with start and end points
best_points_ = ([best_points, [best_points[0]])])
# Get the coordinates of the points corresponding to the best route
best_points_coordinate = points_coordinate[best_points_, :]
# Plot the optimal solution history of the simulated annealing algorithm in the first subplot
ax[0].plot(sa_tsp.best_y_history)
ax[0].set_xlabel("Iteration")
ax[0].set_ylabel("Distance")
# Plot the best route in the second subplot
ax[1].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1],
marker='o', markerfacecolor='white', color='red', linestyle='-')
# Add an arrow to indicate the direction of the route
for i in range(num_points).
ax[1].annotate('', xy=best_points_coordinate[i + 1], xytext=best_points_coordinate[i],
arrowprops=dict(arrowstyle='->', color='green'))
# Use the green square to mark the starting point
ax[1].plot(best_points_coordinate[0, 0], best_points_coordinate[0, 1], 'gs')
# Set the format of the axes
ax[1].xaxis.set_major_formatter(FormatStrFormatter('%.3f'))
ax[1].yaxis.set_major_formatter(FormatStrFormatter('%.3f'))
# Set the label of the axis
ax[1].set_xlabel("Longitude")
ax[1].set_ylabel("Latitude")
# Display the graph
()
[ 8 12 4 2 3 6 9 13 1 7 11 5 0 14 10] 5.6269966435102825 5.6269966435102825
1.5 Ant Colony Algorithm
Ant Colony Algorithm (ACA) is an algorithm that simulates the behavior of ants searching for food and is used to solve path optimization problems. It is inspired by the phenomenon of ants searching for the shortest path to reach the food source. The core concept of the Ant Colony Algorithm is explained below in terms of an adventure:
- Expedition Preparation: Imagine a group of explorers traveling through an unknown forest in search of a treasure. They don't know the exact location of the treasure and have to explore the path through trial and error.
- Discovery of pheromones: Explorers leave a special "pheromone" behind as they move. This pheromone fades over time, but it attracts other explorers in that direction.
- Path selection: when explorers stand at an intersection, they tend to select paths with higher pheromone concentrations because these paths may have been explored and recognized as superior by other explorers.
- Local exploration vs. global optimization: explorers explore locally, i.e., follow paths with high pheromone concentration, but at the same time the algorithm allows them to explore randomly to avoid falling into local optimal solutions.
- Updated Pheromones: Whenever an explorer finds a new path to reach the treasure, they leave more pheromones on that path. This way, other explorers are more likely to choose this new, more pheromone-marked path when they come across this intersection.
- Pheromone update rule: The update of pheromones depends not only on the explorers who find new paths, but also on how fast they find the treasure. If explorers find faster paths, then they leave more pheromones behind, thus influencing the choices of other explorers faster.
- Convergence and stabilization: over time, explorers converge to optimal or near-optimal paths because the constant updating of pheromones makes all explorers tend to choose shorter and shorter paths.
- Termination of the algorithm: the condition for the end of the expedition can be that the treasure is found, or that all explorers are concentrated on a single path, or that a certain number of explorations are reached.
The above analogy may not be entirely accurate; see Ant Colony Algorithm for a detailed understanding:An article to understand what is the ant colony optimization algorithm。
Through this strategy of simulating ants looking for food, the ant colony algorithm can effectively solve the traveler's problem (TSP) and other optimization problems, especially when the problem size is large and the solution space is complex. Therefore the ACO algorithm in scikit-opt library is mainly used to solve the traveler's problem.ACA_TSP class is used to implement the ACO algorithm algorithm.The constructive parameters of ACA_TSP class are described as follows:
| parameters | default value | significance |
|---|---|---|
| func | - | objective function |
| n_dim | - | Number of cities |
| size_pop | 10 | The number of ants, more ants may increase the probability of finding a globally optimal solution, but the computational cost will also increase |
| max_iter | 20 | Maximum number of iterations |
| distance_matrix | - | Distance matrix between cities, where each element represents the distance between two cities, is used to calculate pheromone volatilization |
| alpha | 1 | The degree of pheromone importance determines the influence of the pheromone in the ant's choice of path. Higher alpha values imply greater pheromone influence |
| beta | 2 | The importance of fitness determines the influence of path fitness (e.g., distance or cost) in choosing a path. Higher beta values imply a greater influence of fitness |
| rho | 0.1 | Pheromone volatilization rate, which controls the rate of pheromone volatilization over time. Higher values of rho mean that the pheromone evaporates faster, thus reducing the effect of the pheromone on path selection |
The following case shows how to solve the traveler problem using the ACA_TSP class:
# Import the required libraries
import numpy as np
from scipy import spatial
import pandas as pd
import as plt
# Set the number of points
num_points = 20
# Generate the coordinates of the points
points_coordinate = (num_points, 2)
# Calculate the Euclidean distance matrix between points
distance_matrix = (points_coordinate, points_coordinate, metric='euclidean')
# Define the function that calculates the total distance for the traveler's problem
def cal_total_distance(routine).
# Get the path length
num_points, =
# Calculate and return the total distance of the path
return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])
# Import the ACA_TSP algorithm from the sko library to solve the TSP problem
from import ACA_TSP
# Initialize the ACA_TSP algorithm and set the problem parameters.
# Note that running the following code directly will result in an error: module 'numpy' has no attribute 'int'.
# Need to change the ACA_TSP function error location to = ((size_pop, n_dim)).astype(np.int32)
aca = ACA_TSP(func=cal_total_distance, n_dim=num_points,
size_pop=50, max_iter=200,
distance_matrix=distance_matrix)
# Run the algorithm and get the optimal solution
best_x, best_y = ()
# Create the drawing window and axes
fig, ax = (1, 2)
# Connect the points of the optimal path, including the start and end points
best_points_ = ([best_x, [best_x[0]])])
best_points_coordinate = points_coordinate[best_points_, :]
# Draw the optimal path in the first subplot
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
# Add arrows to the optimal path to indicate the direction of travel
for i in range(num_points).
ax[0].annotate('', xy=best_points_coordinate[i + 1], xytext=best_points_coordinate[i],
arrowprops=dict(arrowstyle='->', color='green'))
# Mark the start of the optimal path with a green square
ax[0].plot(best_points_coordinate[0, 0], best_points_coordinate[0, 1], 'gs')
# Plot the change in algorithm performance with the number of iterations in the second subplot
(aca.y_best_history).cummin().plot(ax=ax[1])
# Display the graph
()
1.6 Immuno-optimization algorithms
Immune Optimization Algorithm (IOA) is a computational method inspired by the human immune system that mimics the process of recognizing and destroying foreign pathogens in the biological immune system. This algorithm is commonly used to solve optimization problems, especially on complex and high-dimensional problems that are difficult to solve with traditional algorithms. The following is an exploratory explanation of the core idea of the immune optimization algorithm:
- IMMUNE SYSTEM INSPIRATION: The body's immune system is capable of recognizing and destroying invading pathogens, such as bacteria and viruses. This ability is achieved by recognizing specific antigens (specific parts of pathogens).
- Antibody diversity: the immune system generates a large number of different antibodies to cover a wide range of antigen types. In an optimization algorithm, this corresponds to the generation of multiple possible solutions.
- Clonal selection: when antibodies successfully recognize and bind to an antigen, the immune system clones these antibodies to increase their number to fight the pathogen more effectively. In the algorithm, this is equivalent to copying and enhancing a good solution.
- Memory cells: the immune system retains some successful antibodies as memory cells for rapid response in future encounters with the same or similar pathogens. In the algorithm, this means retaining and updating the best solution.
- Negative selection: the immune system removes antibodies that might attack its own tissues through a process of negative selection. In algorithms, this is equivalent to avoiding finding solutions that conflict with problem constraints.
- Affinity maturation: the ability of an antibody to bind to an antigen is improved by a process of mutation and selection. In algorithms, this corresponds to improving the quality of the solution through localized search.
- Diversity maintenance: the immune system maintains its diversity by introducing new antibodies in response to changing pathogens. In algorithms, this involves introducing new solutions to avoid falling into a local optimum.
- Parallel processing: the immune system processes multiple antigens at the same time, which is equivalent to evaluating multiple solutions in parallel in the algorithm.
The above analogy may not be entirely accurate; see Immuno-Optimization Algorithm Algorithm for a detailed understanding:10,000-word article on the principles of immunization algorithms.. The immuno-optimization algorithm in the scikit-opt library is mainly used to solve the traveler problem. The IA_TSP class is provided for implementing the immune optimization algorithm, and the constructor parameters of the IA_TSP class are described as follows:
| parameters | default value | significance |
|---|---|---|
| func | - | Objective function to evaluate the fitness or quality of the solution |
| n_dim | - | Number of cities, indicating the problem size, i.e., the number of variables in the optimization problem |
| size_pop | 50 | Population size, denoting the number of individuals in each iteration |
| max_iter | 200 | Maximum number of iterations, upper limit on the number of iterations for which the algorithm can run |
| prob_mut | 0.001 | Mutation probability, which indicates the likelihood that an individual will mutate during the iteration process |
| T | 0.7 | Antibody-to-antibody affinity threshold for determining inter-individual similarity, greater than which individuals are considered to be affinity, otherwise they are considered to be non-affinity |
| alpha | 0.95 | Diversity evaluation index for balancing antibody fitness and diversity, i.e., importance of antibody and antigen versus antibody concentration |
The following case shows how to solve the traveler problem using IA_TSP:
import numpy as np
# Import the function for generating TSP problems from the demo_func module of the sko library
from sko.demo_func import function_for_TSP
# num_points is the number of points, points_coordinate is the coordinates of the points, and distance_matrix is the distance matrix between the points.
# cal_total_distance is a function that calculates the total distance of a given path
num_points, points_coordinate, distance_matrix, cal_total_distance = function_for_TSP(num_points=8)
from import IA_TSP
# Define the optimization function
ia_tsp = IA_TSP(function=cal_total_distance, n_dim=num_points, size_pop=500, max_iter=800, prob_mut=0.2,
T=0.7, alpha=0.95)
# best_points is the index sequence of the points of the optimal path
# best_distance is the total distance of the optimal path
# Please note that this code may run slowly because it involves a lot of iterative computation
best_points, best_distance = ia_tsp.run()
# ia.generation_best_Y optimal function value for each generation
# ia.generation_best_X Input values corresponding to the best function values for each generation
# ia.all_history_FitV Fitness of each individual per generation
# ia.all_history_Y Function value per individual per generation
# ia.best_y Optimal function value
# ia.best_x Input value corresponding to best function value
print('best routine:', best_points, 'best_distance:', best_distance)
# Import the pyplot module of the matplotlib library for plotting.
import as plt
# Create a graph and axes object
fig, ax = (1, 1)
# Form a closed-loop path with the points of the best path along with the starting points
best_points_ = ([best_points, [best_points[0]]])
# Get the coordinates of the points of the optimal path according to their indexes.
best_points_coordinate = points_coordinate[best_points_, :]
# Draw the points of the optimal path and connect them with a red line
(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
# Add arrows to the optimal path to indicate the direction of travel
for i in range(num_points).
# Add an arrow between two points using the annotate function
('', xy=best_points_coordinate[i + 1], xytext=best_points_coordinate[i], arrowprops=dict(i)
arrowprops=dict(arrowstyle='->', color='green'))
# Mark the starting point of the best path with a green square
(best_points_coordinate[0, 0], best_points_coordinate[0, 1], 'gs')
# Display the graph
()
best routine: [0 3 4 6 1 5 7 2] best_distance: [2.49060449]
1.7 Artificial fish schooling algorithms
Artificial Fish-Swarm Algorithm (AFSA) is an optimization algorithm that simulates the behavior of fish in nature. Its core concept can be explained in the following ways, just like an adventure:
- Exploration and Exploitation: Explorers need to explore in the unknown as well as exploit known resources. Similarly, individuals (simulated fish) in AFSA explore the search space to find optimal solutions and also exploit the currently found better solutions with a view to further optimization.
- Group behavior: members of an expedition usually collaborate with each other and share information. In the fish schooling algorithm, fish work together to find food resources through group behaviors, such as following and avoiding obstacles. In the algorithm, individuals adjust their search strategy based on the location and information of other individuals in the group.
- Stochasticity and Adaptation: the expedition process is full of uncertainties, and explorers need to flexibly adjust their strategies according to the changes in the environment. Individuals in the artificial fish schooling algorithm also adaptively adjust to feedback from the environment, such as changing the search direction or speed.
- Survival competition: in exploration, resources are limited and there may be competition among explorers. In fish school algorithms, there is also competition between individuals, through which the diversity of the algorithm can be promoted to avoid premature convergence.
- LEARNING AND MEMORY: Explorers use previous experiences to guide future actions. In AFSA, individuals learn and remember previous successes and use this information to guide the current search process.
- Environmental interaction: explorers need to interact with the environment to understand its characteristics. Individuals in the fish swarm algorithm also interact with the environment in the search space, adjusting their search strategy based on environmental feedback.
- Goal Orientation: the ultimate goal of an expedition is to achieve a specific objective. the goal of AFSA is to find the optimal solution to a problem, and all behaviors and strategies serve this goal.
The above analogy may not be entirely accurate; see the Artificial Fish Swarming Algorithm algorithm for a detailed understanding of the algorithm:Artificial Fish Swarming Algorithm Super Detailed ExplanationThe AFSA class in the scikit-opt library is used to implement the Artificial Fish Swarming Algorithm, and the constructor parameters of the AFSA class are described below:
| parameters | default value | significance |
|---|---|---|
| func | - | objective function |
| n_dim | - | Dimension of the objective function |
| size_pop | 50 | population size |
| max_iter | 300 | Maximum number of iterations |
| max_try_num | 100 | Maximum number of predation attempts |
| step | 0.5 | Maximum displacement ratio for each step |
| visual | 0.3 | defines the extent to which individuals can perceive other individuals during the search process |
| q | 0.98 | Sensory range attenuation factor for fish |
| delta | 0.5 | Crowding threshold, larger values may lead to overaggregation and localized searches |
The following code shows how the artificial fish schooling algorithm can be used for multivariate function optimization:
def func(x):
x1, x2, x3 = x
return (x1 - x2) ** 2 + (x2 - 0.01) ** 2 + x3 ** 2
from import AFSA
afsa = AFSA(func, n_dim=3, size_pop=50, max_iter=100,
max_try_num=100, step=0.5, visual=0.3,
q=0.98, delta=0.5)
best_x, best_y = ()
print(best_x, best_y)
[ 0.00593808 0.00693321 -0.00039819] 1.0554063699211183e-05
2 Reference
- scikit-opt
- scikit-opt-doc
- Basic concepts and principles of differential evolutionary algorithms
- Understanding Genetic Algorithms in 10 Minutes
- Detailed explanation of particle swarm optimization algorithms
- Simulated Annealing Algorithm Explained
- From simulated annealing to annealing evolutionary algorithms
- An article to understand what is the ant colony optimization algorithm
- 10,000-word article on the principles of immunization algorithms
- Artificial Fish Swarming Algorithm Super Detailed Explanation