Resolución de un problema de construcción de circuitos virtuales a través de ag 11




descargar 83.93 Kb.
títuloResolución de un problema de construcción de circuitos virtuales a través de ag 11
fecha de publicación20.02.2016
tamaño83.93 Kb.
tipoSolución
b.se-todo.com > Documentos > Solución







Universidad de Buenos Aires

Facultad de Ingeniería



Sistemas de Programación No Convencional de Robots (75.70)

TRABAJO PRÁCTICO FINAL

Aplicación de Algoritmos Genéticos en la construcción de Circuitos Virtuales de Red”


Docente: Merlino Hernán

Fecha de Entrega: 11/08/2008



CARRIZO HERNÁN

FAGALDE PATRICIO

AMANTEA ARIEL R.

GIACHINI ANDRÉS

83608

83810

81968

82096


Nota de Presentación: Firma:




Índice

Esquema general del algoritmo genético 8

Funcionamiento de un algoritmo genético 8

Limitaciones y campo de aplicación de los algoritmos genéticos 8

10

Resolución de un problema de construcción de circuitos virtuales a través de AG 11

Exposición de la resolución con Algoritmos Genéticos 11

Algoritmo de resolución 12

Objetivo

A través del presente trabajo se pretende emplear la técnica de algoritmos genéticos para la construcción de circuitos virtuales en una red de computadoras, a fin de resolver el problema de poder obtener el camino más corto a través del cual hacer viajar los datos desde un punto a otro de la red.

Luego de desarrollar los conceptos teóricos necesarios, se demostrará un uso práctico de la técnica en un desarrollo de software que da una solución al problema que se plantea a lo largo del trabajo.
Descripción del problema

Dado el caso en que una organización o empresa desea montar una red WLAN, para mantener interconectadas varios puntos de ventas, dicha red puede ser implementada utilizando los recursos que provee Internet, vale decir, puede ser “montada virtualmente” utilizando los routers que se utilizan en Internet, para poder alcanzar un punto de una red, desde otro punto remoto.

Internet se encuentra conformada por una serie routers interconectados, en donde cada router sabe hacia dónde debe dirigir un paquete que recibe gracias a la dirección IP destino que se incluye en el paquete. El router en base a la dirección IP de destino busca en una tabla cual de los routers interconectados sabe como dirigir el paquete y se lo envia a éste. La trayectoria que sigue el paquete al ir desde un punto hacia otro, no es siempre la misma pues un router puede estar interconectado a 2 o mas routers que saben dirigir el paquete y la decisión de a quien entregárselo puede depender de factores como congestión del router destinatario, enlace caído, etc.

En una red virtual, el viaje de un punto de la misma hacia otro se hace siempre por el mismo camino, ya que se supone que los caminos alternativos se conocen y el que se elige es el mejor, o el que provee una menor latencia.

Un circuito virtual es el establecimiento de un camino “lógico” entre dos nodos o puntos de la red, que encapsula los saltos intermedios que debe realizar un paquete para llegar desde el origen al destino (El equipo que envía la información sabe que la misma llegará al destino si la envía a través de su salida más cercana, pero no conoce el camino “físico” que va a seguir la información).
Transmisión de paquetes sin circuitos virtuales
En la figura se muestra una representación de la trayectoria que siguen los paquetes de datos a través de la red para llegar desde el origen (A) hasta el destino (B), en una transmisión que se efectúa sin utilizar circuitos virtuales, con lo cual dependiendo del caso, los paquetes seguirán rutas diferentes (o no).


Transmisión de paquetes con circuito virtual
En este caso, la figura muestra que para transmitir datos de A hacia B, se sigue siempre el mismo camino entre los posibles conocidos, dado que se consiguió determinar de alguna forma, que el elegido era el óptimo.




De este último caso, surge entonces la problemática a resolver.

