Freewill and Ruzzle

(Click to enlarge)

Freewill already shows very good results!

My heart just stopped when I read the last results on the Transcript!  I had done it!  1634, my goal, had been achieved [1]!  I had broken Didier Müller’ record!  The maximum number of French words a ruzzle grid could contain was 1634!

The joy didn’t last long! I quickly realized that I had only equaled Müller’s record (see his results here), finding just another transposition of the 2 grids he had found.

But it’s promising!  The same iteration also found a grid with 1625 words in it, which is still better than Müller’s second best!  I’m currently setting up parallel workers to run 5 genetic algorithms at the same time. And this time, I’ll be looking for grids with more than 1634 words!

I want to break that record!

[1] Note: for those who are wondering what I am talking about, I explain that ruzzle quest here (in French).

Save

Save

Save

Save

Publicité

Genetic Algorithms Introduction

Interested in genetic algorithms?  Here’s a quick-and-short list of some of the best free material out there to get you started.

• Obitko website
• Genetic Algorithms FAQ
• Wikipedia
• A Practical Introduction To Genetic Algorithms
• An Introduction To Genetic Algorithms
• Introduction to Genetic Algorithms
• Genetic Algorithms : Theory and Applications
• Genetic Algorithms

If you ever get serious about genetic algorithms, I recommend you buy Goldberg’s book Genetic Algorithms in Search, Optimization , and Machine Learning.

Save

Save

Freewill in action

The very first image of Freewill (see here for details) in action, trying to solve a ruzzle problem as well as a TSP problem (Burma14) and a simple diophantine equation (Hermawanto)! Click on picture to enlarge!

What’s new?

What’s new?

After a major data loss (I haven’t given up on getting back all my data, mostly code repositories and databases!), I had to start all my pet projects from scratch. Luckily, it’s easier second time around as they say! And, lucky me, I store all my personal stuff on the web! So here’s a list of what’s coming up on this blog.

Ruzzle

Even though I had a decent working version of the genetic algorithm program to find the best ruzzle grid (original posts in French here, here and here), I wasn’t satisfied with the code.  It slowly evolved from a bunch of code snippets into something I could somehow call a genetic algorithm.  Problem was that my solution was tailored for this specific problem only!  Since I lost all the Smalltalk code, I redid the whole thing from scratch : better design, simpler API, more flexible framework.  I can currently solve a TSP problem, the best ruzzle grid search and a diophantine equation.

I also plan to provide examples of the 8 queens problem, the knapsack problem, a quadratic equation problem, a resource-constrained problem and a simple bit-based example with the GA framework.  Besides, the are now more selection operators, more crossover operators, more termination detectors (as well as support for sets of termination criteria!), cleaner code and the list goes on!  So I’ll soon publish a GA framework for Pharo.

As most of you know, the Rush fan in me had to pick a project name in some way related to my favorite band!  So the framework will be called Freewill, for the lyrics in the song :

Each of us
A cell of awareness
Imperfect and incomplete
Genetic blends
With uncertain ends
On a fortune hunt that’s far too fleet

Bingo

A stupid quest I’ll address after the first version of my GA framework is published.  It all started with a simple question related to the game of bingo (don’t ask!) : can we estimate the number of bingo cards sold in an event based on how many numbers it takes for each card configuration to have a winner?  So it’s just a matter of generating millions of draws and cards à la Monte Carlo and averaging how many numbers it takes for every configuration.  Why am I doing that?  Just because I’m curious!

Glorp

There’s been a lot of action on the Pharo side and Glorp.  I plan on having a serious look at the latest Glorp/Pharo combo and even participate to the development!

Sudoku

I’ll translate my articles (in French here, here and here) on the SQL sudoku solver in English and test the whole thing on the latest MySQL server.  Besides, db4free has upgraded to a new MySQL server version!

NeoCSV

I had done a port of NeoCSV to Dolphin right before losing all my code data.  Wasn’t hard to port so I’ll redo it as soon as I reinstall Dolphin!

Smalltalk

It’s time to reinstall VisualAge, VisualWorks, Squeak, ObjectStudio and Dolphin and see what’s new in each environment!  From what I saw, there’s a lot of new and interesting stuff on the web side.  Add to that the fact that most social media platforms have had significant changes in their respective APIs recently, so there’s a lot to learn there!

 

That’s a wrap folks!

Problème du voyageur de commerce

Si l’utilisation d’un algorithme génétique pour solutionner le problème du voyageur de commerce vous intéresse, il y a l’excellent article Solving the Traveling Salesman Problem Using Google Maps and Genetic Algorithms. Fait intéressant, ce projet éducatif utilise également Google Maps!  Le code source (JavaScript) est même gratuitement téléchargeable!

Pour des références plus pointues sur le problème du voyageur de commerce (TSP), il y a le site web TSP de l’université de Waterloo.

Ruzzle : mise à jour

Je suis à peaufiner la 2ième partie (de 7) de la série débutée dans cet article.  Je devrais publier ce billet sur les méthodes de création durant la semaine.

Entre-temps, j’ai une version fonctionnelle de mon algorithme génétique : il ne me reste que 3 méthodes de sélection et 3 méthodes d’immigration à coder et à tester.  Ensuite, j’optimiserai certaines parties plutôt lentes du code! Pour l’intant, ça a l’air de ceci (cliquez sur l’image pour agrandir)…