Kuinka evoluutioalgoritmit voivat optimoida lajittelun?

Seuraava artikkeli auttaa sinua: Kuinka evoluutioalgoritmit voivat optimoida lajittelun?

Järjestämätön elementtijoukko lajitellaan asettamalla ne monotonisesti nousevaan (tai laskevaan) järjestykseen. Suurten datajoukkojen lajittelun tehokkuus sekä ajan että käytetyn muistin osalta vaatii edistystä lajittelualgoritmeissa ja niiden toteutuksissa nykyaikaisessa laskennassa. Koneoppimismalleja voidaan käyttää parantamaan näitä lajittelualgoritmeja. Analysoimalla kokeellista dataa koneoppiminen mahdollistaa mukautuvien algoritmien luomisen. Tässä artikkelissa tarkastellaan evoluutioalgoritmeja, jotta voit valita algoritmin tietojoukon ominaisuuksien mukaan. Seuraavassa on käsiteltävät aiheet.

Sisällysluettelo

1. Lajittelu koneoppimisessa
2. Lajittelun optimointiin käytetyt geneettiset algoritmit
3. Geneettisen algoritmin käytön edut

Lajittelu on saanut paljon huomiota tietokoneiden alusta lähtien perustavanlaatuisena datatoimintona. Ymmärretään lajittelualgoritmit.

Lajittelu koneoppimisessa

Lajittelutoiminto sisältää tietojen sijoittamisen tiettyyn järjestykseen. Lajittelualgoritmi määrittelee tekniikan tietojen järjestämiseksi tiettyyn järjestykseen. Tiedonhaku voi olla erittäin tehokasta, kun tiedot pidetään lajiteltuna, minkä vuoksi lajittelu on tärkeää. Tietojen esittäminen ymmärrettävämmillä tavoilla on toinen lajittelun käyttötarkoitus.

Tietojen lajittelun algoritmit saattavat tarvita hieman enemmän tilaa vertailuun ja muutaman tietokomponentin lyhytaikaiseen tallentamiseen. Näiden algoritmien väitetään lajittelevan paikan päällä esimerkiksi itse taulukon sisällä, eivätkä ne vie enempää tilaa. Sitä kutsutaan paikan päällä tapahtuvaksi lajitteluksi. Esimerkki paikan päällä tapahtuvasta lajittelusta on kuplalajittelu. Mutta joissakin lajittelualgoritmeissa ohjelman käyttämä tilan määrä on suurempi tai yhtä suuri kuin lajitettavien elementtien lukumäärä. Ei-in-place -lajittelu määritellään lajitteluksi, jolla on sama tai suurempi tilantarve. Esimerkki ei-in-place -lajittelusta on yhdistä-lajittelu.

Tietojen lajittelun jälkeisten vaikutusten perusteella nämä lajittelualgoritmit luokitellaan stabiileihin ja epävakaisiin. Esimerkiksi kun halutaan säilyttää elementtien järjestys monikossa, algoritmin stabiiliudella on merkitystä.

Analytics India -lehti

Jos lajittelualgoritmi käyttää lajiteltavien luettelossa aiemmin “lajiteltuja” kohteita, sen sanotaan olevan mukautuva. Toisin sanoen lajittelun aikana adaptiiviset algoritmit pyrkivät välttämään elementtien uudelleenjärjestämistä, jos lähdeluettelossa on jo osa niistä lajiteltuina. Algoritmin, joka jättää huomioimatta aiemmin lajitellut kohteet, sanotaan olevan ei-adaptiivinen. Varmistaakseen, että elementit lajitellaan oikein, ne yrittävät työntää jokaisen elementin uuteen järjestykseen.

Miksi optimointia tarvitaan?

Vaikka kääntäjäteknologia on automatisoinut ohjelmien optimoinnin suuresti, korkealaatuisen koodin tuottaminen vaatii edelleen paljon ihmisen osallistumista. Tälle väitteelle on kaksi perustetta:

