Entradas etiquetadas como ‘Optimización’

10 consejos para dar consejos

Todos hemos visto alguna vez esas listas que aparecen en internet de gente experta en algún tema que nos dan consejos sobre prácticas convenientes o no en alguna red social o en algún apartado específico de la red. Normalmente, además, son consejos negativos: de cosas que no debemos hacer. En muchos casos, dichos consejos están dictados por el sentido común, en otros después de observar ciertas prácticas abusivas por parte de algunos usuarios y muchas son simplemente un corta y pega de otros consejos elaborados por otros. Son comunes las listas de prácticas de buena costumbre en Twitter, en Instagram o en Facebook. La verdad es que yo hubiera agradecido que algunos comentaristas de blogs se hubieran leído alguna lista de consejos sobre comentarios y la aplicaran. Así que me voy a animar y voy a dar una de dichas listas, casi se podría considerar una metalista, puesto que voy a dar consejos para elaborar cualquiera de esas listas de consejos:

Allá va mi lista:

10 consejos que has de seguir cuando quieras elaborar una lista de consejos sobre cualquier tema en internet:

  1. No dé consejos.

Creo que he terminado mi lista un poco antes de lo previsto, pero ahora voy a tratar de justificarla y mi justificación, aunque parezca imposible, viene de la mano de algunos resultados matemáticos. Me explico:

Existen algunos problemas de optimización (encontrar el mejor valor que puede alcanzar una función) que no pueden resolverse por métodos clásicos y que, si tratamos de resolverlos con un ordenador, nos encontramos con un problema bastante serio como se verá. Para que se me entienda voy a escoger el más típico de dichos problemas de optimización. Ya hablamos de él en algún momento: el problema del viajante (TSP): en dicho problema, expresado de forma simple,se trata de visitar un conjunto de ciudades volviendo al punto de partida (se conocen las distancias entre ellas) recorriendo la menor distancia posible. dijkstra_1

Por extraño que parezca, a pesar de lo simple de su planteamiento, si el número de ciudades no es muy bajo no existe ningún método que nos permita encontrar la ruta óptima. Uno puede pensar que probando todas las combinaciones de ciudades se podrá encontrar la mejor. Pero nos encontramos con la dificultad de que todas las combinaciones, en general, es un número ingente. Supongamos que tenemos que visitar 100 ciudades, todas las combinaciones es 100! y este es un número más grande de lo imaginable (el número de partículas elementales en el universo observable es mucho menor). Por lo tanto, hemos de renunciar a encontrar la ruta óptima y limitarnos a conseguir una ruta aceptablemente buena. Para conseguir dicha ruta aceptablemente buena, un procedimiento que se suele utilizar es el llamado de Algoritmos Genéticos ¿Cómo funcionan los algoritmos genéticos? Pues los algoritmos genéticos tratan de simular el proceso darwinista mediante el cual la naturaleza consigue especies que se adapten a su medio. Voy a intentar explicarlo con el ejemplo de las ciudades:

Para simplificar, supongamos que tenemos 6 ciudades a las que denominamos A, B, C, D, E y F. Tratamos de encontrar la permutación óptima de dichas letras que nos de la distancia mínima. Los elementos que componen nuestro algoritmo genético son los siguientes:

En primer lugar necesitamos una población inicial con el número de individuos que decidamos de antemano, para obtener dicha población inicial nos basta con encontrar aleatoriamente tantas permutaciones como nos sean necesarias. Así entre todas las permutaciones posibles escogemos por sorteo unas cuantas. Supongamos que, en nuestro caso, la población inicial es de 6 individuos y construimos dichos individuos aleatoriamente y obtenemos los siguientes seis: ABEFDC, ABCEFD, AEBCFD, ACDBEF, AEFCDB y ADCBFE (empezamos siempre en la A que es donde está el punto de partida y entendemos que, al final, hemos de volver a A) . Como estos individuos los hemos construidos aleatoriamente, puede que ninguno de ellos se acerque, ni de lejos, a la solución óptima, pero nos da igual, eso no es importante. Lo siguiente que necesitamos es una función que nos diga cómo de buenos son los elementos de nuestra población. En este caso la función puede ser la distancia que tenemos que recorrer si seguimos el orden de cada permutación; esto es: para ABEFDC (y para todas las demás permutaciones), medimos la distancia de A a B, le sumamos la distancia de B a E, de E a F, de F a D, de D a C y de C a A, para obtener la distancia total de ABEFDC.

