TSP - Simple hill climb algorithm?

[FancyThat]

SEE POST 4

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 AGESSS! 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?

At the end of the day its just converting psuedo into Java but i have not been working with Java for a long while and i feel that joining this forum will help me get back into it as well as answering this problem at the same time.

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

SEE POST 4

[servlet]

Instead of asking to write the whole program for you. If you try to do it your self and come back with the difficulties you encounter, you chance of getting answers are better.

[FancyThat]

I'm not asking for the answer, just a point in the right direction, i've genuinely hit a brick wall. I've tried what i can but it clearly is not good enough. Sorry if it comes out as if i'm looking for the answer.

I won't learn anything that way so it's pointless just getting an answer.

The thing is i understand exactly what it's asking me to do but i just can't do it..

This bit of code that i did actually uses the SmallChange class that i'm trying to build.

public static void main(String args[])
	{
		ScalesSolution s = new ScalesSolution("11111");
		s.println();
		s.SmallChange();
		s.println();
	}

As you can see it will print 111111 and then the SmallChange class gets called and should change a random number from 1 to 0, and if i change the "111111" to "000000" it should change a random one of those to a 1.

[FancyThat]

Won't start a new thread but hopefully i can get some answers. I've had some help from a friend for the first bit of pseudo code i posted and nearly finished that but im still struggling with this one:

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.

The reason for this is because i don't know what the code is asking me to do. I know for some bits but it would be really helpful if you guys could indicate to me what each step is asking me to do. That way it's up to me to go and do the research and implement it myself.

I realised that when doing the first psuedo code i only needed someone to tell me what its asking me to do and then i did it myself. For example steps 2 and 3 on this one; what function/method should i be using for that? I really just need to know what methods need to be implemented and then i'll go off do the research and hopefully learn something by doing so.

[Fou-Lu]

#2 can be done with java.lang.Math.random method, or java.util.Random class. #3 can be done with whatever method you write to deal with the fitness.