0

I'm trying to use the Simple hill climbing algorithm to solve the travelling salesman problem. I want to create a Java program to do this. I know it's not the best one to use but I mainly want it to see the results and then compare the results with the following that I will also create:

  • Stochastic Hill Climber
  • Random Restart Hill Climber
  • Simulated Annealing.

Anyway back to the simple hill climbing algorithm I already have this:

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);
    }
}

Is this all I need? Is this code even right..? I have a range of different datasets in text documents that I want the program to read from and then produce results.

Would really appreciate any help on this.

----- EDIT ----

I was being an idiot and opened the Java file straight into Eclipse when i should have opened it in notepad first.. here is the code i have now got.

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);
    }
}
5
  • "Is this code even right.. ?" -- right for what? I don't see any hill climbing algorithm in it. Also, I would just initialize rand inside main() and get rid of the test inside UR().
    – Ted Hopp
    Mar 15, 2011 at 5:41
  • Well, right for going through a few datasets using the hill climbing algorithm. The datasets being tour distances. Looks like it does not of what i thought it did. Little confused now. Thanks for the other bit of advice.
    – RED_
    Mar 15, 2011 at 5:52
  • Just found the description for the snippet of java posted above "three methods in a TSP java class, for reading in an array (city distance file), printing an array and reading in a tour file (integer list file)." Am i missing something?
    – RED_
    Mar 15, 2011 at 5:57
  • Simulated Annealing will be pretty hard to get right (and easy to get wrong). Take a look at the source code of Drools Planner (java, open source) Mar 15, 2011 at 8:32
  • Is what i have above actually a simple hill climb algorithm? I will have to looking simulated annealing a little later but i can't even get this yet..
    – RED_
    Mar 16, 2011 at 2:46

2 Answers 2

3

You can compare your results against the code repository for the textbook
"Artificial Intelligence a Modern Approach", here is the aima code repository.
Their hill climbing implementation is HillClimbingSearch.java

2
  • how can i run this program! is there any tutorial to run this source code ..
    – S Gaber
    Dec 24, 2012 at 4:50
  • The tutorial is the textbook which this code accompanies, the home page for the textbook at aima.cs.berkeley.edu
    – crowne
    Dec 24, 2012 at 11:27
2

I'm not sure what the code you pasted has to do with Traveling Salesman. You have a function UR which generates a random number in the interval [a,b).

2
  • oh.. well that's disappointing. I'm completely confused now. I was under the impression that the code uses set numbers at the moment (3,4) and that all i needed to do was change it so that it read the datasets.
    – RED_
    Mar 15, 2011 at 5:50
  • Ok, i just found the description to the snippet of java posted above: "three methods in a TSP java class, for reading in an array (city distance file), printing an array and reading in a tour file (integer list file)"
    – RED_
    Mar 15, 2011 at 5:56

Not the answer you're looking for? Browse other questions tagged or ask your own question.