Algoritmo Genético para el Problema del Viajero

problema Viajero en Matlab

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

Licencia de Creative Commons
Algoritmo Genético para problema del Viajero by Luigi Pérez Calzada is licensed under a Creative Commons Reconocimiento-CompartirIgual 3.0 Unported License.