GECCO 2008 Contest Problems

A 2D Packing Problem

In this problem you can try to devise new ways to evolve with a 2D chromosome. The objective of this problem is to best pack a grid so that sum of the point scores for every pair of adjacent numbers is maximized. The trick is that once you collect the points for a particular pair, you can't collect those points a second time in the same grid! Here are the details:

You are given the size of an X by Y rectangular grid.
You are given a range of numbers from 0 to N-1.
You are given a list of ordered pairs of numbers (x, y) where x and y are integers in the range from 0..N-1 For each pair in the list you are given a postive integer point value. For any (x, y) not in the list you assume it has a point value of zero. The array containing points is loaded before the scoring function is called. Note that the points for (x, y) need not be the same as for (y, x)!
Evolve an X by Y grid of numbers in the range 0..N-1 that maximizes this fitness function whose semantics is defined by this sample fitness function.
The parameters for the problem are specified in a file as follows:
- The first line has the values of X, Y, and N as three integers.
- The lines that follow are triples of (x, y, pointValue). The list of lines is terminated by a single -1

Example Evaluation

Here is an example problem expressed in the requested format:

The first line states the problem is on a 3 by 2 grid that can be filled with numbers in the range 0 to 8. The point values for specific pairs follow up to the -1 line. They are:

  pair  points
   1 1      5
   1 3      2
   1 4      9
   2 2      8
   2 4      4
   4 4     11
   3 1      7
   3 3      9
   4 5      3
   4 3      4
   5 1      5

All other pairs are assumed to have a value of 0.

Now let's evaluate this example grid for its fitness:

3 1 4

1 5 3

First we can compute all the pairs in the grid starting with the 1 in the upper left corner and proceeding left to right and top to bottom. This gives us a list of possible pairs that could get points. Here is that list of pairs generated from the example grid. Pairs that were awarded points have those points listed to their right:

pair      points 
          awarded
   3 1       7
   3 5
   3 1
   1 3       2
   1 1       5
   1 5
   1 3
   1 4       9
   4 1
   4 5       3
   4 3       4
   1 3
   1 1 
   1 5
   5 1       5
   5 3
   5 1
   5 4
   5 3
   3 5
   3 1
   3 4
     TOTAl: 35

Note that a pair cannot be counted more than once. For instance the pair (3,1) occurs more than once but the 7 points are awarded only for the first occurance. Also note that the score for a pair (x,y) can be different than for (y,x). For example (3,1) gets 7 points and (1,3) gets 2 points. We believe this made the writing of the exemplar algorithm above clearer but, of course, one rightly reasons that for each time (x,y) is counted (y,x) will eventually also be counted. Feel free to make such equivalent valued optimizations in your code. Finally, note that any pair that was not specified in the problem definition is assumed to have a score of 0. For example (5,3) has a score of 0. The problem definition is defining a possibly sparse pair scoring matrix.

[Problem input]
[Sample grid] with fitness of 153843728

Your Output

Submit a grid of the form: 3 numbers: X, Y, and N. Followed by X*Y numbers in the range 0 to N-1. Fitness will be based on the problem input above.

Current Record

This is the current record best score for the input above.

Date Contributer Location Best Score

Mar 20 Sample Grid Above - 153843728

Apr 12 Christopher B. McCubbin Johns Hopkins University, USA 862715024

Apr 24 Wang Weilei Soochow University, China 911189197

May 27 Lee Taehee Seoul National University, Korea 912309200

Jun 2 Dave Oranchak,Christopher McCubbin Johns Hopkins Applied Physics Lab, USA 921591896

Jun 11 Dave Oranchak,Christopher McCubbin Johns Hopkins Applied Physics Lab, USA 923467221

Jun 13 Dave Oranchak,Christopher McCubbin Johns Hopkins Applied Physics Lab, USA 923545101

Jun 27 Dave Oranchak,Christopher McCubbin Johns Hopkins University, USA 960018824

Jun 14 Taegyoon Kim Seoul National University, Korea 967146637

Jun 15 Sandro Pirkwieser Vienna University of Technology, Austria 981211516

Jun 27 Gautham Anil, Adam Campbel, Chris Ellis, Yinghua Hu and R. Paul Wiegand University of Central Florida 981678735

Jun 25 Sandro Pirkwieser Vienna University of Technology, Austria 991368535

Jun 24 Jin Kim, Kim Jin Hyun, Byung-Ro Moon Optimization Lab at Seoul National University, Korea 1025153604

Jun 27 Coromoto Leon, Gara Miranda, Carlos Segura University Of La Laguna, Spain 1026780634

Jun 27 Jin Kim, Kim Jin Hyun, Byung-Ro Moon Optimization Lab at Seoul National University, Korea 1032295097

Date	Contributer	Location	Best Score
Mar 20	Sample Grid Above	-	153843728
Apr 12	Christopher B. McCubbin	Johns Hopkins University, USA	862715024
Apr 24	Wang Weilei	Soochow University, China	911189197
May 27	Lee Taehee	Seoul National University, Korea	912309200
Jun 2	Dave Oranchak,Christopher McCubbin	Johns Hopkins Applied Physics Lab, USA	921591896
Jun 11	Dave Oranchak,Christopher McCubbin	Johns Hopkins Applied Physics Lab, USA	923467221
Jun 13	Dave Oranchak,Christopher McCubbin	Johns Hopkins Applied Physics Lab, USA	923545101
Jun 27	Dave Oranchak,Christopher McCubbin	Johns Hopkins University, USA	960018824
Jun 14	Taegyoon Kim	Seoul National University, Korea	967146637
Jun 15	Sandro Pirkwieser	Vienna University of Technology, Austria	981211516
Jun 27	Gautham Anil, Adam Campbel, Chris Ellis, Yinghua Hu and R. Paul Wiegand	University of Central Florida	981678735
Jun 25	Sandro Pirkwieser	Vienna University of Technology, Austria	991368535
Jun 24	Jin Kim, Kim Jin Hyun, Byung-Ro Moon	Optimization Lab at Seoul National University, Korea	1025153604
Jun 27	Coromoto Leon, Gara Miranda, Carlos Segura	University Of La Laguna, Spain	1026780634
Jun 27	Jin Kim, Kim Jin Hyun, Byung-Ro Moon	Optimization Lab at Seoul National University, Korea	1032295097

Submit your best to the people below and we will post it here. Good luck and have fun!

Questions about these pages or the problems themselves can be sent to [Robert Heckendorn] or [Terry Soule] at the University of Idaho