Algoritmos de Colonia de Formigas
Por: Pablo Eduardo Souza • 30/6/2019 • Pesquisas Acadêmicas • 1.237 Palavras (5 Páginas) • 154 Visualizações
Vamos discutir os principais parâmetros para o algoritmo ACO, declarados na classe AntColonyOptimization :
1
2
3
4
5
6
7
private double c = 1.0;
private double alpha = 1;
private double beta = 5;
private double evaporation = 0.5;
private double Q = 500;
private double antFactor = 0.8;
private double randomFactor = 0.01;
O parâmetro c indica o número original de trilhas, no início da simulação. Além disso, o alfa controla a importância do feromônio, enquanto o beta controla a prioridade da distância. Em geral, o parâmetro beta deve ser maior que alfa para os melhores resultados.
Em seguida, a variável de evaporação mostra o percentual de quanto o feromônio está evaporando em cada iteração, enquanto Q fornece informações sobre a quantidade total de feromônio deixada na trilha por cada formiga , e antFactor nos informa quantas formigas usaremos por cidade.
Finalmente, precisamos ter um pouco de aleatoriedade em nossas simulações, e isso é coberto por randomFactor .
3.2. Criar formigas
Cada formiga poderá visitar uma cidade específica, lembrar de todas as cidades visitadas e acompanhar o comprimento da trilha:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void visitCity(int currentIndex, int city) {
trail[currentIndex + 1] = city;
visited[city] = true;
}
public boolean visited(int i) {
return visited[i];
}
public double trailLength(double graph[][]) {
double length = graph[trail[trailSize - 1]][trail[0]];
for (int i = 0; i < trailSize - 1; i++) {
length += graph[trail[i]][trail[i + 1]];
}
return length;
}
3.3. Configurar formigas
No início, precisamos inicializar nossa implementação de código ACO fornecendo matrizes de trilhas e formigas:
1
2
3
4
5
6
7
8
graph = generateRandomMatrix(noOfCities);
numberOfCities = graph.length;
numberOfAnts = (int) (numberOfCities * antFactor);
trails = new double[numberOfCities][numberOfCities];
probabilities = new double[numberOfCities];
ants = new Ant[numberOfAnts];
IntStream.range(0, numberOfAnts).forEach(i -> ants.add(new Ant(numberOfCities)));
Em seguida, precisamos configurar a matriz das formigas para começar com uma cidade aleatória:
1
2
3
4
5
6
7
8
9
10
public void setupAnts() {
IntStream.range(0, numberOfAnts)
.forEach(i -> {
ants.forEach(ant -> {
ant.clear();
ant.visitCity(-1, random.nextInt(numberOfCities));
});
});
currentIndex = 0;
}
Para cada iteração do loop, executaremos as seguintes operações:
1
2
3
4
5
IntStream.range(0, maxIterations).forEach(i -> {
moveAnts();
updateTrails();
updateBest();
});
3.4. Mover Ants
Vamos começar com o método moveAnts () . Precisamos escolher a próxima cidade para todas as formigas, lembrando que cada formiga tenta seguir as trilhas de outras formigas:
1
2
3
4
5
6
7
8
public void moveAnts() {
IntStream.range(currentIndex,
...