Bienvenidos hoy hablaremos sobre algoritmos genéticos
Cuando hablamos de algoritmos genéticos, hay que hablar de John Holland que en 1962 asienta las bases para sus posteriores desarrollos hasta llegar a lo que se conoce hoy por algoritmos genéticos.
Un algoritmo genético es un método de búsqueda que imita la teoría de la evolución biológica de Darwin para la resolución de problemas. Para ello, se parte de una población inicial de la cual se seleccionan los individuos más capacitados para luego reproducirlos y mutarlos para finalmente obtener la siguiente generación de individuos que estarán más adaptados que la anterior generación.
CodificacióndelasVariables
Los cromosomas de alguna manera deberán contener información acerca de la solución que representa. La codificación se puede realizar de varias formas. La más utilizada es mediante una cadena de números binarios (1s o 0s). Pero también se puede realizar la codificación mediante números enteros o incluso cadenas de palabras.
La elección de la codificación dependerá también del problema a resolver pues puede darse la situación en la que la resolución de un caso sea más óptimo el uso de una codificación basada en números reales mientras que esa codificación complique la solución en otro caso. Así pues hay que estudiar la codificación más óptima según el caso que se esté estudiando.
Algoritmo basico para un algoritmo genético
Inicio (1) t = 0;
inicializar P(t);
evaluar P(t);
Mientras (no se cumpla la condición de parada) hacer Inicio(2)
t= t+1
seleccionar P(t) desde P(t-1) recombinar P(t)
mutación P(t)
evaluar P(t)
Final(2)
Final(1)
Ejemplo resolviendo la ruta mas corta que cruze todas las ciudades
Como se vio en el algoritmo el primer paso es inicializar una población de individuos, en este caso son genes, traducidos a la computación vectores en este caso, la representación del gen será mediante números, cada numero debería representar una ciudad, las ciudades hipoteticamente hablando están relacionadas en un grafo cada arista tiene un valor que es el coste de ir de tal ciudad a tal ciudad , no lo puse por que no se vería en la imagen.
un grafo anterior es la representación de una matriz de adyacencia en este caso de la siguiente matriz
k=[ 0 29 20 21 16 31 100 12 4 31 18;
29 0 15 29 28 40 72 21 29 41 12;
20 15 0 15 14 25 81 9 23 27 13;
21 29 15 0 4 12 92 12 25 13 25;
16 28 14 4 0 16 94 9 20 16 22;
31 40 25 12 16 0 95 24 36 3 37;
100 72 81 92 94 95 0 90 101 99 84;
12 21 9 12 9 24 90 0 15 25 13;
4 29 23 25 20 36 101 15 0 35 18;
31 41 27 13 16 3 99 25 35 0 38;
18 12 13 25 22 37 84 13 18 38 0];
Una matriz de adyacencia describe la relación que existe entre cada nodo de un grado con otro nodo cada columna siendo los nodos por eso en la diagonal tiende a cero pues el nodo en relación con si mismo no tiene un costo.
Empezamos con el código primero la generación de la población inicial
pl=zeros(1,1);
%creamos un arreglo del tamaño de las ciudades en este caso 11. [1,2,3,4,5,6,7,8,9,10,11]
seed=[1:size];
% creacion de nuetra poblacion permutada
%este ciclo nos genera una matriz de 11x150 donde serán 150 cromosomas diferentes que son %combinaciones del vector de 11 ciudades, en pocas palabras simples combinaciones
for i=1:150
pob(i,:)= seed(randperm(length(seed)));
end
pobsize=length(pob);
x=zeros(1,pobsize);
%iniciamos a los padres que generaran otra población
padres=zeros(10,size);
después se realiza el proceso que replica el comportamiento de la evolución , los padres se van cruzando (fallan mas que los taringeros ) con otros cromosomas (padres igual aquí creo no vale el genero :V), posterior a esto, se realiza una mutación de un porcentaje pequeño de la población que resulto de la cruza , la mutación cambia en este caso algún cromosoma del gen (en este problema la mutación hace algún cambio entre posiciones ) , ya teniendo esto se realiza la agregación de los hijos resultantes de la cruza si como los mutados(deformes o genios jaja) y se procede a evaluar cada gen de la población utilizando una función fitness esta es la siguiente :
%recibe c que es el cromosoma o gen y g que es la matriz de adyacencia y nos regresa un valor del coste total que recorre esa combinación de ciudades recordemos que queremos buscar la combinación o ruta que pase por todas las ciudades que cueste menos, entonces entre menos nos cueste es mejor la solucion.
function[fit]=fitness(c,g)
sigma=0;
for i=1:length(c)-1
sigma=sigma+g(c(i),c(i+1));
end
fit=sigma;
end
finalmente de evaluar la población se escogen los mejores y se procede a matar a los demás jajaja, se eliminan los cromosomas mas débiles y se dejan los mejores para que las próximas generaciones tengan mejores hijos y así sucesivamente hasta que el resultado del fitness sea el mejor.
for k=1:alp
for i=1:pobsize
x(i)=fitness(pob(i,:),matrixAdj);
end
%seleccion por ruleta;
x=x/sum(x);
for i=1:pobsize*.50
a=rand;
sig=0;
for j=1:pobsize
sig=sig+x(j);
if sig>a
padres(i,:)=pob(j,:);
break;
end
end
end
sons=zeros(10,size);
%cruza
for i=1:2:pobsize*.50
ar1=randi([1,pobsize*.50],1,1);
ar2=randi([1,pobsize*.50],1,1);
[ch1,ch2]=OX(padres(ar1,:),padres(ar2,:));
sons(i,:)=ch1;
sons(i+1,:)=ch2;
end
%mutacion
len=length(sons);
for j=1:4
a=randi([1,pobsize*.50],1,1);
v=padres(a,:);
sons(len+j,:)=v(randperm(length(v)));
end
len=length(pob);
%add hujos to poblation
for j=1:length(sons)
pob(len+j,:)=sons(j,:);
end
temp=pob;
%evaluacion
for i=1:length(pob(:,1))
pob(i,size+1)=fitness(temp(i,:),matrixAdj);
end
temp=zeros(10,size);
%sort poblation
sortPop=sortrows(pob,size+1);
for i=1:pobsize
temp(i,:)=sortPop(i,1:size);
end
pob=temp;
pl(k)=sortPop(1,size+1);
end
pob=pob(1,:);
end
Para finalizar utilizando la matriz de adyacencia que mencionamos al principio y aplicando el algoritmo mencionado nos devuelve una ruta siguiente
7 2 11 9 1 8 3 5 4 10 6
nos quiere decir que empezar por la ciudad 7 pasar las ciudades mencionadas 2,11,9 etc y finalizar en la ciudad 6 nos da la combinación mas optima, se puede ver en la siguiente figura la ruta.
las lineas rojas marcan la ruta que debe seguir para realizar el recorrido.
Les comparto el código completo en Github
https://github.com/Cosijopiii/AlgoritmoGeneticoTSP
también si quieren pueden pasarse por mis anteriores post's
Cualquier duda o comentario escríbanlo abajo, con gusto repondere no olvides dejarme unos puntos y recomendarme , seguiré con esta serie de post un poco técnicos pero interesantes.
