{"id":23164,"date":"2023-03-06T09:30:50","date_gmt":"2023-03-06T09:30:50","guid":{"rendered":"https:\/\/www.booksofall.com\/cn\/?post_type=product&p=23164"},"modified":"2023-03-06T09:30:51","modified_gmt":"2023-03-06T09:30:51","slug":"essentials-of-metaheuristics","status":"publish","type":"product","link":"https:\/\/www.booksofall.com\/cn\/essentials-of-metaheuristics\/","title":{"rendered":"Essentials of Metaheuristics"},"content":{"rendered":"

0.1 What is a Metaheuristic?<\/h3>\n

Metaheuristics<\/a> is a rather unfortunate1 term often used to describe a major subfield, indeed the primary subfield, of\u00a0stochastic optimization<\/b><\/a>. Stochastic optimization is the general class of algorithms and techniques which employ some degree of randomness to find optimal (or as optimal as possible) solutions to hard problems. Metaheuristics are the most general of these kinds of algorithms, and are applied to a very wide range of problems.<\/p>\n

What kinds of problems? In Jacobellis v. Ohio<\/a> (1964, regarding obscenity), the United States Supreme Court Justice<\/a> Potter Stewart<\/a> famously wrote,<\/p>\n

I shall not today attempt further to define the kinds of material I understand to be embraced within that shorthand description; and perhaps I could never succeed in intelligibly doing so.\u00a0But I know it when I see it<\/b>, and the motion picture involved in this case is not that.<\/p>\n

Metaheuristics are applied to I know it when I see it problems. They\u2019re algorithms used to find answers to problems when you have very little to help you: you don\u2019t know beforehand what the optimal solution looks like, you don\u2019t know how to go about finding it in a principled way, you have very little heuristic information to go on, and brute-force search is out of the question because the space is too large. But if you\u2019re given a candidate solution to your problem, you can test it and assess how good it is. That is, you know a good one when you see it.<\/p>\n

For example: imagine if you\u2019re trying to find an optimal set of robot behaviors for a soccer goalie robot. You have a simulator for the robot and can test any given robot behavior set and assign it a quality (you know a good one when you see it). And you\u2019ve come up with a definition for what robot behavior sets look like in general. But you have no idea what the optimal behavior set is, nor even how to go about finding it.<\/p>\n

The simplest thing you could do in this situation is\u00a0Random Search<\/b><\/a>: just try random behavior sets as long as you have time, and return the best one you discovered. But before you give up and start doing random search, consider the following alternative, known as\u00a0Hill-Climbing<\/b>. Start with a random behavior set. Then make a small, random modification to it and try the new version. If the new version is better, throw the old one away. Else throw the new version away. Now make another small, random modification to your current version (which ever one you didn\u2019t throw away). If this newest version is better, throw away your current version, else throw away the newest version. Repeat as long as you can.<\/p>\n

Hill-climbing is a simple metaheuristic algorithm. It exploits a heuristic belief about your space of candidate solutions which is usually true for many problems: that similar solutions tend to behave similarly (and tend to have similar quality), so small modifications will generally result in small, well-behaved changes in quality, allowing us to \u201cclimb the hill\u201d of quality up to good solutions. This heuristic belief is one of the\u00a0central defining features of metaheuristics<\/b>: indeed, nearly all metaheuristics are essentially elaborate combinations of hill-climbing and random search.<\/p>\n

The \u201cI know it when I see it\u201d problems tackled by metaheuristics are a subclass of\u00a0inverse problems<\/b>. An inverse problem is one in which you have a test function f which takes a candidate solution and produces an assessment of it, but in which it\u2019s difficult or impossible to construct the inverse function f\u22121 which takes an assessment and returns a candidate solution which would have had that assessment.2 In our example, our robot simulator and test procedure is f . But what we really want is an inverse function f\u22121 which takes an assessment and returns a robot behavior set. That way, if we were lucky, we could plug in the optimal assessment value into f\u22121 and get the optimal robot behavior set.<\/p>\n

Optimization<\/a> methods (such as metheuristics) are designed to overcome inverse problems. But many classic optimization techniques, such as\u00a0Gradient Ascent\u00a0<\/b>(Algorithm 1) make strong assumptions about the nature of f : for example, that we also know its first derivative f \u2032. Metaheuristics make far weaker assumptions, and sometimes make none at all. This means that metaheuristics are very general, but also means that they\u2019re often best thought of as last-ditch methods, used when no other known technique works. As it so happens, that\u2019s the case for an enormous, important, and growing collection of problems.<\/p>\n","protected":false},"excerpt":{"rendered":"