Internet comprende un número elevado de routers interconectados, a través de los cuáles podría establecerse un circuito virtual, cada uno de los cuales puede tener n conexiones a otros routers, con lo cual la decisión de cuál es el camino óptimo a seguir no es algo sencillo de determinar, sino que comprende un problema complejo que requiere de un procesamiento exhaustivo dada la cantidad de combinaciones posibles, y para lo cual no existe una “fórmula” que permita calcularlo de una manera eficiente.

Solución propuesta

Dada una topología de una red definida, en la cual se conocen los routers o nodos que la componen, y el tiempo de latencia entre cada router o nodo, se propone la utilización de la técnica de algoritmos genéticos para efectuar la construcción de un circuito virtual entre dos puntos específicos de la red, de forma tal de que se minimice el tiempo de transferencia de datos entre los puntos elegidos. El camino virtual construido será válido durante el transcurso de tiempo en el cual no se modifique la topología de la red. Con cada modificación de la topología, los circuitos virtuales deberán calcularse nuevamente.
Algoritmos Genéticos

A mediados de la década de 1970, un investigador de la Universidad de Michigan llamado John Holland, ideó una técnica de búsqueda basada en la teoría de la evolución de Darwin, la cual se dio a conocer como algoritmo genético.
Su nombre proviene de su inspiración en la evolución biológica y su base genético-molecular.

Esta técnica se basa en los mecanismos de selección que utiliza la naturaleza, de acuerdo a los cuales los individuos más aptos de una población son los que sobreviven, al adaptarse más fácilmente a los cambios que se producen en su entorno.

Hoy en día se sabe que estos cambios se efectúan en los genes de un individuo (unidad básica de codificación de cada uno de los atributos de un ser vivo), y que sus atributos más deseables se transmiten a sus descendientes cuando éste se reproduce sexualmente.
John Koza [1] define “algoritmo genético” de la siguiente manera:
"Es un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas de entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres (letras o números) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta función matemática que refleja su aptitud. "
La importancia de los Algoritmos Genéticos reside en que son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización.
Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.

Un algoritmo genético consiste en una función matemática o una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuáles de ellos deben generar descendencia para la nueva generación.
Versiones más complejas de algoritmos genéticos generan un ciclo iterativo que directamente toma a la especie (el total de los ejemplares) y crea una nueva generación que reemplaza a la antigua una cantidad de veces determinada por su propio diseño.
Una de sus características principales es la de ir perfeccionando su propia heurística en el proceso de ejecución, por lo que no requiere largos períodos de entrenamiento especializado por parte del ser humano, principal defecto de otros métodos para solucionar problemas, como los Sistemas Expertos.
Los algoritmos genéticos forman parte de una familia denominada algoritmos evolutivos, que incluye las estrategias de evolución, la programación evolutiva y la programación genética.



Figura 1 – Esquema general del algoritmo genético

Esquema general del algoritmo genético


  1. Inicializar aleatoriamente una población de soluciones a un problema, representadas por una estructura de datos adecuada.

  2. Evaluar cada una de las soluciones, y asignarle una puntuación o fitness según lo bien que lo hayan hecho.

  3. Escoger de la población la parte que tenga una puntuación mayor

  4. Mutar (cambiar) y entrecruzar (combinar) las diferentes soluciones de esa parte escogida, para reconstruir la población.

  5. Repetir un número determinado de veces, o hasta que se haya encontrado la solución deseada.

Funcionamiento de un algoritmo genético


Los algoritmos genéticos establecen una analogía entre el conjunto de soluciones de un problema, llamado fenotipo, y el conjunto de individuos de una población natural, codificando la información de cada solución en una cadena, generalmente binaria, llamada cromosoma. Los símbolos que forman la cadena son los llamados genes. Cuando la representación de los cromosomas se hace con cadenas de dígitos binarios se le conoce como genotipo. Los cromosomas evolucionan a través de iteraciones, llamadas generaciones. En cada generación, los cromosomas son evaluados usando alguna medida de aptitud. Las siguientes generaciones (nuevos cromosomas), llamada descendencia, se forman utilizando dos operadores, de cruzamiento y de mutación.

Limitaciones y campo de aplicación de los algoritmos genéticos


