Improving Pheromone Update Performance

[Barbapoulpe]

The pheromone update has quite poor performance as it is now because it loops on the graph matrix (O(n²)), then for each cell (edge), it loops over each ant (potentially O(n) since most papers use a number of ants similar or equal to the number of cities).
An easy improvement would be to treat the evaporation and depositing separately.
for Deposits: loop over the ants and their path (O(n²)) directly depositing the pheromones on the path (O(1))
for Evaporation: loop over the matrix only (O(n²))
Further improvement would be to have those run in parallel (parallelization of the evaporation is quite simple as there should be no racing conflicts but for the deposits a locking mechanism on the edges would be necessary as several ants can use the same edge in their paths)

[Barbapoulpe]

public class ImprovedPartialDeposit extends PartialDeposit{
        private int resetValue;
	double[][] deposits;
	public ImprovedPartialDeposit(ACO aco, double rate, AbstractSubSet subSet) {
		super(aco, rate, subSet);
		this.deposits=new double[aco.getProblem().getNumberOfNodes()] [aco.getProblem().getNumberOfNodes()];
                resetValue=aco.getProblem().getNumberOfNodes();

	}
	private void resetPheromones() {
		for(int i=0; i<deposits.length;i++) {
			for(int j=0;j<deposits[i].length;j++) {
				deposits[i][j]=0;
			}
		}
		calcDeposits();
	}
	public double getTheNewValue(int i, int j) {
		if(i<resetValue) resetPheromones();
		resetValue=i;
		return aco.getGraph().getTau(i, j) + rate * deposits[i][j];
		
	}
	private void calcDeposits() {
		int nNodes=aco.getProblem().getNumberOfNodes();
		for(Ant a: subSet.getSubSet()) {
			for(int k=0;k<nNodes;k++) {
				int i=a.getSolution()[k];
				int j=a.getSolution()[(k+1)%nNodes];
				double deltaTau=aco.getProblem().getDeltaTau(a.getTourLength(), i, j);
				if(a.path[i][j]==1) {
					deposits[i][j]+= deltaTau;
				}
				if(a.path[j][i]==1) {
					deposits[j][i]+= deltaTau;
				}
			}
		}
	}
} 

seems to work with minimal change to the code and improves the run time drastically (tested on a280.tsp).

Edit: fixed formatting of code and now correctly uses only the ants from the subset
Edit2: now supports asymetric TSP

[Barbapoulpe]

Hello @thiagodnf I edited the code to now support asymetric problems (under the assumption that for Symetric problems, the path[j][i] of ants is set to one when the path[i][j] is - another way to handle Asymetric problems would be to use a boolean in the Problem Class). The way it was implemented, it thought that you only made it work with symetrical problems as the updatePheromones() method in the ACO class explicitely sets the pheromone value on edge (j,i) to be that of (i,j). 2018-07-09 22:53 GMT+02:00 Thiago Nascimento <[email protected]>:

…

Hello @Barbapoulpe <https://github.com/Barbapoulpe> Thanks for your suggestion. I took some time to understand what you sent me. I guess I cannot implement this in the current code because you are considering that the "deltaTau" values are the same for i -> j and j -> i I am not sure if the behavior is "default" for all problems (is it default?). I can see it for TSP and other problems but not for everyone. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#3 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AnF5Wd_WfmhoQ9X833gohfKwMH2kb01kks5uE8LZgaJpZM4VHSJc> .