ITI0120lab5

Lokaalne otsing

Lahendame rändkaupleja (TSP) ülesannet lokaalse otsinguga. Ülesanded pärinevad logistikaülesannete teegist TSPLIB

Rakendame mäeronimis- ja simulated annealing (SA) algoritme. Neid pole aima-python teegi kasutamisel vaja ise implementeerida.

Ettevalmistus

Laadi alla fail lihtsustatud formaadis väikeste ülesannetega Media:Iti0120lab5.zip. Ülesanded on kõik tekstifaili kujul, kus esimesel real on linnade arv N ning järgmised NxN rida ja veergu annavad paarikaupa kaugused linnade vahel. Kirjuta kood, mis failist linnade kauguste maatsiksi suudab sisse lugeda. Linnad ise on nimetud, tähistame neid kokkuleppeliselt numbritega 0..N-1 või 1-N. Linnade koordinaadid ei ole antud. Edaspidises tekstis ülesande "instants" viitab konkreetsele linnade ja kauguste kombinatsioonile, millel on teegis ka oma nimi, näiteks gr48.

2-Opt heuristik

Kasutame Wikipediast laenatud 2-Opt käigu tegemise algoritmi.

2optSwap(route, i, k) {
       1. take route[0] to route[i-1] and add them in order to new_route
       2. take route[i] to route[k] and add them in reverse order to new_route
       3. take route[k+1] to end and add them in order to new_route
       return new_route;
   }

Siin route on hetkeolek, mis on antud linnade listina samas järjekorras, milles neid läbitakse. i, k on kahe linna indeksid, millest järgmised kaared lahti ühendatakse. See tähendab, et võetakse lahti kaared i, i+1 ja j, j+1. Pane tähele, et listis viimase linna ja kohal 0 asuva linna vahel on ka kaar.

TSP klass

Kui kasutada search.py moodulit, siis tuleb ülesande klass ehitada umbes nii:

class TSP(search.Problem):
    def __init__(self, instance):
        # laadi sisse ülesanne sobival kujul
        # genereeri algolek (võib olla list linnade indeksitest)

    def actions(self, state):
        # siin genereerime võimalikud lahti ühendatavate graafi kaarte paarid 2-Opt jaoks

    def result(self, state, action):
        # siin tekitame uue oleku, kus mingid kaared lahti ühendatakse ja teistpidi kokku ühendatakse, kasutades ülalolevat pseudokoodi.
        # action on üks i, j paar.

    def cost(self, state):
        # arvuta (või leia muul viisil) praeguse marsruudi kogupikkus. Ära unusta, et marsruut on suletud.

    def value(self, state)
        # kuna valmis otsingufunktsioonid arvavad, et mida suurem väärtus, seda parem, siis meie minimeerimisülesande TSP
        # lahendamiseks tuleb teepikkusest pöördväärtus võtta.
        return 1/(self.cost(state)+1)

Kasuta järgmiselt

p = search.InstrumentedProblem(TSP("gr48"))
g = search.hill_climbing(p)
print(g)
print(p.cost(g))

Parameeter "gr48" on lihtsalt näide, see eeldaks, et TSP klass oskab avada "gr48.txt" faili ja sealt andmed sisse laadida. Selle töö võib ka enne ära teha ja TSP klassile juba valmis kauguste maatriksi anda.

SA kasutamine vaikimisi parameetritega ja natuke pikendatud otsinguga:

g = search.simulated_annealing(p)
#g = search.simulated_annealing(p, search.exp_schedule(limit=10000))

Optimaalsed lahendused (mida ei pea saavutama):

Lisaülesanne

Antud kirjelduse järgi lahendades on käikude genereerimine O(N**2) keerukusega linnade arvu N suhtes. Eeldades, et lõpplahenduses on linnad üksteise lähedal, võiks vaadata otsingukäikude genereerimisel ainult linnade paare, kus linn j on linna i k lähima naabri hulgas. Käikude genereerimine oleks siis lineaarse keerukusega O(kN).