alext - Developer IT

Boosting my GA with Neural Networks and/or Reinforcement Learning

- by AlexT

As I have mentioned in previous questions I am writing a maze solving application to help me learn about more theoretical CS subjects, after some trouble I've got a Genetic Algorithm working that can evolve a set of rules (handled by boolean values) in order to find a good solution through a maze. That being said, the GA alone is okay, but I'd like to beef it up with a Neural Network, even though I have no real working knowledge of Neural Networks (no formal theoretical CS education). After doing a bit of reading on the subject I found that a Neural Network could be used to train a genome in order to improve results. Let's say I have a genome (group of genes), such as 1 0 0 1 0 1 0 1 0 1 1 1 0 0... How could I use a Neural Network (I'm assuming MLP?) to train and improve my genome? In addition to this as I know nothing about Neural Networks I've been looking into implementing some form of Reinforcement Learning, using my maze matrix (2 dimensional array), although I'm a bit stuck on what the following algorithm wants from me: (from http://people.revoledu.com/kardi/tutorial/ReinforcementLearning/Q-Learning-Algorithm.htm) 1. Set parameter , and environment reward matrix R 2. Initialize matrix Q as zero matrix 3. For each episode: * Select random initial state * Do while not reach goal state o Select one among all possible actions for the current state o Using this possible action, consider to go to the next state o Get maximum Q value of this next state based on all possible actions o Compute o Set the next state as the current state End Do End For The big problem for me is implementing a reward matrix R and what a Q matrix exactly is, and getting the Q value. I use a multi-dimensional array for my maze and enum states for every move. How would this be used in a Q-Learning algorithm? If someone could help out by explaining what I would need to do to implement the following, preferably in Java although C# would be nice too, possibly with some source code examples it'd be appreciated.

Read the article

Using GA in GUI

- by AlexT

Sorry if this isn't clear as I'm writing this on a mobile device and I'm trying to make it quick. I've written a basic Genetic Algorithm with a binary encoding (genes) that builds a fitness value and evolves through several iterations using tournament selection, mutation and crossover. As a basic command-line example it seems to work. The problem I've got is with applying a genetic algorithm within a GUI as I am writing a maze-solving program that uses the GA to find a method through a maze. How do I turn my random binary encoded genes and fitness function (add all the binary values together) into a method to control a bot around a maze? I have built a basic GUI in Java consisting of a maze of labels (like a grid) with the available routes being in blue and the walls being in black. To reiterate my GA performs well and contains what any typical GA would (fitness method, get and set population, selection, crossover, etc) but now I need to plug it into a GUI to get my maze running. What needs to go where in order to get a bot that can move in different directions depending on what the GA says? Rough pseudocode would be great if possible As requested, an Individual is built using a separate class (Indiv), with all the main work being done in a Pop class. When a new individual is instantiated an array of ints represent the genes of said individual, with the genes being picked at random from a number between 0 and 1. The fitness function merely adds together the value of these genes and in the Pop class handles selection, mutation and crossover of two selected individuals. There's not much else to it, the command line program just shows evolution over n generations with the total fitness improving over each iteration. EDIT: It's starting to make a bit more sense now, although there are a few things that are bugging me... As Adamski has suggested I want to create an "Agent" with the options shown below. The problem I have is where the random bit string comes into play here. The agent knows where the walls are and has it laid out in a 4 bit string (i.e. 0111), but how does this affect the random 32 bit string? (i.e. 10001011011001001010011011010101) If I have the following maze (x is the start place, 2 is the goal, 1 is the wall): x 1 1 1 1 0 0 1 0 0 1 0 0 0 2 If I turn left I'm facing the wrong way and the agent will move completely off the maze if it moves forward. I assume that the first generation of the string will be completely random and it will evolve as the fitness grows but I don't get how the string will work within a maze. So, to get this straight... The fitness is the result of when the agent is able to move and is by a wall. The genes are a string of 32 bits, split into 16 sets of 2 bits to show the available actions and for the robot to move the two bits need to be passed with four bits from the agent showings its position near the walls. If the move is to go past a wall the move isn't made and it is deemed invalid and if the move is made and if a new wall is found then the fitness goes up. Is that right?

Read the article

Can I get a person's display name or composite name from Apple AddressBook on OSX platform?

- by AlexT

I have come across ABRecordCopyCompositeName() in these pages but, having Spotlighted it, have a hunch it's only available for the IOS platform. The AddressBook app itself, and ABPeoplePicker obviously do something similar internally, so is there an equivalent API for OSX? It's a tedious thing to retrieve title, first name, middle name, last name, suffix and work out if it's a company before building it yourself.

Read the article

Bundle package everything

- by AlexT

Hello all. I want pack not installed gems but also which fetched from repositories, for example: I want pack paperclip which declared in Gemfile: gem 'paperclip', :git => 'git://github.com/thoughtbot/paperclip.git', :branch => 'rails3' Thanks

Read the article

Factorising program not working. Help required.

- by Ender

I am working on a factorisation problem using Fermat's Factorization and for small numbers it is working well. I've been able to calculate the factors (getting the answers from Wolfram Alpha) for small numbers, like the one on the Wikipedia page (5959). Just when I thought I had the problem licked I soon realised that my program was not working when it came to larger numbers. The program follows through the examples from the Wikipedia page, printing out the values a, b, a2 and b2; the results printed for large numbers are not correct. I've followed the pseudocode provided on the Wikipedia page, but am struggling to understand where to go next. Along with the Wikipedia page I have been following this guide. Once again, as my Math knowledge is pretty poor I cannot follow what I need to do next. The code I am using so far is as follows: import java.math.BigInteger; /** * * @author AlexT */ public class Fermat { private BigInteger a, b; private BigInteger b2; private static final BigInteger TWO = BigInteger.valueOf(2); public void fermat(BigInteger N) { // floor(sqrt(N)) BigInteger tmp = getIntSqrt(N); // a <- ceil(sqrt(N)) a = tmp.add(BigInteger.ONE); // b2 <- a*a-N b2 = (a.multiply(a)).subtract(N); final int bitLength = N.bitLength(); BigInteger root = BigInteger.ONE.shiftLeft(bitLength / 2); root = root.add(b2.divide(root)).divide(TWO); // while b2 not square root while(!(isSqrt(b2, root))) { // a <- a + 1 a = a.add(BigInteger.ONE); // b2 <- (a * a) - N b2 = (a.multiply(a)).subtract(N); root = root.add(b2.divide(root)).divide(TWO); } b = getIntSqrt(b2); BigInteger a2 = a.pow(2); // Wrong BigInteger sum = (a.subtract(b)).multiply((a.add(b))); //if(sum.compareTo(N) == 0) { System.out.println("A: " + a + "\nB: " + b); System.out.println("A^2: " + a2 + "\nB^2: " + b2); //} } /** * Is the number provided a perfect Square Root? * @param n * @param root * @return */ private static boolean isSqrt(BigInteger n, BigInteger root) { final BigInteger lowerBound = root.pow(2); final BigInteger upperBound = root.add(BigInteger.ONE).pow(2); return lowerBound.compareTo(n) <= 0 && n.compareTo(upperBound) < 0; } public BigInteger getIntSqrt(BigInteger x) { // It returns s where s^2 < x < (s+1)^2 BigInteger s; // final result BigInteger currentRes = BigInteger.valueOf(0); // init value is 0 BigInteger currentSum = BigInteger.valueOf(0); // init value is 0 BigInteger sum = BigInteger.valueOf(0); String xS = x.toString(); // change input x to a string xS int lengthOfxS = xS.length(); int currentTwoBits; int i=0; // index if(lengthOfxS % 2 != 0) {// if odd length, add a dummy bit xS = "0".concat(xS); // add 0 to the front of string xS lengthOfxS++; } while(i < lengthOfxS){ // go through xS two by two, left to right currentTwoBits = Integer.valueOf(xS.substring(i,i+2)); i += 2; // sum = currentSum*100 + currentTwoBits sum = currentSum.multiply(BigInteger.valueOf(100)); sum = sum.add(BigInteger.valueOf(currentTwoBits)); // subtraction loop do { currentSum = sum; // remember the value before subtract // in next 3 lines, we work out // currentRes = sum - 2*currentRes - 1 sum = sum.subtract(currentRes); // currentRes++ currentRes = currentRes.add(BigInteger.valueOf(1)); sum = sum.subtract(currentRes); } while(sum.compareTo(BigInteger.valueOf(0)) >= 0); // the loop stops when sum < 0 // go one step back currentRes = currentRes.subtract(BigInteger.valueOf(1)); currentRes = currentRes.multiply(BigInteger.valueOf(10)); } s = currentRes.divide(BigInteger.valueOf(10)); // go one step back return s; } /** * @param args the command line arguments */ public static void main(String[] args) { Fermat fermat = new Fermat(); //Works //fermat.fermat(new BigInteger("5959")); // Doesn't Work fermat.fermat(new BigInteger("90283")); } } If anyone can help me out with this problem I'll be eternally grateful.

Developer IT