Computer Science – Neural and Evolutionary Computing
Scientific paper
2011-05-14
Computer Science
Neural and Evolutionary Computing
7 pages
Scientific paper
Ant Colony Optimization (ACO) is a very popular metaheuristic for solving computationally hard combinatorial optimization problems. Runtime analysis of ACO with respect to various pseudo-boolean functions and different graph based combinatorial optimization problems has been taken up in recent years. In this paper, we investigate the runtime behavior of an MMAS*(Max-Min Ant System) ACO algorithm on some well known hypergraph covering problems that are NP-Hard. In particular, we have addressed the Minimum Edge Cover problem, the Minimum Vertex Cover problem and the Maximum Weak- Independent Set problem. The influence of pheromone values and heuristic information on the running time is analysed. The results indicate that the heuristic information has greater impact towards improving the expected optimization time as compared to pheromone values. For certain instances of hypergraphs, we show that the MMAS* algorithm gives a constant order expected optimization time when the dominance of heuristic information is suitably increased.
Hota Ashish Ranjan
Pat Ankit
No associations
LandOfFree
Ant Colony Optimization and Hypergraph Covering Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Ant Colony Optimization and Hypergraph Covering Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ant Colony Optimization and Hypergraph Covering Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-579357