Iti0210lab5

Allikas: Lambda

Lokaalne otsing

Sissejuhatus

Lahendame rändkaupmehe (travelling salesperson problem ehk TSP) lokaalse otsinguga. Kasutame aima-python paketti, kus on vajalikud lokaalse otsingu algoritmid juba olemas. Meie ülesanne on TSP nendele algoritmidele arusaadavalt kirjeldada.

TSP puhul on antud linnad. Tuleb leida lühim võimalik marsruut, mis läbib kõik linnad täpselt ühe korra. Marsruut peab olema suletud, ehk lõpp-punkt on sama mis alguspunkt.

Lokaalse optimumi leidmiseks kasutame 2-opt käiku; vt. wikipedia artikkel.

Lahendame neid ülesannete instantse: Fail:Iti0210lab5.zip. Need on võetud suuremast logistikaülesannete benchmarkide paketist TSPLIB.

Edasises ülesande kirjelduses tuleks sõna "instants" mõista, kui ühte konkreetset ülesande andmete ja parameetrite komplekti - seda terminit kasutatakse tavaliselt publitseeritud benchmarkide puhul.

Ettevalmistus

Hangi endale aima-python või analoogne teek mingis teises keeles (Eelmise nädala juhend).

Kirjuta kood mis loeb ülesande instantsi tekstifailist sisse. Instantsid on sellises formaadis:

 N
 0 d_12 ... d_1N
 d_21 0 ... d_2N
 ...
 d_N1 d_N2 ... 0

Kus N on linnade arv ja d_ij on kaugus linnade i ja j vahel. Sealjuures kui i == j, siis kaugus on alati 0.

Lihtsustamise eesmärgil pole linnade koordinaate vm atribuute antud, mistõttu nende visualiseerimine pole võimalik. See pole aga optimaalse marsruudi leidmiseks ka vajalik. Linnu tähistame numbritega (Pythonis kõige lihtsam võtta vahemik 0..N-1).

TSP kodeerimine

Rändkaupmehe ülesanne tuleb kirjeldada search.Problem klassi kasutades.

Klassi skelett (kui see jääb segaseks, vt uuesti eelmise nädala juhendit):

import search

class TSP(search.Problem):
    def __init__(self, ülejäänud parameetrid):
        # tekitab otsingu algseisu

    def actions(self, state):
        # returnib actionite listi
    
    def result(self, state, action):
        # returnib UUE oleku

    def value(self, state):
        # returnib olekule vastava marsruudi pikkuse

Pane tähele, et path_cost() pole selles ülesandes oluline, kuna me otsime optimaalset olekut, aga selle leidmise käik pole oluline. Samuti ei saa defineerida goal_test() meetodit, kuna me EI TEA, milline lõppolek on.

Oleku esitus

Kuna lahendus peab läbima kõiki linnu, siis on oluline ainult nende järjekord. Seega oleks loomulik esitusviis kasutada Pythoni listi, kus esimene element on esimesena läbitav linn, teine element järgmine linn jne. Eeldame, et iga olek kujutab endast suletud marsruuti, s.t. listi viimane element ja esimene element on ka ühendatud.

Soovi korral võib kasutada ka muud esitust.

__init__()

See meetod peab tekitama mingi algoleku. Võimalikud variandid, kuidas algolekut konstrueerida:

  • linnad numbrite järjekorras
  • linnad juhuslikus järjekorras
  • nearest neighbour ahne otsing

Omista algolek atribuudile self.initial

Millised parameetrid sellel meetodil on, otsusta ise. Oluline on, et otsingu käigus, s.t. TSP klassi sees oleks teada konkreetse instantsi linnade arv ja omavaheliste kauguste maatriks. Võimalikud variandid oleks ette anda instantsi failinimi

Actions ja result

Lokaalse otsingu korral annavad actions() ja result() meetodid naaberolekuid. Naaberolekute leidmiseks kasutame 2-opt käiku (vt wikipedia selgitus). Laename ka oleku tegemise pseudokoodi wikipediast:

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;
}

Kuna see teeb vanast olekust uue oleku, siis sobib ta result() meetodisse, seega actions() meetodi ülesandeks võiks jääda sobivate i, k paaride leidmine.

Leia siin kõik naabrid. Milline neist valitakse, otsustab otsingualgoritm.

value()

Siin tuleb kokku arvutada mingile olekule vastava marsruudi pikkus. Selleks kasuta omavaheliste kauguste maatriksit. Ära unusta, et marsruut on suletud, ehk siis kaugust viimasest punktist algpunkti tuleb ka arvestada.

OLULINE search mooduli otsingufunktsioonid on mõeldud maksimeerimisülesannete jaoks, TSP on aga minimeerimisülesanne. Seetõttu peab value() tagastama teepikkuse vähenemisel SUUREMA numbri. Kuna meid huvitavad ka reaalsed teepikkused, siis võiks teepikkuse arvutamise osa eraldi meetodina hoida.

Sõltuvalt linnade arvust ülesande instantsis võib olla kasulik laiendada olekut nii, et seal sees hoitakse ka hetke summaarset teepikkust. 2-opt käigu tegemisel lahutatakse sealt siis eemaldatud lõikude pikkus ja liidetakse lisatud lõikude pikkus. 17 linna puhul see veel erilist efekti ei anna.

Lokaalse otsingu katsetamine

Kasuta search mooduli funktsioone, et lahendusi otsida. Optimaalsed (või teadaolevad parimd) lahendused on toodud siin.

problem = TSP(sinu parameetrid)
g = search.hill_climbing(problem)
#g = search.simulated_annealing(problem)
# muudame SA parameetreid
#g = search.simulated_annealing(problem, search.exp_schedule(limit=10000))
print(g)

Lisaülesanne

(Mittekohustuslik)

2-opt käikude genereerimine on ajakulukas, igas olekus tekib O(n**2) naaberolekut. On loomulik oletada, et iga linn peaks optimaalses marsruudis olema ühendatud distantsi poolest võimalikult lähedaste linnadega. Kui me vaatame naabrite genereerimisel iga linna juures ainult k lähemat linna, siis väheneb keerukus O(kn) peale.

  1. Tekita tabel, kus iga linna puhul on kirjas k lähimat linna.
  2. Muuda actions() meetodit, nii et 2-opt käike genereeritakse seda tabelit kasutades. Kui linn ühendatakse lahti, siis uus ühendus tekitatakse ainult linnadega, mis on tema läheduses.

See peaks oluliselt kiirendama 48 ja 120 linnaga instantside lahendamist. Mõtle või katseta, kuidas see mõjutab lahenduse kvaliteeti.