Skip to content

Genetic Algorithm in LabVIEW to solve the shortest path routine problem

April 16, 2014

I came across Genetic Algorithm (GA) the other day when I was doing the project. It is typically adopted to solve the shortest path routine problem or design and optimize the structure of proteins. It is a very smart algorithm inspired by the biological system.

I will try to describe the idea behind the concept briefly: In some problems there are many possible solutions, and we look for the best one. To find this very best solution it is like creating the chromosome of the genes in the most optimized order. To find out the best (-ish) combination, one way is comparing ALL possible combinations, which is impractical in some cases.  So instead of listing all solutions and comparing them, a sub-group of solutions (population) are created, and then we pick two out of them as the parents. The better the solution was, the higher chance it can be selected. Then the two chromosomes crossover (exchange genes) to “breed” new populations. There is a chance of mutation for the new population as well. The new population are usually more “advanced” than their parent population (not necessarily better than their parents). Then new parents are picked out again to breed new populations and so on.

Typically the genes to order in the chromosome are binary, but we can also do that for integer numbers and other values. Please find this tutorial for more encoding methods.

To demonstrate the implementation of GA in LabVIEW I downloaded the coordinates of 31 cities of China and tried to find out the shortest path routine of them. So here is the .gif demo (the labels for X and Y axises should be “Latitude” and “Longitude”). Please note that this may not be the BEST solution. But in term of the number iterations we ran it, it is good enough.

 

Shortest path routine for 31 cities in China

Shortest path routine for 31 cities in China

You can download this code here:Genetic Algorithm. Please rename it to .zip file and unzip it.

Let me know your score ;)

 

 

A quick update for the Flappy Bird project

April 7, 2014

It seems last post was found by @labview and brought much visiting here. So this project is still undergoing and I was kind of busy this month. But I will try finish this ASAP :)

Here are some updates since last post.

An Arduino controlled stylus now can be controlled by clicking the mouse.

Image

There is a tip that the stylus needs to be earthed (via the red wire) to take affect.

And the Flappy Bird game is (poorly) simulated on LabVIEW. So I simulated FB (not facebook!) on LabVIEW to test the Q-learning algorithm in a purely software environment. Now it can pass 5 gaps :) The algorithm needs to be altered a bit and then I will integrate the whole things.

Image

Implement Q-Learning algorithm in LabVIEW

March 21, 2014

So this is the story: Flappy Bird was so popular that my friend suggested that we should develop a LabVIEW kit with a motor to play it. Two days later, we found Sarvagya Vaish managed to score 1000 by applying Q-learning algorithm. A couple of days later, a studio used arduino to play the game. Hmm…I will finish my work anyway.

That’s where I learned about the Q-learning, one of the reinforcement learning algorithm. Here is a brief tutorial helped me to have a better understanding of it. So if a goal is achieved by multiple steps, this algorithm grades each step by assigning a reward to it. Each step, or action, is not graded right away, but one step later. In this way the “right” action can be determined by the reward it received.

The equation can be described as
Q’(s, a) = (1 – alpha)*Q(s, a) + alpha*(R(s, a) + Gamma * Max[Q(s', all a')])

Where Q (accumulative experience) is a table of s (state) and a (action), s’ is the next state and a’ is the next action. alpha is the step size and Gamma is the discount reward. I tried to google a Q-learning example in LabVIEW but failed. So I created this vi myself and hope it can be useful to someone.

Image

This is a single loop vi and the shift register stores the value for Q. The reset button is to initialize Q’s value and can be replaced by “first call?” node. The user shall build their own “Reward” vi according to their applications. In this vi the next action is determined by the Q value that rewards the most but it can also be a random action (or other methods).

Please find the tutorial links 1 2 for more information about Q-learning algorithm.

Multiclass classification in LabVIEW using SVM and one-vs-all method

January 11, 2014

As I mentioned in the last post, I am now studying machine learning in my new position. Today I came across a problem to use SVM to do multiclass classification. The toolkit (link) downloaded from NI did not provide the ability to do multiclass classification with SVM but only for two classes (it’s quite a useful tool still). So I took use of the SVM VIs and made a multiclass version using one-vs-all method.

There is a good tutorial on one-vs-all or one-vs-rest classification by Andrew Ng (link). So basically we pick one class each iteration as Class A and make the rest classes as Class B. Only the test data that locate in Class A are allocated to the known class. Here is the code:

SVM one-vs-all

The original trained labelled data are classified as Class 0, 1, 2, … N. In the i-th iteration, only the data from Class i are re-classified to Class 1 and the rest data are re-classified to Class 0. When the test data locate in class 1 area, they are classified as Class i. Any unsorted data are left in Class -1. When I test the performance of this one-vs-all classifier, the result seems fine :)

one-vs-all front panel

The code is not optimized and the execution may cost a while.

New year, new job

January 2, 2014

Hi all, hope you had a wonderful Christmas and a happy new year. It’s been 4 months since last post and something changed in my life. I started a new job in a LabVIEW consultancy company based in London. I always love London, in which there are so many places to explore.

So have to say goodbye to the lab and neuroscience. I am doing signal processing with LabVIEW now. It sounds fun and can be a good opportunity for me to learn more about machine learning and advanced LabVIEW programming. I will keep updating the blog and am thinking if I should change the blog title to some more general one ;) (Let machine learn? Let lab wow?).

All the best.

Quit all loops when an error happens in one loop

August 22, 2013
tags: ,

When I tried to do parallel tasks (e.g. multiple producer/consumer loops) in LabVIEW, it was always painful to quit all loops “elegantly”. What I wanted was a notifier to tell all loops when an error occours in any loop. I know there are a few error manager VIs in the internet already but I just reinvented the wheel anyway.

In this error manager.vi there are 3 states: reset (clear errors in the shift registor), read (monitor if there is an error) and hold (stop reading when error).

sub3 sub1 sub2

So I sort of created a functional global variable here using the single loop to store the error. You can use this VI in every loop and it will quit all loops if an error happens. Here is an example:

topNote that we need to initialize the error manger before using it. When an error button is pressed in a loop, all loop will quit.

Hope this is useful to you:)

Days of PhD (9)

March 7, 2013

Yes I changed my style back in this post. Hope you will like it:)DOP_9

Follow

Get every new post delivered to your Inbox.

Join 213 other followers