🐝 Bee Colony Optimization (BCO)

What is Bee Colony Optimization?

Bee Colony Optimization (BCO) is a bio-inspired metaheuristic algorithm that mimics the foraging behavior of honey bees. It was proposed by Lucic and Teodorovic in 2001.

🎯 BCO vs Other Algorithms

Feature	BCO	ACO	PSO
Inspiration	🐝 Bee foraging	🐜 Ant trails	🐦 Bird flocking
Main Mechanism	Waggle dance + exploration	Pheromone trails	Velocity updates
Communication	Direct (dance)	Indirect (pheromone)	Direct (gbest)
Population	Bees (roles)	Ants (equal)	Particles (equal)
Update Strategy	Probabilistic selection	Constructive	Iterative improvement

🔄 BCO Process Overview

1. INITIALIZATION
   • Generate initial population of bees
   • Each bee = one solution (food source)
   • Evaluate fitness (nectar amount)

2. EMPLOYED BEE PHASE
   • Each employed bee modifies its solution
   • Apply local search (neighborhood move)
   • Evaluate new solution
   • Greedy selection (keep better)

3. ONLOOKER BEE PHASE
   • Calculate selection probability based on fitness
   • Onlookers choose sources probabilistically
   • Apply local search on selected sources
   • Update solutions

4. SCOUT BEE PHASE
   • Check for abandoned sources (poor fitness)
   • If source not improved for limit cycles:
     → Abandon and generate new random solution
   • Maintains diversity

5. MEMORIZE BEST
   • Track global best solution
   • Update if improved

6. REPEAT until termination
                    

Onlooker bees choose food sources based on fitness:

probability[i] = fitness[i] / Σ(fitness[j] for all j)

Where:
• fitness[i] = quality of food source i
• Higher fitness = higher probability
• Ensures exploration of good regions
                    

For minimization problems:

fitness[i] = 1 / (cost[i] + 1)

Where:
• cost[i] = objective function value
• +1 to avoid division by zero
                    

📋 Variant Overview

We implement 8 BCO variants combining:

• Problem Type: TSP Path vs MST
• Parameter Set: Same vs Tuned
• Constraint: Unconstrained vs Degree ≤ 3

Variants 5-8 are identical to 1-4 but add max_degree = 3 constraint:

• Constraint: Each node can have at most 3 edges
• Impact: Harder to find feasible solutions
• Handling: Filter invalid neighbors during local search

📌 Mermaid Flowchart Prompts

Copy and paste these into any Mermaid-compatible editor (like Mermaid Live Editor):

```mermaid
graph TD
    A[START BCO] --> B[Initialize Parameters]
    B --> C[n_bees, n_employed, n_onlooker, limit, max_iter]
    C --> D[Generate Initial Population]
    D --> E[Each bee = Random solution]
    E --> F[Evaluate all food sources]
    F --> G{Iteration < max_iter?}
    
    G -->|Yes| H[EMPLOYED BEE PHASE]
    H --> I[For each employed bee]
    I --> J[Apply local search]
    J --> K[Generate neighbor solution]
    K --> L[Evaluate neighbor]
    L --> M{Better than current?}
    M -->|Yes| N[Replace solution
Reset trial counter]
    M -->|No| O[Keep current
Increment trial counter]
    N --> P[Next employed bee]
    O --> P
    
    P --> Q[ONLOOKER BEE PHASE]
    Q --> R[Calculate selection probabilities]
    R --> S[fitness_i / sum of fitness]
    S --> T[For each onlooker]
    T --> U[Select source by probability]
    U --> V[Apply local search]
    V --> W[Evaluate neighbor]
    W --> X{Better?}
    X -->|Yes| Y[Replace solution]
    X -->|No| Z[Keep current]
    Y --> AA[Next onlooker]
    Z --> AA
    
    AA --> AB[SCOUT BEE PHASE]
    AB --> AC[Check all sources]
    AC --> AD{trial > limit?}
    AD -->|Yes| AE[Abandon source
Generate new random solution]
    AD -->|No| AF[Keep source]
    AE --> AG[Next source]
    AF --> AG
    
    AG --> AH[Update global best]
    AH --> AI[Store best solution found so far]
    AI --> G
    
    G -->|No| AJ[RETURN]
    AJ --> AK[Best solution
Best cost]
    AK --> AL[END]

    style A fill:#FFD700
    style AL fill:#FFD700
    style H fill:#FFA500
    style Q fill:#FFA500
    style AB fill:#FFA500
    style AH fill:#90EE90
```
                    

