martes, 26 de septiembre de 2017

Algoritmos Genéticos

Los Algoritmos Genéticos son una de las más conocidas y originales técnicas de resolución de problemas dentro de lo que se ha definido como "Computación Evolutiva" (o "Algoritmos Evolutivos"), término que agrupa a los Algoritmos Genéticos, las Estrategias Evolutivas y la Programación Evolutiva. En realidad todas estas técnicas son muy parecidas y comparten muchos aspectos.

Un Algoritmo Evolutivo es una técnica de resolución de problemas inspirada en la evolución de los seres vivos.

En un Algoritmo Evolutivo se define una estructura de datos que admita todas las posibles soluciones a un problema.

Cada uno de los posibles conjuntos de datos admitidos por esa estructura será una solución al problema. Unas soluciones serán mejores, otras peores.

Solucionar el problema consistirá en encontrar la solución óptima, y por tanto, los Algoritmos Evolutivos son en realidad un método de búsqueda.

Pero un método de búsqueda muy especial, en el que las soluciones al problema son capaces de reproducirse entre sí, combinando sus características y generando nuevas soluciones.

En cada ciclo se seleccionan las soluciones que más se acercan al objetivo buscado, eliminando el resto de soluciones. Las soluciones seleccionadas se reproducirán entre sí, permitiendo de vez en cuando alguna mutación o modificación al azar durante la reproducción.


VENTAJAS DE LOS ALGORITMOS GENÉTICO

 • Una clara ventaja es que los algoritmos genéticos son intrínsicamente paralelos, es decir, operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales. 

Esto significa que mientras técnicas tradicionales sólo pueden explorar el espacio de soluciones hacia una solución en una dirección al mismo tiempo, y si la solución que descubren resulta subóptima, no se puede hacer otra cosa que abandonar todo el trabajo hecho y empezar de nuevo. Sin embargo, los algoritmos genéticos simplemente desechan esta solución subóptima y siguen por otros caminos. 

• Cuando se usan para problemas de optimización resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas tradicionales. Muchos algoritmos de búsqueda pueden quedar atrapados en los óptimos locales: si llegan a lo alto de una colina del paisaje adaptativo, descubrirán que no existen soluciones mejores en las cercanías y concluirán que han alcanzado la mejor de todas, aunque existan picos más altos en algún otro lugar del mapa, situación que no sucede para algoritmos genéticos. 

• Otra ventaja es su habilidad para manipular muchos parámetros simultáneamente. Resulta interesante en caso de tener varios objetivos a resolver. 

• No necesitan conocimientos específicos sobre el problema que intentan resolver. 
Realizan cambios aleatorios en sus soluciones candidatas y luego utilizan la función de aptitud para determinar si esos cambios producen una mejora o no.

 • Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivas en paralelo. 

• Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de las otras técnicas. 

DESVENTAJAS DE LOS ALGORITMOS GENÉTICOS 

• Definir una representación del problema. El lenguaje utilizado para especificar soluciones candidatas debe ser robusto, debe ser capaz de tolerar cambios aleatorios que no produzcan constantemente errores fatales o resultados sin sentido. Se puede solucionar mediante la definición de los individuos como listas de números donde cada número representa algún aspecto de la solución candidata. 

• Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen -tamaño de la población, número de generaciones… 

• Pueden converger prematuramente debido a una serie de problemas. Si un individuo que es más apto que la mayoría de sus competidores emerge muy pronto en el curso de la ejecución, se puede reproducir tan abundantemente que merme la diversidad de la población demasiado pronto, provocando que el algoritmo converja hacia el óptimo local que representa ese individuo, en lugar de rastrear el paisaje adaptativo lo bastante a fondo para encontrar el óptimo global. Esto es un problema especialmente común en las poblaciones pequeñas, donde incluso una variación aleatoria en el ritmo de reproducción puede provocar que un genotipo se haga dominante sobre los otros. 


 APLICACIONES DE LOS ALGORITMOS GENÉTICOS 

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

 Su espacio de búsqueda debe estar delimitado dentro de un cierto rango. 
• Debe poderse definir una función de aptitud que nos indique qué tan buena o mala es una cierta respuesta. 
• Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora. 

Dentro de los distintos problemas de optimización podemos encontrar unas áreas de aplicación:

• Diseño por computadora de nuevos materiales que cumplan múltiples objetivos. 
• Optimización del la carga de containers. 
• Asignación de procesos en topologías de redes con procesamiento distribuido. 
• Ubicación de archivos en sistemas de almacenamiento distribuido. 
• Diseño de circuitos integrados. 
• Optimización de la infraestructura de telefonía celular. 
• Ingeniería Aeroespacial. 
• Juegos. 
• Robótica


¿Que es la Computación Evolutiva?

