Tag Archives: classes

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! 😀

Advertisements

Classes in JacaScript? There’s a way

I was messing with my game prototype when something came along: how do I create objects in this thing? Many of the examples I’ve seen were quite weird, with functions creating new instances of things and being used to define objects. But what about real classes? Inheritance? After all, is there a standard in JavaScript?

Looks like it doesn’t, and many approaches seem to consist in implementing custom sugar functionality or using some weird techniques (from a C++/Java/Python developer’s point of view). I still want to check the examples to establish a memory footprint, because, apart from “static” (in JavaScript, prototype) functions there is no such thing as static beside a “global variable” (that might even contain a function). JavaScript is indeed an easy but weird language. 🙂

Anyway, my project was pushed to GitHub today, there is some basic functionality but not much beside some test bench. I’m working now to reach an architectural model for my objects with shallow inheritances to assure it “stays small” and following some best practices. The JavaScript/HTML5 Netbeans plugin is awesome! Also took some time to try jVI again, I’m more productive with it even with its performance penalty.

 

DVenn: venn diagrams with a cup of coffee

Long time ago, at one college night class, I was quite amazed that my teacher would have to draw over and over again Venn diagrams to explain logic problems and exercises. That class had a projector that was mainly used to display PPS slides. Since I was already quite proficient at Java and Swing development, I started to develop an application to help him by rendering the diagrams based on a logic expression without the need to draw the whole thing on the blackboard.

dvenn

That application was called DVenn and I guess it still helps him on classes. It can present up to 4-way diagrams and automatically adjust the render based on the number of variables. We published a paper about it and presented at some event. I’ve put it on github. I guess it’s still in portuguese, but there’s not much to translate even, so it should be easy to port around.

Looking at the code right now, it seems quite bulky for what it does, but I’m OK with it. Perhaps some day I’ll do some refactoring and call it done.