COSC 6367 (Dr. Eick) - Spring 2008
Project 1

USING EC FOR SOLVING N CITY TRAVELLING SALESMAN PROBLEMS

Due Date: February 26, 2008 at 11p
Last Updated:February 4, 2008, 1pm


Develop two systems (1) a simple system(SS), and (2) a systems that employs evolutionary computing (ECS) that is capable of solving N city travelling salesman problems for 3 given cost functions. Your software should have an interactive interface that
  • allows to select the system (either SS or ECS)
  • the cost function (either c1 or c2 or c3)
  • the number of cities N for which the problem should be solved
  • an integer random number seed to guarantee reproducability of results
  • a maximal effort bound (TBDL; optinal parameter> and runs the system and reports the best solutions found and other summaries about the search conducted. In a addition to implementing the system and running and enhancing it for the given benchmark, choose a scietific theme related to the project, explore it, and describe what you did and what the finding were in more detail in the project report.

    Write a report (approx. 9 to 13 single spaced pages) that describes the evolution of the project, gives a clear description of the explored and employed search strategies (report the best solution found and its cost for each case), and summarizes the results of running the system for the 2008 TSP Benchmark, and other themes you explored during the course of the project. Finally, the report should interpret the experimental results and summarize the important findings and accomplishments of the project.

    Other Requirements for ECS

    The size of the population should remain constant during a run. Your EC-system should employ at least one crossover operator. Your system should have a user interface described in the first half of the document---if it doesn't you will lose a lot of points. Udit (our TA) has to be able to run your program---if you make it particularly difficult for him, you will lose some points.

    Program Termination Condition

    Total number of new solutions generated = 70,000

    Terminate your program when this condition is reached. Assuming population size is constant per generation, if your population selection model is:

    Generational selection: new solutions = number of generations * population size
    Steady-state selection: new solutions = initial population size + number of surviving offspring added to the population

    Generational selection: The surviving offspring become the entire next generation. No individuals are retained between generations.
    Steady-state selection: Some offspring survive and replace less-fit members of the previous generation. Some individuals are retained between generations.

    Results

    Run your program 3 times for each problem (e.g. with a different random number generator seed) and report the results 33 result sets.

    Submission

    Submit electronically, by email to TA (udit@cs.uh.edu):
    1. Project report
    2. Source code
    3. Makefile, project files
    4. README file
      • specify platform, compiler for your project
      • instructions on how to run your program
      • list of source files, simple description of each
    Submit hard-copy in class.

    Any questions or concerns, please contact Mary or Dr. Eick.

    Good luck !!!