Skip to main content

Tabu search



Tabu search is a combinatorial optimization problem whereby it tries to look for the best possible solution to a problem such as travelling salesman problem.

When a best move is found it is added into a tabu. List of tabu is used to ensure search path / node is not traverse again. Tabu is remove with each iteration and only when it reaches zero, then search moves forward.

This is to prevent search process to get stuck locally.

For example, please take a look at diagram below. We have 5 location labeled (0, 1, 2, 3, 4) and each has an associated cost. Tabu search is able to tell us minimum cost associated with our chosen path.




We use a 5x5 (2d) matrix to keep track of the cost associated with a edge / path / link.

C# code for this TSP tabu search can be download here. Also included in the code is hill climbing algorithm for solving tsp problem.

The output looks like this

Search done! 
Best Solution cost found = 9
Best Solution :
0 1 2 4 3 0 








Comments

Popular posts from this blog

Android Programmatically apply style to your view

Applying style to your view (button in this case) dynamically is pretty easy. All you have to do is place the following in your layout folder (res/layout)
Let's call this file : buttonstyle.xml
<?xml version="1.0" encoding="utf-8"?> <selector xmlns:android="http://schemas.android.com/apk/res/android"> <item android:state_pressed="true" > <shape> <solid android:color="#449def" /> <stroke android:width="1dp" android:color="#2f6699" /> <corners android:radius="3dp" /> <padding android:left="10dp" android:top="10dp" android:right="10dp" android:bottom="10dp" /> </shape> </item> <item> <shape> <gradient android:startColor="#449def" a…

OpenCover code coverage for .Net Core

I know there are many post out there getting code coverage for .dotnetcore. I'm using opencover to address this needs.

In case, you do no want to use opencover and wanted to stick with vs2015 code coverage, you can try to copy Microsoft.VisualStudio.CodeCoverage.Shim.dll from C:\Program Files (x86)\Microsoft Visual Studio 14.0\Team Tools\Dynamic Code Coverage Tools\coreclr\ and drop it into your project "bin\Debug\netcoreapp1.0" folder.  Please note : you need to be on VS2015 Enterprise to do this. 

To get started, I guess we need to add OpenCover and ReportGenerator for our test projects, as shown in diagram below :-



When nuget packge gets restored, we will have some binaries downloaded to our machine and we going to use this to generate some statistics. I think the biggest issue is to getting those command lines work.

In dotnetcore, we run test project using "dotnet test" (assuming you are in the test project folder - if not please go there)  So we add this …

DataTable does not have AsEnumerable

I have problem locating my AsEnumerable extension method in my DataTabe (System.Data). Thank god for this post by Angel
(http://blogs.msdn.com/angelsb/archive/2007/02/23/does-not-contain-a-definition-for.aspx)

I was able to find this method once i have added reference to the following assembly.

C:\Program Files\Reference Assemblies\Microsoft\Framework\v3.5\System.Data.DataSetExtensions.dll

Try to do a dummy Build and you should be able to get it.