Progress Blog Post 3

Ant Colony Optimization

Over the last month, the ant colony optimization has been implemented into the program. An ant colony optimization finds the quickest path by simulating the way in which ant colonies seek out and find food. There are many variations upon the original Ant Colony Optimization algorithm, and research indicated that the best variation for this project would be the MMAX algorithm. The steps for each iteration of the optimization are as follows:

Step 1: Ants Seek Goal

Each iteration, or crawling round, starts with all of the ants at the starting node. At this node, along with every other node following, the ant has a decision procedure to decide which of edges to choose for its next advancement. The decision procedure combines an affinity for travelling towards the destination node, a preference for travelling in faster directions, a tendency to choose paths with more pheromones (where ants have traveled recently), a desire not to reverse directions, and a healthy amount of randomness. The randomness allows for the discovery of new and better paths. All of the above criteria are taken into account and the ant stochastically selects a direction of advancement. This decision is completed for every ant until each ant has reached the destination.

Step 2: Evaluate Quickest Time

Once all of the ants have reached the destination node, their travel times are evaluated. The first step of this evaluation is to remove loops from the paths of the ants. Once that is complete, the ant retraces the loop-free path, but this time, it evaluates its time to reach the destination and reports the value back to the program. The best path of the iteration is saved and the rest are discarded.

Step 3: Update Pheromone Trails

The final step is to update the pheromones of all of the edges in the connected grid. This is where the MMAX variation differs compared to other variations of the Ant Colony Optimization. In this variation, only the best ant lays down pheromones upon its return. The pheromone addition is deposited in a strength proportional to the speed of the path. All other edges experience an evaporation of pheromones. Finally, any edges with ratios above or below a defined threshold are readjusted to minimal and maximal values.

Once step three is complete, the algorithm starts again at Step 1 and cycles through the steps continually until told to stop, usually after 500 iterations. A snapshot of the program during the ant colony optimization is included below. Once the ant colony optimization is complete, a local search optimization takes place which no longer relies on nodes, but optimizes the path on a continuous field. For the sake of brevity, the details of the local search optimization will be found in a future publication.

ACO_in_action
A screenshot of the optimization in progress. This was taken during iteration 8 of 500. The jagged lines are typical of paths in the early stages of optimization. Future iterations improve the path greatly.

Validation of Data

In the reference dataset, we filter the available reference maritime routes with both departure dates and arriving dates for the use of validation. Several source excel files have been created for the reference data recognition. Port source excel file stores all of the ports including departure ports, destination ports, and passing by ports with their parameters of longitude and latitude. Search source excel file stores all the available traveling parameters including ports’ names, ship sizes, ship owners, ship captains, departure dates with arriving dates, routes with respectively each passing by port, and travelling cost.

Then a program was created to read the reference data. Firstly the programs search in the search source file to find the destination port and the route. Secondly it gets all these ports’ longitude and latitude by searching in port source file and gains the reference maritime routing ports on the map. Then the programs read the corresponding parameters in the search source file respected to the reference route, including the all of the associated information and output them, along with traveling time, for the reference route. Then the travelling times are ranked to do the trend analysis. If fruitful, results of the trend analysis will be included in the final report and presentation of the project.

Next Steps

  • Completing validation of optimization algorithm
  • Adding a GUI at the end which allows the path to be viewed along with wind and water current data
  • Trying to find a way to load the program to the Venice Atlas blog
  • Writing abstract and completing poster