Computing Minimal Hitting Sets with Genetic Algorithm

Abstract

A set S that has a non-empty intersection with every set in a collection of sets C is called a hitting set of C. If no element can be removed from S without violating the hitting set property, S is considered to be minimal. Several interesting problems can be partly formulated as ones that a minimal hitting set or more ones have to be found. Many of these problems are required for proper solutions, but sometimes the approximate solutions are enough. A genetic algorithm and advantaged algorithms were devised for computing minimal hitting sets. An improvement makes them get most minimal hitting sets efficiently. Furthermore, they are smaller, i.e., fewer rules.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 04, 2002
Accession Number
ADP012697

Entities

People

  • Jiang Yunfei
  • Lin Li

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Chromosomes
  • Computations
  • Computer Programming
  • Computers
  • Evolutionary Algorithms
  • Genetic Algorithms
  • Information Processing
  • Information Science
  • Information Systems
  • Instructors
  • Mutations
  • Neural Networks
  • Signal Detection
  • Technical Information Centers
  • Trees

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.

Technology Areas

  • AI & ML
  • AI & ML - Information Retrieval
  • AI & ML - Machine Learning Algorithms
  • Biotechnology