Ethan Codes

Here is some editted sample output from a test run. I set up 6 cities in a square, so the best tour with be easy for me to see.

BAEDCC CACBCF CBEEDC EAEEBC BCFDCE ACCAEA
BDBACE BEFFCF ECAFDB FACCAD AFDCBF FFBCCD
BDACEC FFEDAB CDAABD AFBCCD CBACFA BFABDC
AFBBEB FBDCDF CCECCC EDECED AFAECE FEACDF
AFDADB BCDCEB BFBAEE BFCEEA CDCBEA CBBDBF
CEACBD BCDFFB FCDDAC BCDCEE FCDEBC DEDECD
BDBBDD CFCADB AACBDB DBABCA BDDCDC CAFEEA
FDCEDE ABEDFE CEBFBA DEBEDE BDFBBF BBFEFA
FEABEF DBADEE CDBAAD CEBCFA BCAADF DACADA
BBBDCB FABDCC DDBEDF FDCEFD DCAEBB DCFADD
FECACB FBBBCD EAAEDD EDBECE EBDDCB ADBEDC
DAFADD DCCAAB DACEFD ADCECD FFACCD FCCBEE
Unique tours: 72
Dominant tour: BAEDCC (10009.233345472034)
...
BAEDCC ECCBCD ECAFDC EAAFBC BADFBC BFAFBC
BFAACD EFABCB ECAFDD EFDFDD BFDCBF BFACCD
FFABCD FCABDB EFAFBD AFBCDE AFBBDE BFABDE
AFAABD ACAADB ECAFEF AFBCDC AFEEDC FFEBDE
AFDBBB AECCEB BEABEC BFDEBC AFDBBC AEEBBA
DECCBA FEDCBB FEDBBC FDDBBE BEDBDA DEFCBA
ABCDFE CEDDFA CCDBBD BDAEDE BDFEDF BBCCEA
ABCDFE CBCAED CCBFED CCBAEF BCAEDF BBCEDF
FBADEE FBBAED CBBAFD CEBAFD CCBEFD FBCADF
FBADCB FABDCC CBBAFC DCBAFC DCBEBC FEBADC
DACDCB FABBCD FAABCD DCBAFC FEBADC FEBADC
DAEDCB ECCACD ACCCFD AABCFD FFBFDC DAACCB
Unique tours: 68
Dominant tour: FEBADC (16.233345472033854)

*snip*

EFABCD EFABCD EFABCD EFAFBC EEDFBC EEAFCC
EFABCD EFABCD EFABCD AFAFCD EFBCCC BFABCD
EFABCD EFABCD EFABCD EFABDD AFBCDE BFAECD
AFEECC EFABCD AFDECC AFDCDC AFBEBE AFEECC
EBDEBC AFABBC AFDEBC AFDEBC AFDEBC AFDEBC
AFDEFC ABDDBE ABDEBE AFDEBC AFDEBC AFDEBC
ABCDDE ABCDFE ABCDFE ABDEBC AFDEFE ABDEDE
FBCADE FBDAFE AEDDFE DEDAFE DBCAFE DBCAFE
FBCADE FBBAFE CEBAFE DEBAFC DBCAFE FBCADE
FEBBDD CEBAFC DEBAFC DEBAFC DEBAFE DBBACE
FEEBCB FEBDCD DEBAFC DEBAFC DEBAFC DEBAFD
EAEDCD EAABCB DFAAFC DEBAFC DEBFBC DABFBD
Unique tours: 45
Dominant tour: EFABCD (10.485281374238571)
...
EFABCD EFABCD EFABCD EEDACC EFDADC EEAABC
EFABCD EFABCD EFABCD EFABCD EFABDE EFABCD
EFABCD EFABCD EFABCD EFABCD EFACCC EFABCD
EFAECD EFABCD EFAEBC AFDECC AFDEBC AFAEBD
AFDBFC EFCBCC AFDEBC AFDEBC AFDEBC AFDEBC
ABDEBC ABCDFE ABCDBE AFDEBC AFDEBC AFDEBC
DBCADE ABCDFE ABCDFE ABCDFE ABCABE ABCEBC
DBCAFE DBCAFE DBCAFE DBCAFE DBCAFE DBCAFE
FBBAFE DBBAFE DBBAFE DBBAFE DBCAFE DBCAFE
DBBAFE DEBAFC DEBAFC DEBAFC DEBAFE DECAFE
DEBAFB EEBACB DEBAFC DEBAFC DEBAFC DEBAFD
DEAFCB EEAACB DFBACC DEBAFC DEBAFC DEBAFD
Unique tours: 31
Dominant tour: EFABCD (10.485281374238571)
...
EFABCD EFABCD EFABCD EEBAFC DFBBFE EFAACC
EFABCD EFABCD EFABCD EFABCD EFABDE EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABBD EFDBCD EFABBC EFABCD
EFABCC EBABBE AFDEBC AFDEBC AFDEBC AFDEBC
EBDDFE ABDEFE AFDEBC AFDEBC AFCEBC AFDEBC
DBCAFE DBCAFE ABDEBE ABDEFE DBCAFE DBCAFE
DBCAFE DBCAFE DBCAFE DBCAFE DBCAFE DBCAFE
DBCAFE DBCAFE DBCAFE DBCAFE DBCAFE DBCAFE
DBCAFE DBCAFC DEBAFE DBCAFE DBCAFE DBCAFE
DEBAFE DEBAFC DEBAFC DEBAFC DBCAFE DEBAFE
DEAAFE DFAAFC DFBACC DEBAFC DEBAFC DEBAFC
Unique tours: 22
Dominant tour: DBCAFE (12.233345472033857)

