HW5 - MaxWalkSat

[aisobran]

Initialized the code using code4. I think it's a good framework to use. Added the Oszyczka2 model. Need to adapt base_runner and below by adding constraints.

[meneal]

Just to try to frame out how this should go.

For the baseline:

• produce a master random number: x
• use x to produce the six Xn values by mapping the random number to the ranges for each value. Use the same method to produce Xn values within the actual program.
• Then run the model 1000 times to produce the range of Oszyczka f1 and f2
• Use those values to produce normalization functions for f1 and f2

For the actual program:

• Change neighbor to mutate, remove the temperature parameter
• Determine within the new mutate function whether retry is necessary (if Xn values are out of range)
• Remove everything temperature related.
• Create a separate step function that operates on some sort of state data (vector, whatever)
• Replace k < kmax in the while loop with step number and max number of steps.
• peg probability to .5 in elif
• Everything energy related stays the same.

This is just a start, but I wanted to check in with you all and see if that's what you both see on this before I really get to chopping wood here.

[aisobran]

How would you map a single random to all six values? This would probably produce a correlation among all 6 values which would bound our solution space.

[ghost]

I agree with @aisobran in that we should generate six separate random values within the ranges allowed. Everything else looks okay.

[aisobran]

Added the jump all around functionality.

[ghost]

Is there a reason why there is a GLOBAL_BOUND_MAX set to 100,000? Running MWS gave an energy around 1, but then I changed the bounds for each of the variables to match what was in the Osyczka2 spec and I got an energy of around 1.22. What am I missing?

[meneal]

So I just noticed something in here. Looked at the bounds:

GLOBAL_BOUND_MAX = 100000
x1bound = bounds(0 , GLOBAL_BOUND_MAX)
x2bound = bounds(-GLOBAL_BOUND_MAX, 10)
x3bound = bounds(1, GLOBAL_BOUND_MAX)
x4bound = bounds(0, 6)
x5bound = bounds(-GLOBAL_BOUND_MAX, 5)
x6bound = bounds(0, 10)

Are incorrect per the block here.

I think these are the correct variable bounds:

x1bound = bounds(0, 10)
x2bound = bounds(0, 10)
x3bound = bounds(1, 5)
x4bound = bounds(0, 6)
x5bound = bounds(1, 5)
x6bound = bounds(0, 10) 

The original bounds in the comment block make it look like there is no lower or upper bound on a few of the variables, but that isn't right.

[ghost]

Ok, I see. I fixed the bounds. I ran the model again and got an energy of about 1.4, which is pretty close to sqrt(2).

[meneal]

Yep. I just fixed it on my end. and got around that too. Seems like it sped the whole thing up exponentially too. I guess it was just that the big numbers in there were causing larger mathematical operations? I guess that makes sense though. In both f1 and f2 we would've been squaring already big numbers and then adding them together...

On Fri, Sep 25, 2015 at 4:03 PM, Joseph Sankar notifications@github.com wrote:

Ok, I see. I fixed the bounds. I ran the model again and got an energy of about 1.4, which is pretty close to sqrt(2).

— Reply to this email directly or view it on GitHub https://github.com/LambdaConglomerate/x9115lam/issues/11#issuecomment-143338523 .

[aisobran]

Yeah I thought the the comma separated the variables from each other in the pdf. This makes more sense.

[meneal]

So seems like we've covered part of this then.

FOR i = 1 to max-tries DO
  solution = random assignment
  FOR j =1 to max-changes DO
    IF  score(solution) > threshold
        THEN  RETURN solution
    FI
    c = random part of solution 
    IF    p < random()
    THEN  change a random setting in c
    ELSE  change setting in c that maximizes score(solution) 
    FI
RETURN failure, best solution found

In the block above it looks like he means for us to be able to independently manipulate parts of the solution. He says c=random part of solution and then change random setting in c. There are bunches of ways to go about this part of it.

Also the else block where we change a setting in c the maximizes score is probably best done in a similar way to the way that we previously did the neighbor function.

I'll poke around at that stuff. See if I can make something out of it and then just make a post with what I actually did.

[ghost]

I think Menzies mentioned to choose something like a third of the values to mutate? I don't think he recommends mutating every part like in SA.

For maximizing the score he recommended stepping through the values for the variable under mutation with (max - min)/steps with steps = 10, meaning we will try 10 values no matter the bounds of the variable.

[meneal]

Yeah that makes sense. I figured I'd poke maybe 2 of the variables at a time since they have those dependencies. So that "How" line you're talking about, the way I interpret that is that when we jump into our step function we pick a variable or two variables, or whatever. The way I'm reading that line is that we have that function equal epsilon in our mutation for the following, given we're talking about x1:

epsilon = (10 - 0) / 10 = 1

