Skip to content

README.md

Latest commit

 

History

History
97 lines (88 loc) · 4.92 KB

README.md

File metadata and controls

97 lines (88 loc) · 4.92 KB
Raw

UG Dissertation

Our final year dissertation project. The topic, at least for now, "Metaheuristic Models for Solving Travelling Salesperson Problems"

Metaheuristic Models

  • Ant Colony Optimization (ACO) @Ra20r
  • Particle Swarm Optimisation (PSO) @Ra20r
  • Artificial Bee Colony (ABC) @Ra20r
  • Genetic Algorithm (GA) @denisovichdev
  • Simulated Annealing (SA) @denisovichdev

To-Do

  • Calculate and record individual statistics like convergence rate and heuristic data (like pheromone evaporation in ACO)
  • Plot all
  • Compare all five models with identical params to see which one:
    • Converges to the best solution
    • Is the fastest to converge

Technicals

  • Internal API endpoints (POST unless mentioned otherwise):
    • /hello
      • Purpose: Says hello
      • Params:
        • "name" : send any string
    • /aco
      • Purpose: Takes graph and other parameters and runs the ACO model to get the optimal path and return it
      • Params:
        • "graph": dictionary containing graph data
          • "nodes": list of nodes (nodes are integers)
          • "edges": list of tuples (node node weight, weights can be floating), corresponding to edges
          • "check": "u" if graph is undirected "d" otherwise
        • "params": dictionary containing data for
          • "n_ants": number of ants (int)
          • "n_best": number of best ants to choose for pheromone updation (int)
          • "n_iterations": number of iterations for the model (int)
          • "decay": pheromone decay rate (float)
          • "alpha": pheromone importance factor (int)
          • "beta": heuristic importance factor (int)
    • /ga
      • Purpose: Takes graph and other parameters and runs the Genetic Algorithm (GA) model to solve the TSP and return the optimal path
      • Params:
        • "graph": dictionary containing graph data
          • "nodes": list of nodes (nodes are integers)
          • "edges": list of tuples (node, node, weight), weights can be floating
          • "check": "u" if the graph is undirected, "d" otherwise
        • "params": dictionary containing data for
          • "population_size": number of individuals in the population (int)
          • "mutation_rate": probability of mutation for each individual (float)
          • "n_generations": number of generations the algorithm will run (int)
          • "elitism_size": number of top individuals to carry over to the next generation unchanged (int)
    • /pso
      • Purpose: Takes graph and other parameters and runs the Particle Swarm Optimization (PSO) model to solve the TSP and return the optimal path
      • Params:
        • "graph": dictionary containing graph data
          • "nodes": list of nodes (nodes are integers)
          • "edges": list of tuples (node, node, weight), weights can be floating
          • "check": "u" if the graph is undirected, "d" otherwise
        • "params": dictionary containing data for
          • "n_particles": number of particles in the swarm (int)
          • "n_iterations": number of iterations the algorithm will run (int)
          • "w": inertia weight to control the impact of previous velocities on the current velocity (float, optional, default=0.5)
          • "c1": cognitive parameter, the factor for personal best (float, optional, default=1)
          • "c2": social parameter, the factor for global best (float, optional, default=2)
    • /abc
      • Purpose: Takes graph and other parameters and runs the Artificial Bee Colony (ABC) model to solve the TSP and return the optimal path
      • Params:
        • "graph": dictionary containing graph data
          • "nodes": list of nodes (nodes are integers)
          • "edges": list of tuples (node, node, weight), weights can be floating
          • "check": "u" if the graph is undirected, "d" otherwise
        • "params": dictionary containing data for
          • "n_bees": number of bees in the colony (int)
          • "n_iterations": number of iterations the algorithm will run (int)
          • "limit": limit for the number of iterations a bee can stay in the employed phase (int)
    • /sa
      • Purpose: Takes graph and other parameters and runs the Simulated Annealing (SA) model to solve the Traveling Salesman Problem (TSP) and return the optimal path.
      • Params:
        • "graph": dictionary containing graph data
          • "nodes": list of nodes (nodes are integers)
          • "edges": list of tuples (node, node, weight), weights can be floating
          • "check": "u" if the graph is undirected, "d" otherwise
        • "params": dictionary containing data for
          • "n_iterations": number of iterations the algorithm will run (int)
          • "initial_temp": initial temperature for the annealing process (float)
          • "cooling_rate": rate at which the temperature decreases (float)
    • /generate_complete_graph
      • Purpose: Generate a random complete graph for given number of vertices
      • Params:
        • "num_vertices": number of vertices in the graph
        • "type": type of graph (u/d)

How To Run

docker compose up