Slime Mould Algorithm to find shortest path in a list of coordinates

slime-mould-algorithm.js

function findShortestPath(coordinates, populationSize, maxIterations) {
  // Initialize the positions of slime mould
  const positions = [];
  let bestFitness = Number.MAX_VALUE;
  let bestPosition;

  for (let i = 0; i < populationSize; i++) {
    const position = coordinates.slice(); // Make a copy of the coordinates array
    positions.push(position);
  }

  // Calculate the fitness of all slime mould
  function calculateFitness(positions) {
    const fitnessValues = [];

    for (let i = 0; i < positions.length; i++) {
      const position = positions[i];

      // Calculate fitness as the total distance of the path
      let fitness = 0;
      for (let j = 1; j < position.length; j++) {
        const lat1 = position[j - 1].latitude;
        const lon1 = position[j - 1].longitude;
        const lat2 = position[j].latitude;
        const lon2 = position[j].longitude;

        // Calculate the distance between two coordinates using a suitable formula (e.g., Haversine formula)
        const distance = calculateDistance(lat1, lon1, lat2, lon2);

        fitness += distance;
      }

      fitnessValues.push(fitness);
    }

    return fitnessValues;
  }

  // Update positions using SMA algorithm
  function updatePositions(positions) {
    for (let i = 0; i < populationSize; i++) {
      const position = positions[i];

      // Calculate p, vb, and vc based on equations provided
      const p = Math.tanh(Math.abs(calculateFitness(positions)[i] - bestFitness));
      const vb = Math.random() * 2 - 1;
      const vc = 1 - (i / populationSize);

      // Update the position using the SMA equation
      if (Math.random() < p) {
        const xa = positions[Math.floor(Math.random() * populationSize)];
        const xb = positions[Math.floor(Math.random() * populationSize)];

        // Swap a random segment of the path between xa and xb
        const start = Math.floor(Math.random() * (position.length - 1));
        const end = Math.floor(Math.random() * (position.length - start - 1)) + start + 1;
        const segment = position.slice(start, end);
        xa.splice(start, segment.length, ...segment);
        xb.splice(start, segment.length, ...segment);
      } else {
        // Shrink the path towards the initial position
        for (let j = 1; j < position.length; j++) {
          position[j].latitude *= vc;
          position[j].longitude *= vc;
        }
      }
    }
  }

  // Calculate the distance between two coordinates using the Haversine formula
  function calculateDistance(lat1, lon1, lat2, lon2) {
    const earthRadius = 6371; // Earth's radius in kilometers

    const dLat = degToRad(lat2 - lat1);
    const dLon = degToRad(lon2 - lon1);

    const a =
      Math.sin(dLat / 2) * Math.sin(dLat / 2) +
      Math.cos(degToRad(lat1)) * Math.cos(degToRad(lat2)) *
      Math.sin(dLon / 2) * Math.sin(dLon / 2);

    const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

    const distance = earthRadius * c;

    return distance;
  }

  // Convert degrees to radians
  function degToRad(degrees) {
    return degrees * (Math.PI / 180);
  }

  // Run the SMA algorithm
  for (let iteration = 0; iteration < maxIterations; iteration++) {
    // Calculate fitness for all positions
    const fitnessValues = calculateFitness(positions);

    // Find the best fitness value and its corresponding position
    for (let i = 0; i < populationSize; i++) {
      if (fitnessValues[i] < bestFitness) {
        bestFitness = fitnessValues[i];
        bestPosition = positions[i];
      }
    }

    // Update positions using SMA algorithm
    updatePositions(positions);
  }

  // Return the best fitness value and position (shortest path)
  return {
    bestFitness,
    bestPosition
  };
}


// Example usage of Slime Mould Algorithm
// to find shortest path in a list of coordinates.
const coordinates = [
  { latitude: 52.520008, longitude: 13.404954 }, // Berlin
  { latitude: 48.8566, longitude: 2.3522 }, // Paris
  { latitude: 51.5074, longitude: -0.1278 }, // London
  { latitude: 41.9028, longitude: 12.4964 }, // Rome
  { latitude: 40.7128, longitude: -74.0060 }, // New York
];
const populationSize = 150;
const maxIterations = 150;

