PRELIMINARES

INTRODUCCION

El presente modulo se ha diseado para facilitar el aprendizaje a los alumnos del curso de Bioinformtica de la escuela de ingeniera de Sistemas e Informtica, ya que es un curso que requiere de uso y manejo de Lenguajes de Programacin para la construccin de Algoritmos Genticos como: Lenguaje C, Java, etc. y contenidos de Biologa, es por ello que el presente modulo brinda la informacin necesaria para que el alumno pueda comprender mejor el curso.

Bioinformtica, utiliza tecnologa de la informacin para organizar, analizar y distribuir informacin optima, con la ayuda de la biolgica y poder solucionar problemas complejos de la vida real.

El modulo consta de 5 Actividades de Aprendizaje las cuales se detalla a continuacin:

Actividad de Aprendizaje N 01: Computacin basada en modelos naturales.- Aqu en primer lugar se define los modelos de Computacin Bioinspirados, Caractersticas de los modelos Bioinspirados, modelos bioinspirados: Redes Neuronales, Algoritmos evolutivos, optimizacin basada en colonias de hormigas, Particle Swarm Optimization (PSO), Algoritmos Inmunolgicos, Sistema Inmune Artificial, al finalizar los temas se mostrar una conclusin final, luego los alumnos observaran videos y elaboraran 4 conclusiones e investigaran sobre las diferentes aplicaciones que existen sobre modelos naturales.Actividad de Aprendizaje N 02: Optimizacin mediante colonias de hormigas. Aqu el alumno empieza a conocer los algoritmos basados en poblaciones, combinaciones y mutaciones, para ello se necesita una serie de conceptos como: Funcin Maximizar, lenguajes binarios, nmeros aleatorios, probabilidades, cruce, mutacin.Conocer algoritmos de optimizacin como el problema de la mochila donde se ver: Introduccin, descripcin, otras explicaciones sobre el problema de la mochila.Algoritmo de optimizacin sobre el problema del Viajante, al finalizar se dejar un Trabajo sobre los diferentes algoritmos aprendidos.Actividad de Aprendizaje N 03: Heursticas Bioinspiradas basadas en la adaptacin de probabilidades. Aqu el alumno conocer y aplicar tcnicas de optimizacin probabilista y usara trminos como: recombinacin, mutacin, funcin de calidad, algoritmo evolutivo, tipos de seleccin, tipos de Crossover.

El alumno desarrollar un trabajo grupal en aula, donde encontraran a la mejor generacin de un grupo de individuos. Actividad de Aprendizaje N 04: Introduccin y conceptos Bsicos de Algoritmos Genticos. Aqu el alumno aprende a relacionar los conceptos de biologa (Genotipo, Fenotipo, Cromosoma, Gen, Alelo, Funcin de aptitud), con los algoritmos genticos (Cdigo de cadenas, Punto sin codificar, Cadena, Posicin de Cadenas, Valor en una posicin determinada y Valor de la Funcin Objetivo). Luego el alumno realizar un Trabajo de investigacin.

Actividad de aprendizaje n 05: Programacin Gentica. Aqu se programaran diferentes aplicaciones Bioinformticas tomando como referencia lo ledo anteriormente; por Ejemplo el problema del viajante, problemas GPS, la Mochila, problema de Poblaciones etc.INDICE

Pg

Introduccin2

ndice3

Actividad de Aprendizaje N 01: Computacin Basada en Modelos Naturales 5Bioinformtica5

Modelos Naturales5Caractersticas de los Modelos Bioinspirados5Modelos Bioinspirados6Redes Neuronales6Algoritmos Evolutivos7Optimizacin basada en colonias de hormigas7Particle Swarm Optimization (pso) 7Algoritmos Inmunolgicos8Sistemas Inmune Artificial8Ejemplo de una aplicacin 8Conclusin Final de la Actividad de Aprendizaje 0110Trabajo de Investigacin10Actividad de Aprendizaje N 02: Optimizacin Basada En Colonias de Hormigas11Optimizacin Basada En Colonias de Hormigas11Algoritmo Basados en Poblaciones, Combinaciones y Mutaciones11Algoritmo de Optimizacin con Colonia de Hormigas para el Problema de la Mochila13Introduccin al Problema de la Mochila13Descripcin del Problema de la Mochila14Otra Explicacin del Problema de la Mochila15Problemas, Representacin y Funcin de Calidad17Algoritmo de problema del Viajante17Definiciones 17Trabajo Grupal 20Actividad de Aprendizaje N 03: Heursticas Bioinspiradas Basadas en la Adaptacin de Probabilidades21Heursticas Bioinspiradas Basadas en la Adaptacin de Probabilidades21DFD de una Poblacin de Individuos22Un Algoritmo Evolutivo23Tipos de Individuo23Operadores Genticos23El Cruce23Evaluacin de Soluciones24Historia de John Holland 24Algoritmos Genticos Propiamente dicho25Tamao de la Poblacin 25Codificacin de terminacin 25Evaluacin y Seleccin25Basado en el Rango26Rueda de Ruleta, Seleccin de Torneo y Crossover27Crossover de n Puntos y Crossover Uniforme28Crossover Especializados y Mutacin29Trabajo Grupal en el Aula29Actividad de Aprendizaje N 04: Introduccin y Conceptos Bsicos de Algoritmos Genticos31Introduccin y Conceptos Bsicos de Algoritmos Genticos31Cuadro de comparacin en biologa y en algoritmos genticos31Ejemplo Hipottico35Resumen41Espacio de Bsqueda52Problemas NP Completos52Ejemplo Mximo Funcin54Operadores de un Algoritmo Gentico55Operador de Mutacin56Operador de Aceptacin57Parmetros de los AGs57Seleccin58Elitismo61Representaciones de Genotipos61Actividad de aprendizaje n 05: Programacin Gentica63Programacin Gentica63Problema del Viajante63Problema de poblaciones65Problema de la Mochila78Diagramas de Flujo del Problema de la Mochila80Diagramas de Flujo: Solucin 0181Diagramas de Flujo Solucin 0282Diagramas de Flujo Solucin 0384Aplicacin del Problema de la Mochila (Ventanas)92Codificacin del Problema de la Mochila94Bibliografa102Actividad de Aprendizaje N 01

Computacin Basada en Modelos NaturalesObjetivos: Definir modelos de Computacin Bioinspirados.

Conocer las caractersticas de los modelos Bioinspirados.

Investigar sobre las diferentes aplicaciones que existen sobre modelos naturales.

Contenidos:Modelos de Computacin Bioinspirados.

Caractersticas de los Modelos Bioinspirados. Aplicaciones sobre Modelos Naturales.BIOINFORMTICA

Bioinformtica es una disciplina cientfica emergente que utiliza tecnologa de la informacin para organizar, analizar y distribuir informacin con la ayuda de la biolgica y poder solucionar problemas complejos de la vida real.

Bioinformtica es un rea de investigacin multidisciplinaria, la cual puede ser ampliamente definida como la interface entre dos ciencias: Biologa y Computacin y est impulsada por la incgnita del genoma humano y la promesa de una nueva era en la cual la investigacin genmica puede ayudar dramticamente a mejorar la condicin y calidad de vida humana.

MODELOS NATURALES

COMPUTACIN BASADA EN MODELOS NATURALES

CONCEPTO DE MODELOS DE COMPUTACIN BIOINSPIRADOS

Se basa en emplear analogas con sistemas naturales o sociales para la resolucin de problemas.

Los algoritmos bioinspirados simulan el comportamiento de sistemas naturales para el diseo de mtodos heursticos no determinanticos de bsqueda /aprendizaje/comportamiento.

CARACTERSTICAS DE LOS MODELOS BIOINSPIRADOS

Modelan (de forma aproximada) un fenmeno existente en la naturaleza. Metfora biolgica.

Son no determinsticos: Es decir un algoritmo no determinstico es un algoritmo que con la misma entrada ofrece muchos posibles resultados. No se puede saber de antemano cul ser el resultado de la ejecucin de un algoritmo no determinstico.

A menudo presentan, implcitamente, una estructura paralela (mltiples agentes).

Son adaptativos (utilizan realimentacin con el entorno para modificar el modelo y los parmetros).

MODELOS BIOINSPIRADOS

A) REDES NEURONALES: Basados en la simulacin del comportamiento del Sistema Nervioso

Paradigma de Aprendizaje Automtico

B) ALGORITMOS EVOLUTIVOS: Basados en los principios Darwinianos de Evolucin Natural.

C) OPTIMIZACIN BASADA EN COLONIAS DE HORMIGAS: Basados en la simulacin del comportamiento de las colonias de hormigas cuando recogen comida.

D) PARTICLE SWARM OPTIMIZATION (PSO): Es una tcnica de optimizacin inspirada en el comportamiento social de bandadas de aves o peces.

E) ALGORITMOS INMUNOLGICOS: Basados en la simulacin del comportamiento del sistema inmunolgico (El sistema inmunolgico es la defensa natural del cuerpo contra las infecciones).

F) SISTEMAS INMUNE ARTIFICIAL: Los sistemas inmunes artificiales son sistemas adaptativos, inspirados por teora de la inmunologa y funciones, principios y modelos observados en el sistema inmune, los cuales son aplicados para solucionar problemas.

EJEMPLO DE UNA APLICACIN

Problema de Registrado de Imgenes

Problema: Se define el registrado entre dos imgenes (I1, I2) como una aplicacin que pone en correspondencia dichas imgenes.

Se considera que existe una transformacin espacial f implcita entre ambas:

I2(x,y,z) = I1(f(x,y,z))

Desarrollos: Obtencin los parmetros que definen la transformacin geomtrica que ha sufrido una imagen 2D o 3D empleando algoritmos evolutivos y metaheursticas(es un mtodo heurstico para resolver un tipo de problema computacional general, usando los parmetros dados por el usuario sobre unos procedimientos genricos y abstractos de una manera que se espera eficiente).

Aplicaciones: Reconocimiento de objetos, medicina, teledeteccin, etc.

CONCLUSION FINAL DE LA ACTIVIDAD DE APRENDIZAJE 01

TRABAJO DE INVESTIGACIN1. Observar el Video y elaborar 4 conclusiones finales.

2. investigaran sobre las diferentes aplicaciones que existen sobre modelos naturales.Actividad de Aprendizaje N 02Optimizacin Basada en Colonias de Hormigas

Objetivos:

Conocer los algoritmos basados en poblaciones y mutaciones.

Interpretar conceptos basados en poblaciones. Conocer los algoritmos basados en optimizacin.

Contenidos:

Optimizacin mediante colonias de hormigas.Algoritmos basados en poblaciones, combinaciones y mutaciones.

Definicin e concepto como: Funcin Maximizar, lenguajes binarios, nmeros aleatorios, probabilidades, cruce, mutacin.

Definicin de Algoritmos de optimizacin como el problema de la mochila y el problema del Viajante.

Trabajo sobre los diferentes algoritmos aprendidos.

