Ejecución de pruebas

Algoritmos de optimización evolutiva

James McCaffrey

Descargar el ejemplo de código

Un algoritmo de optimización evolutiva es la implementación de una meta heurística modelada a partir del comportamiento de la evolución biológica. Estos algoritmos se pueden usar para descubrir soluciones aproximadas para problemas de minimización numérica difíciles o imposibles. Existen tres razones por las que puede interesarse en los algoritmos de optimización evolutiva. Primero, saber cómo codificar estos algoritmos puede ser un complemento práctico para sus habilidades como desarrollador, administrador y evaluador. Segundo, algunas de las técnicas usadas, como la selección de torneo, se pueden reutilizar en otros algoritmos y de escenarios de codificación. Y tercero, muchos ingenieros simplemente encuentran que estos algoritmos son interesantes en sí mismos.

Un algoritmo de optimización evolutiva es fundamentalmente un tipo de algoritmo genético en que los cromosomas virtuales se crean a partir de valores reales, en vez de alguna representación de bits. La Ilustración 1 y la Ilustración 2 ejemplifican muy bien lo que pretendo.

Ilustración 1 La función de Schwefel

Ilustración 2 Demostración de la optimización evolutiva

El gráfico de la Ilustración 1 muestra la función Schwefel, un problema minimización numérica estándar para realizar pruebas comparativas. La función de Schwefel se define como:

f(x,y) = (-x * sin(sqrt(abs(x)))) + (-y * sin(sqrt(abs(y))))

La función posee un valor mínimo de -837,9658 cuando x = y = 420,9687. En la Ilustración 1, este valor mínimo se encuentra en la esquina al extremo izquierdo del gráfico. La función se diseñó intencionalmente para ser difícil de resolver mediante algoritmos de optimización, debido a la gran cantidad mínimos locales falsos.

La captura de pantalla en la Ilustración 2 muestra los resultados de una aplicación de consola en C#. Después de mostrar algunos mensajes informativos, el programa configura ocho parámetros y luego emplea un algoritmo evolutivo para buscar la solución óptima. En este ejemplo, el algoritmo descubrió la mejor solución de (420,9688, 420,9687), que es bastante cercana, pero no exactamente igual a la solución óptima de (420,9687, 420,9687).

Los algoritmos de optimización evolutiva modelan una solución, del mismo modo como un cromosoma lo hace para un individuo. En pseudocódigo de alto nivel, el algoritmo implementado en la Ilustración 2 es:

initialize a population of random solutions
determine best solution in population
loop
  select two parents from population
  make two children from the parents
  place children into population
  make and place an immigrant into population
  check if a new best solution exists
end loop
return best solution found

En las secciones que siguen, presentaré todo el código que generó la captura de pantalla en la Ilustración 2. Puede acceder al código en archive.msdn.microsoft.com/mag201206TestRun. Este artículo supone que cuenta con conocimientos de programación intermedias o avanzadas y, por lo menos, un conocimiento básico sobre los algoritmos genéticos. Codifiqué el programa de demostración en C#, pero no debería tener problemas para refactorizarlo para otro lenguaje como Visual Basic .NET o IronPython.

Estructura del programa

La estructura general del programa aparece en la Ilustración 3. Usé Visual Studio 2010 para crear un nuevo proyecto de aplicación de consola C# llamado EvolutionaryOptimization. En la ventana del Explorador de soluciones, cambié el nombre de Program.cs a EvolutionaryOptimizationProgram.cs, lo que automáticamente cambió el nombre de la clase Program. También borré todas las instrucciones using innecesarias generadas por las plantillas.

Ilustración 3 Estructura general del programa EvolutionaryOptimization

