Aún no tienes acceso a esta clase

Crea una cuenta y continúa viendo este curso

Introducción a la optimización

23/25
Recursos

Aportes 105

Preguntas 4

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesión.

comparto con ustedes un video de derivando donde explica el problema p vs np:
https://www.youtube.com/watch?v=UR2oDYZ-Sao

Problemas del milenio por Un millón de dólares

  • P versus NP
  • La conjetura de Hodge
  • La conjetura de Poincaré
  • La hipótesis de Riemann
  • Existencia de Yang-Mills y del salto de masa
  • Las ecuaciones de Navier-Stokes
  • La conjetura de Birch y Swinnerton-Dyer

Seria muy interesante curso en platzi de este tema!!!

El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en la investigación de operaciones y en la ciencia de la computación.

Me pase 4 dias viendo videos y problemas de n - np // mala idea profundirzar 😃

Revisen este video del canal derivando 😉 es buenisimo y explica bien.

https://www.youtube.com/watch?v=UR2oDYZ-Sao

si quieren indagar mas en optimizacion pueden buscar programacion lineal o no lineal, donde encontraran cosas como el metodo simplex. Recomiendo el libro taha o hillier son de “investigacion de operaciones”. Aqui encontraran muchos otros algoritmos para resolver problemas de minimos y maximos.

Existe la Metaheuristica, que da soluciones aproximadas:

En múltiples problemas de IA nos encontramos modelos asociados a problemas de optimización y búsqueda. Los algoritmos metaheurísticos son algoritmos aproximados de optimización y búsqueda de propósito general. Son procedimientos iterativos que guían una heurística subordinada combinando de forma inteligente distintos subordinada combinando de forma inteligente distintos conceptos para explorar y explotar adecuadamente el espacio de búsqueda.

Casualmente, hay un librería dePython llamada Gurobi que está optimizada para Programaci’no Lineal Entera que es una forma de programación que se utiliza para resolver Problemas como el del Travel Salesman

Aquí lo explican con más ejemplos. Es muy interesante sobretodo a partir del min 5.
https://www.youtube.com/watch?v=wsIru1p5fs0

Comparto este video sobre el Traveling Salesman Problem que lo explica de una forma visual muy buena:
https://www.youtube.com/watch?v=SC5CX8drAtU

Para ver la película Traveling Salesman:

https://www.youtube.com/watch?v=-7mxlwMOORQ

PROBLEMA DEL VENDEDOR VIAJERO

Consiste en un comerciante que quiere visitar n ciudades, empezando y terminando en la misma ciudad y debe determinar el recorrido a seguir para que la distancia sea minima.

Se engloba dentro de los denominados problemas de rutas.

Un solución no tan eficiente pero si un poco optima que lei al problema del travelling salesman es hacer conjuntos pequeño, es decir con 12 ciudades hacer 4 conjuntos de 3 ciudades, probar la ruta mas pequeña entre esas 3 ciudades y asi con cada conjunto, luego repetir esto con los conjutos, espero se haya entendido mi explicación

“P versus NP” es algo más que un rompecabezas matemático abstracto. Su objetivo es determinar—de una vez por todas—qué tipo de problemas se pueden resolver con ordenadores, y cuáles no. Los problemas de clase “P” son “fáciles” de resolver para los ordenadores; es decir, las soluciones a estos problemas pueden ser calculadas en una cantidad razonable de tiempo, en comparación con la complejidad del problema.

https://github.com/karlbehrensg/poo-y-algoritmos-python
Introducción a la optimización

El concepto de optimización permite resolver muchos problemas de manera computacional. Cuando pensamos en un algoritmo de optimización debemos definir una función objetivo que debemos maximizar o minimizar, respetando una serie de limitantes que definamos.

La solución de este tipo de problemas es toda una rama de la inteligencia artificial conocida como Constraint Satisfaction Problems (CSP), aquí un ejemplo: https://www.youtube.com/watch?v=lCrHYT_EhDs

Si alguien esta interesado en saber mas sobre los tipos de optimización, les recomiendo el libro Introducción a la investigación de operaciones de Frederick S Hillier, Gerald J. Lieberman.

Para iniciar en mundo de la optimización es el método simplex.

He aquí una explicación del problema ¿P = NP?
https://www.youtube.com/watch?v=UR2oDYZ-Sao

Hola a todos, les comparto mi grafica, es el historico semanal de la cotización de bitcoin de yahoo finance. lo pueden obtener descargando yfinance o yahoo-finance en sus terminales. Gracias!

from WIKI:
El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en la investigación de operaciones y en la ciencia de la computación.

El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, una gran cantidad de heurísticas y métodos exactos son conocidos, de manera que, algunas instancias desde cien hasta miles de ciudades pueden ser resueltas.

El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y en la fabricación de circuitos electrónicos. Un poco modificado, aparece como: un sub-problema en muchas áreas, como en la secuencia de ADN. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem).

En la teoría de la complejidad computacional, la versión de decisión del TSP (donde, dado un largo “L”, la tarea es decidir cuál grafo tiene un camino menor que L) pertenece a la clase de los problemas NP-completos. Por tanto, es probable que en el caso peor el tiempo de ejecución para cualquier algoritmo que resuelva el TSP aumente de forma exponencial con respecto al número de ciudades.

Esto es Investigación de operaciones y programación lineal. Aquí todas las restricciones se expresan de forma matemática, ya sean ecuaciones o inecuaciones.

1M cash no questions asked. That’s what I like 😎

Optimizar significa buscar la mejor manera de realizar una actividad, y en términos matemáticos, hallar el máximo o mínimo de una cierta función, definida en algún dominio. La optimización constituye un proceso para encontrar la mejor solución de un problema donde “lo mejor” se concilia con criterios establecidos previamente.

  • El concepto de optimización permite resolver muchos problemas de manera computacional.
  • Una función objetivo que debemos maximizar o minimizar.
  • Una serie de limitantes que debemos respetar.

Muy interesante este tema.

Uf! Estas clases motivan, a investigar más sobre el traveling salesman.

El TSP yo lo he trabajado con algoritmos genéticos, sin embargo quiero aprender más sobre inteligencia artifical, como maching learning o redes neuronales.

Compañeros, profesor, en el siguiente link les comparto algo de mi trabajo …

https://github.com/jccp33/TSP-EAX-POSIX

Buscaré más acerca de Travelling Salesman

Optimización
Son algoritmos en los que buscamos la respuesta optima (maximizamos o minimizamos nuestros resultados). Respetando una serie de limitaciones que vienes de nuestro modelado.

Nota:

  • No todos los problemas se pueden resolver (problema P/NP)

Aquí dejo mi código comentado.

#Importamos librerías desde Bokeh. figure es para tener la ventana donde se muestra gráfico.
#output_file es para nombrar el archivo html a generar. show es para  crear un servidos que mostrará el html.
from bokeh.plotting import figure, output_file, show

if __name__ == '__main__':
    #Nombramos archivo de salida
    output_file('graficado_simple.html')

    #Generamos la figura, es decir, dónde pondremos el gráfico
    fig = figure()

    #Pedimos valores a graficar
    total_vals = int(input('¿Cuántos valores quieres graficar?'))

    #Con el número dado por el usuario creamos una lista de valores independientes
    x_val = list(range(total_vals))

    #Inicializamos lista de valores dependientes
    y_val = []

    #Pedimos al usuario valos dependientes
    for x in x_val:
        val = int(input(f'Valor y para {x}:'))
        y_val.append(val)

    #Aquí dibujamos la figura indicando los valores para el eje de las abscisas (x) y las ordenadas (y)
    #En esta sentencia podemos poner los estilos que llevará el gráfico
    fig.line(x_val, y_val, line_width=2)
    
    #Para pedir a bokeh que nos muestre la figura
    show(fig)

Madrugándole al Platzi, jaja

Yandere dev sale del chat

Si les interesa profundizar, hay una disciplina que estudia específicamente este tema y se llama Investigación de operaciones, aunque es recomendable primero entender álgebra lineal.

El concepto de optimización permite resolver muchos problemas de manera computacional. Cuando pensamos en un algoritmo de optimización debemos definir una función objetivo que debemos maximizar o minimizar, respetando una serie de limitantes que definamos.

Creo que estos son de los denominados problemas imposibles, tales como los que se usan para hacer encriptación.

Polinomiales*

Graficando la función Seno(x)

from bokeh.plotting import figure, output_file, show
import math
import numpy as np

if __name__ == '__main__':
    output_file('graficado_simple.html')
    fig = figure()

    x_vals =  np.arange(0,20,0.1)
    y_vals = []

    for x in x_vals :
        val = math.sin(x)
        y_vals.append(val)

    fig.line(x_vals,y_vals,line_width=2)
    show(fig)

También encontramos problemas dentro de nuestros conceptos algorítmicos, que todavía no se han resuelto, como la diferencia entre polinomineal vs no polinomineal.

The travelling sales man, es un problema, que todavía no tiene solución y que demuestra que hay problemas que el humano, todavía no es capaz de resolver por el momento.

Los problemas de optimización, no son solo cuestiones académicas. También son formas de modelar soluciones para el mundo real.

