Algoritmo de búsqueda aleatoria (Random Search) en C++- Explicación, ejemplo y código

El algoritmo de búsqueda aleatoria es un método de búsqueda basado en seleccionar aleatoriamente un conjunto de soluciones del espacio de búsqueda y verificar si pueden resolver el problema. Este enfoque se usa a menudo cuando no hay información o estrategia específica para guiar la búsqueda.

Cómo funciona

1. Inicialización: comience con un conjunto de soluciones iniciales generado aleatoriamente.
2. Evaluación: Evaluar la calidad de cada solución en base a la función objetivo o criterio de evaluación.
3. Selección: seleccione un subconjunto de las mejores soluciones del conjunto en función de las probabilidades o la selección aleatoria.
4. Pruebas: probar si las soluciones seleccionadas son capaces de resolver el problema.
5. Repetir: iterar a través de los pasos 2 a 4 hasta que se logre un resultado satisfactorio o se alcance un número predefinido de iteraciones.

Ejemplo: optimización de la Fibonacci función

Considere el problema de optimización de la Fibonacci función F(x) = F(x-1) + F(x-2) con F(0) = 0, F(1) = 1. Queremos encontrar el valor de x para el cual F(x) se maximiza. El método de búsqueda aleatoria puede seleccionar aleatoriamente valores de x, calcular el Fibonacci valor en cada x y elegir el valor de x correspondiente al Fibonacci valor más alto obtenido.

Ejemplo de código en C++

#include <iostream>  
#include <cstdlib>  
#include <ctime>  
  
int fibonacci(int n) {  
    if(n <= 0) return 0;  
    if(n == 1) return 1;  
    return fibonacci(n- 1) + fibonacci(n- 2);  
}  
  
int randomSearchFibonacci(int maxIterations) {  
    int bestX = 0;  
    int bestValue = 0;  
  
    srand(time(0));  
  
    for(int i = 0; i < maxIterations; ++i) {  
        int x = rand() % maxIterations;  
        int value = fibonacci(x);  
        if(value > bestValue) {  
            bestValue = value;  
            bestX = x;  
        }  
    }  
  
    return bestX;  
}  
  
int main() {  
    int maxIterations = 20;  
    int result = randomSearchFibonacci(maxIterations);  
  
    std::cout << "Optimal x for maximum Fibonacci value: " << result << std::endl;  
  
    return 0;  
}  

En este ejemplo, usamos el método de búsqueda aleatoria para optimizar la Fibonacci función. Seleccionamos aleatoriamente valores de x, calculamos el Fibonacci valor en cada x y luego elegimos el valor de x correspondiente al Fibonacci valor más alto que hemos calculado.