Hellbrownies

La Variable Neighborhood Search no es tan poética como el Simmulated Annealing, pero también podemos intentar explicarla parabólicamente. Esta búsqueda está basada asimismo en búsqueda local, pero con una filosofía bastante distinta. Como sabemos, la búsqueda local elige un punto cualquiera de la función que queremos minimizar/maximizar y mira si alguno de los puntos de alrededor son «mejores»; si lo son, sigue buscando a partir de dicho punto. En la gráfica, el verde es el punto inicial, y la flechita 1 marca la solución encontrada siguiendo búsqueda local en un problema de minimización. Éste es también el primer paso en la VNS.

Lo novedoso de VNS es que modifica el concepto de «puntos de alrededor». Por ejemplo, los vecinos del 11 no serán ya el 10 y el 12, sino que podré definir un segundo vecindario en el que los vecinos sean puntos a distancia 10 entre sí (1, 21, 31, …), un tercer vecindario con puntos a distancia creciente en potencias de 2 (…, 5, 9, 13, 17, 25, 31, …), un cuarto vecindario elevando ese número a sí mismo (121, 1331, …), y así sucesivamente. Si me quedo sólo con el primer vecindario, puede ocurrir que las soluciones mejoren lentamente y se estanquen en un mínimo local. La idea del VNS básico es cambiar de vecindario cuando ya no sea posible mejorar una solución en el vecindario actual.

En la gráfica, el punto Y sería vecino del mínimo local en 1, y el punto Z del mínimo local en 2. Para que esta historia no se convierta en una búsqueda a ciegas, los vecindarios se definen con cierta lógica dentro del problema que estamos estudiando; esta «lógica» es la heurística que guía a tu algoritmo para que no vaya dando bandazos aleatoriamente.

Dijo aquél que sólo entiendes algo cuando eres capaz de explicárselo a tu abuela… yo no soy capaz, salta a la vista. Próxima entrega, algoritmos genéticos.

Así está mi cerebro, pero sin el simulado. Y eso que ha tenido tiempo de enfriarse un poco a lo largo de este fin de semana… Este post se gestó en estado de ebullición cerebral pero, ya que estaba escrito, publiquémoslo.

Esto del recocido es una de las metáforas curiosas que reinan en el mundo de la metaheurística; no es la única, comparte protagonismo con los algoritmos genéticos, los cúmulos de partículas y las colonias de hormigas…

Traducido también como enfriamiento simulado, el simulated annealing consiste en imitar el proceso del recocido industrial: se calienta un metal y se enfría lentamente para que las moléculas tengan tiempo de configurarse óptimamente; por lo visto, los cristales que se forman así son más perfectos y se reduce la energía interna. Esta idea inspira, en pocas palabras, un algoritmo que busca un valor lo más cercano posible al óptimo global de una función.

La manera más simple de buscar el óptimo podría ser aplicar búsqueda local a partir de una solución cualquiera. Imaginemos una función que queremos, por ejemplo, minimizar; elegimos un valor al azar, y nos dejamos caer siguiendo menos el gradiente hasta alcanzar un mínimo y quedar parados en un valle. ¿Cuál es el problema? Que lo más seguro es que acabemos en un mínimo local, si no tenemos la suerte de elegir caer por la pendiente adecuada.

Ahora imaginemos que estamos aplicando búsqueda local pero que, de vez en cuando, elegimos soluciones «peores», es decir, que no minimizan la función. Esto haría que pudiéramos saltar montañas enteras, para acabar en un valle mucho más profundo que en el que nos encontramos. El problema es ahora que saltar mucho puede ser también perjudicial, pues el algoritmo no se centra en mejorar exhaustivamente una solución, que es al fin y al cabo el objetivo de todo esto, conseguir un mínimo lo suficientemente bueno. ¿Qué se hace? Aquí entra en juego el recocido. Se usa un parámetro, llamado metafóricamente temperatura, que va descendiendo, es decir, enfriándose. Cuando la temperatura es alta, hay también una alta probabilidad de aceptar soluciones en principio «malas»; cuando es baja, la probabilidad de aceptar una solución peor es casi nula. Lo normal es que la probabilidad de aceptar una solución siga una distribución de Boltzmann; a efectos prácticos, significa que dicha probabilidad desciende exponencialmente.

Supongamos que la bola verde marca la solución inicial, que vamos mejorando a lo largo de la flecha 1; sin embargo, en un momento dado decidimos aceptar la solución que está arriba del todo, de calidad pésima si lo que queremos es minimizar. Sin embargo, esta solución nos lleva a un mínimo mejor que el que nos esperaba por el otro camino, con lo que quedaríamos más contentos que unas pascuas cuando termine de ejecutarse el algoritmo.

Y esto es todo, aquí acaba el primer capítulo de metaheurísticas divulgativas.

… eine JAR-Datei bauen und deployen

"Construir y deployar un archivo JAR"… sin comentarios.

Las quejas del post anterior venían a cuento de una presentación que tengo que preparar para mañana. El tema es SOA, Service-Oriented Architecture, o si queréis, arquitectura orientada a servicios. De lo que trata, no viene a cuento ahora… sólo quiero dejar por aquí una curiosidad que encontré mientras buscaba información:

Yo estoy con el ponente. Es un ejemplo más de cómo se pueden rellenar páginas con palabras vacuas… Y como es de bien nacidos ser agradecidos, aquí está la presentación completa, en SlideShare.

Supongamos que estamos intentando enterarnos de qué se esconde detrás de unas determinadas siglas, por ejemplo, XYZ:

"XYZ es un concepto de arquitectura de software que define la utilización de servicios para dar soporte a los requerimientos de software del usuario."

"XYZ proporciona una metodología y un marco de trabajo para documentar las capacidades de negocio y puede dar soporte a las actividades de integración y consolidación."

Dudo que dichas líneas puedan aclarar a nadie lo que se puede esconder tras XYZ. Me pregunto si a alguien le dirá algo lo que a mí me parecen palabras vacías; si así fuera, pues admitiré que esto no es para mí. Además de ininteligible, no sé si hay peor manera de empezar un artículo; lo que es peor es que los párrafos siguientes no son mucho más clarificadores, están plagados de perlas como ésta:

"La XYZ es tanto un marco de trabajo para el desarrollo de software como un marco de trabajo de implantación."

Esta abominable manera de expresarse no es exclusiva de un artículo en concreto; al contrario, suele ser lo corriente en todo aquello que tiene que ver con los servicios web. Todo lo que gira alrededor de ellos, se mueve por un vocabulario artificioso, que huelo a distancia (y que no soporto). Además, no se limita todo a las traducciones nefastas al español. Aquí algunas muestras en inglés:

"ABC is defined as the uses of software and computer systems architectural principles to integrate a set of enterprise computer applications."

Ay >_<.

Últimamente no voy a ningún sitio, más que de mi piso a la FH, con alguna que otra incursión a la maravillosa biblioteca municipal de Heilbronn. Entre áridos apuntes en alemán sobre redes y/o economía, y bastante entretenimiento con Eclipse, esto que sigue es de lo más emocionante que pasa por mis días:

Es la placa que nos han dado para el proyecto de Embedded Systems, y con la que jugamos a programar un ATMega169, alias Butterfly, alias Mariposa.

Es decir, por una parte, programamos el ATMega169, utilizando como intermediaria la placa de ahí arriba, conectada al puerto serie del ordenador. Para ello utilizamos AVR Studio, y algún programa (C / Ensamblador) que trastee los puertos del cacharro en cuestión. Una vez que tiene su programa, la Mariposa es independiente, pues tiene alimentación propia, un LCD bastante grande, un joystick, un reproductor de sonidos bastante decente y un sensor de luz y temperatura. Todo ello en el tamaño de una tarjeta de crédito, y según nos han dicho, por tan sólo 20 euros.

Mi relación con ese cacharro es de amor-odio… aunque últimamente me gusta, sobre todo cuando las cosas parece que funcionan. Y desde luego, prefiero jugar a la electrónica que a sacar tendencias económicas de la empresa de turno… A veces incluso me dan ganas de seguir dedicándome a esto, aunque supongo que cuando termine este curso, se acabó, no volveré a tener un microcontrolador en las manos.

