Los algoritmos genéticos (AG) son algoritmos de búsqueda heurística adaptativa que pertenecen a la mayor parte de los algoritmos evolutivos. Los algoritmos genéticos se basan en las ideas de la selección natural y la genética. Se trata de una explotación inteligente de la búsqueda aleatoria proporcionada con datos históricos para dirigir la búsqueda a la región de mejor rendimiento en el espacio de soluciones. Se utilizan comúnmente para generar soluciones de alta calidad para problemas de optimización y problemas de búsqueda.
Los algoritmos genéticos simulan el proceso de selección natural, lo que significa que aquellas especies que pueden adaptarse a los cambios en su entorno pueden sobrevivir, reproducirse y pasar a la siguiente generación. En palabras simples, simulan la «supervivencia del más apto» entre individuos de generaciones consecutivas para resolver un problema. Cada generación consiste en una población de individuos y cada individuo representa un punto en el espacio de búsqueda y posible solución. Cada individuo se representa como una string de caracteres/entero/flotante/bits. Esta string es análoga al cromosoma.
Fundación de Algoritmos Genéticos
Los algoritmos genéticos se basan en una analogía con la estructura genética y el comportamiento de los cromosomas de la población. La siguiente es la base de los GA basados en esta analogía:
- Los individuos de la población compiten por los recursos y se aparean
- Aquellos individuos que tienen éxito (los más aptos) se aparean para crear más descendencia que otros.
- Los genes de los padres «más aptos» se propagan a lo largo de la generación, es decir, a veces los padres crean descendencia que es mejor que cualquiera de los padres.
- Así, cada generación sucesiva es más adecuada para su entorno.
Espacio de búsqueda
La población de individuos se mantiene dentro del espacio de búsqueda. Cada individuo representa una solución en el espacio de búsqueda para un problema dado. Cada individuo se codifica como un vector de longitud finita (análogo al cromosoma) de componentes. Estos componentes variables son análogos a los genes. Así, un cromosoma (individuo) se compone de varios genes (componentes variables).
Puntuación de condición física
A cada individuo se le otorga un puntaje de condición física que muestra la capacidad de un individuo para «competir» . Se busca al individuo que tenga una puntuación de condición física óptima (o casi óptima).
Los GA mantienen la población de n individuos (cromosomas/soluciones) junto con sus puntajes de aptitud física. Los individuos que tienen mejores puntajes de aptitud física tienen más posibilidades de reproducirse que otros. Se seleccionan los individuos con mejores puntajes de aptitud física que se aparean y producen mejores descendientes al combinar los cromosomas de los padres. El tamaño de la población es estático, por lo que se debe crear la sala para los recién llegados. Entonces, algunos individuos mueren y son reemplazados por recién llegados que eventualmente crean una nueva generación cuando se agotan todas las oportunidades de apareamiento de la población anterior. Se espera que a lo largo de generaciones sucesivas lleguen mejores soluciones mientras que los menos aptos mueren.
Cada nueva generación tiene en promedio más “mejores genes” que el individuo (solución) de las generaciones anteriores. Así, cada nueva generación tiene mejores “soluciones parciales” que las generaciones anteriores. Una vez que la descendencia producida no tiene una diferencia significativa con la descendencia producida por poblaciones anteriores, la población converge. Se dice que el algoritmo converge a un conjunto de soluciones para el problema.
Operadores de Algoritmos Genéticos
Una vez que se crea la generación inicial, el algoritmo evoluciona la generación utilizando los siguientes operadores:
1) Operador de selección: la idea es dar preferencia a los individuos con buenos puntajes de aptitud y permitirles pasar sus genes a generaciones sucesivas.
2) Operador de Cruce: Representa el apareamiento entre individuos. Se seleccionan dos individuos mediante el operador de selección y los sitios de cruce se eligen al azar. Luego, los genes en estos sitios de cruce se intercambian, creando así un individuo completamente nuevo (descendencia). Por ejemplo –
3) Operador de mutación: la idea clave es insertar genes aleatorios en la descendencia para mantener la diversidad en la población y evitar la convergencia prematura. Por ejemplo –
Todo el algoritmo se puede resumir como:
1) Randomly initialize populations p
2) Determine fitness of population
3) Until convergence repeat:
a) Select parents from population
b) Crossover and generate new population
c) Perform mutation on new population
d) Calculate fitness for new population
Problema de ejemplo y solución usando Algoritmos Genéticos
Dada una string objetivo, el objetivo es producir una string objetivo a partir de una string aleatoria de la misma longitud. En la siguiente implementación, se hacen las siguientes analogías:
- Los caracteres AZ, az, 0-9 y otros símbolos especiales se consideran genes
- Una string generada por estos caracteres se considera como cromosoma/solución/individuo
La puntuación de aptitud es el número de caracteres que difieren de los caracteres de la string de destino en un índice particular. Por lo tanto, se da más preferencia a las personas que tienen un valor de aptitud más bajo.
C++
// C++ program to create target string, starting from
// random string using Genetic Algorithm
#include <bits/stdc++.h>
using namespace std;
// Number of individuals in each generation
#define POPULATION_SIZE 100
// Valid Genes
const string GENES = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP"\
"QRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}";
// Target string to be generated
const string TARGET = "I love GeeksforGeeks";
// Function to generate random numbers in given range
int random_num(int start, int end)
{
int range = (end-start)+1;
int random_int = start+(rand()%range);
return random_int;
}
// Create random genes for mutation
char mutated_genes()
{
int len = GENES.size();
int r = random_num(0, len-1);
return GENES[r];
}
// create chromosome or string of genes
string create_gnome()
{
int len = TARGET.size();
string gnome = "";
for(int i = 0;i<len;i++)
gnome += mutated_genes();
return gnome;
}
// Class representing individual in population
class Individual
{
public:
string chromosome;
int fitness;
Individual(string chromosome);
Individual mate(Individual parent2);
int cal_fitness();
};
Individual::Individual(string chromosome)
{
this->chromosome = chromosome;
fitness = cal_fitness();
};
// Perform mating and produce new offspring
Individual Individual::mate(Individual par2)
{
// chromosome for offspring
string child_chromosome = "";
int len = chromosome.size();
for(int i = 0;i<len;i++)
{
// random probability
float p = random_num(0, 100)/100;
// if prob is less than 0.45, insert gene
// from parent 1
if(p < 0.45)
child_chromosome += chromosome[i];
// if prob is between 0.45 and 0.90, insert
// gene from parent 2
else if(p < 0.90)
child_chromosome += par2.chromosome[i];
// otherwise insert random gene(mutate),
// for maintaining diversity
else
child_chromosome += mutated_genes();
}
// create new Individual(offspring) using
// generated chromosome for offspring
return Individual(child_chromosome);
};
// Calculate fitness score, it is the number of
// characters in string which differ from target
// string.
int Individual::cal_fitness()
{
int len = TARGET.size();
int fitness = 0;
for(int i = 0;i<len;i++)
{
if(chromosome[i] != TARGET[i])
fitness++;
}
return fitness;
};
// Overloading < operator
bool operator<(const Individual &ind1, const Individual &ind2)
{
return ind1.fitness < ind2.fitness;
}
// Driver code
int main()
{
srand((unsigned)(time(0)));
// current generation
int generation = 0;
vector<Individual> population;
bool found = false;
// create initial population
for(int i = 0;i<POPULATION_SIZE;i++)
{
string gnome = create_gnome();
population.push_back(Individual(gnome));
}
while(! found)
{
// sort the population in increasing order of fitness score
sort(population.begin(), population.end());
// if the individual having lowest fitness score ie.
// 0 then we know that we have reached to the target
// and break the loop
if(population[0].fitness <= 0)
{
found = true;
break;
}
// Otherwise generate new offsprings for new generation
vector<Individual> new_generation;
// Perform Elitism, that mean 10% of fittest population
// goes to the next generation
int s = (10*POPULATION_SIZE)/100;
for(int i = 0;i<s;i++)
new_generation.push_back(population[i]);
// From 50% of fittest population, Individuals
// will mate to produce offspring
s = (90*POPULATION_SIZE)/100;
for(int i = 0;i<s;i++)
{
int len = population.size();
int r = random_num(0, 50);
Individual parent1 = population[r];
r = random_num(0, 50);
Individual parent2 = population[r];
Individual offspring = parent1.mate(parent2);
new_generation.push_back(offspring);
}
population = new_generation;
cout<< "Generation: " << generation << "\t";
cout<< "String: "<< population[0].chromosome <<"\t";
cout<< "Fitness: "<< population[0].fitness << "\n";
generation++;
}
cout<< "Generation: " << generation << "\t";
cout<< "String: "<< population[0].chromosome <<"\t";
cout<< "Fitness: "<< population[0].fitness << "\n";
}
Python3
# Python3 program to create target string, starting from
# random string using Genetic Algorithm
import random
# Number of individuals in each generation
POPULATION_SIZE = 100
# Valid genes
GENES = '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP
QRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}'''
# Target string to be generated
TARGET = "I love GeeksforGeeks"
class Individual(object):
'''
Class representing individual in population
'''
def __init__(self, chromosome):
self.chromosome = chromosome
self.fitness = self.cal_fitness()
@classmethod
def mutated_genes(self):
'''
create random genes for mutation
'''
global GENES
gene = random.choice(GENES)
return gene
@classmethod
def create_gnome(self):
'''
create chromosome or string of genes
'''
global TARGET
gnome_len = len(TARGET)
return [self.mutated_genes() for _ in range(gnome_len)]
def mate(self, par2):
'''
Perform mating and produce new offspring
'''
# chromosome for offspring
child_chromosome = []
for gp1, gp2 in zip(self.chromosome, par2.chromosome):
# random probability
prob = random.random()
# if prob is less than 0.45, insert gene
# from parent 1
if prob < 0.45:
child_chromosome.append(gp1)
# if prob is between 0.45 and 0.90, insert
# gene from parent 2
elif prob < 0.90:
child_chromosome.append(gp2)
# otherwise insert random gene(mutate),
# for maintaining diversity
else:
child_chromosome.append(self.mutated_genes())
# create new Individual(offspring) using
# generated chromosome for offspring
return Individual(child_chromosome)
def cal_fitness(self):
'''
Calculate fitness score, it is the number of
characters in string which differ from target
string.
'''
global TARGET
fitness = 0
for gs, gt in zip(self.chromosome, TARGET):
if gs != gt: fitness+= 1
return fitness
# Driver code
def main():
global POPULATION_SIZE
#current generation
generation = 1
found = False
population = []
# create initial population
for _ in range(POPULATION_SIZE):
gnome = Individual.create_gnome()
population.append(Individual(gnome))
while not found:
# sort the population in increasing order of fitness score
population = sorted(population, key = lambda x:x.fitness)
# if the individual having lowest fitness score ie.
# 0 then we know that we have reached to the target
# and break the loop
if population[0].fitness <= 0:
found = True
break
# Otherwise generate new offsprings for new generation
new_generation = []
# Perform Elitism, that mean 10% of fittest population
# goes to the next generation
s = int((10*POPULATION_SIZE)/100)
new_generation.extend(population[:s])
# From 50% of fittest population, Individuals
# will mate to produce offspring
s = int((90*POPULATION_SIZE)/100)
for _ in range(s):
parent1 = random.choice(population[:50])
parent2 = random.choice(population[:50])
child = parent1.mate(parent2)
new_generation.append(child)
population = new_generation
print("Generation: {}\tString: {}\tFitness: {}".\
format(generation,
"".join(population[0].chromosome),
population[0].fitness))
generation += 1
print("Generation: {}\tString: {}\tFitness: {}".\
format(generation,
"".join(population[0].chromosome),
population[0].fitness))
if __name__ == '__main__':
main()
Producción:
Generation: 1 String: tO{"-?=jH[k8=B4]Oe@} Fitness: 18
Generation: 2 String: tO{"-?=jH[k8=B4]Oe@} Fitness: 18
Generation: 3 String: .#lRWf9k_Ifslw #O$k_ Fitness: 17
Generation: 4 String: .-1Rq?9mHqk3Wo]3rek_ Fitness: 16
Generation: 5 String: .-1Rq?9mHqk3Wo]3rek_ Fitness: 16
Generation: 6 String: A#ldW) #lIkslw cVek) Fitness: 14
Generation: 7 String: A#ldW) #lIkslw cVek) Fitness: 14
Generation: 8 String: (, o x _x%Rs=, 6Peek3 Fitness: 13
.
.
.
Generation: 29 String: I lope Geeks#o, Geeks Fitness: 3
Generation: 30 String: I loMe GeeksfoBGeeks Fitness: 2
Generation: 31 String: I love Geeksfo0Geeks Fitness: 1
Generation: 32 String: I love Geeksfo0Geeks Fitness: 1
Generation: 33 String: I love Geeksfo0Geeks Fitness: 1
Generation: 34 String: I love GeeksforGeeks Fitness: 0
Nota: cada vez que el algoritmo comienza con strings aleatorias, por lo que la salida puede diferir
Como podemos ver en el resultado, nuestro algoritmo a veces se atasca en una solución óptima local, esto se puede mejorar aún más actualizando el algoritmo de cálculo de puntuación de fitness o ajustando los operadores de mutación y cruce.
Por qué usar Algoritmos Genéticos
- son robustos
- Proporcionar optimización sobre estado de espacio grande.
- A diferencia de la IA tradicional, no se rompen con un ligero cambio en la entrada o la presencia de ruido.
Aplicación de Algoritmos Genéticos
Los algoritmos genéticos tienen muchas aplicaciones, algunas de ellas son:
- Red neuronal recurrente
- Pruebas de mutación
- descifrar código
- Filtrado y procesamiento de señales
- Aprendizaje de la base de reglas difusas, etc.
Referencias
https://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications
https://en.wikipedia.org/wiki/Genetic_algorithm
https://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol1/ hmw/article1.html
Este artículo es una contribución de Atul Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA