Chance of Stochastic Hill Climbing find a decent answer

[dougy83]

Hi all,

I have a question regarding the ability of the SHC algorithm to find a decent answer.

Basically, the algorithm I'm referring to - **broken link removed** - chooses a set of 8 items out of a reserve bag of 48 possible items then proceeds to perform a number of random mutations/tweaks on this set. Each tweak swaps out 1 (randomly chosen) of the 8 items with any (randomly chosen) of the remaining items in the reserve bag.

After each tweak the suitability of the new set is checked, and if better than the last set, may be kept for the next generation of mutations. If it is worse, then the previously best set will be used again for the next gen of mutations.

Their pseudo-code for this process is shown in the attached image, duplicated from their paper.

Eight items must be chosen out of a bag of 48; the algorithm attempts to find the best combination (of 377,348,994 possible) using a total of 1800 guesses (30 rounds of 60 mutations). Some of the items complement each other, others are just duplicates and others might be mainly noise.

How likely is it that this method gets a good result given the massive search space and the small query size? I think I must be coming from the wrong angle.

 

[dougy83]

Any input fellas? Is this question too far out of the realm of interesting?

 

[jpanhalt]

When I first read your post, I thought, hey, that's how I do Assembly programming.

In reality, I was not actually aware of that term, but it seemed an ample description of how our immune system works. Sure enough, that is the case.

http://www.cell.com/biophysj/retrieve/pii/S0006349506722627

There are lots of articles on it. How well it works? Well, I haven't gotten sick this Winter, yet.

As for your question per se, I am sure there are members here who have knowledge of that method's performance. There are certainly scholarly articles on it to be found in Google. Perhaps, if your question were phrased differently and more specifically, some of the AI experts will comment.

John