Haku kielloilla

Tabuhaku tai tabuhaku on metahakualgoritmi, joka käyttää paikallisia hakumenetelmiä , joita käytetään matemaattiseen optimointiin . Algoritmin loi Fred W. Glover vuonna 1986 [1] ja se formalisoitiin vuonna 1989 [2] [3]

Paikallinen haku (naapureiden toimesta) etsii mahdollisen ratkaisun ongelmaan ja tarkistaa sen välittömät naapurit (eli ratkaisut, jotka ovat samankaltaisia ​​muutamaa hyvin pientä yksityiskohtaa lukuun ottamatta) paremman ratkaisun löytämisen toivossa. Paikalliset hakumenetelmät jäävät usein jumiin optimaalista heikoille alueille tai tasangoille, joissa monet ratkaisut ovat yhtä sopivia.

Estetty haku parantaa paikallishaun suorituskykyä lieventämällä sen perussääntöä. Ensinnäkin, heikkeneminen voidaan olettaa jokaisessa vaiheessa, jos parannusta ei tapahdu (samaan tapaan, kun haku juuttuu paikalliseen minimiin ). Lisäksi otetaan käyttöön kieltoja (alias tabuja ), joilla estetään jo käytyjen ratkaisujen etsiminen.

Estä haun toteutus käyttää rakenteita, jotka kuvaavat vierailupäätöksiä tai käyttäjän sääntöjoukkoja [2] . Jos mahdollisessa ratkaisussa on vieraillut jonkin lyhyen ajanjakson aikana tai se rikkoo sääntöä, se merkitään " tabuksi ", jotta algoritmi ei harkitse ratkaisua uudelleen.

Sana tabu tulee tongankielisestä sanasta, joka tarkoittaa asioita, joihin ei pidä koskea, koska ne ovat pyhiä [4] .

Tabuhaku on meta-algoritmi , jonka avulla voidaan ratkaista kombinatorisia optimointiongelmia (ongelmia, joissa sinun on löydettävä optimaalinen järjestys ja vaihtoehtojen valinta).

Nykyiset estetyt hakusovellukset ulottuvat sellaisille alueille kuin resurssisuunnittelu , televiestintä, VLSI-suunnittelu , talousanalyysi, aikataulutus, aluesuunnittelu, energian jakelu, molekyylitekniikka, logistiikka, mallien luokittelu , joustava valmistus, jätehuolto, mineraalien etsintä, biolääketieteellinen analyysi, ympäristönsuojelu ja monet muut. Viime vuosina useiden tieteenalojen lehdet ovat julkaisseet akateemisia artikkeleita ja laskennallisia tutkimuksia, jotka osoittavat tabuhaun onnistuneen laajentaa tehokkaasti ratkaistavien ongelmien rajoja ja tuottanut ratkaisuja, jotka ovat usein laadultaan paljon parempia kuin tähän asti menetelmillä saadut. . Laaja luettelo sovelluksista, mukaan lukien tiivistelmä käytännön soveltamisesta saaduista tuloksista, löytyy Gloverin ja Lagunan artikkelista [5] . Nykyaikaiset tabuhakukehitykset ja -sovellukset löytyvät Tabu Search Vinjetit -artikkelista .

Perusteet

Tabuhaku käyttää paikallishakua tai naapurihakumenettelyä siirtyäkseen iteratiivisesti yhdestä mahdollisesta ratkaisusta parempaan naapurustoon, kunnes jokin pysäytyskriteeri täyttyy (yleensä iteraatioiden määrä tai tavoitepistekynnys). Paikalliset hakurutiinit juuttuvat usein kohteisiin, joissa kohdeestimaatit ovat huonot tai joissa arvio muodostaa tasangon (tasainen vaakasuora pinta). Välttääkseen nämä sudenkuopat ja tutkiakseen hakuavaruuden alueita , jotka jäävät tutkimatta muilla hakumenettelyillä, tabuhaku tutkii huolellisesti kunkin hakuprosessin ratkaisun lähistön. Uusien naapureiden tunnistamat ratkaisut määritetään muistissa olevien rakenteiden avulla. Näitä rakenteita käyttämällä haku etenee iteratiivisesti siirtymällä nykyisestä ratkaisusta luettelosta parannettuun ratkaisuun .

