technical-recipes.blogspot.com

Some sample C# code on how a genetic algorithm can be applied to the quadratic assignment problem. The quadratic assignment problem (QAP) is a combinatorial optimization problem that models the following real-life problem: Given a set of n facilities and a set of n locations, specify a distance for each pair of locations and a flow for each pair of facilities, the objective is to assign each facility to a different location such that the sum of the distances multiplied by the corresponding flows is minimised. The problem statement resembles that of the assignment problem, except that the cost function is expressed in terms of quadratic inequalities, hence the name. This example is implemented as a simple console application using C# code developed in Microsoft Visual Studio. To help break down the problem a little, I develop a number of classes for the purposes of encoding potential solutions as chromosomes, maintaining a population of chromosome and applying genetic oper...

Some sample C# code on how a genetic algorithm can be applied to the linear assignment problem. This problem can be efficiently solved using the Hungarian algorithm, but I wanted to demonstrate how the genetic algorithm can produce an optimal solution too. This example is implemented as a simple console application using code developed in Microsoft Visual Studio. To help break down the problem a little, I develop a number of classes for the purposes of encoding potential solutions as chromosomes, maintaining a population of chromosome and applying genetic operators to the population of solutions in the form of crossover, mutation and selection. Code samples as follows: Program.cs The main program loop: [code language="csharp"] using System; namespace LinearAssignmentProblem { class Program { static void Main(string[] args) { var tasks = 5; var popSize = 100; var rnd = new Random(); // Do we seek to maxi...

For the Java equivalent see this link: https://www.technical-recipes.com/2017/applying-the-2-opt-algorithm-to-traveling-salesman-problems-in-java/ For the C++ equivalent see this link: https://www.technical-recipes.com/2012/applying-c-implementations-of-2-opt-to-travelling-salesman-problems/ This post demonstrates how to apply the 2-opt algorithm to a number of standard test problems in C# while displaying the results in a WPF style window, while using the MVVM design pattern. See this link for an overview of the two opt algorithm. http://en.wikipedia.org/wiki/2-opt But essentially the 2-opt link swapping heuristic can be summarised by the following steps: The actual 2-opt heuristic can be summarised by the following pseudocode steps, repeating for all feasible combinations of I and k: [code language="text"] 1. take route[1] to route[i-1] and add them in order to new_route 2. take route[i] to route[k] and add them in reverse order to new_route 3. take r...

This post tackles the problem of applying the 2-opt algorithm to travelling salesman problems in Java. The results of applying the 2-opt heuristic and applying it to a number standard traveling salesman test problems. are shown For a more in-depth description of the 2-opt heuristic, please refer to the following Wiki page: http://en.wikipedia.org/wiki/2-opt The actual 2-opt heuristic can be summarised by the following pseudocode steps, repeating for all feasible combinations of I and k: [code language="xml"] 1. take route[1] to route[i-1] and add them in order to new_route 2. take route[i] to route[k] and add them in reverse order to new_route 3. take route[k+1] to end and add them in order to new_route 4. return the new_route; [/code] A nearest neighbour search algorithm is included in the Java implementation. A comparison is made of the kind of results we get from the 2-opt algorithms, with and without improving the initial tour using the nearest n...

A guide on how to get up and running with Gurobi , a powerful software tool that is well suited to finding solutions to tough optimization problems encountered in industry and academic research. In addition to finding good solutions within practical time scales, I was pleasantly surprised to discover how easy it was easy to use and configure within Microsoft Visual Studio. To apply the Gurobi tools to optimization problems, the developer simply makes calls to Gurobi Application Program Interfaces (APIs) at the appropriate places in the code, tweaking them to suit the application area. The following steps demonstrate how to achieve this for a mixed integer programming problem: 1. Install & Licence Gurobi Run the Gurobi installer file. At the time of writing this post, I installed 32-bit version of Gurobi 6.5.0, using the straightforward 'vanilla' installation: ... thereby installing Gurobi, and it's contents to a default location: 2. Create a new...

