Assignments 'Real world problems for Genetic Algorithms'

This page contains some additional information to get you started with the two final optimisation problems of the Genetic Algorithm part of this course.

• What you should do
• Software installation
• Suspend/resume functionality
• Charges on a Sphere Problem
• Travelling Salesman Problem

What you should do

Choose either the charges on a sphere or the travelling salesman problem as the main case study in your report, or do both if you are ambitious. The two problems are sketched below, the required exercises are specified as well.

Software installation

The two problems below are set up quite far already for you. Follow the steps below to install it into your current galib/ directory.

• Download galib_problems.tar.gz (available around week 45).
• Save it in your ~/labsci/galib directory and unpack it:

  [labsc@oeleboeter:~]$ cd labsci/galib
  [labsc@oeleboeter:~/labsci/galib/]$ tar zxvf galib_problems.tar
  

• Build and run the sample program spherecharges:

  [labsc@oeleboeter:~/labsci/galib/]$ cd problems/spherecharges
  [labsc@oeleboeter:~/labsci/galib/problems/spherecharges/]$ make
  [labsc@oeleboeter:~/labsci/galib/problems/spherecharges/]$ spherecharges
  

• Build and run the sample program tsp:

  [labsc@oeleboeter:~/labsci/galib/]$ cd problems/tsp
  [labsc@oeleboeter:~/labsci/galib/problems/tsp/]$ make
  [labsc@oeleboeter:~/labsci/galib/problems/tsp/]$ tsp
  

Suspend/resume functionality

Read about, and use the suspend/resume functionality described here.

Charges on a Sphere Problem (spherecharges)

Consider n identical electrically charged particles that are placed on a (unit) sphere in a d-dimensional space. The Coulomb forces will cause all particles to push each other away. The optimal solution, that with lowest Coulomb energy, will have some form of equidistribution of all particles on the sphere.
A generalisation of this problem searches for the minimal Riesz-s energy. The Coulomb energy is just one special case with s=1. More details are in the course book.

Exercises

• Implement the missing parts in the spherecharges sources.
• Do two or more exercises from ex. 4.15–4.17.
• Investigate the effect of mutation/crossover/elitism parameters on the convergence speed of the objective function.

Below are additional suggested exercises that did not make it into the course book yet.

Exercise 5.18: Exploit symmetry

Change HypSphPointSetChromosome in such a way that it removes some freedom due to symmetry.

Exercise 5.19: Platonic solids

For certain numbers of points, the convex polyhedra that are formed by the points should become the platonic solids in the optimal configuration. Try to find these configurations in as little iterations as possible.

Travelling Salesman Problem (TSP)

The travelling salesman problem is a widely known and notoriously difficult optimisation problem. Goal is to find the shortest path that visits all cities in a set exactly once. More details are in the course book.

TSPLIB

TSPLIB is a library of sample instances of the TSP. All problem specifications can be downloaded from the TSPLIB homepage, sometimes including the optimal solutions. In our software, these files can be read in by the function tspProblem.readtspFile. it currently assumes the .tsp files to be of: "EDGE_WEIGHT_TYPE: EXPLICIT, EDGE_WEIGHT_FORMAT: FULL_MATRIX"-type. You can extend the function yourself to support more variants. A technical specification of the format can be found in the TSPLIB documentation (PS).

Exercises

Exercise 5.13 summarises what is expected from you, but at least the following is mandatory:

• Implement the missing parts in the tsp sources.
• Think of at least one other type of mutation and crossover, other than is implemented in the gaproblems software already. Investigate its effect on the convergence of the objective function.
• Try to find an optimal solution to the "bays29"-problem (available here) in as little iterations as possible.
• Try to find an optimal solution to a problem of your choice, with at least 70 cities.