Visual Basic Developer
Authors: Jones A. Russell
Published year: 1999
Pages: 33-37/175

<< Previous page
Table of contents
Next page >>

Other Applications

ART1 generally provides the ability to cluster data into independent segments. The clustering can be of use by itself to understand the classes (types) of clusters that result. Additionally, as we saw in the personalization algorithm, looking at the members of an individual cluster can provide interesting information. Additional applications include:

Statistics
Pattern recognition
Reducing the dimensionality of search spaces
Biology
Web search engines
Spatial data mining
many others

Summary

This chapter has illustrated a simple algorithm that clusters sets of data into groups for use as a recommender system. While originally defined as an offline processing tool that could be used for data mining, the efficiency of the algorithm lends itself to real-time processing of data within a commercial Web environment.

The example application shown here was very simple and represented a very small data set. For Web site personalization, the data set could include not only a representation of the Web content, but also time spent viewing a particular piece of content. The types and representation of the data ultimately depend upon the algorithm providing the personalization service. With proper encoding within feature vectors, the ART1 algorithm can work with a wide variety of data representing many aspects of a consumer's behavior in a Web setting.

Despite the harmful applications that exist for personalization engines, they can be beneficial timesaving devices and therefore should not be overlooked.

References

[Gallant 1994] Gallant, Stephen. 1994 . Neural Network Learning . Cambridge, Mass.: MIT Press.

Resources

Carpenter, G. and S. Grossberg. 1987 . "A Massively Parallel Architecture for a Self-Organizing Neural Pattern Recognition Machine," Computer Vision, Graphics and Image Processing 37 : 54 “115.

Wolfram Research. "Eric Weisstein's World of Mathematics," available online at http:// mathworld .wolfram.com/ (accessed January 17, 2003 )

Chapter 4: Ant Algorithms

Download CD Content

In this chapter, we'll look into an interesting multi-agent simulation that's useful in solving a wide variety of problems. Ant algorithms, or Ant Colony Optimization (the name coined by its inventor Marco Dorigo), uses the natural metaphor of ants and stigmergy to solve problems over a physical space [Dorigo 1996]. Nature has provided a number of different methods and ideas in the space of optimization (as illustrated by other chapters in this book such as "Simulated Annealing" and "Introduction to Genetic Algorithms"). Ant algorithms are particularly interesting in that they can be used to solve not only static problems, but also highly dynamic problems such as routing problems in changing networks.

Natural Motivation

Although ants are blind, they navigate complex environments and can find food some distance from their nest and return to their nest successfully. They do this by laying pheromones while they navigate their environment. This process, known as stigmergy, modifies their environment to permit communication between the ants and the colony as well as memory for the return trip to the nest.

What is most surprising about this process is that ants tend to take the best route between their nest and some external landmark. This natural optimization is again part of stigmergy. As more ants use a particular trail to an external landmark, the trail becomes higher in pheromone concentration. The closer the landmark is to the nest, the higher the number of round-trips made by each ant. For a landmark that's farther away, a lesser number of round-trips are made, and a higher concentration of pheromones is applied. The higher the concentration of pheromones, the more ants will choose this route over others that might be available. This iterative process achieves sub-optimal to optimal trails between the endpoints.

Ant algorithms are interesting because they share some of the fundamental qualities of ants themselves . Ants are altruistic, cooperative, and work collectively toward a common goal. Ant algorithms share these traits in that the simulated ants within the environment work in parallel to solve a problem, and through stigmergy, help others to further optimize the solution.

Consider the example in Figure 4.1. Two ants at their nest must reach the food on the other side of the obstacle . While the ants travel, each ant deposits a small amount of pheromone along the route as a marker.

click to expand
Figure 4.1: Initial configuration (T ).

With equal probability, each ant takes a different route. One ant takes the upper route and the other the lower route. Since the lower route is half the distance to the food, the lower ant has reached the destination at time T ₁ . The ant taking the higher route has only reached the halfway mark (see Figure 4.2).

click to expand
Figure 4.2: One unit of time has passed (T ₁ ).

Once an ant reaches the food, it takes one of the objects and returns back to the nest using the same path . At time T ₂ , the lower ant has returned to the nest with the food while the upper ant has finally reached the food landmark (see Figure 4.3).

click to expand
Figure 4.3: Two units of time have passed (T ₂ ).

Recall that as each ant travels , a small amount of pheromone is deposited along the trail. In the case of the upper ant, the trail has been covered only once during the period T -T ₂ . The lower ant has covered its trail twice during the same period. Therefore, twice the amount of pheromone has been deposited along the lower trail compared to the upper trail. At time T ₄ , the upper ant will have returned to the nest while the lower ant will have completed another run to the food landmark and back. At this point, the concentration of pheromone on the lower trail will be twice that of the upper trail. The upper ant will then likely decide to use the lower trail, based solely on the concentration of pheromone detected .

This is the basic idea behind ant algorithms ”optimization through indirect communication between autonomous agents .

<< Previous page
Table of contents
Next page >>