using System;
namespace EvolutionaryOptimization
{
  class EvolutionaryOptimizationProgram
  {
    static void Main(string[] args)
    {
      try
      {
        int popSize = 100;
        int numGenes = 2;
        double minGene = -500.0; double maxGene = 500.0;
        double mutateRate = 1.0 / numGenes;
        double precision = 0.0001;
        double tau = 0.40;
        int maxGeneration = 8000;
        Evolver ev = new Evolver(popSize, numGenes, 
          minGene, maxGene, mutateRate,
          precision, tau, maxGeneration);
        double[] best = ev.Evolve();
        Console.WriteLine("\nBest solution found:");
        for (int i = 0; i < best.Length; ++i)
          Console.Write(best[i].ToString("F4") + " ");
        double fitness = Problem.Fitness(best);
        Console.WriteLine("\nFitness of best solution = " 
          + fitness.ToString("F4"));
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
      }
    }
  }
  public class Evolver
  {
    // Member fields
    public Evolver(int popSize, int numGenes, 
      double minGene, double maxGene,
      double mutateRate, double precision, 
      double tau, int maxGeneration) { ... }
    public double[] Evolve() { ... }
    private Individual[] Select(int n) { ... }
    private void ShuffleIndexes() { ... }
    private Individual[] Reproduce(Individual parent1, 
      Individual parent2) { ... }
    private void Accept(Individual child1, 
      Individual child2) { ... }
    private void Immigrate() { ... }
  }
  public class Individual : IComparable<Individual>
  {
    // Member fields
    public Individual(int numGenes, 
      double minGene, double maxGene,
      double mutateRate, double precision) { ... }
    public void Mutate() { ... }
    public int CompareTo(Individual other) { ... }
  }
  public class Problem
  {
    public static double Fitness(double[] chromosome) { ... }
  }
} // NS

Además de la clase principal del programa, la demostración EvolutionaryOptimization posee tres clases definidas por el programa. La clase Evolver contiene la mayor parte de la lógica del algoritmo. La clase Individual modela una solución posible para el problema de minimización. La clase Problem define la función que se minimizará y en este caso corresponde a la función de Schwefel. Otra estructura de diseño posible sería colocar la clase Individual dentro de la clase Evolver.

La clase Individual

La definición de la clase Individual comienza así:

public class Individual : IComparable<Individual>
{
  public double[] chromosome;
  public double fitness;
  private int numGenes;
  private double minGene;
  private double maxGene;
  private double mutateRate;
  private double precision;
  static Random rnd = new Random(0);
...

La clase se hereda de la interfaz IComparable para que las matrices de objetos Individual se puedan organizar automáticamente según su aptitud. La clase posee ocho miembros de datos. La matriz chromosome representa una posible solución para el problema objetivo. Observe que chromosome es una matriz de double, en vez de ser una matriz con cierta forma de representación de bits, que los algoritmos genéticos usan típicamente. Los algoritmos de optimización evolutiva algunas veces se conocen como algoritmos de genética con valoración real.

El campo fitness es una medida de qué tan buena es la solución de chromosome. Para los problemas de minimización, los valores más pequeños de fitness son mejores que los más grandes. Para simplificar las cosas, chromosome y fitness se declaran con alcance público para que la lógica en la clase Evolver los pueda ver. Un gen es un valor en la matriz chromosome y el campo numGenes contiene la cantidad de valores reales en una posible solución. Para la función de Schwefel, este valor se establece en 2. En varios problemas de optimización numérica, se pueden especificar los valores mínimos y máximos para cada gen y estos valores se almacenan en minGene y maxGene. Si se desconocen estos valores, minGene y maxGene se pueden configurar como double.MinValue y double.MaxValue. Explicaré los campos mutateRate y precision cuando presente el código que los usa.

La definición de la clase Individual continúa con el constructor de la clase:

public Individual(int numGenes, double minGene, double maxGene,
  double mutateRate, double precision)
{
  this.numGenes = numGenes;
  this.minGene = minGene;
  this.maxGene = maxGene;
  this.mutateRate = mutateRate;
  this.precision = precision;
  this.chromosome = new double[numGenes];
  for (int i = 0; i < this.chromosome.Length; ++i)
    this.chromosome[i] = (maxGene - minGene) 
    * rnd.NextDouble() + minGene;
  this.fitness = Problem.Fitness(chromosome);
}

El constructor asigna memoria para la matriz chromosome y asigna valores aleatorios en el intervalo (minGene, maxGene) para cada celda del gen. Observe que el valor del campo fitness se configura al llamar el método Fitness definido externamente. De manera alternativa, podríamos pasar una referencia al método Fitness en el constructor a través de un delegado. El método Mutate se define del siguiente modo:

public void Mutate()
{
  double hi = precision * maxGene;
  double lo = -hi;
  for (int i = 0; i < chromosome.Length; ++i) {
    if (rnd.NextDouble() < mutateRate)
      chromosome[i] += (hi - lo) * rnd.NextDouble() + lo;
  }
}

La operación de mutación avanza por la matriz chromosome, establece algunos genes elegidos al azar en valores aleatorios en el intervalo (lo, hi). El intervalo de los valores que se asignan depende de los valores de los miembros precision y maxGene. En el ejemplo que aparece en la Ilustración 2, precision está configurado como 0,0001 y maxGene como 500. El valor máximo posible para la mutación de un gen es 0,0001 * 500 = 0,05, lo que significa que al mutar, el valor nuevo del gen será el valor antiguo más o menos un valor aleatorio entre -0,05 y +0,05. Observe que el valor precision corresponde la cantidad de cifras decimales en la solución; esto es un valor heurístico razonable la precision. El valor de la tasa de mutación controla cuántos genes del cromosoma se modificarán. Una heurística para el valor del campo mutateRate es para usar 1,0 / numGenes, para que se mute un gen del cromosoma en promedio cada vez que se llama Mutate.

La definición de la clase Individual concluye con el método CompareTo:

...
  public int CompareTo(Individual other)
  {
    if (this.fitness < other.fitness) return -1;
    else if (this.fitness > other.fitness) return 1;
    else return 0;
  }
}

