Ant Colony Optimization and Hypergraph Covering Problems
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationSimilar Papers 제목 키워드 기반
CACO : Competitive Ant Colony Optimization, A Nature-Inspired Metaheuristic For Large-Scale Global Optimization
Large-scale problems are nonlinear problems that need metaheuristics, or global optimization algorithms. This paper reviews nature-inspired metaheuristics, then it introduces a framework named Competitive Ant Colony Opti…
global-optimizationMemcomputing and Swarm Intelligence
We explore the relation between memcomputing, namely computing with and in memory, and swarm intelligence algorithms. In particular, we show that one can design memristive networks to solve short-path optimization proble…
SchedulingAnt Colony Optimization for Inferring Key Gene Interactions
Inferring gene interaction network from gene expression data is an important task in systems biology research. The gene interaction network, especially key interactions, plays an important role in identifying biomarkers …
Drug DesignA modified ant colony based approach to digital image edge detection
Ant Colony Optimization (ACO) is a nature inspired meta-heuristic algorithms, which can be applied to a wide range of optimization problems. In this paper we present a modified method for edge detection based on the Ant …
Edge DetectionAnt Colony Sampling with GFlowNets for Combinatorial Optimization
We present the Generative Flow Ant Colony Sampler (GFACS), a novel meta-heuristic method that hierarchically combines amortized inference and parallel stochastic search. Our method first leverages Generative Flow Network…
Combinatorial Optimization