Algorithms Inspired by Nature. Part 2
First part.
In the world of modern technology, scientists are increasingly turning to nature for inspiration when creating new algorithms. One such example is the Bacterial Foraging Algorithm (BFA), which models the foraging process of bacteria. Since its introduction in 2002, BFA has attracted attention due to its effectiveness in solving complex optimization problems. We will look at how exactly this algorithm works, the biological processes that underlie it, and how it can be applied.
Introduction
Nature has “developed” many effective strategies for survival and adaptation over billions of years of evolution. One of these amazing mechanisms is the way bacteria search for food. Despite their microscopic size and simplicity, they exhibit complex behavior that allows them to effectively find energy sources. This process, called chemotaxis, inspired scientists to create a bacterial search algorithm.
Bacteria respond to chemical gradients in their environment by moving toward higher nutrient concentrations. This process, coupled with reproduction and elimination-dispersion phases, allows bacteria not only to find food but also to adapt effectively to changes in their environment. Based on these observations, BFA was developed that uses these biological principles to solve optimization problems.
History and concept of BFA
The bacterial search algorithm was first proposed in 2002 by Kevin M. Passinho of Ohio University. The idea was based on modeling the foraging behavior of E. coli bacteria. In Passinho's paper, published In an article published in IEEE Control Systems Magazine, the author details the biological processes underlying bacterial behavior and how these processes can be used to solve optimization problems.
Basics of the theory
Evolution shapes the foraging strategies of animals, ensuring the survival and successful reproduction of those individuals who can effectively find and use resources in their environment. Animals that use ineffective strategies die out, and their genes are not passed on to the next generation. As a result of such processes, optimal foraging strategies are formed, which can be modeled as optimization processes. Foraging theory focuses on maximizing the energy obtained per unit of time spent foraging, taking into account physiological and ecological constraints.
Chemotaxis
The basic process that underlies BFA is chemotaxis, the movement of bacteria toward increasing nutrient concentrations. E. coli bacteria use flagella to move, alternating between “swimming” and “spinning” modes. When the flagella spin counterclockwise, the bacteria swim in one direction, and when the flagella spin clockwise, the bacteria begin to move in the other direction.
To detect changes in the concentration of nutrients, the bacteria use receptors. If the concentration increases, the bacteria continue to swim. When the concentration decreases, the bacteria return to the basic behavior of alternating swimming and spinning.
Mechanisms of BFA operation
The BFA algorithm consists of three main stages: chemotaxis, reproduction, and elimination-dispersion. Let's consider each of them in more detail:
ChemotaxisIn the algorithm, it is implemented through random steps that are aimed at improving the current solution.
Reproduction. The bacteria that achieve the best results divide, creating copies of themselves. This allows the algorithm to save the best solutions and simultaneously explore new areas of space.
Elimination-dispersion. Periodically, part of the bacterial population is replaced by new random agents. This helps to avoid local minima and facilitates the global search for the optimal solution.
Example of algorithm with code
To demonstrate how the bacterial search algorithm works, let's look at an example of function minimization.
Code
import numpy as np
import random
import matplotlib.pyplot as plt
import seaborn as sns
def objective_function(x):
# Функция, которую будем минимизировать
return np.sum(x**2)
class BacterialForagingAlgorithm:
def __init__(self, num_agents, num_dimensions, lb, ub, max_iters):
self.num_agents = num_agents
self.num_dimensions = num_dimensions
self.lb = lb
self.ub = ub
self.max_iters = max_iters
self.agents = np.random.uniform(lb, ub, (num_agents, num_dimensions))
self.fitness_history = []
def chemotaxis(self, agent):
# Метод отвечает за перемещение бактерий
step_size = 0.1
new_agent = agent + step_size * np.random.uniform(-1, 1, self.num_dimensions)
new_agent = np.clip(new_agent, self.lb, self.ub)
return new_agent
def reproduce(self, agents, fitness):
# Выполняет репродукцию, сохраняет лучших и удваивает их популяцию
sorted_indices = np.argsort(fitness)
half_population = self.num_agents // 2
new_agents = agents[sorted_indices[:half_population]]
return np.vstack((new_agents, new_agents))
def eliminate_and_disperse(self, agents):
# Элиминация и дисперсия, заменяет бактерий новыми случайными агентами
for i in range(self.num_agents):
if random.random() < 0.25:
agents[i] = np.random.uniform(self.lb, self.ub, self.num_dimensions)
return agents
def optimize(self):
for iter in range(self.max_iters):
new_agents = []
fitness = np.array([objective_function(agent) for agent in self.agents])
self.fitness_history.append(np.mean(fitness))
for agent in self.agents:
new_agent = self.chemotaxis(agent)
new_fitness = objective_function(new_agent)
if new_fitness < objective_function(agent):
new_agents.append(new_agent)
else:
new_agents.append(agent)
self.agents = np.array(new_agents)
self.agents = self.reproduce(self.agents, fitness)
self.agents = self.eliminate_and_disperse(self.agents)
best_agent = self.agents[np.argmin([objective_function(agent) for agent in self.agents])]
best_fitness = objective_function(best_agent)
return best_agent, best_fitness
# Параметры алгоритма
num_agents = 50
num_dimensions = 10
lb, ub = -5, 5
max_iters = 100
bfa = BacterialForagingAlgorithm(num_agents, num_dimensions, lb, ub, max_iters)
best_agent, best_fitness = bfa.optimize()
print("Лучшее решение:", best_agent)
print("Наименьшее значение функции:", best_fitness)
# Визуализация истории приспособленности
plt.figure(figsize=(10, 6))
sns.lineplot(x=np.arange(max_iters), y=bfa.fitness_history)
plt.title('История приспособленности')
plt.xlabel('Итерации')
plt.ylabel('Средняя приспособленность')
plt.show()
What about practice?
In a recent 2023 study published in the journal Energiesa bacterial search algorithm was used to improve the training of neural networks in an automatic generation controller system. The researchers demonstrated that BFA can effectively determine the initial weights of the neural network, which can reduce the training time and improve the prediction accuracy. In tests on a hybrid power system using a MATLAB/Simulink model, the BFA-based controller showed high efficiency in adjusting the frequency and minimizing overshoot under load changes and power fluctuations.
The bacterial search algorithm has found wide application in a variety of fields. For example, it is successfully used in energy system management tasks, where it allows optimizing resource allocation. In an article on the platform MQL5 BFA has been tested against other algorithms, demonstrating flexibility and efficiency in various contexts. this In the study, BFA was applied to optimize control parameters in hybrid power systems, showing high performance and robustness to changing conditions.
Conclusion
The use of biological principles in optimization algorithms opens up new possibilities for solving complex problems in various fields. BFA has shown effectiveness in solving various optimization problems due to its ability to avoid local minima and find globally optimal solutions. The algorithm has significant potential for further development. Improving the models of chemotaxis, reproduction, and elimination-dispersion can make BFA even more powerful. Perhaps in the future, we will see its widespread application in new fields such as artificial intelligence and robotics.
Have you ever used BFA or one of its derivatives? If so, what tasks have you found it most useful for?
