TY - GEN
T1 - Obtaining subtrees from graphs
T2 - 2003 IEEE Swarm Intelligence Symposium, SIS 2003
AU - Gosavi, S.
AU - Das, S.
AU - Vaze, S.
AU - Singh, G.
AU - Buehler, E.
N1 - Publisher Copyright:
© 2003 IEEE.
PY - 2003
Y1 - 2003
N2 - The ant systems optimization approach is a new method of solving combinatorial optimization problems. It was originally introduced as a metaheuristic approach for the well-known traveling salesman problem. But it was subsequently shown to be an equally effective algorithm for solving other optimization problems. This article supplies more results for an extended ant colony algorithm, which can be used to compute a minimum cost Steiner tree from a graph. In each pass of the proposed algorithm, ants are placed at the terminal nodes of the Steiner tree to be computed. They are then allowed to move towards one another, along the edges of the graph, until they merge into a single entity. In this process, the paths taken by the ants define a Steiner tree. Edges receive reinforcement in the form of pheromone deposits along the paths taken by the ant, that is based on the quality of the Steiner tree produced. Pheromones eventually accrue most along better edges. As a result, after several iterations, a good Steiner tree can be extracted from the deposit. The algorithm can easily be used in several practical applications.
AB - The ant systems optimization approach is a new method of solving combinatorial optimization problems. It was originally introduced as a metaheuristic approach for the well-known traveling salesman problem. But it was subsequently shown to be an equally effective algorithm for solving other optimization problems. This article supplies more results for an extended ant colony algorithm, which can be used to compute a minimum cost Steiner tree from a graph. In each pass of the proposed algorithm, ants are placed at the terminal nodes of the Steiner tree to be computed. They are then allowed to move towards one another, along the edges of the graph, until they merge into a single entity. In this process, the paths taken by the ants define a Steiner tree. Edges receive reinforcement in the form of pheromone deposits along the paths taken by the ant, that is based on the quality of the Steiner tree produced. Pheromones eventually accrue most along better edges. As a result, after several iterations, a good Steiner tree can be extracted from the deposit. The algorithm can easily be used in several practical applications.
KW - Ant colony optimization
KW - Application software
KW - Computational modeling
KW - Computer networks
KW - Cost function
KW - Integrated circuit synthesis
KW - Polynomials
KW - Routing
KW - Simulated annealing
KW - Traveling salesman problems
UR - http://www.scopus.com/inward/record.url?scp=84942155265&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84942155265&partnerID=8YFLogxK
U2 - 10.1109/SIS.2003.1202262
DO - 10.1109/SIS.2003.1202262
M3 - Conference contribution
AN - SCOPUS:84942155265
T3 - 2003 IEEE Swarm Intelligence Symposium, SIS 2003 - Proceedings
SP - 160
EP - 166
BT - 2003 IEEE Swarm Intelligence Symposium, SIS 2003 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 24 April 2003 through 26 April 2003
ER -