The set covering problem is NP-complete as it can be transformed to the
vertex cover problem~\cite{Aho_1974b}.

SCP has various application areas such as assigning flying crews to flight
legs, fire companies to fire houses~\cite{Walker}, etc.

The fitness function of the SCP includes many local optima since a
relatively small number of ones distributed over a big long bit strings.

Liepins~\cite{Liepins_MEOSA} compared two algorithms: one is based on VEGA 
and the other is
based on Pareto-optimality. In VEGA model, one objective is minimize the
cost while the other objective is to minimize the infeasibility of the
solution. In Pareto model, Goldberg's ranking is used and objective
function tried to minimi cost and infeasibility. Liepins compared 1PX, 2PX,
and a greedy crossover operations. Greedy crossover operation calculates
the Chavatal's~\cite{Chavatal_1979} greedy choice on column set  
which is obtainde from its parents. He reports a slightly better 
performance in favor of a greedy crosssover operation.

Hernandez~\cite{Hernandez_1995} proposed a divide-and-conquer approach 
with GA. In his
formulation, problem is broken down to several non overlapping sub problems
and for eac subproblem, a population of solutions is produced with GA.
Fitness value of a chromosome in a subpopulation is evaluated according to
its ability to produce a feasible solution when combined with other sub
solutions from other populations. He reports that a better performance is
obtained compared to other GA approaches.

Back~\cite{Back_AE_1995} is applied additive penalty term to punish the infeasible solutions.
Penalty term is calculated by estimating the total minimum cost to
transform an infeasible solution to a feasible one based on their greedy
choice. He compared 1PX, 2PX, uniform crossover, and fusion 
crossover~\cite{Beasley_Chu_1996}. The
fusion crossover takes the $gene_i$  from one of its parents proportional
to their fitness values. He reported that without repairing(with only
penalty functions) GA could not produce comparable results compared to
Greedy Algorithms meanwhile GA with  repairing ssometimes beats the greedy
solutions. He also reported that the selection of any crossover operator
did not affect the final results at all. 

Feasible solution regions are seperated by a large Hamming Distance and the
objective function values of local optimas might differ a lot. This fitness
lanscape unfortunately traps GA to the attraction points vry quickly and a
mutationm operator could not help to push it to another region.

Bit string representation is the common preferred chromosome coding in the
studies so far since it is suitable for application of generalized
operators and techniques while it wastes most of the code. This kind of
representation might be the reason for large HD values between feasible
regions.

