Optimización: fuerza bruta frente a muestreo aleatorio

En este artículo vamos a ilustrar la debilidad del método de optimización por fuerza bruta cuando el número de variables es muy alto y la alternativa de probar en valores aleatorios, lo que llamaremos optimización por muestreo aleatorio.

El siguiente programa compara los dos métodos cuando se optimiza una función de 5 variables. Al ejecutar el programa vemos que el método de fuerza bruta encuentra un mejor candidato pero también a un mayor coste en tiempo. Cuando el número de variables crece, el tiempo que tarda el método de fuerza bruta lo hace inservible.

% Optimizar una función que depende de muchas variables
% Definimos la función
f=@(a) a(1)+3*a(2)^2-a(3)*a(4)-5+a(1)*(a(5)-2*a(3));
% Primero la optimizamos por fuerza bruta
tic;   % ponemos el cronómetro  
a1=-1:0.1:1;   % intervalo de parámetros para cada variable
a2=a1; a3=a1; a4=a1; a5=a1; a6=a1; a7=a1;
l=length(a1);  % longitud de cada parámetro
m=10000;       % guardamos en m el valor más bajo de la función
for i1=1:l
    for i2=1:l 
        for i3=1:l 
            for i4=1:l
                for i5=1:l
                    coste=f([a1(i1),a2(i2),a3(i3),a4(i4),a5(i5)]);
                    if coste<m  % en este caso mejoramos
                       m=coste; % nos quedamos con este valor
                       % ahora guardamos los parámetros donde se alcanza el
                       % óptimo
                       b=[a1(i1),a2(i2),a3(i3),a4(i4),a5(i5)];
                    end
                end
            end
        end
    end
end
time=toc; % paramos el cronómetro
sprintf('La fuerza bruta encuentra el valor mínimo %d en %d segundos',m,time);
tic;       % ponemos de nuevo el cronómetro
% metodo 2: Muestreo aleatorio
% Elegimos 10000 valores aleatorios de los parámetros (entre -1 y 1)
bb=rand(10000,5)*2-1; 
mm=10000;      % guardamos en m el valor más bajo de la función
for i=1:length(bb)
    coste=f(bb(i,:));
    if coste<mm   % en este caso mejoramos
        mm=coste; % nos quedamos con este valor
        % ahora guardamos los parámetros donde se alcanza el
        % óptimo
        val=bb(i,:);
    end
end
time=toc; % paramos el cronómetro
sprintf('El muestreo aleatorio encuentra el valor mínimo %f en %f segundos',mm,time)