So then for our mutation of x1 we add 1. But as you say it's 10 steps for that variable. What I'm thinking of doing is randomly selecting a set of those paired variables and then adding or subtracting that epsilon value, and then picking another set on the following step until we're out of steps.

[meneal]

Alternatively we could just mutate the same set of vars each time for a set number of steps, and then switch to another set, and bounce around like that for awhile.

[ghost]

From what I understand, the point of stepping through the variable is to find the value(s) that maximize distance from hell. Half the time, we can mutate one step value in either direction, like you said. But for the other half, I think we're supposed to iterate through the values of whatever variables we decide to mutate and pick the best values. I'm not sure if we should mutate the same variables each time though.

[aisobran]

In the step function we only pick one variable to mutate.

"Then, at probability (1-p), fixate on one variable and try all its values in (say) increments of (max-min)/10 (and use the value that most improves the score function)."

also:

"Sometimes, sitting still while rolling marbles left and right"

This would indicate only one variable at a time. If we mutated more we would be moving in more directions.

Where do you guys see part about stepping and mutating multiple value at once.

[aisobran]

The point of stepping is to find the local environment around the point we are currently in, trying to figure out if we are in a local maxima, local minima. We do not pick the same variables each time either.

[meneal]

I think that may have been mentioned in class, but manipulating one variable is easier anyway.

[aisobran]

