Swarm Intelligence Series : Krill Herd Optimization Algorithm

The Krill Herd optimization algorithm is a novel swarm-based metaheuristic optimization algorithm that has been inspired by the herding behavior of the krill, a type of marine crustacean that also tends to form one of the largest swarms in the Antarctic Ocean. This algorithm is designed to mimic the behavior of the krill in their natural environment where they move together in groups or swarms to find food, ensuring each krill is as close as possible to a food source while in the presence of another krill.

Introduction

The krill herd optimization algorithm is a new bio-inspired optimization algorithm that simulates the herding or grouping behaviors exhibited by their crustaceans for food-gathering purposes. It has been utilized heavily to tackle optimization problems in different domains and has been found to be very efficient. This algorithm is a swarm intelligence search algorithm that has been inspired by the movement of the krill in a herd. The Krill Herd Optimization algorithm has been proven to outperform several state-of-the-art metaheuristic algorithms on various benchmark problems. It has been applied in various fields, including engineering optimization, portfolio optimization, clustering, and even in solving complex problems like the optimal reconfiguration of distribution feeders in smart grids. The algorithm's effectiveness stems from its ability to balance exploration and exploitation, ensuring that the search process is efficient and converges to high-quality solutions.

Inspiration for the Krill Herd Optimization Algorithm

The Inspiration for this algorithm has been mainly derived from the herding behavior exhibited by the krill, a kind of marine crustacean. Krill are known for their unique social behavior where they move in large groups to find food. This behavior is characterized by the presence of multiple krill moving towards a common goal in a group banded together which in their case is the food source. The Krill Herd Optimization algorithm is designed to mimic this behavior in a computational setting where the goal is to find an optimal solution for the optimization task at hand.

The main idea behind this algorithm is to simulate the herding behavior of krill to solve optimization problems. The algorithm uses the collective behavior of krill to explore the search space more efficiently. By moving together, the krill can cover a larger area of the search space and find the optimal solution more quickly than if they were to move independently. This collective behavior is incorporated into the algorithm through the movement of each "krill" (individual solution) in the search space, which is influenced by the presence of other "krill" and the direction toward the food source (optimal solution).

Convergence of the Krill Herd Optimization Algorithm

The convergence of the krill herd optimization algorithm proves to be an important factor that ensures that the algorithm performs and explores the search space effectively and converges to an optimal or at least a near-optimal solution. The algorithms' convergence is influenced by several factors, including the movement induced by other individuals, foraging behavior, and random diffusion.

These factors work together to guide the "krill" towards the optimal solution, while also ensuring diversity and exploration of the search space.

Steps taken by the Krill Herd Optimization Algorithm

The Krill Optimization algorithm simulates the herding behavior of the krill to solve optimization problems by adjusting the positions of the individual solutions known as krills in this case in the search space based on their own characteristics and interactions with other solutions. Here are the detailed steps that are taken by this algorithm,

1. Initialization: The algorithm starts off by initializing a population of krill individuals, each representing a potential solution to the optimization problem. The positions of these krill are randomly set in a predefined search space. The fitness of each krill is evaluated using the objective function of the optimization problem.

2. Foraging Movement: Each krill moves towards the best solution (food source) based on its fitness and the distance to it. This movement also considers the krill's current position and levy movement (random exploration).

3. Swarming Movement: Krill are attracted to nearby individuals with higher fitness values, encouraging them to move towards promising regions.

4. Levy Movement: A random component is added to each krill's movement to explore the search space and avoid local optima.

5. Physical Diffusion: A small random diffusion term is added to further diversify the krill positions and prevent stagnation.

6. Update Fitness: Evaluate the fitness of each krill after movement based on the objective function. Update Individual Best: Each krill compares its current fitness with its personal best and updates the latter if necessary.

Parameters Influencing the Krill Herd Optimization Algorithm

1. Population Size (N): This parameter defines the number of krill individuals in the swarm. The larger this size, the more the exploration and diversity in the search data and the krills respectively but a high enough value of it can slow down convergence.

2. Maximum Iterations (max_iter): This parameter specifies the maximum amount of iterations the main algorithm flow for this algorithm repeats. It controls the overall computational cost of the algorithm and it needs to be balanced to allow sufficient exploration and convergence as well.

3. Levy Exponent (β): This parameter governs the distribution of the jumps during levy flight, affecting the range of exploration smaller values of it can lead to larger jumps and broader exploration, and higher values of it can lead to smaller jumps and more focused exploration near the end goal. Its range is between 1.5-3 in general.

4. Foraging coefficient (ω): This parameter controls the strength of attraction towards the best solution and the higher values lead the krill to move closer to the best solution, leading to potentially faster convergence but risk premature stagnation. The lower values of it favor exploration but possibly slow down the convergence while increasing the chance of finding a global optimum.