Hay que tener en cuenta todos los constraints, para encontrar valores dentro de esos parámetros.

Tenemos que repestar ciertas limitantes a la hora de optimizar.

Maximizar, se refiere a encontrar el input que devuelve el outpur más alto, mientras que minimizar, se refiere a el input que retorna el output más pequeño.

Pensar en algoritmos de optimización, pensamos en una función por maximizar o minimizar.

Los grandes problemas del mundo, se pueden reducir a problemas de optimización.

La optimización, nos permite comprender todo un amalgama de problemas computacionales.

La forma en cómo optimizamos nuestros algoritmos, es encontrando valores con ciertas características.

Seria muy interesante un curso de optimización computacional en Platzi.

Excelente clase! 😄

billones = miles de millones

Este video ayuda a entender el problema del agente viajero que nos mencionó David en la clase. O el famoso"Traveling salesman problem"

https://www.youtube.com/watch?v=LUuSLdBSejQ

Espero a alguien le pueda servir. Es explicación básica pero concisa.

Optimización
Rezolver muchos problemas de manera computacional.
Traveling salesman.
Premios Turing

El problema de Ruta de Transporte no se resuelve con derivadas debido a que el problema contiene demasiadas variables, para ello existen algoritmos clásicos pararesolverestos problemas. como Algoritmo de Esquina Noroeste, Ruta mas corta. Todos estos los puedes encontrar en cualquier libre de Investigacion de Operaciones, yo les recomiendo el Taha. si quieren profundizar mas en esto.

Optimizacion: En mi experiencia vi una materia en el 9no semetres de ingenieria de sistemas respecto a optimizacion de sistemas y algoritmos y pues me encontraba con problemas como el que explico el profesor uno por logica puede pensar de que si agarra la ruta A llegaras mas rapido a la ruta B, pero no es tan sencillo como parece en el ambito de la optimizacion se requiere utilizar muchos modelos matematicos y estadisticos para encontrar la solucion adecuada a este problema y a eso sumale la complejidad del algoritmo, lo que quiere decir si realmente este algoritmo es eficiente para este problema, por que no basta solamente con una respuesta sino saber si la respuesta es factible o no, realmente un campo muy bonito donde se ven las matematicas, estadisticas y logica computacional, para algunos puede ser complejos o aterrador pero una vez que lo entiendes o lo comprendes te daras de cuenta que es algo muy hermoso como los numeros te guian a la respuesta deseada.

¿Habrá algún curso enfocado a la optimización en profundidad? 🤓

Hay que diferenciar entre problemas de optimización y problemas de decisión para entender ciertos detalles interesantes. En los primeros se busca un máximo o mínimo, mientras que en los últimos se busca la existencia de un cierto objeto. El problema P vs NP es una pregunta sobre problemas de decisión.
El TSP (traveling salesman problem) es un problema de optimización en el cual se busca un mínimo. Es fácil ver que hay un problema de decisión asociado a el TSP: “Hay un camino de longitud menor o igual a X?” donde X es un numero positivo.
TSP es un problema NP-hard y el problema de decisión asociado a el es NP-complete.
Los problemas P son aquellos para los que existe un algoritmo determinista de tiempo polinomial que lo resuelve (el algoritmo puede construir en tiempo polinomial el objeto deseado). Los problemas NP son aquellos para los que existe un algoritmo no determinista de tiempo polinomial que lo resuelve (el algoritmo puede verificar en tiempo polinomial si un objeto es el objeto buscado, mas no necesariamente construye el objeto).
El problema P vs NP es la pregunta “A es un problema de decisión tal que para cualquier objeto, se puede verificar en tiempo polinomial si es el objeto deseado. Se puede construir el objeto deseado en tiempo polinomial?”

Curiosa calse. De esas que te generan más dudas que certezas e invitan a seguir investigando.

Travelling Salesman Problem (TSP): Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

En los años 50 inicio la investigación de operaciones, y se crearon bastantes modelos matematicos que en esa epoca no eran posibles y que hoy pueden ser posibles

Excelente clase y bastante inspiradora

Esto lo relaciono con lo visto en programación lineal, un curso de la universidad en donde veíamos diferentes técnicas de optimización. De hecho estos problemas de optimización de recursos en diferentes sistemas, son pan de cada día en la investigación y desarrollo hecha por muchas organizaciones al rededor del mundo.

¿Cómo se relacionan las optimizaciones matemáticas (por ejemplo, el teorema de Lagrange) con la optimización de algoritmos a nivel práctico?

Apasionante

Profundizando en el tema ahora mismo!

Investigación de Operaciones

Que gran tema!! ❤️

