Project: Bandwidth reduction

This post is a follow-up to the problem of bandwidth reduction presented earlier. I've done a small Delphi application that can generate sparse matrices of various sizes and densities (the density of a sparse matrix is the percent of non-zero elements is contains) and that features 3 (well, actually more like 2) bandwidth reduction algorithms. The first algorithm is the original Cuthill-McKee algorithm, the second one is the Reverse Cuthill-Mckee algorithm (both of which have been covered in detail) and the third algorithm I've decided to implement is a genetic algorithm.
.

I must say that I was very curious to see how a genetic algorithm would perform on this problem as the bandwidth reduction problem is basically a combinatorial problem. As it turns out there is a really nice study performed by A. Lim, B. Rodrigues and F. Xiao that covers this exact topic. The three researchers carry on the work of R. Marti and V. Campos in trying to use a metaheurisc approach in order to obtain better results than the classic bandwidth reduction algorithms (RCM and GPS).
.

Although genetic algorithms perform very well in global search, some researchers argue that they are less suitable for highly tuned search. As such, Lim, Rodrigues and Xiao combined their genetic algorithm with a hill climbing approach. The resulting hybrid (memetic) algorithm performs very well and generally produces solutions of better quality than the Reverse Cuthill-McKee algorithm.
.

My implementations of the CutHill-McKee algorithm and of the genetic algorithm are by no means optimal! (the genetic algorithm is also slightly modified). Hence, both algorithms perform relatively poor (in terms of speed) compared with their creators' estimations. However, the main purpose of this project was to show that in the field of NP-complete problem solving, metaheuristic approaches, although considered rather slow, can be expected to produce very high quality results.
.
You cand download a fully working version of the application (source code included) by clicking here or from the Downloads box (BandwidthReduction.zip). Here are two screenshots:

And here is an example of how RCM and the hybrid metaheuristics-based algorithm performed on a 150x150 randomly generated simetric sparse matrix with a density of 3.5% (788 non-zero elements):

1. The initial sparse matrix. (bandwidth = 142)

 
2. The solution obtained using RCM. (bandwidth = 81)

 
3. The solution obtaind using the hybrid genetic + hill climbing algorithm. (bandwidth = 65). This solution was obtained after 15 generations using a mutation rate of 40%.

Application platform: Win32

Project: AutomatedTimetable

This project is the result of a university team-assignment me and my colleagues signed up for in the spring of 2008. The goal was to build an automated timetabling solution that would aid in the generation of our department's timetable.

.

The application had to implement the following features:

- it should allow the user to specify the general planning context (the number of professors, the student groups, the number of lectures, the type of a given lecture, available classrooms, etc.);

- it should enable the user to specify a certain constraints (some lectures are to be held in a particular classroom, some professors are available only in some time periods, etc.);

- it should automatically generate in a reasonable amount of time "the best" timetable in accordance to the given planning context and the constraints that must be enforced (given that a solution to the planning problem exists);

- it must export timetables for each student group, professor and classroom in both a .pdf and .xml format;

As the problem at hand was fairly complex, the workload for this project was clearly divided between the 4 team members:

- Andrei Niciu was in charge of developing the main Delphi application which, besides integrating all other parts of the project, offers custom made, smart and extremly user friendly tools for manipulating planning contexts and related constraints;
- Alexandra Kulcsar developed the Java export module that generates the beautifully looking .pdf files that represent the solution of the given timetabling problem;
- Mihaela Radescu worked on the comunication protocol between the different modules of the application, providing valuable means of data conversion and storage.
- I worked on finding adapting and implementing the automated timetabling algorithm employed in the project. This type of scheduling problem has been proved to be NP-complete so the search for a good heuristic or metaheuristic was on.

This scheduling algorithm is derived from the one proposed by M. Chiarandini, M Birattari, K. Socha and O. Rossi-Doria in their 2006 article in the Springer Journal of Scheduling. It is based on construction heuristics and metaheuristics (local search, tabu search, simulated annealing). The proposed algorithm also tries to divide the general timetabling problem into two smaller ones that are resolved sequentially:

