caesarius

Buenas gente !!! Les presento el problema del viajero (tsp por sus siglas en ingles)a los que no lo conocen este problema lo vimos en una materia que se llama investgacion operativa, sucede que es un problema combinacional completo, dificil de resolver eficientemente si son muchas las ciudades involucradas , pero bueno, primero les presento el problema y luego les muestro como encare yo el problema :) espero que les sirva! ha y por cierto esto lo hice junto a 2 compañeras :) no les quitemos credito xD 1.ABSTRACT El problema del viajante (también conocido como problema del viajante de comercio o por sus siglas en inglés: TSP) es uno de los problemas más famosos (y quizás el mejor estudiado) en el campo de la matemática computacional. El problema fue formulado por primera vez como un problema matemático en 1930. Dada una lista de las ciudades y sus distancias dos a dos, la tarea es encontrar un recorrido más corto posible que visita cada ciudad exactamente una vez.El problema tiene considerables aplicaciones prácticas, aparte de las más evidentes en áreas de logística de transporte, que cualquier negocio de reparto, pequeño o grande, conoce. Por ejemplo, en robótica, permite resolver problemas de fabricación para minimizar el número de desplazamientos al realizar una serie de perforaciones en una plancha o en un circuito impreso. También puede ser utilizado en control y operativa optimizada de semáforos, etc.El TSP es ya un problema estándar para muchos algoritmos heurísticos como los algoritmos genéticos, el recocido simulado (Simulated Annealing, SA), la búsqueda tabú, el algoritmo hormiga el método Cross-entropy (entropía cruzada). 2.INTRODUCCION TSP uno de los problemas clásicos de optimización, se formula de la siguiente manera: Un agente viajero, partiendo de su ciudad de origen, debe visitar exactamente una vez cada ciudad de un conjunto de ellas (previamente especificado) y retornar al punto de partida. Un recorrido con estas características, es llamado dentro de este contexto un tour. El problema consiste en encontrar el tour para el cual la distancia total recorrida sea minima. Se asume que se conoce, para cada par de ciudades, la distancia entre ellas. El problema en si es fácil de formular. Sin embargo es sumamente difícil de resolver (por resolver, nos referimos a encontrar la solución optima al problema y probar desde luego que esta es efectivamente la mejor solución posible). Esto no implica que el problema no pueda resolverse, sino que cada algoritmo existente para la solución del problema tiene un tiempo de ejecución que crece explosivamente (exponencialmente) con el tamaño del problema. Desde luego hay razones prácticas que hacen importante el TSP. Un problema que se presenta de forma natural en algunas empresas lo podemos encontrar dentro de la logística de distribución de mercancía a los clientes. Un esquema común es que se disponga de un almacén central y una flota de unidades de transporte. Por lo tanto, las unidades de servicio son limitadas; si la empresa dispone de una sola unidad el problema de determinar la ruta que debe seguir el vehiculo para entregar en el menor tiempo posible toda la mercancía es ni mas ni menos que el TSP. Pero aquí hay 2 problemas: puede ser que el tiempo mínimo resulte demasiado largo y por otro lado las unidades tienen una cierta capacidad de almacenamiento y puede ser que se necesiten varias para poder cargar con toda la mercancía que debe ser entregada. Así pues vemos que este problema tiene varios dentro: determinar cual es el tamaño ideal de la flota de vehículos, determinar cuales son los clientes que deben ser asignados cada unidad para hacer la entrega, y cual es la ruta que debe de seguir cada una con el fin de terminar con el reparto en el menor tiempo posible (TSP). Para complicar mas las cosas estos problemas no son independientes, sino que la solución de uno determina la de otro. Este problema se conoce como el problema de ruteo de vehículos (VRP). Obviamente existen muchas aplicaciones más.Tabu Search es una heurística que puede prometer una eficacia cercana a la optima solución al TSP. En primer lugar, búsqueda tabú comienza con una solución inicial, que puede ser generada de acuerdo con el algoritmo del vecino más cercano. Para crear nuevas soluciones, el orden en que se visitan dos ciudades se intercambia. La distancia del viaje en total entre todas las ciudades se utiliza para juzgar lo bueno que es una solución sobre otra. Para evitar ciclos y salir de óptimos locales , una solución se añade a la lista tabú si es aceptado en N * (x), el barrio solución. Las nuevas soluciones siguen siendo creadas, hasta que algunos de los criterios de parada, como un número arbitrario de iteraciones, se cumplen. Una vez que se detiene búsqueda tabú, la mejor solución es la solución con la distancia más corta para el recorrido total entre todas las ciudades.En las siguientes secciones:Sección 3. Se profundizara el problema, presentando el modelo matemático. Sección 4. Se especificará la solución propuesta.Sección 5.Se incluirá la información sobre las instancias de prueba usadas, los parámetros para los algoritmos usados y los resultados obtenidos.Sección 6. Conclusiones. 3.EL PROBLEMA3.1 Profundización del problema En el viajante de comercio, se tiene una red de nodos, que pueden ser ciudades o simplemente lugares de una ciudad. Se parte de un lugar inicial, y deben recorrerse todos sin pasar más de una vez por cada lugar, volviendo al lugar inicial. Para cada arco, se tiene un valor Cij, que indica la distancia o el costo de ir del nodo i al nodo j. Se trata de encontrar en qué orden recorrer los nodos de la red, de modo de minimizar la distancia total recorrida.Dado que en definitiva se busca un circuito o tour completo, es indiferente el lugar que designemos como origen.Es ciertamente sin sentido para algunas aplicaciones la restricción de que no debe pasarse más de una vez por cada ciudad. Sin embargo, si los nodos representan lugares de una ciudad, no hay razón para pasar dos veces por el mismo lugar, y el problema del viajante de comercio se puede aplicar con todo éxito.Este problema también se conoce con el nombre del Agente Viajero, y en inglés, Traveling Salesman Problem (TSP).El problema del viajante de comercio es la base para muchas aplicaciones de reparto de mercadería en una ciudad. Las situaciones reales suelen complicarse con: más de un vehículo de reparto; horarios de reparto impuestos por los clientes; demoras en los lugares de entrega; capacidades en los vehículos, que limitan los recorridos, etc. 3.2 El Enunciado Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante. Es decir, encontrar una permutación P = {c0,c2,...,cn − 1} tal que sea mínimo. La distancia entre cada ciudad viene dada por la matriz D: NxN, donde d[x, y] representa la distancia que hay entre la ciudad X y la ciudad Y.3.3 Modelo MatemáticoSean n nodos, y Cij la distancia para ir de i a j. Sea también Xij una variable entera tal que:(no se ve por ahora lo buscare en internet a la imagen y la subire sorry)Xij = 0 si no se pasa por el arco i,j.Xij = 1 si se pasa por el arco i,j.Entonces, el modelo matemático es: (no se ve por ahora lo buscare en internet a la imagen y la subire sorry)   Las restricciones de la primera sumatoria nos dicen que se debe llegar a todas las ciudades una vez. Las restricciones de la segunda sumatoria nos dicen que se debe salir de todas las ciudades una vez. Si un viajante parte de la ciudad A y las distancias a todas las demás ciudades son conocidas, ¿cuál es la ruta óptima que debe elegir para visitar todas las ciudades y volver a la ciudad de partida? 4.SOLUCION PROPUESTA En nuestro trabajo empleamos HBMO para generar las poblaciones por donde va a ir iterando nuestro algoritmo, teniendo en cuenta una distancia minima entre soluciones. La mejor solución obtenida (reina) la vamos mejorando con 2opt, luego con 3otp ,ambos optimizados con listas tabú . Luego se procede al cruzamiento de esta nueva solución (reina) con los otros zánganos(resto de la población de soluciones). HBMO Obtención de la reina: se generan soluciones pseudo-aleatorias hasta que se alcanza alguna que cumpla con todas las restricciones del problema y dicha solución se transformara en reina; sino, será la solución menos infactible luego de una cierta cantidad de iteraciones. En nuestro Algoritmo la reina inicial será la que posea menor costo en la función objetivo y por cada vuelo de la reina se encontraran nuevas reinas y nuevos zánganos para realizar los cruzamientos.Obtención de los zánganos: son las mejores soluciones infactibles previas a la obtención de la reina.Cruzamiento: la nueva cría se forma por las mejores asignaciones de personal de la reina y ciertas asignaciones del zángano seleccionado para el apareo. Una vez apareado, el zángano muere (es eliminado). En nuestro Algoritmo los zánganos serán zánganos si no son reinas, y un zángano que se aparea y no genera una cría mejor que el mismo no muere sino que se mantiene entre la población. TABU SEARCH La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de búsqueda local mediante el uso de estructuras de memoria: una vez que una potencial solución es determinada, se la marca como "tabú" de modo que el algoritmo no vuelva a visitar esa posible solución. Puede utilizarse para resolver problemas de optimización combinatoria, tales como el problema del viajante (TSP, del inglés Travelling Salesman Problem). La búsqueda tabú utiliza un procedimiento de búsqueda local o por vecindades para moverse iterativamente desde una solución x hacia una solución x' en la vecindad de x, hasta satisfacer algún criterio de parada.Quizás la estructura de memoria más importante usada para determinar las soluciones permitidas a un N * (X), sea la lista tabú. En su forma más simple, una lista tabú es una memoria de corto plazo que contiene las soluciones que fueron visitadas en el pasado reciente (menos de n iteraciones atrás, donde n es el número de soluciones previas que van a ser almacenadas (n también es llamado el tenor del tabú).Dos componentes muy importantes de búsqueda tabú son la intensificación y diversificación de estrategias. Intensificación de las estrategias se basan en la modificación de las normas de elección para atentar a combinaciones y características de soluciones encontradas, históricamente buenas. Esto implica que es necesario identificar un conjunto de soluciones élite, cuyos buenos atributos puedan ser incorporados a nuevas soluciones creadas. La pertenencia al conjunto de soluciones élite se determina generalmente atendiendo a los valores de la función objetivo comparados con la mejor solución obtenida hasta el momento También puede iniciar el retorno a regiones atractivas para buscar más a fondo. Puesto que las soluciones de elite deberán estar registrados, a fin de examinar sus vecindarios inmediatos, la memoria explícita está estrechamente relacionado con la aplicación de las estrategias de intensificación. 2 OPT Para una ruta cualquiera T, decimos que T’ es un 2-vecino de T si T’ se puede obtener a partir de T añadiendo dos ejes y borrando dos ejes.Decimos que es 2-optimo si la longitud de T es menor o igual que la longitud de cada uno de sus 2-vecinos.Algoritmo 2-optIniciar con una ruta factible T Mientras T no sea 2-optimo sustituir T por un 2-vecino de T que tenga una longitud menor.2-opt suele producir buenas soluciones, pero no está garantizado; Siempre elimina los ejes cruzados; Suele estar dentro del 7% de optimalidad. 3 OPT Similar a 2opt, 3opt genera vecinos eliminando 3 ejes y añadiendo otros 3Para una ruta cualquiera T, decimos que T’ es un 3-vecino de T si T’ se puede obtener a partir de T añadiendo tres ejes y borrando tres ejes.Decimos que es 3-optimo si la longitud de T es menor o igual que la longitud de cada uno de sus 3-vecinos.Algoritmo 3-optIniciar con una ruta factible T Mientras T no sea 3-optimo sustituir T por un 3-vecino de T que tenga una longitud menor.5.Pruebas: no seran incluidas en el post puesto que toma mucho tiempo hacerlas y seria bueno que uds mismos probaran si funciona o no el programa :)) 6. CONCLUSIONES En el campo de las metaheurísticas hay frecuentes oportunidades para nuevas ideas donde aplicar la intuición más que la deducción. Los conceptos principales raramente se definen con precisión y todavía hay muy pocos teoremas significativos. Los intentos por organizarlo son numerosos, pero ninguna propuesta ha conseguido una aceptación general. Cada metaheurística tiene su propio punto de vista, pueden explicar otras heurísticas en su propio vocabulario y absorber ideas de todo el campo.El TSP está entre los problemas denominados NP-completos, esto es, los problemas que no se pueden resolver en tiempo polinomial en función del tamaño de la entrada (en este caso el número N de ciudades que el viajante debe recorrer). Sin embargo, algunos casos concretos del problema sí han sido resueltos hasta su optimización, lo que le convierte en un excelente banco de pruebas para algoritmos de optimización que pertenezcan a la misma familia (lo que en jerga matemática se denominan problemas isomorfos). Por lo que se proponen para su resolución métodos Heurísticos. Por ello en este trabajo se diseñó procedimientos basados en la estrategia metaheurística de Búsqueda Tabú, Tabú Search -TS, tal que como hemos probado, brinda mediante movimientos vecinales, una solución eficiente en un tiempo computacional considerable.Las herramientas fueron eficazmente utilizadas y complementadas, unas para mejorar el desempeño de las otras.Además de cumplir con las heurísticas planteadas, este algoritmo tiene en cuenta también las distancias que hay entre las soluciones.Se han alcansado los objetivos del problema al reducir las soluciones a un margen de error a menos del 3% de distancia de la mejor solucion obtenida./* * TSPTabuSearchView.java este documento es creado en su mayor parte por netbeans , es la parte que implementa la interfas grafica de mi trabajo, disociada totalemente de la capa de negocio (eliminada por que el post se hace muy largo si alguie lo quiere que mande mp o comente) *//* * TSPTabuSearchApp.java en esta parte implemento todo lo referido al problema */package tsptabusearch;import org.jdesktop.application.Application;import org.jdesktop.application.SingleFrameApplication;import java.io.*;import java.util.*;import javax.print.attribute.Size2DSyntax;import javax.swing.JLabel; class TabuSearch{ static Vector tabuPoints = new Vector(); static Vector tabuTimes = new Vector(); static boolean busca(int p){ // System.out.println("entre a buscar"); // System.out.println(""); boolean esta=true; // System.out.println("punto buscado "+p+" "); for(int j=0;j<tabuPoints.size();j++){ if (((Integer)tabuPoints.elementAt(j)).intValue()==p){ // System.out.println("punto buscado y encontrado "+p+" "); return esta; } } return !esta; } static void muestraTabu(){ for (int i=0;i<tabuPoints.size();i++){ System.out.print(" "+((Integer)tabuPoints.elementAt(i)).intValue()+" "); } System.out.println(" "); for (int i=0;i<tabuPoints.size();i++){ System.out.print(" "+((Integer)tabuTimes.elementAt(i)).intValue()+" "); } System.out.println(" "); } static boolean addPoint(int t,int p){ int i=0; boolean esta=busca(p); Integer po=new Integer(p); Integer ti=new Integer(t); if(esta==false){ tabuPoints.addElement(po); tabuTimes.addElement(ti); // System.out.println("agregue a "+p+" a la lista tabu"); // muestraTabu(); }else{ // System.out.println(p+" es tabu activo"); // muestraTabu(); } return !esta; } static void decTime(){ int aux; for(int i=0;i<tabuTimes.size();i++){ aux=((Integer)tabuTimes.elementAt(i)).intValue()-1; Integer ax= new Integer(aux); tabuTimes.setElementAt(ax,i); if(((Integer)tabuTimes.elementAt(i)).intValue()==0){ // System.out.println(((Integer)tabuPoints.elementAt(i)).intValue()+" ya no es tabu activo"); tabuTimes.removeElementAt(i); tabuPoints.removeElementAt(i); } } } }class punto { double x; double y; public punto (double e,double i) { x=e; y=i; } void setValores(double e,double i){ x=e; y=i; } double getx(){ return x;} double gety(){ return y;} void muestraPunto(){ System.out.println("x: "+x+" y: "+y); }}public class TSPTabuSearchApp extends SingleFrameApplication { static Vector Data = new Vector(); private static Vector faultList = new Vector(); public static Boolean loadFile(String dirArchivo,int cant) throws IOException{ /*leido el archivo se tubieron problemas con la lectura de las lineas.. por esa razon este procedimiento solo abrira la instancia p654.tsp o alguna otra que tenga exactamente el mismo formato*/ BufferedReader entrada;// ingresar datos por tecladoentrada = new BufferedReader (new InputStreamReader(System.in)); //ingresar datos por teclado File Archivo = new File(dirArchivo); try { entrada = new BufferedReader( new FileReader(Archivo));} catch(FileNotFoundException fnfe) { System.out.println(" Archivo no encontrado "); } catch (IOException ioe) {System.out.println(" Error al leer "); } String linea = entrada.readLine(); String problemName = linea.trim().split(":")[1]; int j=0; int cant_datos=0; Vector data = new Vector(); int c=0; String[] aux; double aux1; double aux2; while (linea!=null){ if (c==5){ j=1;} else if(j==1){ if (c<cant+6){ cant_datos+=1; aux = ((String)linea.trim()).split(" "); aux1=Double.valueOf(aux[1]); aux2=Double.valueOf(aux[2]); punto point = new punto (aux1,aux2); data.add(point); } } linea=entrada.readLine(); c++; } entrada.close(); Data=data; return true; } private static boolean trueDrone(Vector drone,int size){ Vector drine = new Vector(); boolean flagsize=false; boolean flagsum=true; boolean flag=false; int aux=1; int i=1; pegar(drone,drine); if (drone.size()==size){ flagsize=true; } order(drine); while(i<drine.size()){ if (aux!=((Integer)drine.elementAt(i)).intValue()) {flagsum=false; i=drine.size(); } aux++; i++; } if(aux==52){ flagsum=true; } if(flagsize==flagsum==true){ flag=true; } else { if(flagsize!=true){ System.out.println("drone no completo faltan elementos");} else{ System.out.println("drone no completo faltan elementos el primero de ellos es "+aux);} } System.out.println("dronetrue? "+flag); showDrone(drone); return flag; } static Vector getDistanceMatrix(Vector data){ Vector distanceMatrix = new Vector(); int max= data.size(); double X0; double Y0; double X1; double Y1; double distance; for (int i=0; i<max-1;i++){ Vector dist = new Vector (); for (int j=i+1;j<max;j++){ X0=((punto)data.elementAt(i)).getx(); Y0=((punto)data.elementAt(i)).gety(); X1=((punto)data.elementAt(j)).getx(); Y1=((punto)data.elementAt(j)).gety(); distance = getDistance(X0,Y0,X1,Y1); dist.addElement(new Double(distance)); } distanceMatrix.addElement(dist); } return distanceMatrix; } static Vector getInitialPopulation(int rangeOfData,int population,int minDist){ Vector droneList= new Vector(); Vector drone = new Vector(); for (int i=0;i<population ;i++){ drone=getNaiveSolution(rangeOfData); while (!ItsfarEnough(drone,droneList,minDist)){ drone=getNaiveSolution(rangeOfData); } droneList.add(drone); } return droneList; } private static void mostrarMatrizDistancia(Vector distanceMatrix) { int max=distanceMatrix.size(); Vector linea; for (int i=0;i<max;i++){ linea = (Vector)distanceMatrix.elementAt(i); for (int j=0;j<linea.size();j++){ Double dist = (Double)linea.elementAt(j); System.out.print(dist.doubleValue()+" "); } System.out.println(linea.size()+" elementos "); } } static void mostrarMatrizPuntos(Vector data){ int max=data.size(); for (int i=0; i<max;i++){ double X0=((punto)data.elementAt(i)).getx(); System.out.print("x0: "+X0); double Y0=((punto)data.elementAt(i)).gety(); System.out.println(" y0: "+Y0); } } static double getDistance(double X0,double Y0,double X1,double Y1){ double distance = Math.sqrt(Math.pow(X0-X1,2)+ Math.pow(Y0-Y1,2)); return distance; } static double getDistance(Vector drone1,Vector drone2){ int x=0; int y=0; int aux; double aux2; double count=0; for(int i=0;i<drone1.size();i++){ x=((Integer)drone1.elementAt(i)).intValue(); y=((Integer)drone2.elementAt(i)).intValue(); aux=x-y; aux2=Math.pow(aux, 2); count += aux2; } return Math.sqrt(count); } static double getDistance(int X0,int Y0,Vector distanceMatrix){ Vector fila= new Vector(); double distance; if(X0==Y0){ System.out.println("error al tomar la distancia entre "+X0+" y "+Y0); } if (X0<Y0){ fila = (Vector)distanceMatrix.elementAt(X0-1); distance = ((Double)fila.elementAt(Y0-X0-1)).doubleValue(); } else{ fila = (Vector)distanceMatrix.elementAt(Y0-1); distance = ((Double)fila.elementAt(X0-Y0-1)).doubleValue(); } return distance; } static double getObjFunctionValue(Vector distanceMatrix,Vector solution){ double objFunctionValue=0; int max = solution.size(); int vertexI; int vertexJ; Vector filas ; Double dobles; for (int i=0;i<max-1;i++){ vertexI=(Integer)solution.elementAt(i); vertexJ=(Integer)solution.elementAt(i+1); if (vertexI==vertexJ){ System.out.println("error 2 elementos iguales"); return -1; } Vector fila = new Vector(); if (vertexI<vertexJ){ fila=(Vector)distanceMatrix.elementAt(vertexI-1); Double doble = (Double)fila.elementAt(vertexJ-vertexI-1); objFunctionValue += doble.doubleValue(); } else { fila=(Vector)distanceMatrix.elementAt(vertexJ-1); Double doble = (Double)fila.elementAt(vertexI-vertexJ-1); objFunctionValue += doble.doubleValue(); } } vertexI = (Integer)solution.elementAt(max-1); vertexJ = (Integer)solution.elementAt(0); if (vertexI<vertexJ){ filas = (Vector) distanceMatrix.elementAt(vertexI-1); dobles = (Double)filas.elementAt(vertexJ-vertexI-1); objFunctionValue += dobles.doubleValue(); } else { filas = (Vector) distanceMatrix.elementAt(vertexJ-1); dobles = (Double)filas.elementAt(vertexI-vertexJ-1); objFunctionValue += dobles.doubleValue(); } return objFunctionValue; } static boolean itsOnIt(int b ,Vector sol){ boolean ret=false; for (int i=0; i<sol.size();i++){ if (((Integer)sol.elementAt(i)).intValue()==b){ ret=true; } } return ret; } static Vector getNaiveImproveSolution(int size,int flights,Vector distanceMatrix){ Vector sol = new Vector(); sol=getNaiveSolution(size); for(int i=0;i<flights;i++){ sol=apply3opt(sol,distanceMatrix,false); sol=apply2opt(sol,distanceMatrix,false); } return sol; } static Vector getNaiveSolution(int rangeOfData){ Vector solution= new Vector(); int max= rangeOfData; Random rand = new Random(); boolean flag; for (int i=0;i<max;i++){ int vertexAtRandom=rand.nextInt(max)+1; flag = itsOnIt(vertexAtRandom,solution); while (flag){ vertexAtRandom=rand.nextInt(max)+1; flag = itsOnIt(vertexAtRandom,solution); } solution.addElement(new Integer(vertexAtRandom)); } return solution; } /* static int getDrones() throws IOException{ System.out.println("ingrese el numero de zanganos: "); BufferedReader entrada;// ingresar datos por tecladoentrada = new BufferedReader (new InputStreamReader(System.in)); //ingresar datos por teclado String linea = entrada.readLine(); entrada.close(); return Integer.valueOf(linea); } static int getFlights() throws IOException{ System.out.println("ingrese el numero de vuelos de la reina: "); BufferedReader entrada;// ingresar datos por tecladoentrada = new BufferedReader (new InputStreamReader(System.in)); //ingresar datos por teclado String linea = entrada.readLine(); entrada.close(); return Integer.valueOf(linea); } static int getProbability() throws IOException{ System.out.println("ingrese probabilidad: "); BufferedReader entrada;// ingresar datos por tecladoentrada = new BufferedReader (new InputStreamReader(System.in)); //ingresar datos por teclado String linea = entrada.readLine(); entrada.close(); return Integer.valueOf(linea); } */ static void showDrone(Vector drone){ for (int i=0;i<drone.size();i++){ System.out.print(" "+(Integer)drone.elementAt(i)+" "); } System.out.println(); } static void showDist(Vector drone){ for (int i=0;i<drone.size();i++){ System.out.print(" "+(Double)drone.elementAt(i)+" "); } System.out.println(); } static int getWorstSolution(Vector distanceMatrix,Vector Poblacion){ int max=Poblacion.size(); int maxPos= 0; double maxi=0; double aux=0; for(int i=0;i<max;i++){ aux=getObjFunctionValue(distanceMatrix,(Vector)Poblacion.elementAt(i)); if (aux==-1){ return -1; } if (aux > maxi){ maxi=aux; maxPos=i; } } return maxPos; } static int getOptimalSolution(Vector distanceMatrix,Vector Poblacion){ int max=Poblacion.size(); int minPos= 0; double min=999999999; double aux=0; for(int i=0;i<max;i++){ aux=getObjFunctionValue(distanceMatrix,(Vector)Poblacion.elementAt(i)); if (aux < min){ min=aux; minPos=i; } } return minPos; } static Vector getPorcion(int f, int t, Vector partido){ Vector aux= new Vector(); for (int i=f ;i<=t ;i++){ aux.addElement((Integer)partido.get(i)); } return aux; } static Vector reverse(Vector partido){ Vector aux = new Vector(); int k= partido.size()-1; for(int i=k ; i>=0 ;i-- ){ aux.add(partido.elementAt(i)); } return aux; } static void pegar(Vector solution,int min,int max, Vector aux){ int j=0; for(int i=min;i<=max;i++){ solution.setElementAt(aux.elementAt(j), i); j++; } } static void pegar(Vector esto,Vector aqui){ int max=esto.size(); aqui.removeAllElements(); for(int i=0;i<max;i++){ aqui.addElement((Integer)esto.elementAt(i)); } } static int buscar(int b,Vector sol){ int aux=-1; int i=0; while ( i<sol.size()){ if (((Integer)sol.elementAt(i)).intValue()==b){ return i; } i++; } return -1; } static void InitializeFault(Vector faultList,int drones){ for(int f=0;f<drones;f++){ Boolean aux = false; faultList.setElementAt(aux, f); } } private static boolean ItsfarEnough(Vector drone, Vector droneList, int minDist) { boolean flag = true; double dist=0; for (int i=0;i<droneList.size();i++){ dist=getDistance(drone,(Vector)droneList.elementAt(i)); if (dist<minDist){ flag=false; return flag; } } return flag; } private static int findNext(Vector positions,int size) { int aux=0; int i=0; while ( i<positions.size()){ if (((Integer)positions.elementAt(i)).intValue()!=aux){ i=positions.size(); return aux; } i++; aux++; } if (aux<size){ return aux;} else{return -1;} } private static void order(Vector positions) { Integer aux; for(int i=0;i<positions.size()-1;i++){ for(int j=i+1;j<positions.size();j++){ if(((Integer)positions.elementAt(i)).intValue()>((Integer)positions.elementAt(j)).intValue()){ aux=(Integer)positions.elementAt(i); positions.setElementAt((Integer)positions.elementAt(j), i); positions.setElementAt(aux, j); } } } } private static void ititializeChild(Vector child) { for (int i=0;i<child.size();i++){ Integer aux = new Integer(0); child.setElementAt(aux,i); } } static Vector blocal (Vector solution, Vector distanceMatrix){ Vector Menor = new Vector(solution); double fo=getObjFunctionValue(distanceMatrix,solution); double NFO; for(int k=0;k<solution.size()-1;k++){ for (int l=k+1;l<solution.size();l++){ Vector backup = new Vector(solution); if (k!=l){ Integer aux = (Integer)backup.set(k, (Integer)backup.elementAt(l)); backup.set(l,aux); NFO = getObjFunctionValue(distanceMatrix,backup); if (fo>NFO){ fo=NFO; Menor.removeAllElements(); Menor=backup; } } } } return Menor; } static Vector apply2opt(Vector solution,Vector distanceMatrix,boolean tabuSwitch){ int rangeOfData=solution.size(); TabuSearch ltabu = new TabuSearch(); double D1; double D2; Vector aux= new Vector(); Vector BSolTabu= new Vector(); Vector sol2= new Vector(); pegar(solution,sol2); int auxi; int auxi1; int auxj; int auxj1; boolean fi; boolean fi1; boolean fj; boolean fj1; pegar(solution,BSolTabu); double solV=0; double BSolTabuV=0; for (int i=1;i<rangeOfData-3;i++){ for (int j=i+2;j<rangeOfData-1;j++){ auxi=((Integer)sol2.elementAt(i)).intValue(); auxi1=((Integer)sol2.elementAt(i+1)).intValue(); auxj=((Integer)sol2.elementAt(j)).intValue(); auxj1=((Integer)sol2.elementAt(j+1)).intValue(); D1=getDistance(auxi,auxi1,distanceMatrix)+getDistance(auxj,auxj1,distanceMatrix); D2=getDistance(auxi,auxj,distanceMatrix)+getDistance(auxi1,auxj1,distanceMatrix); if ((D1>D2)&&!(tabuSwitch)){ aux= getPorcion(i+1,j,sol2); aux = reverse(aux); pegar (sol2,i+1,j,aux);} else{ if(tabuSwitch){ ltabu.decTime(); fi=ltabu.addPoint(10, auxi); fi1=ltabu.addPoint(10, auxi1); fj=ltabu.addPoint(10, auxj); fj1=ltabu.addPoint(10, auxj1); if((fi)&&(fi1)&&(fj)&&(fj1)){ aux= getPorcion(i+1,j,sol2); aux = reverse(aux); pegar (sol2,i+1,j,aux); solV=getObjFunctionValue(distanceMatrix,sol2); BSolTabuV=getObjFunctionValue(distanceMatrix,BSolTabu); if(solV<BSolTabuV){ pegar(sol2,BSolTabu); } } } } } } if(tabuSwitch){ solV=getObjFunctionValue(distanceMatrix,sol2); BSolTabuV=getObjFunctionValue(distanceMatrix,BSolTabu); if(solV<BSolTabuV){ return sol2; } else{ return BSolTabu; } } return sol2; } static Vector apply3opt(Vector solution, Vector distanceMatrix, boolean tabuSwitch){ TabuSearch ltabu = new TabuSearch(); int rangeOfData=solution.size(); Vector sol2 = new Vector(); Vector aux = new Vector(); Vector aux2 = new Vector(); Vector BSolTabu = new Vector(); double D1; double D2; double d1; double d2; double d3; int auxi; int auxj; int auxk; int auxi1; int auxj1; int auxk1; boolean fi; boolean fi1; boolean fj; boolean fj1; boolean fk; boolean fk1; pegar(solution,sol2); pegar(solution,BSolTabu); double solV=0; double BSolTabuV=0; for (int i=0;i<rangeOfData-7;i++){ for (int j=i+2;j<rangeOfData-5;j++){ for (int k=j+2;k<rangeOfData-3;k++){ auxi=((Integer)sol2.elementAt(i)).intValue(); auxj=((Integer)sol2.elementAt(j)).intValue(); auxk=((Integer)sol2.elementAt(k)).intValue(); auxi1=((Integer)sol2.elementAt(i+1)).intValue(); auxj1=((Integer)sol2.elementAt(j+1)).intValue(); auxk1=((Integer)sol2.elementAt(k+1)).intValue(); d1=getDistance(auxi,auxi1,distanceMatrix); d2=getDistance(auxj,auxj1,distanceMatrix); d3=getDistance(auxk,auxk1,distanceMatrix); D1=d1+d2+d3; d1=getDistance(auxi,auxj,distanceMatrix); d2=getDistance(auxi1,auxk,distanceMatrix); d3=getDistance(auxj1,auxk1,distanceMatrix); D2=d1+d2+d3; if ((D1>D2)&&!(tabuSwitch)){ pegar(sol2,aux2); aux= getPorcion(i+1,j,aux2); aux = reverse(aux); pegar (aux2,i+1,j,aux); aux= getPorcion(j+1,k,aux2); aux = reverse(aux); pegar (aux2,j+1,k,aux); pegar(aux2,sol2); aux2.removeAllElements(); aux.removeAllElements();} else{ if(tabuSwitch){ ltabu.decTime(); fi=ltabu.addPoint(10, auxi); fi1=ltabu.addPoint(10, auxi1); fj=ltabu.addPoint(10, auxj); fj1=ltabu.addPoint(10, auxj1); fk=ltabu.addPoint(10, auxk); fk1=ltabu.addPoint(10, auxk1); if((fi)&&(fi1)&&(fj)&&(fj1)&&(fk)&&(fk1)){ pegar(sol2,aux2); aux= getPorcion(i+1,j,aux2); aux = reverse(aux); pegar (aux2,i+1,j,aux); aux= getPorcion(j+1,k,aux2); aux = reverse(aux); pegar (aux2,j+1,k,aux); pegar(aux2,sol2); aux2.removeAllElements(); aux.removeAllElements(); solV=getObjFunctionValue(distanceMatrix,sol2); BSolTabuV=getObjFunctionValue(distanceMatrix,BSolTabu); if(solV<BSolTabuV){ pegar(sol2,BSolTabu); } } } } } } } if(tabuSwitch){ solV=getObjFunctionValue(distanceMatrix,sol2); BSolTabuV=getObjFunctionValue(distanceMatrix,BSolTabu); if(solV<BSolTabuV){ return sol2; } else{ return BSolTabu; } } return sol2; } static Vector circularCrossOver(Vector madre,Vector padre,int size,double probability){ Vector child = new Vector(); Vector positions = new Vector(); pegar(padre,child); ititializeChild(child); Random rand = new Random(); boolean flag=false; int mPoint=-1; int pPoint=-1; int mPosition=-1; int pPosition=-1; int next=0; double prob=0; int choise; prob=rand.nextDouble(); if(prob<probability){ choise=0; } else{ choise=1; } if (choise==0){ mPosition=0; positions.addElement(new Integer(mPosition)); mPoint=((Integer)madre.elementAt(mPosition)).intValue(); child.setElementAt(new Integer(mPoint),mPosition); } else{ pPosition=0; positions.addElement(new Integer(pPosition)); pPoint=((Integer)padre.elementAt(pPosition)).intValue(); child.setElementAt(new Integer(pPoint),pPosition); } while (flag==false){ if (choise==0){ pPoint=((Integer)padre.elementAt(mPosition)).intValue(); mPosition=buscar(pPoint,madre); mPoint=((Integer)madre.elementAt(mPosition)).intValue(); child.setElementAt(new Integer(mPoint),mPosition); }else{ mPoint=((Integer)madre.elementAt(pPosition)).intValue(); pPosition=buscar(mPoint,padre); pPoint=((Integer)padre.elementAt(pPosition)).intValue(); child.setElementAt(new Integer(pPoint),pPosition); mPosition=pPosition; } if ((itsOnIt(mPosition,positions))){ flag=true; } else{ positions.addElement(new Integer(mPosition));} if (flag==true){ order(positions); next=findNext(positions,size); if (next!=-1){ flag = false; if (choise==0) {choise=1; pPoint=((Integer)padre.elementAt(next)).intValue(); child.setElementAt(new Integer(pPoint),next); pPosition=next; } else{ if (choise==1) {choise=0; mPoint=((Integer)madre.elementAt(next)).intValue(); child.setElementAt(new Integer(mPoint),next); mPosition=next; } } } } } return child; } static Vector randomCrossOver(Vector madre,Vector padre,double probability){ int max= madre.size(); Random rand = new Random(); double valueAtRandom; int aux; boolean itsOnIt; Vector child = new Vector(); for (int i=0;i<max;i++){ valueAtRandom=rand.nextDouble(); if (valueAtRandom<probability){ aux=((Integer)madre.elementAt(i)).intValue(); itsOnIt=itsOnIt(aux,child); while(itsOnIt){ aux=rand.nextInt(max)+1; itsOnIt=itsOnIt(aux,child); } child.addElement(aux); }else { aux=((Integer)padre.elementAt(i)).intValue(); itsOnIt=itsOnIt(aux,child); while(itsOnIt){ aux=rand.nextInt(max)+1; itsOnIt=itsOnIt(aux,child); } child.addElement(aux); } } return child; } static Vector applyCrossOver(Vector mother,Vector father,double probability,Vector distanceMatrix,int size){ int max=mother.size(); Vector child= new Vector(); Random rand = new Random(); boolean itsOnIt=false; double valueAtRandom; child = circularCrossOver(mother,father,size,probability); double d1=getObjFunctionValue(distanceMatrix,child); double d2=getObjFunctionValue(distanceMatrix,father); if (d1<d2){ System.out.println("el drone :"); showDrone(child); System.out.println("fue generado por crusamiento mejorando"); System.out.println(d1+"<"+d2); return child; } else{ return father; } } static void showFault(Vector faults){ for(int i=0;i<faults.size();i++){ System.out.print(" "+((Boolean)faults.elementAt(i))+" "); } System.out.println(" "); } static double solveTSP(int flights,double probability,int drones,double restartValue,JLabel label){ //inicio de las definiciones for(int f=0;f<drones;f++){ Boolean aux = false; faultList.add(aux.FALSE); } int OptimalPos=0; int WorstPos=0; Vector droneList = new Vector(); Vector Bsolution=new Vector(); Vector distanceMatrix= new Vector(); Vector aux= new Vector(); System.out.println("obtengo la matriz distancia"); distanceMatrix = getDistanceMatrix(Data); //genero la Poblacion Inicial int MinDist = 100; System.out.println("obtengo la poblacion inicial"); System.out.println("cant de puntos "+Data.size()); droneList=getInitialPopulation(Data.size(),drones,MinDist); System.out.println("poblacion Inicial"); for(int i=0;i<droneList.size();i++){ showDrone((Vector)droneList.elementAt(i)); System.out.println("valor de func Obj: "+getObjFunctionValue(distanceMatrix,(Vector)droneList.elementAt(i))); System.out.println("can datos"+((Vector)droneList.elementAt(i)).size());} System.out.println(""); InitializeFault(faultList,drones); //aplico crusamiento a la poblacion por cada "vuelo de la reina" for (int i=0;i<flights;i++){ System.out.println("vuelo "+(i+1)) ; System.out.println(""); System.out.println(""); System.out.println("poblacion + 3opt"); showFault(faultList); System.out.println(""); double valueOld=0; double valueNew=0; for (int j=0;j<droneList.size();j++){ //aplico 3opt a Bsolution Bsolution=apply3opt((Vector)droneList.elementAt(j),distanceMatrix,false); valueNew=getObjFunctionValue(distanceMatrix,Bsolution); valueOld=getObjFunctionValue(distanceMatrix,(Vector)droneList.elementAt(j)); if (valueNew<valueOld*(1-restartValue)){ if (((Boolean)faultList.elementAt(j)).booleanValue()==true){ faultList.setElementAt(new Boolean(false),j); } droneList.setElementAt(Bsolution,j); } else{ if (((Boolean)faultList.elementAt(j)).booleanValue()==true){ faultList.setElementAt(new Boolean(false),j); valueOld=getObjFunctionValue(distanceMatrix,(Vector)droneList.elementAt(j)); aux=apply3opt((Vector)droneList.elementAt(j),distanceMatrix,true); valueNew=getObjFunctionValue(distanceMatrix,aux); OptimalPos=getOptimalSolution(distanceMatrix,droneList); if (OptimalPos!=j){ droneList.setElementAt(aux,j);/* System.out.println("segunda falta del vector numero "+j); System.out.println("el vector numero "+j+" fue reiniciado y se logro"); showDrone(aux); System.out.println("valor de func Obj: "+getObjFunctionValue(distanceMatrix,aux)); System.out.println("porcentaje de diferencia con el original "+(valueNew/valueOld));*/ System.out.println("el vector fue reiniciado"+j); System.out.println("valor de func Obj: "+getObjFunctionValue(distanceMatrix,aux)); System.out.println("porcentaje de diferencia con el original "+(valueNew/valueOld)); } } else{/* System.out.println("primera falta del vector numero "+j); System.out.println("no supero el "+(1-restartValue)+"% del original"); System.out.println("porcentaje de diferencia con el original "+(valueNew/valueOld));*/ faultList.setElementAt(new Boolean(true),j); } } showDrone((Vector)droneList.elementAt(j)); System.out.println("valor de func Obj: "+getObjFunctionValue(distanceMatrix,(Vector)droneList.elementAt(j))); System.out.println("porcentaje de diferencia con el original "+(valueNew/valueOld)); } showFault(faultList); System.out.println(""); System.out.println("poblacion + 2opt"); System.out.println(""); for (int j=0;j<droneList.size();j++){ //aplico 2opt a Bsolution Bsolution=apply2opt((Vector)droneList.elementAt(j),distanceMatrix,false); valueNew=getObjFunctionValue(distanceMatrix,Bsolution); valueOld=getObjFunctionValue(distanceMatrix,(Vector)droneList.elementAt(j)); if (valueNew<valueOld*(1-restartValue)){ if (((Boolean)faultList.elementAt(j)).booleanValue()==true){ faultList.setElementAt(new Boolean(false),j); } droneList.setElementAt(Bsolution,j); } else{ if (((Boolean)faultList.elementAt(j)).booleanValue()==true){ OptimalPos=getOptimalSolution(distanceMatrix,droneList); if (OptimalPos!=j){ faultList.setElementAt(new Boolean(false),j); valueOld=getObjFunctionValue(distanceMatrix,(Vector)droneList.elementAt(j)); aux=apply2opt((Vector)droneList.elementAt(j),distanceMatrix,true); valueNew=getObjFunctionValue(distanceMatrix,aux); droneList.setElementAt(aux,j); /* System.out.println("segunda falta del vector numero "+j); System.out.println("el vector numero "+j+" fue reiniciado y se logro"); showDrone(aux); System.out.println("valor de func Obj: "+getObjFunctionValue(distanceMatrix,aux)); System.out.println("porcentaje de diferencia con el original "+(valueNew/valueOld));*/ System.out.println("el vector fue reiniciado"+j); System.out.println("valor de func Obj: "+getObjFunctionValue(distanceMatrix,aux)); System.out.println("porcentaje de diferencia con el original "+(valueNew/valueOld)); } } else{/* System.out.println("primera falta del vector numero "+j); System.out.println("no supero el "+(1-restartValue)+"% del original"); System.out.println("porcentaje de diferencia con el original "+(valueNew/valueOld));*/ faultList.setElementAt(new Boolean(true),j); } } showDrone((Vector)droneList.elementAt(j)); System.out.println("valor de func Obj: "+getObjFunctionValue(distanceMatrix,(Vector)droneList.elementAt(j))); System.out.println("porcentaje de diferencia con el original "+(valueNew/valueOld)); } showFault(faultList); System.out.println(""); System.out.println(" cruzamiento!!"); System.out.println(""); OptimalPos=getOptimalSolution(distanceMatrix,droneList); for (int j=0;j<droneList.size();j++){ if (OptimalPos!=j){ //aplico crusamiento para un drone con la reina(elemento en OptimalPos) Bsolution=applyCrossOver((Vector)droneList.elementAt(OptimalPos),(Vector)droneList.elementAt(j),probability,distanceMatrix,Data.size()); droneList.setElementAt(Bsolution, j); } } System.out.println("poblacion + cruzamiento"); for(int k=0;k<droneList.size();k++){ showDrone((Vector)droneList.elementAt(k)); System.out.println("valor de func Obj: "+getObjFunctionValue(distanceMatrix,(Vector)droneList.elementAt(k))); } System.out.println(""); //blocal OptimalPos=getOptimalSolution(distanceMatrix,droneList); Bsolution=(Vector)droneList.elementAt(OptimalPos); Bsolution=blocal(Bsolution,distanceMatrix); if(getObjFunctionValue(distanceMatrix,(Vector)droneList.elementAt(OptimalPos))>getObjFunctionValue(distanceMatrix,Bsolution)){ droneList.setElementAt(Bsolution, OptimalPos); } OptimalPos=getOptimalSolution(distanceMatrix,droneList); label.setText("la mejor solucion hasta ahora es la numero "+OptimalPos); } //aplico blocal a Bsolution OptimalPos=getOptimalSolution(distanceMatrix,droneList); Bsolution=(Vector)droneList.elementAt(OptimalPos); Bsolution=blocal(Bsolution,distanceMatrix); droneList.setElementAt(Bsolution,OptimalPos); System.out.println(""); System.out.println("mejor solucion + blocal"+getObjFunctionValue(distanceMatrix,Bsolution)); System.out.println("cant ciudades "+Bsolution.size()); System.out.println(""); //valor de Bsolution-2opt-blocal OptimalPos=getOptimalSolution(distanceMatrix,droneList); return getObjFunctionValue(distanceMatrix,(Vector)droneList.elementAt(OptimalPos)); } @Override protected void startup() { show(new TSPTabuSearchView(this)); } /** * This method is to initialize the specified window by injecting resources. * Windows shown in our application come fully initialized from the GUI * builder, so this additional configuration is not needed. */ @Override protected void configureWindow(java.awt.Window root) { } /** * A convenient static getter for the application instance. * @return the instance of TSPTabuSearchApp */ public static TSPTabuSearchApp getApplication() { return Application.getInstance(TSPTabuSearchApp.class); } /** * Main method launching the application. */ public static void main(String[] args) { launch(TSPTabuSearchApp.class, args); }}