I was trying to explain the sorts of algorithms I use at work to a friend the other night. In general, they're called metaheuristics (in particular, I have experience with simulated annealing and genetic algorithms.) I used an analogy of an ordinary heuristic like one that tries to find the shortest path between to points.
Shortest path: Imagine you want to find X marks the spot on a map. However, there are all these barriers in the way and you can't really be sure if the route you're taking will 1) get you there; or 2) get you there with the least steps. However, so long as there is someone/something telling you how far away you are from the X, you should always be able to find the shortest route - if there is one. That's A*.
To describe when to use a metaheuristic, however, I said "well, imagine you don't actually know where X marks the spot is." But it's much worse than that. Imagine you don't really know where it is and no matter which direction you take you don't necessarily or reliably get any closer to X. For example, you start a long way from X; you go ten metres north and you're close; then go twenty metres south and you're just as close. But, actually, the closest you could ever get to X might be five metres east from the start! It just doesn't make any sense. Like someone calling out "hotter" or "colder" seemingly at random when you're trying to find something. They aren't lying to you, it's just really hard to find. If you have a situation like that, use a metaheuristic, or punch them.