DocumentCode
1652512
Title
An evolutionary algorithm for the T-constrained variation of Minimum Hitting Set problem
Author
Cutello, V. ; Mastriani, E. ; Pappalardo, F.
Author_Institution
Dept. of Math. & Comput. Sci., Catania Univ., Italy
Volume
1
fYear
2002
Firstpage
366
Lastpage
371
Abstract
We propose an evolutionary algorithm to approximate optimal solutions to instances of the T-constrained variation of the Minimum Hitting Set Problem. The base problem, Minimum Hitting Set, is a well known 𝒩𝒫-complete problem. Our genetic algorithm will use the idea of viruses which infect chromosomes and change one of their bits. A special dynamic fitness function has been also used to improve overall performance
Keywords
computational complexity; genetic algorithms; set theory; Minimum Hitting Set problem; Minimum Set Cover; NP complete problem; T-constrained variation; chromosomes; combinatorial problems; dynamic fitness function; evolutionary algorithm; genetic algorithm; optimal solution approximation; performance; viruses; Biological cells; Computer science; Evolutionary computation; Genetic algorithms; Genetic mutations; Mathematics; NP-complete problem; Performance evaluation; Polynomials; Viruses (medical);
fLanguage
English
Publisher
ieee
Conference_Titel
Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress on
Conference_Location
Honolulu, HI
Print_ISBN
0-7803-7282-4
Type
conf
DOI
10.1109/CEC.2002.1006262
Filename
1006262
Link To Document