Al menos este "puente" (para vosotros, porque para mí no es tal) tengo visita :-). Al menos saldré a airearme un poco, espero.

Creo que hace algo más de dos años que empecé a usar normalmente Linux; según recuerdo, las prácticas de Sistemas Operativos ya las hacía en mi SuSE, que tuve instalada un año. Después instalé Ubuntu, hará ahora un año… y aunque al principio Gnome me parecía un poco simplón, y aunque sigo pensando que las aplicaciones de KDE son mucho mejores, en seguida me acostumbré, y ahora KDE me parece demasiado recargado (por eso me instalo Kaffeine, Kate, y algún otro en Gnome, y punto).

El cuatrimestre pasado acaeció lo peor… sólo teníamos red inalámbrica en el piso, y tuve que renunciar a Ubuntu… por más que lo intenté, no había manera de que Dapper se conectara. Éste es el problema más gordo que he tenido -¡me obligó a utilizar Windows cinco meses!- y que no he conseguido solucionar.

El problema que he tenido hoy es mucho menos importante… o al menos, me lo parece, después de arreglarlo. Resulta que, después de un mes funcionando como la seda, el sonido de mi Ubuntu ha decidido dejar de funcionar. No los mp3, o el sonido del navegador, o skype… no, todo el sonido, ni siquiera un mísero bip. Creo que se trata de un bug de Edgy, porque jamás me pasó con Dapper, y ahora van dos veces seguidas. La primera vez, reinstalé. Total, lo acababa de instalar, y no me costaba nada hacerlo otra vez. Ahora ya me resultaba más fastidioso volver a meterme en una reinstalación, cuando ya lo tengo todo configurado a mi gusto, y por un problema tan estúpido.  

¿Qué creo que lo causó? Pues yo me inclino por un paquete, el Clips, que es lo único que he instalado hoy. Según he leído por ahí, le ha pasado a mucha más gente, y también sospechan que ha sido algún paquete de actualización. Esperemos que lo arreglen para Feisty, si no, esto es lo que a mí me ha funcionado (sin garantías :P):

1. Desinstalar todos los paquetes alsa. Atención, porque te desinstala paquetes aparentemente no relacionados, en mi caso fueron gnome-terminal, gnome-session, gnome-control-center, gnome-applets, ubuntu-minimal, gdm, y algún otro.
2. Reiniciar. Entra en modo consola, porque se ha cargado el inicio gráfico. Ahora instalar los paquetes alsa, y también todos los que fueron borrados en el paso anterior.
3. Reiniciar. Si os habéis olvidado de gdm, estaréis otra vez en modo consola. Si no, ya estaréis en Gnome.
4. Atención: el sonido está ahora automáticamente al mínimo. Sólo hay que subirlo y ya funciona todo otra vez.

Aquí está lo que me quitó el sueño. Es una feria tecnológica, y según dicen, la más grande del mundo; su contrapartida española sería el SIMO, que para que nos hagamos una idea, ocupa 65.000 metros cuadrados, mientras que el CeBIT ocupa 450.000. Es inmenso: de los 26 pabellones nosotros no veríamos más que 5 ó 6.

La foto no es la mejor del mundo, pero entre unas cosas y otras, no hice más que un par de ellas; éste es el pabellón 2 (como digo, de 26).

Si me preguntan mi opinión, diré que está bien, pero no compensa meterse 1000km entre pecho y espalda; no creo que la gente vaya allí a hacer el negocio de su vida, debe ser que no tengo esa mentalidad ganadora. Ahora, si vives en un radio de 200km o tienes tiempo para pasar un par de días, es una buena opción. A nosotros nos regalaron las entradas en la FH, creo que rondaban los 33 euros.

