One intuition that helps is to see evolution as a random search through solution space. Another thing to realize is that -in evolutionary algorithms- the distribution of random trials will be strongly biased around existing solutions.
It helps to understand that in some situations, a search algorithm with some level of randomness can arrive at a solution faster than a systematic/random approach, on average. In other situations, a search with added randomization might be slower, but its ability to escape local optimae (to some degree) means that it is much more likely to find the global optimum (or at least a better local optimum :-P ).
Interesting points. But I would add that sexual selection can select for some trait that is actually counterproductive, a famous example being peacock tails. Female peacocks use them to evaluate the health of potential partners, so it is an indirect measure of fitness to the environment. But at the same time, it is clear that healthy peacocks would still be better off without carrying around such big tails. If tails weren't so important for reproduction, they would have likely shrunk by now. I wonder how a comparison with the methods you mentioned would capture this.
It helps to understand that in some situations, a search algorithm with some level of randomness can arrive at a solution faster than a systematic/random approach, on average. In other situations, a search with added randomization might be slower, but its ability to escape local optimae (to some degree) means that it is much more likely to find the global optimum (or at least a better local optimum :-P ).
Compare also: Monte-Carlo methods.
https://en.wikipedia.org/wiki/Evolutionary_algorithm