Skip to content
/ HBAonFPGA Public

Implementation of Hardware Bee Algorithm (HBA) on FPGA for solving the Traveling Salesperson Problem (TSP) (M.S. Thesis)

0 stars 0 forks Branches Tags Activity
Star
Notifications You must be signed in to change notification settings

pourya-kgp/HBAonFPGA

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
Docs
Docs
 
 
Figures
Figures
 
 
Matlab
Matlab
 
 
VHDL
VHDL
 
 
.gitignore
.gitignore
 
 
README.md
README.md
 
 

Repository files navigation

HBAonFPGA

Implementation of Hardware Bee Algorithm (HBA) on FPGA for solving the Traveling Salesperson Problem (TSP) (M.S. Thesis)

Overview

This project implements a Hardware Bee Algorithm on FPGA for solving the Traveling Salesperson Problem (TSP). The system followed these main steps:

  1. Algorithm Implementation
    The project implements several well-known bee colony algorithms as faithfully as possible:
    - BA (Bee Algorithm)
    - BCO (Bee Colony Optimization - Constructive)
    - BCOi (Bee Colony Optimization improvement)
    - CABC (Combinatorial Artificial Bee Colony)
    Each algorithm supports two different local optimization methods:
    - 2-Opt : 2-Opt for edge exchange.
    - GSTM : Greedy Sub-Tour Mutation.
    For the BCOs algorithm, two types of backward pass methods are available:
    - Nonloyal : Recruitment based on fitness probabilities.
    - Loyal : Loyalty-based recruitment with probabilistic retention.
    Additionally, the project includes scripts to extract TSP data from the original Fortran-based database, as well as scripts to load TSP instance data from a MAT-file (which is extremely faster than Fortran-based extraction).
  2. Algorithm Evaluation
    Each algorithm is evaluated to determine its advantages and disadvantages.
  3. Algorithm Selection
    The best algorithm is selected for hardware implementation, which, in this project, is the Bee Algorithm (BA).
  4. Hardware Bee Algorithm (HBA) Proposal
    Based on FPGA constraints, the project proposes an HBA that is compatible and optimized for hardware. The implementation aims to minimize hardware area while maximizing speed. This is achieved with behavioral-level and structural-level modeling. The implementation process is designed to facilitate testing of different TSP instances.
  5. HDL Implementation
    The project implements the required HDL in VHDL.
  6. MATLAB Support Scripts
    MATLAB scripts necessary for implementation and test benches are developed.
  7. Documentation
    Comprehensive thesis documentation is provided.

Included Documents

1. Thesis (Persian/Farsi)

2. VHDL Cores Details

M-Files & MAT-file Overview

Bee Colony Algorithms (BCAs)

  • BCA_Evaluation.m : Evaluates five Bee Colony Algorithms (BCAs) for solving the TSP, including BA, BCO, BCOi, CABC, and HBA.
  • BA.m : Implements the Bee Algorithm (BA) for solving the TSP.
  • BCO.m : Implements the Constructive Bee Colony Optimization algorithm (BCO) for the TSP.
  • BCOi.m : Implements the Bee Colony Optimization improvement algorithm (BCOi) for the TSP.
  • CABC.m : Implements the Combinatorial Artificial Bee Colony algorithm (CABC) for the TSP.
  • HBA.m : Implements the Hardware Bee Algorithm (HBA) for the TSP.

Common Functions Directory

  • bco_backward_pass.m : Performs the backward pass phase of the Bee Colony Optimization algorithm (BCO/BCOi).
  • compute_tour_distances.m : Computes the Euclidean distances for various scenarios in a TSP.
  • gstm.m : Implements the Greedy Sub-Tour Mutation (GSTM) for TSP optimization.
  • opt2.m : Performs a single iteration of the 2-Opt optimization for TSP.
  • nn_tour.m : Constructs nearest neighbor tours for the TSP.
  • nn_tour_assign.m : Initializes a bee structure using the Nearest Neighbor algorithm.
  • recruited_local_search.m : Applies local optimization to a bee structure.
  • site_abandonment.m : Checks if a site should be abandoned and reinitialized.
  • roulette_wheel.m : Implements the Roulette Wheel Selection method.
  • result_figure.m : Plots the TSP tour and, optionally, the best tour length over iterations.
  • visualize_progress.m : Displays and visualizes the progress of the optimization algorithm for solving the TSP.

