[pyar] Buscar máximo

[Enrique Gabriel Baquela]

Nunca hay que olvidarse a la vieja y querida fuerza bruta. Para este caso
puntual, que hay infinitos valoes de X, es inaplicable, pero podriamos
separar el dominio en intervalos de longitud p, muestrear el punto medio de
cada intervalo, y en una segunda etapa, tomar el intervalo con valor mas
grande y volver a muestrearlo con una longitud de intervalo mucho menor. Si
p esta bien elegido, aproximas el optimo bastante bien.


El 18 de enero de 2014, 11:49, Enrique Gabriel Baquela
<egbaquela en gmail.com>escribió:

> 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/717b0aca/attachment.html>