Erottaminen ja arviointi
Algoritmin haara ja sidonta , tai haara ja sidonta englanniksi, on yleinen menetelmä kombinatorisen optimoinnin ongelmien ratkaisemiseksi .
Kombinatorinen optimointi koostuu pisteen löytämisestä, joka minimoi toiminnon, jota kutsutaan kustannukseksi, laskettavassa joukossa . Naiivi tapa ratkaista tämä ongelma on luetella kaikki ongelman ratkaisut, laskea kunkin kustannukset ja antaa sitten vähimmäismäärä. Joskus on mahdollista välttää sellaisten ratkaisujen luetteloiminen, jotka tiedämme analysoimalla ongelman ominaisuuksia, olevan huonoja ratkaisuja, toisin sanoen ratkaisuja, jotka eivät voi olla vähäisimpiä. Erottaminen ja arviointi menetelmä on yleinen menetelmä tämän.
Tätä menetelmää käytetään laajalti NP-täydellisten ongelmien ratkaisemiseen , toisin sanoen ongelmiin, joita on vaikea ratkaista tehokkaasti.
Haara ja sidottu on joskus verrattu toiseen ratkaisun havainto tekniikassa A * algoritmi , usein käytetty tekoälyä , kun taas haara ja sitoi on enemmän tarkoitettu toiminnan tutkimuksen ongelmia .
Konteksti: optimointiongelma
Olkoon S äärellinen joukko, mutta "suuren" kardinaalisuuden, jota kutsumme toteutettavien ratkaisujen joukoksi (tai avaruudeksi). Meillä on funktio f, joka palauttaa S: n mahdollisen ratkaisun x kohdalla kustannuksen f ( x ). Ongelman tavoitteena on löytää toteutettavissa oleva ratkaisu x vähäisin kustannuksin. Puhtaasti eksistentiaalisesta näkökulmasta ongelma on triviaali: sellainen ratkaisu on olemassa, koska joukko S on rajallinen. Toisaalta tehokas lähestymistapa ongelmaan on kaksi ongelmaa. Ensimmäinen on se, että elementtien S luetteloimiseksi ei välttämättä ole yksinkertaista algoritmia . Toinen on se, että toteutettavissa olevien ratkaisujen määrä on hyvin suuri, mikä tarkoittaa, että kaikkien ratkaisujen laskenta-aika on kohtuuton ( aikakompleksisuus on yleensä eksponentiaalinen).
Erotus- ja arviointimenetelmissä erottaminen tarjoaa yleisen menetelmän kaikkien ratkaisujen luetteloimiseksi, kun taas arvioinnissa vältetään kaikkien ratkaisujen systemaattinen luettelointi.
Menetelmän esittely
Erottaminen
Faasien erottumista toteutetaan irrottamalla ongelma useisiin osa-ongelmia, joilla kullakin on joukko mahdollisia ratkaisuja siten, että nämä yhdessä muodostavat päällysteen (ihanteellisesti yksi arkki ) joukon S . Siten ratkaisemalla kaikki alaongelmat ja ottamalla paras löydetty ratkaisu on varmasti ratkaistu alkuperäinen ongelma. Tätä erotusperiaatetta voidaan soveltaa rekursiivisesti kaikkiin saatuihin ratkaisujen osajoukkoihin, ja niin kauan kuin on joukkoa, jotka sisältävät useita ratkaisuja. Näin rakennettujen ratkaisujen sarjoilla (ja niihin liittyvillä osahäiriöillä) on luonnollinen puuhierarkia, jota usein kutsutaan tutkimuspuuksi tai päätöspuuksi .
Arviointi
Hakupuun solmun arvioinnin tarkoituksena on määrittää optimaalinen kyseiseen solmuun liittyvien toteutettavissa olevien ratkaisujen joukko tai päinvastoin todistaa matemaattisesti, että tämä joukko ei sisällä mielenkiintoista ratkaisua. ongelma (tyypillisesti, että optimaalista ratkaisua ei ole). Kun tällainen solmu tunnistetaan hakupuusta, on sen vuoksi tarpeetonta suorittaa sen ratkaisutilan erottaminen.
Tietyssä solmussa alaongelman optimaali voidaan määrittää, kun osaongelma muuttuu "riittävän yksinkertaiseksi". Esimerkiksi kun toteutettavissa olevien ratkaisujen joukosta tulee yksikkö, ongelma on todellakin yksinkertainen: optimaali on joukon ainutlaatuinen osa. Muissa tapauksissa sattuu, että erottelupelien avulla päästään alaongelmaan, jossa "vaikeat" päätökset on tehty ja joka voidaan siten ratkaista polynomissa.
Sen määrittämiseksi, että joukko toteutettavissa olevia ratkaisuja ei sisällä optimaalista ratkaisua, yleisin menetelmä koostuu joukon sisältämien ratkaisujen kustannusten alarajan määrittämisestä (jos se on minimointiongelma). Jos onnistumme löytämään alarajan, joka on suurempi kuin tähän mennessä löydetyn parhaan ratkaisun hinta, voimme vakuuttaa, että osajoukko ei sisällä optimaalia. Tavallisimmat tekniikat alarajan laskemiseksi perustuvat ajatukseen rentouttavista rajoituksista : jatkuva rentoutuminen , Lagrangin rentoutuminen jne.
Valintatekniikat
Tutkimuksen laatu riippuu suurelta osin heuristin valinnasta, jonka oletetaan olevan paremmat mahdollisuudet saada paras tulos ensimmäisissä. Tällä tavoin lisätään todennäköisyyttä löytää hyviä toteutettavissa olevia ratkaisuja tutkimuksen alkaessa.
Ohjelma muistaa myös tavoitetoiminnon kasvun tai vähenemisen ajan myötä, jotta voidaan ehdottaa pidempiä etsintäaikoja, jos tutkimusajanjakson loppupuolella saavutetaan suuria voittoja.
Voimme myös muistaa parhaat löydetyt ratkaisut, vaikka se ei ole pakollista. Sekvenssin uudelleenjärjestelyistä johtaa parempiin tuloksiin voi puolestaan johtaa uusiin heuristiikka.
On myös mahdollista saada aikaan ohjelman kanssa näppäimistön näppäintä testi , vuorovaikutuksen avulla näppäimistön tai ajoitus varmistaa, että se pysäyttää jonkin ajan yhteensopiva budjetin sekä tulostamisesta. Paras tulos löytyi tuolloin (tulokset ovat tulostetaan tai näytetään usein, kun tiedät, milloin lopettaa).
Arviointitekniikat
Hyvä arviointitoiminto on välttämätön, jotta menetelmä olisi tehokas. Arviointitoiminnon tarkoituksena on antaa arvio, joka on mahdollisimman lähellä tarkkaa arvoa, toisin sanoen alaongelman pienintä kustannusta. Laadun ja laskenta-ajan välillä on kuitenkin tehtävä kompromissi .
Kaksi klassista tekniikkaa ovat rentoutumisten käyttö ja kustannustoiminnon muokkaaminen.
Parannuksia
- Heuristiikan epätäydellisyyden voittamiseksi ohjelmassa on usein metaheuristiikkaa, jonka avulla voidaan väliaikaisesti luopua etsinnästä, kun se ei tuota haluttua suorituskykyä.
- Kun puiden indeksointi tapahtuu vastakkaista pelaajaa vastaan, käytetään toista samanmielistä pikakuvaketta, joka on alfa-beeta-karsinta (jota kutsutaan joskus PQ-leikkaukseksi ).
Sovelluskentät
Tätä tekniikkaa käytetään hyvin yleisesti operaatiotutkimuksessa NP-täydellisten ongelmien ratkaisemiseksi . Ne ovat erityisesti kokonaisluvun lineaarisen optimoinnin ja rajoitusten ohjelmoinnin ratkaisijoiden ytimessä .
Huomautuksia ja viitteitä
- Djamal Rebaïne, " Luentoseloste : Haara ja sidottu menetelmä " , Université du Québec à Chicoutimi .
- (en) Jens Clausen, ” Haara- ja sidotut algoritmit - periaatteet ja esimerkit. " ,1999.
Katso myös
Ulkoinen linkki
- Djamal Rebaïne, " Luentomoniste : Haara ja sidottu menetelmä " , Université du Québec à Chicoutimi