La computación evolutiva (en adelante CE) es una de las ramas de la Inteligencia Artificial que se aplica para la resolución de problemas de optimización combinatoria. La CE está inspirada en los mecanismos de evolución biológica propuestos por Darwin, Medel y Lamark. Sin entrar mucho en detalle sobre los estudios que hicieron estos científicos, solo vamos a mencionar brevemente lo que propusieron. Darwin propuso la "Selección natural de los más adaptados", Medel propuso la "Teoría corpuscular de la herencia" y Lamark propuso la "Herencia de caracteres adquiridos".


En la naturaleza todos los seres vivos se enfrentan a problemas que deben resolver con éxito, como conseguir más luz del sol, o cazar una mosca. La Computación Evolutiva interpreta la naturaleza como una inmensa máquina de resolver problemas y trata de encontrar el origen de dicha potencialidad para utilizarla en nuestros programas.


Algoritmos Genéticos y Sistemas Expertos

lgoritmos Genéticos y Sistemas Expertos

Un Sistema Experto es un programa de computadora que encuentra soluciones a problemas del tipo condicional con la estructura:
Si ocurren los hechos A,B,C,D , cual sería el valor del suceso E

Ejemplo: Si un análisis médico detecta los síntomas A , B , C y D en un paciente , ¿Cual será la enfermedad del sujeto?

Ejemplo: Si el análisis geológico de una capa de suelo detecta la presencia de los compuestos químicos A , B , C y D ¿Es factible que exista petróleo en la misma?.

Si bien existen en la literatura ejemplos de la utilidad de ésta técnica , las reglas deben ser provistas por un especialista ( o varios ) en el tema. Por ende , se requiere que los conocimientos estén disponibles, que sean estructurados o factibles de ser estructurados ( convertidos a reglas heurísticas ) y que los hechos de la realidad sean relativamente estáticos , es decir que las causas para arribar a una determinada conclusión no cambien , ya que cada vez que esto sucede , los expertos deben reelaborrar las reglas , lo cual dificulta y retarda considerablemente la operatoria del sistema.
Las condiciones básicas necesarias para la implementación efectiva de un sistema experto pueden observarse en el cuadro GA005.

