Random Articles
Reseach Article
Multi-Colony Ant Systems for Multi-Hose Routing
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 59 - Number 2 |
| Year of Publication: 2012 |
| Authors: T G I Fernando, Tatiana Kalganova |
10.5120/9517-3931
|
T G I Fernando, Tatiana Kalganova . Multi-Colony Ant Systems for Multi-Hose Routing. International Journal of Computer Applications. 59, 2 ( December 2012), 1-14. DOI=10.5120/9517-3931
Abstract
Ant System (AS) is a general purpose heuristic algorithm inspired by the foraging behaviour of real ant colonies. AS and its improved versions have been successfully applied to difficult combinatorial optimization problems such as travelling salesman problem, quadratic assignment problem and job shop scheduling. In this paper, two versions of multi-colony ant systems that are extensions to the AS are proposed for the multi-hose routing. In both versions, each colony of ants searches for an optimum path between two end points (or commodities). While each colony searches for optimum paths, they try to maximum use of other colonies paths (sharing paths, or bundling) for easy handling of multiple paths. The first version uses a single pheromone matrix for all colonies and the second version uses different pheromone matrices for each colony and a modified random propositional rule to attract ants toward foreign pheromones. The tessellated format of the obstacles was used in the algorithm instead of the original shapes of the obstacles. As a result of using this format, the algorithm can handle freeform obstacles and speed up the algorithm when checking the collision detections. The experimental results show that there is no significant difference in the quality of the solutions produced by two versions and the first version takes less computation time. Further first version needs low computer memory and one parameter lesser than of the second version.
References
- Dorigo, M. , Maniezzo, V. , & Colorni, A. (1996). The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26, No. 1, pp. 1-13.
- Colorni, A. , Dorigo, M. , & Maniezzo, V. (1991). Distributed Optimization by Ant Colonies. In proceedings of ECAL91 - European Conference on Artificial Life, Elsevier Publishing, pp. 134-142.
- Stutzle, T. & Hoos, H. (1997). MAX-MIN Ant System and Local Search for the Travelling Salesman Problem, IEEE International Conference on Evolutionary Computation, pp. 309-314.
- Maniezzo, V. , Dorigo, M. , & Colorni, A. (1994). The Ant System Applied to the Quadratic Assignment Problem. Technical Report IRIDIA/94-28, Universit Libre de Bruxelles, Belgium.
- Dorigo, M. , Maniezzo, V. , & Colorni, A. (1996). The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man and Cybernetics - Part B, 26 (1), pp. 29-41.
- Gambardella, L. , & Dorigo, M. (1996). Solving Symmetric and Asymmetric TSPs by Ant Colonies. In IEEE Conference on Evolutionary Computation (ICEC'96), IEEE Press, pp. 622-627.
- Bullnheimer, B. , Hartl, R. F. , & Strauss, C. (1997). A New Rank-based Version of the Ant System - A Computational Study. Technical report, University of Viena, Institute of Management Science.
- Bonabeau, E. , Dorigo, M. , & Theraulaz, G. (1999). From natural to artificial swarm intelligence. New York: Oxford University Press.
- Corne, D. Dorigo, M. , & Glover, F. (Eds. ). (1999). New ideas in optimization. Maidnhead, UK: McGraw-Hill.
- Gambardella, L. M. , & Dorigo, M. (1999). Ant algorithms for discrete optimization. Artificial Life 5: Massachusetts Institute of Technology. pp. 137-172.
- Gambardella, L. M. , & Dorigo, M. (1997). Ant Colony System: A cooperative learning approach to the travelling salesman problem. Evolutionary Computation, IEEE Transactions. pp. 53-66.
- Sim, K. M. , & Sun, W. H. (2003). Ant Colony Optimization for Routing and Load-Balancing: Survey and New Directions. IEEE Transactions, MAN, and CYBERNETICSUniversity Press. ISBN 0-19-513159-2.
- Sandurkar, S. , & Chen, W. (1998). GAPRUS - Genetic algorithms based pipe routing using tessellated objects. The journal of computers in industry.
- Gottschalk, S. , Lin, M. C. , & Manocha, D. RAPID (Robust and Accurate Polygon Interface Detection). Available: http://www. cs. unc. edu/ geom/OBB/OBBT. html
- Thantulage, G. , Kalganova, T. & Fernando,W. A. C. (2006). A Grid-based Ant Colony Algorithm for Automatic 3D Hose Routing. IEEE Congress on Evolutionary Computation, CEC 2006, Vancouver, Canada, Jul. , 2006. pp. 48-55.
- Thantulage, G. , Kalganova, T. & Wilson, M. (2006). Grid Based and Random Based Ant Colony Algorithms for Automatic Hose Routing in 3D Space. Transactions on Engineering, Computing and Technology, Volume 14, International Journal of Applied Science, Engineering and Technology (IJASET), Enformatika, ISBN 1503-5313, ISBN 975-00803-3-5, Aug. , 2006. pp. 144-150.
- Nowe, A. , Verbeeck, K. & Vrancx, P. (2004). Multi-type Ant Colony: The Edge Disjoint Paths Problem. Ants 2004, LNCS 3172, Springer-Verlag Berlin Heidelberg, 2004. pp. 202-213.
- Karp, R. (1972). Complexity of Computer Computations. Chapter - Reducibility among Combinatorial Problems. Plenum Press, 1972. pp. 85-213.
- Kramer, M. & Leeuwen, J. V. (1984). Advances in Computing Research, Volume 2: VLSI Theory. Chapter - The Complexity of Wire-routing and Finding Minimum Area Layouts for Arbitrary VLSI Circuits. Jai Press, 1984. pp. 129-146.
- Middendorf, M. & Pfeiffer, F. (1993). On the Complexity of the Disjoint Path Problem. Combinatorica 13, 1993. pp. 97-107.
- Nishizeki, T. , Vygen, J. & Zhou, X. (2001). The Edgedisjoint Paths Problem is NP-Complete for Series-Parallel Graphs. Discrete Applied Mathematics 115, 2001. pp. 177- 186.
- Marx, D. (2004). Eulerian Disjoint Paths Problem in Grid Graphs is NP-Complete. Discrete Applied Mathematics 143, 2004. pp. 336-341.
- Vygen, J. (1995). NP-Completeness of Some Edge- Disjoint Paths Problems. Discrete Applied Mathematics 61, 1995. pp. 83-90.
- Ahuja, N. & Hwang Y. K. (1992). Gross Motion Planning - A Survey. ACM Computing Surveys, 24(3), 219-291.
- Aurenhammer, F. (1991). Voronoi Diagrams - A survey of fundamental geometric data structure. ACM Computing Survey, 23(3) (Sept. ), 345-405.
- Koditschek, D. E. (1989). Robot Planning and Control via potential functions. Robotics Review, Vol 1, MIT Press, Cambridge, Mass.
- Conru, A. B. & Cutkosky, M. R. (1993). Computational Support for Interactive Cable Harness Routing and Design. Advances in Design Automation, DE- 65(1), 551-558.
- Szykman, S. and Cagan, J. (1995). Synthesis of Optimal Non-orthogonal Routes. Advances in Design Automation, DE- 82(1), 431-438.
- Chang, H. & Li T-Y. (1995). Assembly Maintainability Study with Motion Planning. IEEE International Conference on Robotics and Automation, 1012-1019.
Index Terms
Keywords