Nämä rakenteet muodostavat ns. tabulistoja, joukon sääntöjä ja nimettyjä ratkaisuja, joiden avulla suodatetaan, mitkä naapuriratkaisut käsitellään haettaessa. Yksinkertaisimmassa muodossaan tabuluettelo on lyhytaikainen joukko päätöksiä, joissa on vieraillut viimeisimmissä iteraatioissa (vähemmän kuin iteraatiot, missä on yhtä suuri kuin muistettujen päätösten lukumäärä ja tätä lukua kutsutaan tabu elinkaareksi). Useimmiten tabulista koostuu päätöksistä, joita on muutettu siirryttäessä päätöksestä toiseen. Esityksen helpottamiseksi on kätevää ymmärtää joidenkin attribuuttien koodaama ja edustama "ratkaisu".

Muistityypit

Tabuhaussa käytetyt muistirakenteet voidaan jakaa karkeasti kolmeen kategoriaan [6] :

Lyhyen, keskipitkän ja pitkän aikavälin luettelot voivat olla päällekkäisiä. Näissä luokissa muistia voidaan edelleen erottaa kriteereillä, kuten tehtyjen muutosten tiheydellä ja vaikutuksilla. Yksi esimerkki keskipitkän aikavälin rakenteesta on tiettyjä ominaisuuksia sisältävien päätösten kieltäminen tai kannustaminen (esimerkiksi päätökset, jotka sisältävät joidenkin muuttujien ei-toivottuja tai toivottuja arvoja) tai muistirakenne, joka estää tai synnyttää joitain liikkeitä (esim. , joka perustuu aiemmin löydettyjen mahdollisten ja lupaamattomien ratkaisujen ominaisuuksien esiintymistiheyteen). Lyhytaikaisessa muistissa valitut attribuutit äskettäin vierailluissa ratkaisuissa on merkitty "tabu-aktiivisiksi". Tabuaktiivisia elementtejä sisältävien ratkaisujen käyttö on kielletty. Ratkaisun tabu-tilan muuttamiseen käytetään poistokriteeriä, jossa poissuljetut ratkaisut sisällytetään sallittujen luetteloon (ratkaisu on "riittävän hyvä" laadun tai eron mukaan). Yksinkertainen ja yleisesti käytetty poistokriteeri on sallia nykyistä parasta ratkaisua parempien ratkaisujen käyttö.

Pelkästään lyhytaikainen muisti saattaa riittää tuottamaan tavanomaisilla paikallisilla hakumenetelmillä löydettyä ratkaisua paremman ratkaisun, mutta monimutkaisempien ongelmien ratkaisemiseen tarvitaan usein keskipitkän ja pitkän aikavälin rakenteita [7] . Tabuhakua verrataan usein muihin meta-algoritmiin menetelmiin, kuten simuloituun hehkutusalgoritmiin , geneettisiin algoritmeihin , muurahaisyhdyskuntien algoritmeihin , reaktiiviseen hakuun, valvottuun paikallishakuun tai ahneeseen adaptiiviseen satunnaishakuun . Lisäksi tabuhaku yhdistetään joskus muihin meta-algoritmeihin hybridimenetelmien luomiseksi. Yleisin tabby-hakuhybridi syntyy yhdistämällä se hajontahakuun [  8 ] [ 9] , luokkaan proseduureja, joilla on yhteiset juuret tabuhaun kanssa ja joita käytetään usein laajamittaisten epälineaaristen optimointiongelmien ratkaisemiseen.

Pseudokoodi

Seuraava pseudokoodi edustaa yllä kuvatun tabuhakualgoritmin yksinkertaistettua versiota. Tällä toteutuksella on yksinkertaisin versio lyhytaikaisesta muistista, eikä se sisällä keskipitkän tai pitkän aikavälin rakenteita. Termi "kuntoisuus" viittaa tavoitefunktion laskemiseen ehdokasratkaisulle.

