Jump to content

User:Anandiitmandi/sandbox

From Wikipedia, the free encyclopedia

Metahuristics and Ant Colony Optimization

[edit]

Metaheuristics

[edit]

Metaheuristics are solution methods that engineer an interaction between local improvement procedures and higher level strategies to create a process that is capable of not getting trapped into local optima and performing a robust search of a solution space.

These methods also includes any procedures that employ strategies for overcoming the trap of local optimality in complex solution spaces, especially those procedures that utilize neighborhood as a means of considering admissible moves to transition from one solution to another, or to build or destroy solutions in constructive and destructive processes. The degree to which neighborhoods are exploited varies according to the type of procedure.

Numerous strategies emerged from the creation of metaheuristic methods and have proved to be remarkably effective, and become preferred line of attack for solving many types of complex optimization problems.

Metaheuristics vs Exact Methods For Optimization

[edit]

While metaheuristics do not guarantee the exact optimal solutions, exact procedures (which theoretically provide such a guarantee, if allowed to run long enough) have often proved incapable of finding solutions whose quality is close to that obtained by the leading metaheuristics-particularly for real-world problems, which often attain notably high levels of complexity. In addition, some of the more successful applications of exact methods integrates metaheuristic strategies within them. These outcomes have motivated additional research and application of new and improved metaheuristic methodologies.

How this simple swarm of Ants be inspiration for a new metaheuristic ACO.

Ant Colony as Metaheuristics

[edit]

Ant Colony Optimization (ACO) is a metaheuristic approach for solving hard combinatorial optimization problems. The inspiring source of ACO is the pheromone trail laying and following behavior of real ants which use pheromones as a communication medium[1][2][3].

ACO algorithms were first proposed in 1990’s by M. Dorigo and colleagues[4][5] to solve combinatorial optimization problems and is applied successfully to solve most of the hard combinatorial optimization problems in reasonable time.

Important point of consideration is how the Foraging behavior of ant can be simulated as algorithm that can be run on computer to solve optimization problem and get benefited from the methodology available in nature.

Very first step in solving optimization problems using ACO is to model optimization problem as a graph. Then following are the major steps that are involved in ACO algorithms are

1. Initialization by establish nest on various selected nodes of the graph. Nodes are generally selected randomly and may be more than one.
2. Start hunting for food on various edges of the graph. Edges to start hunting are also selected by ants. After spotting food source each ant deposits a substance, known as pheromone, with the quality and quantity depends on the quality of the food source found on the edges on return. Quantity of the pheromone on the edge effects the path selection decision of subsequent ants.
3. Update pheromone by each ant on their chosen path. Updation can take place locally or can take place globally.
4. Update solution when better solution found.

Psudocode

[edit]

ACO Variants

[edit]

The first example of such an algorithm is Ant System (AS), which was proposed using as example application the Traveling Salesman Problem (TSP)[6][7][8][9]. Then it is used successfully to solve considerable number of applications including the quadratic assignment, vehicle routing, sequential ordering, scheduling, routing in Internet-like networks, and so on[10].

Various variants of ACO algorithms are also reported for solving combinatorial optimization problems[11][12] and then modified and used to solve other classes of problems like continuous-variable optimization problems[13][14][15][16][17][18][19] mixed-variable optimization problems[20][21] and multi-objective optimization problems and has been proved promising.

For more information on ongoing projects, research works and publications visit the webpage [22].

References

