Einfaches hill-climbing-Algorithmus?
Ich versuche, den Einfachen hill-climbing-Algorithmus zur Lösung des travelling salesman problem. Erstellen Sie ein Java-Programm, dies zu tun. Ich weiß, es ist nicht die beste, jedoch möchte ich hauptsächlich, um zu sehen, die Ergebnisse und vergleichen Sie anschließend die Ergebnisse mit den folgenden, die ich auch erstellen:
- Stochastische Hill-Climber
- Random-Restart Hill-Climber
- Simulated Annealing.
Sowieso zurück zu den einfachen hill-climbing-Algorithmus habe ich bereits diese:
import java.util.*;
public class HCSA
{
static private Random rand;
static public void main(String args[])
{
for(int i=0;i<10;++i) System.out.println(UR(3,4));
}
static public double UR(double a,double b)
{
if (rand == null)
{
rand = new Random();
rand.setSeed(System.nanoTime());
}
return((b-a)*rand.nextDouble()+a);
}
}
Ist das alles, was ich brauche? Ist dieser code auch richtig..? Ich habe eine Reihe von verschiedenen Datensätze in text-Dokumente, die ich will, das Programm zu Lesen und dann Ergebnisse produzieren.
Würde wirklich zu schätzen jede Hilfe bei diesem.
- - - - - - EDIT - - - - -
Ich war ein idiot und öffnete die Java-Datei direkt in Eclipse, wenn ich sollte Sie öffnen im Editor erstmal.. hier ist der code den ich nun habe.
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
{
//Print a 2D double array to the console Window
static public void PrintArray(double x[][])
{
for(int i=0;i<x.length;++i)
{
for(int j=0;j<x[i].length;++j)
{
System.out.print(x[i][j]);
System.out.print(" ");
}
System.out.println();
}
}
//reads in a text file and parses all of the numbers in it
//is for reading in a square 2D numeric array from a text file
//This code is not very good and can be improved!
//But it should work!!!
//'sep' is the separator between columns
static public double[][] ReadArrayFile(String filename,String sep)
{
double res[][] = null;
try
{
BufferedReader input = null;
input = new BufferedReader(new FileReader(filename));
String line = null;
int ncol = 0;
int nrow = 0;
while ((line = input.readLine()) != null)
{
++nrow;
String[] columns = line.split(sep);
ncol = Math.max(ncol,columns.length);
}
res = new double[nrow][ncol];
input = new BufferedReader(new FileReader(filename));
int i=0,j=0;
while ((line = input.readLine()) != null)
{
String[] columns = line.split(sep);
for(j=0;j<columns.length;++j)
{
res[i][j] = Double.parseDouble(columns[j]);
}
++i;
}
}
catch(Exception E)
{
System.out.println("+++ReadArrayFile: "+E.getMessage());
}
return(res);
}
//This method reads in a text file and parses all of the numbers in it
//This code is not very good and can be improved!
//But it should work!!!
//It takes in as input a string filename and returns an array list of Integers
static public ArrayList<Integer> ReadIntegerFile(String filename)
{
ArrayList<Integer> res = new ArrayList<Integer>();
Reader r;
try
{
r = new BufferedReader(new FileReader(filename));
StreamTokenizer stok = new StreamTokenizer(r);
stok.parseNumbers();
stok.nextToken();
while (stok.ttype != StreamTokenizer.TT_EOF)
{
if (stok.ttype == StreamTokenizer.TT_NUMBER)
{
res.add((int)(stok.nval));
}
stok.nextToken();
}
}
catch(Exception E)
{
System.out.println("+++ReadIntegerFile: "+E.getMessage());
}
return(res);
}
}
- "Ist dieser code auch richtig.. ?" -- der richtige für was? Ich kann nicht sehen, hill climbing Algorithmus in es. Außerdem würde ich nur initialisieren
rand
innenmain()
und loszuwerden, den test innerhalbUR()
. - Gut für den Gang durch ein paar Datensätze mit dem hill climbing Algorithmus. Die datasets, die als tour-Strecken. Wie es aussieht nicht, was ich dachte, es Tat. Etwas verwirrt jetzt. Danke für den anderen Tipp.
- Gerade festgestellt, dass die Beschreibung für den java-snippet oben geschrieben "drei Methoden in eine TSP-java-Klasse, zum Lesen in ein array (Stadt Entfernung-Datei), drucken Sie ein array und lese in einer tour-Datei (integer-Liste-Datei)." Bin ich etwas fehlt?
- Simulated Annealing wird ziemlich schwer zu bekommen Recht (und einfach falschen). Werfen Sie einen Blick auf die Quellcode von Drools Planner (java, open source)
- Ist das, was ich oben eigentlich eine einfache hill climb-Algorithmus? Ich Suche simulated annealing ein wenig später, aber ich kann nicht sogar das noch..
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ich bin mir nicht sicher, was der code, den Sie eingefügt hat zu tun mit den Traveling Salesman. Sie haben eine Funktion
UR
erzeugt eine Zufallszahl im Intervall[a,b)
.Können Sie vergleichen Sie Ihre Ergebnisse gegen die code-repository für das lehrbuch
"Künstliche Intelligenz-ein Moderner Ansatz", hier ist der aima-code-repository.
Ihre Hügel klettern Umsetzung ist HillClimbingSearch.java