Así, cada uno de los individuos de nuestra población tendrá asignado un número y, en nuestro caso, cuanto más pequeño sea dicho número, mejor, más corta será la distancia que tengamos que recorrer. Esta función es lo que se llama la aptitud de los individuos, por lo tanto, en nuestro ejemplo cuanto más pequeña sea la distancia asociada a una permutación, más apta será dicha permutación.

Ahora le asignamos papeletas a cada individuo para realizar un sorteo, cuanto más apto sea un individuo (menos distancia tengamos que recorrer), más papeletas le asignamos para el siguiente sorteo que consiste en un proceso de selección: vamos a realizar emparejamientos por puro sorteo (pero los mejores individuos tienen más papeletas) y vamos a construir 3 parejas mediante dicho sorteo (puede que un mismo individuo salga dos o más veces en dicho proceso de emparejamiento). Supongamos que una de dichas parejas sea la formada por los individuos ABCEFD y ACDBEF, ahora vamos a cruzar a dichos individuos, vamos a obtener sus hijos, para construir la siguiente generación.

Hay varios métodos para hacer esto, en algunos casos es más simple describir dicho proceso, en otros un poco más complicado. Propongamos uno: hacemos otro sorteo y escogemos un lugar entre 2 y 4: supongamos que sale 3: eso significa que al cruzar ABCEFD con ACDBEF, vamos a obtener dos hijos, el primero escogemos las tres primeras ciudades de ABCEFD: ABC y el resto de las ciudades las recorremos: después de C, en el orden en el que aparecen en ACDBEF: después de C está D, después estaría B, pero como por B ya hemos pasado, nos la saltamos y vamos a E y por último a F; por tanto, el primer hijo sería ABCDEF. Ahora hacemos lo mismo empezando por ACDBEF, así las tres primeras ciudades serían ACD, en ABCEFD, la siguiente ciudad después de D es A, que nos la saltamos, después B, después C que nos la saltamos porque ya la hemos visitado, después E y por último F. Por lo tanto, a partir de ABCEFD y ACDBEF hemos obtenido dos hijos: ABCDEF y ACDBEF (que, curiosamente, es igual que uno de sus padres, pero no nos preocupamos por ello).

Por lo tanto, como teníamos tres parejas y de cada pareja hemos obtenidos dos hijos, tenemos ahora seis individuos de nuevo. Esos individuos los hemos obtenido intercambiando la información genética de la población inicial. Pero ahora interviene un elemento esencial, sin él el método no funcionaría, sin él la naturaleza no habría obtenido los individuos que mejor se adaptan a su habitat: la mutación. Mutaciones ocurren pocas y la mayoría son regresivas: dan peores individuos, pero , muy de vez en cuando, producen individuos mejor adaptados y sin ella el proceso darwiniano no tendría sentido. Así lo que hacemos es, una vez obtenidos los hijos, realizamos un nuevo sorteo pero tal que la probabilidad de ser mutado sea muy pequeña (digamos 1 entre 1000), por lo tanto, de cada 1000 individuos mutamos aproximadamente a 1. Supongamos que uno de los hijos que hemos obtenido en el proceso anterior ABCDEF sale mutante ¿qué hacemos? realizar otro sorteo (ya llevamos unos cuantos) y sacamos dos números entre el 2 y el 6, por ejemplo 3 y 5, pues intercambiamos las ciudades que aparecen en tercer y quinto lugar para obtener ABEDCF.

Resumiendo:

a partir de la población inicial, escogemos parejas (por un sorteo asignando más papeletas a los mejores individuos), cruzamos dichas parejas (en un proceso en el que se intercambia la información de dichas parejas) y puede que mutemos algún individuo y con estas tres operaciones hemos construido la siguiente generación a la que le volvemos a aplicar el proceso y así tantas veces como se decida en un principio. Lo curioso es que hay un resultado matemático que nos asegura que, con este método, vamos a aproximarnos a la solución óptima tanto como queramos (cuantas más generaciones mejor) y que si algunos de los elementos no lo tenemos en cuenta puede que nunca nos aproximemos a dicha solución porque nos quedemos estancados en lo que se llama un óptimo local y nunca nos aproximemos al óptimo global que es lo que estamos buscando.

maximo

Y ¿qué tiene que ver todo esto con las listas de consejos en internet?

Pues que si seguimos las listas de consejos, no estamos siguiendo un proceso evolutivo: nos estamos estancando en óptimos locales ya que hacen que todos los individuos se parezcan y eliminamos diversidad que es fundamental para obtener mejores elementos. En algún sentido se puede decir que el mestizaje es fundamental para la mejora de la población (¿hacen alta más argumentos aún para probar lo estúpido del racismo?) y que poblaciones muy endógamas (como las familias reales), suelen degenerar y dar individuos muy defectuosos.

