Project 01: Swarm Intelligence Search Algorithms

CSC14003 - Introduction to Artificial Intelligence

Project for implementing, analyzing, and comparing Swarm Intelligence algorithms against traditional search methods.

---

Implemented Algorithms

Swarm Intelligence Algorithms

1. Ant Colony Optimization (ACO):
   • ContinuousACO (ACOR): For continuous problems, based on a solution archive and Gaussian sampling.
   • PermutationACO (Ant System): For discrete/permutation problems like TSP, using a traditional pheromone matrix.
2. Particle Swarm Optimization (PSO):
   • ContinuousPSO: Standard PSO for continuous domains.
   • BinaryPSO: For binary discrete problems like Knapsack, using a sigmoid function to update positions.
3. Artificial Bee Colony (ABC):
   • ContinuousABC: For continuous problems.
   • IntegerABC / BinaryABC: For discrete problems.
4. Firefly Algorithm (FA):
   • ContinuousFA: For continuous problems.
   • BinaryFA: For binary discrete problems.
5. Cuckoo Search (CS):
   • ContinuousCS: For continuous problems, using Lévy flights.
   • PermutationCS: For permutation problems like TSP.

Traditional Search Algorithms

1. Hill Climbing (HC):
   • ContinuousHC (Steepest Ascent): For continuous problems.
   • BinaryHC (Steepest Ascent): For binary discrete problems.
   • PermutationHC (Steepest Ascent): For permutation problems.
2. Simulated Annealing (SA):
   • ContinuousSA: For continuous problems.
   • BinarySA: For binary discrete problems.
   • PermutationSA: For permutation problems.
3. Genetic Algorithm (GA):
   • ContinuousGA: For continuous problems.
   • BinaryGA: For binary discrete problems.
   • PermutationGA: For permutation problems.

Implemented Problems

The algorithms were tested on the following benchmark problems:

• Continuous Optimization:
  • Rastrigin Function: A complex, multi-modal function used to test global optimization capabilities.
  • Ackley Function: Another standard multi-modal benchmark function.
• Discrete Optimization:
  • Knapsack Problem: A classic combinatorial problem for binary optimization.
  • Traveling Salesman Problem (TSP): A classic combinatorial problem for permutation optimization.

Project Structure

The project is organized into a modular structure for clarity and scalability:

prj01/
├── algorithms/
│   ├── swarm/                # Swarm Intelligence algorithms
│   └── traditional/            # Traditional search algorithms
├── data/
│   └── ...                   # Data files for test problems (TSP, Knapsack)
├── experiments/
│   ├── runner.py             # Core experiment execution engine
│   └── comparisons.py        # Defines specific comparison setups
├── problems/
│   ├── continuous/
│   └── discrete/
├── results/
│   └── ...                   # Output directory for plots, CSVs, and logs
├── main.py                   # Main entry point to run experiments
├── parameter_analysis.py     # Script for parameter sensitivity analysis
└── complexity_analysis.py    # Script for complexity analysis

Setup and Installation

1. Clone the repository:

   git clone https://github.com/NgTrongDoanh/Intro2AI-Project01.git
   cd Into2AI-Project01

2. Install required libraries: The only core dependency is NumPy. Other libraries are for plotting and data handling.

   pip install numpy pandas matplotlib

How to Run

All experiments are run from the command line via main.py and parameter_analysis.py.

Running Comparison Experiments

The main.py script is used to run a full comparison between a selected Swarm algorithm and the three traditional algorithms on both a continuous and a discrete problem.

Usage:

python main.py --algo <algorithm_name> [--dims <dimensions>] [--times <num_runs>]

Arguments:

• --algo: (Required) The swarm algorithm to test. Choices: pso, fa, abc, cs, aco, all.
• --dims: (Optional) The number of dimensions for the continuous problem. Default is 10. You can provide multiple values for scalability testing (e.g., --dims 10 30 50).
• --times: (Optional) The number of times each experiment is run to get statistical results. Default is 20.

Examples:

# Run comparison for PSO vs. traditional algorithms, 30 times each
python main.py --algo pso --times 30

# Run comparison for ACO on a 15-city TSP problem, 20 times
# (dims is used for TSP's number of cities here)
python main.py --algo aco --dims 15 --times 20

# Run all swarm algorithm comparisons with default settings
python main.py --algo all

Results (summary tables as CSV and convergence plots as PNG) will be saved automatically to the results/ directory, organized by algorithm and problem.

Running Parameter Sensitivity Analysis

The parameter_analysis.py script is used to analyze the effect of different hyperparameter combinations on the performance of a specific swarm algorithm.

Usage:

python parameter_analysis.py --algo <algorithm_name>

Example:

# Analyze the effect of w, c1, c2 parameters for PSO
python parameter_analysis.py --algo pso

# Analyze the effect of alpha, beta, rho parameters for ACO
python parameter_analysis.py --algo aco

Results will be saved to results/parameter_analysis/.

Running Comlexity Analysis

The complexity_analysis.py script is used to visualize the complexity

Usage:

python complexity_analysis.py 

Results will be saved to the directory of each result.

Team Members

Student ID	Full Name
23120004	Nguyễn Trọng Doanh
23120052	Nguyễn Lê Khánh
23120254	Trịnh Thị Thu Hiền
23120421	Hồ Thùy Trâm