sParas ← s0 paras ehdokas ← s0 tabulista ← [] tabuList . työnnä ( s0 ) kun ( ei pysähdyKunto ()) sNeighborhood ← getNeighbors ( paras ehdokas ) for ( sCndidate in sNeighborhood ) if ( ( ei tabuList . sisältää ( sCandidate )) ja ( kunto ( sCandidate ) > kunto ( parasEhdokas )) ) parasEhdokas ← sEhdokas loppu loppu jos ( kunto ( paras ehdokas ) > kunto ( sBest )) sBest ← paras ehdokas loppu tabuList . push ( paras ehdokas ) jos ( tabuList . size > maxTabuSize ) tabuList . poistaFirst () loppu loppu palauta sBest

Riveillä 1-4 tehdään alkutehtäviä, luodaan alkuperäinen ratkaisu (ehkä saatu satunnaishakumenetelmillä), asetetaan tuloksena oleva ratkaisu ensimmäiseksi katsotuksi ja alustetaan tabuluettelo tällä ratkaisulla. Tässä esimerkissä tabuluettelo on vain lyhytaikainen rakenne, joka sisältää tietueen vierailluista kohteista.

Pääsilmukka alkaa riviltä 5. Tämä silmukka jatkaa parhaan ratkaisun etsimistä, kunnes se saavuttaa käyttäjän määrittämän pysäytyskriteerin (kaksi esimerkkiä tällaisesta kriteeristä ovat yksinkertaisesti aikaraja tai kuntopistekynnys). Naapuriratkaisut tarkistetaan tabujen varalta rivillä 8. Lisäksi algoritmi tallentaa naapureiden parhaat ei-kielletyt ratkaisut.

Kuntotavoitteen funktio on yleensä matemaattinen funktio, joka palauttaa tavoitepisteen tai -kriteerin - esimerkiksi uuden hakutilan löytämistä [4] voidaan pitää kohdekriteerinä . Jos parhaalla paikallisella ehdokkaalla on korkeampi kunto-arvo, niin nykyinen arvo on paras (rivi 12), se hyväksytään nyt parhaaksi (rivi 13). Paikallinen paras ehdokas lisätään aina tabuluetteloon (rivi 15) ja jos tabulista on täynnä (rivi 16), jonkin elementin tabu katsotaan vanhentuneen (rivi 17). Yleensä elementit poistetaan luettelosta siinä järjestyksessä, jossa ne lisättiin siihen. Menettelyssä valitaan paras paikallinen ehdokas (vaikka sen kunto-arvo on huonompi kuin sBest) hyppäämään pois paikallisesta optimista.

Tätä prosessia jatketaan, kunnes saavutetaan käyttäjän määrittelemä pysäytyskriteeri, jolloin palautetaan paras prosessissa löydetty ratkaisu (rivi 20).

Esimerkki: matkustavan myyjän ongelma

Matkamyyjä-ongelmaa käytetään joskus kuvaamaan tabuhaun toimintaa [7] . Tämä ongelma kysyy, kun otetaan huomioon kaupunkiluettelo, mikä on lyhin reitti vierailla kaikissa kaupungeissa? Jos esimerkiksi kaupunki A ja kaupunki B ovat lähellä toisiaan, mutta kaupunki C on kaukana toisistaan, reitin kokonaispituus on lyhyempi, jos käymme ensin A ja B:ssä ja sitten kaupunkiin C. optimaalisen ratkaisun löytäminen on NP-kovaa , heuristiset approksimaatiomenetelmät (kuten paikallishaku) ovat hyödyllisiä lähes optimaalisen ratkaisun saamiseksi. Hyvien ratkaisujen saamiseksi matkustavan myyjän ongelmaan on tärkeää tarkastella graafin rakennetta. Ongelmarakenteen tutkimisen arvo on toistuva teema meta-algoritmisissa menetelmissä, ja tabuhaku sopii tähän hyvin. Tabuhakuun liittyvä strategialuokka ja niin sanotut poistoketjumenetelmät  mahdollistavat korkealaatuisten ratkaisujen löytämisen matkustavan myyjän ongelmaan tehokkaasti [ 10] .

