Title :
A genetic algorithm approach for set covering problems
Author :
Huang, Wen-Chih ; Kao, Cheng-Yan ; Horng, Jorng-Tzong
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Abstract :
We introduce a genetic algorithm approach for set covering problems. Since the set covering problems are constrained optimization problems we utilize a new penalty function to handle the constraints. In addition, we propose a mutation operator which can approach the optima from both sides of feasible/infeasible borders. We experiment with our genetic algorithm to solve several instances of computationally difficult set covering problems that arise from computing the 1-width of the incidence matrix of Steiner triple systems. We have found better solutions than the currently best-known solutions for two large test problems
Keywords :
constraint handling; genetic algorithms; optimisation; Steiner triple systems; constrained optimization problems; genetic algorithm approach; incidence matrix; mutation operator; penalty function; set covering problems; Computational efficiency; Computer science; Constraint optimization; Genetic algorithms; Legged locomotion; Linear programming; Processor scheduling; Resource management; System testing;
Conference_Titel :
Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-1899-4
DOI :
10.1109/ICEC.1994.349997
