Posts tagged C++

Project work on genetic algorithms, the TSP and parallelism

Over the course of the last semester I did a project work with the title ‘Approximation of the Traveling Salesman Problem utilising a genetic algorithm in a parallel system‘. As this is a very complex title by itself, I will explain what this work was about in a few sentences. For further details please take a look at the documentation.

The main goal of this project was to develop an algorithm to approximate an optimal tour for the traveling salesman problem, which is in short as follows: A salesman wants to visit X cities under the following conditions:

  • every city must be visited exactly once
  • the tour has to be a round trip

This is a NP-complete problem, meaning there is no efficient algorithm known to solve it in a worthwhile timeframe. Since nobody wants to wait for several years to get an optimal tour, there are some approximation algorithms which are rather good. As multi-core processors are becoming more and more common, programming applications that utilize multiple cores has become an important trait.

This is where genetic algorithms come into play: Offering intrinstic parallelism they’re well suited for parallelization. Also, they are very general in nature: All that’s necessary is to encode the problem in a way the genetic alorithm can handle it. The algorithm does not need any problem-specific information, although it could be used to enhance the results.

The TSPLib was used for sample data, which is pretty nice as there are best known solutions to it.

Build Environment

The program was developed in Linux using eclipse CDT 5.0.1 and CMake 2.6, so this is the recommended environment to build and run it. It also utilizes OpenMP and TR1 for shared pointers, so make sure your compiler supports it. For further details, see How to build.

Building under Windows

By default the build environment is set to linux to compile. If you want to compile it under windows, you have to set the appropriate define in the config.h file:

//#define LINUX
#define WIN_32

Also note that this is a console application, so make sure you’ve set your IDE to the correct system.

Downloads

Disclaimer

It was written to the best of my knowledge, though I can’t guarantee it’s perfectly free of errors. Furthermore, the disclaimer of this blog applies.

Mech Heat Tracker

As my application for the MechWarior: Living Legends Crysis Mod (which was successful, btw 😉 ), I had to implement a Mech Heat Tracker. I was given a template to work from—a class with a couple of method and attribute declarations—and had to work out the implementation details all by myself. I was only given a few instructions (see MechHeatTracker.h).

Basically, this is a simulation of a two-legged combat vehicle called ‘BattleMech’ (in short ‘Mech) which generates lots of heat while fighting. ‘Mechs are equipped with heat sinks to dissipate the excessing heat they are generating. When the excess heat is just too much the heat sinks to cope with they can flush coolant to increase their cooling rate, as long as the coolant tanks don’t run out of it. Heat sink’s effectiveness is affected by the environment (they have a harder time to dissipate heat in the sahara as they would have at the north pole). Also, if the heat exceeds a certain threshold, the heat sinks may take some damage—when they are, their effectiveness is affected.

You can take a look at my implementation by downloading the source files given in the download links below. I’ve also created a little test program (Windows binary), which just generates some random input data for the Mech Heat Tracker and prints the results to the console.

Downloads

Go to Top