Algoritmos Genéticos

                    [pic 1][pic 2]

 UNIVERSIDAD DE GUAYAQUIL

FACULTAD DE CIENCIAS MATEMÁTICAS Y FISICA

CARRERA: INGENIERÍA EN SISTEMAS COMPUTACIONALES

 TEMA:

Algoritmos Genéticos

INTEGRANTES:

• Palma Jacinto
• Pucuna Joan
• Saquicela Jorge
• Salinas Kerlly

DOCENTE:                            

Ing. Katya Faggioni, Mgs

MATERIA:

Inteligencia Artificial

CURSO:                                 5-2

AÑO LECTIVO:                         2019-2020

Contenido

ALGORITMOS GENÉTICOS        3

1.        HISTORIA        3

2.        CONCEPTO        5

3.        DEFINICIÓN DE LOS ELEMENTOS DEL ALGORITMO.        7

4.        FUNCIONES        10

5.        VENTAJAS Y DESVENTAJAS        13

6.        ESTRUCTURA        15

7.        EJEMPLO DE ALGORITMO GENÉTICO        18

8.        CONCLUSIÓN        22

9.        PREGUNTAS        23

BIBLIOGRAFÍA        27

ALGORITMOS GENÉTICOS

1. HISTORIA

Partes de muchos acontecimientos científicas han basado sus teorías a partir de hechos o procedimientos naturales que llevados a una sistematización nos derivan a un resultado esperado basado en el mismo esquema natural del que ha sido imitado.  Durante millones de años las diferentes especies de este planeta han ido evolucionando su biología con el objetivo de adaptarse a los diferentes cambios de ambiente; es basado en estas teorías que surge la computación evolutiva como una familia de los modelos computacionales inspirados en la evolución.

Más formalmente, el término de computación evolutiva se refiere a los estudios de fundamentos y aplicaciones de ciertas técnicas heurísticas basados en los principios de la evolución natural (Tomassini, 1995). Estas técnicas heurísticas podrían clasificarse en tres grandes categorías o grupos dando lugar a la ecuación evolutiva.

[pic 3]

Ilustración 1: Ecuación Evolutiva

El algoritmo genético es una técnica de búsqueda basada en la teoría de la evolución de Darwin, su aparición data de finales de los años 50 e inicios de los años 60, época en la cual dichos algoritmos de manera no tan concreta eran programados en computadoras por biólogos evolutivos que buscaban explícitamente realizar aspectos de la evolución natural. Pero hasta entonces ninguno de estos investigadores tomaba la iniciativa de aplicar estas técnicas en problemas artificiales. En 1965 surgió un desarrollo exitoso, cuando Ingo Rechenberg introdujo una técnica que llamó estrategia evolutiva, la cual proponía descendencias a partir de la mutación del padre, no había población ni cruzamiento.

El siguiente desarrollo importante en este campo surgió 1966, cuando L.J. Fogel, A.J. Owens y M.J. Walsh introdujeron en América una técnica que llamaron programación evolutiva. En este método, las soluciones candidatas para los problemas se representaban como máquinas de estado finito sencillas, su algoritmo funcionaba mutando aleatoriamente una de estas máquinas simuladas y conservando la mejor de las dos (Marczyk, 2014).

Ya con estos avances dados la computación evolutiva y los algoritmos genéticos ganaban un gran campo de atención y estudio en las ciencias computacionales. Sin embargo, lo que todavía faltaba en estas dos metodologías era el reconocimiento de la importancia del cruzamiento.

En el año de 1962 el trabajo de John Holland investigador de la Universidad de Michigan sobre sistemas adaptativos llamado “planes reproductivos” basados en la selección natural, estableció los principios para desarrollos posteriores; y lo que es más importante, Holland fue el primero en proponer explícitamente el cruzamiento y otros operadores de recombinación (M. Gestal, 2010). A raíz de la publicación de su libro en el año de 1975 “Adaptación en Sistemas Naturales y Artificiales'' sus estudios son reconocidos con el nombre de Algoritmos Genéticos; este libro fue el primero en presentar sistemática y rigurosamente el concepto de sistemas digitales adaptativos utilizando la mutación, la selección y el cruzamiento, simulando el proceso de la evolución biológica como estrategia para resolver problemas.

Ese mismo año, la importante tesis de Kenneth De Jong estableció el potencial de los Algoritmos Genéticos demostrando que podían desenvolverse bien en una gran variedad de funciones de prueba, incluyendo paisajes de búsqueda ruidosos, discontinuos y multimodales (Marczyk, 2014).

Estos estudios y acontecimientos establecieron un interés más generalizado en la computación evolutiva permitiendo así que a partir de los 80, los algoritmos genéticos se estaban aplicando en una amplia variedad de áreas, desde problemas matemáticos abstractos hasta asuntos tangibles de ingeniería como el control de flujo en una línea de ensamble y clasificación de patrones.

Al principio, estas aplicaciones eran principalmente teóricas. Sin embargo, al seguir proliferando la investigación, los algoritmos genéticos migraron hacia el sector comercial, al cobrar importancia con el crecimiento exponencial de la potencia de computación y el desarrollo de Internet (Marczyk, 2014).

Hoy en día, la computación evolutiva es un campo floreciente, y los algoritmos genéticos están resolviendo problemas de interés cotidiano en áreas de estudio tan diversas como son la predicción en la bolsa y la planificación de la cartera de valores, ingeniería aeroespacial, diseño de microchips, bioquímica y biología molecular, entre otros campos. El potencial que representa la evolución se ha plasmado virtualmente en cualquier campo que uno pueda nombrar, pues los estudios aún continúan. Esto podríamos llamarlo la consecuencia de una simple pero poderosa idea de Charles Darwin que se plasma en los algoritmos genéticos basado en la ley de la selección, que es una técnica de resolución de problemas de inmenso poder y de aplicación casi ilimitada.

1. CONCEPTO

Tomando una definición formal de algoritmos genéticos dada por Goldberg este propone: “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 constituir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas” (Goldberg, 2002).

Los Algoritmos Genéticos abreviados como (AGs) son métodos de programación adaptativos que usados para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Charles Darwin en su teoría de la evolución. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de estas.

Los principales elementos que componen un algoritmo genético son:

• Esquema de codificación, hace referencia a la manera en que se representa una posible solución al problema.
• Función de evaluación, realiza un método el cual evalúa si un individuo es apto para resolver el problema planteado.
• Operadores básicos: reproducción, cruce y mutación. Estos operadores son simples y se basan en copias de cadenas de cromosomas.

• Parámetros que controlan el desempeño del algoritmo genético: probabilidad de cruce, probabilidad de mutación, tamaño de la población, número de generaciones, etc.

En el campo aplicativo la codificación que resulta ser más viable es mediante cadenas binarias, aunque se han utilizado también números reales y letras o caracteres para representar los cromosomas. El primero de estos esquemas ha sido una de los más populares originalmente propuesto por John Holland, y porque resulta fácil implementar. Operaciones sencillas de bits permiten efectuar el cruce, la mutación y otras operaciones. Hoy en día Investigaciones y proyectos que aplican algoritmos genéticos se realizaron en cadenas de longitud variable y otras estructuras, sin embargo, la mayor parte de estos se enfocan en cadenas de caracteres de longitud fija.

...