METODOS MATEMATICOS EN CIENCIAS DE LA COMPUTACION 07-08
UNIVERSIDAD DEL PAIS VASCO - EUSKAL HERRIKO UNIBERTSITATEA, UPV-EHU

       PEQUEÑO DICCIONARIO-GUÍA "AD-HOC" PARA ALGORITMOS EVOLUTIVOS

    Recuerda que estamos en el campo de la computación evolutiva - evolutionary computation, o de los heurísticos de búsqueda - search heuristics. Heurístico es una palabra que proviene del griego, y que a nivel intuitivo significa "truco". La mayoría de los heurísticos de búsqueda tienen son de naturaleza aleatoria - estocástica - stochastic, con un componente de azar - random. Realizamos una búsqueda heurística, ya que el visitar todas las posibles soluciones - exhaustive search, en un espacio tan grande de soluciones, necesitaría una necesidades de cómputo ingentes - CPU times, recursos de cómputo - computation resources: suele decirse que este tipo de problemas que veremos durante el curso son NP-duros NP-hard: este acrónimo (siglas) viene a decirnos que no existe un algoritmo que resuelva (encuentre el óptimo global) el problema en un tiempo polinómico - poder expresar mediante una ecuación la estimación de tiempo necesaria para poder resolverlo (NP ≈ non polynomial) (mira en la Wikipedia, que seguro lo explica mejor que yo); ya que no existe un algoritmo que pueda resolver estos problemas en un tiempo asumible, por lo tanto, suele decirse que el uso de algoritmos heurísticos para tratar de resolver este tipo de problemas está justificado.

  El cálculo o evaluación (≈assesment) de la función objetivo o función de adaptación de cada individuo puede denominarse de distintas maneras, objective function - target function (target ≈ diana) - fitness function - score - scoring function.

    La representación o codificación del individuo es clave en cualquier algoritmo de búsqueda. Es inmediata la comprensión de los términos representation, individual, population.  El término offspring viene a representar el nuevo conjunto de individuos generados tras el cruce y la mutación. Una palabra que puede aparecer es scheduling - organización, que según en qué contexto estará íntimamente ligado a alguno de los términos anteriores. A veces puede interesar que en la población inicial aparezcan individuos de un determinado corte o naturaleza, esto es, "semillar" esa primera población o seed (initialize) the initial (first) population.

    Para denominar las variables o genes con los que se codifica la representación (o cada uno de los individuos), aparecen los términos variable-feature-attribute-gen-bit, y que en la mayoría de ocasiones puedes entenderlos como sinónimos: según la naturaleza de estas variables, éstas pueden ser discrete, binary, continuous, y de ahí que aparezcan términos como continuous optimization - mixed optimization.

    Al disponer de un experto del dominio a optimizar, su conocimiento - domain knowledge, se puede utilizar en nuestro algoritmo de distintas maneras. Un subtipo de problemas especialmente difíciles de optimizar o resolver son los conocidos como deceptive problems (engaño - deceptive). Piensa en un problema de cuatro bits o variables binarias en las que la función objetivo de un individuo vale 1 si aparece un único bit a 1 entre los cuatro, vale 2 si aparecen dos bits a 1 entre los cuatro, vale 3 si aparecen tres bits a 1 entre los 4, PERO vale 0 si aparecen los cuatro bits a 1. Este tipo de problemas son muy difíciles de resolver...

    Íntimamente ligado con el punto anterior aparece un término común en los heurísticos de búsqueda, que son los building blocks: su traducción al castellano no la veo como inmediata, pero podría entenderse como los "ladrillos" (partes de la solución) con los cuales se "construye" una "casa" (o solución). En el problema deceptivo anterior podría entenderse que cada bit por separado, tomando el valor de 1, parece que va construyendo el óptimo global... aunque finalmente no es así. Los algoritmos genéticos y la mayoría de algoritmos de búsqueda están inspirados en la posibilidad de ir contruyendo-encontrando la solución global por partes, por trozos, por bulding blocks, concatenándolos para generar el óptimo global. Estos building blocks, a la hora de crear el óptimo global, es posible que puedan solaparse - overlap.

    El problema a optimizar - resolver (problema subyacente - underlying problem) puede tener a veces varios objetivos que trate de optimizar - multiobjective. El problema puede tener a menudo, como ocurre en los clásicos enunciados de investigación operativa, distintas restricciones - constraints, haciendo no válidas - unfeasible algunas de las soluciones del espacio de búsqueda. Estas condiciones pueden ser de una mayor/menor exigencia a la hora de ser estrictamente cumplidas - hard and soft constraints.

    Hay varios conjuntos de siglas comunes en este tipo de textos: AI (Artificial Intelligence), CS (Computer Science), EC (Evolutionary Computation), GA (Genetic Algorithms).

    Para acabar, una miscelénea de términos finales como swap (intercambio de bits - genes, o sus valores), likelihood (probabilidad, verosimilitud), bound (límite, upper bound - límite superior), generations-iterations, runs o distintas ejecuciones del algoritmo, number of evaluations hace referencia al fin y al cabo al número de soluciones visitadas en toda la búsqueda.