Results 1 to 6 of 6

Thread: Hill climbing inventors

  1. #1
    Member
    Join Date
    Apr 2015
    Location
    Norway
    Posts
    16
    Thanks
    5
    Thanked 2 Times in 2 Posts

    Hill climbing inventors

    Hi,

    looking for clues to whom invented hill-climbing. searching for papers (as early years as possible) that explains hill-climbing.
    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 hill-climb, but is there someone who invented the first one?

    I would like to find out.

  2. #2
    Member
    Join Date
    Oct 2010
    Location
    New York
    Posts
    21
    Thanks
    9
    Thanked 2 Times in 1 Post

  3. Thanks (2):

    biject.bwts (22nd December 2015),Rudi (22nd December 2015)

  4. #3
    Member
    Join Date
    Apr 2015
    Location
    Norway
    Posts
    16
    Thanks
    5
    Thanked 2 Times in 2 Posts
    ayaya looks decent. thanks alot!

  5. #4
    Member
    Join Date
    Oct 2013
    Location
    Filling a much-needed gap in the literature
    Posts
    350
    Thanks
    177
    Thanked 49 Times in 35 Posts
    Unless you're talking about some narrow definition used in some particular field, I'd think hill-climbing is as old as the hills. (Or people thinking in terms of hills.) It's about the most obvious search procedure there is---iteratively 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 better---you'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 well-known to have been re-invented 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 hill-climbing 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 hill-climbing methods were part of Leibniz' and Newton's motivations for inventing calculus ("the calculus of infinitesimals"), and those problems had been well-known 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.

  6. Thanks:

    Rudi (23rd December 2015)

  7. #5
    Member
    Join Date
    Oct 2013
    Location
    Filling a much-needed gap in the literature
    Posts
    350
    Thanks
    177
    Thanked 49 Times in 35 Posts
    Now that I think about it, I might not be surprised at all if the idea of hill-climbing 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 game-playing 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.

  8. #6
    Member
    Join Date
    Apr 2015
    Location
    Norway
    Posts
    16
    Thanks
    5
    Thanked 2 Times in 2 Posts
    Well, my interest in this has to do with finding correct algorithms for doing exact computations of problem-solvers. So probably its the global maximum/minimum in those cases that are of interest using hill-climb 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 lossy-methods 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/logic-operators are universal (and also combinations of them). So the idea is to use Hill-climb methods to find exact formulas for computing solutions to problems (if possible).

    K-maps are ideal to optimize logic operators into fewer (and in the early days cheaper) logic-gates. In compression this may be an ideal approach as well. Im sure people have done similar things before. I just think that compression-algorithms 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 k-map method. The problem is to go back from the optimized k-map operators back to the original data. But the point here is not that one looses the original operators, the point is that the logic-formulas produce the same result as the non-optimized 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 k-map method) formula that is smaller than the original.

    The point where the hill-climb 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 hill-climb 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
  •