Du nouveau dans le problème du voyageur de commerce!

17 septembre 2017

Le problème du voyageur de commerce est un des problèmes d’optimisation les plus étudiés autant en mathématiques qu’en informatique.  Bon nombre de chercheurs ont travaillé sur ce problème complexe, en grande partie à cause de son énorme utilité dans le monde réel.

Une avancée récente (décrite ici) risque de relancer l’intérêt pour cet problème d’optimisation.

Pour les plus curieux, un site web incontournable traitant de ce problème.


Freewill in progress (2)

3 août 2016

Freewill Selection Policies(Click to enlarge)

What’s up?

As you can see, Freewill now supports 17 different selection policies.  At this point, all of them are coded but only half of them have been tested.

The 11 available termination policies are coded, half of them tested.

So far, only 2 mutation policies are available.  Both of them are coded and tested. I will probably need a few extras for TSP type of problems as well as numerically parametrized problems (e.g. De Jong functions with a domain for each variable).  I’ll probably add 3-4 other ones specific to the problem that started all this adventure!

Only one immigration policy (no immigration!) is available and it will stay that way for a long time.  I’ll wait until I am hyper confident that this framework is rock solid before introducing parallelism and exchange of individuals between « islands » (i.e. simulations).  This one is a faaaaaaar away!

Six crossover policies are available as of now .  This area will require some (minor I think at first glance) changes for the TSP type of problems : not quite decided on the approach I will take to solve this.  Since crossover is often very problem/chromosome specific, I’ll probably delay those change until the end, once I have all examples coded and ready to be tested to have a better idea of what is needed.  But I will definitely add a few (3-4) crossover policies tailored for the Ruzzle problem.

I have solved the discrepancy (see here and here) between my results and the TSPLIB ones regarding the tour length of the Burma14 problem.  Will probably add a lot bigger TSP problem to see how the framework can handle an extremely huge search space! Oh!  And I need to clean up all the crap I added/modified while looking for the problem of « distance difference » : 2 classes were butchered in the process!

I need to add a few « crash test dummy » classes to test all those different selection policies (and crossover) in a simpler and more efficient manner!  Or I should kick myself in the %*&#$!@ and code the « bits » example classes…

I will soon work on a customizable display of statistics.  All that’s needed is already there, it’s just a matter of gluing everything together!

Once I’m done with the 8 queens problems, I’ll attack the numerically parametrized problems.  Will probably have 2-3 examples (from De Jong functions) as well as the INSANE Griewank function.

The classes used for randomly choosing the next parent chromosomes as well as scaling/ranking can be optimized.  But since they just work great since day 1, I’ll keep that for the very end.  But I know they can be a lot faster than what they are right now.

I also plan on having a very basic export mechanism so I can dump all those ruzzle chromosomes in a MySQL database to be able to do some reporting and study the various policies and their effects.

I started adding comments to the classes, mostly to keep references, maintain a todo list per class and add some notes for myself to quickly remember why things work that way!

I’ll probably have an image by tomorrow that will run simulations for the ruzzle problem full-time. I wanna beat that record!






Does 1/7 + 6/7 = 1 ?

1 août 2016

Number precision in Smalltalk(Click on image to enlarge)

We often forget how Smalltalk handles some stuff with class (no pun intended!), efficiency and precision…  Mostly because it’s always been that way!  That’s a given for Smalltalkers!

Recently, I was brutally reminded how sad this world is while trying to solve the Burma14 TSP problem.  I couldn’t figure out why I kept having a +24 km difference for the optimal tour so I started looking on the internet.  My program was finding the optimal tour but I could never get a tour length of 3323 km!

I first thought I wasn’t using the proper function to calculate distances.  Then I thought the reference ellipsoid I was using might be different than the one used to come up with 3323 km.  Then I though it could be caused by rounding errors in my code so I used ScaledDecimal, then I thought this, then I thought that, then I read more, then followed links, then more links, then more debugging, then…

Then I found the TSPLIB FAQ.  The culprit happens to be in the degrees to radians conversion method that is used in TSPLIB calculations. It’s not precise.  It’s not very precise at least.  And the value of Pi used in the calculations seems good enough to do the job but, quite frankly, I don’t think it is!  If I can get a 24km difference for a tour of only 14 cities, what would it be like for a tour of a few thousand cities?

Smalltalkers often forget that, in our world, 1/7 + 6/7 equals 1.  And that evaluating 1000!/999! doesn’t bomb and it equals 1000.  And I’m grateful that things are as they should be… in Smalltalk!

Note: if you look at the image at the beginning of this post, you’ll see that in Smalltalk evaluating 1/7 + 6/7 = 1 and  1000!/999! = 1000. And Pi is a little bit more than 3.141592.



Freewill in action

19 juillet 2016

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!

First look at Freewill in action

What’s new?

19 juillet 2016

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.


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


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!


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!


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!


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!


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

14 avril 2015

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.

Problème du voyageur de commerce

6 février 2015

Le problème du voyageur de commerce, mieux connu sous le nom de Traveling Salesman Problem (TSP), me fascine depuis longtemps.  C’est le genre de défi mathématique qui pousse le domaine informatique dans ses derniers retranchements.  Ce problème exige des solutions algorithmiques de plus en plus intelligentes, efficaces et complexes sans qu’on en vienne à bout de façon satisfaisante.

Pour en savoir plus sur le TSP,  il y a l’excellent site de l’Université de Waterloo sur le sujet.