El poder de los Algoritmos Genéticos proviene del hecho de que se trata de una técnica robusta, y pueden tratar con éxito una gran variedad de problemas provenientes de diferentes áreas, incluyendo aquellos en los que otros métodos encuentran dificultades. Si bien no se garantiza que el Algoritmo Genético encuentre la solución óptima, del problema, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimización combinatoria. En el caso de que existan técnicas especializadas para resolver un determinado problema, lo más probable es que superen al Algoritmo Genético, tanto en rapidez como en eficacia. El gran campo de aplicación de los Algoritmos Genéticos se relaciona con aquellos problemas para los cuales no existen técnicas especializadas. Incluso en el caso en que dichas técnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas hibridándolas con los Algoritmos Genéticos.

La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pudieran ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla:

  • Su espacio de búsqueda (sus posibles soluciones) debe estar delimitado dentro de un cierto rango.

  • Debe poderse definir una función de aptitud que nos indique qué tan buena o mala es una cierta respuesta.

  • Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora.

El primer punto es muy importante, y lo más recomendable es intentar resolver problemas que tengan espacios de búsqueda discretos aunque éstos sean muy grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de búsqueda continuos, pero preferentemente cuando exista un rango de soluciones relativamente pequeño.

La función de aptitud no es más que la función objetivo de nuestro problema de optimización. El algoritmo genético únicamente maximiza, pero la minimización puede realizarse fácilmente utilizando el recíproco de la función maximizante (debe cuidarse, por supuesto, que el recíproco de la función no genere una división por cero). Una característica que debe tener esta función es que tiene ser capaz de "castigar" a las malas soluciones, y de "premiar" a las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez.

La codificación más común de las soluciones es a través de cadenas binarias, aunque se han utilizado también números reales y letras. El primero de estos esquemas ha gozado de mucha popularidad debido a que es el que propuso originalmente Holland, y además porque resulta muy sencillo de implementar.

Resolución de un problema de construcción de circuitos virtuales a través de AG


A continuación se detalla la aplicación de la técnica de algoritmos genéticos para la construcción de circuitos virtuales en una red.

Dada la siguiente topología de una red, en la cual cada nodo del grafo representa un router



Los números que aparecen en los vértices del grafo indican el tiempo de latencia entre nodo y nodo. Se busca encontrar el camino o circuito virtual con menor tiempo de latencia que conecte A con G.

Exposición de la resolución con Algoritmos Genéticos


Definimos la estructura del AG de la siguiente manera:

ROUTER

A

B

C

D

E

F

G

ORDEN

0

OB

OC

OD

OE

OF

OG

Donde Oi representa el orden que tiene el router en el circuito virtual, es decir el individuo…

A

B

C

D

E

F

G

0

0

5

1

3

2

4

Representa el circuito A –> B –> D –>F –> G

Con lo expuesto anteriormente se podría realizar un programa informático que resuelva este tipo de problemas de forma general tomando como entrada el nodo origen, el nodo destino y la topología de la red que bien podría ser una matriz cuadrada, donde cada columna y cada fila de la misma representen los nodos de la red y sus coordenadas el tiempo de latencia de la conexión. En el ejemplo, la misma sería:




A

B

C

D

E

F

G

A

0

2

3

-

-

-

-

B

2

0

-

4

-

-

5

C

3

-

0

-

4

-

-

D

-

4

-

0

-

3

-

E

-

-

4

-

0

-

5

F

-

-

-

3

-

0

1

G

-

5

-

-

5

1

0

Desde dicha matriz se podrían deducir los esquemas inválidos.

La función aptitud debe evaluar el tiempo de latencia entre cada nodo consecutivo propuesto por el individuo. Una función que podría aplicarse a este problema, sería obtener el circuito virtual a través de la estructura del individuo y luego sumar todas las conexiones de los nodos obteniendo los datos de la matriz, por ejemplo:

A

B

C

D

E

F

G

0

1

*

2

*

3

4

Donde: * = Cualquier nro.

A –> B –> D –>F –> G