• Kääntäjien epäjohdonmukaiset toteutukset.
• Perinteiset kääntäjät eivät sisällä semanttista tietoa, mikä rajoittaa niiden kykyä muuttaa tietoja.

Etsitkö täydellistä arkistoa tietotieteessä käytettävistä Python-kirjastoista, katso tästä.

Lajittelun optimointiin käytetyt geneettiset algoritmit

Optimaalinen algoritmi löytyy vain etsimällä, koska lajittelualgoritmien suorituskyvystä ei ole olemassa analyyttisiä malleja koneen arkkitehtonisten parametrien suhteen. Lisäksi aiemmat lajittelun monimutkaisuutta koskevat tutkimukset perustuivat virheelliseen olettamukseen, että jokaisen kappaleen saaminen vie yhtä paljon aikaa nykytekniikalla.

Geneettisessä algoritmissa lajittelu- ja valintaprimitiivien parametriarvot sekä niiden koostumus määräävät hakuavaruuden. Haun tavoitteena on löytää koneen arkkitehtonisiin ominaisuuksiin ja syöttöjoukon ominaisuuksiin parhaiten sopiva hierarkkinen lajittelu.

Analogia populaation kromosomien geneettisen rakenteen ja käyttäytymisen välillä toimii perustana geneettisille algoritmeille. Tähän vertailuun perustuvien GA:iden perusta on seuraava.

• Väestön jäsenet kilpailevat resursseista ja pariutumisesta.
• Peräkkäiset (kuntoisimmat) yksilöt parittelevat sitten saadakseen enemmän lapsia kuin muut yksilöt.
• Vanhemmilla on toisinaan lapsia, jotka ovat parempia kuin kumpikaan vanhempi; tämä johtuu siitä, että “parimpien” vanhempien geenit leviävät sukupolven yli.
• Tämän seurauksena jokaisesta seuraavasta sukupolvesta tulee ympäristöystävällisempää.

Lajittelu- ja valintaprimitiivejä käytetään skeeman puupohjaisina solmuina. Uusien lasten luomiseen ja populaation muuttamiseen hyödynnetään geneettisiä toimijoita. Kaksi operaatiota, joita suurin osa geneettisistä algoritmeista käyttää, ovat crossover ja mutaatio.

Crossover

Crossoverin aikana käydään kauppaa eri puiden alipuilla. Crossoverin tavoitteena on tuottaa uusia jälkeläisiä, jotka menestyvät vanhempiaan paremmin. Kun uudet lapset perivät hienoimmat alipuut vanhemmiltaan, tämä tapahtuu todennäköisesti. Useimmissa tapauksissa käytetään yhden pisteen jakoa, jolloin jakopiste valitaan satunnaisesti.

Mutaatio

Tämä operaattori tekee säädöt vain yhteen puuhun. Se antaa populaation varianssin. Populaatio ei voi pysyä samana minkään sukupolven jälkeen mutaation vuoksi. Tämä strategia mahdollistaa haun osittaisen paeta paikallista optimia. Parempien arvojen tunnistamiseksi mutaatio muuttaa parametriarvoja. Seuraavat muutokset ovat mahdollisia mutaatiooperaattorilla:

• Muuta parametrien arvoja satunnaisesti lajittelussa ja perussolmujen valinnassa.
• Vaihda kaksi alipuuta.
• Sisältää uuden alipuun.
• Ota alipuu ulos. Tällä tekniikalla voidaan poistaa tarpeettomat alipuut.

Kuntotoiminto

Yksilön lisääntymisen todennäköisyys määräytyy kuntotoiminnon mukaan. Todennäköisyys, että organismi lisääntyy ja kehittyy, kasvaa kunnon myötä. Kuntotoiminto on suoritus. Mutta kuntotoimintoa suunniteltaessa on otettu huomioon seuraavat kaksi tekijää:

• Tavoitteena on lajittelualgoritmi, joka toimii hyvin kaikkien mahdollisten syötteiden kanssa. Siksi puun peruskunto on sen keskimääräinen suorituskyky. Vaihtuvan suorituskyvyn omaaville puille asetetaan sakko lisäämällä peruskuntoisuutta luvulla, joka perustuu niiden suorituskyvyn keskihajontaan testisyötteitä lajitettaessa; Lajittelualgoritmin on kuitenkin toimittava hyvin johdonmukaisesti eri syötteissä, on myös tavoite.

• Väestön kuntovaihtelu on merkittävä alkusukupolvien aikana. Toisin sanoen jotkut lajittelupuut pärjäävät paljon paremmin kuin toiset. Koska näillä harvoilla puilla olisi huomattavasti suurempi todennäköisyys lisääntyä, suurin osa lapsista olisi heidän jälkeläisiään, jos kuntotoimintomme olisi suoraan verrannollinen puun suorituskykyyn. Nämä jälkeläiset muodostaisivat lopulta suurimman osan väestöstä. Tästä saattaa ilmetä ennenaikainen konvergenssi, mikä rajoittaisi algoritmia tutkimasta hakuavaruuden osia erittäin sopivien puiden läheisyyden ulkopuolella. Tämän ongelman ratkaisemiseksi kuntotoimintomme hyödyntää väestön lajittelupuiden suoritusjärjestystä tai sijoitusta. Puiden välinen absoluuttinen suorituskykyero jätetään huomioimatta suoritusarvojärjestystä sovellettaessa, joten heikomman suorituskyvyn puilla on suurempi todennäköisyys lisääntyä kuin puilla, joiden suorituskyky on korkeampi. Tämä eliminoi ongelman varhaisesta konvergenssista ja lähentymisestä paikalliseen optimiin.

Geneettisten algoritmien käytön edut ja haitat

Geneettisten algoritmien käytöllä on joitain etuja muihin optimointimenetelmiin verrattuna.

• Lajittelualgoritmit voidaan ilmaista puuna primitiivien avulla, jolloin jokainen primitiivi edustaa solmua. Tämän seurauksena geneettisiä algoritmeja voidaan yksinkertaisesti käyttää mahdollisten puiden universumin tutkimiseen parhaan puurakenteen ja kuhunkin solmuun liittyvien parametriarvojen löytämiseksi.

• Geneettiset algoritmit ylläpitävät hienoimpia alipuita ja lisäävät niiden lisääntymismahdollisuuksia. Koska alipuu on myös lajittelualgoritmi, lajittelualgoritmit voivat hyödyntää tätä.

Geneettinen algoritmi on lupaava ongelmanratkaisutyökalu, mutta siinä on muutamia puutteita, jotka voivat johtaa tehottomuuteen.

• Asetusten hienosäätö on vaikeaa. Se edellyttää useiden parametrien, kuten populaation koon, mutaationopeuden ja maksimiajon keston määrittämistä, sekä algoritmien luomista valintaa, rekombinaatiota ja mutaatiota varten. Näille toteuttamiskelpoisten vaihtoehtojen löytäminen on vaikea tehtävä, jolla on vähän tai ei ollenkaan teoreettista tukea.

• Ei ole takeita siitä, että lähentyminen tapahtuu. Ei ole takeita siitä, että algoritmi löytää globaalin optimin. On mahdollista, että se jää kiinni johonkin paikallisista optimeista.

Johtopäätös

Sopivan evoluutioalgoritmin valinta on kriittinen päätös. Evoluutioalgoritmi päättää kuinka monta lasta syntyy, kuinka monta nykyisen sukupolven jäsentä korvataan ja niin edelleen. Tämän artikkelin avulla olemme ymmärtäneet lajittelun optimointivaatimuksen ja GA:n käytön lajittelualgoritmien optimoinnissa.

Viitteet