1. an existential problem (try to find a scheduling configuration that doesn't break any hard constraints);
2. an optimization problem (take a solution to the existential problem and improve it so that it breaks the fewest number of soft constraints);

After finishing my work on the AutomatedTimetable application, I've continued experimenting with various scheduling methods and my Bachelor's Thesis presents my version of a lightweight scheduling algorithm inspired by the works of M. Chiarandini & Co. I've also rewritten the original Delphi Component used by the AutomatedTimetable such as to employ the new algorithm and thus benefit from its improvements (new structure for the soft constraint optimizer, multithreading and thread trimming stages).

You can download a fully working version of the AutomatedTimetable application by clicking here or from the Downloads box (AutomatedTimetable.zip). Unfortunately, for now, the application does not have any help files. If you have any questions regarding how to use it, please don't hesitate to ask. Here are some screenshots:
 

Application platform: Win32 + Java (JRE)

Project: DOthello

DOthello is my implementation of the classic Othello (aka Reversi) board game. The starting point of the project was an AI lab assignment regarding game trees (minmax, alpha-beta pruning, etc). I've decided not only to implement these algorithms but also incorporate them into a fun and easy to use application. DOthello has a quick in-game save and load mechanism and the position of the game board can be adjusted by selecting its margin and dragging it.

.

The program was written in Delphi and for the graphics part I've used OpenGL. For DOthello, I've also designed my own meshes and textures.

The game features the following AI players:

1. Dazzy - a random player;
2. Jabba - an alpha-beta player with a mainly greedy evaluation function
3. Bugzy - an alpha-beta player with a mainly very basic mobility based evaluation function;
4. BOB - an alpha-beta player with with a mobility function that combines basic mobility with piece count and weighted positions;
5. Dexter - an alpha-beta player with a slightly more advance mobility limiting evaluation function that also relies on piece count and weighted positions; 

All AI's perform searches to a depth of 5 ply in early and midgame and 13 ply in endgame. Here are two snapshots from the application:
 

I don't think that any experienced Othello player would have a problem in defeating all of these AI's easily as they are fairly basic, but for a novice the game should be rather interesting.

.

I submitted DOthello to FDAC on delphi.about a few months back. You can download a fully working version of DOthello (source code and resources included) by clicking here or from my Downloads box (DOthello.zip).

Application platform: Win32 + OpenGL support

Project: AFN to AFD

AFN to AFD is one of my very first programs written in C (in 2005). I just came across it as I was cleaning up one of my old project folders. The main objective of the program is to convert a non-deterministic finite automata (AFN) into a deterministic finite automata (AFD) and to display, using C style graphics, the two types of automata. Here are two screenshots (in the left one, we have the AFN and in the other one, the resulting AFD):

You can download a fully working version of this project (source code included) by clicking here or from the Downloads box (AFNtoAFD.zip). The file help.txt contains detailed information about the format of the input file.

Application platform: Win32, MS-DOS

Project: Ground Attack

Ground Attack is an arcade game that I wrote in Delphi (OpenGL API) during my 2005 spring break for a private customer. The game itself is very simple and not very original (in fact I had to design the whole gameplay in order to imitate a demo previously released by Garage Games). The challenging thing about this project was the fact that I had to develop an easy to change and general design and the fact that I had to make my own textures as well.
.
You can download a fully working version of Ground Attack by clicking here or from the Downloads box (GroundAttack.zip).

Application platform: Win32 + OpenGL support

Project: DWS

DWS (Digital Weather Station) was a weather monitoring system designed to monitor the skiing conditions that a certain skiresort could offer in winter. I worked on this application together with my colleagues Andrei Niciu & Marius Popescu (microcontroller programmer and hardware module designer) and managed to finish most of it over the course of 3-4 months in 2005. The project won the 1st Gold Medal in the 2005 edition of Infomatrix (hardware control section). Here is a short description and some photos:

The DWS system measures, with the help of sensors, the temperature (of the air and of the snow), the pressure, the humidity, the wind speed, the wind direction, the fog density, and of course the snow layer in certain key points along the slopes. All these sensors are incorporated into compact modules and controlled by microcontrollers.
The application gathers information from all the modules, and creates, using simulation algorithms an accurate virtual 3D model of each slope. The operator can thus have a perspective view of the entire slope and can issue prompt warnings about avalanches, heavy fog, heavy winds, unskiable portions of the slope etc.
The program can also be used for live-monitoring of the slopes as it can access LAN cameras situated at various interest points in the resort.

Project: Virtual Architect

From time to time I'll present on this blog a few of the programs/projects I've worked on since I got into IT&C as well as other stuff I'll consider somewhat interesting :)). 

First off is Virtual Architect, a light-weight modeling program and the very first "big project" I ever worked on. And that was very rewarding work as the project was submitted in the 2004 edition of Infomatrix and won the 1st Gold Medal in the programming section. Here is an old description of the application and some snapshots.

Virtual Architect was designed to be an easy to use modeling program that would enable any user to create plans for various buildings with the help of a 2D drawing board and to preview these buildings in a 3D environment.
Thus, the drawing board will be used in the actual development of the architectural project (the placement, resizing and movement of walls, ceilings, stairs, doors, windows and furniture) but, at any stage of development for a given project, the user can preview the design using the 3D rendering engine. The 3D engine incorporates simple features like: collision detection and response, gravity movement, basic lighting and skybox concept.
I developed this application back in 2004, over the course of 4 months, with the help of my colleague and friend Andrei Niciu. He worked on the main platform of the program and I designed the 3D rendering engine employed in the program.