OPTIMIZACIN BASADA EN COLONIAS DE HORMIGAS

Un algoritmo es una lista ordenada de operaciones necesarias para obtener la solucin a un problema. En consistencia con las tcnicas de optimizacin (heursticas y metaheursticas), se distinguen los algoritmos exactos (aquellos que pretenden un ptimo global), y los algoritmos aproximados (que buscan una solucin de alta calidad, aunque no necesariamente la ptima). Las tcnicas metaheursticas utilizan conceptos de campos diversos como la gentica, la biologa, las matemticas, la fsica o la neurologa, entre otros. Una de la recientes, es la Optimizacin basada en Colonias de hormigas (Ant Colony Optimization, ACO en ingls).

Colonia de Hormigas en un Ambiente Paralelo Asncrono

ALGORITMO BASADOS EN POBLACIONES, COMBINACIONES Y MUTACIONES.

Se eligi aleatoriamente x=13 luego 24,8 y 19.

Generar una poblacin intermedia. Para ello asignar a cada individuo una probabilidad de ser seleccionado directamente proporcional a su funcin de calidad.

De la poblacin intermedia se seleccionan parejas de forma aleatoria.

Cruce: elegir un punto intermedio e intercambiar los genes de los padres a partir de ese punto.

Mutacin: cambio de un bit elegido aleatoriamente (probabilidad pequea).

ACHPM: ALGORITMO DE OPTIMIZACIN CON COLONIA DE HORMIGAS PARA EL PROBLEMA DE LA MOCHILASe presenta un algoritmo de optimizacin para resolver el problema de la mochila el cual se encuentra clasificado entre los NP-Duros dentro de la teora de la complejidad, el algoritmo desarrollado utiliza colonias de hormigas la cual es una tcnica relativamente nueva que ha tenido bastante aceptacin en los ltimos aos, para probar este algoritmo se diseo un formato para obtener los datos del problema el cual se muestra en este trabajo, este formato fue implementado en archivos de texto a travs del cual se capturan las instancias del problema para realizar las pruebas del diseo de experimento, se mencionan algunos de los trabajos relacionados con algoritmos de Optimizacin con Colonias de Hormigas para el problema del la Mochila Multidimencional, as como los resultados obtenidos por el algoritmo en el diseo de experimentos.

Palabras Claves: Problema de la Mochila, Optimizacin con Colonia de Hormigas, Problemas NP-Duros

INTRODUCCIN AL PROBLEMA DE LA MOCHILA

El Problema de la Mochila (PM) es un problema NP- Duro el cual tiene diversas aplicaciones prcticas como son: la asignacin de procesos en sistemas distribuidos, el presupuesto de capital, entre otras.

El objetivo del problema de la mochila es encontrar un subconjunto de objetos con el cual se maximice el beneficio o utilidad que proporcionan los objetos mientras que satisface la restriccin de no sobrepasar la capacidad (espacio o peso) de un contenedor o depsito (en este caso la mochila) donde sern colocados los objetos.

Actualmente existe un gran inters en implementar nuevas tcnicas de optimizacin como son la meta-heurstica (Algoritmos genricos que pueden ser implementados para resolver diferentes problemas de optimizacin a travs de variaciones mnimas).

Los Algoritmos de Optimizacin de Colonia de Hormigas son una meta-heurstica bio-inspirada basada en el comportamiento de las hormigas naturales, en la forma de como estas establecen el camino ms corto entre el hormiguero y su fuente de alimentos a travs de una sustancia denominada feromona.

Esta tcnica es realmente un sistema multiagentes en la cual cada agente (hormiga), construye una solucin candidata. La construccin de la solucin por parte de una hormiga es guiada por una informacin heurstica que depende del problema y por los rastros de feromonas que se encuentran depositados en los caminos.

Alaya, Solnon, y Ghdira en el 2004 [1] implementaron un algoritmo de optimizacin con colonias de hormigas para resolver el problema de la mochila multidimencional el cual es el algoritmo ms reciente.

DESCRIPCION DEL PROBLEMA DE LA MOCHILA

El Problema de la Mochila consiste en, dado un conjunto de objetos los cuales tienen un peso y un beneficio utilidad, se desea encontrar un subconjunto de objetos que maximice el beneficio utilidad total de los objetos seleccionados sin sobrepasar la capacidad de la mochila (Contenedor deposito) ver figura 1, el objetivo de problema puede representarse formalmente a travs de frmula 1 que se muestra a continuacin.

Donde pj es el beneficio de seleccionar el objeto j, xj vale 1 si elemento j existe en la solucin, rij es el espacio que ocupa el objeto, la sumatoria del peso de los objetos seleccionados debe ser menor o igual a la capacidad de la mochila C.

El problema de la mochila puede ser tratado tambin como un problema multiojetivo debido a que por un lado se debe Maximizar la utilidad de los objetos y por el otro minimizar el peso de los objetos para no sobrepasar la capacidad de la mochila.

En este caso el problema se trata a travs de una funcin agregativa en la cual se tomo en cuenta el peso y la utilidad dentro de la funcin para obtener la solucin.

Figura 1. Seleccin de un subconjunto de objetosOTRA EXPLICACION DEL PROBLEMA DE LA MOCHILARecordar.

Se tienen n objetos y una mochila

El objeto i tiene peso pi y la inclusin del objeto i en la mochila produce un beneficio b i.

El objetivo es llenar la mochila, de capacidad C, de manera que se maximice el beneficio.

Problemas:

Codificacin gentica: cmo representar las soluciones

Calidad de las soluciones: cmo se mide.

Representacin:

Funcin de calidad:

Penalizar la no factibilidad. Obliga al algoritmo a elegir soluciones factibles porque son mejores.

Inicializacin:

Generar secuencias de ceros y unos.

Operador de cruce de un punto.

Otra posible representacin:

Una lista con los elementos que metemos en la mochila.

Problema: qu operador de cruce utilizamos?

Observar que el operador de un punto no sirve, es necesario adaptarlo.

Por ejemplo, eliminar los elementos repetidos.

Hay m recursos de capacidades c1,c2,,cm y n tareas a ejecutar que consumen parte de los recursos.

La tarea i-sima consume wij partes del recurso j.

La ejecucin de la tarea i-sima produce un beneficio bi.

Se trata de decidir qu tareas se ejecutan de manera que se maximice el beneficio total.

Representacin de un individuo:

La funcin de calidad:

Resultados obtenidos tras 100 ejecuciones de 6 casos distintos:

ALGORITMO: EL PROBLEMA DEL VIAJANTE

El problema del viajante

Recordar

Encontrar un recorrido de longitud mnima para un viajante que tiene que visitar varias ciudades y volver al punto de partida, conocida la distancia existente entre cada dos ciudades.

Codificacin: en forma de vector siguiendo el orden del recorrido

Ejemplo:

DEFINICIONES

Cruce:

De un punto:

Pueden aparecer ciudades repetidas

No siempre visitamos todas.

Heurstica:

Elegir una ciudad , i, aleatoriamente.

Suponer que en el padre 1 de la ciudad i vamos a la j y en el padre 2 de i vamos a k.

Si j,k ya estn incluidos, elegir una nueva ciudad.

Si no, aadir la ciudad que no est incluida ms prxima a i.

Repetir mientras queden ciudades sin recorrer.

Otra codificacin:

Asignar a cada ciudad un valor entre 0 y 1 aleatoriamente. El recorrido se obtiene al ordenar estos nmeros de mayor a menor.

Ejemplo:

Cruce:

Cualquiera de los habituales, de un punto por ejemplo.

Variantes del esquema bsico

Codificacin: cmo se representan las soluciones en forma de cromosomas?

Cadenas de 0s y 1s (algoritmos clsicos)

Nmeros enteros y reales

Otros

Cuestiones a tener en cuenta:

Factibilidad: los cromosomas pueden codificar soluciones no factibles del problema.

Solucin: penalizar en la funcin de calidad descartar reparar.

Legalidad: los cromosomas pueden no ser decodificables a una solucin.

Ejemplo: problema de la mochila

Unicidad de la codificacin:

Uno a uno

Uno a N

N a uno

Cambio de generacin:

Manteniendo el tamao de la poblacin

Reemplazar padres por hijos

Reemplazar un par de individuos elegidos aleatoriamente por los hijos

Otros

Aumentando el tamao de la poblacin

Crear una poblacin temporal formada por los padres y los hijos y seleccionar de ah los mejores para formar la nueva generacin

Dados n padres generar m hijos (m>n) y de ah seleccionar los n mejores.

Seleccin:

Asignar a cada individuo una probabilidad de ser elegido definida como

Donde f puede ser:

La funcin de calidad (quizs escalada o centrada)

La posicin de la solucin si se ordenan segn su calidad

Cruce

De un punto: seleccionar aleatoriamente un punto en el cromosoma e intercambiar el final de cada cromosoma a partir de dicho punto.

De dos puntos:

Uniforme: cada gen se hereda de un padre elegido aleatoriamente.

Mutacin

Evita que solo se considere un subconjunto de las posibles soluciones.

Por qu funciona?

Un esquema es el conjunto de cromosomas que siguen un patrn.

Ejemplo:

00*1*0={000100, 000110, 001100, 001110}

Teorema del esquema:

Relaciona la calidad de los miembros de un esquema en una generacin con

el nmero esperado de miembros en la siguiente generacin.

= Ns(g)* ms(g)/m(g)

Ns(g) es el nmero de elementos del esquema s en la generacin g.

m(g) la calidad media de los cromosomas en la generacin g

ms(g) una estimacin de la calidad media de los cromosomas de la generacin s que pertenecen al esquema s.

es el valor esperado.

Observaciones:

La evolucin est dirigida por la calidad relativa

Existe un paralelismo implcito, las operaciones se hacen implcitamente sobre todo un esquema.

Encontrar un equilibrio entre explotacin/exploracin.

Los algoritmos genticos funcionan mejor cuando:

Las soluciones potenciales pueden representarse de forma que quede explcita la composicin.

Existen operadores para mutar y recombinar estas representaciones.

Los algoritmos genticos funcionan peor cuando:

La representacin no recoge las caractersticas de las soluciones

Los operadores no generan candidatos interesantes

TRABAJO GRUPAL (GRUPOS DE 05 INTEGRANTES)1. Crear Diagramas de Flujo de Datos de cada Algoritmo aprendido.

Actividad de Aprendizaje N 03

Heursticas Bioinspiradas Basadas en la Adaptacin de Probabilidades

Objetivos:

Aplicar tcnicas de optimizacin probabilstica. Usar trminos de optimizacin probabilstica. Determinar la mejor generacin para un grupo de individuos.Contenidos:

Heursticas Bioinspiradas basadas en la adaptacin de probabilidades.Tcnicas de optimizacin probabilista.

Recombinacin, mutacin, funcin de calidad, algoritmo evolutivo.

Tipos de seleccin, tipos de Crossover.

Trabajo grupal en aula, donde encontraran a la mejor generacin de un grupo de individuos.

ALGORITMO BASADO EN LA OPTIMIZACIN MEDIANTE COLONIAS DE HORMIGAS PARA LA RESOLUCIN DEL PROBLEMA DEL TRANSPORTE DE CARGA DESDE VARIOS ORGENES A VARIOS DESTINOS

HEURSTICAS BIOINSPIRADAS BASADAS EN LA ADAPTACIN DE PROBABILIDADES.

Es su modelo basada en la evolucin de poblaciones. En este caso, las poblaciones representan soluciones completas a un problema, que generacionalmente evolucionaran por medio de tcnicas de optimizacin probabilstica hacia la mejor de las soluciones.

Siguiendo con la metfora, los individuos de la poblacin deben tener la capacidad de reproducirse de modo que sus descendientes presenten alguna variedad respecto a ellos, pues en esta diferencia puede encontrarse la mejora.

La variedad se presenta tras la recombinacin y/o mutacin del cdigo gentico de padres a hijos y la poblacin evoluciona gracias al reemplazamiento y seleccin de los nuevos padres segn criterios de adaptacin.

En este contexto, entendemos que cada individuo de la poblacin representa una solucin, que la calidad de la solucin ser equivalente (depender) de la capacidad de adaptacin del individuo al entorno, y de que el entorno viene representado por el problema para el que buscamos solucin.

DFD de una poblacin de individuos

Como se puede observar en la Figura, el proceso se inicia con la generacin aleatoria de una poblacin de individuos cada uno de los cuales representa una solucin factible al problema que se desea resolver. En funcin de la bondad de la solucin que representa cada individuo, se le asigna una valoracin que en definitiva establece el grado de efectividad del individuo para competir por unos determinados recursos. Cuanto mayor sea la adaptacin de un individuo mayor ser la probabilidad de que dicho individuo sea seleccionado para reproducirse y, en consecuencia, para que su material gentico se propague en sucesivas generaciones.

El proceso de reproduccin se realiza cruzando el material gentico del individuo con el de otro individuo seleccionado de igual forma, generando una nueva poblacin que reemplaza a la anterior con la ventaja de que esta poblacin contiene una mayor proporcin de buenas caractersticas que la poblacin anterior. A travs de sucesivas generaciones las nuevas poblaciones estarn mejor adaptadas que las poblaciones de las que provienen sin ms que favorecer el cruce de los individuos con mejores caractersticas, ya que de esta forma se van explorando las reas ms prometedoras del espacio de bsqueda.

Adicionalmente tambin es posible someter a la poblacin de individuos (soluciones) al proceso de mutacin, con la finalidad de potenciar que ningn punto del espacio de bsqueda tenga probabilidad cero de ser examinado. Los principios bsicos del funcionamiento de los AGs fueron propuestos por Holland en 1975.

Un Algoritmo Evolutivo

Tipos de individuo

Mientras que un algoritmo gentico simple utiliza individuos que codifican las variables

Como cadenas binarias, otros tipos de algoritmos evolutivos pueden utilizar estructuras complejas como vectores de nmeros reales, redes neuronales, grafos, rboles, etc.

En cada caso se debe elegir una representacin que se adapte convenientemente al problema.

Operadores genticos

En la Evolucin, una mutacin es un suceso bastante poco comn (sucede aproximadamente una de cada mil replicaciones). En la mayora de los casos las mutaciones son letales, pero en promedio, contribuyen a la diversidad gentica de la especie. En un algoritmo gentico tendrn el mismo papel, y la misma frecuencia (es decir, muy baja).

Una vez establecida la frecuencia de mutacin, por ejemplo, uno por mil, se examina cada bit de cada cadena cuando se vaya a crear la nueva criatura a partir de sus padres.

Si un nmero generado aleatoriamente est por debajo de esa probabilidad, se cambiar

el bit (es decir, de 0 a 1 o de 1 a 0). Si no, se dejar como est.

No conviene abusar de la mutacin. Es cierto que es un mecanismo generador de diversidad, y, por tanto, la solucin cuando un algoritmo gentico est estancado, pero tambin es cierto que reduce el algoritmo gentico a una bsqueda aleatoria. Siempre es ms conveniente usar otros mecanismos de generacin de diversidad, como aumentar el tamao de la poblacin, o garantizar la aleatoriedad de la poblacin inicial.

El cruce consiste en el intercambio de material gentico entre dos cromosomas. Es el principal operador gentico, hasta el punto que se puede decir que no es un algoritmo gentico si no tiene cruce, y, sin embargo, puede serlo perfectamente sin mutacin.

Para aplicar el cruce se escogen aleatoriamente dos miembros de la poblacin, los dos cromosomas se cortan por N puntos, y el material gentico situado entre ellos se intercambia. Lo ms habitual es un cruce de un punto o de dos puntos.

El cruce es el encargado de mezclar bloques buenos que se encuentren en los diversos Progenitores, y que sern los que den a los mismos una buena puntuacin. La presin selectiva se encarga de que slo los buenos bloques se perpeten, y poco a poco vayan formando una buena solucin.

Evaluacin de las soluciones

Durante la evaluacin, se decodifica el gen, convirtindose en una serie de parmetros de un problema, se halla la solucin del problema a partir de esos parmetros, y se le da una puntuacin a esa solucin en funcin de lo cerca que est de la mejor solucin. A esta puntuacin se le llama fitness.

El fitness determina siempre los cromosomas que se van a reproducir, y aquellos que se van a eliminar, pero hay varias formas de considerarlo para seleccionar la poblacin de la siguiente generacin.

Historia de John HollandLos algoritmos genticos (AG), fueron inventados en 1975 por John Holland, de la Universidad de Michigan. Los AG son, simplificando, algoritmos de optimizacin, es decir, tratan de encontrar la mejor solucin a un problema dado entre un conjunto de soluciones posibles. Los mecanismos de los que se valen los AG para llevar a cabo esa bsqueda pueden verse como una metfora de los procesos de evolucin biolgica.

John Holland desde pequeo, se preguntaba cmo logra la naturaleza, crear seres cada vez ms perfectos. No saba la respuesta, pero tena una cierta idea de como hallarla: tratando de hacer pequeos modelos de la naturaleza, que tuvieran alguna de sus caractersticas, y ver cmo funcionaban, para luego extrapolar sus conclusiones a la totalidad.

Fue a principios de los 60, en la Universidad de Michigan en Ann Arbor, donde, dentro del grupo Logic of Computers, sus ideas comenzaron a desarrollarse y a dar frutos. Y fue, adems, leyendo un libro escrito por un bilogo evolucionista, R. A. Fisher, titulado La teora gentica de la seleccin natural, como comenz a descubrir los medios de llevar a cabo sus propsitos de comprensin de la naturaleza.

De ese libro aprendi que la evolucin era una forma de adaptacin ms potente que el simple aprendizaje, y tom la decisin de aplicar estas ideas para desarrollar programas bien adaptados para un fin determinado.

En esa universidad, Holland imparta un curso titulado Teora de sistemas adaptativos. Dentro de este curso, y con una participacin activa por parte de sus estudiantes, fue donde se crearon las ideas que ms tarde se convertiran en los AG.

Por tanto, cuando Holland se enfrent a los AG, los objetivos de su investigacin fueron dos:

- Imitar los procesos adaptativos de los sistemas naturales.

- Disear sistemas artificiales (normalmente programas) que retengan los mecanismos importantes de los sistemas naturales.

El cruceOpera sobre las cadenas de los genotipos de cada pareja de las soluciones elegidas como progenitores. El sistema mediante el cual se obtienen nuevas soluciones a partir las precedentes, es decir lo que se llama el operador de cruzamiento, puede ser distinto segn las tcnicas especficas empleadas. El que se describe en el punto siguiente es uno de los ms generalizados.

Algoritmo gentico propiamente dichoPara comenzar la competicin, se generan aleatoriamente una serie de cromosomas. El algoritmo gentico procede de la forma siguiente: Cada uno de los pasos consiste en una actuacin sobre las cadenas de bits, es decir, la aplicacin de un operador a una cadena binaria. Se les denominan, por razones obvias, operadores genticos, y hay tres principales: seleccin, crossover o recombinacin y mutacin; aparte de otros operadores genticos no tan comunes, todos ellos se vern a continuacin.Un algoritmo gentico tiene tambin una serie de parmetros que se tienen que fijar para cada ejecucin, como los siguientes:

Tamao de la poblacinDebe de ser suficiente para garantizar la diversidad de las soluciones, y, adems, tiene que crecer ms o menos con el nmero de bits del cromosoma, aunque nadie ha aclarado cmo tiene que hacerlo. Por supuesto, depende tambin del ordenador en el que se est ejecutando.

Condicin de terminacinLo ms habitual es que la condicin de terminacin sea la convergencia del algoritmo gentico o un nmero prefijado de generaciones.

Evaluacin y seleccinDurante la evaluacin, se decodifica el gen, convirtindose en una serie de parmetros de un problema, se halla la solucin del problema a partir de esos parmetros, y se le da una puntuacin a esa solucin en funcin de lo cerca que est de la mejor solucin. A esta puntuacin se le llama fitness.

Por ejemplo, supongamos que queremos hallar el mximo de la funcin f(x), una parbola invertida con el mximo en x=1. En este caso, el nico parmetro del problema es la variable x. La optimizacin consiste en hallar un x tal que F(x) sea mximo. Crearemos, pues, una poblacin de cromosomas, cada uno de los cuales contiene una codificacin binaria del parmetro x. Lo haremos de la forma siguiente: cada byte, cuyo valor est comprendido entre 0 y 255, se transformar para ajustarse al intervalo [-1,1], donde queremos hallar el mximo de la funcin.

Valor binarioDecodificacinEvaluacin f(x)

10010100210,9559

10010001190,9639

101001-860,2604

1000101-580,6636

El fitness determina siempre los cromosomas que se van a reproducir, y aquellos que se van a eliminar, pero hay varias formas de considerarlo para seleccionar la poblacin de la siguiente generacin:

Usar el orden, o rango, y hacer depender la probabilidad de permanencia o evaluacin de la posicin en el orden.

Aplicar una operacin al fitness para escalarlo.

En algunos casos, el fitness no es una sola cantidad, sino diversos nmeros, que tienen diferente consideracin. Basta con que tal fitness forme un orden parcial, es decir, que se puedan comparar dos individuos y decir cul de ellos es mejor. Esto suele suceder cuando se necesitan optimizar varios objetivos.

Una vez evaluado el fitness, se tiene que crear la nueva poblacin teniendo en cuenta que los buenos rasgos de los mejores se transmitan a sta. Para ello, hay que seleccionar a una serie de individuos encargados de tan ardua tarea. Y esta seleccin, y la consiguiente reproduccin, se puede hacer de diferentes formas:

Basado en el RangoEn este esquema se mantiene un porcentaje de la poblacin, generalmente la mayora, para la siguiente generacin. Se coloca toda la poblacin por orden de fitness, y los M menos dignos son eliminados y sustituidos por la descendencia de alguno de los M mejores con algn otro individuo de la poblacin.

A este esquema se le pueden aplicar otros criterios; por ejemplo, se crea la descendencia de uno de los paladines/amazonas, y esta sustituye al ms parecido entre los perdedores. Esto se denomina crowding, y fue introducido por DeJong. Una variante de este es el muestreado estocstico universal, que trata de evitar que los individuos con ms fitness copen la poblacin dando ms posibilidades al resto de la poblacin; de esta forma, la distribucin estadstica de descendientes en la nueva poblacin es ms parecida a la real. Rueda de Ruleta Se crea un conjunto gentico formado por cromosomas de la generacin actual, en una cantidad proporcional a su fitness. Si la proporcin hace que un individuo domine la poblacin, se le aplica alguna operacin de escalado. Dentro de este conjunto, se cogen parejas aleatorias de cromosomas y se emparejan, sin importar incluso que sean del mismo progenitor (para eso estn otros operadores, como la mutacin). Hay otras variantes: por ejemplo, en la nueva generacin se puede incluir el mejor representante de la generacin actual. En este caso, se denomina mtodo elitista.

Seleccin de torneo Se escogen aleatoriamente un nmero T de individuos de la poblacin, y el que tiene puntuacin mayor se reproduce, sustituyendo su descendencia al que tiene menor puntuacin.

CrossoverConsiste en el intercambio de material gentico entre dos cromosomas (a veces ms, como el operador orga propuesto por Eiben et al.). El crossover es el principal operador gentico, hasta el punto que se puede decir que no es un algoritmo gentico si no tiene crossover, y, sin embargo, puede serlo perfectamente sin mutacin, segn descubri Holland. El teorema de los esquemas confa en l para hallar la mejor solucin a un problema, combinando soluciones parciales.

Para aplicar el crossover, entrecruzamiento o recombinacin, se escogen aleatoriamente dos miembros de la poblacin. No pasa nada si se emparejan dos descendiente de los mismos padres; ello garantiza la perpetuacin de un individuo con buena puntuacin (y, adems, algo parecido ocurre en la realidad; es una prctica utilizada, por ejemplo, en la cra de ganado, llamada inbreeding, y destinada a potenciar ciertas caractersticas frente a otras). Sin embargo, si esto sucede demasiado a menudo, puede crear problemas: toda la poblacin puede aparecer dominada por los descendientes de algn gen, que, adems, puede tener caracteres no deseados. Esto se suele denominar en otros mtodos de optimizacin atranque en un mnimo local, y es uno de los principales problemas con los que se enfrentan los que aplican algoritmos genticos.

En cuanto al teorema de los esquemas, se basa en la nocin de bloques de construccin. Una buena solucin a un problema est constituida por unos buenos bloques, igual que una buena mquina est hecha por buenas piezas. El crossover es el encargado de mezclar bloques buenos que se encuentren en los diversos progenitores, y que sern los que den a los mismos una buena puntuacin. La presin selectiva se encarga de que slo los buenos bloques se perpeten, y poco a poco vayan formando una buena solucin. El teorema de los esquemas viene a decir que la cantidad de buenos bloques se va incrementando con el tiempo de ejecucin de un algoritmo gentico, y es el resultado terico ms importante en algoritmos genticos.

El intercambio gentico se puede llevar a cabo de muchas formas, pero hay dos grupos principales

Crossover n-puntosLos dos cromosomas se cortan por n puntos, y el material gentico situado entre ellos se intercambia. Lo ms habitual es un crossover de un punto o de dos puntos. Padre

00010101010101

Madre

10111001110111

Hijo

00010001110101

Crossover uniforme

Se genera un patrn aleatorio de 1s y 0s, y se intercambian los bits de los dos cromosomas que coincidan donde hay un 1 en el patrn. O bien se genera un nmero aleatorio para cada bit, y si supera una determinada probabilidad se intercambia ese bit entre los dos cromosomas.

Padre

00010101010101

Madre

10111001110111

Hijo

00110001110111

Crossover especializadosEn algunos problemas, aplicar aleatoriamente el crossover da lugar a cromosomas que codifican soluciones invlidas; en este caso hay que aplicar el crossover de forma que genere siempre soluciones vlidas. Un ejemplo de estos son los operadores de crossover usados en el problema del viajante.

Mutacin

En la Evolucin, una mutacin es un suceso bastante poco comn (sucede aproximadamente una de cada mil replicaciones), como ya se ha visto anteriormente. En la mayora de los casos las mutaciones son letales, pero en promedio, contribuyen a la diversidad gentica de la especie. En un algoritmo gentico tendrn el mismo papel, y la misma frecuencia (es decir, muy baja).

Una vez establecida la frecuencia de mutacin, por ejemplo, uno por mil, se examina cada bit de cada cadena cuando se vaya a crear la nueva criatura a partir de sus padres (normalmente se hace de forma simultnea al crossover). Si un nmero generado aleatoriamente est por debajo de esa probabilidad, se cambiar el bit (es decir, de 0 a 1 o de 1 a 0). Si no, se dejar como est. Dependiendo del nmero de individuos que haya y del nmero de bits por individuo, puede resultar que las mutaciones sean extremadamente raras en una sola generacin.

No hace falta decir que no conviene abusar de la mutacin. Es cierto que es un mecanismo generador de diversidad, y, por tanto, la solucin cuando un algoritmo gentico est estancado, pero tambin es cierto que reduce el algoritmo gentico a una bsqueda aleatoria. Siempre es ms conveniente usar otros mecanismos de generacin de diversidad, como aumentar el tamao de la poblacin, o garantizar la aleatoriedad de la poblacin inicial.TRABAJO GRUPAL EN EL AULA1. Leer el Enunciado: A continuacin se comienza con una poblacin de soluciones posibles, que pueden ser generadas al azar o mediante algn mtodo que produzca soluciones relativamente satisfactorias. A partir de este punto inicial, el algoritmo procede por etapas que ejecutan los pasos elementales siguientes:

Se evalan todas las soluciones de la poblacin, con el fin de otorgar ms probabilidades de emparejamiento a las ms satisfactorias.

Mediante un mecanismo de azar, aunque dando ms oportunidades a las mejor evaluadas, se eligen las soluciones que han de cruzarse entre s para dar lugar a descendencia. 2. Para nuestra poblacin, Indicar 5 caractersticas de cada individuo del aula de Bioinformtica (caractersticas sobre rendimiento acadmico positivo).

3. Para nuestra poblacin del aula de Bioinformtica, seleccionar una serie de individuos encargados para una ardua tarea Cientfica. (seleccin de la muestra = 4).

4. Emplear las tcnicas ledas y lo tratado en la pgina 11 y 12, considerando la probabilidad para la seleccin.

5. Determinar la funcin de calidad.

6. Determinar los FITNESS.(proceso de seleccin de la evaluacin y seleccin)

7. Determinar el CROSSOVER(un punto, dos puntos, N puntos).

8. Determinar el tipo de seleccin escogida.(Basado en el rango, Rueda de ruleta, seleccin de torneo)

9. Generar Cruce

10. Generar la MutacinEjemplo:

Seleccin de la muestra = 4

Actividad de Aprendizaje N 04

Introduccin y Conceptos Bsicos de Algoritmos Genticos

Objetivos:

Introducir conceptos bsicos de Algoritmos Genticos. Relacionar los conceptos de Biologa con los algoritmos Genticos. Realizar trabajos de Investigacin.Contenidos:

Introduccin y conceptos Bsicos de Algoritmos Genticos.Definiciones - Biologa: Genotipo, Fenotipo, Cromosoma, Gen, Alelo, Funcin de aptitud.

Definiciones - Algoritmos genticos: Cdigo de cadenas, Punto sin codificar, Cadena, Posicin de Cadenas, Valor en una posicin determinada y Valor de la Funcin Objetivo.

Trabajo de investigacin.

CONCEPTOS DE ALGORITMOS Y PROGRAMACION GENETICA.

INTRODUCCIN Y CONCEPTOS BSICOS DE ALGORITMOS GENTICOS.

Conceptos bsicos en biologa y en algoritmos genticos

En esta seccin explicamos el significado que tienen en los algoritmos genticos una serie de conceptos clave en biologa. A continuacin se definen una serie de trminos con los que conviene estar familiarizados: genotipo, fenotipo, cromosoma, etc. Cuadro de comparacin en biologa y en algoritmos genticos

Evolucin NaturalAlgoritmo Gentico

GenotipoCdigo de cadenas

FenotipoPunto sin codificar

CromosomaCadena

GenPosicin de Cadenas

AleloValor en una posicin determinada

Funcin de aptitudValor de la Funcin Objetivo

Genoma

El genoma es la totalidad de la informacin gentica que posee un organismo en particular.

Es como un manual de instruccin. Contiene todas las instrucciones especficas que se utilizan para construir un organismo vivo.

Todas las especies tienen su propio genoma. Una copia de su genoma se encuentra en casi cada clula de su cuerpo.

Un genoma se divide en cromosomas. Cromosomas son como paquetes que guardan los genes y los mantienen organizados. Los genes se componen de ADN. ADN contiene informacin importante sobre cada cosa viva.

Una copia de su genoma se encuentra en casi cada clula de su cuerpo. En cada una de estas clulas hay un ncleo. En los humanos, cada ncleo contiene tpicamente dos genomas combinados. Uno de su madre y uno de su padre. Tpicamente, cada humano tiene 23 pares de cromosomas. Dentro de los 23 pares de cromosomas en humanos, hay una combinacin de 20.000 a 25.000 genes. En el genoma humano hay alrededor de 3 mil millones de bases de ADN.

Todas las especies tienen su propio genoma. Hay un genoma de Todas las especies tienen su propio genoma. Una copia de su genoma se encuentra en casi cada clula de su cuerpo. Un genoma se divide en cromosomas. Cromosomas son como paquetes que guardan los genes y los mantienen organizados. Los genes se componen de ADN. ADN contiene informacin importante sobre cada cosa viva.

Genotipo

El genotipo es el contenido genoma especfico de un individuo, en forma de ADN. Junto con la variacin ambiental que influye sobre el individuo.

Toda la informacin contenida en los cromosomas se conoce como genotipo.

El fenotipo se refiere a la expresin del genotipo ms la influencia del medio.

Cromosoma

Cromosomas cadena de bits

Los cromosomas son los portadores de la mayor parte del material gentico y condicionan la organizacin de la vida y las caractersticas hereditarias de cada especie.

Gen

Un gen es un segmento corto de ADN, que le dice al cuerpo cmo producir una protena especfica. Hay aproximadamente 30.000 genes en cada clula del cuerpo humano y la combinacin de todos los genes constituye el material hereditario para el cuerpo humano y sus funciones.

La composicin gentica de una persona se llama genotipo

AleloUn alelo es un valor para un gen. Utilizando la definicin de gen que hace referencia a una porcin de cadena gentica determinada, los alelos de ese gen seran todos los posibles valores que puede tomar ese segmento de cadena gentica.

Definicin tcnica de un alelo - Es la forma alternativa de un lugar gentico; un solo alelo se hereda de cada progenitor (e.g., el lugar para el color del ojo el alelo puede resultar en ojos azules o marrones).

Pensemos que un gen es como como una pgina de un libro. En esta pgina imagine que existen las instrucciones completas para fabricar un producto. Imaginemos tambin que todos los individuos de una especie tienen esta pgina en su 'biblioteca genetica' (genoma). De un individuo a otro puede haber pequeas diferencias en las letras que aparecen en estas pginas dadas. Pensemos, por ejemplo, que hay 99 letras en la pgina. Todas las letras pueden ser iguales de una pgina de un individuo a otro. Pero, puede haber una, o unas pocas letras, en la pagina que pueden ser diferentes de un individuo a otro. Esta variacin se llama un alelo.

Si las pginas tienen letras diferentes, pero estas letras tienen la misma posicin en los libros de una biblioteca a otra (en las mismos especies), entonces esas pginas se llaman alleles. y, si dos personas tienen pginas que son exactamente iguales ellas dos tienen el mismo allele. Si hay una pequea diferencia en la pgina de dos individuos, tienen entonces alelos diferentes. Esos pequeos cambios en la pagina pueden o no pueden influenciar lo que finalmente se produce en las instrucciones en la pgina. En algunos casos esas diferencias pueden tener un gran efecto en el organismo. Por ejemplo, alleles pueden influenciar el color del pelo de los conejos (vase abajo) o el color de una flor.

Ejemplo Hipottico

Los conejos tienen tpicamente dos copias de las mismas pginas (genes) en su biblioteca. Organismos que tienen tpicamente dos copias de la misma pgina en su biblioteca se llaman organismos diploid. Tal organismo (diploid) puede tener un nmero exacto de copias de la misma pgina (gene) o dos pequeas copias diferentes de la misma pgina.

Cuando un individuo tiene dos copias de la pgina (dos copias del mismo alelo) le llamamos organismo homogeneo (homo significa mismo). Cuando un individuo tiene dos copias de la pgina ligeramente diferentes entonces le llamamos individuo heterogeneo (hetero significa diferente). En el ejemplo de abajo utilizamos el color de la piel de los conejos para explicar mejor los alelos.

Los dos conejos tienen exactamente el mismo par de pginas (alelo) para el color del pelo. Todas las letras de la pagina que controlan (gene) el color del pelo son iguales entre dos conejos. Debemos decir que tienen el mismo alelo.

Cada pgina es anloga a un gene controlador del color del pelo Todas las pginas son el mismo alelo.

Si hay incluso diferencia entre las letras en las dos pginas, entonces tenemos alelos diferentes de la misma pgina (gene). El ejemplo dado en las figuras inmediatas esta debajo la letra diferente a la pgina que causa a los conejos tener un color de pelo diferente.

Cada conejo tiene dos copias de la misma pgina haciendoles homogeneos en esa pgina. Las pginas que el conejo negro tiene son diferentes del conejo blanco. Asi ellas, tienen diferente alelos.

Otros conceptos con respecto a los alelos

Exploraremos ms alla los alelos que influencian el aspecto exterior de una planta o de un animal. Tenemos alelos que llamamos dominantes y otros que llamamos recesivos. Debajo aparece una explicacin de alelo dominante y recesivo utilizando como analoga los conejos y la pgina. Primero, se demustra que solo ha cambiado la letra en la pgina, nosotros haremos las dos pginas diferentes (i.e., alelos) de dos colores diferentes (negro y blanco). As, la pgina del negro da lugar como resultado a un conejo de piel negra y una pgina blanca a un conejo con la piel manchada blanca.

En este ejemplo la pgina negra es dominante sobre la pagina blanca. Por este medio si un conejo tiene una pgina negra y una pgina blanca, entonces el conejo tendr la piel negra.

El (negro) y la combinacin de la pgina (del blanco) significan que los conejos son heterogneos.

Solamente los conejos con dos paginas blancas tendrn el blanco y la piel manchada. (blanco) y la combinacin de las dos pginas (blancas) significa que los conejos son homogneos.

Por supuesto si los conejos tienen dos pginas negras tendrn piel negra. El negro (negro) y la combinacin (negra) de la pgina significa que los conejos son homogneos.

As, si uno cruza un conejo negro (con dos pginas negras) con un conejo manchado blanco (con dos paginas blancas), todos los descendientes tendr una copia de la pgina negra y una copia de la pgina blanca. Pero todos tendran piel negra.

Posibilidades del descendiente entre el negro homogeneo y los conejos blancos homogenos se encuentran dentro de la rejilla negra gruesa.

Si tomamos los conejos que aparecen con una copia de la pagina negra y una copia de la pgina blanca, conseguiremos que los descendientes tengan las siguientes combinaciones:

Posibilidades del descendiente entre el negroheterogneo y los conejos negros se encuentran dentro de la rejilla negra gruesa.

Ejemplo hipottico de la dominacin incompleta

Hay algunos genes donde los alelos no son completamente dominantes o recesivos. Tal situacion es una dominante incompleta. Nosotros utilizaremos un ejemplo hipotetico con flores para explicar este concepto.

Como en el ejemplo previo del conejo, nuestras flores tienen dos copias de las mismas paginas (genes) en su biblioteca (por ejemplo, ellos son diplocitos). Cuando las flores tienen dos copias del mismo alelo para el tratado de la flor blanca, las flores son blancas. Cuando las flores tienen dos copias del mismo allele para el tratado del alelo de la flor roja, las flores son rojas. Pero, si las flores tienen una copia para el alelo de la flor roja y una copia para el alelo de la flor blanca, la mezcla da como resultado flores rosas. Nosotros utilizamos un ejemplo de hojas de papel blancas y rojas asi como las flores para explicar. Por favor vaya mas abajo para ver la explicacion de como los alleles pueden interactuar para formar diferentes colores de flores.

Esta flor tiene el numero exacto de pagina (alelo) para su color. Todas las letras de la pagina (gene) controlando el color son las mismas entre dos flores. Y, nosotros diremos que ellos tienen los mismos alelos.

Cada pgina es anloga al gen que controla el color. Todas las paginas con los mismos alelo.

Si hay una letra diferente entre las letras en las dos pginas entonces tenemos diferentes alelos de la misma pgina (gene). En el ejemplo dado inmediatamente ms abajo, la letra diferente en la pagina causa que las flores tengan diferente color.

Cuando alguien cruza las flores rojas y blancas, el resultado (la nueva flor) tendr una copia de la pagina roja y una copia de la pagina blanca. Porque la situacin es que de la dominante incompleta, las flores que aparecen no son ni rojas ni blancas pero en lugar de eso de un color intermedio que es el rosa.

RESUMEN

Espacio de bsquedaCuando se resuelve un problema, se busca la mejor solucin entre un conjunto de posibles soluciones. Al conjunto de todas las posibles soluciones a un problema concreto se llama espacio de bsqueda. Cada punto en el espacio de bsqueda representa una posible solucin. Cada posible solucin se le puede asociar un fitness o un valor que indicar cmo de buena es la solucin para el problema. Un algoritmo gentico (AG) devolver la mejor solucin de entre todas las posibles que tenga en un momento dado.

Entonces parece que buscar una solucin se reduce a buscar un valor extremo (mnimo o mximo) en el espacio de bsqueda. A veces el espacio de bsqueda puede ser bien definido, pero en la mayora de las ocasiones slo se conocen algunos puntos en el espacio de bsqueda. Cuando se usa un AG las posibles soluciones generan otras a medida que el gentico evoluciona.

La resolucin de un problema puede expresarse como la busqueda del extremo de una funcin Aqu resolvemos ese problema, este es un algortmo gentico que calcula el mximo de una funcin. La grfica representa un espacio de busqueda y las lneas verticales son posibles soluciones. La lnea roja es el mejor individuo de la poblacin y las verdes el resto.

Pulsa el botn Empezar para que el gentico comience, el botn Parar detendr la ejecucin, en el botn Paso a Paso se ejecutar un nico paso creando una nueva poblacin y el botn Reiniciar crear una nueva poblacin inicial.

El problema estriba en que la bsqueda puede ser muy compleja por diversas razones, como por ejemplo no saber dnde buscar una solucin o dnde empezar a buscarla. Existen muchos mtodos que se usan para buscar una solucin vlida, pero no necesariamente obtienen la mejor solucin. Algunos de estos mtodos son los algoritmos de escalada, backtracking o vuelta atrs, bsqueda a ciegas y los algoritmos genticos. Las soluciones que encuentran estos tipos de bsqueda suelen ser buenas soluciones, pero no siempre encuentran la ptima.

Problemas NP Completos

Cuando se plantea un problema concreto, habr una serie de algoritmos aplicables. Se suele decir que el orden de complejidad de un problema es el del mejor algoritmo que se conozca para resolverlo. As se clasifican los problemas, y los estudios sobre algoritmos se aplican a la realidad.

Estos estudios han llevado a la constatacin de que existen problemas muy difciles, problemas que desafan la utilizacin de los ordenadores para resolverlos. En lo que sigue esbozaremos las clases de problemas que hoy por hoy se escapan a un tratamiento informtico.

Clase P

Los algoritmos de complejidad polinmica se dice que son tratables en el sentido de que suelen ser abordables en la prctica. Los problemas para los que se conocen algoritmos con esta complejidad se dice que forman la clase P.Aquellos problemas para los que la mejor solucin que se conoce es de complejidad superior a la polinmica, se dice que son problemas intratables. Seria muy interesante encontrar alguna solucin polinmica (o mejor) que permitiera abordarlos.

Clase NP

Algunos de estos problemas intratables pueden caracterizarse por el curioso hecho de que puede aplicarse un algoritmo polinmico para comprobar si una posible solucin es vlida o no. Esta caracterstica lleva a un mtodo de resolucin no determinista consistente en aplicar heursticos para obtener soluciones hipotticas que se van desestimando (o aceptando) a ritmo polinmico.

Los problemas de esta clase se denominan NP (la N de no-deterministas y la P de polinmicos).

Clase NP Completos

Se conoce una amplia variedad de problemas de tipo NP, de los cuales destacan algunos de ellos de extrema complejidad. Grficamente se puede decir que algunos problemas se hayan en la "frontera externa" de la clase NP. Son problemas NP, y son los peores problemas posibles de clase NP. Estos problemas se caracterizan por ser todos "iguales" en el sentido de que si se descubriera una solucin P para alguno de ellos, esta solucin sera fcilmente aplicable a todos ellos. Actualmente hay un premio de prestigio equivalente al Nobel reservado para el que descubra semejante solucin... y se duda seriamente de que alguien lo consiga!

