# Genetic Algorithm Simulated Annealing Based Clustering



## thinkinginenglish

Hola, el título de artículo de una revista cientifica es el siguiente:
"Genetic Algorithm Simulated Annealing Based Clustering Strategy in MANET"

Hay una palabra a la que no le encuentro sentido "annealing" y lo que viene en el diccionario no me encaja. Por favor, ¿alguien podría arrojar un poco de luz sobre este asunto?
Todavía no me he leído el artículo en cuestión, porque antes de empezar me gustaría saber si va a ser interesante 

Muchas gracias.


----------



## danielfranco

Estrategia en... este, creo que faltan algunos guiones o al menos comas para saber cuál palabra modifica a cual, pero creo que "genetic" modifica a "algorithm", estos modifican a "simulated annealing", y todos estos juntos son la base de la estrategia de "clustering" para un *mobile ad-hoc network *(MANET).

Pero en informática no sé que cuernos quiera decir una "templanza simulada". No, no es cierto, no sé como se traduce "simulated annealing", pero aquí está un enlace que lo explica: CLIC



EDIT - Lo de "simulated annealing" es una analogía de lo que se logra en metalurgia, pero en cuestiones de informática. Si tú entiendes al respecto, felicidades. A mi me quedó la jeta así:


----------



## raulortz

Que tal? Antes que nada en programacion un algoritmo es una serie de pasos que definen la manera de resolver algo, los algoritmos geneticos son usados en inteligencia artificial para resolver problemas de optimizacion (busquedas, ordenamientos, reacciones a situaciones, etc). Entre los algoritmos geneticos encontramos al "Simulated annealing", que es un algoritmo genetico que simula lo que sucede en metalurgia cuando calientas hasta cierto punto un metal que se dilata y que conforme se va enfriando las moleculas van quedando mas compactas porque se van acomodando poco a poco.

La manera mas sencilla de entender el Simulated Annealing Algorithm es haciendo la analogia de cuando tienes una caja con multiples objetos (o arena) y quieres que ocupen el menor espacio posible, lo que naturalmente se hace si no son objetos fragiles es tomar la caja y moverla de un lado hacia otro y los objetos encuentran su mejor posicion entre los demas objetos (la arena se compacta porque los granos encuentran el mejor lugar entre los demas granos de arena).

El algoritmo funciona basicamente igual a lo arriba descrito, se tiene un estado inicial y se busca la optimizacion donde cada movimiento de la caja es un estado diferente que deberia acercar al estado que se busca, si el estado que se logra con una modificacion (baja de temperatura o movimiento de la caja) nos acerca al estado que se busca se acepta y se parte de ese estado para el siguiente, si nos aleja se rechaza y se regresa al estado anterior. Se sigue haciendo esto mismo hasta que no importando cual sea el movimiento que se realice no hay mejora de estado o bien que se hayan realizado cierto numero definido de variaciones (se alcanza temperatura ambiente)


----------



## igres

Os adjunto unos comentarios al respecto que me ha enviado mi hijo, que es experto en el tema, por si pueden ayudar:

De hecho un Simulated Annealing Algorithm no es un algoritmo genético. Los algoritmos genéticos se basan en la simulación de la evolución natural sobre una población de posibles soluciones. El algoritmo de Simulated Annealing no se basa en ninguna población. De todos modos, al igual que los genéticos, también se puede utilizar para realizar una búsqueda de una solución en una espacio de búsqueda de dimensiones considerables.

Supongamos que entre muchos millones de soluciones a un problema queremos encontrar la más eficiente, es decir, la que tiene coste menor. Todas las soluciones posibles al problema conforman el espacio de búsqueda. Realizando transformaciones sobre una solución se puede llegar a una solución “vecina”, es decir, parecida a la primera. La idea del simulated annealing es partir de una solución concreta del espacio de búsqueda escogida al azar e ir recorriendo el espacio realizando pequeñas transformaciones, lo que se llama un recorrido aleatorio. 

Mimetizando los procesos de enfriamiento del metal, primero se permite, desde el punto inicial escoger cualquier solución vecina, tanto si es mejor como peor, pero a medida que pasa el tiempo cada vez se permite menos escoger soluciones con costes mayores. De este modo podemos ir centrándonos poco a poco en una “area” del espacio de búsqueda donde las soluciones sean suficientemente buenas y acabar convergiendo en un mínimo local… que con un poco de suerte también será el global.

Saludos a todos.


----------



## raulortz

Tu hijo tiene razon, el Simulated Annealing no es un algoritmo genetico porque no usa grupos o colonias de "agentes" para ir validando las posibles soluciones y converger a la mas optima. Esta tecnica va validando cada variacion de estado (transformacion) para llegar a la mas optima.

Aunque este foro no es para discusiones tecnicas sino de lenguaje, es muy buena la aclaracion para no dejar informacion erronea.

Volviendo a la pregunta original, aunque lo mas seguro es que para estas fechas thinkinginenglish ya haya leido el articulo y el mismo nos pueda dar el correcto significado de "Genetic Algorithm Simulated Annealing Based Clustering Strategy in MANET", el abstract del articulo dice que habla de una nueva estrategia de "clustering" para administracion de redes de dispositivos moviles basado en una tecnica de optimizacion hibrida llamada GASA (Genetic Algorithm Simulated Annealing).

