Paikallinen hakualgoritmi (Local Search) sisään Java

Paikallinen hakualgoritmi on ohjelmoinnin hakutekniikka Java, joka keskittyy ratkaisujen optimointiin tekemällä hakuja nykyisen ratkaisun läheisyydestä. Koko ratkaisuavaruuden etsimisen sijaan algoritmi keskittyy ratkaisujen etsimiseen pienemmältä "naapurustolta".

Kuinka paikallinen hakualgoritmi toimii

Algoritmi lähtee alkuratkaisusta ja yrittää jatkuvasti parantaa sitä etsimällä parempia ratkaisuja lähiympäristöstä. Algoritmi iteroi läheisten ratkaisujen läpi ja valitsee niistä parhaan ratkaisun.

Paikallisen hakualgoritmin edut ja haitat

Edut:

• Tehokkuus: Algoritmi toimii usein nopeammin suuremmissa ongelmatiloissa etsimällä läheisiä tiloja koko tilan sijaan.
• Integrointi: Voidaan yhdistää muihin menetelmiin haun tehokkuuden parantamiseksi.

Haitat:

• Paikallinen optimi: Algoritmi saattaa konvergoida paikalliseen optimipisteeseen löytämättä globaalia ratkaisua.

Esimerkki ja selitys

Tosielämän esimerkki paikallishakualgoritmista on liikennereitin optimointi. Katsotaan kuinka tämä algoritmi toimii:

import java.util.*;  
  
public class LocalSearchExample {  
    static double evaluateSolution(double[] solution) {  
        // Function to evaluate the quality of a solution  
        // Lower value indicates a better solution  
        return 1.0 /(1.0 + solution[0] + solution[1]);  
    }  
  
    static double[] localSearch(double[] initialSolution, double stepSize, int maxIterations) {  
        double[] currentSolution = Arrays.copyOf(initialSolution, initialSolution.length);  
        double currentEvaluation = evaluateSolution(currentSolution);  
  
        for(int i = 0; i < maxIterations; i++) {  
            double[] nextSolution = Arrays.copyOf(currentSolution, currentSolution.length);  
            nextSolution[0] += stepSize;  
            double nextEvaluation = evaluateSolution(nextSolution);  
  
            if(nextEvaluation < currentEvaluation) {  
                currentSolution = nextSolution;  
                currentEvaluation = nextEvaluation;  
            } else {  
                stepSize /= 2;  
            }  
        }  
  
        return currentSolution;  
    }  
}  

Yllä olevassa esimerkissä käytämme paikallishakualgoritmia numeerisen ratkaisun optimointiin. Algoritmi etsii nykyisen ratkaisun läheisyydestä muuttamalla kiinteää askelta ja tarkistaa, onko uusi ratkaisu parempi. Tuloksena on, että algoritmi löytää asteittain paremman ratkaisun ajan myötä.