Chapitre 82 : assembleur ARM64 : algorithme génétique appliqué au problème du voyageur de commerce

Pour ce chapitre je vais repartir du livre de Virginie MATHIVET « L’Intelligence Artificielle pour les développeurs »  en suivant le chapitre sur les algorithmes génétiques écrit pour le langage Java. Je pensais utiliser les listes chainées vues au chapitre précédent mais ici cela semble inutile car les données population et génome sont fixes. Il est donc plus performant d’utiliser des tables.

Comme dans le livre, nous allons utiliser ce type d’algorithmes pour résoudre le problème du voyageur de commerce pour 7 villes (PVC). Pour la théorie sur ce type d’algorithme, je vous renvoie au livre ci-dessus ou sur Wikipedia ou autres sites.

Dans le programme genPVS64.s nous commençons par décrire 2 structures de données nécessaires : individu et processus évolutionnaire puis les tables contenant les noms de ville, les pointeurs vers ces noms et une table contenant les distances entre toutes les villes. Ces tables peuvent être complétées ou modifiées sans difficulté . Vous remarquerez la façon de calculer le nombre de postes ce qui évite d’avoir une divergence entre données.

Seule la table population a sa place réservée dans la section BSS. La table génome associée à chaque individu sera créee sur le tas lorsque cela sera nécessaire.

Le code reprend les différentes routines pour traiter le problème. Les commentaires sont suffisamment nombreux pour la compréhension des instructions.

La difficulté d’écriture de longs programmes en assembleur provient de la bonne utilisation des registres. Normalement la convention est de séparer les registres en 3 parties : les  paramètres, les intermédiaires et les permanents. Seuls ces derniers doivent être sauvegardés. Mais cette norme est surtout valable si le programme fait appel à des librairies extérieures. Sur un programme personnel, sans contraintes d’optimisation, il faut surtout veiller à la bonne sauvegarde restauration des registres contenant des données générales. Et hélas j’ai pris de mauvaises habitudes en commençant par utiliser les registres x0,x1 x2 .. au lieu d’utiliser les registres x20, x21 etc.

Il faut aussi veiller à ce que chaque routine ne dépasse pas une taille d’écran afin qu'elle soit lisible en totalité sans avoir à utiliser l’ascenseur.

Enfin vous remarquerez que chaque nom de routine est suivie du mot clé INFO :. Cela me permet dans notepad++ d’utiliser un pluggin qui affiche toutes les routines et facilite leur accès.

Remarque : je n’ai pas encore poussé ce programme avec un nombre de villes plus important pour analyser les résultat.

Merci de me signaler les erreurs éventuelles.

Quelques jours après : j'ai testé de nouveau ce programme avec les 13 préfectures de la région Occitanie. J'ai seulement modifié le générateur de nombres aléatoires pour que ceux ci soient toujours différents après plusieurs lancements du programme.
Le résultat semble satisfaisant car il trouve ce chemin après modification des paramètres :

(+1257)Auch Toulouse Montauban Cahors Albi Rodez Mende Nimes Montpellier Perpignan Carcassonne Foix Tarbes