Thread: Simple Hill Climbing algorithm?

Hi everyone,

I need a bit of help in trying to create a simple hill climbing algorithm in order to solve the travelling salesman problem.

I have some pseudo code that i cannot turn into java, mostly because i have not done Java in a while. I was hoping someone on here could help me.

Here is the first bit of pseudo code i have:


1) Create a random integer p that ranges between 0 and n-1.
2) Create an empty new string say x.
3) Copy from elements 0 to p-1 from scasol to x.
4) Copy the changed version of position p of string scasol to x.
5) Copy from p+1 to n-1 of scasol to x.
6) Set scasol to be x.

and here is what i have done so far on it:

public void SmallChange()
	{
	Random rand = new Random();
	rand.setSeed(System.currentTimeMillis());
 
 
	int n = scasol.length();
	int p = Math.abs(rand.nextInt() % n);
	String x;
 
	}

I've basically converted the first two bits of pseudo into java but cannot do the rest, can anyone help? Would really appreciate it.

Here is the second pseudo code:


1) We need to add a For loop that iterates for the specified number of iterations.
2) We need to create an initial random solution of size n.
3) We need to evaluate the fitness of our current solution within the loop.
4) We need to copy the current solution (say oldsol).
5) We make a small change to the current solution and evaluate the fitness to another variable.
6) If the new fitness is worse than the old, we copy oldsol back to being our current solution.
7) After the For loop has completed we return the current solution.


I cannot do this one at all so i was hoping that someone could point me in the right direction? I'm really worried about doing this since i've become really stuck.

I would greatly appreciate anyones help on this. I've tried do this for a few days now and i've hit a brick wall so i was hoping that i could get some help.

Thanks in advance.

String Functions

the above link can help you