1

Confira se os dados contidos na parte inferior desta capa esto corretos e, em seguida, assine no espao reservado para isso.

Se, em qualquer outro local deste Caderno, voc assinar, rubricar, escrever mensagem, etc., ser excludo do Exame.

2 Este Caderno contm 5 questes discursivas referentes Prova da Lngua Estrangeira escolhida pelo candidato. No destaque nenhuma folha.

3 Se o Caderno estiver incompleto ou contiver imperfeio grfica que impea a leitura, solicite imediatamente ao Fiscal que o substitua.

4 Ser avaliado apenas o que estiver escrito no espao reservado para cada resposta, razo por que os rascunhos no sero considerados.

5 Escreva de modo legvel, pois dvida gerada por grafia, sinal ou rasura implica r reduo de pontos.

6 No ser permitido o uso de dicionrio.

7 Use exclusivamente caneta esferogrfica, confeccionada em material transparente, de tinta preta ou azul. Em nenhuma hiptese se avaliar resposta escrita com grafite.

8 Utilize para rascunhos, o verso de cada pgina deste Caderno.

9 Voc dispe de, no mximo, trs horas, para responder as 5 questes que constituem a Prova .

10 Antes de retirar-se definitivamente da sala, devolva ao Fiscal este Caderno.

Assinatura do Candidato: ________________________________________________

UFRN Exame de Proficincia 2012_3 Espanhol Cincias Exatas e da Terra 1

As questes de 01 a 05, cujas respostas devero ser redigidas EM PORTUGUS, referem -se

ao texto abaixo.

Metaheurstica de optimizacin mediante colonias de hormigas y aplicaciones

Evelyn Menndez Alonso

Resumen:

La mayora de los Problemas de Optimizacin Combinatoria de inters cientfico o prctico estn

incluidos en la clase NP-completos, ya que no existen algoritmos exactos con complejidad

polinmica que permitan resolverlos. Debido a su intratabilidad, se han diseado una gran

cantidad de mtodos aproximados, los cuales encuentran buenas soluciones en tiempos

razonables. Uno de estos mtodos es la metaheurstica de Optimizacin mediante Colonias de

Hormigas (ACO); que tiene su fuente de inspiracin en el comportamiento de las hormigas reales,

que minimizan el recorrido entre su colonia y cualquier fuente de abastecimiento, basndose

fundamentalmente en los rastros de feromona que van dejando a su paso. Para la metaheurstica

ACO se han propuesto varios algoritmos, que desde su surgimiento han probado su amplia

aplicabilidad y eficiencia en la solucin de Problemas de Optimizacin Combinatoria.

I. INTRODUCCIN

La existencia de una gran cantidad y variedad de Problemas de Optimizacin Combinatoria

incluidos en la clase NP-completos que necesitan ser resueltos de forma eficiente, impuls

el desarrollo de procedimientos para encontrar buenas soluciones, aunque no fueran ptimas.

Estos mtodos, en los que la rapidez del proceso es tan importante como la calidad de la

solucin obtenida, se denominan heursticos o aproximados. Un mtodo heurstico es

un procedimiento para resolver un problema de optimizacin bien definido mediante una

aproximacin intuitiva, en la que la estructura del problema se utiliza de forma inteligente para

obtener una buena solucin. Luego, con el propsito de obtener mejores resultados que los

alcanzados por los heursticos tradicionales surgen los denominados procedimientos

metaheursticos. Los procedimientos metaheursticos son una clase de mtodos aproximados que

estn diseados para resolver problemas difciles de optimizacin combinatoria, en los que los

heursticos clsicos no son efectivos . Los metaheursticos proporcionan un marco general para

crear nuevos algoritmos hbridos combinando diferentes conceptos derivados de la inteligencia

artificial, la evolucin biolgica y los mecanismos estadsticos.

II. METAHEURSTICA DE OPTIMIZACIN MEDIANTE COLONIAS DE HORMIGAS

La metaheurstica Optimizacin mediante Colonias de Hormigas o Ant Colony Optimization,

propuesta para resolver problemas complejos de optimizacin combinator ia, tiene su fuente de

inspiracin en el comportamiento de colonias de hormigas reales. Las hormigas son capaces de

seguir la ruta ms corta en su camino de ida y vuelta entre la colonia y una fuente de

abastecimiento. Al desplazarse cada una va dejando un rastro de una sustancia qumica llamada

feromona a lo largo del camino seguido, "transmitindose informacin" entre ellas de esta forma.

Las feromonas forman un sistema indirecto de comunicacin qumica entre animales de una

misma especie, que transmiten informacin acerca del estado fisiolgico, reproductivo y social,

as como la edad, el sexo y el parentesco del animal emisor, las cuales son recibidas en el

sistema olfativo del animal receptor, quien interpreta esas seales, jugando un papel importante

en la organizacin y la supervivencia de muchas especies.

Al iniciar la bsqueda de alimento, una hormiga aislada se mueve a ciegas, es decir, sin nin guna

seal que pueda guiarla, pero las que le siguen deciden con buena probabilidad seguir el camino

con mayor cantidad de feromona. Considere la Figura 1 donde se observa cmo las hor migas

establecen el camino ms corto. En la figura (a) las hormigas llegan a un punto donde tienen que

decidir por uno de los caminos que se les presenta, lo que resuelven de manera aleatoria. En

consecuencia, la mitad de las hormigas se dirigirn hacia un extremo y la otra mitad hacia el otro

UFRN Exame de Proficincia 2012_3 Espanhol Cincias Exatas e da Terra 2

extremo, como ilustra la figura (b). Ya que las hormigas se mueven aproximadamente a

