• Author / Uploaded
• Beto Hernandez

• Categories
• Ciencia de sistemas
• Ciencia computacional
• Matemáticas De La Computación
• Física y matemáticas
• Matemáticas

Citation preview

UNIVERSIDAD AUTÓNOMA DE NUEVO LEÓN

Facultad de Ciencias FísicoMatemáticas

Simulación Proyecto Final “Búsqueda Tabú”

Maestro: Roberto Soto

Alumnos: Gómez Vaca Karen Lizet -

1343188 1075245

Roberto Carlos Chávez Espinosa -

San Nicolás de los Garza, N.L. a 26 de Noviembre del 2010 %a partir de una solucion inicial (punto rojo) se crea una vecindad de %radio variable, se dan "np" puntos aleatorios a esa vecindad a la que %llamaremos "candidatos" y obtenemos el candidato mas optimo dependiendo de %lo que queremos encontrar (maximizar o minimizar) %es que a partir del primer candidato optimo se genere otra vecindad %y de ahi obtener otro optimo y asi sucesivamente hasta que se cicle o %llegue a 100 la cantidad de candidatos optimos obtenidos (iteraciones) %y despues mandar ese candidato optimo final a la lista tabu y obtener %otra vecindad (punto rojo) generada aleatoriamente %------------------------------------------------------------------------%el # de iteraciones lo modifico en la linea: %129 %las funciones las modifico en las lineas: %75 (grafica) %76 (grafica) %82 = 104 (deben ser iguales) %89 = 111 (deben ser iguales) %156 %en 145 y 281 hay pause %------------------------------------------------------------------------clear all close all np=10; %np=# de puntos aleatorios en el entorno o vecindad % o sea, los candidatos repetido = 0; solucion_inicial(1:1,1:2)= 0; %solucion obtenida al generar la solucion %inicial de una vecindad solucion_final(1:1,1:2)= 0; %solucion obtenida despues de generar %la ultima solucion inicial de una vecindad

nv=10;

%nv=# de vecindades(neihborhood) o entornos vecindades(1:nv,1:5)=0 %matriz de vecindades %con "nv" filas y 5 columnas ( x , y=f(x) , radio , a , b ) %donde "x" y "f(x)" son el centro de la vecindad %"radio" de la vecindad es la distancia de "x" a "a" o a "b" %"a" y "b" son los extremos de la vecindad (aleatorios) candidatos(1:np,1:2)=0 %matriz de candidatos % con "np" filas (np=# puntos) % y 2 columnas ( xc , yc=f(xc) )

Lista_tabu(1:nv,1:2)=0 %matriz con la lista tabu %con "nv" filas porque va a sacar 1 punto por cada vecindad %y con 2 columnas ( xt , f(xt) )

hold on %---------------------------------------------------------------------%GRAFICA DE LA FUNCION xg=-(14)*pi:0.1:(14)*pi; %dominio, las x que toma la grafica yg yg= abs( xg.* cos(xg) ); % funcion que vamos a optimizar yg=f(xg) plot(xg,yg,'b') %---------------------------------------------------------------------for i=1:nv x=( (1/7)*pi -((-1/7)*pi) )*rand + ((-1/7)*pi); %genera la solucion inicial en %intervalo ((-1/7)*pi,(1/7)*pi),tambien %tambien genera la "x" del centro %de la vecindad vecindades(i,1)=x; %guarda a "x" en la columna 1 y= abs( x.* cos(x) ); % "x" evaluada en f(x) vecindades(i,2)=y; %guarda a "y=f(x)" en la columna 2 solucion_inicial(1,1)= x ; solucion_inicial(1,2)= y ; %-----------------------------------------------------------------------%VERIFICAR SI LA SOLUCION PERTENECE A LA LISTA TABU if nv > 1 %aqui vamos a checar si la solucion inicial esta en la lista tabú for J=1:nv if solucion_inicial(1,:)==Lista_tabu(J,:) %si sol. esta en tabu x=( (1/7)*pi -((-1/7)*pi) )*rand + ((-1/7)*pi); %genera la solucion inicial en %intervalo ((-1/7)*pi,(1/7)*pi),tambien %genera la "x" del centro de

% la vecindad vecindades(i,1)=x; %guarda a "x" en la columna 1 y= abs( x.* cos(x) ); % "x" evaluada en f(x) vecindades(i,2)=y; %guarda a "y=f(x)" en la columna 2 solucion_inicial(1,1)= x ; solucion_inicial(1,2)= y ; J=1; end end end solucion_inicial plot(x,y,'*r') %grafica las vecindades iteracion = 0; %---------------------------------------------------------------------while iteracion < 100 radio=(3-0)*rand + (0); %se genera un radio aletorio para %la vecindad de tamaño entre 0 y 3 vecindades(i,3)=radio; %guarda a "radio" en la columna 3 b=x + radio; a=x - radio; %nos dan los valores extremos de la vecindad vecindades(i,4)=a; vecindades(i,5)=b; vecindades; %pause(.00000000000000005) plot(x,y,'*r') %grafica las vecindades generadas a partir del %candidato optimo

suma_de_yc=0; %contador para las yc, necesario para la aptitud for j=1:np xc=(b-a)*rand + a; %se genera la "x" del candidato en (a,b) candidatos(j,1)=xc; yc= abs( xc.* cos(xc) ); % "xc" evaluada en f(xc) candidatos(j,2)=yc; suma_de_yc= suma_de_yc + yc ; %suma las yc obtenidas(para aptitud) end candidatos %---------------------------------------------------------------------%APTITUD %necesitamos el candidato mas apto suma_de_yc; % tambien se puede escribirsuma_de_yc= sum(candidatos(:,2)) for k=1:np

aptitud_de_yc(k,1)= candidatos(k,2) / suma_de_yc; %maximizar %aptitud_de_yc(k,1)= 1 - (candidatos(k,2) / suma_de_yc); %minimizar end aptitud_de_yc; suma_de_todas_las_aptitudes=sum(aptitud_de_yc); %la suma de todas las %aptitudes debe ser = 1

%---------------------------------------------------------------------%SELECCION DE CANDIDATOS for m=1:np g=rand; %creo que porque la aptitud esta entre 0 y 1 suma_de_aptitudes=0; w=1; while suma_de_aptitudes