Es ms, si se descubriera una solucin para los problemas NP-completos, esta sera aplicable a todos los problemas NP y, por tanto, la clase NP desaparecera del mundo cientfico al carecerse de problemas de ese tipo. Realmente, tras aos de bsqueda exhaustiva de dicha solucin, es hecho ampliamente aceptado que no debe existir, aunque nadie ha demostrado, todava, la imposibilidad de su existencia...

Una alternativa para resolver los problemas NP-completos son los algoritmos genticos. Ejemplos de problemas NP-completos son el problema del viajante de comercio (TSP), el problema del coloreamiento de un grafo, el problema de la satisfacibilidad...

Clase NP Duros

Esta clase puede ser descrita como conteniendo los problemas de decisin que son al menos tan dificiles como un problema de NP. Esta afirmacin se justifica porque si podemos encontrar un algoritmo A que resuleve uno de los problemas H de NP-hard en tiempo polinmico, entonces es posible construir un algotimo que trabaje en tiempo polinmico para cualquier problema de NP ejecutando primero la reduccin de este problema en H y luego ejecutando el algoritmo A. La clase NP-completo puede definirse alternativamente como la interseccin entre NP y NP-hard.

Ejemplo Mximo Funcin

Ejemplo

Este es un algoritmo gentico que calcula el mximo de una funcin. La grfica representa un espacio de bsqueda y las lneas verticales son posibles soluciones. La lnea roja es el mejor individuo de la poblacin y las verdes el resto.

El botn Empezar hace que el gentico comience, el botn Parar detiene la ejecucin, en el botn Paso a Paso se ejecutar un nico paso creando una nueva poblacin y el botn Reiniciar crea una nueva poblacin inicial.

Es recomendable comenzar pulsando el botn Paso a Paso y observar en detalle como funciona el algoritmo gentico. Se puede observar que se utiliza el elitismo.

Operadores de un Algoritmo Gentico

Operador de cruce

Los operadores de cruce tratan de crear una generacin de individuos nuevos (offspring) pidiendo informacin a sus ancestros. Aunque estos operadores parecen corresponderse con la representacin basada en precedencia, realizando un estudio mas minucioso se observa que su funcionamiento est influenciado por otros factores.

Cruce en un punto

Se copian los genes del primer padre hasta el punto de corte y se rellena con el resto de elementos que hagan la solucin vlida en el orden en que aparecen en el segundo padre considerando la cadena de genes como cclica. En el caso de que se haya utilizado una codificacin binaria simplemente se copian el resto de genes del segundo padre.

11001011+11011111 = 11001111

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

Cruce en dos puntos

Se copian los genes del primer padre comprendidos entre los dos puntos de cruce y se rellenan los que faltan con los del segundo padre considerando la cadena de genes como cclica.

11001011 + 11011111 = 11011111

Cruce uniforme

No se puede aplicar a la representacin basada en permutaciones. Se escoge aleatoriamente si el gen i-simo del hijo se toma del primer o del segundo padre.

11001011 + 11011101 = 11011111

Cruce aritmtico

No se puede aplicar a la representacin basada en permutaciones. Se realizan operaciones aritmticas con los genes de los padres para resultar la codificacin gentica del hijo.

11001011 + 11011111 = 11001001 (AND)

Operador de mutacin

Inversin de genes

Se seleccionan genes aleatoriamente y se invierte su valor. Se utiliza en representaciones de bits, cambiando 0s por 1s o viceversa.

11001001 => 10001001

Cambio de orden

Se seleccionan dos genes aleatoriamente y se intercambian sus posiciones. Se utiliza en representaciones basadas en permutaciones.

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

Modificacin de genes

Se realizan pequeas modificaciones en los genes. Por ejemplo en una codificacin basada en numeros reales se realizan sumas de nmeros muy pequeos positivos o negativos.

(1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55)

Operador de aceptacin

Despus de realizar el cruce y la mutacin de los individuos de la poblacin llega el momento de decidir si aceptamos los hijos generados. Tenemos varias tcnicas que podemos aplicar para ello.

Aceptacin total

Es la manera ms comnmente utilizada, todos los hijos generados son aceptados y pasan a formar parte de la nueva poblacin.

De mejora

Los hijos pasan a la nueva poblacin si son mejores que los peores individuos de la poblacin actual, sino son los peores los que pasan a la poblacin actual.

Por torneo

Podemos realizar un torneo, como el explicado en el apartado de seleccin entre los hijos y los peores individuos de la poblacin actual y son los de mayor fitness los que pasan a la nueva poblacin.

Parmetros de los AGs

Porcentaje de Cruce (Pc)

Indica con qu frecuencia se cruzarn los individuos. Si ste es 0% , los hijos sern como los padres y slo sern alterados por la mutacin. Si ste es 100% todos los individuos nuevos sern creados mediante cruce de los padres de la generacin previa. Cuanto ms se crucen los individuos se supone que los hijos sern mejores. Sin embargo es recomendable, por la naturaleza del gentico, que algunos individuos pasen sin modificar a la siguiente generacin.

Porcentaje de Mutacin (Pm)

Establece la probabilidad con la cual los individuos sern mutados. Si ste porcentaje es 0% los individuos generados despus de aplicarse el cruce no sufrirn ningn cambio por el contrario si es de 100% todos lo individuos de la poblacin sufrirn cambios o mutaciones. La mutacin trata de impedir que la bsqueda del gentico caiga en extremos locales por eso es conveniente que ocurra de vez en cuando. No es bueno, sin embargo, que la mutacin ocurra continuamente, ya que la bsqueda del gentico pasa de ser "inteligente" a bsqueda aleatoria.

Tamao de la Poblacin (tam-pob)

Establece cuntos individuos habr en cada una de las generaciones. Si el tamao de la poblacin es muy bajo, el algoritmo gentico tiene pocas posibilidades de evolucionar por el cruce y los los individuos nuevos se parecern mucho a sus padres. Tampoco un tamao excesivo es adecuado porque se llega a un punto en el que los resultados no mejoran por mucho que se incremente el tamao de la poblacin. Lo ideal es, en funcin del problema y la codificacin, establecer un lmite adecuado del tamao de la poblacin.

Nmero de Generaciones (nro-gen)

Con el paso de las generaciones la poblacin del gentico evolucionar obteniendo cada vez mejores individuos. Conviene, al igual que con el tamao de la poblacin, fijar un nmero de generaciones adecuado para conseguir el resultado deseado.

Tamao del Individuo (tam-ind)

Depender del nmero de elementos que constituyan una solucin. Vara con el problema a resolver.

Seleccin

Como ya se ha visto los individuos se seleccionan para reproducirse, ahora bien el problema est en cmo seleccionar. De acuerdo con la teora de la evolucin de Darwin, slo los mejores individuos se reproducen. Basndose en esto existen varios mtodos que son utilizados por los genticos: Seleccin por la Regla de la Ruleta ,Seleccin por Ranking, Seleccin de Estado Fijo por citar algunos de los ms utilizados.

Seleccin por la Regla de la Ruleta

Los padres se seleccionan de acuerdo a su fitness. Los individuos mejores (con mayor fitness) son los que tienen mayores posibilidades de ser elegidos. Intuitivamente el proceso construye una ruleta o un "tarta" en la que cada uno de las porciones representa a un individuo. La porcin de tarta que le toca a cada individuo es proporcional a su fitness. As los individuos buenos se llevarn las mayores porciones y al revs ocurrir con los peores. El siguiente ejemplo clarifica el proceso:

Ahora, al igual que en un casino se lanza a la ruleta una canica. En el lugar que pare dicha canica, ser un lugar ocupado por un cromosoma que ser elegido. Resulta claro que los individuos con mayor fitness son los que ms a menudo son elegidos.

Existe un algoritmo para realizar este proceso:

1. [SumaTotal] Calcular la suma total acumulada de los fitness de todos los individuos de la poblacin actual.

2. [Elegir un nmero aleatorio r] Generar un nmero aleatorio entre 0 y la SumaTotal.

3. [Recorrer] Recorrer la poblacin acumulando nuevamente los fitness. Cuando la suma que se lleve sea mayor o igual a r seleccionamos el individuo donde se vaya recorriendo.

Seleccin por Ranking

El anterior tipo de seleccin funciona mal cuando existan grandes diferencias entre los fitness de los individuos de la poblacin. Por ejemplo si un cromosoma ocupa el 90% de la ruleta el resto de los cromosomas tienen muy pocas posibilidades de ser elegidos. La seleccin por ranking da solucin a este problema.

Los individuos son ordenados de acuerdo a su ranking de fitness. De esta manera si tenemos n cromosomas el individuo con peor fitness se le asignar un 1 y el que tenga el mejor fitness se le asignar la n.

Vase en las dos siguientes figuras cmo cambia la situacin antes y despus del ranking.

Situacin antes del Ranking (Ruleta)

Situacin despus del Ranking

Ahora todos los cromosomas tienen la oportunidad de ser seleccionados. Sin embargo este mtodo puede hacer que el gentico converja lentamente a la solucin, ya que los mejores individuos no se diferencian apenas de los peores.

A este esquema se le pueden aplicar otros criterios; por ejemplo, se crea la descendencia de uno de los paladines/amazonas, y esta sustituye al ms parecido entre los perdedores. Esto se denomina crowding, y fue introducido por DeJong. Una variante de este es el muestreado estocstico universal, que trata de evitar que los individuos con ms fitness copen la poblacin; en vez de dar la vuelta a una ruleta con una ranura, da la vuelta a la ruleta con N ranuras, tantas como la poblacin; de esta forma, la distribucin estadstica de descendientes en la nueva poblacin es ms parecida a la real.

Seleccin por Torneo K/L

La seleccin por Torneo K/L consiste en seleccionar K individuos de la poblacin aleatoriamente y de estos K individuos se seleccionan los L que tengan mejor fitness. Este proceso se repite todas las veces necesarias hasta formar la nueva poblacin.

Este es uno de los mtodos de seleccin ms utilizados actualmente. Se utiliza tambin en algunos algoritmos en el momento de la aceptacin.

Elitismo

Este concepto expresa la idea de que el mejor individuo de la actual generacin pase sin modificar a la siguiente generacin. De esta forma no se perder el mejor cromosoma. Al resto de la poblacin se le aplica la reproduccin normalmente.

Por otra parte existen algoritmos genticos llamados elitistas debido a que convergen muy rpidamente a la solucin. Esto se debe al tipo de problema que se trate. Ms adelante se ver un caso concreto El problema del coloreamiento de un grafo.

Representacin del genotipo

Es esencial distinguir en una solucin a un problema entre el genotipo y el fenotipo. El genotipo es la representacin interna que nosotros utilizamos para trabajar con la solucin, mientras que el fenotipo es la solucin en s misma. Los operadores del algoritmo trabajarn con el genotipo.

Se ha de elegir una representacin para el genotipo:

Representacin Binaria