Ahora sabiendo que Genetic Algorithm Simulated Annealing es una sola cosa y no dos diferentes ya tiene mas sentido el titulo, me atreveria a dar una aproximacion como: "Clustering Strategy based on Genetic Algorithm Simmulated Annealing applied to MANET". El articulo lo escribio un chino.


----------



## thinkinginenglish

Jeje, pues no me llegué a leer el artículo porque no me era útil. De todas formas, MUCHAS GRACIAS por todas vuestras aclaraciones. ))))


----------



## Shanilka

Muchísimas gracias a todos, estoy estudiando para un examen de computación biológica, que es en inglés, y me metí aquí a traducir la palabra "annealing". Toda la información que habeis escrito aquí me viene genial. Mil gracias!!


----------



## Dysnomia

Pero cómo se diría entonces "anneling" en español? (yo me metí buscando una traducción de esa palabra porque las que he encontrado hasta ahora no me cuadran, pero me he quedado igual...)


----------



## Ilialluna

Hola, Dysnomia. En el contexto en que estás trabajando (ácidos nucleicos), annealing se refiere a "hibridación".


----------



## Dysnomia

Hola, Ilialluna! 
Siempre acudes al rescate, jeje, muchas gracias!


----------



## Lazarillo

Ilialluna said:


> Hola, Dysnomia. En el contexto en que estás trabajando (ácidos nucleicos), annealing se refiere a "hibridación".



(*Edit**: *Creo que Ilialluna no tiene razón. En realidad mis explicaciones se refieren sólo al título del hilo.)

Es un poco tarde, pero aprotaré lo siguiente por si sirve de algo en el futuro:

En realidad los algoritmos simuladores del "recocido" (a veces se llaman así en español) reproducen el proceso del recocido (_annealing_) en las fundiciones. Este proceso pretende reducir el número de núcleos sobre el que se va depositando el metal conforme se va enfriando, haciendo que la estrutura final tenga menos defectos. El algoritmo que lo reproduce se emplea para la toma de decisiones en sistemas inteligentes, ya que permite reducir el conjunto de soluciones posibles del sistema (que, o bien tiene por defecto, o que aprende mediante otros métodos).

Por otro lado, la computación evolutiva hace uso de algoritmos genéticos, que reproducen procesos biológicos implicados en la evolución (mutaciones, recombinación y selección natural). Este tipo de algoritmos permite a los sistemas inteligentes generar nuevas soluciones a partir de las existentes. En algunos casos se aplica también la selección de las más efectivas a los sistemas, mientras que en otras, es el experimentador quien hace la selección.

Creo que a lo que se refiere el título del artículo es que se han diseñado algoritmos genéticos que también son capaces de producir el "recocido" de las soluciones. Este proceso es previo a la selección, por lo que se vería simplificado de alguna manera: la selección del algoritmo genético ya no opera sobre todas las soluciones posibles, sino sólo sobre las que han sido identificadas por el recocido como más apropiadas.

Por otra parte, el recocido simulado al que se hace referencia en el artículo, está basado en otra técnica empleada en muchas disciplinas, los métodos de _clustering_ o agrupamiento (crean conjuntos a partir de similitudes entre los elementos).

El artículo no tiene por qué estar referido especificamente a ácidos nucleicos (las aplicaciones de estos métodos de inteligencia artificial son numerorísimas), y desde luego _annealing_ no se refiere a "hibridación".

Resumiendo: en un algoritmo genético, la hibridación (y la mutación) daría lugar a versiones de los posibles algoritmos-hijo creados a partir de dos algoritmos-padre; los métodos de "recocido" y "clustering" harían una preselección de esos algoritmos-hijo en función de unos parámetros pre-establecidos o que compone la propia máquina. Posteriormente se ejecutarían los procedimientos de selección natural de los algoritmos genéticos.

No sé si lo he expuesto bien...

Un saludo,

L


----------



## Ilialluna

Hola, Lazarillo. La cuestión es que Dysnomia hizo una pregunta sobre "annealing" independientemente de este hilo, con el que no tiene nada que ver, y el moderador la unió a él. Por eso le contesté que en el contexto en que ella trabajaba la traducción era "hibridación". Este término se usa así en genética, aunque se hable de "recocido" y "templado" de metales.
Un saludo.


----------



## Lazarillo

Ilialluna said:


> Hola, Lazarillo. La cuestión es que Dysnomia hizo una pregunta sobre "annealing" independientemente de este hilo, con el que no tiene nada que ver, y el moderador la unió a él. Por eso le contesté que en el contexto en que ella trabajaba la traducción era "hibridación". Este término se usa así en genética, aunque se hable de "recocido" y "templado" de metales.
> Un saludo.



Ah, OK, Ilialluna. No me había dado cuenta. Creí que el hilo hacía sólo referencia al título.

Edito mi mensaje anterior.

Saludos!

L


----------