A

–>

B

–>

D

–>

F

–>

G




2

+

4

+

3

+

1

= 10

Como el problema es de minimización y la mayoría de los métodos de selección eligen los individuos con mejor puntaje, se podría elegir un tope arbitrario al que sea restado el resultado de la función aptitud.

Algoritmo de resolución


Para resolver el problema comenzamos con una población de individuos con genes cuyos alelos son elegidos al azar.

Con el tipo de estructura propuesto pueden generarse individuos inválidos, los cuales deben ser descartados cada vez que nazcan. Por Ejemplo:

B

C

D

E

F

1

2

0

4

5

Pues el nodo A no está conectado con el nodo D.

Generalizando para el caso del primer nodo se puede ver que los individuos que no cumplan con el esquema

B

C

D

E

F

< 2

< 2

*

*

*

Son individuos inválidos.

Además del anterior, existen muchos esquemas más que delatan individuos inválidos, éstos pueden ser armados antes de comenzar la resolución del problema, o bien sobre la marcha.

Luego de descartar los individuos inválidos iniciales se evalúa la aptitud de cada uno a través de la función aptitud.

Posteriormente se procede a la cruza de los más aptos, adoptando cualquier mecanismo de selección y acto seguido se realiza una mutación de algunos individuos de la nueva población.

Implementación práctica de la solución

Se realizo el siguiente prototipo del problema:



El problema presentado se resolvió de forma óptima utilizando la herramienta LINGO y de forma heurística utilizando una implementación adaptada al problema de AG. El objetivo del trabajo es poder comparar que tan bien funcionan los AG para la resolución de este tipo de problemas y si es factible su uso práctico en este ámbito, evaluando el tiempo que tomo llegar a la solución y cuanto se aproxima ésta a la solución óptima

Resolución Óptima

Para resolver el problema en forma optima, se desarrollo el modelo de programación lineal que representa al problema planteado y se implemento el mismo en el leguaje LINGO que es una herramienta diseñada para resolver problemas de investigación operativa, el código se detalla en el anexo.

El resultado óptimo fue el siguiente:



Se demoró 10,2 seg en su resolución.

Conclusiones

Referencias

[1] - http://www.genetic-programming.com/johnkoza.html

[2] - http://eddyalfaro.galeon.com/alg-geneticos.html

Algoritmos Genéticos Paralelos – Antonio la Torre de la Fuente – 16/09/2006

[3] - http://desacad.ita.mx/contec/rev23-5.pdf


similar:

Resolución de un problema de construcción de circuitos virtuales a través de ag 11 iconResolución de circuitos

Resolución de un problema de construcción de circuitos virtuales a través de ag 11 iconProblema 2 Miscelánea de construcción

Resolución de un problema de construcción de circuitos virtuales a través de ag 11 iconLa construcción de la alteridad a través de las imágenes

Resolución de un problema de construcción de circuitos virtuales a través de ag 11 iconCapitulo Nº 6: Resolución Del Problema

Resolución de un problema de construcción de circuitos virtuales a través de ag 11 icon4. Usuarios Virtuales. 1 Creamos un grupo y usuarios virtuales. Otras opciones

Resolución de un problema de construcción de circuitos virtuales a través de ag 11 iconEl mayor problema a través de la historia de la humanidad, con relación...

Resolución de un problema de construcción de circuitos virtuales a través de ag 11 iconGerardo Schmedling
No se preocupen porque en algún momento la mente rechace una información nueva; eso es absolutamente normal, eso no tiene ningún...

Resolución de un problema de construcción de circuitos virtuales a través de ag 11 iconEl problema del conocimiento esta vinculado al problema de la verdad

Resolución de un problema de construcción de circuitos virtuales a través de ag 11 iconEl problema del conocimiento esta vinculado al problema de la verdad

Resolución de un problema de construcción de circuitos virtuales a través de ag 11 iconResumen La radiación electromagnética es la transmisión de energía...




Todos los derechos reservados. Copyright © 2019
contactos
b.se-todo.com