La representacin binaria es la ms comn. En ella, un cromosoma es una cadena de bits 0 1. Las primeras investigaciones en genticos utilizaron este tipo de codificacin debido a su sencillez. Es una representacin indirecta.

CROMOSOMA A101100101100101011100101

CROMOSOMA B111111100000110000011111

Representacin basada en Permutaciones

Una permutacin de los elementos de un determinado conjunto Z induce un orden total en ellos. Esta relacin de orden total puede ser representada mediante una matriz de 1 y 0 llamada matriz de precedencia. El elemento de la matriz aij colocado en la fila i y la columna j es 1 (Verdadero) si y solo si el smbolo etiquetado como i antecede al smbolo etiquetado como j en la secuencia. Esto da lugar a una primera forma de manipular una permutacin, como una coleccin no ordenada de relaciones de precedencia.

En ciertas ocasiones esta representacin es demasiado exhaustiva y conviene relajarla un poco utilizando el concepto de adyacencia. En esta representacin una permutacin es un vector de |Z| (cardinal del conjunto que estamos considerando) pares, cada uno de ellos indicando cual es el inmediato predecesor de cada uno de ellos.

La forma mas natural para representar una permutacin es la basada en la posicin, es decir una lista ordenada de los elementos del conjunto Z. Tambin se puede considerar una representacin basada en bloques, siendo un bloque un subconjunto de elementos contiguos.

De todas estas posibles representaciones se elegir la basada en la posicin por considerarse mas sencilla de usar y suficientemente eficaz para el problema a resolver. Es una representacin indirecta.

CROMOSOMA A1 5 3 2 6 4 7 9 8

CROMOSOMA B 8 5 6 7 2 3 1 4 9

Representacin Directa

En este tipo de representacin se usa directamente en problemas que utilizan valores difciles de representar. por ejemplo si se usan nmero reales. Se trata de problemas en los que una codificacin binaria sera demasiado complicada.

Cada cromosoma es una secuencia de valores. Los valores son cualquier cosa relacionada con el tipo problema.(Nmeros reales, caracteres u otros tipos de objetos).

CROMOSOMA A1.2324 5.3243 0.4556 2.3293 2.4545

CROMOSOMA BABDJEIFJDHDIERJFDLDFLFEGT

CROMOSOMA C(atrs), (atrs), (derecha), (hacia delante), (izquierda)

Actividad de Aprendizaje N 05

Programacin GenticaObjetivos:

Programar aplicaciones Bioinformticas usando programacin gentica. Conocer los conceptos bsicos sobre el problema del viajante, problema de poblaciones y problema de la mochila. Construir Diagramas de Flujo de Datos, pantallas y cdigo para el problema de la Mochila.Contenidos:

Programacin de aplicaciones Bioinformticas usando programacin gentica.Definiciones del problema del viajante, problema de Poblaciones y el problema de la Mochila.

Diagramas de flujo, pantallas y cdigo del problema de la mochila.PROGRAMACIN GENTICA

Aqu se programaran diferentes aplicaciones Bioinformticas tomando como referencia lo ledo anteriormente.Problema del Viajante: Problema NP-CompletoEl problema del Viajante consiste en dado un grupo de ciudades y las distancias entre ellas, calcular el camino hamiltoniano mnimo.

Implementacin

Se utiliza una poblacin de 16 individuos. Se utiliza una codificacin basada en permutaciones sobre las ciudades. Cabe destacar que cuando se aade una nueva ciudad o se borra una de las existentes es necesario generar una nueva poblacin inicial y comenzar la ejecucin del gentico desde el comienzo. Se puede escoger el tipo de cruce y el tipo de mutacin.

Cruce

Cruce en un punto

Cruce en dos puntos

Sin cruce, los hijos son una copia exacta de sus padres

Mutacin Mutacin aleatoria

Mutacin aleatoria de mejora, despus de producirse la mutacin aleatoria se seleccionan aleatoriamente unas cuantas ciudades y se intercambian. Slo las mutaciones que mejoran el individuo se realizan.

Mutacin sistemtica de mejora, se produce una mutacin aleatoria y despus se prueba a intercambiar todos los genes entre s. Slo las mutaciones que mejoran el individuo se realizan.

Mutacin de mejora, se seleccionan aleatoriamente unas cuantas ciudades y se intercambian. Slo las mutaciones que mejoran el individuo se realizan.

Mutacin sistemtica, se prueba a intercambiar todos los genes entre s. Slo las mutaciones que mejoran el individuo se realizan.

Sin mutacin.

Ejemplo

El applet que se muestra a continuacin muestra un algoritmo gentico que resuelve el problema del Viajante. El botn Cambiar Vista permite alternar entre la vista de la poblacin completa y la vista del mejor individuo de la poblacin. Se puede aadir una ciudad nueva haciendo clic en una zona libre del grafo y borrar una ciudad haciendo clic sobre ella. Al aadir una ciudad nueva o al borrar una se crea una poblacin nueva. Cabe destacar que estamos trabajando con un grafo completo. Intenta cambiar el tipo de cruce y el tipo de mutacin para observar los diferentes tiempos de convergencia. Es recomendable aadir ms ciudades para poder observarlo mejor.

Problema de Poblaciones

La Figura siguiente muestra el funcionamiento conjunto de los tres operadores.

Generacin de una nueva poblacin mediante la aplicacin de los operadores de seleccin, cruce en un punto y

Mutacin

Ejemplo

A continuacin vamos a ilustrar la estrategia operativa de un algoritmo gentico simple.

La aplicacin que consideramos est tomada de [Michalewicz 94]. Se trata del clculo

del mximo de la funcin

f(x)=x*sen(10x)+2.0

en el intervalo [-1..2]. La figura siguiente muestra la grfica de esta funcin. Si

calculamos de forma analtica los mximos de la funcin anterior (calculando los ceros

de la primera derivada ....), observamos que el mximo global en el intervalo [-1..2] se

obtiene para el valor 1.85, siendo f(1.85) = 3.85.

Para resolver este problema, hay que particularizar algunos elementos del algoritmo

gentico como la funcin fitness y el tamao de los individuos. Otros, como los

operadores genticos, en principio no dependen del problema. Las particularidades del

algoritmo para esta aplicacin son las siguientes.

Representacin de los individuos

Los individuos deben representar valores de la variable X en el intervalo [-1..2 ], ya que

en principio estos valores son las soluciones potenciales del problema. Dado que

consideramos una representacin binaria, el tamao de los individuos se determinar

teniendo en cuenta la precisin requerida. Por ejemplo, si queremos seis dgitos despus

del punto decimal, necesitamos, al menos, 3000000 valores distintos. Esto significa que

Necesitamos al menos 22 bits, ya que

As, necesitamos una aplicacin de un vector de 22 bits en valores reales del intervalo [-

1..2]. Por ejemplo, el cromosoma (1000101110110101000111) representa al nmero

0.637197; y los vectores de 22 ceros y 22 unos representan respectivamente los valores

1 y 2. En este caso, resulta evidente que cada genotipo representa nicamente a un solo

fenotipo.

Poblacin inicial

Si no se dispone de algn tipo de informacin que nos ayude en este punto, la poblacin

Inicial se generar de forma aleatoria.

Operadores genticos

Elegiremos los operadores de cruce en un punto y de mutacin comentados anteriormente.

Funcin de evaluacin

La funcin de evaluacin eval sobre un cromosoma v puede ser simplemente el valor de

que nos da la funcin f sobre el valor real x que representa v eval(v)=f(x).

Como hemos comentado, la funcin de evaluacin juega el papel del entorno clasificando las soluciones potenciales en funcin de su fitness o adaptacin. Por ejemplo, los individuos

v1 = (1000101110110101000111),

v2 = (0000001110000000010000),

v3 = (1110000000111111000101),

corresponden a los valores reales x1=0.637197, x2=-0.958973 y x3=1.627888,

respectivamente. Consecuentemente, la funcin de evaluacin para estos individuos

tomar los valores

eval(v1) = f(x1) = 2.586345,

eval(v2) = f(x2) = 1.078878,

eval(v3) = f(x3) = 3.250650.

Problema de la MochilaDefinicin del problema El problema de la mochila es un problema de programacin entera, estando sta ltima dentro del campo de la programacin matemtica y consiste en escoger un conjunto de artculos para llenar una mochila de modo de que se cumplan ciertas restricciones. Por ejemplo imagnese hacer una excursin a la que solo podemos llevar una mochila que, lgicamente, tiene una capacidad limitada. Cada objeto que introducimos ocupa un volumen dentro de la misma y en contrapartida durante el viaje nos proporcionar un beneficio o utilidad (ejemplo: una cantimplora), el problema surge cuando debemos elegir qu objetos seleccionar para llevar en la mochila de forma que nuestro beneficio sea mximo (tengamos todo lo necesario) sin exceder su capacidad. Esta situacin se presenta con cierta frecuencia en los mbitos econmico e industrial, donde la mochila suele representar la restriccin presupuestaria (cantidad mxima de recursos econmicos de los que se dispone) y donde la utilidad de los objetos seleccionados se equipara a un beneficio econmico por adquirir o llevar a cabo ciertas acciones, entre otras aplicaciones. 2. Caractersticas del problema

2.1 Datos del problema: n: nmero de objetos entre los que se puede elegir. ci: peso del objeto i - se refiere el objeto -simo que no es ms que una forma de hacer referencia a un objeto cualquiera que pueda ser incluido en la mochila, es decir, ci representa el coste de escoger un objeto, en tanto en cuanto va a ocupar un espacio de la mochila que dejar fuera otros objetos. bi: utilidad o beneficio que proporciona cada objeto, de nuevo se hace referencia al objeto i-simo. P: capacidad de la mochila, equivale al presupuesto mximo del que se dispone. 2.2 Variables a tener en cuenta: Los elementos a introducir en la mochila van a ser nuestras variables objeto de anlisis, cada variable la denotaremos como xi. El rasgo ms importante de nuestras xi es que se tratan de variables dicotmicas o binaria, es decir, slo pueden tomar dos valores, en este caso, escogeremos el valor 1 (si el objeto se incluye en la mochila) 0 (si el objeto se excluye de la mochila).2.3 Restricciones: La restriccin vendr marcada por la capacidad mxima de la mochila, de tal forma que la suma de todos los objetos multiplicados por el espacio que ocupan en la mochila no podr exceder dicha capacidad mxima.

2.4 Funcin a maximizar: Si redefinimos el problema introduciendo los elementos que mencionamos en las lneas precedentes llegaremos a la siguiente formulacin:

3. Mtodos de resolucin Este problema se ha resuelto tradicionalmente mediante programacin lineal entera. El hecho de que se trate de programacin lineal hace referencia a que la funcin a optimizar y las inecuaciones que constituyen las restricciones han de ser lineales, es decir, han de ser funciones cuyas incgnitas estn elevadas exclusivamente a la unidad. Otra forma de resolver este tipo de problema, a travs de los denominados algoritmos voraces. Una aproximacin voraz consiste en que cada elemento a considerar se evala una nica vez, siendo descartado o seleccionado, de tal forma que si es seleccionado forma parte de la solucin, y si es descartado, no forma parte de la solucin ni volver a ser considerado para la misma. Otro sistema para resolver el problema de la mochila es mediante algoritmos genticos que son mtodos de optimizacin que tratan de hallar (xi,...,xn) tales que sea mximo.3.1 Algoritmos voraces:a) Aplicacin del mtodo: Partimos de la formulacin del problema de la mochila aportada anteriormente: Maximizar [Sumatoria (bi*xi) desde i= 1 hasta n] Sujeto a: xi {0,1} con i =1,..., n [Sumatoria (ci*xi) desde i=1 hasta n] < P La utilizacin de un algoritmo voraz consiste en introducir en la mochila segn orden decreciente de utilidad (beneficio) los diversos objetos. En una primera etapa, se adicionarn unidades enteras hasta que, por motivo de capacidad, no sea posible seguir introduciendo enteros y haya que aadir la porcin que quepa del siguiente objeto.b) Concepto de solucin ptima: Teorema: si se ordenan los objetos de forma de decreciente en cuanto a su relacin (utilidad/ponderacin = bi/ci) y se introducen en la mochila enteros en este orden mientras quepan y cuando no quede capacidad para uno entero se aade la porcin que an tenga cabida el resultado al que se llega es una solucin ptima.3.2 Algoritmos genticos: Se basan en el proceso gentico de los organismos vivos, por imitacin de este proceso, los Algoritmos Genticos son capaces de ir creando soluciones para problemas del mundo real. La evolucin de dichas soluciones hacia valores ptimos del problema depende en buena medida de una adecuada codificacin de las mismas. Para utilizar un algoritmo gentico hacen falta tres elementos:Descripcin de la poblacin de individuos: cada individuo representa una solucin factible a un problema dado. A cada individuo se le asigna un valor puntuacin, relacionado con la bondad de dicha solucin.Funcin de evaluacin (llamada funcin de ajuste): encontrar una expresin matemtica que punte a cada individuo de forma que nuestro ideal sea un mximo o un mnimo.Seleccin o Mecanismos de reproduccin: la funcin de seleccin de padres ms utilizada, es la denominada funcin de seleccin proporcional a la funcin objetivo, en la cual cada individuo tiene una probabilidad de ser seleccionado como candidato que es proporcional al valor de su funcin objetivo.4. Formulacin del problema:Cul es el mtodo ptimo para la implementacin del problema de la mochila, dada la capacidad inicial de la mochila y una serie de objetos con sus respectivos pesos y utilidades, teniendo como objetivo hallar la utilidad mxima sin sobrepasar la capacidad de la mochila? 5. Solucin del problema planteado:

Por el mtodo tradicional: a travs de la maximizacin del problema anteriormente formulado mediante mtodos de programacin lineal entera.

Por algoritmos: existen tipos de algoritmos (genticos, voraces), pero para el problema planteado usaremos un algoritmo voraz.

Se presenta el diagrama de flujo general correspondiente a la solucin del problema. 5.1 Diagrama de flujo general: A continuacin presentamos diferentes Diagramas de flujo correspondiente a la solucin del problema de la mochila. 1. Solucin 012. Solucin 02

3. Solucin 03

Subrutinas.

Subrutinas.

Subrutina.

Subrutina.

Subrutina: ELIMINAR

Subrrutina: Modificar

Aplicacin del Problema de la mochila

Esta es la Ventana Principal,. Puede acceder a las diferentes opciones de la aplicacin mediante los mens y botones respectivos.

Figura 1.

Mens y Botones

Abrir aplicacin

Muestra la interfaz donde se desarrolla el problema de la mochila.

Nuevo Objeto

Permite abrir la ventana para agregar un nuevo objeto.

Guardar

Permite guardar en disco el progreso que se haya hecho en la aplicacin.

Ayuda

Permite abrir esta ayuda.

Salir

Permite salir de la aplicacin.

Acerca de

Permite ver los autores y la fecha de creacin.

Ventanas

Ventana Problema de la mochila

Esta es la ventana de la aplicacin del problema (Figura 2). Aqu tenemos dos paneles. En el primer panel se muestra el ingreso de datos necesarios para correr la aplicacin. Podemos escoger si deseamos ingresar los datos manualmente o generarlos de modo aleatorio, en ese caso todos los valores se generaran al azar. Si escogemos la opcin manual, nosotros podremos ingresar los datos uno por uno ingresando su peso y utilidad o seleccionar algunos objetos que hayamos agregado anteriormente. Para ingresar un objeto en la tabla solo debemos hacer clic en el botn Aadir. Adicionalmente podremos modificar los datos ingresados o eliminarlos si se desea mediante los botones de la parte inferior: Modificar y Eliminar. En el siguiente panel llamado visor de resultados, tenemos una ventana donde se irn mostrando los resultados obtenidos; slo debemos pulsar el botn Ejecutar.

Mediante el botn de Reiniciar, podemos limpiar todos los valores para iniciar una nueva ejecucin y mediante el botn Salir, salimos de esa aplicacin.

Ventana Agregar objeto

Esta es la ventana para agregar un nuevo objeto (Figura 3). Puede agregar un nuevo objeto llenando todos los campos y pulsando el Botn OK. En esta ventana existen los campos nombre, peso y utilidad del objeto, los cuales son obligatorios. Adicionalmente existe el campo imagen, donde se podr agregar una imagen al objeto.

Cuando se agregue una nueva persona se agregara un icono representativo que est en el Men Principal.

Ventana Edicin de objetos

Esta es la ventana para editar un objeto (Figura 4). Para acceder a esta ventana solo se necesita hacer Doble Clic sobre el icono representativo del objeto en la Men Principal.

Se edita un objeto llenando todos los campos y pulsando el Botn OK. Esta ventana tambin da la posibilidad de borrar un objeto con solo hacer clic en el botn BORRAR, donde se pedir la confirmacin de esta accin.

Codificacin:

JAVA(NETBEANS 6.8 O SUPERIOR)Cdigo del problema de la Mochila

package proyectobio;

import java.util.*;

import javax.swing.JOptionPane.*;

import javax.swing.*;

import javax.swing.table.*;

public class Prob_Mochila extends javax.swing.JDialog {

private DefaultListModel lista = new DefaultListModel();

private DefaultTableModel tabla = new DefaultTableModel();;

private int it=1;

private int capacidad=0;

private int peso1=0, utilidad1=0;

private String datos[] = new String [4];

String titulos[]={"Objeto","Peso","Utilidad"};

public Prob_Mochila(java.awt.Frame parent, boolean modal,LinkedList grafo) {

super(parent, modal);

this.setUndecorated(true);

this.grafo=grafo;

initComponents();

tabla.setColumnIdentifiers(titulos);

jTable1.setModel(tabla);

jList1.setModel(lista);

setSize(550,500);

}

//Busca una persona en el grafo

public Vertice buscarObjeto(String nombre)

{

for(int i=0;i=0)

tabla.removeRow(fila);

else

JOptionPane.showMessageDialog(null,"Selecciona una fila de la tabla para eliminar");

}

private void jButton5ActionPerformed(java.awt.event.ActionEvent evt) {

int nfilas=-1,ncolums=0,aux2,aux3;

int ut=0,p=0,cap;

double valor,aux1;

String aux4;

lista.clear();

nfilas=tabla.getRowCount();

if (jTextField1.getText().length()==0){

JOptionPane.showMessageDialog(null,"FALTA INGRESAR LA CAPACIDAD DE LA MOCHILA");

return;

}else if(nfilas=0){

x=x+peso[j];

if(xumax){

umax=u;

pmax=pes;

items=sit;

}

if(j==0){

cont2=cont2+1;

x=peso[i];

u=utilidad[i];

sit=""+item[j];

j=i-cont2;

}else{

j=j-1;

}

}

}

lista.addElement("");

lista.addElement("- Los Objetos siguientes: "+items);

lista.addElement("- La maxima utilidad es: "+umax);

lista.addElement("- El peso de los objetos es: "+pmax);}

}

private void jComboBox1ActionPerformed(java.awt.event.ActionEvent evt) {

int indice;

indice = jComboBox1.getSelectedIndex();

switch (indice){

case 0:

break;

case 1:

peso1=15;

utilidad1=22;

break;

case 2:

peso1=20;

utilidad1=25;

}

}

BIBLIOGRAFA. O. Cordn, F. Herrera, F. Hoffmann, L. Magdalena. GENETIC FUZZY SYSTEMS. Evolutionary Tuning and Learning of Fuzzy Knowledge Bases. World Scientific, Julio 2001. ISBN 981-02-4016-3 (Advances in Fuzzy Systems - Applications and Theory, Vol. 19)

W. Banzhaf, P. Nordin, R.E. Keller, F.D. Francone; Genetic Programming. An Introduction, Kaufmann Pub., 1998.

L. Chambers (Eds.); Practical Handbook of Genetic Algorithms. Vol I., Vol II, CRC. Press. 1995.

Ramss Salas A. y Carlos Scotto Espinoza. Manual Universitario de prcticas de Gentica General, Diciembre 2006 Lima Per. Editado por la Asamblea Nacional de Rectores.

RAFAEL LAHOZ-BELTRA; Bioinformtica simulacin, vida artificial e inteligencia artificial.

Solomon, Berg y Martin, Biologia, Marzo 2005 Mexico, Editorial Mexicana.

GENERACIN DE POBLACIN DE SOLUCIONES

Peso:

Utilidad:

Ingrese la Capacidad de la Mochila

Fin

IMPRIMIR : mochila[], peso2[], utilidad2[];

total1=total1+peso[i];total2=total2+utilidad[i];

mochila[cont]=elementos[i];

peso2[cont]=peso[i];

utilidad2[cont]=utilidad[i];break;

peso[i]==dife & utilidad[i]==1

total1=total1+peso[i];total2=total2+utilidad[i];

mochila[cont]=elementos[i];

peso2[cont]=peso[i];

utilidad2[cont]=utilidad[i];break;

peso[i]==dife & utilidad[i]==2

total1=total1+peso[i];total2=total2+utilidad[i];

mochila[cont]=elementos[i];

peso2[cont]=peso[i];

utilidad2[cont]=utilidad[i];break;

peso[i]==dife & utilidad[i]==3

For =0 to n-1

Break(salir de bucle)

difepeso[j+1]

aux= peso[j];

aux1=utilidad[j];

aux2=elementos[j];

peso[j]=peso[j+1];

utilidad[j]=utilidad[j+1];

elementos[j]=elementos[j+1];

peso[j+1]=aux;

utilidad[j+1]=aux1;

elementos[j+1]=aux2;

Ingresar el nmero de tems

Hay ms combinaciones posibles?

Sumamos los pesos de la siguiente combinacin.

Ya se oper una combinacin con los mismos tems?

Suma = utilidadmax

Hallamos para cada tem: ji=