As privacy concerns become more important, effective and efficient security techniques will become critical to those that are charged with the protection of sensitive information. Agencies that disseminate numerical data encounter a common disclosure control problem called the complementary cell suppression problem. In this problem, cell values that are considered sensitive in the statistical table must be suppressed before the table is made public. However, suppressing only these cells may not provide adequate protection since their values may be inferred using available marginal subtotals. In order to ensure that the values of the sensitive cells cannot be estimated within a specified degree of precision additional non-sensitive cells, called complementary cells, must also be suppressed. Since suppression of non-sensitive cells diminishes the utility of the released data, the objective in the complementary cell suppression problem is to minimize the information lost due to complementary suppression while guaranteeing that the sensitive cells are adequately protected. The resulting constrained optimization problem is known to be NP-hard and has been a major focus of research in statistical data security. Several heuristic methods have been developed to find good solutions for the complementary cell suppression problem. More recently, genetic algorithms have been used to improve upon these solutions. A problem with these GA-based approaches is that a vast majority of the solutions produced do not protect the sensitive cells. This is because the genetic operators used do not maintain the associations between cells that provide the protection. Consequently, the GA has to include an additional procedure for repairing the solutions. This dissertation details an improved GA-based method for the complementary cell suppression problem that addresses this limitation by designing more effective genetic operators. Specifically, it mitigated the problem of chromosomal repair by developing a crossover operator that maintains the necessary associations. The study also designed an improved mutation operator that exploits domain knowledge to increase the probability of finding good quality solutions. The proposed GA was evaluated by comparing it to extant methods based on the quality of its evolved solutions and its computational efficiency.

Cell suppression is a common method for disclosure avoidance used to protect sensitive information in two-dimensional tables where row and column totals are published along with non-sensitive data. In tables with only positive cell values, cell suppression has been demonstrated to be non-deterministic NP-hard. Therefore, finding more efficient methods for producing low-cost solutions is an area of active research. Genetic algorithms (GA) have shown to be effective in finding good solutions to the cell suppression problem. However, these methods have the shortcoming that they tend to produce a large proportion of infeasible solutions. The primary goal of this research was to develop a GA that produced low-cost solutions with fewer infeasible solutions created at each generation than previous methods without introducing excessive CPU runtime costs. This research involved developing a GA that produces low-cost solutions with fewer infeasible solutions produced at each generation; and implementing selection and replacement operations that maintained genetic diversity during the evolution process. The GA's performance was tested using tables containing 10,000 and 100,000 cells. The primary criterion for the evaluation of effectiveness of the GA was total cost of the complementary suppressions and the CPU runtime. Experimental results indicate that the GA-based method developed in this dissertation produced better quality solutions than those produced by extant heuristics. Because existing heuristics are very effective, this GA-based method was able to surpass them only modestly. Existing evolutionary methods have also been used to improve upon the quality of solutions produced by heuristics. Experimental results show that the GA-based method developed in this dissertation is computationally more efficient than GA-based methods proposed in the literature. This is attributed to the fact that the specialized genetic operators designed in this study produce fewer infeasible solutions. The results of these experiments suggest the need for continued research into non-probabilistic methods to seed the initial populations, selection and replacement strategies that factor in genetic diversity on the level of the circuits protecting sensitive cells; solution-preserving crossover and mutation operators; and the use of cost benefit ratios to determine program termination.