*snip*

EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EBABCD DFABCD DFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
Unique tours: 3
Dominant tour: EFABCD (10.485281374238571)
...
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
EFABCD EFABCD EFABCD EFABCD EFABCD EFABCD
Unique tours: 1
Dominant tour: EFABCD (10.485281374238571)
501 iterations.

I found out that this implementation is such a memory hog that I can’t run a simulation with more than 6 cities- I run out of memory.

After a few hours of work, I think it works. I’m not using the Generation 5 JDK because their Torus is for “states” which are integers, not strings. I’d already written my own anyway, so, no real problem.

All the cities are stored as Cartesian coordinates, and I store them in an array. The first city gets labelled A, and Ax is in coordinates[0][0], Ay is in coordinates[0][1], Bx is in coordinates[1][0], By is in coordinates[1][1], and so on.

Finding the distance between two points is math. I would call distanceBetween(‘A’, ‘B’) and it would return the answer. The code follows:

public static double distanceBetween(char pointA, char pointB) {
        int pA = pointA - 65;
        int pB = pointB - 65;
        int x = Math.abs(coordinates[pA][0] - coordinates[pB][0]);
        int y = Math.abs(coordinates[pA][1] - coordinates[pB][1]);
        double distance = Math.sqrt((x * x) + (y * y));
        return distance;
    }

To find the length of a tour you just walk through the whole thing. A tour is a string that looks like ABCDEF. I would call tourDistance(“ABCDEF”) and it will return the length of the whole tour, which would be the distance from A to B, B to C, and so on, and including F to A because we have to return to the first city. The code looks like this:

public static double tourDistance(String tour) {
        double distance = 0.0;
 
        char a, b;
        for (int i = 0; i < tour.length() - 1; i++) {
            a = tour.charAt(i);
            b = tour.charAt(i + 1);
            distance += distanceBetween(a, b);
        }
        // don't forget to return to home
        distance += distanceBetween(tour.charAt(tour.length() - 1) , tour.charAt(0));
 
        distance += penalties(tour);
        return distance;
    }

My penalties function just says that if a node/city appears more than once, tack on some extra numbers to the distance becase this is not a favorable route. Remember that we want to visit each city only once.

I have some more tweaking to do because I haven’t tested this much, but I’ll post some cool looking results when I get them.

I’m going to start a new project and I thought maybe I’ll do some thinking and planning before I start coding. I’m using Kennedy & Eberhart’s fabulous Swarm Intelligence book again. On page 271 they begin describing an experiment using Axelrod’s Culture Model to solve the Traveling Salesman Problem. I’ve played around with Swarms before, but this one is a bit harder.

In the Traveling Salesman Problem you have a set of cities or nodes. You must find the shortest path that visits all of the cities exactly once, and returns to the first city. If there are C cities, there are C^C possible paths and C! possible legal paths.

In their simulation, they use a set of cities on Cartesian coordinates and contrive a best tour that goes something like ABCDEFGH, starting on any letter and going in any direction. They build an 18×8 population and run it, and it finds the best route most of the time. I’m probably going to go along similar lines.

I’m going to use the Generation 5 JDK because there’s a nice two-dimensional cellular automata torus thing already written for me. I’ll need to develop a method to represent the cities and their coordinates, methods for evaluating distances between cities. I’ll need functions to decide which neighbor has a better “tour” during interactions. I’m not planning to make this with any fancy GUI, so I’ll need some way to display results, monitor some statistics, and determine when it’s “done.”

So, to work…

A different implementation of my swarm code. This one is probably better. Run the applet here.

My first swarm is based on Axelrod’s Culture Model. Axelrod’s Culture Model supposes a population of individuals with attributes, for example, numbers. One individual might look like 13579 and another might look like 97531. They are arranged in a two-dimensional array, such as a 10×10 grid. For each individual, pick one of the four adjacent neigbors at random (up, down, left or right). The chance of these two individuals interacting is based on how similar they are. The more they have in common, the more likely they are to interact. So we go through both individuals attributes and compare them. In our example, they have 1 in 5 symbols in common, which evaluates to 20%. That means there’s a 20% chance they will interact. Now, supposing that they do interact, we pick one of the symbols that DIFFER
and copy it from the neighbor to the individual. If we were operating on 13579 and were interacting with the neighbor 97531, we might copy the 7 from the neighbor and get 17579. Or we might copy the 1 from the neighbor and get 13571. It’s picked at random.

I decided to give the individuals in my population three attributes, values from 0 to 5, which would stand for red, green, or blue. Here are screenshots from the same execution:

Sometimes the population will balance out with one or more huge patches of one color, and the swarm doesn’t change any more. But sometimes it just keeps going, with clouds of color swirling around. You can watch the applet here. The Generation 5 JDK was immensely helpful in the creation of this simulation.