A post showing how a genetic algorithm when used appropriately can be used as a powerful means to solve the n-Queens problem of increasing sizes. A downloadable Visual Studio 2010 C++ project implementing the genetic algorithm is available. Problem Description The N-Queens problem is the placement of queens on a chess board so that none are threatened - no single queen share a common row, column, or diagonal. The difficulty of the problem explodes with the number of queens involved and is known to be computation expensive. For example, there are 4,426,165,368 possible arrangements of eight queens on an 8×8 board, but only 92 solutions (source: Wikipedia ). Applying the genetic operators An outline of the genetic algorithm that was applied to this problem and implemented in C++ is as follows: Generate a population of solutions representing the positions of the N number of queens on the chessboard. Solutions ("chromosomes") are represented using integer arra...

Introduction Many real-world optimization problems require multiple, often conflicting objectives, to optimized simultaneously. Historically, their solution was frequently addressed by single fitness function consisting of a weighted sum of the multiple attributes. This approach can be problematic for a number of reasons. Firstly, the final solution obtained can be highly sensitive to small changes in the weighting factors. The result obtained is a single point solution that will largely depend on the weights assigned to each objective. Secondly, this approach is inefficient because it cannot find multiple, Pareto-optimal solutions in a single run. The classical approach would need to be run at least as many times as the desired number of Pareto-optimal solutions.

Sorting networks are networks consisting of wires that carry input values along with a number of interconnections between pairs of these wires, which function as comparators for swapping values on the wires if they are not in a desired order, or leaving them as is if they are. A graphical representation of a simple 4-input sorting network is as follows:

An excellent implementation of the Simplex algorithm exists over at Google Code, written by Tommaso Urli: https://code.google.com/p/cpplex/ Implemented as class library, it relies on no other dependencies other than the C++ Standard Library. I've taken this implementation and compiled it as a Visual Studio application. The only slight modification I needed was to insert: [code language="cpp"]#include <algorithm>[/code] into matrix.cpp then it compiled std::max just fine.

Introduction The flow deviation algorithm as developed by Leonard Kleinrock et al is an efficient means of assigning routes and flows for a given network topology so as to minimize the overall average delay. The problem consists of finding a set of routes for all communicating end nodes which minimize the delay without violating link capacity constraints. The Flow Deviation method works in a manner very similar to gradient methods for functions with continuous variables, whereby the concept of using gradients is replaced by the concept of "shortest path" flows.

Following on from a previous posting on genetic algorithm based routing optimization, further improvements have been made and the source code has been made available. This software is written using MFC / C++ and is essentially a single document interface allowing the user to create network nodes and links by way of standard mouse click actions and enter network parameters using the available menu items.

Introduction Following on from a previous posting on Simulated Annealing applied to travelling salesman problems, here is a posting that carries on in a similar vein, this time focusing on genetic algorithms as our optimization technique of choice.

Introduction Following from a previous post , I have extended the ability of the program to implement an algorithm based on Simulated Annealing and hill-climbing and applied it to some standard test problems. Once you get to grips with the terminology and background of this algorithm, it's implementation is mercifully simple. The algorithm can be tweaked such that it can also be implemented as a greedy hill-climing heuristic.

Introduction Some initial results from experimenting with the 2-opt heuristic and applying it to a standard traveling salesman test problem. C# / WPF equivalent implementation can be found here: https://www.technical-recipes.com/2017/applying-the-2-opt-algorithm-to-travelling-salesman-problems-in-c-wpf/ A summary of the 2-opt heuristic is given here: http://en.wikipedia.org/wiki/2-opt A nearest neighbour search algorithm is included in the implementation. A comparison is made of the kind of results we get from the 2-opt algorithms, with and without improving the initial tour using the nearest neighbour algorithm.

Introduction An example of how a genetic algorithm can be applied to optimize standard mathematical functions, such as the Rosenbrock function. (Image obtained from the Wikipedia page.)

(For source code see this updated post .) Introduction This post describes the use of a tool written in C++ that could be used to assist a network designer in establishing an optimal set of virtual paths in ATM networks. In broadband ATM networks, the cellD based switching capacity is frequently built over digital cross connect system (DCS) networks.  The DCS network can be considered the backbone for connecting ATM switches and for reconfiguration.  As a consequence, the problem confronted by the system designer is how to configure the optimal topology and capacities within the DCS network.