Applying Ant Colony Optimisation to travelling salesman problems in C#

Some results of applying a C# / WPF implementation of the ant colony optimisation algorithm to the travelling salesman problem (TSP). My initial observation is that it finds fairly reasonable solutions within a given number of iterations, but falls short of algorithms such as two-opt, Lin-Kernighan etc. The software is built around the Model-View-ViewModel (MVVM) architecture, thereby keeping the graphical display and data separate. For an explanation of the ant colony algorithm see the Wikipedia page. Edge selection Each ant iteratively finds a path from the source node, visiting every other node until it reaches the start node again. The intermediate solutions (node choices) are referred to as solution states. At each iteration, each ant moves from a state x to state y, corresponding to a more complete intermediate solution. Thus, each ant k computes a set of feasible expansions to its current state in each iteration, and moves to one of these in probability. For ant k, the probability of moving from state x to state y depends on the combination of two values: 1. the "attractiveness" of the move, as computed by some heuristic indicating the a priori desirability of that move and the trail level of the move, indicating how proficient it has been in the past to make that particular move. The trail level represents a posteriori indication of the desirability of that move. Trails are updated when all ants have completed their path, increasing or decreasing the level of trails corresponding to moves that were part of "good" or "bad" solutions, respectively. In general, the kth ant moves from state x to state y with probability Demonstration of algorithm as follows: https://player.vimeo.com/video/294008591 Obtain the Visual Studio project from here:

Comments

Post a Comment

Popular posts from this blog

Using the Supervisor Controller Pattern to access View controls in MVVM

Image
As discussed on a StackOverflow post , this is considered bad practice, so only use this when necessary. Step 1: Create a new WPF project Step 2: Add event handling code A number of classes are needed for doing command bindings in MVVM. Create the following classes and add to your Visual Studio project: RelayCommand.cs [code language="csharp"] using System; using System.Windows.Input; namespace SupervisorControllingPattern { public class RelayCommand<T> : ICommand { private readonly Predicate<T> _canExecute; private readonly Action<T> _execute; public RelayCommand(Action<T> execute) : this(execute, null) { _execute = execute; } public RelayCommand(Action<T> execute, Predicate<T> canExecute) { if (execute == null) throw new ArgumentNullException(nameof(execute)); _execute = execute; _canExecute = canExecute; ...
Read more

Getting started with client-server applications in C++

Image
A demonstration of simple Internet client-server applications in C++ (Linux-based). The client application tries to connect to the remote server application using the IP address of the remote server ('localhost' or 127.0.0.1) and the server port number which defaulted to 1234. The server application listens to port number 1234 for a connection request. When the server application receives the connection request it sends the text message "Hello!\r\n" to the client.
Read more

How to send an e-mail via Google SMTP using C#

Image
First things first, some useful StackOverflow links: https://stackoverflow.com/questions/9201239/send-e-mail-via-smtp-using-c-sharp https://stackoverflow.com/questions/17462628/the-server-response-was-5-7-0-must-issue-a-starttls-command-first-i16sm1806350 To demonstrate how this is done I first create a new Visual Studio project: Some example code for sending an email via a Google email account (smtp.goolgle.com) - obviously replace this with email / credentials of your own... I put the code within a try-catch block in order to capture any errors that may occur while attempting this. [code language="csharp"] using System; using System.Net; using System.Net.Mail; namespace EmailSmtp { class Program { static void Main(string[] args) { try { // Credentials var credentials = new NetworkCredential("someEmail@gmail.com", "somePassword"); // Mail message var ...
Read more