Heuristiques : descente et recuit simulé

Une partie du travail consiste à compléter le fichier Recuit.java. Une autre partie du travail consiste en le réglage du recuit simulé.

• Le fichier Voyageur.java contient tout ce qui concerne l'interface graphique.
• Le fichier GestionnaireVoyageur.java contient toutes les données du problème et des méthodes de base utiles à la résolution.
• Le fichier Parametres.java contient tout les éléments graphiques pour choisir les paramètres du recuit simulé.
• Le fichier PanneauTrace.java décrit le panneau dans lequel se fait le dessin du tour.
• Le fichier Heuristique.java contient le code d'une classe qui étend la classe Thread et qui sert de super-classe pour les classes décrivant la descente et le recuit.
• Le fichier Descente.java contient le code de la méthode de descente.
• Le fichier Recuit.java est destiné à contenir le code du recuit simulé ; il reste à le compléter, sa version actuelle étant une sorte de descente aléatoire. Une autre méthode est à compléter, la méthode qui calcule une température initiale pour le recuit en fonction d'un taux d'acceptation initial.
• Le fichier AppliVoyageur.java contient la méthode main.

  Travail à rendre

  A la fin du TP, les élèves devront rendre un document où seront consignés certains résultats (voir plus loin).

  Premier temps : Télécharger les huit fichiers de code, compiler et constater, en exécutant par :
  java AppliVoyageur
  que le recuit dans son état actuel ne fonctionne pas mieux que la descente.

  Deuxième temps : Compléter le fichier Recuit.java pour qu'il s'agisse réellement d'une méthode de recuit.

  Troisième temps : Essayer de régler le recuit pour les deux graphes suivants :
  - la grille 12 * 12
  - un graphe lu dans un fichier et d'ordre 100 ; les élèves auront tous un graphes différent dont le nom sera indiqué par les enseignants. Pour chaque graphe, on indiquera la plus petite longueur déterminée par le recuit et, pour ce recuit, les valeurs des paramètres.

  Les fichiers pour les graphes de test :

  • g100-1
  • g100-2
  • g100-3
  • g100-4
  • g100-5
  • g100-6
  • g100-7
  • g100-8
  • g100-9
  • g100-10
  • g100-11
  • g100-12
  • g100-13
  • g100-14
  • g100-15
  • g100-16
  • g100-17
  • g100-18
  • g100-19
  • g100-20
  • g100-21
  • g100-22
  • g100-23
  • g100-24
  • g100-25

  Quatrième temps : Compléter la méthode calculerTemperatureInitiale pour qu'une température initiale soit calculée en fonction du taux initial d'acceptation de transformations désavantageuses.

  Corrigé

  Recuit.java

  Vous pouvez voir ici une applet correspondant à notre application.

  ---

  Irène Charon, Télécom ParisTech, 2011