Skip to content

Instantly share code, notes, and snippets.

@darkterminal
Created July 14, 2023 05:38
Show Gist options
  • Save darkterminal/bbb64d92e34b2d0f1bb95747cf21f8b5 to your computer and use it in GitHub Desktop.
Save darkterminal/bbb64d92e34b2d0f1bb95747cf21f8b5 to your computer and use it in GitHub Desktop.
Slime Mould Algorithm to find shortest path in a list of coordinates
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)
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"])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment