Introduction to Metaheuristics (6/9). Random search

[@suhailasaidat174]

Thank you...good explanation.

[@qianyingliao1675]

Thank you for the clear explaination!

[@MatheusSilva-bq3ff]

Great explanation!

[@sebon11]

Another clear explanation - comment for stats :D

[@LuisRIzquierdo]

... and much appreciated! :D

[@sebon11]

@@LuisRIzquierdo :)

[@EmilioGarcia_]

Great lecture, thanks for sharing it. Quick question, in the IF loop when comparing “Best” and “S” what does Quality measure? I thought about it as a route for routing problem, then I pick one route randomly and set it as “Best” and then another route as “S”, then the Quality I see it as the most economical one (if we look for the route with the min cost) Am I right with this interpretation of Quality(*)? Thanks for your feedback!

[@LuisRIzquierdo]

Indeed. Quality measures how good a candidate solution is. The better the solution, the higher the quality. Thus, in your problem, the lower the cost of the route, the greater its quality. In any case, you can interpret the piece of code "If Quality(S) > Quality(Best)" simply as "If S is better than Best". Thus, in your routing problem, you can replace that piece of code with "If Cost(S) < Cost(Best)" (note I replaced > with

[@hanserj169]

Thanks for the content. I have a question: if the candidate solution set is known, why not to exclude a candidate from the solution set every time we notice that it is not better than the current best solution? In that way we eliminate the possibility of choosing the same inefficient solution.

[@LuisRIzquierdo]

Great question, Hanser! The algorithm you propose would tend to give better solutions after any given number of iterations, and it would guarantee reaching the optimum if the number of iterations equals the number of candidate solutions. What you propose is often called “sampling without replacement”. The only drawback is that the algorithm you propose would need to keep a list of the candidate solutions already visited (or, alternatively, the unvisited candidate solutions). This requires memory. The use of memory is often a factor to consider when you design an algorithm, and there is often a tradeoff between this factor and other criteria such as efficiency. Great question, keep it up!

[@hanserj169]

@@LuisRIzquierdo thanks for the answer. It makes sense totally. Very interesting!