on mayo 4, 2023

COMPARTE ESTE ARTÍCULO

Scatter Search es un algoritmo de optimización basado en metaheurísticas que se utiliza para resolver problemas de optimización combinatoria. El algoritmo utiliza dos conjuntos principales: P y R. El conjunto P es un conjunto de soluciones de referencia, mientras que el conjunto R es un conjunto de soluciones generadas a partir de las soluciones en P. Estos dos conjuntos se utilizan en conjunto para explorar el espacio de búsqueda y encontrar soluciones de alta calidad.

El algoritmo Scatter Search se puede dividir en las siguientes etapas:

Inicialización: En esta etapa, se crea un conjunto inicial de soluciones (generalmente aleatorias o generadas mediante heurísticas simples) y se seleccionan las mejores soluciones para formar el conjunto P. Este conjunto es el conjunto de soluciones de referencia que se utilizará en las siguientes etapas del algoritmo.
Combinación: Durante la fase de combinación, se generan nuevas soluciones a partir de las soluciones en el conjunto P. Estas nuevas soluciones se crean combinando características de dos o más soluciones de P. Por ejemplo, en el caso del problema del viajante de comercio, se podrían combinar partes de dos rutas diferentes para crear una nueva ruta. Las soluciones generadas se almacenan en el conjunto R.
Mejora: En esta etapa, se pueden aplicar técnicas de búsqueda local u otras heurísticas de mejora a las soluciones en el conjunto R. Esto ayuda a refinar las soluciones generadas y mejorar la calidad general del conjunto R.
Actualización de P: A continuación, se seleccionan las mejores soluciones de la unión de P y R y se utilizan para actualizar el conjunto P. Esto puede implicar reemplazar algunas soluciones en P con soluciones más prometedoras de R. El objetivo es mantener la diversidad en el conjunto P, mientras se asegura de que las soluciones de alta calidad estén representadas.
Criterio de parada: El algoritmo repite los pasos 2-4 hasta que se cumpla un criterio de parada, como un número máximo de iteraciones o el tiempo de ejecución.

El algoritmo Scatter Search se basa en la idea de que al combinar las características de las soluciones de alta calidad en P y explorar el espacio de búsqueda a través de la generación y mejora de soluciones en R, es posible encontrar soluciones de alta calidad de manera eficiente. Además, la actualización de P con soluciones de R asegura que el algoritmo continúe explorando diferentes áreas del espacio de búsqueda y no se estanque en soluciones locales subóptimas.

Cómo implementarlo en Java

