26 de junio de 2014

¿Qué es el soft computing?

El soft computing es un conjunto de técnicas y métodos computacionales inexactos para solucionar problemas, en muchos casos de optimización, muy difíciles, en los cuales no tenemos las ventajas de la convexidad, continuidad, diferenciabilidad y condiciones que nos permiten usar métodos tan rápidos y poderosos como los son los métodos basados en gradientes o cuasi-newton. O bien funciones para las que tenemos información incompleta.

Algunas de las areas y algorítmos populares del soft computing son las siguientes:


Por interés personal he decidido de manera arbitraria iniciar esta exposición (serie de exposiciones) con evolución diferencial.

Nota: Sin pérdida de generalidad, supondremos todos los problemas de optimización como problemas de minimización, pues de tratarse de un problema de maximización es posible transformarlo a uno de minimización.

Evolución diferencial


Intuición


Se trata de un algoritmo que entra en las categorias de computación evolutiva, metaheurística e  inteligencia poblacional/de enjambre. La idea de esta heurística creada por Storn & Price[], es emular el proceso evolutivo creando poblaciones de individuos. Cada individuo tiene cierta aptitud, la aptitudo es un criterio de supervivencia o para evaluar la calidad del individuo. Cualquier par de individuos puede tener un hijo mediante cruza, después de esta cruza los cromosomas del individuo pueden mutar.

El ciclo de cruza, mutación, muerte, se repite por un cierto número de iteraciones, o se puede elegir algún otro criterio.


Sea $f:R^D \rightarrow R$ la función a minimizar.
Y sea  $x\in R^D$ algún individuo en la población.

Algoritmo


  1. Inicializar NP individuos X aleatoriamente
  2. Por cada X en la población
    • Elegir 3 individuos r1, r2 y r3, distintos entre sí y distintos a x
    • Elegir $R\in{1,2,...,D}$ aleatoriamente
    • Por cada $i \in {1,..,R} generar un $r_i \sim U(0,1)$
      • Si $r_i
  3. Si el criterio de terminación no se ha cumplido ir a 2
  4. Elegir al individuo más apto (cuyo valor en f sea menor) y regresarlo como mejor solución
(Aquí dejo una versión que acabo de programar y subir a github:)

Código



Obviamente está inspirado de la versión original de Price y Storn.