Toisaalta yksinkertaisella tabuhaulla voidaan löytää tyydyttävä ratkaisu matkustavan myyjän ongelmaan (eli sopivuuskriteerin täyttävän, vaikkakin huonolaatuisen ratkaisun, joka saadaan graafin rakenteen tarkastelun jälkeen) Haku alkaa alkuratkaisulla, joka voidaan saada satunnaisesti tai jonkin lähimmän naapurin algoritmin mukaan . Uusien ratkaisujen luomiseksi vaihdetaan mahdollisessa ratkaisussa järjestystä, jossa kaupungeissa käydään. Kaikkien kaupunkien välistä kokonaisreitin etäisyyttä käytetään vertaamaan, kuinka paljon parempi ratkaisu on kuin toinen. Silmukoitumisen eli tietyn ratkaisujoukon uudelleen saamisen ja paikalliseen optimiin juuttumisen estämiseksi kiellettyjen ratkaisujen listalle lisätään ratkaisu, jos se hyväksytään haettaessa naapureita, .

Uusia ratkaisuja luodaan, kunnes saavutetaan jokin pysäytyskriteeri, kuten iteraatioiden määrä. Heti kun yksinkertainen tabuhaku pysähtyy, se palauttaa parhaan suorituksen aikana löytämänsä ratkaisun.

Muistiinpanot

  1. ↑ Glover, 1986 , s. 533–549.
  2. ↑ 1 2 Glover, 1989 , s. 190-206.
  3. ↑ Glover, 1990 , s. 4–32.
  4. ↑ 1 2 Kurssia | Fuzzy-Neural Group | NC-tila ISE . Haettu 16. tammikuuta 2019. Arkistoitu alkuperäisestä 12. tammikuuta 2014.
  5. ↑ Glover, Laguna, 1997 .
  6. ↑ Glover/A Tutorial, 1990 .
  7. ↑ 1 2 Malek, Huruswamy, Owens, Pandya, 1989 .
  8. ↑ Glover, Laguna, Marti, 2000 , s. 653–684.
  9. ↑ Laguna, Marti, 2003 .
  10. ↑ Gamboa, Rego, Glover, 2005 , s. 154-171.

Kirjallisuus

  • Fred Glover. Tulevaisuuden polut kokonaislukuohjelmointiin ja linkit tekoälyyn // Tietokoneet ja operaatioiden tutkimus. - 1986. - T. 13 , no. 5 . - doi : 10.1016/0305-0548(86)90048-1 .
  • Fred Glover. Tabu Search – Osa 1 // ORSA Journal on Computing. - 1989. - Osa 1 , numero. 2 . - doi : 10.1287/ijoc.1.3.190 .
  • Fred Glover. Tabu Search – Osa 2 // ORSA Journal on Computing. - 1990. - Osa 2 , numero. 1 . - doi : 10.1287/ijoc.2.1.4 .
  • Gamboa D., Rego C., Glover F. Tietorakenteet ja poistoketjut suurten matkustavien myyntimiesongelmien ratkaisemiseen // European Journal of Operational Research. - 2005. - T. 160 , no. 1 . - doi : 10.1016/j.ejor.2004.04.023 .
  • Glover F., Laguna M. Tabu Search. — Kluwer Academic Publishers. – 1997.
  • Fred Glover. Tabu-haku: opetusohjelma // Liitännät. – 1990.
  • Malek M., Huruswamy M., Owens H., Pandya M. Sarja- ja rinnakkaishakutekniikat matkustavan myyjän ongelmaan. Annals of OR: Linkages with Artificial Intelligence. – 1989.
  • Glover F., Laguna M., Marti R. Scatter Search and Path Relinking perusteet. — Ohjaus ja kybernetiikka. - 2000. - T. 29. - S. 653-684.
  • Laguna M., Marti R. Scatter Search: Methodology and Implementations in C. - Kluwer Academic Publishers, Boston. – 2003.

Linkit