It is very difficult to efficiently solve a large-scaled maximal covering problem(MCP) by a genetic algorithm. In this paper, we present new crossover and mutation operators specially designed for genetic algorithms to solve large-scaled MCPs efficiently. We also introduce a novel genetic algorithm employing unexpressed genes. Unexpressed genes are the genes which are not expressed and thus do not affect the evaluation of the individuals. These genes play the role of reserving information susceptible to be lost by the application of genetic operations but is suspected to be potentially useful in later generations. The genetic algorithm employing unexpressed genes enjoys the advantage of being able to maintain diversity of the population and thus can search more efficiently to solve large-scaled MCPs. Experiments with large-scaled real MCP data has shown that our genetic algorithm employing unexpressed genes significantly outperforms tabu search which is one of the popularly used local neighborhood search algorithms for optimization.