If you look in the notes I posted (I think you guys weren't there):

"MaxWalkSat -> sometimes focus on just one dimension"

[meneal]

Gotcha so then we essentially have that inner for loop with j =1 where if p<random() we randomly select a variable and manipulate it up or down randomly by some set amount.

And else change setting in c that maximizes score(solution) we jump into a step function where we start at the minimum or maximum value of a randomly selected variable and step up or down through the entire range, at each step testing energy and then return the best of those steps.

Does that sound right?

[ghost]

Ok, that makes sense @aisobran. It's hard to make the distinction because we only had one variable to mutate in SA anyways. So in SA we would mutate all the variables, while in MaxWalkSat we only mutate one, correct?

@meneal that sounds right.

[aisobran]

In MaxWalkSat we mutate all with probability p, and mutate 1 step-wise with probability 1-p

[aisobran]

I pushed up an implementation of the step function. To keep everything tidy I'm using lists for the bounds and constraints.

I'm getting numbers greater than sqrt(2) though so I need to double check the index references but it may be the that base_runner doesn't cover enough area. Check it out to see if you can see whats up.

[aisobran]

Every time I run it the vectors are all in bounds and the step function is working as advertised. I think the problem may be that we should do sqrt(6) because we have 6 dimensions.

[meneal]

I've been poking around at the maxWalkSat function overall and I'm working on my own version of mutate so I haven't really had time yet to look at your code. I'll play around with it some more.

The emax value shouldn't be changed though. Energy for this case is only dealing with f1 and f2. It doesn't care how many dimensions we have only those two values, So emax is still sqrt(2).

On Fri, Sep 25, 2015 at 5:53 PM, Alexander Sobran notifications@github.com wrote:

Every time I run it the vectors are all in bounds and the step function is working as advertised. I think the problem may be that we should do sqrt(6) because we have 6 dimensions.

— Reply to this email directly or view it on GitHub https://github.com/LambdaConglomerate/x9115lam/issues/11#issuecomment-143362551 .

[aisobran]

your right

[ghost]

I'm a little confused about what happens with probability p. The notes say to "change a random setting in c" (p) or "change setting in c that maximizes score(solution) " (1-p). It makes more sense to mutate all variables in c with probability p, like SA, so I'm not sure why we would want to mutate only one in that case.

[meneal]

P doesn't really matter for this thing honestly. We're just doing one thing 50% of the time and doing another thing 50% of the time.

[aisobran]

that's what I chose

[aisobran]

The "change setting in c that maximizes score(solution) " is saying roll your marble left and right and pick the best energy.

[ghost]

But what about "change a random setting in c"? Are we suppose to mutate all variables in c or one (or somewhere in between)?

[aisobran]

"Jump all around the hills" Here we can do the 1/3 mutations if you wanted.

[ghost]

I think we should experiment with how many variables we mutate to see if we can reduce the time it takes to get an optimal solution.

[aisobran]

It doesn't take long if we mutate all.

[ghost]

In order to get a distance larger than sqrt(2), we must be getting negative values for f1 and f2 normalized. Does that mean our min and max values are off somehow?

[aisobran]

I figured it out the issue it's breaking out of constraints. Fix incoming

[meneal]

So looking at what's going on in there the one thing I'd say is that when we get to the overhaul of the main max walk sat function we need to be able to reset to a completely new random solution. But if we reset to a completely new random solution at that point, why would we generate a completely random solution within 1 try. It seems better to select a variable at random in the vector and tweak that value instead basically starting over again.

Take a look at what I pushed to the matt branch. It's not working right now, but just to give you an idea of what I'm looking at doing beyond the step function.

On Fri, Sep 25, 2015 at 6:27 PM, Alexander Sobran notifications@github.com wrote:

I figured it out the issue it's breaking out of constraints. Fix incoming

— Reply to this email directly or view it on GitHub https://github.com/LambdaConglomerate/x9115lam/issues/11#issuecomment-143367504 .

[meneal]

Fixed some stuff. Getting output now.

On Fri, Sep 25, 2015 at 6:39 PM, Matthew Neal meneal@gmail.com wrote:

So looking at what's going on in there the one thing I'd say is that when we get to the overhaul of the main max walk sat function we need to be able to reset to a completely new random solution. But if we reset to a completely new random solution at that point, why would we generate a completely random solution within 1 try. It seems better to select a variable at random in the vector and tweak that value instead basically starting over again.

Take a look at what I pushed to the matt branch. It's not working right now, but just to give you an idea of what I'm looking at doing beyond the step function.

On Fri, Sep 25, 2015 at 6:27 PM, Alexander Sobran < notifications@github.com> wrote:

I figured it out the issue it's breaking out of constraints. Fix incoming

— Reply to this email directly or view it on GitHub https://github.com/LambdaConglomerate/x9115lam/issues/11#issuecomment-143367504 .

[aisobran]

My issue was from list copying, so it works now.

[aisobran]

I'll check yours out

[meneal]

Sorry dude. I actually have to go. I'll look back at this in the morning.

There's something wrong with mine. Not sure exactly what it is. Something isn't quite right in the normalization function. But there are probably a bunch of other messed up things in there too.

[aisobran]

Right away I can tell your solutions are not within the constraints, getting x1 = 10, x2 = 10. This messes things up because base_runner is within constraints.

[aisobran]

Your also going out of bounds, tweak should be implemented with some type of mod. You can use the same implementation I used in the neighbor function of SA.

[aisobran]

Just cleaned up my code and commented. I think it's good to go.

If you want to implement one random mutation instead of full random mutation for the jump around part you can uncomment (line 207-209):

c = int(math.floor(6 * random.random()))
sn[c] = xbounds[c](random.random())
while not constraintsStack[int(math.floor(c/2))](sn[int(math.floor(c/2) * 2)], sn[int(math.floor(c/2) * 2) + 1]): sn[c] = xbounds[c](random.random())

and on line 203 comment out:

sn = generateValidValues()

And if you wanted to iterate those put a for loop outside of the if statement on line 201

[meneal]

So, what aisobran did up to this point was great. I took that code and merged some of my own ideas with it in the matt branch. Basically I'm doing as follows:

generate a random vector
for x number of tries:
  for y number of changes:
    pick a variable from (x1, ... , x6) randomly
    either randomly change that variable 
    or run through its range testing energy
  print the best of that set of y changes
  if it is the best for all of the tries set it to sbo
  get rid of everything done in that set of y changes and regen a random vector

I made a few changes to the way that stepping was done just to make it easier to read, but kept the spirit of it. Basically I made a few more functions since everything was getting a little messy.

I think it's really working well at this point and it's doing what it's supposed to, ocassionally it will hit the sqrt(2) max, but it's hitting close to it on every run with 100 tries and 1000 changes per try. In the output EBO is the best energy overall and SBO is the best vector overall.

[aisobran]

It looks awesome. I approve submission.

[meneal]

Cool. Should I rebase into master then?

On Sat, Sep 26, 2015 at 1:55 PM, Alexander Sobran notifications@github.com wrote:

It looks awesome. I approve submission.

— Reply to this email directly or view it on GitHub https://github.com/LambdaConglomerate/x9115lam/issues/11#issuecomment-143475709 .

[aisobran]

Definitely not. Rebasing is destructive and since we're working in a collaboration I'd rather not lose the history of the work.

I'd rather you branch off what I've currently done if you used the code in it.

[meneal]

I guess I could just merge it? I don't think it makes sense to make a whole different branch off of what you've done so far. I'm already working in a branch from yesterday.

I just hate merging. Seems like something always gets messed up. I totally see what you're getting at though.

On Sat, Sep 26, 2015 at 2:03 PM, Alexander Sobran notifications@github.com wrote:

Definitely not. Rebasing is destructive and since we're working in a collaboration I'd rather not lose the history of the work.

I'd rather you branch off what I've currently done if you used the code in it.

— Reply to this email directly or view it on GitHub https://github.com/LambdaConglomerate/x9115lam/issues/11#issuecomment-143476553 .

[aisobran]

I'm good with a merge.

[ghost]

I'm fine with merging too.