Algoritmo evolutivo basado en el mecanismo de haplodiploidia para resolver el problema de planificación de <i>weighted tardiness</i>

Abstract

Los Algoritmos Evolutivos (EAs) suelen considerarse una buena técnica para encontrar rápidamente regiones prometedoras del espacio de búsqueda. Son algoritmos de búsqueda ciega, que solamente hacen uso de la bondad relativa de las solucione s, e ignoran la naturaleza del problema. Su rendimiento puede mejorarse usando enfoques multirecombinativos, los que proveen un balance exc elente entre la explotación y la exploración. Aunque los Algoritmos Evolutivos pueden encontrar óptimos globales de problemas de alta complejidad, la realidad es que muchas veces el costo computacional que requieren es prohibitivamente alto y se los prefieren para encontrar una solución razonable ya que eso suelen hacerlo en un tiempo relativamente corto. En muchos problemas de planificación, la calidad de las soluciones provistas, debe ser balanceada con el esfuerzo necesario para producirla. A menudo se requiere una aceleración de la convergencia a pesar de una aceptada pérdida de la calidad de los resultados. Este trabajo incorpora variantes que se basan en el mecanismo biológico de la haplodiploidia para determinar el sexo, en los operadores de cruzamiento PMX (Partial Mapped Crossover) y OX2 (Order Crossover) con el objetivo de reducir el esfuerzo computacional requerido para la obtención de una solución. Las variantes se aplicaron a un algoritmo evolutivo que permite resolver problemas de weighted tardiness en un ambiente de máquina única.