Skip to content

Latest commit

 

History

History
197 lines (145 loc) · 8.12 KB

documentation.md

File metadata and controls

197 lines (145 loc) · 8.12 KB

What is the Monarch Butterfly Optimization Algorithm (MBO)?

The Monarch Butterfly Optimization (MBO) algorithm is a nature-inspired metaheuristic optimization technique. It mimics the migration behavior of monarch butterflies between different regions (e.g., North America and Mexico). The goal of the algorithm is to solve optimization problems by simulating exploration and exploitation of the solution space.

Key Concepts of MBO:

  1. Subpopulations:

    • The population is divided into two subpopulations representing different regions.
    • Subpopulation A: Larger, focusing on exploration.
    • Subpopulation B: Smaller, focusing on exploitation.

  2. Migration:

    • A portion of the solutions in subpopulation A is transferred to subpopulation B.
    • This represents the movement of butterflies between regions, helping to explore new areas of the search space.

  3. Mutation:

    • Random alterations (e.g., flipping binary values) are applied to solutions to maintain diversity and avoid premature convergence.

  4. Selection:

    • The best solutions are retained across generations to ensure that the population improves over time.

What is the Knapsack Problem?

The 0–1 Knapsack Problem is a classic combinatorial optimization problem.

Problem Statement:

You are given:

  1. A knapsack with a maximum capacity (C).
  2. A set of items, where each item has:
    • A value (v) indicating its importance.
    • A weight (w) indicating its space requirement.

Objective: Select a subset of items to maximize the total value without exceeding the knapsack's weight capacity.

Mathematical Representation:

Let ( x_i ) represent whether an item ( i ) is selected (( x_i = 1 )) or not (( x_i = 0 )).

[ \text{Maximize } \sum_{i=1}^n v_i x_i \quad \text{subject to} \quad \sum_{i=1}^n w_i x_i \leq C ]

Applications:

  • Resource allocation.
  • Budget optimization.
  • Supply chain management.

How is the Knapsack Problem Being Solved in This Project?

The Enhanced Monarch Butterfly Optimization Algorithm solves the 0–1 Knapsack Problem by:

  1. Representing solutions as binary arrays (e.g., [1, 0, 1] where 1 means the item is selected).
  2. Evaluating the fitness of each solution (total value of selected items, penalizing infeasible solutions).
  3. Using migration, mutation, and selection to iteratively improve solutions.

Additionally, Google Gemini AI is used to:

  1. Generate problem instances: Create knapsack problems dynamically based on user-defined parameters.
  2. Analyze results: Provide insights into convergence and performance.

Parameters and Their Meanings

Parameter Description
Population Size Number of candidate solutions in each generation. Larger sizes improve diversity but increase runtime.
Number of Generations Total iterations for which the algorithm will run. More generations allow better optimization.
Mutation Rate Probability of flipping a bit in a solution during mutation. Higher rates improve diversity.
Knapsack Capacity Maximum weight the knapsack can hold.
Item Values Importance or profit associated with each item.
Item Weights Space or cost required by each item.

Explanation of Each Function (Code Breakdown)

File 1: mbo_core.py

  1. generate_random_solution(num_items):

    • Purpose: Creates a random binary solution (e.g., [0, 1, 1, 0]).
    • Parameters:
      • num_items: Total number of items.
    • Returns: A list of 0s and 1s.

  2. initialize_population(pop_size, num_items):

    • Purpose: Generates the initial population of random solutions.
    • Parameters:
      • pop_size: Number of solutions in the population.
      • num_items: Total number of items.
    • Returns: A list of binary solutions.

  3. fitness(solution, values, weights, capacity):

    • Purpose: Calculates the fitness (value) of a solution.
    • Logic:
      • If the total weight exceeds the capacity, the fitness is 0.
      • Otherwise, it sums the values of selected items.
    • Parameters:
      • solution: Binary solution.
      • values: List of item values.
      • weights: List of item weights.
      • capacity: Knapsack capacity.
    • Returns: Fitness score.

  4. repair(solution, weights, capacity, values):

    • Purpose: Fixes infeasible solutions by removing items until the total weight is within capacity.
    • Logic:
      • Removes items with the lowest value-to-weight ratio first.
    • Returns: A feasible binary solution.

  5. split_population(population):

    • Purpose: Divides the population into two subpopulations.
    • Returns: Two subpopulations.

  6. single_point_crossover(parent1, parent2):

    • Purpose: Performs crossover between two parent solutions.
    • Logic:
      • Combines parts of parent1 and parent2 to create two offspring.
    • Returns: Two child solutions.

  7. migration_phase(population):

    • Purpose: Simulates migration by performing crossover between subpopulations.
    • Returns: Migrated population.

  8. mutate(solution, mutation_rate):

    • Purpose: Applies mutation to a solution by flipping bits with a certain probability.
    • Parameters:
      • mutation_rate: Probability of flipping a bit.
    • Returns: Mutated solution.

  9. local_search(solution, values, weights, capacity):

    • Purpose: Improves a solution by locally adding items if they fit and improve value.
    • Returns: Improved solution.

  10. mutate_and_search(population, mutation_rate, values, weights, capacity):

    • Purpose: Applies mutation and local search to all solutions in the population.

  11. select_next_generation(population, fitness_values, pop_size):

    • Purpose: Selects the top solutions to form the next generation.

  12. main_knapsack_mbo(values, weights, capacity, pop_size, max_generations, mutation_rate, verbose):

    • Purpose: Main function to solve the knapsack problem using MBO.
    • Steps:
      • Initializes the population.
      • Iterates through generations, applying migration, mutation, and selection.
      • Tracks and prints the best solution.

File 2: knapsack_problem.py

  1. load_knapsack_instance(file_path):

    • Purpose: Loads a knapsack problem instance from a file.
    • Returns: Item values, weights, and knapsack capacity.

  2. main():

    • Purpose: Command-line interface for running the algorithm.
    • Logic:
      • Parses command-line arguments.
      • Loads the knapsack instance.
      • Executes the MBO algorithm.
      • Saves or displays plots.

File 3: utils.py

  1. plot_solution(solution, values, weights, capacity, save_path):

    • Purpose: Visualizes the selected items in a bar chart.
    • Parameters:
      • save_path: If provided, saves the plot as an image.

  2. plot_fitness_history(fitness_history, save_path):

    • Purpose: Plots the fitness convergence over generations.

File 4: test_mbo_core.py

  1. test_generate_random_solution():

    • Validates that generated solutions have the correct length and format.

  2. test_fitness_feasible():

    • Verifies correct fitness calculation for feasible solutions.

  3. test_fitness_infeasible():

    • Ensures that infeasible solutions are penalized.

  4. test_repair_feasible():

    • Confirms that feasible solutions remain unchanged during repair.

  5. test_repair_infeasible():

    • Checks that infeasible solutions are repaired correctly.

See the README file for more details.