una velocidad constante, las que eligieron el camino ms corto alcanzarn el otro extremo ms

rpido que las que tomaron el camino ms largo, quedando depositada mayor cantidad de

feromona por unidad de longitud, como ilustra la figura (c). La mayor densidad de feromonas

depositadas en el trayecto ms corto hace que ste sea ms deseable para las siguientes

hormigas y por lo tanto, la mayora elige transitar por l. Considerando que la evaporacin de la

sustancia qumica hace que los caminos menos transitados sean cada vez menos deseables y la

realimentacin positiva en el camino con ms feromona, resulta claro que al cabo de

un tiempo casi todas las hormigas transiten por el camino ms corto, como se ilustra en la figura

(d).

Figura 1: Comportamiento de las hormigas reales.

En analoga con el ejemplo biolgico, ACO se basa en la comunicacin indirecta de una colonia

de agentes simples, llamados hormigas (artificiales), por medio de la huella de feromona

(artificial). La huella de feromona en ACO sirve como informacin numrica distribuida, que las

hormigas usan para la construccin probabilstica de soluciones del problema a resolver y la

adaptan durante la ejecucin del algoritmo para reflejar su experiencia de bsqueda.

Las hormigas de la colonia se mueven, concurrentemente y de manera asncrona, a travs de los

estados adyacentes de un problema, que puede representarse en forma de grafo con pesos.

Este movimiento se realiza siguiendo una regla de transicin basada en la informacin local

disponible en las componentes o nodos. Esta informacin incluye una heurstica y una

memorstica (rastros de feromona) para guiar la bsqueda. La inicializacin de parmetros

depende del algoritmo especfico, generalmente deben tenerse en cuenta parmetros como: el

rastro inicial de feromona asociado a cada transicin o arco, el nmero de hormigas en la

colonia, los pesos que definen la proporcin en la que afectarn la informacin heurstica y

memorstica en la regla de transicin probabilstica. En programacin de actividades se controla

la planificacin de tres componentes: la generacin y puesta en funcionamiento de las hormigas

artificiales; la evaporacin de feromona, que se usa como un mecanismo para evitar el

estancamiento en la bsqueda y permitir que la hormigas busquen y exploren nuevas regiones

del espacio; y las acciones del demonio, utilizadas para implementar tareas desde una

perspectiva global que no pueden llevar a cabo las hormigas, por ejemplo, observar la calidad de

todas las soluciones generadas y depositar una nueva cantidad de feromona adicional en las

transiciones asociadas a algunas soluciones. El procedimiento actualiza memoria hormiga se

encarga de especificar el estado inicial desde el que la hormiga comienza su camino y adems

almacenar la componente correspondiente en la memoria de la hormiga L. La decisin sobre cul

ser el nodo inicial depende del algoritmo especfico. En los procedimientos calcular

probabilidades de transicin y aplicar poltica decisin se tienen en consideracin el estado

actual de la hormiga y el conjunto de arcos del grafo (A), los valores actuales de la feromona

visibles en dicho nodo y las restricciones del problema (W) para establecer el proceso de

transicin probabilstico hacia otros estados vlidos. La actualizacin feromona en lnea paso a

paso es el procedimiento donde se actualiza el rastro de feromona asociado a un arco, cuando la

hormiga se mueve entre los nodos que este conecta. Una vez que la hormiga ha construido la

solucin puede reconstruir el camino recorrido y actualizar los rastros de feromona de los arcos

visitados mediante el procedimiento llamado actualizacin feromona en lnea a posteriori .

Disponible en: http://www.monografias.com/trabajos93/metaheuristica -optimizacion-colonias-hormigas-y-aplicaciones/metaheuristica-optimizacion-colonias-hormigas-y-aplicaciones.shtml. Acceso en: 25 set. 2012. [Adaptado]

UFRN Exame de Proficincia 2012_3 Espanhol Cincias Exatas e da Terra 3

Questo 1

Defina procedimentos metaheursticos.

Questo 2

O que fazem os feromnios na trilha das formigas?

Espao para Resposta

Espao para Resposta

UFRN Exame de Proficincia 2012_3 Espanhol Cincias Exatas e da Terra 4

Questo 3

Na experincia ACO, para que serve o rastro do feromnio?

Questo 4

Em que consiste o procedimento actualizacin feromona en lnea paso a paso ?

Espao para Resposta

Espao para Resposta

UFRN Exame de Proficincia 2012_3 Espanhol Cincias Exatas e da Terra 5

Questo 5

Traduza o fragmento textual abaixo no espao reservado para isso.

Seu texto dever apresentar clareza e estar bem articulado tanto em termos estruturais quanto de sentido.

La mayora de los Problemas de Optimizacin Combinatoria de inters cientfico o prctico

estn incluidos en la clase NP-completos, ya que no existen algoritmos exactos con

complejidad polinmica que permitan resolverlos. Debido a su intratabilidad, se han

diseado una gran cantidad de mtodos aproximados, los cuales encuentran

buenas soluciones en tiempos razonables. Uno de estos mtodos es la metaheurstica de

Optimizacin mediante Colonias de Hormigas (ACO); que tiene su fuente de inspiracin en

el comportamiento de las hormigas reales, que minimizan el recorrido entre su colonia y

cualquier fuente de abastecimiento, basndose fundamentalmente en los rastros de

feromona que van dejando a su paso. Para la metaheurstica ACO se han propuesto varios

algoritmos, que desde su surgimiento han probado su amplia aplicabilidad y eficiencia en la

solucin de Problemas de Optimizacin Combinatoria.

ESPAO DESTINADO AO TEXTO DEFINITIVO