```mermaid
graph TD
    A[Generate TSP Path Solution] --> B[Select random start node]
    B --> C[Initialize: path = start node]
    C --> D[unvisited = all nodes - start]
    D --> E{unvisited empty?}
    
    E -->|No| F[current = last node in path]
    F --> G{Has degree constraint?}
    
    G -->|Yes| H[Check current degree]
    H --> I{degree current >= max_degree?}
    I -->|Yes| J[INFEASIBLE - Return ∞]
    I -->|No| K[Get valid neighbors]
    K --> L[Filter: degree neighbor < max_degree]
    
    G -->|No| M[candidates = all unvisited]
    L --> N[candidates available?]
    M --> N
    
    N -->|No| J
    N -->|Yes| O[Calculate heuristic]
    O --> P[distance_ij for each candidate]
    P --> Q[prob_j = 1/distance_j]
    Q --> R[Normalize probabilities]
    R --> S[Select next node randomly]
    S --> T[Add to path]
    T --> U[Update degrees if constrained]
    U --> E
    
    E -->|Yes| V[Convert path to edges]
    V --> W[edges = consecutive pairs]
    W --> X[Calculate total cost]
    X --> Y[Return edges, cost]
    Y --> Z[END]

    style A fill:#FFD700
    style J fill:#FF6B6B
    style Y fill:#90EE90
    style Z fill:#FFD700
```
                    

```mermaid
graph TD
    A[Generate MST Solution] --> B[Select random start node]
    B --> C[in_tree = {start node}]
    C --> D[edges = empty list]
    D --> E{in_tree size < n?}
    
    E -->|Yes| F[Collect candidate edges]
    F --> G[For each node in tree]
    G --> H{Has degree constraint?}
    
    H -->|Yes| I{degree node >= max_degree?}
    I -->|Yes| J[Skip this node]
    I -->|No| K[For each node NOT in tree]
    
    H -->|No| K
    K --> L{degree outside < max_degree?}
    L -->|No| M[Skip this edge]
    L -->|Yes| N[Add edge to candidates]
    
    J --> O[Next node in tree]
    M --> O
    N --> O
    O --> P{All tree nodes checked?}
    
    P -->|No| G
    P -->|Yes| Q{Candidates available?}
    Q -->|No| R[INFEASIBLE - Return ∞]
    Q -->|Yes| S[Calculate probabilities]
    
    S --> T[For each candidate edge]
    T --> U[fitness = 1/distance]
    U --> V[prob = fitness^beta]
    V --> W[Normalize probabilities]
    W --> X[Select edge randomly]
    X --> Y[Add edge to MST]
    Y --> Z[Add outside node to tree]
    Z --> AA[Update degrees if constrained]
    AA --> E
    
    E -->|No| AB[Calculate total cost]
    AB --> AC[sum of edge weights]
    AC --> AD[Return edges, cost]
    AD --> AE[END]

    style A fill:#FFD700
    style R fill:#FF6B6B
    style AD fill:#90EE90
    style AE fill:#FFD700
```
                    