Database Directory

  • list_tsp_names.m : Displays a list of TSP instance names in a structured format.
  • read_fortran_tsp_data.m : Reads and processes TSP instance data from Fortran-based files.
  • read_fortran_tsp_instance.m : Reads TSP instance data from Fortran-based files, extracting city coordinates, optimal tour, and optimal tour lengths (if available).
  • tsp_instance.m : Extracts city coordinates, optimal tour, and optimal tour lengths for a given TSP instance from a MAT-file.
  • tsp_data.m : Saves multiple TSP instances in a MAT-file.
  • tsp_data.mat : Contains multiple TSP instances.
  • tsp_instance_info.m : Provides detailed information about a TSP instance and visualizes its optimal tour (if available).

VHDL Directory

  • vhdl_data_constructor.m : Constructs output files required for FPGA test benches and VHDL ROM cores for various TSP instances.

VHDL

This repository contains 88 VHDL files, including synthesizable and test bench files. The full details are provided in RTL_TB.pdf.

HBA for TSP implements the Hardware Bee Algorithm on FPGA for solving the TSP. The local optimization method used is 2-Opt, and all distance/path/tour calculations utilize a heuristic distance matrix. This implementation utilizes FPGA block RAMs. To reduce block RAM usage, an alternative approach is proposed where TSP city coordinates are stored in FPGA block RAMs, and the heuristic distance matrix is constructed at startup on external RAM. This process is described in the “Distance Matrix Constructor on RAM” section.

Key VHDL files and their corresponding schematic/FSM charts are detailed below:

HBA for TSP (Hardware Bee Algorithm for the Traveling Salesperson Problem)

Distance Matrix Constructor on RAM

RAM/ROM

  • TSP_Dist_One_Port_ROM_Sync.vhd : Single-port ROM with synchronous read (Block RAM), containing the TSP distance matrix.
  • TSP_Dist_One_Port_ROM_Sync_TB.vhd : Test bench for the single-port ROM with synchronous read.
  • TSP_X_One_Port_ROM_Sync.vhd : Single-port ROM with synchronous read (Block RAM) for TSP instance X Coordinates (24 Bit).
  • TSP_X_Dual_Port_ROM_Sync.vhd : Dual-port ROM with synchronous read (Block RAM) for TSP instance X Coordinates (24 Bit).
  • TSP_Y_One_Port_ROM_Sync.vhd : Single-port ROM with synchronous read (Block RAM) for TSP instance Y Coordinates (24 Bit).
  • TSP_Y_Dual_Port_ROM_Sync.vhd : Dual-port ROM with synchronous read (Block RAM) for TSP instance Y Coordinates (24 Bit).
  • Xilinx_One_Port_RAM_Sync.vhd : Single-port RAM with synchronous read (Block RAM).
  • Xilinx_Dual_Port_RAM_Sync.vhd : Dual-port RAM with synchronous read (Distributed RAM).
  • Xilinx_Dual_Port_RAM_TB.vhd : Test bench for dual-port RAM with synchronous/asynchronous read (Distributed RAM).

VHDL Usage

