Algoritmos de Aproximación
Operadores genéticos (mutación y cruzamiento)Un algoritmo de aproximación es un algoritmo
usado para encontrar soluciones aproximadas a
problemas de optimización.
Están a menudo asociados con problemas NPcompletos ya que como es poco probable que alguna vez se descubran algoritmos eficientes de tiempo polinómico que resuelvan exactamente problemas NP-completos, se opta por encontrar soluciones no-óptimas en tiempo polinomial.
A diferencia los algoritmos que utilizan heurísticas, que usualmente sólo encuentran soluciones razonablemente buenas en tiempos razonablemente rápidos, lo que se busca en por parte de un algoritmo de aproximación es encontrar soluciones que está demostrado son de calidad y cuyos tiempos de ejecución están acotados por cotas conocidas.
Los algoritmos de aproximación están siendo cada vez más utilizados para resolver problemas donde los algoritmos exactos de tiempo polinomial son conocidos pero demasiado costosos debido al tamaño de la entrada.
Dichos procesos pueden contemplarse como procesos naturales de optimización. Se han propuesto varios algoritmos de optimización global que simulan estos procesos naturales.
Tres ejemplos clásicos son:
Recocido Simulado, basado en el proceso natural de enfriamiento de un sólido hasta que alcanza su punto de equilibrio.
Algoritmos Evolutivos, basados en el concepto de evolución biológica. Entre los mismos se pueden considerar las siguientes ramas : Algoritmos Genéticos, Estrategias Evolutivas, Programación Evolutiva y Programación Genética.
Redes Neuronales Artificiales, basadas en procesos relacionados con el sistema nervioso central.
Un algoritmo genético es un método de búsqueda dirigida basada en probabilidad. Bajo una condición muy débil (que el algoritmo mantenga elitismo, es decir, guarde siempre al mejor elemento de la población sin hacerle ningún cambio) se puede demostrar que el algoritmo converge en probabilidad al óptimo.
Funcionamiento de un algoritmo genético
Entre un conjunto de soluciones de un problema, llamado fenotipo, y el conjunto de individuos de una población natural, codifica la información de cada solución en una cadena, generalmente binaria, llamada cromosoma. Los símbolos que forman la cadena son llamados genes. Cuando la representación de los cromosomas se hace con cadenas de dígitos binarios se le conoce como genotipo. Los cromosomas evolucionan a través de iteraciones, llamadas generaciones. En cada generación, los cromosomas son evaluados usando alguna medida de aptitud. Las siguientes generaciones (nuevos cromosomas), operadores genéticos, de sobrecruzamiento y de mutación.
Los componentes básicos de un algoritmo genético son
Están a menudo asociados con problemas NPcompletos ya que como es poco probable que alguna vez se descubran algoritmos eficientes de tiempo polinómico que resuelvan exactamente problemas NP-completos, se opta por encontrar soluciones no-óptimas en tiempo polinomial.
A diferencia los algoritmos que utilizan heurísticas, que usualmente sólo encuentran soluciones razonablemente buenas en tiempos razonablemente rápidos, lo que se busca en por parte de un algoritmo de aproximación es encontrar soluciones que está demostrado son de calidad y cuyos tiempos de ejecución están acotados por cotas conocidas.
Los algoritmos de aproximación están siendo cada vez más utilizados para resolver problemas donde los algoritmos exactos de tiempo polinomial son conocidos pero demasiado costosos debido al tamaño de la entrada.
Determinismo
Un algoritmo de aproximación puede ser
determinista o no determinista
Si el algoritmo de aproximación es determinista, se
sabe que siempre obtendrá la misma solución para
los parámetros de entrada y esta será aproximada
según su factor de aproximación determinista.
Si el algoritmo de aproximación no es determinista
y se ejecuta muy rápidamente, es común ejecutarlo
varias veces y elegir la mejor de las soluciones
aproximadas producidas.
Factor de aproximación
Un algoritmo de aproximación bien diseñado cuenta
con un análisis formal que muestra que la diferencia
entre su solución y la solución optima es de un
factor constante.
Este factor se llama el factor de aproximación.
< 1 para maximización
> 1 para minimización
Depende de la aplicación qué tan cerca debería ser
la solución aproximada a la solución óptima
Naturaleza de los problemas
La mayoría de los problemas NP-completos de optimización se puede ver en la Naturaleza y existen muchos procesos que buscan un estado estable.Dichos procesos pueden contemplarse como procesos naturales de optimización. Se han propuesto varios algoritmos de optimización global que simulan estos procesos naturales.
Tres ejemplos clásicos son:
Recocido Simulado, basado en el proceso natural de enfriamiento de un sólido hasta que alcanza su punto de equilibrio.
Algoritmos Evolutivos, basados en el concepto de evolución biológica. Entre los mismos se pueden considerar las siguientes ramas : Algoritmos Genéticos, Estrategias Evolutivas, Programación Evolutiva y Programación Genética.
Redes Neuronales Artificiales, basadas en procesos relacionados con el sistema nervioso central.
Recocido Simulado
El recocido simulado, o enfriamiento simulado es un algoritmo de
búsqueda meta-heurística para problemas de optimización global;
el objetivo general de este tipo de algoritmos es encontrar una
buena aproximación al valor óptimo de una función en un espacio
de búsqueda grande. A este valor óptimo se lo denomina "óptimo
global"
El nombre e inspiración viene del proceso de recocido del acero y
cerámicas, una técnica que consiste en calentar y luego enfriar
lentamente el material para variar sus propiedades físicas. El calor
causa que los átomos aumenten su energía y que puedan así
desplazarse de sus posiciones iniciales (un mínimo local de
energía); el enfriamiento lento les da mayores probabilidades de
recristalizar en configuraciones con menor energía que la inicial
(mínimo global).
El método fue descrito independientemente por Scott Kirkpatrick, C.
Daniel Gelatt y Mario P. Vecchi en 1983,2 y por Vlado Černý en 1985.
El método es una adaptación del algoritmo Metropolis-Hastings, un
método de Montecarlo utilizado para generar muestras de estados de un
sistema termodinámico.
En cada iteración, el método de recocido simulado evalúa algunos
vecinos del estado actual s y probabilísticamente decide entre efectuar
una transición a un nuevo estado s' o quedarse en el estado s. En el
ejemplo de recocido de metales, el estado s se podría definir en función
de la posición de todos los átomos del material en el momento actual; el
desplazamiento de un átomo se consideraría como un estado vecino del
primero en este ejemplo. Típicamente la comparación entre estados
vecinos se repite hasta que se encuentre un estado óptimo que minimice
la energía del sistema o hasta que se cumpla cierto tiempo
computacional u otras condiciones.
Algoritmos Evolutivos
Los algoritmos evolutivos son métodos de optimización y
búsqueda de soluciones basados en los postulados de la evolución
biológica. En ellos se mantiene un conjunto de entidades que
representan posibles soluciones, las cuales se mezclan, y compiten
entre sí, de tal manera que las más aptas son capaces de
prevalecer a lo largo del tiempo, evolucionando hacia mejores
soluciones cada vez.
Los algoritmos evolutivos, y la computación evolutiva, son una
rama de la inteligencia artificial. Son utilizados principalmente en
problemas con espacios de búsqueda extensos y no lineales, en
donde otros métodos no son capaces de encontrar soluciones en
un tiempo razonable.
Siguiendo la terminología de la teoría de la evolución, las entidades
que representan las soluciones al problema se denominan
individuos o cromosomas, y el conjunto de éstos, población. Los
individuos son modificados por operadores genéticos,
principalmente el sobrecruzamiento, que consiste en la mezcla de
la información de dos o más individuos; la mutación, que es un
cambio aleatorio en los individuos; y la selección, consistente en la
elección de los individuos que sobrevivirán y conformarán la
siguiente generación. Dado que los individuos que representan las
soluciones más adecuadas al problema tienen más posibilidades de
sobrevivir, la población va mejorando gradualmente.
Suele hablarse de tres paradigmas principales de algoritmos evolutivos:
- Programación evolutiva
- Estrategias evolutivas
- Algoritmos genéticos
Cada uno de estos paradigmas se originó independientemente y con
distintas motivaciones. Actualmente, los algoritmos tienden a combinar
características de éstos tres y a incluir mecanismos de otros campos de
estudio, tales como el aprendizaje automático, otros algoritmos de
búsqueda, o diferentes estructura de datos. Algunas de las tendencias
actuales son las siguientes:
- Evolución diferencial
- Modelos probabilísticos
- Evolución simulada
- Algoritmos culturales
- Algoritmos meméticos
- Programación genética
Algoritmos Genéticos
Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular. Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.Un algoritmo genético es un método de búsqueda dirigida basada en probabilidad. Bajo una condición muy débil (que el algoritmo mantenga elitismo, es decir, guarde siempre al mejor elemento de la población sin hacerle ningún cambio) se puede demostrar que el algoritmo converge en probabilidad al óptimo.
Funcionamiento de un algoritmo genético
Entre un conjunto de soluciones de un problema, llamado fenotipo, y el conjunto de individuos de una población natural, codifica la información de cada solución en una cadena, generalmente binaria, llamada cromosoma. Los símbolos que forman la cadena son llamados genes. Cuando la representación de los cromosomas se hace con cadenas de dígitos binarios se le conoce como genotipo. Los cromosomas evolucionan a través de iteraciones, llamadas generaciones. En cada generación, los cromosomas son evaluados usando alguna medida de aptitud. Las siguientes generaciones (nuevos cromosomas), operadores genéticos, de sobrecruzamiento y de mutación.
- Operadores genéticos (mutación y cruzamiento)
- Una representación apropiada del problema a resolver
- Una función de Oportunidad o bien llamada de Aptitud (fitness)
- Un procedimiento de inicialización
RedesNeuronales
Las redes de neuronas artificiales son un paradigma
de aprendizaje y procesamiento automático
inspirado en la forma en que funciona el sistema
nervioso de los animales. Se trata de un sistema de
interconexión de neuronas que colaboran entre sí
para producir un estímulo de salida.
Consisten en unidades de procesamiento
densamente interconectadas , llamadas neuronas
por su similaridad funcional con las neuronas
biológicas. Las unidades de procesamiento reciben,
pro-cesan y transmiten señales, tal como las
neuronas biológicas
Composición de las redes neuronales artificiales
Los nueve componentes principales del funcionamiento de
las Redes Neuronales Artificiales son:
- Un conjunto de unidades de procesamiento (neuronas);
- Un estado de activación (variable de estado);
- Una función de salida para cada unidad;
- Un conjunto de conexiones (patrón de conectividad);
- Un conjunto de reglas de propagación para propagar las señales de salida a través de la RNA.
- Una regla de combinación
- Una regla de activación
- Una regla de modificación
- Un ambiente en el cual opera la RNA
Ejemplo: RedNeuronal Perceptrón Multicapa
Comentarios
Publicar un comentario