In bjhufstetler/LeapFrog: LeapFrog for TSP

knitr::opts_chunk$set(echo = TRUE)

Overview

LeapFrog is a single agent metaheuristic search algorithm for solving the Travelling Salesman Problem. LeapFrog can be used with non-symmetrical distance matrices, coordinate matrices, or both. The solution method can easily be expanded to solve for other types of shortest-path problems.

Given a distance matrix, coordinate matrix, or both, the LeapFrog::ImportData() function will create a LeapFrog class object that can then be used with the LeapFrog algorithm function LeapFrog::LF().

Parameters

The LeapFrog algorithm offers the following tunable parameters:

• m: The number of games to be played by the algorithms [1, inf)
• r: The number of rounds in each game [1, inf)
• p: The percentage of available nodes removed in each round (0, 1]
• s: The accuracy of player landing positions in the first round of each game (0, 1]
• a: The decay rate of p as a game is played (0, 1]
• monitor: If TRUE, will print a status message after each game [T, F]

Example

Create LeapFrog Class Object

LeapFrog comes with 13 different known TSP instances, sourced from the TSPLIB [@reinelt1991tsplib]. They can be called using

LeapFrogObject <- LeapFrog::GetData(1)

or by using the function

LeapFrog::ImportData(distances = yourDistanceMatrix, coordinates = yourCoordinateMatrix)

Run the LeapFrog Algorithm

Run the LeapFrog algorithm by passing the LeapFrog class object and any parameters.

LeapFrogOutput <- LeapFrog::LF(LeapFrogObject, m = 10, r = 20, a = .5)

References

bjhufstetler/LeapFrog documentation built on March 19, 2020, 11:51 p.m.