الگوریتم بهینه سازی کلونی مورچگان در جاوا — راهنمای کاربردی

1private double c = 1.0;
2private double alpha = 1;
3private double beta = 5;
4private double evaporation = 0.5;
5private double Q = 500;
6private double antFactor = 0.8;
7private double randomFactor = 0.01;

1public void visitCity(int currentIndex, int city) {
2    trail[currentIndex + 1] = city;
3    visited[city] = true;
4}
5 
6public boolean visited(int i) {
7    return visited[i];
8}
9 
10public double trailLength(double graph[][]) {
11    double length = graph[trail[trailSize - 1]][trail[0]];
12    for (int i = 0; i < trailSize - 1; i++) {
13        length += graph[trail[i]][trail[i + 1]];
14    }
15    return length;
16}

1graph = generateRandomMatrix(noOfCities);
2numberOfCities = graph.length;
3numberOfAnts = (int) (numberOfCities * antFactor);
4 
5trails = new double[numberOfCities][numberOfCities];
6probabilities = new double[numberOfCities];
7ants = new Ant[numberOfAnts];
8IntStream.range(0, numberOfAnts).forEach(i -> ants.add(new Ant(numberOfCities)));

1public void setupAnts() {
2    IntStream.range(0, numberOfAnts)
3      .forEach(i -> {
4          ants.forEach(ant -> {
5              ant.clear();
6              ant.visitCity(-1, random.nextInt(numberOfCities));
7          });
8      });
9    currentIndex = 0;
10}

1IntStream.range(0, maxIterations).forEach(i -> {
2    moveAnts();
3    updateTrails();
4    updateBest();
5});

1int t = random.nextInt(numberOfCities - currentIndex);
2if (random.nextDouble() < randomFactor) {
3    OptionalInt cityIndex = IntStream.range(0, numberOfCities)
4      .filter(i -> i == t && !ant.visited(i))
5      .findFirst();
6    if (cityIndex.isPresent()) {
7        return cityIndex.getAsInt();
8    }
9}

1public void calculateProbabilities(Ant ant) {
2    int i = ant.trail[currentIndex];
3    double pheromone = 0.0;
4    for (int l = 0; l < numberOfCities; l++) {
5        if (!ant.visited(l)){
6            pheromone
7              += Math.pow(trails[i][l], alpha) * Math.pow(1.0 / graph[i][l], beta);
8        }
9    }
10    for (int j = 0; j < numberOfCities; j++) {
11        if (ant.visited(j)) {
12            probabilities[j] = 0.0;
13        } else {
14            double numerator
15              = Math.pow(trails[i][j], alpha) * Math.pow(1.0 / graph[i][j], beta);
16            probabilities[j] = numerator / pheromone;
17        }
18    }
19}

1public void calculateProbabilities(Ant ant) {
2    int i = ant.trail[currentIndex];
3    double pheromone = 0.0;
4    for (int l = 0; l < numberOfCities; l++) {
5        if (!ant.visited(l)){
6            pheromone
7              += Math.pow(trails[i][l], alpha) * Math.pow(1.0 / graph[i][l], beta);
8        }
9    }
10    for (int j = 0; j < numberOfCities; j++) {
11        if (ant.visited(j)) {
12            probabilities[j] = 0.0;
13        } else {
14            double numerator
15              = Math.pow(trails[i][j], alpha) * Math.pow(1.0 / graph[i][j], beta);
16            probabilities[j] = numerator / pheromone;
17        }
18    }
19}

1double r = random.nextDouble();
2double total = 0;
3for (int i = 0; i < numberOfCities; i++) {
4    total += probabilities[i];
5    if (total >= r) {
6        return i;
7    }
8}

1public void updateTrails() {
2    for (int i = 0; i < numberOfCities; i++) {
3        for (int j = 0; j < numberOfCities; j++) {
4            trails[i][j] *= evaporation;
5        }
6    }
7    for (Ant a : ants) {
8        double contribution = Q / a.trailLength(graph);
9        for (int i = 0; i < numberOfCities - 1; i++) {
10            trails[a.trail[i]][a.trail[i + 1]] += contribution;
11        }
12        trails[a.trail[numberOfCities - 1]][a.trail[0]] += contribution;
13    }
14}

1private void updateBest() {
2    if (bestTourOrder == null) {
3        bestTourOrder = ants[0].trail;
4        bestTourLength = ants[0].trailLength(graph);
5    }
6    for (Ant a : ants) {
7        if (a.trailLength(graph) < bestTourLength) {
8            bestTourLength = a.trailLength(graph);
9            bestTourOrder = a.trail.clone();
10        }
11    }
12}