El método CompareTo define un orden predeterminado para los objetos Individual, en este cado desde el fitness menor (el mejor) hasta el mayor.

La clase Problem

La clase Problem encapsula el problema objetivo para el algoritmo evolutivo:

public class Problem
{
  public static double Fitness(double[] chromosome)
  {
    double result = 0.0;
    for (int i = 0; i < chromosome.Length; ++i)
      result += (-1.0 * chromosome[i]) *
        Math.Sin(Math.Sqrt(Math.Abs(chromosome[i])));
    return result;
  }
}

Como la matriz chromosome representa una posible solución, se pasa como un parámetro de entrada al método Fitness. En el caso de los problemas de minimización arbitrarios, la función objetivo que se debe minimizar generalmente se llama función de costo. En el contexto de los algoritmos evolutivos y genéticos, sin embargo, la función generalmente se llama función de fitness. Observe que la terminología es un poco extraña, ya los valores de fitness más bajos son mejores que los valores más altos. En este ejemplo, la función fitness es completamente autónoma. En muchos problemas de optimización, la función de fitness requiere parámetros de entrada adicionales, como una matriz de datos o una referencia a un archivo de datos externo.

La clase Evolver

La definición de la clase Evolver comienza así:

public class Evolver
{
  private int popSize;
  private Individual[] population;
  private int numGenes;
  private double minGene;
  private double maxGene;
  private double mutateRate;
  private double precision;
  private double tau;
  private int[] indexes;
  private int maxGeneration;
  private static Random rnd = null;
...

El miembro popSize contiene la cantidad de individuos de la población. Valores mayores de popSize tienden a incrementar la precisión del algoritmo a expensas de la velocidad. En general, los algoritmos evolutivos son mucho más rápidos que los algoritmos genéticos normales, ya que los primeros trabajan a partir de valores reales y sufren de la sobrecarga que resulta de la conversión y manipulación de las representaciones de bits. El corazón de la clase Evolver es una matriz de objetos Individual llamada population. El método Selection usa los miembros tau e indexes, como veremos pronto.

La definición de la clase Evolver continúa con la definición del constructor que aparece en la Ilustración 4.

Ilustración 4 Constructor de la clase Evolver

public Evolver(int popSize, int numGenes, double minGene, double maxGene,
  double mutateRate, double precision, double tau, int maxGeneration)
{
  this.popSize = popSize;
  this.population = new Individual[popSize];
  for (int i = 0; i < population.Length; ++i)
    population[i] = new Individual(numGenes, minGene, maxGene,
      mutateRate, precision);
  this.numGenes = numGenes;
  this.minGene = minGene;
  this.maxGene = maxGene;
  this.mutateRate = mutateRate;
  this.precision = precision;
  this.tau = tau;
  this.indexes = new int[popSize];
  for (int i = 0; i < indexes.Length; ++i)
    this.indexes[i] = i;
  this.maxGeneration = maxGeneration;
  rnd = new Random(0);
}

El constructor asigna memoria para la matriz population y luego usa el constructor de Individual para llenar la matriz con individuos que poseen genes aleatorios. El método Select, que usa la matriz indexes, elige dos padres. Explicaré indexes más adelante, pero observe que el constructor asigna una celda por individuo y asigna secuencialmente enteros de 0 a popSize-1.

El método Evolve, que aparece en la Ilustración 5, es sorprendentemente corto.

Ilustración 5 Método Evolve

public double[] Evolve()
{
  double bestFitness = this.population[0].fitness;
  double[] bestChomosome = new double[numGenes];
  population[0].chromosome.CopyTo(bestChomosome, 0);
  int gen = 0;
  while (gen < maxGeneration)  {
    Individual[] parents = Select(2);
    Individual[] children = Reproduce(parents[0], parents[1]);
    Accept(children[0], children[1]);
    Immigrate();
    for (int i = popSize - 3; i < popSize; ++i)  {
      if (population[i].fitness < bestFitness)  {
        bestFitness = population[i].fitness;
        population[i].chromosome.CopyTo(bestChomosome, 0);
      }
    }
    ++gen;
  }
  return bestChomosome;
}

El método Evolve devuelve la mejor solución encontrada como una matriz del tipo double. De manera alternativa, podríamos devolver un objeto Individual con el cromosoma que represente la mejor solución encontrada. El método Evolve comienza por inicializar el mejor fitness y los mejores cromosomas en los primeros de la población. El método itera exactamente maxGenerations veces, y usa gen (generación) como el contador del bucle. Una de varias alternativas posibles es detenerlo cuando no hayan ocurrido mejoras después de un número dado de iteraciones. El método Select devuelve dos individuos buenos, pero no necesariamente los mejores de la población. Estos dos padres se pasan a Reproduce, que crea y devuelve dos hijos. El método Accept reemplaza dos individuos existentes en la población por los hijos. El método Immigrate genera un individuo nuevo aleatorio y lo coloca en la población. La población nueva luego se inspecciona para ver si alguno de los tres individuos nuevos en la población es una nueva mejor solución.

El método Select se define como:

private Individual[] Select(int n)
{
  int tournSize = (int)(tau * popSize);
  if (tournSize < n) tournSize = n;
  Individual[] candidates = new Individual[tournSize];
  ShuffleIndexes();
  for (int i = 0; i < tournSize; ++i)
    candidates[i] = population[indexes[i]];
  Array.Sort(candidates);
  Individual[] results = new Individual[n];
  for (int i = 0; i < n; ++i)
    results[i] = candidates[i];
  return results;
}

El método acepta el número de individuos buenos que se seleccionarán y los devuelve en una matriz del tipo Individual. Para minimizar la cantidad de código, omití la comprobación normal de errores, como el control si la cantidad de individuos solicitados es menor que el tamaño de la población. El método Select usa una técnica llamada selección por torneo. Se genera un subconjunto de individuos candidatos aleatorios y se devuelven los n mejores de ellos. El número de candidatos se calcula en la variable tournSize, que corresponde a la fracción tau del total de la población. Valores mayores de tau aumentan la probabilidad de seleccionar los dos individuos mejores.

Recuerde que la clase Evolver posee una matriz de miembro llamada indexes que contiene valores entre 0 y popSize-1. El método auxiliar ShuffleIndexes reordena los valores de la matriz indexes en orden aleatorio. Los primeros n valores de estos índices aleatorios se usan para elegir los candidatos de la población. El método Array.Sort luego ordena los candidatos según el valor de fitness de menor (mejor) a mayor. Se devuelven los n individuos mejores de los candidatos ordenados. Existen varios algoritmos de selección evolutiva. Una ventaja de la selección por torneo comparada con la mayoría de las técnicas es que la presión de selección se puede ajustar mediante parámetro tau.

El método auxiliar ShuffleIndexes usa el algoritmo de ordenamiento aleatorio estándar Fisher-Yates:

private void ShuffleIndexes()
{
  for (int i = 0; i < this.indexes.Length; ++i) {
    int r = rnd.Next(i, indexes.Length);
    int tmp = indexes[r];
    indexes[r] = indexes[i];
    indexes[i] = tmp;
  }
}

El método Reproduce se muestra en la Ilustración 6. El método comienza con la generación de un punto de entrecruzamiento aleatorio. La indización es un poco complicada, pero child1 se forma a partir de la parte izquierda de parent1 y la parte derecha de parent2. Child2 se forma a partir de la parte izquierda de parent2 y la parte derecha de parent1. La idea se muestra en la Ilustración 7, donde hay dos padres con cinco genes y el punto de entrecruzamiento es 2. Otro diseño común emplea varios puntos de entrecruzamiento. Después de crear objetos de los hijos Individual se crean, estos se mutan y se calculan los valores nuevos de fitness.

Ilustración 6 Método Reproduce

private Individual[] Reproduce(Individual parent1, Individual parent2)
{
  int cross = rnd.Next(0, numGenes - 1);
  Individual child1 = new Individual(numGenes, minGene, maxGene,
    mutateRate, precision);
  Individual child2 = new Individual(numGenes, minGene, maxGene,
     mutateRate, precision);
  for (int i = 0; i <= cross; ++i)
    child1.chromosome[i] = parent1.chromosome[i];
  for (int i = cross + 1; i < numGenes; ++i)
    child2.chromosome[i] = parent1.chromosome[i];
  for (int i = 0; i <= cross; ++i)
    child2.chromosome[i] = parent2.chromosome[i];
  for (int i = cross + 1; i < numGenes; ++i)
    child1.chromosome[i] = parent2.chromosome[i];
  child1.Mutate(); child2.Mutate();
  child1.fitness = Problem.Fitness(child1.chromosome);
  child2.fitness = Problem.Fitness(child2.chromosome);
  Individual[] result = new Individual[2];
  result[0] = child1; result[1] = child2;
  return result;
}

Ilustración 7 El mecanismo de entrecruzamiento

El método Accept agrega los dos individuos hijos creados por Reproduce a la población:

private void Accept(Individual child1, Individual child2)
{
  Array.Sort(this.population);
  population[popSize - 1] = child1;
  population[popSize - 2] = child2;
}

La matriz population se ordena según fitness, lo que deja los dos peores individuos en las últimas dos celdas de la matriz, donde luego se reemplazan por los hijos. Existen varias alternativas para elegir los dos individuos que mueren. Una posibilidad es usar una técnica llamada selección de la rueda de ruleta para seleccionar los individuos que se reemplazarán en forma probabilística, donde los peores individuos tienen una mayor probabilidad de ser reemplazados.

El método Immigrate genera un nuevo individuo aleatorio y lo coloca en la población inmediatamente encima de la ubicación de los dos hijos que se acaban de generar (la inmigración ayuda a evitar que los algoritmos evolutivos se queden en soluciones locales mínimas; algunos diseños alternativos son la creación de más de un inmigrante y colocarlo en una ubicación aleatoria en la población, entre otras):

private void Immigrate()
{
  Individual immigrant =
    new Individual(numGenes, minGene, maxGene, mutateRate, precision);
  population[popSize - 3] = immigrant;
}

Punto de inicio para experimentar

En este artículo, la optimización evolutiva se usa para calcular el valor mínimo de una ecuación matemática. Si bien los algoritmos de optimización evolutiva se pueden usar de esta forma, su uso más común es para buscar los valores de un conjunto de parámetros numéricos en un problema de optimización mayor para el que no existe un algoritmo determinista eficaz. Por ejemplo, al usar una red neuronal para clasificar datos existentes con el fin de predecir datos futuros, el principal desafío consiste en determinar un conjunto de ponderaciones y sesgos para las neuronas. El uso de un algoritmo de optimización evolutiva es un método posible para calcular los valores óptimos de las ponderaciones y sesgos. En la mayoría de los casos, los algoritmos de optimización evolutiva no se prestan bien para los problemas de optimización combinatoria no numérica, como el problema del viajante, cuyo objetivo es buscar la combinación de ciudades con la ruta total más corta.

Los algoritmos evolutivos, al igual que los algoritmos genéticos puros, son meta heurísticas. Esto significa que son un marco general y un conjunto de pautas conceptuales que sirven para crear un algoritmo específico con el fin de resolver un problema específico. Por lo tanto, el ejemplo de este artículo se puede ver más como un punto de partida para la experimentación y creación de un código de optimización evolutiva que como una base de código estática y fija.

El Dr. James McCaffreytrabaja en Volt Information Sciences Inc., donde está a cargo del entrenamiento técnico de los ingenieros informáticos que trabajan en el campus de Microsoft en Redmond, Washington. Ha colaborado en el desarrollo de varios productos de Microsoft como, por ejemplo, Internet Explorer y MSN Search. Es el autor de “.NET Test Automation Recipes” (Apress, 2006) y se puede ubicar en la dirección de correo electrónico jammc@microsoft.com.

Gracias al siguiente experto técnico de Microsoft por su ayuda en la revisión de este artículo: Anne Loomis Thompson