Mas aí eu caio em outra dependência de aleatoriedade.

Olá Franco, tudo bem? Espero que sim!

Desculpe pela demora em retornar.

Não há um valor otimizado para a escolha do número de iterações. Tudo vai depender da quantidade de combinações possíveis e quanto tempo está disposto/disponível para rodar o algoritmo. O método randomizado nem sempre trará o melhor resultado possível, visto que ele não passa por todas as situações disponíveis. Mas ele é utilizado justamente para conseguir abarcar uma variedade de combinações e não demandar tanto tempo quanto a exploração total com o gridsearch.

Trata-se de um trade off, você irá perder no aspecto de não encontrar o melhor resultado ou talvez não saber que alcançou o melhor dos resultados, em troca de um ganho de tempo e esforço computacional.

O algoritmo muitas vezes não precisa e não tem que ser o melhor possível, ele precisa resolver o problema e em um tempo hábil para que seja útil de alguma forma. Não adianta ele ser o melhor possível e demorar uma quantidade de tempo que se torna inutilizado.

Espero que tenha tirado sua dúvida.

Estou à disposição. Bons estudos!