Goals and Purpose

The purpose of this project was to investigate the use of genetic algorithms (GAs), and specifically a kind of GA called a memetic algorithm, to solve several interesting and practical problems. Genetic algorithms "evolve" populations of solutions to increase their fitness, using simulated natural selection operators such as crossover and mutation. Memetic algorithms augment this process by applying a local improvement operator to the solutions as they are generated. We applied memetic algorithms to the problem of finding optimal Shellsort sequences and to the problem of devising "deceptive" visually encrypted messages. Our goals were to learn how GAs work, how to devise and conduct experiments, and, of course, to find good solutions to the problems we chose to study. We also planned a visit to SIGCSE 2002 to view other student research projects and to meet computer science students and teachers from other schools.

Research Methods

There were two phases to each problem: coding and testing the genetic algorithm, then running experiments to solve the problem for various values of the problem parameters. To this end we implemented a genetic algorithm (in order to rapidly obtain a working prototype we implemented a so-called "steady- state" GA) and customized it with fitness functions and crossover and mutation operators appropriate to the problems under investigation.

We first devised a GA to search for Shellsort increment sequences that would yield good average-case running time for random arrays. Our (noisy) fitness function was the actual clock time required to sort random files using a particular sequence. We generated several large random input files for Shellsort and ran experiments, on different platforms, to try to eliminate effects of noise in our fitness function. Our final Shellsort sequence was then tested on a different set of random input files.

This summer we hope to complete a project to generate "deceptive" visually encrypted images. Visual encryption involves the division of an image (usually consisting of black and white pixels) into two or more files so that each file individually provides no clue to the image, but simply "overlaying" the files reveals the image. In deceptive encryption, there is a third component to the encryption, an offset of one image with respect to the other. Use of this offset produces the desired image, but use of an incorrect offset may produce a false or misleading image. Given a target image, our GA will produce two files that will attempt to maximize the number of offsets that produce misleading images, while still providing correct encryption of the target image at one particular offset. For our fitness function we intend to measure the largest number of offsets that produce solid areas of black pixels of a given minimum size.

For a few weeks we considered the Hough transform, a technique for detecting patterns (lines, circles, etc.) in line images. We hoped to investigate GA techniques for determining optimal parameters for particular kinds of patterns, but abandoned the idea due to time limitations and problems with third-party software.

Conclusion and Results

We were able to find a Shellsort sequence that sorts more rapidly (on random files of a million distinct elements) than the best sequences that we were able to find in the literature (including another one produced by a different type of genetic algorithm). Our results will be presented at the Genetic and Evolutionary Computing Conference (GECCO 2002) in New York City this July.

We successfully wrote software for visually encrypting black and white images under a given offset, and have devised a first approximation to a fitness function for testing the "deceptiveness" of pairs of files under a given offset. We hope to submit this either to the SIGCSE 2003 student research poster competition or to a genetic programming conference.

The team attended SIGCSE 2002 and enjoyed it enormously; several members of the team came back with ideas for senior research projects.

Details of our project may be found at: http://cs.allegheny.edu/~rroos/crew/