Ruzzle : mise à jour (2)

Ce soir, dans le cadre du petit défi (tous mes articles concernant le Ruzzle sont ici) que j’avais relevé il y a de ça belle lurette, j’ai dépassé le cap des 630 millions de grilles générées à l’aide de mon algorithme génétique Freewill sans avoir encore pu dépasser la marque de la meilleure grille de ruzzle (comportant 1634 mots) établie par Didier Müller.  J’ai trouvé plusieurs fois des transpositions des 2 meilleures grilles que lui-même avait trouvé mais je n’ai jamais pu faire mieux!

La recherche de cette meilleure grille va tout de même se poursuivre jusqu’à ce que j’aie terminé la première version de Freewill mais à moindre vitesse!  Il est temps que je me réapproprie quelques CPUs de mon ordinateur!

Freewill in progress (4)

I’m done working on the 8-queens problem.  But while I was at it, I though I’d try something a little bit harder to solve.

(Click on image to enlarge)

Eight queens is fun. Ten queens is better.  But 30 queens is even better!

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

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.

Algorithmes génétiques et marche

Une amusante démonstration visuelle d’un algorithme génétique cherchant à optimiser la marche!