Notes

import 'dart:js_util';
import 'dart:math';
import 'dart:core';

class AntColonyProgram {
var random = new Random(0);
// influence of pheromone on direction
var alpha = 3;
// influence of adjacent node distance
var beta = 2;

// pheromone decrease factor
var rho = 0.01;
// pheromone increase factor
var Q = 2.0;

void Main() {
print("nBegin Ant Colony Optimization demon");

var numCities = 60;
var numAnts = 4;
var maxTime = 1000;

print("Number cities in problem = $numCities");

print("nNumber ants = $numAnts");
print("Maximum time = $maxTime");

print("nAlpha (pheromone influence) = $alpha");
print("Beta (local node influence) = $beta");
print(
"Rho (pheromone evaporation coefficient) = ${rho.toStringAsFixed(2)}");
print("Q (pheromone deposit factor) = ${Q.toStringAsFixed(2)}");

print("nInitialing dummy graph distances");
List<List<int>> dists = MakeGraphDistances(numCities);

print("nInitialing ants to random trailsn");
List<List<int>> ants = InitAnts(numAnts, numCities);
// initialize ants to random trails
ShowAnts(ants, dists);

List<int> bestTrail = BestTrail(ants, dists);
// determine the best initial trail
var bestLength = Length(bestTrail, dists);
// the length of the best trail

print("nBest initial trail length: ${bestLength.toStringAsFixed(1)}");
//Display(bestTrail);

print("nInitializing pheromones on trails");
List<List<double>> pheromones = InitPheromones(numCities);

var time = 0;
print("nEntering UpdateAnts - UpdatePheromones loopn");
while (time < maxTime) {
UpdateAnts(ants, pheromones, dists);
UpdatePheromones(pheromones, ants, dists);

List<int> currBestTrail = BestTrail(ants, dists);
var currBestLength = Length(currBestTrail, dists);
if (currBestLength < bestLength) {
bestLength = currBestLength;
bestTrail = currBestTrail;
print(
"New best length of ${bestLength.toStringAsFixed(2)} found at time $time");
}
time += 1;
}

print("nTime complete");

print("nBest trail found:");
print("$bestTrail");
print("nLength of best trail found: ${bestLength.toStringAsFixed(2)}");

print("nEnd Ant Colony Optimization demon");
}
}
// Main

// --------------------------------------------------------------------------------------------

InitAnts(var numAnts, var numCities) {
var random = new Random();
List<List<int>> ants = new List.generate(numAnts, (index) => <int>[]);
for (var k = 0; k <= numAnts - 1; k++) {
var start = random.nextInt(numCities);
ants[k] = RandomTrail(start, numCities);
}
return ants;
}

RandomTrail(var start, var numCities) {
// helper for InitAnts
List<int> trail = List<int>.filled(numCities, 0);
;

// sequential
for (var i = 0; i <= numCities - 1; i++) {
trail[i] = i;
}

// Fisher-Yates shuffle
for (var i = 0; i <= numCities - 1; i++) {
var random = new Random();
var r = random.nextInt(i - int.parse(numCities));
var tmp = trail[r];
trail[r] = trail[i];
trail[i] = tmp;
}

var idx = IndexOfTarget(trail, start);
// put start at [0]
var temp = trail[0];
trail[0] = trail[idx];
trail[idx] = temp;

return trail;
}

IndexOfTarget(List<int> trail, var target) {
// helper for RandomTrail
for (var i = 0; i <= trail.length - 1; i++) {
if (trail[i] == target) {
return i;
}
}
throw new Exception("Target not found in IndexOfTarget");
}

Length(List<int> trail, List<List<int>> dists) {
// total length of a trail
var result = 0.0;
for (var i = 0; i <= trail.length - 2; i++) {
result += Distance(trail[i], trail[i + 1], dists);
}
return result;
}

// --------------------------------------------------------------------------------------------

BestTrail(List<List<int>> ants, List<List<int>> dists) {
// best trail has shortest total length
var bestLength = Length(ants[0], dists);
var idxBestLength = 0;
for (var k = 1; k <= ants.length - 1; k++) {
var len = Length(ants[k], dists);
if (len < bestLength) {
bestLength = len;
idxBestLength = k;
}
}
var numCities = ants[0].length;
//INSTANT VB NOTE: The local variable bestTrail was renamed since Visual Basic will not allow local variables with the same name as their enclosing function or property:
List<int> bestTrail_Renamed = List.filled(numCities, 0);
;
ants[idxBestLength].setAll(0, bestTrail_Renamed);
return bestTrail_Renamed;
}

// --------------------------------------------------------------------------------------------

InitPheromones(var numCities) {
List<List<double>> pheromones = List<List<double>>.filled(
numCities, List.generate(numCities, (i) => 0.0));
for (var i = 0; i <= numCities - 1; i++) {
pheromones[i] = List<double>.filled(numCities, 0.0);
}
for (var i = 0; i <= pheromones.length - 1; i++) {
for (var j = 0; j <= pheromones[i].length - 1; j++) {
pheromones[i][j] = 0.01;
// otherwise first call to UpdateAnts -> BuiuldTrail -> NextNode -> MoveProbs => all 0.0 => throws
}
}
return pheromones;
}

// --------------------------------------------------------------------------------------------

UpdateAnts(List<List<int>> ants, List<List<double>> pheromones,
List<List<int>> dists) {
var numCities = pheromones.length;
var random = new Random();
for (var k = 0; k <= ants.length - 1; k++) {
var start = random.nextInt(numCities);
List<int> newTrail = BuildTrail(k, start, pheromones, dists);
ants[k] = newTrail;
}
}

BuildTrail(
var k, var start, List<List<double>> pheromones, List<List<int>> dists) {
var numCities = pheromones.length;
List<int> trail = List<int>.filled(numCities, 0);
List<bool> visited = List<bool>.filled(numCities, true);
trail[0] = start;
visited[start] = true;
for (var i = 0; i <= numCities - 2; i++) {
var cityX = trail[i];
var next = NextCity(k, cityX, visited, pheromones, dists);
trail[i + 1] = next;
visited[next] = true;
}
return trail;
}