problema planteado en 1930 por primera vez, resulta importante por su aplicación que puede funcionar en áreas de logística, electrónicos y genética.

A mi parecer podría ayudar muchísimo a entender mas el ADN y es uno de los campos que mas se están estudiando, pero el problema esta catalogado como NP-hard, que quiere decir muuuuuuy complicado

Que gran tema!!!

Tema muy interesante.

Pueden revisar este texto
"Advances in Combinatorial Optimization: Linear Programming Formulations of the Traveling Salesman and Other Hard Combinatorial Optimization Problems"

aquí un link

https://b-ok.global/book/2660249/710d05

Que interesante saber que hayan problemas que hasta el momento con la teconologia de hoy en dia no se han podido resolver de manera eficiente, seria un reto enorme lograr algo asi.

Interesante tema y que buena clase.

Complicado, complicado hasta de entender el problema mas allá de lo intuitivo. Este million dolars no es para mi.

¡Muy interesante!

De hecho, en los problemas de Machine Learning se buscar minimizar una función de error por diferentes métodos de optimización, por ejemplo, mínimos cuadrados o gradiente descendiente.

Complejidad de un problema != complejidad de resolverlo
np conjunto problemas en que podemos comprobar en un tiempo razonable si la solución es correcta.
p conjunto de problemas que podemos resolver en un tiempo razonable.
p esta incluida en np.
La cuestión es si p = np ( y aún no hemos encontrado el algoritmo) o si p != np (es lo que cree la mayoría pero aún no se ha demostrado)

Bastante interesante el saber que aun hay problemas de optimizacion que no han podido ser resuelto.

Si a alguien le interesa leer sobre esto, tambien existe estrategias como la utilizacion de algoritmos geneticos para hallar la solucion mas optioma entre un rango definido de iteraciones.

https://towardsdatascience.com/introduction-to-optimization-with-genetic-algorithm-2f5001d9964b

https://developers.google.com/optimization/routing/tsp Aquí lo explican con Python, no está sencillo pero por si se quieren dar una idea.

Y me parece interesante que queden problemas por optimizar en el mundo a los cuales no se les ha encontrado un algoritmo correcto, pero al mismo tiempo es una oportunidad 😄

Recomiendo este vídeo explica muy bien porque el problema del Traveling Salesperson es tan complejo!

Coding Challenge #35.1: Traveling Salesperson
Me estoy planteando crear un gráfico dinámico en bokeh para implementar el código en python

Muy interesante

Tengo la solución (el algoritmo optimizado) para el problema del vendedor viajero, pero esta caja de texto es muy pequeña para mostrarla

P = PN ? tiene pinta de que no son iguales

Nosotros pensando en cómo optimizar y la naturaleza nos da siempre lecciones de optimización; ejemplo: la abejas. Las abejas construyen sus panales con celdas con la forma de un prisma hexagonal para colocar a sus larvas y almacenar la miel, de esta manera se minimiza mano de obra y material.

La optimización no sólo es maximizar y minimizar, también consiste en controlar aquellas variables que nos permitan modificar la dinámica de un sistema de tal forma que haga lo que nosotros queremos.

Uff Muy interesante!

Los algoritmos de optimización nos permiten encontrar las mejores opciones para algun problema, cual es el vuelo mas barato, la ruta con menos tráfico, etc.

Los algoritmos de optimización se pueden reducir a algoritmos p vs np (polinominiales vs no poliniominales)

¿Creen ustedes que si se crea una Inteligencia Artificial futura tipo “GPT-4” y le dan el comando de que resuelva este problema… lo haría?

¿Qué hubiese hecho Phileas Fogg scon una computadora? 🌐Definitivamente Julio Verne fue un adelantado de su época.

Notas 👀
Introducción a la optimización.

  • El concepto de optimización permite resolver muchos problemas de manera computacional.
  • Una función objetivo que debemos maximizar o minimizar.
  • Existen una serie de limitantes que debemos respetar.
  • Muchos problemas reales se pueden resolver con optimización (trafico, venta de boletos de avión, etc).
  • Un problema de optimización que no tiene solución aún es el como recorrer varias ciudades de manera óptima. Traveling salesman.
  • Hay más problemas en el mundo que aun no tienen solución.
  • Para observar si un algoritmo es realizable se analiza $P vs NP$. Hay algunos que no se podrán resolver sin importar nada.

😃

Este apartado consiste en explicar en qué consiste el algoritmo de optimización y para que es utilizado

aca dejo otro video de derivando donde habla de uno de los problemas mas difíciles de complejidad algorítmica.

Cuando David dice cosas en inglés quedo o.o

La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder. En esencia, la pregunta ¿es P = NP completo?