
22nd December 2015, 02:51
#1
Hill climbing inventors
Hi,
looking for clues to whom invented hillclimbing. searching for papers (as early years as possible) that explains hillclimbing.
I think I allready understand the technique since someone explained it to me. But i still like to find out about the history and who the author is.
I know there are different types of hillclimb, but is there someone who invented the first one?
I would like to find out.


22nd December 2015, 07:38
#2

Thanks (2):
biject.bwts (22nd December 2015),Rudi (22nd December 2015)

22nd December 2015, 23:17
#3
ayaya looks decent. thanks alot!


23rd December 2015, 00:47
#4
Unless you're talking about some narrow definition used in some particular field, I'd think hillclimbing is as old as the hills. (Or people thinking in terms of hills.) It's about the most obvious search procedure there isiteratively do whatever seems to improve your situation most. In AI terms, it's the most obvious and weakest of "weak methods" that anybody'd think to actually use for heuristic search.
"Hill climbing" is also known as "gradient descent." The former term is based on the idea that up is betteryou're trying to maximize something you like by always going up as fast as possible, locally. The latter is based on the idea that *down* is better, as in energy minimization, or water flowing downhill; you're following the path of least (local) resistance to get to a desirable (hopefully global) minimum. And you get "gradient ascent" when you think of maximization instead. If I recall correctly, this is wellknown to have been reinvented independently at least a few times in several fields and given different names.
Note that the 1962 paper linked above is specifically about quadratic hill climbing. And it refers to a 1955 paper on "gradient methods".
But I think that the ancient Greek mathematicians used explicit hillclimbing approximation methods, which only worked reliably for simple problems where the local maximum is clearly the global maximum. (Think of searching for a square root, for example.) I'd guess that problems with hillclimbing methods were part of Leibniz' and Newton's motivations for inventing calculus ("the calculus of infinitesimals"), and those problems had been wellknown for millennia, by some names or others.
You might be able to trace back to where the modern *term* "hill climbing" was coined, but I suspect the idea is prehistoric or at least predates any surviving mathematical history.

Thanks:
Rudi (23rd December 2015)

23rd December 2015, 01:18
#5
Now that I think about it, I might not be surprised at all if the idea of hillclimbing was literally prehistoric, i.e., predates the invention of general writing. (Which also seems to have evolved in several places.)
Accounting is older than general writing, and the idea of trying to maximize profit in the most obvious way seems pretty obvious.
And puzzles and gameplaying are even older than that, IIRC. Maybe a lot of people had the idea of doing whatever improved your situation the most at each turn, and some of them talked about it explicitly before anyone anywhere knew how to write.


23rd December 2015, 18:53
#6
Well, my interest in this has to do with finding correct algorithms for doing exact computations of problemsolvers. So probably its the global maximum/minimum in those cases that are of interest using hillclimb methods. Im doing research before i attempt at some simple problem solving.
I am more interested in lossless compression than lossy because it seems to me that there are many more lossymethods out there. I loose interest very fast if there are too many methods to learn and too much information to read about. I learn best by simple but powerful (if one can say that) algorithms. Some simple boolean/logicoperators are universal (and also combinations of them). So the idea is to use Hillclimb methods to find exact formulas for computing solutions to problems (if possible).
Kmaps are ideal to optimize logic operators into fewer (and in the early days cheaper) logicgates. In compression this may be an ideal approach as well. Im sure people have done similar things before. I just think that compressionalgorithms and data are the same thing, atleast in computers where bits and bytes can be instructions (they are just opcodes/numbers and also they may be viewed as data as well, since the data or opcodes just represent numbers in memory or otherwise).
Too continue on that, if compression algorithms/methods can be compressed using fewer instructions (logic operators etc) and one mixes the data with the algorithm it will overall produce smaller data  atleast in an ideal kmap method. The problem is to go back from the optimized kmap operators back to the original data. But the point here is not that one looses the original operators, the point is that the logicformulas produce the same result as the nonoptimized formula. When one produces the same results, one has in a formula to produce/generate or whatever numbers that recreates the original data(numbers, bits or whatever) using an optimized (in this case a kmap method) formula that is smaller than the original.
The point where the hillclimb method(s) come into this, is where it potentially finds solutions of the function that was used to try recreate the data (whatever that may be).
There are prolly other methods out there, but I found hillclimb an interesting one to try out first.
Last edited by Rudi; 23rd December 2015 at 18:59.

Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules