brianmburu / artificial-bee-colony-in-python Goto Github PK

This is a Python implementation of the Artificial Bee Colony (ABC) algorithm. The ABC algorithm is an optimization algorithm inspired by the foraging behavior of honey bees. The algorithm works by creating a population of solutions (bees) and iteratively improving these solutions to find the optimal solution. The algorithm has three phases: Employed Bee, Onlooker Bee, and Scout Bee.

To run the code, you will need the following Python packages installed:

• pandas
• numpy
• networkx

You can install these packages using the following pip command. pip install pandas numpy networkx

The given code implements the Artificial Bee Colony (ABC) algorithm, which is a metaheuristic optimization algorithm that is inspired by the foraging behavior of honeybees. The ABC algorithm is used to solve combinatorial optimization problems, such as the traveling salesman problem (TSP).

The ABC algorithm maintains a population of candidate solutions, where each candidate solution represents a possible solution to the problem being solved. In the context of the TSP, a candidate solution is a path that visits each city exactly once and returns to the starting city.

The ABC algorithm has three phases, each of which is represented by a group of bees:

Employed bees: In this phase, each employed bee takes a candidate solution from the population and generates a new candidate solution by applying a random neighborhood structure to the current solution. If the new solution has a better fitness (i.e., a lower cost), the new solution is added to the population and the current solution is replaced with the new solution. Otherwise, the current solution remains in the population.

1. Onlooker bees: In this phase, each onlooker bee selects a candidate solution from the population based on the probability of the solution's fitness. The onlooker bee then generates a new candidate solution by applying a random neighborhood structure to the selected solution. If the new solution has a better fitness than the selected solution, the selected solution is replaced with the new solution in the population.

2. Scout bees: In this phase, a scout bee is responsible for generating a new candidate solution by randomizing a new solution in the population. This phase is activated when a candidate solution has not improved over a certain number of iterations.

3. The ABC algorithm continues to iterate through these three phases until a stopping criterion is met. In the given code, the stopping criterion is the maximum number of iterations.

The ArtificialBeeColony class initializes with the following input parameters:

• G: A NetworkX graph that represents the TSP problem being solved
• num_bees: The number of candidate solutions (i.e., bees) in the population
• max_iterations: The maximum number of iterations before the algorithm stops

The class has the following methods:

• evaluate_fitness: Computes the fitness value of a given path, which represents a candidate solution to the TSP problem.
• apply_random_neighborhood_structure: Applies a neighborhood structure to a given path, which generates a new candidate solution.
• sort_population_by_fitness: Sorts the population of candidate solutions based on their fitness values.
• choose_solution_with_probability: Selects a candidate solution from the population based on the probability of the solution's fitness.
• generate_possible_solution: Generates a new candidate solution by randomly generating a path in the graph.
• run: Runs the ABC algorithm and returns the best solution and its fitness value.