[pyar] Buscar máximo

[Enrique Gabriel Baquela]

Si es muy meseta el algoritmo genético tiene muchas chances de converger en
la meseta me parece. Pero no existe el algoritmo general que resuelva
eficientemente todos los casos. Una opción seria hacer un muestreo
aleatorio por montecarlo y en base al análisis de las muestra ver que
método elegir.
El 18/01/2014 09:01, "Angel Java Lopez" <ajlopez2000 en gmail.com> escribió:
>
> Ahi, ya iria con algoritmo genetico, una especie de hill climbing en
paralelo. Y pondria a 1000 instancias de Amazon a trabajar, cada una con su
poblacion, e intercambiado cromosomas ;-)  Es la idea de
> https://github.com/ajlopez/SimpleGA/tree/master/samples/tspdistr
>
> Lo que envie anoche, es el segundo metodo? el "viejo truco" de perturbar
el punto medio? ;-)
>
> Con las condiciones del problema, puede una recta cortar en mas de tres
puntos a la curva en el intervalo [a,b] ? me parece que si
>
> Si ponemos condicion que toda recta corta a la curva en el intervalo
[a,b] A LO SUMO en dos puntos, y hay un maximo, tenemos un problema que es
subproblema del inicial.
>
> Si tuvieramos un algoritmo magico que nos diera, dados a, b, el x tal que
f'(x) = f(b)-f(a) (es decir el punto x donde la derivada de x se hace igual
a la diferencia de los extremos), entonces ese x nos acerca al maximo. Si
f(b)-f(a) es positivo, nos quedamos con el intervalo [x,b] y repetimos. Si
f(b)-f(a) es negativo, nos quedamos con el intervalo [a,x] y repetimos. El
punto x existe, por el teorema de Rolle. Es unico, por las condiciones del
problema. Cuando f(b)=f(a), x es el maximo.
>
> Nos leemos!
>
> Angel "Java" Lopez
> @ajlopez
>
>
> 2014/1/18 Enrique Gabriel Baquela <egbaquela en gmail.com>
>>
>> Para evitar la meseta estaba bueno lo de correrlo con varios inicios
aleatorios, pero el tiempo de calculo sube bastante.
>>
>> El 17/01/2014 20:30, "fisa" <fisadev en gmail.com> escribió:
>>
>>> Y adelanto el principal problema de hill_climbing (aparte de máximos
>>> locales, que en este caso no tenemos):
>>> Si hay una meseta, se va a quedar estancado en ese punto.
>>>
>>> El día 17 de enero de 2014, 20:27, Angel Java Lopez
>>> <ajlopez2000 en gmail.com> escribió:
>>> > Ah! Ahora entendi, es O(n log(m)) no O(n log(n))
>>> >
>>> > Para mi daba lo mismo, porque
>>> >
>>> > O(n log(m)) en la segunda
>>> > O(2 log(m)) en la primera == O(log(m))
>>> >
>>> > es asi?
>>> >
>>> > Bueno, gracias por el problema, muy bueno, paso a offline, time to
fight for
>>> > my food ;-)
>>> >
>>> > Angel "Java" Lopez
>>> > @ajlopez
>>> >
>>> >
>>> > 2014/1/17 Alejandro Santos <listas en alejolp.com>
>>> >>
>>> >> La busqueda ternaria es O(log(M)), donde M representa la precisión
del
>>> >> resultado en decimales.
>>> >>
>>> >> La busqueda en N subintervalos con el pseudo codigo de recien es O(N
>>> >> log(M)), donde N es la cantidad de subintervalos, y M la precisión
del
>>> >> resultado en decimales.
>>> >>
>>> >>
>>> >>
>>> >>
>>> >> 2014/1/17 Angel Java Lopez <ajlopez2000 en gmail.com>:
>>> >> > Bien, mencionas "n de afuera", cual es el "n de adentro"?
>>> >> >
>>> >> > Si no hay "n de afuera" distinto de "n de adentro", veo que las dos
>>> >> > tienen
>>> >> > la misma O
>>> >> >
>>> >> >
>>> >> > 2014/1/17 Alejandro Santos <listas en alejolp.com>
>>> >> >>
>>> >> >> 2014/1/17 Angel Java Lopez <ajlopez2000 en gmail.com>:
>>> >> >> > Hmmm...
>>> >> >> >
>>> >> >> > cual es el n en O(log(n))?
>>> >> >> >
>>> >> >> > Yo puse n en la segunda solucion, a ese n se refiere O(n
log(n))?
>>> >> >> >
>>> >> >>
>>> >> >> Ok, capaz hacer un analisis BigOh sin codigo es... confuso.
>>> >> >>
>>> >> >> El n de afuera se refiere a la cantidad de subintervalos en que
partís
>>> >> >> [a, b], y en que luego partis el subintervalo no monótono.
>>> >> >>
>>> >> >> Con tu explicación me imaginé algo así:
>>> >> >>
>>> >> >> def busqueda_en_intervalos(f, a, b, N):
>>> >> >>     EPS=1e-8
>>> >> >>     while True:
>>> >> >>         L = partir_en_intervalos(f, a, b, N)
>>> >> >>         for E in L:
>>> >> >>             if not es_monotono(E):
>>> >> >>               a, b = E
>>> >> >>               break
>>> >> >>         if abs(a - b) <= EPS:
>>> >> >>             return (a + b) / 2
>>> >> >>
>>> >> >> --
>>> >> >> Alejandro Santos
>>> >> >>
>>> >> >> _______________________________________________
>>> >> >> pyar mailing list pyar en python.org.ar
>>> >> >> http://listas.python.org.ar/listinfo/pyar
>>> >> >>
>>> >> >> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>> >> >>
>>> >> >> La lista de PyAr esta Hosteada en USLA - Usuarios de Software
Libre de
>>> >> >> Argentina - http://www.usla.org.ar
>>> >> >
>>> >> >
>>> >> >
>>> >> > _______________________________________________
>>> >> > pyar mailing list pyar en python.org.ar
>>> >> > http://listas.python.org.ar/listinfo/pyar
>>> >> >
>>> >> > PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>> >> >
>>> >> > La lista de PyAr esta Hosteada en USLA - Usuarios de Software
Libre de
>>> >> > Argentina - http://www.usla.org.ar
>>> >>
>>> >>
>>> >>
>>> >> --
>>> >> Alejandro Santos
>>> >> _______________________________________________
>>> >> pyar mailing list pyar en python.org.ar
>>> >> http://listas.python.org.ar/listinfo/pyar
>>> >>
>>> >> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>> >>
>>> >> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre
de
>>> >> Argentina - http://www.usla.org.ar
>>> >
>>> >
>>> >
>>> > _______________________________________________
>>> > pyar mailing list pyar en python.org.ar
>>> > http://listas.python.org.ar/listinfo/pyar
>>> >
>>> > PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>> >
>>> > La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
>>> > Argentina - http://www.usla.org.ar
>>>
>>>
>>>
>>> --
>>> fisa  -  Juan Pedro Fisanotti
>>> _______________________________________________
>>> pyar mailing list pyar en python.org.ar
>>> http://listas.python.org.ar/listinfo/pyar
>>>
>>> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>>
>>> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
Argentina - http://www.usla.org.ar
>>
>>
>> _______________________________________________
>> pyar mailing list pyar en python.org.ar
>> http://listas.python.org.ar/listinfo/pyar
>>
>> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>
>> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
Argentina - http://www.usla.org.ar
>
>
>
> _______________________________________________
> pyar mailing list pyar en python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
Argentina - http://www.usla.org.ar
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20140118/a58645ca/attachment.html>