JenPop and Genetic Algorithms on the loose

Hey there! I’ve committed a new class on JenPop, and it’s called “Individual”. It was made to represent the rules of typical genetic algorithms:

I’ve read a bit more on the subject and figured that genetic algorithms, although being able to achieve good solutions with little computing, are only suitable for problems where brute-forcing isn’t feasible. For instance, they do a nice job on combinatorial problems such as the classic knapsack problem, where you have a list of items with value v and weight w, and you must figure what’s the maximum value you can carry in a knapsack of capacity wc by combining different amounts of those items.

And that problem was chosen to serve as the first example. At this kind of problem, a naive approach can easily become unfeasible as the input list grows. With an evolutionary approach there’s a bigger probability that it will result in a better solution, given the same time limits. And even if the solution isn’t better, it will be a decent solution. The more time you let it roll, bigger is the chance of getting a great result.

For the classic scenario with a knapsack with wc = 15, and a (v,w) item list of (4, 12), (2, 2), (2, 1), (1, 1), (10, 4), I was able to achieve the following results:

30 iterations: Best result was { 0, 0, 4, 0, 2 } (v 28, w 12)
100 iterations: Best result was { 0, 3, 0, 9, 0 } (v 15, w 15)
500 iterations: Best result was { 0, 7, 1, 0, 0 } (v 16, w 15)
1000 iterations: Best result was { 0, 3, 4, 4, 0 } (v 18, w 14)
3000 iterations: Best result was { 0, 1, 1, 5, 1 } (v 19, w 12)
5000 iterations: Best result was { 0, 0, 5, 2, 2 } (v 32, w 15)

You can see that while none of those runs delivered the optimal solution, which would be { 0, 0, 3, 0, 3 } (v 36, w 15), they got close enough to provide good solutions. Also, it becomes clear that randomism takes a nice part in this, giving us the chance of achieving a great solution with only 30 iterations. These results also show that the more you let it run, bigger is the chance of getting better results.

Anyway, see you! 😀

JenPop: genetic populations in your hands

I’ve started developing a new hobby project (yeah, why not finish the other projects first?), that can create entire generations of nodes based on a single parent, according to the rules and score methods you provide! It’s JenPop (if you didn’t guess, J is for Java :D, Gen is for genetic, Pop is for population) and I already have code to throw at you!

At the moment, only 2 features are available:

• Create generations and children (of any object) based on the rules you provide, from a parent class extending GeneticNode;
• Get node scores and best nodes based on the rules you provide;

And as a bonus, a sample of Tic Tac Toe implementing the above features, that will never lose. Can’t lose even when playing against itself! 😀 For the moment, the only way you can download and use it is by downloading the tarball from my Google Drive, but I’ll host the project online as soon as I decide where to.

As the next step, I’m aiming into being able to process the best “path” to use after calculating nodes from many generations, looking at the possibilities from the current state. After that, I think I’ll implement some cross-over methods, so that you can “diverse” your population, it’s useful for some problems.

Needless to say, I’m quite happy with the results at this moment.

See ya!