README - SOP_GA_PSO

Solving the Sequential Ordering Problem (SOP) with Genetic Algorithm (GA) and Particle Swarm Optimization (PSO).
Includes a clean parser for TSPLIB-SOP files and side‑by‑side comparisons on ESC07, ESC25, and ESC78.

• Overview
• Project Structure
• Installation
• How to Run
• Results (ESC07/ESC25/ESC78)
• Reproducibility Notes
• Author
• Cite & Acknowledgments
• License

This project implements and compares two metaheuristics for SOP:

• GA on cost matrix with order crossover (OX), tournament selection, swap mutation, and elitism
• PSO in permutation space using swap‑sequence velocities: inertia, cognitive and social components

A lightweight TSPLIB-SOP parser loads:

• node count (DIMENSION)
• cost matrix (EDGE_WEIGHT_SECTION)
• precedence constraints (PRECEDENCE_SECTION)

.
├─ comparare.py           # GA vs PSO comparison and plots
├─ genetic_algorithm.py   # GA version on graph (toy)
├─ pso_algorithm.py       # PSO version on graph (toy)
├─ genetic_matrix.py      # GA on cost matrix (TSPLIB-scale)
├─ pso_matrix.py          # PSO on cost matrix (TSPLIB-scale)
├─ instance_parser.py     # TSPLIB-SOP parser
├─ sop_instances/         # ESC07.sop, ESC25.sop, ESC78.sop
├─ requirements.txt
├─ LICENSE
└─ .github/workflows/build.yml

# 1) (optional, recommended) create venv
python -m venv .venv

# Windows
.\.venv\Scripts\activate

# Linux/macOS
source .venv/bin/activate

# 2) install deps
pip install -r requirements.txt

python comparare.py

This runs GA & PSO on a small in‑code graph and shows the comparative fitness plot.

Ensure the .sop files are in sop_instances/ and run:

python comparare.py

You'll get:

• a plot per instance (GA vs PSO fitness over generations)
• best cost found by each algorithm in console output

Fill with your final numbers after running comparare.py.

Example plot (ESC07):
Add a screenshot to assets/ and embed it:
![ESC07](assets/esc07_plot.png)

• For stable runs, set a seed at the top of comparare.py:

  import random; random.seed(42)

• Suggested starting params for larger instances:
  • GA: population_size=100, generations=300
  • PSO: num_particles=100, generations=300, w=0.4, c1=1.5, c2=1.5
• Infeasible permutations (precedence violated) receive inf cost.

Cella Ioana — github.com/CellaIoana

• TSPLIB95 — SOP instances (ESC07/25/78), Heidelberg University.

BibTeX:

@misc{SOP_GA_PSO,
  author       = {Cella Ioana},
  title        = {SOP\_GA\_PSO: Genetic Algorithm vs Particle Swarm Optimization for the Sequential Ordering Problem},
  year         = {2025},
  howpublished = {\url{https://github.com/CellaIoana/SOP_GA_PSO}}
}

This project is released under the MIT License — see LICENSE.