Algoritmo Genéticos (AG)

El AG es un método de búsqueda heurística que opera mediante búsqueda determinada y aleatoria. El conjunto de soluciones posibles para el problema de la optimización se considera como una población de individuos. El grado de adaptación de un individuo en su entorno esta determinado por su adaptabilidad.

Las coordenadas de un individuo en el espacio de la búsquedas están representadas por los cromosomas, en esencia un conjunto de cadenas de caracteres. Un gen es una subsección de un cromosoma que codifica el valor de un único parámetro que ha de ser optimizado. Las Codificaciones típicas para un gen pueden ser binarias o enteras.

Mediante la simulación de operaciones evolutivas recombinación, mutación, y selección se encuentran nuevas generaciones de puntos de búsqueda, los cuales muestran un mayor nivel de adaptabilidad que sus antecesores.

Según la FAQ de "comp.ai.genetic" no se puede enfatizar más claramente que un AG no es un búsqueda puramente aleatoria para una solución del problema. El AG usa procesos estocástico, pero el resultado es claramente no aleatorio (mejor que el aleatorio).

Diagrama Estructurado de un AG: --------------------------- P(t) generación de antecesores en un tiempo t P''(t) generación de descendientes en un tiempo t +=========================================+ |>>>>>>>>>>> Algoritmo AG <<<<<<<<<<<<<<| +=========================================+ | INICIALIZACIÓN t := 0 | +=========================================+ | INICIALIZACIÓN P(t) | +=========================================+ | evaluación ADAPTABILIDAD de P(t) | +=========================================+ | mientras no CRITERIO DE PARADA hacer | | +-------------------------------------+ | | P'(t) := RECOMBINACIÓN{P(t)} | | +-------------------------------------+ | | P''(t) := MUTACIÓN{P'(t)} | | +-------------------------------------+ | | P(t+1) := SELECCIÓN{P''(t) + P(t)} | | +-------------------------------------+ | | evaluación ADAPTABILIDAD de P''(t) | | +-------------------------------------+ | | t := t + 1 | +===+=====================================+