Skip to content

Main content

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.

References

  1. Tool.io on GitHub
  2. Tool.io TypeScript tools library

Similar or alternative tools