5. Swarming coefficient (φ): This coefficient determines the strength of attraction towards nearby krill with better fitness and higher values of it promote stronger swarming behavior potentially leading to faster convergence but risk neglecting diverse regions and lower values of it encourage exploration, leading to broader search but possibly slower convergence.

6. Physical Diffusion Coefficient (μ): This parameter controls the intensity of the isotropic random diffusion, influencing diversification. The higher values of it introduce more randomness, preventing stagnation but potentially leading to an increase in the search size. The lower values of it promote convergence but risk getting stuck in locally optimum solutions.

7. Visual Distance (d_vis): This algorithm defines the maximum distance a "krill" can see its neighbors. The larger values of this parameter allow for broader communication and swarming but can be computationally expensive. The smaller values of it limit communication and encourage the exploration of diverse regions.

8. Neighborhood size (k): This parameter defines the number of closest neighbors considered for swarming.

9. Stopping Criteria: This parameter adds additional conditions like minimum fitness improvement etc to halt the algorithm.

The algorithm followed programmatically for the Krill Herd Optimization Algorithm

1. Initialization of the krills or the population: This step is necessary to define and initialize a set number of actors in the search space for exploration.

2. Fitness Evaluation: Every individual krill is evaluated based on its position within the search space. The fitness function measures how well every solution meets the optimization problem's objectives. This evaluation is crucial for guiding the search process toward better solutions.

3. Motion induced by the presence of other individuals: The movement of every krill is influenced by the positions of other individuals in the swarm. This collective behavior simulates the herding behavior of krill, where each individual is influenced by the presence and movement of the other individuals in the swarm. This mechanism encourages the exploration of the search space and helps avoid local optima.

4. Foraging Motion: This component of the algorithm simulates the active search behavior employed by the krill marine crustacean to find food. In the context of optimization, this step can be seen as the exploration of the search space toward the best-known solution or the most promising solution. This encourages the diversification of the search process and helps in finding optimal or near-optimal solutions.

5. Physical Diffusion: To introduce randomness into the movement of the krill, the algorithm incorporates a physical diffusion factor. This simulates the unpredictable nature of the environment and helps in escaping from the local optima, ensuring a more thorough exploration of the search space.

6. Updation: Based on the fitness evaluations and the influences of the herd's movements, the positions of the krill individuals are updated within the search space. This process includes the use of genetic operators like crossover and mutation from the genetic algorithm, to introduce diversity and improve the solutions.

7. Repetition: The algorithm repeats these steps of fitness evaluation. The motion is induced by the presence of other individuals, foraging motion, and physical diffusion until a stopping criterion is met. This could be reaching the maximum number of fitness function evaluations or achieving a satisfactory fitness level.

Variations of the Krill Herd Optimization Algorithm

This algorithm has inspired several variations that adapt and enhance its original concepts to address some weaknesses it has and tend to work for a lot more types of optimization problems. Some of the variations of it are -

1. Chaotic Krill Herd: This variant introduces chaotic maps to the krill herd optimization algorithm, enhancing its convergence properties. Chaotic maps add non-linearity and randomness into the algorithm, which can help in escaping the local optima and improving the exploration of the search space. The use of chaotic maps in this algorithm makes the algorithm more robust in finding the global optima.

2. Adaptive Krill Herd: This is a variation that focuses on adaptive parameters that can change during the execution of the algorithm. This adaptability allows the algorithm to respond to the characteristics of the optimization problem being solved, potentially improving the performance across a wide range of optimization tasks.

3. Multi-Objective Krill Herd: This variation extends the original algorithm to handle multi-objective optimization problems. This introduces methods for managing multiple conflicting objectives such as the Pareto dominance or the use of reference points to guide the search towards solutions that balance multiple objectives.

4. Krill Herd with Leader Selection: In this variant, a leader krill is selected based on certain criteria, such as the best fitness value or the most effective exploration of the search space. This leader krill then guides the movement of other krill, focusing the search toward promising regions and maintaining the cohesion of the herd.

5. Krill Herd with Diversity Maintenance: This introduces mechanisms to maintain diversity within the population of krill. This is crucial for exploring the search space thoroughly and avoiding premature convergence to suboptimal solutions. Diversity maintenance strategies can include adjusting the mutation rate or introducing new krill based on the exploration of the search space.

6. Krill Herd with Fuzzy Logic: This incorporates fuzzy logic principles into the algorithm, allowing for more flexible and robust decision-making processes. This can be particularly useful in problems where the objectives or constraints are not strictly defined or where the solution space is complex and irregular.

Applications