const result = findShortestPath(
	coordinates,
    populationSize,
    maxIterations
);
// console.log(result)

slime-mould-algorithm.py

import math
import random

def find_shortest_path(coordinates, population_size, max_iterations):
    # Initialize the positions of slime mould
    positions = []
    best_fitness = float("inf")
    best_position = None

    for _ in range(population_size):
        position = coordinates.copy()  # Make a copy of the coordinates list
        positions.append(position)

    # Calculate the fitness of all slime mould
    def calculate_fitness(positions):
        fitness_values = []

        for position in positions:
            # Calculate fitness as the total distance of the path
            fitness = 0
            for j in range(1, len(position)):
                lat1 = position[j - 1]["latitude"]
                lon1 = position[j - 1]["longitude"]
                lat2 = position[j]["latitude"]
                lon2 = position[j]["longitude"]

                # Calculate the distance between two coordinates using the Haversine formula
                distance = calculate_distance(lat1, lon1, lat2, lon2)

                fitness += distance

            fitness_values.append(fitness)

        return fitness_values

    # Update positions using SMA algorithm
    def update_positions(positions):
        nonlocal best_fitness

        for i in range(population_size):
            position = positions[i]

            # Calculate p, vb, and vc based on equations provided
            p = math.tanh(math.fabs(calculate_fitness(positions)[i] - best_fitness))
            vb = random.uniform(-1, 1)
            vc = 1 - (i / population_size)

            # Update the position using the SMA equation
            if random.random() < p:
                xa = positions[random.randint(0, population_size - 1)]
                xb = positions[random.randint(0, population_size - 1)]

                # Swap a random segment of the path between xa and xb
                start = random.randint(0, len(position) - 2)
                end = random.randint(start + 1, len(position) - 1)
                segment = position[start:end]
                xa[start:start + len(segment)] = segment
                xb[start:start + len(segment)] = segment
            else:
                # Shrink the path towards the initial position
                for j in range(1, len(position)):
                    position[j]["latitude"] *= vc
                    position[j]["longitude"] *= vc

    # Calculate the distance between two coordinates using the Haversine formula
    def calculate_distance(lat1, lon1, lat2, lon2):
        earth_radius = 6371  # Earth's radius in kilometers

        d_lat = deg_to_rad(lat2 - lat1)
        d_lon = deg_to_rad(lon2 - lon1)

        a = math.sin(d_lat / 2) ** 2 + math.cos(deg_to_rad(lat1)) * math.cos(deg_to_rad(lat2)) * math.sin(d_lon / 2) ** 2
        c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))

        distance = earth_radius * c

        return distance

    # Convert degrees to radians
    def deg_to_rad(degrees):
        return degrees * (math.pi / 180)

    # Run the SMA algorithm
    for iteration in range(max_iterations):
        # Calculate fitness for all positions
        fitness_values = calculate_fitness(positions)

        # Find the best fitness value and its corresponding position
        for i in range(population_size):
            if fitness_values[i] < best_fitness:
                best_fitness = fitness_values[i]
                best_position = positions[i]

        # Update positions using SMA algorithm
        update_positions(positions)

    # Return the best fitness value and position (shortest path)
    return {
        "bestFitness": best_fitness,
        "bestPosition": best_position
    }


# Example usage of Slime Mould Algorithm
# to find the shortest path in a list of coordinates
coordinates = [
    {"latitude": 52.520008, "longitude": 13.404954},  # Berlin
    {"latitude": 48.8566, "longitude": 2.3522},  # Paris
    {"latitude": 51.5074, "longitude": -0.1278},  # London
    {"latitude": 41.9028, "longitude": 12.4964},  # Rome
    {"latitude": 40.7128, "longitude": -74.0060},  # New York
]
population_size = 150
max_iterations = 150

result = find_shortest_path(coordinates, population_size, max_iterations)
print("Best Fitness:", result["bestFitness"])
print("Best Position (Shortest Path):", result["bestPosition"])