Una clase para gobernarlos a todos.

AISearch

AISearch es una implementación propia de los algoritmos de búsqueda populares en textos de investigación, con objeto de tener un toolbox fácil de implementar, así como poder cambiar la resolución del problema con distintos algoritmos de forma sencilla. Buscando tener un punto de partida para analizarlos, compararlos o diseñar nuevas estrategias, enfocándose únicamente en los operadores del algoritmo.

Los algoritmos de búsqueda metaheurísticos que utilizan una población de soluciones, buscan mejorar esta población de soluciones mediante un proceso iterativo que hace uso de la información acumulada durante todo el proceso, o bien la disponible en cada iteración. El proceso de estos puede ser abstraído en conjunto con el siguiente diagrama de flujo.

Untitled Diagram (2)

Estos algoritmos comparten múltiples procesos en común, y aunque estos algoritmos pueden ser implementados de múltiples formas, también pueden ser organizados a manera de clases, para trabajar con ellos en un paradigma de programación orientada a objetos. De esta forma pueden compartir una gran parte de las funciones que los componen, y ser mejor comprendidos y analizados únicamente en el núcleo de los operadores que los definen.

Uno no simplemente implementa todos los algoritmos

Hacer uso de la orientación a objetos, trae consigo múltiples beneficios, entre ellos un mayor reúso del código, encapsulación, y un mejor mantenimiento y optimización del código. Aunque esta entrada no busca desarrollar el tema de programación orientada a objetos, una introducción sencilla puede encontrarse en wikipedia.

Con este objetivo en mente, el primer paso entonces es describir la clase principal, que contiene todas las propiedades y métodos que pueden ser compartidos por cada uno de los diferentes algoritmos. Por ejemplo, todos ellos tienen un arreglo donde almacenan la información de la soluciones que se encuentran actualmente en la población. Así mismo un vector con la información de asociada de desempeño por cada solución. Todos ellos comienzan con una población inicial aleatoria, por lo que tener una sola función para realizar este proceso permite que puedan ser comparados equitativamente, o bien que si esta función es mejorada, o se arregla algún error dentro de ella, haciendo cambio de esta, todos los algoritmos se beneficiaran de dicho cambio.

Las propiedades consideradas para esta clase principal son:

 properties
        sizePopulation = 30;
        noDimensions = 1;
        population = [];            %size = (sizePop, NoDim)
        fitness = [];               %size = (sizePop, 1)
        bestSolution = [];
        bestFitness = inf;
        fitnessFunction;
        numberOfFunctionCalls = 0;
        maxNoIterations = 100;
        actualIteration = 0;
 end

Los métodos que estos algoritmos comparten tienen que ver con la población, su fitness, ordenamiento, entre otras utilidades que pueden ser parte o no de los algoritmos, como la visualización gráfica de la información. A continuación citaremos cada uno de ellos.

  • Población Inicial: Usualmente estos algoritmos comienzan con un conocimiento nulo del problema que están buscando resolver de forma optima. Por lo que sus primeros intentos comienzan con soluciones totalmente aleatorias.
function initialPopulation(obj, sizePopulation, noDimensions)
   obj.population = rand(sizePopulation, noDimensions);
end
  • Evaluación de la Población: Cada solución en la población debe ser evaluada para conocer su valor de desempeño, este valor indica la superioridad de las soluciones sobre las demás. Usualmente este valor busca ser maximizado o bien minimizado.
function fit = evalPopulation(obj, population)
   fit = zeros(size(population,1),1);
   for i=1:size(population,1)
     fit(i) = obj.fitnessFunction(population(i,:));
   end
end
  • Ordenamiento de la población: Algunas veces es conveniente tener la población ordenada de acuerdo a su valor de desempeño, de forma que las mejores soluciones se encuentren primero. Aunque este proceso es conocido por ser costoso computacionalmente, por lo que su uso debe ser limitado.
function sortPopulation(obj)
   temp = sortrows([obj.fitness, obj.population], 1);
   obj.fitness = temp(:,1);
   obj.population = temp(:,2:end);
end
  • Revisar los limites de búsqueda: En ocasiones los algoritmos utilizan operadores que pueden sacar de los limites permisibles a las variables que estás siendo controladas en las soluciones. Debido a que la solución que se busca esta restringida en un área bien delimitada, soluciones fuera de esta área no deben ser aceptadas. Por lo que esta función busca entre la población soluciones que tengan variables fuera del rango permisible y las reúbica en el limite permitido.
function solutions = checkBounds(obj, solutions)
   solutions(solutions>1)=1;
   solutions(solutions<0)=0;
end

Para esta implementación consideramos que todos los problemas trabajan variables en el rango de 0 a 1, y estas son escaladas para cada problema en el rango de interés de los mismos.

  • Actualiza la mejor solución: Es común que los algoritmos utilicen la mejor solución encontrada en todo el proceso evolutivo para guiar el movimiento o evolución de la población, para ello este valor debe ser actualizado en cada iteración.
function updateBest(obj)
   [bestFitTemp, bestIndex] = min(obj.fitness);
   if bestFitTemp < obj.bestFitness
      obj.bestSolution = obj.population(bestIndex,:);
      obj.bestFitness = bestFitTemp;
   end
end
  • Ejecución del algoritmo: Este método se encarga de iniciar el proceso de búsqueda, y mantener la evolución del proceso por el número de iteraciones definidas en la clase. Es importante el orden en el que los otros métodos son llamados, así como el método llamado operadores (operators) que es la implementación del algoritmo en sí.
function start(obj)
   obj.initialPopulation();
   obj.evalPopulation();
   for i=1:obj.maxNoIterations
      obj.actualIteration = i;
      obj.operators();
      obj.updateBest();
   end
end

El metodo operators se define como abstracto, por lo que cada subclase (cada algoritmo) debe definirlo. Este método se encarga de modificar las soluciones actuales con la información recibida, y se espera que devuelva la población con las nuevas soluciones junto con el valor de desempeño de las mismas. Esto lo puede hacer internamente o bien utilizando la función definida en la clase base.

  • Otras: Existen otras funciones que son compartidas entre los algoritmos relacionadas en la forma en la que se presenta la información del proceso de evolución, o bien los resultados obtenidos. Estas funciones pueden encontrarse en el repositorio de GitHub.

Cómo un ejemplo de la implementación del algoritmo, dejó el código del método operators del algoritmo basado en enjambre de particulas (PSO), que será mejor explicado en otra ocación:

function operators(obj)
   % atraction to the best personal solution
   pbAtraction = rand(obj.sizePopulation,obj.noDimensions) .* ...
        (obj.bestPersonal(:,2:end)-obj.population);

   % atraction to the best global solution
   bestAtraction = rand(obj.sizePopulation,obj.noDimensions) .* ...
        (repmat(obj.bestSolution, obj.sizePopulation, 1) - obj.population);

   % update velocity trayectories.
   obj.velocity = obj.velocityParam * obj.velocity + ...
        obj.bestPersonalParam * pbAtraction + ...
        obj.bestParam * bestAtraction;

   % update solutions
   obj.population = obj.population + obj.velocity;
   obj.checkBounds();

   % eval fitness
   obj.evalPopulation();
end

Cada función contiene código extra que revisa las condiciones de las variables, y permite un uso mas dinámico de estos métodos. Pero el concepto clave fue expuesto en este documento. Si tienes alguna duda o comentario sobre algún código en esta implementación déjanos saber en la sección de abajo.

Una clase para gobernarlos a todos.