To test different TSP instances, replace the TSP_Dist_One_Port_ROM_Sync.vhd file in the /VHDL directory with the desired TSP instance .vhd file with the exact same name, which can be found in the VHDL/TSP/<TSPInstanceName> directory. Moreover, some changes must be made in the Gen_HBA.vhd and Gen_HBA_TB.vhd files. These changes are:

  • Change the generic ADDR_WIDTH in the Gen_HBA.vhd entity part. For instances with fewer than 65 cities, use 11 bits; for instances with 65 to 91 cities, use 12 bits; and for instances with more cities up to 254, increase the address width accordingly.
  • Update the constant Cities to match the number of cities in the TSP instance.
  • In the test bench file, the generic address width is named addr_width and the constant holding the number of cities is city_num; apply the same changes there.
    With these modifications, TSP instances containing up to 254 cities can be tested.

Furthermore, as in the BA (Bee Algorithm), the number of elite and selected local searches can be set using the constants Recruited_Bees_Elite and Recruited_Bees_Selected, respectively. Additionally, the iteration count and local Search (is) parameters are specified using the constants Iterations and Local_Iter.

Note: All default configurations are set for the eil51 instance and ready for testing.

Directory Structure

This repository is organized as follows:

  • Docs/ – Contains the thesis file and detailed VHDL file descriptions (RTL_TB).
  • Figure/ – Contains schematics, FSM charts, module diagrams, and other figures that illustrate the FPGA implementation.
  • Matlab/ – Contains MATLAB scripts, MAT-file, and database-related files.
    • ~/Common/ – Contains common functions used by the BCAs (Bee Colony Algorithms) implementations.
    • ~/Database/ – Contains MAT-files associated with the TSPLIB95 database.
      • ~/TSPLIB95/ – Includes the TSP instance coordinations directory, optimal tour directory, and extracted TSP instance data (obtained from Fortran files and saved as text files).
        • ~/Database.tour/ – Contains the Fortran .tour.tsp files with the TSP optimal tours.
        • ~/Database.tsp/ – Contains the Fortran .tsp files with the TSP city coordinates.
        • ~/Database.txt/ – Contains TSP instance data in separate text files for each instance.
        • Known_Optimal_Tour_Lengths.txt – A text file containing the optimal tour lengths for symmetric TSP instances.
        • tsp_data.txt – A text file containing all TSP instance data used to generate the tsp_data.m script.
    • ~/VHDL/ – Contains MATLAB files related to VHDL and FPGA implementation.
      • ~/Output/ – Contains the constructed files that are used in the VHDL test benches and for ROM construction.
  • VHDL/ – Contains the main RTL and test bench files for implementing the HBA on the FPGA.
    • ~/Basics – Contains basic HDL files for implementing fundamental digital components used in the structural-level design.
    • ~/RXM – Contains various memory modules (RAM/ROM) for the FPGA. Some of these modules were used in the project, while others are provided for diversity.
    • ~/TSP – Contains VHDL or text files related to TSP instances, which were used for implementation or in test benches for application verification.

Databases

This project was evaluated using the TSPLIB95 database:

TSPLIB95 is a comprehensive library of sample instances for the Traveling Salesman Problem (TSP) and related combinatorial optimization problems. Originally compiled by Gerhard Reinelt at Heidelberg University, TSPLIB95 includes a wide range of instances from various sources, including both symmetric and asymmetric TSPs.

Final Thoughts

This project presents an implementation of the Hardware Bee Algorithm (HBA) on FPGA for solving the Traveling Salesperson Problem. It includes MATLAB scripts for various Bee Colony Algorithms (BCAs) that support two local search methods and can extract TSP instance data from both Fortran-based files and pre-saved MAT-files. The repository also includes VHDL files, comprehensive documentation, and references to ensure reproducibility and to support further research.

Contributions and suggestions are welcome! 😊

About

Implementation of Hardware Bee Algorithm (HBA) on FPGA for solving the Traveling Salesperson Problem (TSP) (M.S. Thesis)

Topics

fpga matlab vhdl xilinx-fpga swarm-intelligence bco ba altera-fpga hba bcoi cabc

Resources

Readme
Activity

Stars

0 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages