Continuando con la materia de Temas Avanzados de Computo Inteligente, en esta ocasión veremos un algoritmo genético para solucionar el problema del viajante o problema del viajero, hace algunos ayeres (más de 2 semestres) programamos unos algoritmos genéticos en Java (si como los universitarios de la UAT somos «javeros»), pues en esta ocasión parece ser que también nos volverán «Matlaboleros», programa y entorno que sigue sin agradarme, pero bueno al final de cuentas hay que dar soluciones y no pretextos, con desveladas (¡¡¡1,500 repeticiones, fue una exageración!!!), el trabajo y desarrollando en Linux (por fin), un proyecto Freelance en php (php si rifa), la tesis en JavaScript, vaya a veces quiero escribir en javaScript algo como:
echo ‘Welcome to Mictlán’;
pero bueno esas son otras historias, continuando con el algoritmo genético para el problema del viajero consiste en que a través de Algoritmo Genéticos se pueda resolver este problema de comenzar en un punto dado y terminar en otro totalmente distinto, recorriendo todas las ciudades (puntos) con el menor costo posible.
Los pasos que seguí fueron:
-
Solicitamos al usuario:
-
El número de generaciones
-
El tamaño de la población
-
La probabilidad de cruce (en escala de 1 a 9)
-
La probabilidad de mutación (en escala de 1 a 9)
-
-
Definimos nuestra matriz con los puntos conectados entre si y el costo para ir a cada punto.
-
Generamos por primera y única ocasión nuestra población inicial de forma aleatoria haciendo permutaciones y recorriendo todos los puntos.
-
De color azul pintaremos la primera generación y sus rutas.
-
Obtenemos los costos de la generación actual.
-
Obtenemos la función de aptitud que conseguiremos con la formula;
f(x) = (Costo mayor + costo menor) – costo actual, al mismo tiempo que obtenemos la sumatoria. -
Obtenemos la probabilidad de selección; probSel=f(x)/sumatoria.
-
Obtenemos la probabilidad acumulada.
-
Generamos un arreglo con n número aleatorios, dónde n es el tamaño de la población.
-
Obtenemos la población Intermedia, esto es; si la probabilidad acumulada actual (ciclo) es mayor al elemento actual de R (paso anterior) tomamos el elemento como eficaz, y lo pasamos a la siguiente generación en caso contrario buscamos un elemento mejor que R.
-
Para la probabilidad de cruce, generamos un número aleatorio si es mayor a la probabilidad de cruce no cruzamos y si es menor cruzamos, el método empleado para la cruza fue el de la cruza parcialmente mapeada, ya que fue el método visto en clase y más entendible para mi, consiste en:
-
Elegir aleatoriamente dos puntos de cruza
-
Intercambiar estos dos segmentos en los hijos que se generan.
-
El resto de las cadenas que conforman los hijos se obtienen haciendo mapeo entre los dos padres:
-
Si un valor no esta contenido en el segmento intercambiado, permanece igual.
-
Si está contenido en el segmento intercambiado, entonces se sustituye por el valor que tenga dicho segmento en el otro padre.
-
-
-
Si el número de la población es impar, pasamos el último elemento de forma automática a la siguiente generación, para tener variedad.
-
Generamos un número aleatorio si es menor a la probabilidad de mutación (introducida por el usuario) realizaremos la mutación, en este caso utilice la Mutación por intercambio recíproco la cual consiste en seleccionar dos puntos al azar e intercambiar estos valores.
-
Volvemos a obtener el costo y la función de aptitud (f(x)).
Obtenemos el de menor costo (que será nuestro mejor individuo generado) y lo gráficamos.
La parte que más me costo y más orgulloso estoy de mi algoritmo, es la función para gráficar toda la ruta, pero la función que ocupe para gráficar Biograph no supe emplearla del todo o no sé, pero tuve que desarrollar un pequeño código para que me funcionara;
[java]
disp(cad);
for i=1:n-1
edgesSel=getedgesbynodeid(bg,cad(i),cad(i+1));
set(edgesSel,’LineColor’,[1 0 0]);
end
bg.view;
[/java]
Donde recorremos la cadena carácter a carácter, e indicamos que nos «guarde» (set) la ruta del punto i al punto i+1 y la pinte de rojo, lo metemos dentro de un ciclo for y así obtendríamos toda la ruta completa
Y apoyando el Software Libre (Stallman últimamente me ha dado suficientes fundamentos para compartir mi código fuente, así cómo lo he venido haciendo a los largo de 5 años totalmente gratis) les copio y pego mi código fuente el cual también grafica la mejor ruta en un grafo:
[java]
clc;
%las letras por posiciones
%gen=1; %número degeneraciones
n=10; %tamaño de los puntos a recorrer
%pob=5; %tamaño de la población
%pc=0.8; %probabilidad de cruce
gen=input(‘Da el número de generaciones que deseas manejar: ‘);
pob=input(‘Da el tamaño de la población: ‘);
pc_2=input(‘Da la probabilidad de cruce en escala de 1 a 9: (n*0.1)’);
pc=pc_2*0.1;
probMut_2=input(‘Da la probabilidad de mutación en escala de 1 a 9: (n*0.01) ‘);
probMut=probMut_2*0.01;
V=[‘A’ ‘B’ ‘C’ ‘D’ ‘E’ ‘F’ ‘G’ ‘H’ ‘I’ ‘J’];
V2=[1 2 3 4 5 6 7 8 9 10];
VV=[0 20 15 30 25 40 30 60 50 95;
20 0 30 20 15 15 20 40 40 30;
15 30 0 25 30 20 30 40 45 50;
30 20 25 0 20 30 10 50 40 30;
25 15 30 20 0 10 20 20 30 40;
40 15 20 30 10 0 20 30 20 30;
30 20 30 10 20 20 0 25 40 30;
60 40 40 50 20 30 35 0 30 15;
50 40 45 40 30 20 40 30 0 20;
95 30 50 30 40 30 30 15 20 0 ];
%fprintf(‘Tabla de distancias: \n’);disp(VV);
bg = biograph(VV, V,’ShowWeights’,’on’);%unimos
%bg.view;
%población permutada
P=[];
for i=1:pob
P(i,:)=randperm(n);
fprintf(‘%s\n’,puntoLetra(P(i,:)));
end
fprintf(‘Población tras permutación: \n’);disp(P);
for i=1:pob
cad=puntoLetra(P(i,:));
disp(cad);
for j=1:n-1
edgesSel=getedgesbynodeid(bg,cad(j),cad(j+1));
set(edgesSel,’LineColor’,[0 0 1]);
end
end
%bg.view;
for g=1:gen
%obtenemos el costo
Cos=[];
for i=1:pob
costo=0;
for j=1:n-1
costo=costo+VV(P(i,j),P(i,j+1));
end %end for j
Cos(i)=costo;
end %end for n
fprintf(‘Costos: \n’);disp(Cos);
%obtenemos la función de aptitud (fmax+fmin)-f
mayor=max(Cos);
menor=min(Cos);
sumatoria=0;
fApt=[];
for i=1:pob
fApt(i)=(mayor+menor)-Cos(i);
sumatoria=sumatoria+fApt(i);
end %end for i
fprintf(‘Max=%d Min=%d f. Aptitud:\n’,mayor,menor);disp(fApt);
fprintf(‘Sumatoria=%d\n’,sumatoria);
%obtenemos la probabilidad de selección y Acumulada
probSel=[];
probAcum=[];
probSel(1)=Cos(1)/sumatoria;
probAcum(1)=probSel(1);
for i=2:pob
probSel(i)=fApt(i)/sumatoria;
probAcum(i)=probAcum(i-1)+probSel(i);
end %end for i
fprintf(‘Probabilidad de Selección\n’);disp(probSel);
fprintf(‘Probabilidad Acumulada\n’);disp(probAcum);
%obtenemos los valores aleatorios de r * sumatoria de la calif. fitness
R=[];
for i=1:pob
R(i)=rand;
end
fprintf(‘R= ‘);disp(R);
%obtenemos población intermedia
pobInt=[];
for i=1:pob
for j=1:pob
if probAcum(j)>R(i) %si calificacion.Acum(j)>r(i) tomamos al ind. si no incrementamos j
pobInt(i,:)=P(j,:); %asignamos en la posicion i (de r) al nuevo individuo de la pos. j
break;
end%end if
end %end for j
end%end for i
fprintf(‘Población Intermedia \n’);disp(pobInt);
%Obtenemos prob. de cruza si es menor cruzamos, además de obtener el punto
%de cruza y obtenemos generacion cruzada
cruz=[];
if (mod(pob,2)~=0)%si es impar la poblacion
cruz(pob,:)=pobInt(pob,:); %asignamos el ultimo elemento directamente
end
for i=1:2:pob
probCruz=rand; %obtenemos la probabilidad de cruce
fprintf(‘probCruce=%f — %f\n’,probCruz,pc);
if(probCruz<pc) %si es menor cruzamos
cad1=»;cad2=»;puntero=2;rango=3;
while(1)
cad1=pobInt(i,puntero:puntero+rango);
cad2=pobInt(i+1,puntero:puntero+rango);
if (comprobarCad(cad1,cad2)==0) %verificamos que no se repita ningun elemento
break;
else
if puntero==n-rango %si llegamos casi al final
rango=rango-1; %disminuimos el rango
puntero=1; %regresamos el puntero al inicio
end
puntero=puntero+1;
end
end %end while
fprintf(‘%d vs %d: pI=%d pF=%d\n’,i,i+1,puntero,puntero+rango);disp(cad1);disp(cad2);
if puntero > puntero+rango fprintf(‘\nImposible realizar cruza\n’); end
for j=1:n
ind=find(cad2==pobInt(i,j));
ind2=find(cad1==pobInt(i,j));
if ind~=0
cruz(i,j)=cad1(ind);
elseif ind2~=0
cruz(i,j)=cad2(ind2);
else
cruz(i,j)=pobInt(i,j);
end
end %end for j
%para el segundo individuo
for j=1:n
ind=find(cad1==pobInt(i+1,j));
ind2=find(cad2==pobInt(i+1,j));
if ind~=0
cruz(i+1,j)=cad2(ind);
elseif ind2~=0
cruz(i+1,j)=cad1(ind2);
else
cruz(i+1,j)=pobInt(i+1,j);
end
end %end for j2
else
cruz(i,:)=pobInt(i,:);
cruz(i+1,:)=pobInt(i+1,:);
end%end probCruz < pc
if (mod(pob,2)~=0)
if i==pob-2 %si es impar la poblacion y estamos en el penultimo elemento (de 2 en 2) rompemos
break;
end
end %end if mod
end%end for pob
fprintf(‘Población Cruza\n’);disp(cruz);
%mutación por intercambio recíproco
for i=1:pob
pM=rand;
if pM<probMut
fprintf(‘\nInd=%d.-probMutAle=%f vs probMutUser=%f\n’,i,pM,probMut);
p1=0;
p2=0;
while(1)
p1=round(rand*n);
p2=round(rand*n);
if p1==0 || p2==0
continue;
elseif p2~=p1
break;
end %end id
end %end while
fprintf(‘Puntos a intercambiar: %d y %d\n’,p1,p2);
temp1=cruz(i,p1);
cruz(i,p1)=cruz(i,p2);
cruz(i,p2)=temp1;
else
continue;
end %end if probMut
end %end for i
fprintf(‘Población Mutada\n’);disp(cruz);
for i=1: pob
fprintf(‘%s\n’,puntoLetra(cruz(i,:)));
end
%obtenemos el costo
Cos=[];
for i=1:pob
costo=0;
for j=1:n-1
costo=costo+VV(P(i,j),cruz(i,j+1));
end %end for j
Cos(i)=costo;
end %end for n
fprintf(‘Costos: \n’);disp(Cos);
%obtenemos la función de aptitud (fmax+fmin)-f
mayor=max(Cos);
menor=min(Cos);
sumatoria=0;
fApt=[];
for i=1:pob
fApt(i)=(mayor+menor)-Cos(i);
sumatoria=sumatoria+fApt(i);
end %end for i
fprintf(‘Max=%d Min=%d f. Aptitud:\n’,mayor,menor);disp(fApt);
fprintf(‘Sumatoria=%d\n’,sumatoria);
end %end for generaciones
menor=10000;
pos=0;
for i=1:pob
if fApt(i)<=menor
menor=fApt(i);
pos=i;
end
end
fprintf(‘El mejor de la última generación es: %f de la pos: %d’,menor,pos);
fprintf(‘\nLa mejor ruta es: %s’,puntoLetra(cruz(pos,:)));
fprintf(‘\nCon un costo de: %d\n’,menor);
cad=puntoLetra(cruz(pos,:));
disp(cad);
for i=1:n-1
edgesSel=getedgesbynodeid(bg,cad(i),cad(i+1));
set(edgesSel,’LineColor’,[1 0 0]);
end
bg.view;
[/java]
Comprobamos la cadena que no se repita ningún elemento, si no la cruza es imposible
[java]
function ban=comprobarCad(a,b)
n=length(a);
ban=false;
for i=1:n
x=find(a==b(i));
if x~=0
ban=true;
break;
end
end
%ban=0 no se repite
%ban=1 se repite
[/java]
Con está función convertimos los números a letras
[java]
function cad=puntoLetra(v)
n=length(v);
cad=’ ‘;
for i=1:n
switch v(i)
case 1,
cad=strcat(cad,’A’);
case 2,
cad=strcat(cad,’B’);
case 3,
cad=strcat(cad,’C’);
case 4,
cad=strcat(cad,’D’);
case 5,
cad=strcat(cad,’E’);
case 6,
cad=strcat(cad,’F’);
case 7,
cad=strcat(cad,’G’);
case 8,
cad=strcat(cad,’H’);
case 9,
cad=strcat(cad,’I’);
case 10,
cad=strcat(cad,’J’);
otherwise,
cad=strcat(cad,’L’);
end %end switch
end %end for i
[/java]
Espero les sea de gran ayuda y muchas gracias por leerme y tratar de entender mi código.
Donwload source: algoritmo genético
Algoritmo Genético para problema del Viajero by Luigi Pérez Calzada is licensed under a Creative Commons Reconocimiento-CompartirIgual 3.0 Unported License.
saludos, da un error o.o!
??? Attempted to access pobInt(10,:); index out of bounds because size(pobInt)=[9,10].
Error in ==> Untitled at 156
cruz(i+1,:)=pobInt(i+1,:);
Con que datos lo intentaste compilar?
Ya que los que viene de prueba si funciona te lo paso nuevamente:
Número de generaciones=1
Tamaño de la población=5
Probabilidad de cruce=8
Probabilidad de mutación=6
Al finalizar obtengo los siguientes datos de resultados:
La mejor ruta es: FCGHEABDIJ
Con un costo de: 190
FCGHEABDIJ
Y se despliega el grafo.
Saludos cordiales 🙂
SAludos , primero buen codigo muchas gracias por el aporte,
te pregunto si conoces un articulo donde se relacione el tema del Algoritmo Genético para el Problema del Viajero para entender y profundizar un poco mas en este interesante tema .
gracias
Hola! Gracias por compartir el código fuente, me servirá de mucho. Te quería preguntar si para ejecutar este código se lo copia directamente en la pantalla principal del Matlab?
Muchas gracias.-
Así solo copias y pegas el código además de copiar y pegar en otros archivos las funciones (son 2 la de comprobar y puntoLetra) ejecutas y debe de funcionar sin problemas.
Gracias por la consulta, ya pude hacerlo funcionar. Ahora tengo otra consulta: En la fórmula de la función de aptitud, por qué la calculas como: f(x) = (costo mayor + costo menor) – costo actual
Podrías explicarme esa fórmula, por qué la planteaste así?
Muchísimas gracias! 🙂
Ya que es una formula que muchos autores manejan para obtener mejores resultados. Y como eran mayoría por ello decidí utilizar dicha formula.
hola tu codigo si me funciona y todo muy bien….solo queria saber si puedes darme como una introduccion algo asi como el objetivo que se desea solucionar con este codigo y que formulas utilizas para desarrollarlo
Toda la información que puedo proporcionarte acerca de este software está publicada mi amigo.
el progama me sale un error y es el siguiente
«??? Error: File: biograph.m Line: 5 Column: 7
The expression to the left of the equals sign is not a valid target for an assignment.
Error in ==> Fabian_Liceth at 29
bg = biograph(VV, V,’ShowWeights’,’on’);%unimos» no se mucho de matlab espero que me ayudes en ese problema; que mal estoy haciendo
Hola! mi problema es si biograph es una function o en que lado se debe pegar el codigo que realizaste para el grafo por que me sale este error
»
??? Attempt to execute SCRIPT biograph as a function:
C:\Users\efarc\Desktop\IA\OR\biograph.m
Error in ==> Fabian_Liceth at 29
bg = biograph(VV, V,’ShowWeights’,’on’);%unimos »
Y no se que hacer
Si estás corriendo los otros 2 programas? intenta ejecutarlo sin modificar.
pues yo solamente hice 4 archivos .m una principal llamado Fabian_Liceth.m y las dos funciones llamados puntoLetra.m y comprobarCad.m; pues lo que no tengo claro es donde pego el codigo que tu creaste llamado biograph; Lo que hice fue copiarlo y pegarlo en un archivo llamado biograph.m y ahi me sale el bendito error
Hola Fabian, deberás primero crear un archivo llamado «puntoLetra.m» (sin lass comillas dobles) y otro llamado «comprobarCad.m» (sin comillas dobles) y el último y principal que se llamará: «fabianLiceth.m» (primera en minúsculas y sin guiones por si las dudas), este último contendrá todo el programa el más grande.
El siguiente código sólo es una explicación:»disp(cad);
for i=1:n-1
edgesSel=getedgesbynodeid(bg,cad(i),cad(i+1));
set(edgesSel,’LineColor’,[1 0 0]);
end
bg.view;» NO hace falta que lo pongas en otro programa ya va incluido dentro del programa principal al cual hemos llamado en este caso «fabianLiceth.m», espero te sirva esta pequeña explicación y logres ejecutarlo sin problemas.
con que versión de matlab trabajaste el programa; yo estoy trabajando con el r2010b
Yo trabaje con la r2008b
Ha con razon tengo el mismo problema que fabian al correr el programa me sale en la linea 31 por la funcion biograph debe ser que se escribio para el matlab r2008b y ahora que esta mas actualizado habra un error de sintaxis o algo asi
como creas la matrix V,VV y V2, en caso de querer agregar otro punto como se haria.. gracias
Para agregar otro punto del vector y la matriz V,VV y V2 deberías de:
V=[‘A’ ‘B’ ‘C’ ‘D’ ‘E’ ‘F’ ‘G’ ‘H’ ‘I’ ‘J’,…,’m’,’n’…’z’];
V2=[1 2 3 4 5 6 7 8 9 10 … n];
VV=[0 20 15 30 25 40 30 60 50 95;
20 0 30 20 15 15 20 40 40 30;
15 30 0 25 30 20 30 40 45 50;
30 20 25 0 20 30 10 50 40 30;
25 15 30 20 0 10 20 20 30 40;
40 15 20 30 10 0 20 30 20 30;
30 20 30 10 20 20 0 25 40 30;
60 40 40 50 20 30 35 0 30 15;
50 40 45 40 30 20 40 30 0 20;
95 30 50 30 40 30 30 15 20 0
//aquí agregas los demás elementos pero ahora serán hasta n.
];
Amigo, muchas gracias por el codigo.
Tengo una duda respecto a la matriz VV. Esta representa las distancias entre cada nodo? o los costos?.
Ahora bien, como vas calculando los costos?
Y lo último, este problema es asimilable al VRP? o son distintos?
Saludos