CSCI 443/543
Evolutionary Computation
Fall, 2009

Project 1: INVESTIGATE A PROBLEM Due Thursday, September 10

Introduction

In a problem of combinatorial optimization, we seek a selection, arrangement, or ordering of problem elements so as to maximize or minimize an objective function on the resulting structure. It is to such problems that we will apply evolutionary algorithms, and this project asks you to investigate one.

Description

Identify a computationally difficult (i.e., NP-hard) combinatorial problem that we have not discussed in class and that does not appear in our text. Write a short paper that describes the problem carefully and precisely. In particular, the paper should address the following:

• The problem itself. Describe it both informally and with mathematical precision. An example is always helpful.
• Applications. Where does this problem arise? How is it applied?
• History. When and by whom was the problem first described? Who demonstrated that it is NP-hard? What techniques, both exact and heuristic, have been applied to it? In particular, have evolutionary algorithms for it been described? How effective have these algorithms been?

The paper should conform to the guidelines presented here, and should be no more than two pages long in this format. Be sure to cite and list references for the information in the paper, and do not limit yourself to a cursory internet search.

This is an opportunity to learn about the LaTeX document formatting system, which is described in several tutorials listed here. This is the system most often used to prepare conference and journal articles in computer science, and it is available on csci and on any Linux machine.

Where to Look

Check books in the library on combinatorial optimization. Also, Crecenzi and Kann have posted a compendium of NP-hard problems. A 1998 version of this compendium is available as an article here. You may consult books and journals in my office.