Mezclénse, por favor… Huy, al final he dado un consejo 😉

 

¡Unamos los pueblos!

Hoy os quisiera plantear un problema de los llamado de optimización, uno de esos problemas que puede parecer, a primera vista, más simple de lo que en realidad es.

Supongamos que tenemos cuatro pueblos cercanos que, por alguna razón, aún no están comunicados entre sí: igual ha pasado un huracán y ha destruido las carreteras que existían o, peor aún, un banco las ha expropiado y se las ha quedado sin saber qué hacer con ellas. Da igual, el caso es que queremos construir carreteras que las unan y estamos en una suposición, por lo tanto, podemos suponer que no nos sobra el dinero y queremos construir la red de carreteras con menos kilómetros, la más económica. El último dato que nos falta es que las ciudades se encuentran formando un cuadrado de lado 10 km. Así tenemos el siguiente diagrama:

En principio, el problema no parece tan difícil, ya que todas los posibles formas de unir los vértices de un cuadrado usando el menor número de carreteras (segmentos de rectas empezando y terminando en ciudades) son los que presentamos a continuación:

Y se puede comprobar que los de la primera fila suman una distancia total de 30 km, los de la segunda (usando el teorema de Pitágoras) de 20+√200 km que son algo más de 34 km. Así que parece claro que gana cualquiera de los diseños de la primera fila. Pero ¿son esas todas las posibles soluciones?

 

En principio no, porque hay otros diseños con la misma longitud que los de la primera fila y que presentan algunas ventajas sobre las anteriores, como las dos que presentamos ahora:

Si nos fijamos estos dos diseños tienen también una longitud de 30 km y la ventaja a la que nos referíamos es que la distancia más larga entre los pueblos es más corta que la distancia más larga en aquellos diseños como el que tenía forma de U: para los de forma de U la distancia más larga posible entre dos pueblos es de 30 km, mientras que en el diseño en H la distancia más larga entre dos pueblos es de 20 km.

Pero todavía lo podemos hacer mejor.  Si consideramos unir cada par de ciudades diagonalmente opuestas por sendas carreteras con un cruce (o una rotonda si tenemos un alcalde al que le gusten mucho: por aquí por el sur, el de Dos Hermanas, por ejemplo), tendremos un diseño en X:

 

La longitud total de esa red de carreteras es poco más de 28 km (de nuevo usando Pitágoras). Y parece que ya no se va a poder mejorar, pero estaremos equivocados

Entonces, ¿tenemos diseño ganador? Pues no, porque podemos modificar ligeramente los diseños en H hasta obtener algo así:

Está demostrado que la longitud mínima se alcanza cuando escogemos los puntos de cruce de las carreteras  de forma que éstas formen un ángulo de 120º en los puntos en los que se bifurcan.

 

Es fácil calcular cómo se ha de escoger el punto en el que las carreteras se bifurcan para que sea óptimo el diseño.

Si nos fijamos  el triángulo ABC es un triángulo rectángulo (el ángulo en C es de 90º) y el ángulo en B debe ser la mitad de 120º , 60º, por lo tanto, puesto que los ángulos internos de un triángulo suman 180º, tenemos que el ángulo en A (en el triángulo ABC) es de 30º. Si hacemos una  copia del triángulo ABC (pegando por el lado AC), y nos fijamos en el triángulo ABB’, éste es un triángulo equilátero (puesto que los ángulos en A, B y B’ son de 60º los 3) y por tanto BC es la mitad de AB, como AC vale 5 km, usando el teorema de Pitágoras tenemos que el lado BC mide 5/ √3 y por lo tanto,  obtenemos que la longitud total de esta red de carreteras es de 10+10√km que es algo más de 27 km y es el ganador absoluto.

Ahora es el momento en el que planteo: ¿y si en vez de cuatro ciudades son tres todas a la misma distancia? ¿Y cinco?

Si queréis ver la solución a estos problemas, se puede este vídeo maravilloso (está en inglés, pero creo que es suficientemente ilustrativo y muy recomendable), donde se da la solución para los distintos casos, pero lo más interesante es que llega a dicha solución con la única ayuda de unas pompas de jabón. Por cierto, esto me da una idea de la que hablaros otro día: de las matemáticas de las pompas de jabón. Pero eso será en otra ocasión.