Gravity-based heuristic for set covering problems and its application in fault diagnosis

A novel algorithm named randomized binary gravita- tional search （RBGS） algorithm is proposed for the set covering problem （SCP）. It differs from previous SCP approaches because it does not work directly on the SCP matrix. In the proposed algo- rithm, the solution of SCP is viewed as multi-dimension position of objects in the binary search space. All objects in the space attract each other by the gravity force, and this force causes a global movement of all objects towards the objects with heavier masses which correspond to good solutions. Computation results show that the proposed algorithm is very competitive. In addition, the proposed aigodthm is extended for SCP to solve the fault diagno- sis problem in graph-based systems.

Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

Currently,the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems.In this sense,metaheuristics have been a common trend in the field in order to design approaches to solve them successfully.Thus,a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments.Following the No Free Lunch theorem,we are interested in testing the performance of the Fruit Fly Algorithm,this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces,based on the foraging behavior of the fruit fly,which usually has much better sensory perception of smell and vision than any other species.On the other hand,the Set Coverage Problem is a well-known NP-hard problem with many practical applications,including production line balancing,utility installation,and crew scheduling in railroad and mass transit companies.In this paper,we propose different binarization methods for the Fruit Fly Algorithm,using Sshaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space.We are motivated with this approach,because in this way we can deliver to future researchers interested in this area,a way to be able to work with continuous metaheuristics in binary domains.This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost.

Input Data Dependency of a Genetic Algorithm to Solve the Set Covering Problem

A genetic algorithm to solve the set covering problem proposed in the literature had some improvements which gave better solutions, i.e., better chromosomes in the first starting population, taking full account of domain specific knowledge with sound programming skill. We have further investigated the input data dependency of their genetic algorithm, i.e., the dependency on costs and density. We have found that for input problem data sets with densities greater than or equal to 3%, our genetic algorithm is still practical both in computing time and approximation ratio.

SET COVERING-BASED TOPSIS METHOD FOR SLOVING SUP-T EQUATION CONSTRAINED MULTI-OBJECTIVE OPTIMIZATION PROBLEMS

This paper considers solving a multi-objective optimization problem with sup-T equation constraints A set covering-based technique for order of preference by similarity to the ideal solution is proposed for solving such a problem. It is shown that a compromise solution of the sup-T equation constrained multi-objective optimization problem can be obtained by ＂solving an associated set covering problem. A surrogate heuristic is then applied to solve the resulting optimization problem. Numerical experiments on solving randomly generated multi-objective optimization problems with sup-T equation constraints are included. Our computational results confirm the efficiency of the proposed method and show its potential for solving large scale sup-T equation constrained multi-objective optimization problems.

An Approximation Algorithm for P-prize-collecting Set Cover Problem

In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=U.Every subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative profit.Our goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit bound.Our main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.

ENERGY-EFFICIENT HEURISTIC METRIC FOR SCP IN SENSOR NETWORKS

A heuristic metric is presented to achieve the optimal connected set covering problem （SCP） in sensor networks. The coverage solution with the energy efficiency can guarantee that all targets are fully covered. Among targets, the crucial ones are redundantly covered to ensure more reliable monitors. And the information collected by the above coverage solution can be transmitted to Sink by the connected data-gathering structure. A novel ant colony optimization （ACO） algorithm--improved-MMAS-ACS-hybrid algorithm （IMAH） is adopted to achieve the above metric. Based on the design of the heuristic factor, artificial ants can adaptively detect the coverage and energy status of sensor networks and find the low-energy-cost paths to keep the communication connectivity to Sink. By introducing the pheromone-judgment-factor and the evaluation function to the pheromone updating rule, the pheromone trail on the global-best solution is enhanced, while avoiding the premature stagnation. Finally, the energy efficiency set can be obtained with high coverage-efficiency to all targets and reliable connectivity to Sink and the lifetime of the connected coverage set is prolonged.

Restricted parameter range promise set cover problems are easy

The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.