[edit]
  1. ^ J. M. Pasteels, J. L Deneubourg, S. Goss, Self-organization mechanisms in ant societies (I): trail recruitment to newly discovered food sources, Experientia Suppl, 54, pp. 155-175, 1987.
  2. ^ J. L. Deneubourg, S. Aron, S. Goss, and J. M. Pasteels, The selforganizing exploratory pattern of the Argentine ant, J. Insect Behav., 3, 159, 1990.
  3. ^ M. Dorigo, and G. Di Caro, The ant colony optimization meta-heuristic, New ideas in optimization, London, McGraw Hill, pp. 11-32, 1999.
  4. ^ name="M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
  5. ^ Alberto Colorni, Marco Dorigo, and Vittorio Maniezzo, Distributed Optimization by Ant Colonies, Proceedings of European Conference on Artificial Life (ECAL), Paris, France, Elsevier Publishing, pp. 134-142, 1991.
  6. ^ L. M. Gambardella, M. Dorigo, Ant-Q: a reinforcement learning approach to the traveling salesman problem, Proceedings of the 12th International Conference on Machine Learning, Palo Alto (CA), Morgan Kaufmann Publishers, pp. 252-260, 1995.
  7. ^ Marco Dorigo, Vittorio Maniezzo, and Alberto Colorni, Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, MAN, AND Cybernetics-Part B Cybernetics, VOL 26, NO 1, FEBRUARY 1996.
  8. ^ M. Dorigo and L. M. Gambardella, Ant Colony System: a cooperative learning approach to travelling salesman problem, IEEE Trans. Evol. Comput., 1(1), 53, 1997.
  9. ^ T. Stützle, and H. H. Hoos, MAX-MIN ant system, Future Gener Comput Syst, 16(8), pp. 889-914, 2000.
  10. ^ E. Bonabeau, M. Dorigo, and G. Theraulaz, Inspiration for optimization from social insect behaviour, Nature, 406, pp. 39-42, 2000.
  11. ^ Bernd Bullnheimer, Richard F. Hartl, Christine S., A New Rank Based Version of the Ant System-A Computational Study, Central European Journal for Operations Research and Economics, 7(1), 25, 1999.
  12. ^ Michael Guntsch and Martin Middendorf, A population based approach for ACO, Proceedings of the Applications of Evolutionary Computing on EvoWorkshops, 2002.
  13. ^ G. Bilchev and I. C. Parmee, The Ant Colony Metaphor for Searching Continuous Design Spaces, AISB Workshop on Evolutionary Computing, pp. 25-39, 1995.
  14. ^ M. Wodrich and G. Bilchev, Cooperative distributed search: the ant’s way, Control and Cybernatics 26, pp. 413-445, 1997.
  15. ^ N. Monmarché, G. Venturini, and M. Slimane. On how pachycondyla apicalis ants suggest a new search algoritm, Future Generation Computer Systems, 16, pp. 937–946, 2000.
  16. ^ M. Mathur, S. B. Karale, S. Priye, V. K. Jyaraman, and B. D. Kulkarni, Ant colony approach to continuous function optimization, Industrial and Engineering Chemistry Research, 39, pp. 3814-3822, 2000.
  17. ^ Seid H. Pourtakdoust and Hadi Nobahari, An Extension of Ant Colony System to Continuous Optimization Problems, In proceeding of 4th International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS), pp. 294-301, Brussels, Belgium, 2004.
  18. ^ Krzysztof Socha, Marco Dorigo, Ant colony optimization for continuous domains, European Journal of Operational Research, 185, pp. 1155-1173, 2006.
  19. ^ Min Kong and Peng Tian, A Direct Application of Ant Colony Optimization to Function Optimization Problem in Continuous Domain, Proceedings of the 5th international conference on Ant Colony Optimization and Swarm Intelligence (ANTS), pp. 324-331, Springer-Verlag Berlin, Heidelberg, 2006.
  20. ^ Martin Shlüter, Jose . Egea, and Julio R. Banga, Extended ant colony optimization for non-convex mixed integer nonlinear programming, Journal Computers and Operations Research, Volume 36, Issue 7, pp. 2217-2229, July 2009.
  21. ^ Tianjun Liao, Marco A. Montes de Oca, Dogan Aydin, Thomas Stützle, Marco Dorigo, An incremental ant colony algorithm with local search for continuous optimization, Proceedings of the 13th annual conference on Genetic and evolutionary computation (GECCO), pp. 125-132, ACM New York, NY, USA, 2011.
  22. ^ M. Dorigo, Ant colony optimization web page, [[1]].
Retrieved from "https://en.wikipedia.org/w/index.php?title=User:Anandiitmandi/sandbox&oldid=558715263"