Scatter Search es un algoritmo metaheurístico basado en la evolución de un conjunto de soluciones a lo largo del tiempo. A continuación, se presenta una implementación simple de Scatter Search en Java. Esta implementación se basa en dos conjuntos, P y R, y se enfoca en resolver el problema de optimización del viajante de comercio (TSP).

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class ScatterSearch {

    public static class Route {
        List<Integer> cities;
        double cost;

        public Route(List<Integer> cities, double cost) {
            this.cities = cities;
            this.cost = cost;
        }
    }

    public static double[][] distanceMatrix;

    public static void main(String[] args) {
        int numberOfCities = 10;
        int numberOfSolutions = 5;
        int maxIterations = 100;

        distanceMatrix = generateRandomDistanceMatrix(numberOfCities);
        List<Route> P = generateInitialSolutions(numberOfSolutions, numberOfCities);
        List<Route> R = new ArrayList<>();

        for (int iter = 0; iter < maxIterations; iter++) {
            R.clear();

            for (int i = 0; i < P.size() - 1; i++) {
                for (int j = i + 1; j < P.size(); j++) {
                    Route newRoute = combineRoutes(P.get(i), P.get(j));
                    R.add(newRoute);
                }
            }

            R.addAll(P);
            R.sort((r1, r2) -> Double.compare(r1.cost, r2.cost));

            P.clear();
            for (int i = 0; i < numberOfSolutions; i++) {
                P.add(R.get(i));
            }

            System.out.printf("Iteración %d: Mejor costo = %.2f%n", iter + 1, P.get(0).cost);
        }
    }

    public static double[][] generateRandomDistanceMatrix(int n) {
        Random random = new Random();
        double[][] matrix = new double[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double distance = random.nextDouble() * 100;
                matrix[i][j] = distance;
                matrix[j][i] = distance;
            }
        }

        return matrix;
    }

    public static List<Route> generateInitialSolutions(int numSolutions, int numCities) {
        List<Route> solutions = new ArrayList<>();

        for (int i = 0; i < numSolutions; i++) {
            List<Integer> cities = new ArrayList<>();
            for (int j = 0; j < numCities; j++) {
                cities.add(j);
            }
            Collections.shuffle(cities);
            double cost = calculateRouteCost(cities);
            solutions.add(new Route(cities, cost));
        }

        return solutions;
    }

    public static Route combineRoutes(Route r1, Route r2) {
        List<Integer> newCities = new ArrayList<>(r1.cities);

        for (Integer city : r2.cities) {
            if (!newCities.contains(city)) {
                newCities.add(city);
            }
        }

        double newCost = calculateRouteCost(newCities);

        return new Route(newCities, newCost);
    }

    public static double calculateRouteCost(List<Integer> cities) {
        double cost = 0;

        for (int i = 0; i < cities.size() - 1; i++) {
            cost += distanceMatrix[cities].get(i)][cities.get(i + 1)];
}
cost += distanceMatrix[cities.get(cities.size() - 1)][cities.get(0)];
    return cost;
}

    
 
 
         
   Maria Del Carmen Hernandez Herrera 
 
 
 
  Contacte con Alejandro por recomendación de una compañera de trabajo a la cuál ayudó mucho en la preparación de unos exámenes muy complicados . La física y química para mi hija en este curso estaba siendo muy complicada, tanto es así ,que suspendió la primera evaluación y ella no había suspendido nunca, desde que acude a sus clases hay un antes y un después ...... Alejandro con su manera de explicar ha conseguido que las entienda , que pueda desarrollar los problemas que tenga confianza en sí misma....tanto es así que ha aprobado todos los exámenes....Paula está súper contenta y yo más!!!! Siempre que tengo alguna duda o que necesito modificar un horario responden super pronto y buscan solución motivo por el cuál recomiendo al 100% está academia. Muchas gracias por su ayuda.
  
 
        
   Arianna Del Campo Martín 
 
 
 
  Yo soy estudiante universitaria, muy finalista y que llegó a la academia con prácticamente cero base… Finalmente aprobé mi examen! Aquí de una manera diferente a lo que convencionalmente se espera de los profes, me enseñaron, muy cercanamente lo que me proporcionó confianza para no callarme las dudas y preguntar todo el tiempo. Me sorprendió que el profe que me dio clases en particular era como una enciclopedia andante, sin necesidad de mirar los libros me decía fórmulas de memoria que son difíciles de entender hasta con ellas delante. Recomiendo 100%
  
 
        
   Ariana García Esquivel 
 
 
 
  No he dudado ni por un segundo que haber asistido a las clases con Alejandro es lo mejor que me ha pasado… No solamente te apoya académicamente, sino que apoya al alumno a pesar de sus dificultades, y a mí me ha estado ayudando muchísimo y en mis peores momentos. Mil gracias por tus consejos, por siempre darme ánimos, por ser tan simpático que alegras las clases aburridas y por ser un profe tan bueno, son de estas personas que nunca olvidas.❤️👏🏻 También he de decir que Raúl, el otro profesor que se encuentra en la academia…es una persona que se preocupa por el alumno a que haga las cosas bien, con tranquilidad, está siempre pendiente a ti, tiene mucha paciencia, dedica a dar sus clases lo más dinámico posible, tiene mucha amabilidad con las personas, en definitiva… tengo a los dos mejores profesores del mundo, se os quiere mucho💓✨.
  
 
        
   Another Weasley. 
 
 
 
  He tenido muchos profes, y muchos particulares, pero como Alejandro ninguno, de verdad, me hace pensar que de verdad no soy tan mala en lo mío 🥺 me apoya muchísimo y me ayuda en todo lo que pueda con mi carrera, es un profesor 10 y una persona sobretodo 10000 Gracias Ale por preocuparte por tus alumnos, por intentar que estén motivados, que las clases sean entretenidas, y lo bien y fácil que explicas !  Para mi, LOS MEJORES 💖 -alba
  
 
        
   yarel febles 
 
 
 
  He entrado a la carrera de enfermería gracias a Alejandro, sin duda estoy súper contento con mi paso por aquí :)
  
 
        
   Ana Carina Benta 
 
 
 
  Gracias por el ambiente familiar Gracias por la paciencia Gracias por la enseñanza Gracias por el apoyo Gracias por la Motivación!! Simplesmente Gracias!! Recomendable 1000%
  
 
        
   Yanet Palacio valdes 
 
 
 
  Desde hace un tiempo mi hijo asiste a la academia, pensabamos no sacaba la eso y hoy con orgullo se gradúa de 4to de la eso,muy agradecida por los profesores,sobre todo su profe Alejando persona entrañable,justo, para el todo nuestro agradecimiento..⭐⭐⭐👌👌
  
 
        
   Mabett Duque 
 
 
 
  ¡De lo bueno lo mejor, y de lo mejor lo superior!
  
 
  
 
  
 
   La evaluación general en Google es 4.4 de 5, en base a 27 reseñas