[pyar] Buscar máximo

[Enrique Gabriel Baquela]

Comentario al margen, al que le interesen las metaheuristicas les paso el
link de un muy buen libro: http://cs.gmu.edu/~sean/book/metaheuristics/
Saludos.


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/fb9e4699/attachment-0001.html>