Skip to content

Latest commit

 

History

History
56 lines (41 loc) · 4.53 KB

README.md

File metadata and controls

56 lines (41 loc) · 4.53 KB
Raw

Ant Colony Optimization Implementation for a serious emerging games engine in Java

Ant Colony Optimization (ACO)

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial Ants stand for multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of Artificial Ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing.

As an example, Ant colony optimization is a class of optimization algorithms modeled on the actions of an ant colony. Artificial 'ants' (e.g. simulation agents) locate optimal solutions by moving through a parameter space representing all possible solutions. Real ants lay down pheromones directing each other to resources while exploring their environment. The simulated 'ants' similarly record their positions and the quality of their solutions, so that in later simulation iterations more ants locate better solutions. The image below gives an example of the ant system:

alt text

Classic Ant Colony Optimization (ACO) algorithm

In the ant colony optimization algorithms, an artificial ant is a simple computational agent that searches for good solutions to a given optimization problem. To apply an ant colony algorithm, the optimization problem needs to be converted into the problem of finding the shortest path on a weighted graph. In the first step of each iteration, each ant stochastically constructs a solution, i.e. the order in which the edges in the graph should be followed. In the second step, the paths found by the different ants are compared. The last step consists of updating the pheromone levels on each edge.

Algorithm 1 - Pseudo-code for Ant Colony Optimization

Initialize parameters
Initialize pheromone trails
Create ants
while Stopping criteria is not reached do
    Let all ants construct their solution
    Update pheromone trails
    Allow Daemon Actions
end while

The detail of the ACO is the Daemon Actions that can perform problem specific operations or centralized operations, which use global knowledge of the solutions. Examples of operations that can be executed in Daemon Actions are: control the feasibility of each solution, give extra pheromone quantity to the best solutions, use some local search routine to improve the solutions, etc.

ACO algorithm have some building blocks that need to be understanded, and in some cases modeled to specific problems to obtain best results. The following building blocks determine the success of the algorithm:

  • Method chosen to construct the solutions
  • Heuristic information
  • Pheromone updating rule
  • Transition rule and probability function
  • Parameters values
  • Termination condition

How to use

The project was constructed with eclipse, so to see the code working just open the project in your favorite Java IDE and run the main class (Program.java). Note that the main class is pointing to the path of the src\test\agrega folder inside the repository, so take care for that the path is configured correctly. The project also utilizes a string similarity algorithm implementation taken from the apache "commons-text-1.6" package, the corresponding jars must be included in order for the program to run.

A little description of the classes of the algorithm are given below:

Classes in the "aco" package

  • Aco: Represents the implementation of ACO for Serious Emerging Games.
  • Ant: Represents the ant agent. It process their own state transition rules in the environment.
  • Environment: Represents the solution space. Contains the vertex and edges of the graph to be optimized and the pheromone let by the ants.
  • Parameters: Global parameters used to adjust the ACO algorithm.
  • Program: Calls the main building blocks of the ACO algorithm.

Classes in the "parser.lom" package

  • Graph: Auxiliary class. It represents a learning object graph to be used in the ACO algorithm.
  • LomParser: Class in charge of parsing the learning objects and transform the information obtained into a graph.
  • Parameters: Global parameters used to adjust the parser and the scoreModule.
  • ScoreModule: Class that compares and scores learning objects. It utilizes a string similarity algorithm implementation taken from the org.apache.commons.text package