Los Sistemas Expertos tuvieron su apogeo en la década de los 80`s , aproximadamente de 1979 a 1985. En esa época se los llegó a considerar verdaderas panaceas que resolverían muchos de los problemas cotidianos del hombre. Incluso se formaron en ese entonces varias compañías con el objeto específico de realizarlos y comercializarlos. Algunos fueron exitosos y funcionaron bien , pero las dificultades planteadas anteriormente no tardaron en aparecer. En particular:
  • Existen temas en los cuales el conocimiento no es estático , sino que la aparición de nueva información altera las pautas o reglas de inferencia de los resultados. La necesidad permanentes de reevaluar las reglas por medio de expertos humanos lleva al sistema a una operatoria lenta y burocrática. Cada conocimiento nuevo implica reentrenar manualmente el sistema. Los Sistemas Expertos demostraron no ser útiles en este campo.
  • Existen temas en los cuales la interrelación de ciertas variables no es conocida. Si la información disponible de cierto asunto es limitada , y no se conoce el comportamiento de algunas de sus variables , el Sistema experto tendrá grandes dificultades de programarse ya que sus reglas serán imprecisas.
El Cuadro GA5 muestra las condiciones básicas necesarias para la implementación efectiva de un sistema experto
  • Los expertos no siempre estructuran su conocimiento. Existen numerosas personas que razonan por métodos empíricos. Esto hace que les resulte muy difícil traducir sus pensamientos o su método deductivo a reglas que la computadora pueda interpretar. Un Sistema experto no podrá llegar a resultados valederos cuando los especialistas en un tema no puedan tener estructurados sus pensamientos. Por ejemplo: supóngase que se quiera programar un sistema experto para calificar obras de arte. Difícilmente se encontrará un crítico de arte que pueda estructurar las razones por las cuales considera "buena" o "mala" a una obra de arte. En general las palabras que pueda decir resultarán a los oídos del programador del Sistema como una serie de subjetividades imposibles de sistematizar.
Luego de observar todo esto, se empezó a considerar a los Sistemas expertos como aptos solamente para entornos reducidos y con condiciones de ejecución acotadas. La idea del Sistema Experto como "resolvedor universal de problemas " quedó sepultada.

Si bien la investigación básica de los algoritmos genéticos es contemporánea a la de los sistemas expertos , la renovada importancia que se les dio en el ámbito científico se produjo en paralelo a la desvalorización que sufrieron estos últimos.

Los algoritmos genéticos se revalorizaron ya que poseen las siguientes ventajas competitivas:
  • Solo necesitan asesoramiento del experto cuando se agregan o suprimen variables al modelo. 
  • Los Sistemas Expertos requieren la presencia del mismo ante cada modificación del entorno.
  • Los algoritmos genéticos solo requieren el asesoramiento del experto para identificar las variables pertinentes , aunque no es necesario que éstos definan sus valores ni sus relaciones (las reglas) iniciales o finales. Los Sistemas Expertos solo trabajan con las reglas y valores que les dictan los seres humanos.

lunes, 25 de septiembre de 2017

Técnicas de busqueda

Las técnicas de búsqueda son una serie de esquemas de representación del conocimiento, que mediante diversos algoritmos nos permite resolver ciertos problemas desde el punto de vista de la I.A. 

Los elementos que integran las técnicas de búsqueda son:
  - Conjunto de estados: todas las configuraciones   posibles en el dominio.
  - Estados iniciales: estados desde los que partimos.
  - Estados finales: las soluciones del problema.
  - Operadores: se aplican para pasar de un estado a   otro.
Solucionador: mecanismo que nos permite   evolucionar de un estado a otro mediante un   algoritmo aplicando los siguientes pasos:
  1.  Elegir el estado a explorar
  2. Establecer un operador que trabaje sobre el   estado elegido en el paso 1
  3. Comprobar si el resultado obtenido es un estado   final (es una solución del problema). Sino ir al paso 1

Tipos de solucionadores
Para decidir como contestar a las preguntas del solucionador podemos usar dos tipos de búsqueda:
  - Búsqueda ciega:
  - Se hace crecer el árbol de forma sistemática
  - No se realiza análisis entre el estado   obtenido y la solución
  - Búsqueda heurística:
  - El crecimiento del árbol se hace inyectando   conocimiento.
  - Este conocimiento permite calcular la   distancia entre el estado obtenido y el estado   final
Un buen solucionador será aquel que realice su función a bajo coste según los siguientes parámetros:
  - Complejidad temporal: tiempo empleado en obtener la   solución
  - Complejidad espacial: cantidad de recursos necesarios   para obtener la solución. Por ejemplo: memoria.
La explosión combinatoria es un fenómeno que hace que el problema no se pueda abordar computacionalmente.

Optimizar

En los ámbitos de la informática y la tecnología, la optimización es el proceso a través del cual se mejora la eficiencia y la rapidez en el funcionamiento de un sistema informático. En este sentido, se puede optimizar un software, un hardware, un sistema de redes, una computadora, un celular, o incluso la ejecución de un juego de PC.


La optimización de software es el proceso de modificación de un software para hacer que algún aspecto del mismo funcione de manera más eficiente y/o utilizar menos recursos (mayor rendimiento). En general, un programa puede ser optimizado para que se ejecute más rápidamente, o sea capaz de operar con menos memoria u otros recursos, o consuman menos energía.

La optimización puede ocurrir en una serie de niveles:
  • Nivel de diseño: En el nivel más alto, el diseño puede ser optimizado para aprovechar al máximo los recursos disponibles. La implementación de un proyecto se beneficiará de una buena selección de algoritmos eficientes y la aplicación de estos algoritmos se beneficiarán de la escritura de código de buena calidad. El diseño arquitectónico de un sistema mayoritariamente afecta a su rendimiento. La elección del algoritmo afecta la eficiencia más que cualquier otro elemento del diseño y, desde que la elección del algoritmo suele ser lo primero que hay que decidir, los argumentos en contra de la "optimización prematura" temprana pueden ser difíciles de justificar.

  • Nivel de código fuente: Evitar la codificación de mala calidad también puede mejorar el rendimiento, evitando ralentizaciones obvias. Después de eso, sin embargo, algunas optimizaciones pueden disminuir el mantenimiento. Algunas optimizaciones en la actualidad se pueden realizar por los compiladores optimizadores.

  • Nivel de armado: Entre el código y el nivel de compilación, directivas y flags pueden ser usados para ajustar las opciones de rendimiento en el código fuente y el compilador respectivamente, como el uso del preprocesador para desactivar características innecesarias de software, o la optimización de los modelos de procesadores específicos o capacidades de hardware.

  • Nivel de compilación: El uso de un compilador optimizador tiende a asegurar que el programa ejecutable se optimiza por lo menos tanto como el compilador puede predecir.

  • Nivel ensamblador: En el nivel más bajo, la escritura de código utilizando lenguaje ensamblador, diseñado para una plataforma de hardware particular, pueden producir el código más eficiente y compacta si el programador se aprovecha de todo el repertorio de instrucciones de la máquina.

  • Tiempo de ejecución: Los compiladores just-in- time y los programadores de ensamblador pueden ser capaz de realizar la optimización en tiempo de ejecución exdiendo la capacidad de los compiladores estáticos, ajustando dinámicamente los parámetros de acuerdo con la entrada actual u otros factores.