Assignment 0: Breaking Up Is Hard To Do

As described in class, in this project you will write and run a simple GA to solve the problem of partitioning a graph into two parts such that:

There will be no more than a total of 31 nodes
The "weight" of communication between each pair of nodes is specified by a number between 0 and 1 (inclusive); these weights are specified by a lookup table
Every node appears in one and only one of the two parts
The number of nodes in each of the two parts is equal; in the case of an odd number of nodes, the number of nodes in the parts differs by one
The sum of the weight values of all the graph arcs spanning the two parts is minimized

The GA structure is entirely up to you. In fact, you need not code your GA from scratch; it is perfectly allowable for you to use an existing GA library or tool to create your GA.

Input To Your Program

The input to your program is simply:

The total number of nodes (an integer from 1 to 31)
One line per node; line k lists the floating-point weights for arcs from k to each of the nodes

A simple 5-node example is:

5
0.000000 0.694844 0.389750 0.383836 0.000000
0.694844 0.000000 0.282904 0.000000 0.000000
0.389750 0.282904 0.000000 0.536894 0.000000
0.383836 0.000000 0.536894 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000

This says, for example, that the arc from node 0 to node 1 has a weight of 0.694844 (as does the arc from node 1 to node 0). The partitioned weight sum is simply the sum of all weights that correspond to arcs between nodes in different parts. Thus, if nodes 0 and 1 are in different parts, that fact contributes 0.694844 to the sum twice, once for the arc in each direction.

You have been provided with a program that creates such a graph: mkg.c.

Your GA's output can be fairly verbose, but must include the list of node numbers in first part and the total cost of that partitioning.

Hints

The limit of 31 nodes is intended to simplify encoding using a single 32-bit int; using 31 instead of 32 bits neatly avoid the signed vs. unsigned shift issue. To count the 1 bits in 31-bits of int, you can use something like the code on the magic algorithms page.

Due Dates, Submission Procedure, & Such

This project was originally due by 11:59PM, Friday, September 30, 2005, but is now bumped to October 5. Before you can submit anything, you need to register with the CGI server here... the delay in posting the server registration link is why you have been given more time. Submit a tarball containing the following:

A Makefile such that make compiles your code into an executable file named a0. Typing make run should cause your program to be run with "reasonable" parameters and accepting input from stdin. Feel free to print as much output as you like, but the last line of output from your C program should contain a single integer value, printed by printf("%d\n", ...), which is the best geneotype found encoded as an int (as described above).
Your C source code.
A very brief HTML-formatted document, a0.html, explaining what you did and why.
(Remember: 50% credit is given for documented errors!)

Submit the tarball here:

Your email address is .

Your password is .

Type your "section"; 1 for EE599, 2 for EE699:

Although this is not a secure server, users are bound by the UK code of conduct not to abuse the system. Any abuses will be dealt with as serious offenses.

http://aggregate.org/EC/ (Advanced) Evolutionary Computing