Había muchos pabellones que querían hacer negocios, tratos, conseguir nuevos socios, inversores, y tal: allí se distinguían entre ellos por el traje, a mí desde luego no me pararon ;). El más interesante para mí fue el de las universidades; los del DFKI presentaban aplicaciones muy de su estilo (reconocimiento de voz, multimedia, agentes), que ya me conozco de vista gracias a aquello de la traducción automática; uno de mis favoritos fue un stand con ordenadores (a simple vista, bastante normales) que podías controlar con la mirada; primero calibraba tu vista y parpadeos, y luego podías jugar al tres en raya, escribir un email, etc., y sólo usando la vista: mirando y pestañeando. Llamadme naive, pero me resultó impresionante :P.

Para no seguir acribillando con fotos de Berlín… un post de los que escribí en Febrero y que nunca vio la luz. 

Dicen que una de las ventajas que tiene estudiar algo técnico es que, vayas donde vayas, el vocabulario no difiere demasiado, y el inglés se supone que puede sacarte del apuro. Igual que dicen que 2+2=4 (y yo digo, depende…) pues no es difícil intuir qué significan Prozess o Implementierung. En Alemania no tienen además ningún complejo para usar directamente la palabra inglesa en vez de buscar un término equivalente; es lo que hacen en Server, Tools, Web Services o Software Engineering. Lo ponen en inglés y se quedan tan anchos; en España se tiende a traducir bastante más.

Por eso no me daba realmente miedo de venir a estudiar a Alemania (por eso y por un exceso de confianza); luego llegan los exámenes orales y se fastidia la cosa ;). Sin embargo la pseudoregla arriba enunciada tiene notables excepciones como Wechselseitiger Ausschluss (¿quién diría sin saberlo que eso es "exclusión mutua"?), o Verklemmung (deadlock, interbloqueo, o como diría cierto personajillo, abrazo mortal).

Como recuerdo, dejo aquí algunas bonitas palabras alemanas, de longitud creciente, que he coleccionado en mis horas de estudio; las dejo tal cual iban apareciendo (declinadas, en plural…) y con la traducción para que os riáis un rato los que decíais "ah, ¿pero tú sabes alemán?" No, no sé… pero me medio voy apañando.

• Selbstoffenbarungsohr (22): Intraducible concepto, cuyo significado no me atrevo a aventurar
• Helligkeitsinformationen (24): Informaciones de la luminosidad
• Herstellerunabhängigkeit (24): Independencia del fabricante
• Wahrnehmungeigenschaften (24): Propiedades de la percepción
• anwendungsunterstützenden (25): Dícese de aquello que apoya a una aplicación
• Auslieferungsinformationen (26): Informaciones de la entrega
• Datenbeschreibungssprachen (26): Lenguaje de descripción de datos
• Videokompressionalgorithmus (27): Algoritmo de compresión de vídeo
• Fehlererkennungsmechanismen (27): Mecanismos de reconocimiento de errores
• Selbstbeschreibungsfähigkeit (28): Capacidad de describirse a sí mismo
• Schnittstellendefinitionssprachen (33): Lenguajes de definición de interfaces
• Programmiersprachenunabhängigkeit (33): Independencia del lenguaje de programación

Hay quien tiene ideas raras y no soy la única: si no a ver, quién se dedica a ver este blog en Lynx, que no es otra cosa que un navegador en modo texto, y mandarme capturas después… ejem.

Por su parte, Lynx no deja de ser curioso, se puede probar aquí y la última versión es de octubre de 2006, así que no es un proyecto abandonado; de hecho yo lo he probado y corre estupendamente en mi Ubuntu (que ya no puedo utilizar, explicación al respecto irrelevante). A pesar de las evidentes limitaciones, las páginas se ven aceptablemente bien, algunos colores, y nada más allá de pura información textual.

No nos engañemos… el primer navegador de internet no fue en modo texto, sino gráfico, desarrollado en el CERN por Tim Berners-Lee (la historia, una captura). Aquello fue a finales de 1990, principios de 1991. Lynx fue desarrollado a mediados de 1992, por gente de la Universidad de Arkansas para uso interno de la misma. Luego lo liberaron y tal, pero todavía hay gente que se dedica al mantenimiento. Recomendado como curiosidad…