Seuraava artikkeli auttaa sinua: Kuinka käyttää simuloitua hehkutusta funktion lähentämiseen?
Simuloitu hehkutus on tietämätön hakutekniikka funktion globaalien minimien optimoimiseksi. Siitä on tullut suosittu lähestymistapa kahden viime vuosikymmenen aikana sen helppokäyttöisyyden, lähentymisominaisuuksien ja mäkikiipeilyliikkeiden käytön ansiosta paikallisten optimien välttämiseksi. Sitä käytetään ensisijaisesti erillisten optimointiongelmien ja vähäisemmässä määrin jatkuvien optimointiongelmien ratkaisemiseen. Tässä artikkelissa keskustelemme simuloidusta hehkutuksesta pienellä toteutuksella ymmärtääksemme tämän tekniikan toimintaa. Tällä menetelmällä selvitetään tietyn funktion minimit. Seuraavassa on käsiteltävät aiheet.
Sisällysluettelo
- Tietoja paikallisesta optimoinnista
- Tietoja simuloidusta hehkutuksesta
- Simuloidun hehkutuksen toiminta
- Simuloidun hehkutuksen toteuttaminen toiminnon optimoimiseksi
Simuloitu hehkutus on meta-heuristinen paikallinen hakualgoritmi, joka pystyy pakenemaan paikallisista optimeista. Aloitetaan ymmärtämällä paikallista optimointia.
Tietoja paikallisesta optimoinnista
Kombinatorinen optimointiongelma määritellään määrittelemällä kokoelma ratkaisuja ja kustannusfunktio, joka määrittää kullekin vaihtoehdolle numeerisen arvon. Optimaalinen ratkaisu on sellainen, jonka kustannukset ovat mahdollisimman alhaiset (sellaisia ratkaisuja voi olla useampi kuin yksi). Paikallinen optimointi pyrkii parantamaan mielivaltaista ratkaisua tällaiseen ongelmaan joukolla vähitellen paikallisia parannuksia.
Aloita paikallisen optimointialgoritmin määrittely tarjoamalla keino häiritä ratkaisuja erilaisten ratkaisujen hankkimiseksi. “A”:n naapuri viittaa ratkaisujen joukkoon, joka voidaan saada yhdessä tällaisessa vaiheessa tietystä ratkaisusta “A”. Algoritmi suorittaa sitten perussilmukan jättäen tarkat tekniikat ratkaisun (S) ja testaamattoman naapurin (S’) valitsemiseksi toteutuksen yksityiskohtiin.
Vaikka S:n ei tarvitse olla paras ratkaisu silmukan valmistumisen jälkeen, se on paikallisesti optimaalinen siinä mielessä, että yhdelläkään sen naapureista ei ole halvempaa. Toivotaan, että paikallisesti optimi toimii. Alla on kuva, jossa on joukko vaiheita paikallisen optimoinnin laskemiseksi.
Etsitkö täydellistä arkistoa tietotieteessä käytettävistä Python-kirjastoista, katso tästä.
Tietoja simuloidusta hehkutuksesta
Simuloitu hehkutus on nimetty kiinteiden aineiden fysikaalisen hehkutusprosessin mukaan, jossa kiteistä kiinteää ainetta kuumennetaan ja jäähdytetään sitten varovasti, kunnes se saa säännöllisimmän mahdollisen kidehilan rakenteen ja siksi siinä ei ole kidevirheitä.
Lopullisella järjestelyllä saadaan aikaan kiinteämpi rakenne, jos jäähdytysaikataulu on sopivan hidas. Simuloitu hehkutus yhdistää tällaisen termodynaamisen käyttäytymisen globaalien minimien etsimiseen erillisessä optimointiongelmassa. Se esittelee myös algoritmisen menetelmän tällaisen suhteen hyödyntämiseksi.
Kahden ratkaisun (nykyinen ratkaisu ja juuri valittu ratkaisu) arvoja verrataan jokaisessa simuloidun hehkutusprosessin iteraatiossa, jota sovelletaan erilliseen optimointiongelmaan. Parannettavat ratkaisut hyväksytään aina, kun taas osa ei-parannuttavia (huonompia) ratkaisuja sallitaan tavoitteena paeta paikallista optimia ja saavuttaa globaali optimi.
Parantumattomien ratkaisujen hyväksymisen todennäköisyys määräytyy lämpötilaparametrin avulla, joka ei normaalisti nouse jokaisen algoritmin iteroinnin yhteydessä.
Simuloidun hehkutuksen olennainen algoritminen puoli on, että se mahdollistaa paikallisten optimien karkaamisen mäkikiipeilyportaiden kautta (eli liikkeitä, jotka huonontavat tavoitefunktion arvoa). Lämpötilaparametrin lähestyessä nollaa mäkikiipeilyliikkeet muuttuvat vähemmän yleisiksi, ja algoritmin käyttäytymistä mallintavaan epähomogeeniseen Markov-ketjuun liittyvä ratkaisujakauma konvergoi muotoon, jossa kaikki todennäköisyys on keskittynyt globaalisti optimaalisten ratkaisujen joukkoon (edellyttäen, että Algoritmi on konvergentti; muuten algoritmi konvergoi paikalliseen optimiin, joka voi olla tai ei ole globaalisti optimaalinen).
Simuloidun hehkutuksen toiminta
Useita määritelmiä tarvitaan luonnehtimaan simuloidun hehkutusmenetelmän erityispiirteitä diskreeteille optimointiongelmille.
Harkitse kaikkien mahdollisten ratkaisujen kokoelmaa, joka tunnetaan usein ratkaisutilana. Luo sitten ratkaisuavaruuteen tavoitefunktio. Tarkoituksena on määrittää ratkaisujoukossa oleva globaali minimi. Jotta voidaan varmistaa, että globaali minimi on olemassa, tavoitefunktiota on rajoitettava. Määritä naapuruusfunktio ratkaisujen kokoelmaa varten. Tämän seurauksena naapuriratkaisut liitetään kuhunkin ratkaisuun, ja ne voidaan saada paikallisen hakualgoritmin yhdellä iteraatiolla.
Simuloitu hehkutus alkaa ratkaisulla, joka valitaan liuoskokoelmasta. Sen jälkeen luodaan naapuriratkaisu, joko satunnaisesti tai ennalta määritellyn säännön mukaan. Metropolis-hyväksymiskriteeriä käytetään kuvaamaan, kuinka termodynaaminen järjestelmä etenee nykyisestä ratkaisusta tai tilasta kandidaattiratkaisuun, jonka energiasisältö on pienin.
Hyväksymistodennäköisyyden perusteella ehdokasratkaisu valitaan nykyiseksi ratkaisuksi. Tämä hyväksymistodennäköisyys on simuloidun hehkutuksen hakuprosessin perustavanlaatuinen rakennuspalikka. Jos lämpötilaa lasketaan asteittain, järjestelmä voi lähestyä tasapainoa (stationaarista tilaa) jokaisella toistolla.
Tavoitefunktiot määritellään ja ratkaisuihin liittyvä energia on merkitty. Tasapaino määräytyy Boltzmannin jakauman perusteella. Se voidaan määritellä todennäköisyydeksi, että järjestelmä on tilassa, jossa on energiafunktio (tavoitefunktio) tietyssä lämpötilassa, jossa todennäköisyys on verrannollinen kaikkien ajateltavissa olevien funktioiden kokonaismäärään.
Jos todennäköisyys luoda ehdokasratkaisu ratkaisun naapureista on yksi, voidaan luoda ei-negatiivinen neliöstokastinen matriisi siirtymätodennäköisyyksineen. Nämä siirtymän todennäköisyydet määrittelevät joukon ratkaisuja, jotka on tuotettu epähomogeenisen Markov-ketjun avulla.
Simuloidun hehkutuksen toteuttaminen toiminnon optimoimiseksi
Toteutetaan simuloitu hehkutus laskemalla sokeahaku funktion minimien optimoimiseksi ja edistymisen tarkkailemiseksi.
Tuo tarvittavat kirjastot
tuonti numpy muodossa np tuonti matplotlib.pyplot nimellä plt
Määritetään tavoitefunktio, jolle optimointi on suoritettava. Käytämme yksinkertaista yksiulotteista tavoitefunktiota rajoilla [-10,10] optimin ollessa 0,0.
def tavoite(x): palauttaa x[0]**2,0 r_min, r_max = -10,0, 10,0 tuloa = np.arange(r_min, r_max, 0,1) tulokset = [objective([x]) x:lle inputs]plt.plot(syötteet, tulokset) x_optima = 0,0 plt.axvline(x=x_optima, ls=”–“, color=”red”) plt.show()
Analytics India -lehtiSen jälkeen meillä voi olla selkeämpi käsitys siitä, kuinka suurkaupunkien hyväksymiskriteeri muuttuu lämpötilan mukaan ajan kuluessa. Kriteerit ovat lämpötilariippuvaisia, mutta se riippuu myös siitä, kuinka uuden pisteen objektiivinen arviointi eroaa nykyisestä työratkaisusta. Tämän seurauksena piirrämme kriteerin muutamille selkeälle “tavoitefunktion arvon eroille” osoittaaksemme, kuinka ne vaikuttavat hyväksymistodennäköisyyteen.
iteraatiot = 120 aloituslämpötila = 12 iteraatiota = [i for i in range(iterations)]
lämpötilat = [initial_temp/float(i + 1) for i in iterations]
erot = [0.01, 0.1, 0.5, 1.0]
d:lle erot: metropoli = [np.exp(-d/t) for t in temperatures]
label=”diff=%.2f” % d plt.plot(iteraatiot, metropoli, label=label) plt.xlabel(‘Iteraatio’) plt.ylabel(‘Metropolis Criterion’) plt.legend() plt.show()
Analytics India -lehtiJuoni on jaettu neljään riviin kuvaamaan neljää eroa uuden huonomman vaihtoehdon ja nykyisen toimivan ratkaisun välillä. Kuten voidaan ennustaa, mitä suurempi ero on, sitä epätodennäköisemmin malli hyväksyy huonomman vaihtoehdon algoritmin toistosta riippumatta. Voimme myös nähdä, että mahdollisuus hyväksyä huonompia vastauksia pienenee algoritmien iteraatiolla kaikissa olosuhteissa.
Rakennetaan simuloitu hehkutusfunktio
def simulated_annealing(tavoite, rajat, n_iteraatiot, askelkoko, temp): paras = rajat[:, 0] + np.random.rand(len(bounds)) * (rajoja[:, 1] – rajoja[:, 0]) paras_eval = tavoite(paras) curr, curr_eval = paras, paras_eval pisteet = lista() i:lle alueella(n_iteraatioita): ehdokas = curr + np.random.randn(len(bounds)) * askel_koko ehdokas_eval = tavoite(ehdokas) if ehdokas_eval < paras_eval: paras, paras_eval = ehdokas, ehdokas_eval pisteet.append(paras_eval) print('>%df(%s) = %.5f’ % (i, paras, paras_eval)) ero = ehdokas_arvo – curr_eval t = temp / float(i + 1) metropoli = np.exp(-diff / t) jos ero < 0 tai np.random.rand() < metropoli: curr, curr_eval = ehdokas, ehdokas_eval return [best, best_eval, scores]
Nyt kun tiedämme, kuinka lämpötila ja metropolin hyväksymiskriteerit käyttäytyvät ajan myötä, voimme käyttää simuloitua hehkutusta testiongelmaamme.
np.random.seed(10) bounds = np.asarray([[-10.0, 10.0][%(parastulos))
Analytics India -lehtiAloita kylvämällä pseudosatunnaislukugeneraattori. Tämä ei ole yleisesti ottaen oleellista, mutta tässä tapauksessa on välttämätöntä varmistaa, että joka kerta menetelmää suoritettaessa tuotetaan sama satunnaislukusarja, jotta tulokset voidaan piirtää jälkikäteen.
Algoritmi etsii tässä esimerkissä 1 000 iteraatiota askelkoolla 0,1. Lähtölämpötila on 12,0. Koska hakutekniikka on herkempi hehkutusaikataululle kuin alkulämpötila, alkulämpötila-asetukset ovat lähes mielivaltaisia.
Piirrä edistymisraportti
plt.figure(figsize=(10,5)) plt.plot(pisteet, ‘.-‘) plt.xlabel(‘Parannusnumero’) plt.ylabel(‘Arviointi f(x)’) plt.show()
Analytics India -lehtiMäkikiipeilyhaun aikana muodostetaan viivakaavio, joka näyttää kunkin parannuksen tavoitefunktion arvioinnin. Haun aikana näemme tavoitefunktion arvioinnissa noin 78 muutosta, joista alkuun on tehty olennaisia muutoksia ja hyvin vaatimattomia tai huomaamattomia muutoksia lähellä päätelmää, kun algoritmi asettui optimiin.
Lopullinen tuomio
Simuloituja hehkutuksen optimointimenetelmiä voidaan käyttää sekä yhden tavoitteen että usean tavoitteen optimointiongelmien ratkaisemiseen. Sitä on käytetty niinkin erilaisilla tieteenaloilla kuin prosessijärjestelmäsuunnittelu, toimintatutkimus ja älykkäät materiaalit. Tämän käytännön toteutusartikkelin avulla olemme ymmärtäneet simuloidun hehkutuksen toiminnan funktion approksimoinnin optimoimiseksi.