1. Engineering Optimization: This algorithm has proven its efficacy in tackling intricate engineering challenges. From design optimization to manufacturing process refinement and structural enhancement, the algorithm's ability to navigate solution spaces with efficiency sets it apart in engineering applications. By simulating the foraging behavior of krill, the algorithm adeptly explores and identifies optimal or near-optimal solutions, making it a valuable tool for engineers seeking innovative solutions to complex problems.

2. Financial Optimization: In the realm of finance, this algorithm has found significant utility in portfolio optimization, investment strategy formulation, and risk management. Its application extends to determining the optimal allocation of resources and devising sound investment strategies within the constraints of financial markets. By leveraging this algorithm, financial professionals can make informed decisions that maximize returns and mitigate risks effectively.

3. Logistics and Supply Chain Management: This algorithm has proved to be a boon for this field. Optimizing logistics and supply chain processes is essential for enhancing operating efficiency and reducing costs. This algorithm plays a pivotal role in this domain by optimizing delivery routes, scheduling tasks, and managing inventory effectively. Its unique ability to balance exploration and exploitation enables organizations to find cost-effective solutions that streamline their logistical operations and improve overall performance.

4. Image and Signal Processing: Image segmentation, feature extraction, and pattern recognition are critical tasks in the image and signal process where this algorithm has been successfully applied and used to identify optimal methods for segmenting images into distinct regions and extracting relevant features for pattern recognition.

Limitations

1. Parameter Sensitivity: Although less sensitive than some algorithms, the performance of this algorithm depends on choosing appropriate parameter values, and inappropriate parameter values when chosen from its wide set of available parameter values can lead to slow convergence, premature stagnation, or suboptimal solutions.

2. Convergence Speed: This algorithm may not be the fastest optimization algorithm for problems with large search spaces or complex objective functions and sometimes algorithms like the Particle Swarm Optimization algorithms can reach convergence much quicker than it can.

3. Local Optima: While this algorithm aims for the globally optimum solution to be reached, it can still get stuck in local optima especially when navigating through a complex landscape or when exploring inadequately.

4. High-dimensional problems: This problem's performance can decrease when faced with high dimensionality which can affect exploration and convergence efficiency.

5. Limited commercial implementations: This algorithm is not as established as other biological metaheuristic algorithms and is not as readily available in commercial software implementations, which might limit its adoption in certain domains or regions.

Code Implementation

This algorithm can be implemented in the following way using Python.

### A Basic Implementation of the Krill Herd Optimization Algorithm
### Inspiration Credits - https://medium.com/@evertongomede/the-krill-herd-algorithm-kha-mimicking-natures-collective-intelligence-for-optimization-8f8b7389fcc7


import numpy as np
def objective_function(x):
  return sum(x**2)

# Parameters for the krill herd optimization algorithm
num_dimensions=10
num_krill = 30
max_iterations = 100

# Initialization of the krill positions in the search space
krill_positions = np.random.uniform(-5, 5, (num_krill, num_dimensions))

# Initialize Krill Fitness Values
krill_fitness = np.array([objective_function(krill) for krill in krill_positions])

for iteration in range(max_iterations):
  for krill in range(num_krill):
    # Attraction step
    attractor = krill_positions[np.argmin(krill_fitness)]
    movement = np.random.random() * (attractor - krill_positions[krill]) # Moving the krills around

    # Replusion movement
    repulsion = np.sum(krill_positions - krill_positions[krill], axis=0)

    # Updating the krill positions
    krill_positions[krill] += movement + repulsion

    # Boundary handling as and when needed.
    krill_positions[krill] = np.clip(krill_positions[krill], -5, 5)

    # Update krill fitness value
    krill_fitness[krill] = objective_function(krill_positions[krill])

  # Updating the attractor position based on the best krill found
  attractor = krill_positions[np.argmin(krill_fitness)]


best_solution = krill_positions[np.argmin(krill_fitness)]
best_fitness = min(krill_fitness)

print("Optimal Solution: ", best_solution)
print("Optimal Fitness: ", best_fitness)

Conclusion

Overall, The Krill Herd optimization algorithm, inspired by the herding behavior of krill, is a powerful bio-inspired optimization method that has been applied across various domains due to its effectiveness in solving complex optimization problems. The algorithm's core principles are based on the behavior of krill, which are known for their ability to form large swarms and move in groups to find food, ensuring high density and reaching food sources efficiently. This behavior is mimicked in the algorithm through the movement and interaction of "krill" (individual solutions) within a computational search space.

This algorithm operates by simulating the herding behavior of krill, where each krill is influenced by the positions and movements of other krill in the swarm. This collective behavior encourages the exploration of the search space and helps in avoiding local optima, making the algorithm particularly effective for global optimization problems.