Bookmark this: tool.io/optimization/ant-colony-tsp/source-code
Ant Colony TSP Solver Source Code
Browse the implementation files for Ant Colony TSP Solver.tool.ts typescript
// Tool: Ant Colony TSP Solver
interface Point {
x: number;
y: number;
}
const MAX_ANTS = 500;
const MAX_ITERATIONS = 1_000;
const MAX_POINTS = 100;
const MAX_WORK = 20_000_000;
const parseFiniteNumber = (input: unknown): number | null => {
if (
(typeof input !== 'string' && typeof input !== 'number') ||
(typeof input === 'string' && input.trim() === '')
) {
return null;
}
const value = Number(input);
return Number.isFinite(value) ? value : null;
};
const parsePositiveInteger = (
input: unknown,
maximum: number
): number | null => {
const value = parseFiniteNumber(input);
return value !== null &&
Number.isSafeInteger(value) &&
value >= 1 &&
value <= maximum
? value
: null;
};
const parsePoints = (input: unknown): Point[] | null => {
if (typeof input !== 'string' || input.trim() === '')
return null;
try {
const points: unknown = JSON.parse(input);
if (
!Array.isArray(points) ||
points.length < 3 ||
points.length > MAX_POINTS
) {
return null;
}
const parsed = points.map((point) => {
if (
Array.isArray(point) &&
point.length === 2 &&
point.every(
(value) =>
typeof value === 'number' && Number.isFinite(value)
)
) {
return { x: point[0], y: point[1] };
}
return null;
});
if (parsed.some((point) => point === null)) return null;
const validPoints = parsed as Point[];
const unique = new Set(
validPoints.map(({ x, y }) => `${x}\u0000${y}`)
);
return unique.size === validPoints.length
? validPoints
: null;
} catch {
return null;
}
};
const createRandom = (seed: string): (() => number) => {
let state = 2166136261;
for (let index = 0; index < seed.length; index += 1) {
state ^= seed.charCodeAt(index);
state = Math.imul(state, 16777619);
}
return () => {
state += 0x6d2b79f5;
let value = state;
value = Math.imul(value ^ (value >>> 15), value | 1);
value ^=
value + Math.imul(value ^ (value >>> 7), value | 61);
return ((value ^ (value >>> 14)) >>> 0) / 4294967296;
};
};
const round = (value: number): number =>
Number(value.toPrecision(12));
export const solveAntColonyTsp = (
pointsInput: unknown,
antCountInput: unknown,
iterationCountInput: unknown,
pheromonePowerInput: unknown,
distancePowerInput: unknown,
evaporationInput: unknown,
depositInput: unknown,
seedInput: unknown
): string => {
const points = parsePoints(pointsInput);
const antCount = parsePositiveInteger(
antCountInput,
MAX_ANTS
);
const iterationCount = parsePositiveInteger(
iterationCountInput,
MAX_ITERATIONS
);
const pheromonePower = parseFiniteNumber(pheromonePowerInput);
const distancePower = parseFiniteNumber(distancePowerInput);
const evaporation = parseFiniteNumber(evaporationInput);
const deposit = parseFiniteNumber(depositInput);
if (
points === null ||
antCount === null ||
iterationCount === null ||
pheromonePower === null ||
pheromonePower < 0 ||
pheromonePower > 10 ||
distancePower === null ||
distancePower <= 0 ||
distancePower > 20 ||
evaporation === null ||
evaporation <= 0 ||
evaporation > 1 ||
deposit === null ||
deposit <= 0 ||
deposit > 1_000_000_000_000 ||
typeof seedInput !== 'string' ||
seedInput.trim() === '' ||
antCount * iterationCount * points.length * points.length >
MAX_WORK
) {
return '';
}
const size = points.length;
const distances = Array.from({ length: size }, () =>
new Array<number>(size).fill(0)
);
for (let first = 0; first < size; first += 1) {
for (let second = first + 1; second < size; second += 1) {
const distance = Math.hypot(
points[first].x - points[second].x,
points[first].y - points[second].y
);
if (!Number.isFinite(distance) || distance <= 0)
return '';
distances[first][second] = distance;
distances[second][first] = distance;
}
}
const pheromones = Array.from({ length: size }, () =>
new Array<number>(size).fill(1)
);
const random = createRandom(seedInput);
let bestTour: number[] = [];
let bestDistance = Infinity;
const bestByIteration: number[] = [];
const tourDistance = (tour: number[]): number =>
tour.reduce((total, city, index) => {
const next = tour[(index + 1) % tour.length];
return total + distances[city][next];
}, 0);
for (
let iteration = 0;
iteration < iterationCount;
iteration += 1
) {
const tours: Array<{ distance: number; tour: number[] }> =
[];
for (let ant = 0; ant < antCount; ant += 1) {
const start = Math.floor(random() * size);
const tour = [start];
const unvisited = new Set(
Array.from({ length: size }, (_, index) => index)
);
unvisited.delete(start);
while (unvisited.size > 0) {
const current = tour.at(-1)!;
const candidates = [...unvisited];
const weights = candidates.map(
(candidate) =>
pheromones[current][candidate] ** pheromonePower *
(1 / distances[current][candidate]) ** distancePower
);
const total = weights.reduce(
(sum, weight) => sum + weight,
0
);
if (!Number.isFinite(total) || total <= 0) return '';
let threshold = random() * total;
let selected = candidates.at(-1)!;
for (
let index = 0;
index < candidates.length;
index += 1
) {
threshold -= weights[index];
if (threshold <= 0) {
selected = candidates[index];
break;
}
}
tour.push(selected);
unvisited.delete(selected);
}
const distance = tourDistance(tour);
tours.push({ distance, tour });
if (distance < bestDistance) {
bestDistance = distance;
bestTour = [...tour];
}
}
for (let first = 0; first < size; first += 1) {
for (let second = 0; second < size; second += 1) {
pheromones[first][second] = Math.max(
Number.EPSILON,
pheromones[first][second] * (1 - evaporation)
);
}
}
for (const { distance, tour } of tours) {
const amount = deposit / distance;
if (!Number.isFinite(amount)) return '';
for (let index = 0; index < tour.length; index += 1) {
const first = tour[index];
const second = tour[(index + 1) % tour.length];
pheromones[first][second] += amount;
pheromones[second][first] += amount;
}
}
bestByIteration.push(round(bestDistance));
}
if (
!Number.isFinite(bestDistance) ||
bestTour.length !== size
) {
return '';
}
return JSON.stringify(
{
bestByIteration,
bestDistance: round(bestDistance),
bestTour: [...bestTour, bestTour[0]],
seed: seedInput
},
null,
2
);
};
export const Tool: TypeTool = {
name: 'Ant Colony TSP Solver',
slug: 'optimization/ant-colony-tsp',
intro:
'Approximate a short traveling-salesperson tour with seeded Ant System pheromone updates.',
tool: solveAntColonyTsp,
i: [
{
example: '[[0,0],[1,0],[1,1],[0,1]]',
label: 'Points',
placeholder: 'JSON array of unique [x, y] coordinates',
render: 'textarea',
type: 'text',
value: '[[0,0],[1,0],[1,1],[0,1]]'
},
{
example: '20',
label: 'Ants',
placeholder: 'Number of ants per iteration',
type: 'number',
value: 20
},
{
example: '100',
label: 'Iterations',
placeholder: 'Number of optimization iterations',
type: 'number',
value: 100
},
{
example: '1',
label: 'Pheromone Power',
placeholder: 'Non-negative pheromone influence',
type: 'number',
value: 1
},
{
example: '2',
label: 'Distance Power',
placeholder: 'Positive inverse-distance influence',
type: 'number',
value: 2
},
{
example: '0.5',
label: 'Evaporation',
placeholder: 'Evaporation rate above 0 and up to 1',
type: 'number',
value: 0.5
},
{
example: '1',
label: 'Deposit',
placeholder: 'Positive pheromone deposit scale',
type: 'number',
value: 1
},
{
example: 'tool.io',
label: 'Seed',
placeholder: 'Seed for reproducible tours',
type: 'text',
value: 'tool.io'
}
],
o: [
{
example:
'{ "bestDistance": 4, "bestTour": [0, 1, 2, 3, 0] }',
label: 'Best Tour',
placeholder: 'Best ant-colony tour will appear here...',
render: 'textarea',
type: 'text'
}
],
cite: [
{
title:
'Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem',
url: 'https://doi.org/10.1109/4235.585892'
},
{
title: 'Ant colony optimization algorithms — Wikipedia',
url: 'https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms'
}
]
};
export default Tool;
Description
Browse the implementation files for Ant Colony TSP Solver.