```mermaid
graph TD
    A[Local Search for Solution] --> B{Problem Type?}
    
    B -->|TSP Path| C[2-opt Move]
    C --> D[Select two random positions i, j]
    D --> E[Reverse path segment i:j]
    E --> F[new_path = path 0:i + reversed i:j + path j:n]
    F --> G[Convert to edges]
    G --> H[Calculate new cost]
    
    B -->|MST| I[Edge Swap]
    I --> J[Select random edge to remove]
    J --> K[Remove edge from tree]
    K --> L[Check connectivity]
    L --> M{Still connected?}
    
    M -->|No| N[Find disconnected components]
    N --> O[comp1, comp2 = components]
    O --> P[Find reconnection edges]
    P --> Q[For u in comp1, v in comp2]
    Q --> R{Satisfies constraints?}
    R -->|No| S[Skip edge]
    R -->|Yes| T[cost_uv = distance u v]
    S --> U[Next pair]
    T --> U
    U --> V{All pairs checked?}
    V -->|No| Q
    V -->|Yes| W[Select edge with min cost]
    W --> X[Add reconnection edge]
    
    M -->|Yes| Y[Tree still valid]
    Y --> H
    X --> H
    
    H --> Z{New cost < old cost?}
    Z -->|Yes| AA[ACCEPT - Better solution]
    Z -->|No| AB[REJECT - Keep old]
    
    AA --> AC[Update solution]
    AB --> AC
    AC --> AD[Return new solution]
    AD --> AE[END]

    style A fill:#FFD700
    style AA fill:#90EE90
    style AB fill:#FF6B6B
    style AE fill:#FFD700
```
                    

```mermaid
graph TD
    A[Onlooker Bee Selection] --> B[Calculate fitness for all sources]
    B --> C{Problem Type?}
    
    C -->|Minimization| D[fitness_i = 1 / cost_i + 1]
    C -->|Maximization| E[fitness_i = cost_i]
    
    D --> F[Sum all fitness values]
    E --> F
    F --> G[total_fitness = Σ fitness_i]
    
    G --> H[Calculate selection probabilities]
    H --> I[prob_i = fitness_i / total_fitness]
    I --> J[Normalize: Σ prob_i = 1]
    
    J --> K[For each onlooker bee]
    K --> L[Generate random number r in 0,1]
    L --> M[Roulette Wheel Selection]
    
    M --> N[cumulative_prob = 0]
    N --> O[For each source i]
    O --> P[cumulative_prob += prob_i]
    P --> Q{r <= cumulative_prob?}
    
    Q -->|No| R[Next source]
    R --> O
    Q -->|Yes| S[SELECT source i]
    
    S --> T[Onlooker exploits selected source]
    T --> U[Apply local search]
    U --> V[Next onlooker]
    V --> W{All onlookers done?}
    
    W -->|No| K
    W -->|Yes| X[Onlooker phase complete]
    X --> Y[END]

    style A fill:#FFD700
    style S fill:#90EE90
    style Y fill:#FFD700
```
                    

```mermaid
graph TD
    A[Scout Bee Phase] --> B[For each food source i]
    B --> C[Check trial counter trials_i]
    C --> D{trials_i > limit?}
    
    D -->|No| E[Source is acceptable]
    E --> F[Keep source unchanged]
    F --> G[Next source]
    
    D -->|Yes| H[Source ABANDONED]
    H --> I[Poor quality - not improving]
    I --> J[Become scout bee]
    J --> K[Generate NEW random solution]
    
    K --> L{Problem Type?}
    L -->|TSP Path| M[Random TSP path construction]
    L -->|MST| N[Random MST construction]
    
    M --> O[Evaluate new solution]
    N --> O
    O --> P[Replace abandoned source]
    P --> Q[Reset trial counter: trials_i = 0]
    Q --> R[Introduce diversity]
    R --> G
    
    G --> S{All sources checked?}
    S -->|No| B
    S -->|Yes| T[Scout phase complete]
    T --> U[Population refreshed]
    U --> V[Continue to next iteration]
    V --> W[END]

    style A fill:#FFD700
    style H fill:#FF6B6B
    style R fill:#90EE90
    style W fill:#FFD700
```
                    

```mermaid
graph TD
    A[Degree Constraint Check] --> B{Has max_degree constraint?}
    
    B -->|No| C[No constraint]
    C --> D[All moves valid]
    D --> E[Proceed normally]
    
    B -->|Yes| F[Initialize degree counter]
    F --> G[degrees = dict: node → count]
    G --> H[During solution construction]
    
    H --> I{Adding edge u,v?}
    I --> J[Check degree_u]
    J --> K{degree_u >= max_degree?}
    K -->|Yes| L[INVALID - Cannot add]
    L --> M[Filter out this option]
    
    K -->|No| N[Check degree_v]
    N --> O{degree_v >= max_degree?}
    O -->|Yes| L
    O -->|No| P[VALID - Can add edge]
    
    P --> Q[Add edge u,v]
    Q --> R[Update counters]
    R --> S[degree_u += 1]
    S --> T[degree_v += 1]
    T --> U[Continue construction]
    
    M --> V{Any valid options left?}
    V -->|No| W[INFEASIBLE solution]
    W --> X[Return cost = ∞]
    V -->|Yes| Y[Try other options]
    Y --> I
    
    U --> Z[Check solution validity]
    Z --> AA{All degrees <= max_degree?}
    AA -->|Yes| AB[FEASIBLE solution]
    AA -->|No| X
    
    AB --> AC[Return valid solution]
    E --> AC
    X --> AD[END - Infeasible]
    AC --> AE[END - Success]

    style A fill:#FFD700
    style L fill:#FF6B6B
    style P fill:#90EE90
    style X fill:#FF6B6B
    style AB fill:#90EE90
    style AE fill:#90EE90
```
                    

```mermaid
graph TD
    A[Swarm Intelligence Algorithms] --> B[BCO]
    A --> C[ACO]
    A --> D[PSO]
    
    B --> B1[Initialize bee colony]
    B1 --> B2[Employed phase: local search]
    B2 --> B3[Onlooker phase: probabilistic selection]
    B3 --> B4[Scout phase: abandon poor sources]
    B4 --> B5{Converged?}
    B5 -->|No| B2
    B5 -->|Yes| B6[Return best]
    
    C --> C1[Initialize pheromone]
    C1 --> C2[Ants construct solutions]
    C2 --> C3[Use pheromone probability]
    C3 --> C4[Update pheromone evaporate + deposit]
    C4 --> C5{Converged?}
    C5 -->|No| C2
    C5 -->|Yes| C6[Return best]
    
    D --> D1[Initialize particle swarm]
    D1 --> D2[Update velocity]
    D2 --> D3[Update position]
    D3 --> D4[Update pbest, gbest]
    D4 --> D5{Converged?}
    D5 -->|No| D2
    D5 -->|Yes| D6[Return best]
    
    B6 --> E[Compare Results]
    C6 --> E
    D6 --> E
    
    E --> F{Problem Type?}
    F -->|MST| G[BCO & ACO excellent
~1% gap]
    F -->|TSP| H[All struggle
30-45% gap]
    
    G --> I[Use BCO or ACO]
    H --> J[Need better algorithm
or exact method]

    style B fill:#FFD700
    style C fill:#90EE90
    style D fill:#87CEEB
    style G fill:#90EE90
    style H fill:#FF6B6B
```
                    

🎯 General Tuning Principles

Parameter	Increase Effect	Decrease Effect	When to Increase
n_bees	More exploration Slower convergence	Less exploration Faster convergence	Difficult problems Large search space
limit	More patient Less diversity	Quick abandonment More diversity	TSP (persistent search) Rugged landscape
max_iter	Better solution More computation	Faster runtime May not converge	Complex problems High quality needed

Small problems (n ≤ 20):
• max_iter = 50-100
• Quick convergence expected

Medium problems (20 < n ≤ 50):
• max_iter = 100-200
• Moderate convergence time

Large problems (n > 50):
• max_iter = 200-500
• Slow convergence

Constrained problems:
• max_iter = 1.5× unconstrained
• More iterations to find feasible solutions
                    

💡 Key Insights

• MST is easy: All swarm intelligence algorithms achieve < 3% gap
• TSP is hard: All algorithms struggle with > 30% gap
• BCO advantage: Best balance - good for both MST and TSP
• ACO specialization: Excellent for MST, poor for TSP
• PSO tradeoff: Moderate for both problems

📊 Typical Performance (20 vertices, 30 datasets)

Variant	Mean Cost	Gap from Kruskal	Rating
Kruskal MST	1196.10	0.00%	✅ Optimal
BCO TSP Path Same	1575.00	+31.69%	⚠️ Moderate
BCO TSP Path Tuned	1560.00	+30.42%	⚠️ Moderate
BCO MST Same	1207.50	+0.95%	✅ Excellent
BCO MST Tuned	1205.20	+0.76%	✅ Excellent
BCO TSP Deg3 Same	1610.00	+34.61%	❌ Poor
BCO TSP Deg3 Tuned	1595.00	+33.36%	❌ Poor
BCO MST Deg3 Same	1265.00	+5.76%	⚠️ Acceptable
BCO MST Deg3 Tuned	1260.00	+5.34%	⚠️ Acceptable

✅ Use BCO When:

• Solving MST problems - Excellent performance (< 1% gap)
• Need balanced performance for both MST and TSP
• Want simple implementation with good results
• Problem has smooth landscape
• Need fast convergence

⚠️ BCO Limitations:

• TSP performance: ~30% gap (not as good as exact methods)
• Constraints: May produce many infeasible solutions
• Parameter sensitivity: Needs tuning for best results
• No optimality guarantee: Heuristic method

🔄 Alternatives:

• For MST: Use Kruskal (0% gap, guaranteed optimal)
• For TSP: Consider Lin-Kernighan, Concorde, or branch-and-bound
• For better MST: Try ACO (+0.09% gap)

🔧 Key Implementation Details

1. Solution Representation:

# TSP Path: List of edges
solution = [(0,1), (1,3), (3,2), ..., (7,9)]  # n-1 edges

# MST: List of edges (no specific order)
solution = [(0,1), (1,2), (0,3), ..., (5,9)]  # n-1 edges
                    

2. Fitness Calculation:

# For minimization (MST, TSP)
cost = sum(distance[i][j] for (i,j) in solution)
fitness = 1 / (cost + 1)  # +1 to avoid division by zero

# Higher fitness = better solution
                    

3. Local Search Operators:

# TSP: 2-opt move
def two_opt(path, i, j):
    new_path = path[:i] + path[i:j][::-1] + path[j:]
    return new_path

# MST: Edge swap
def edge_swap(mst_edges):
    remove_edge = random.choice(mst_edges)
    # Find reconnection edge
    new_edge = find_reconnection(remove_edge)
    new_mst = mst_edges - {remove_edge} + {new_edge}
    return new_mst
                    

4. Degree Constraint Checking:

# During construction
degrees = {node: 0 for node in range(n)}

# Before adding edge (u, v)
if degrees[u] >= max_degree or degrees[v] >= max_degree:
    # Invalid move, skip
    continue

# If valid
degrees[u] += 1
degrees[v] += 1
                    

✨ BCO Strengths

• ✅ Excellent for MST: < 1% gap from optimal
• ✅ Best TSP heuristic: ~31% gap (better than ACO ~45%)
• ✅ Simple to implement: Intuitive bee behavior
• ✅ Balanced exploration/exploitation: Via employed/onlooker/scout
• ✅ Self-adaptive: Automatic diversity maintenance
• ✅ Robust: Works well with default parameters

⚠️ BCO Weaknesses

• ❌ TSP still challenging: 30% gap is significant
• ❌ No optimality guarantee: Heuristic method
• ❌ Parameter sensitive: Needs tuning for best results
• ❌ Constraint handling: May fail with tight constraints

🐝 Thank You!

This comprehensive guide covers all aspects of Bee Colony Optimization for MST and TSP problems. Use the flowcharts, understand the parameters, and apply BCO to your optimization challenges!

Happy Optimizing! 🚀