Antecedentes del tema.
Anteriormente hice la tesis llamada algoritmos Algoritmos genéticos aplicados a búsqueda de motifs en secuencias de ADN, pero quiero ahora quiero ver a los algoritmos matemáticos desde un punto de vista matemático.
Bases Teoricas
Métodos exhaustivos de búsqueda.
Los métodos exhaustivos son conocidos también como de fuerza bruta ya que examinan cada una de las posibles alternativas para encontrar una solución. Estos métodos son muy útiles sobre todo cuando no se conoce un método eficiente de solución, además que no son difíciles de diseñar y programar, son buenos para resolver algunos problemas en la biología, pero cabe señalar que pueden tardar mucho tiempo en encontrar una solución cuando crece el tamaño de variables a evaluar. Existen muchos métodos que a su vez utilizan métodos exhaustivos para solucionar problemas, pero reducen su complejidad al ir descartando posibilidades que se sabe que no están dentro del rango de soluciones, como lo hacen los algoritmos de Branch-andBound o en español son conocidos como ramificación y acotamiento y los algoritmos genéticos en los cuales se hace enfoque en este trabajo.
Algoritmos genéticos.
Los algoritmos genéticos son un modelo computacional, utilizados en problemas de búsqueda y optimización inspirados en la evolución humana, la reproducción sexual y en el principio de supervivencia del más apto. Una definición más formal dada por Goldberg es que "los algoritmos genéticos son algoritmos de búsqueda basados en la mecánica de selección natural y de la genética natural. Combinan la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado para construir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas"(Goldberg, 1989) [13] El primer paso en el algoritmo genético es generar una población de manera aleatoria, esto creará individuos que representan posibles soluciones y codificadas de una forma similar a un cromosoma que irán evolucionando conforme avancen las generaciones mediante la selección natural, el cruce y la mutación. A su vez estos cromosomas tendrán asociada una aptitud o fitness que nos permitirá cuantificar si es un buen individuo que represente una posible solución. En base a esta aptitud se le pueden dar más o menos oportunidades de reproducirse pudiendo ser de una manera elitista, aunque cabe señalar que la mezcla con individuos menos calificados puede dar una mezcla que al final haga que los descendientes tengan una buena evaluación ya que dan más posibilidades de explorar otras soluciones sin caer en un solo sector en donde los individuos mejor calificados no lleguen a explorar del todo otras posibles soluciones.
Representación de un cromosoma.
La figura 1 muestra un cromosoma que por lo regular se representa de forma binaria, pero también puede representarse con números enteros, flotantes, reales, etc. Sin embargo se sustentará más adelante la razón del porqué se pueden realizar mejor las operaciones de un algoritmo genético de forma binaria.
Cuando se dice que el programa converge es cuando ya no se tienen cambios en la solución en cada generación. Es decir, la solución ya no va a cambiar porque ya no se puede mover más y es posible que ya encontró la solución o porque se fue a un mínimo local y no puede explorar más posibles soluciones.
Fuente:
[1]Miguel Angel Castañeda. (2016). Algoritmos genéticos aplicados a busqueda de motifs en secuencias de ADN. ITESM CEM: Tesis.
Anteriormente hice la tesis llamada algoritmos Algoritmos genéticos aplicados a búsqueda de motifs en secuencias de ADN, pero quiero ahora quiero ver a los algoritmos matemáticos desde un punto de vista matemático.
Bases Teoricas
Métodos exhaustivos de búsqueda.
Los métodos exhaustivos son conocidos también como de fuerza bruta ya que examinan cada una de las posibles alternativas para encontrar una solución. Estos métodos son muy útiles sobre todo cuando no se conoce un método eficiente de solución, además que no son difíciles de diseñar y programar, son buenos para resolver algunos problemas en la biología, pero cabe señalar que pueden tardar mucho tiempo en encontrar una solución cuando crece el tamaño de variables a evaluar. Existen muchos métodos que a su vez utilizan métodos exhaustivos para solucionar problemas, pero reducen su complejidad al ir descartando posibilidades que se sabe que no están dentro del rango de soluciones, como lo hacen los algoritmos de Branch-andBound o en español son conocidos como ramificación y acotamiento y los algoritmos genéticos en los cuales se hace enfoque en este trabajo.
Algoritmos genéticos.
Los algoritmos genéticos son un modelo computacional, utilizados en problemas de búsqueda y optimización inspirados en la evolución humana, la reproducción sexual y en el principio de supervivencia del más apto. Una definición más formal dada por Goldberg es que "los algoritmos genéticos son algoritmos de búsqueda basados en la mecánica de selección natural y de la genética natural. Combinan la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado para construir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas"(Goldberg, 1989) [13] El primer paso en el algoritmo genético es generar una población de manera aleatoria, esto creará individuos que representan posibles soluciones y codificadas de una forma similar a un cromosoma que irán evolucionando conforme avancen las generaciones mediante la selección natural, el cruce y la mutación. A su vez estos cromosomas tendrán asociada una aptitud o fitness que nos permitirá cuantificar si es un buen individuo que represente una posible solución. En base a esta aptitud se le pueden dar más o menos oportunidades de reproducirse pudiendo ser de una manera elitista, aunque cabe señalar que la mezcla con individuos menos calificados puede dar una mezcla que al final haga que los descendientes tengan una buena evaluación ya que dan más posibilidades de explorar otras soluciones sin caer en un solo sector en donde los individuos mejor calificados no lleguen a explorar del todo otras posibles soluciones.
Representación de un cromosoma.
La figura 1 muestra un cromosoma que por lo regular se representa de forma binaria, pero también puede representarse con números enteros, flotantes, reales, etc. Sin embargo se sustentará más adelante la razón del porqué se pueden realizar mejor las operaciones de un algoritmo genético de forma binaria.
Fig. 1 Representación binaria de un Cromosoma [1]
Algoritmo genético simple.
BEGIN
Generar población Inicial
Evaluar cada individuo
WHILE NOT Terminado DO
FOR 1 TO Tamaño de la población / 2
Seleccionar un par individuos
Cruzar individuos seleccionados
Mutar descendientes
Evaluar descendientes
Insertar descendientes en nueva generación
END FOR
IF Programa converge ó número de generaciones = N THEN
Terminado = True
END IF
END WHILE
END
Fuente:
[1]Miguel Angel Castañeda. (2016). Algoritmos genéticos aplicados a busqueda de motifs en secuencias de ADN. ITESM CEM: Tesis.
Comments
Post a Comment