May 29 2008
BC Prueba 3: Algoritmos genéticos
Atención : Este artículo es la tercera prueba del Bloggers Confrontation
Una de las ideas más prometedoras en la inteligencia artificial son los llamados algoritmos genéticos. A mediados de los 70 John Henry Holland, un profesor de Filosofía, de Ingeniería Eléctrica y de Ciencias de la computación en la Universidad de Michigan ideo este concepto. Los algoritmos genéticos o evolutivos, son llamados así, porque se basan en la famosa teoría de la evolución.
Según esta concepción, un algoritmo parte de una determinada población de soluciones potenciales a un problema, todas las cuales son medidas en función de su aptitud. Se parte del supuesto que no todas las soluciones funcionaran o que incluso algunas de ellas pueden llegar a solventar el problema, en cuyo caso, se buscaría mejorar dicha solución. Entonces, una de estas posibles soluciones generalmente conocida como cromosoma puede conservarse, e incluso reproducirse, cada reproducción además, puede sufrir toda una serie de cambios generalmente conocidos como mutaciones. El algoritmo entonces, ira descartando aquellas soluciones que no puedan adaptarse, aquellas que hayan logrado sobrevivir, podrán reproducirse y continuar.
Un algoritmo genético tiene también una serie de parámetros que se tienen que fijar para cada ejecución, como los siguientes:
- Tamaño de la población: debe de ser suficiente para garantizar la diversidad de las soluciones, y, además, tiene que crecer más o menos con el número de bits del cromosoma, aunque nadie ha aclarado cómo tiene que hacerlo.
- Condición de terminación: lo más habitual es que la condición de terminación sea la convergencia del algoritmo genético o un número prefijado de generaciones.
Funcionamiento de los algoritmos genéticos
Entonces, el funcionamiento general de un algoritmo genético se puede describir como sigue
- Se genera una determinada población de soluciones al problema (cromosomas) ya sea de manera aleatoria o no, en cuyo último caso, se deberá contar con la cantidad suficiente de cromosomas para garantizar la no terminación temprana del algoritmo.
- A cada cromosoma se le mide su “aptitud”, es decir, se somete a prueba para ver que tan buena es.
- En base a esto último, se eligen los cromosomas que pasaran a la siguiente generación, para ello, se implementa alguno de los métodos de selección existentes. Aunque el predominante generalmente es el método elitista (es decir, aquellos que demostraron mayor aptitud)
- Se determina la probabilidad de un cromosoma a ser elegido en base al método de selección
- Una vez elegido, se procede al “cruzamiento” de dos cromosomas para generar dos cromosomas nuevos con características de ambos
- El algoritmo terminará si y solo si se ha cumplido alguna de estas variables
- Se ha encontrado la solución más apta
- Se ha excedido el número de iteraciones necesarias o determinadas (donde cada iteración representa una nueva generación)
- No hubo cambios en la población, lo que se conoce como convergencia prematura, es decir, el algoritmo termino antes de tiempo al no encontrar un cromosoma superior
¿En qué se usan estos algoritmos?
Entre otras cosas, los algoritmos genéticos se usan para:
- Investigación en diseño de materiales y diseño multi-objetivo de componentes automovilísticos
- Diseño automatizado de sistemas de Mecánica de precisión, mediante grafos de bond y programación genética
- Diseño automatizado de equipamiento industrial
- Diseño automatizado de sistemas de comercio en el sector financiero
- Optimización de carga de contenedores
- Diseño de sistemas de distribución de aguas
- Diseño de topologías de circuitos impresos
- Diseño de topologías de redes computacionales
- En Teoría de juegos, resolución de equilibrios
- Aprendizaje de comportamiento de robots
- Aprendizaje de reglas de Lógica difusa
- Análisis lingüístico, incluyendo inducción gramática, y otros aspectos de Procesamiento de lenguajes naturales, tales como eliminación de ambigüedad de sentido
- Infraestructura de redes de comunicaciones móviles
- Etc.
Loading ...
