Bevaring av informasjon og ko-evolusjon: Ny BIO-kompleksitet artikkel av Ewert og Marks
Brian Miller; 7. september 2017
Oversatt herfra.

Bilde 1. Bien og blomsten

I en tidligere artikkel beskrev jeg Winston Ewert, Robert Marks og William Dembskis bok Introduction to Evolutionary Informatics -innvendinger her; som identifiserer begrensningene av evolusjonære algoritmer for å finne løsninger på komplekse problemer. Boken demonstrerer at denne klassen av programmer bare er i stand til å oppnå ikke-trivielle resultater med mindre informasjon om ønskede resultater er programmert inn i dem. For eksempel må et program utviklet for å finne den beste strategien for å spille sjakk ha detaljert informasjon om spillet programmert i søkemetoden. Det kunne ikke utvikle en strategi for å spille sjakk uten å endre den underliggende algoritmen for å inkludere ny sjakkrelatert informasjon.

Denne begrensningen er et direkte resultat av No Free Lunch (NFL) teoremer og tilhørende lov om bevaring av informasjon -her. Forsøk har vært gjort for å overvinne denne utfordringen ved å appellere til det som kalles koevolusjonære søk. Men som Ewert og Marks demonstrerer i en ny artikkel for tidsskriftet BIO-Complexity, unngår ikke disse algoritmene NFL-barrieren, så de er ikke mer effektive i gjennomsnitt enn tilfeldige søk.

Evolusjonære algoritmer følger vanligvis et standard sett av trinn. De genererer prøveløsninger til et problem, og deretter tilordner hver prøve en "fitness" -verdi. Disse verdiene brukes da til å bestemme hvordan neste iterasjon av forsøk genereres for testing. Prosessen fortsetter til et mål er funnet.

Bilde 2. Bok om praktiske genetiske algoritmer

Ewert og Marks bruker illustrasjonen av å generere oppskrifter for å lage pannekaker. I dette eksemplet representerer en prøveoppskrift en liste over de spesifikke mengdene av hver ingrediens og detaljer om matlagingen, som for eksempel brennerinnstilling og -tider. Den tildelte verdien tilsvarer den forberedte pannekakeens smak, og den bestemmer hvordan nye oppskrifter genereres. Prosessen fortsetter til en pannekake er opprettet som oppfyller noen smakstandarder. Settet av verdier knyttet til alle mulige forsøk beskrives som et treningslandskap, og søkealgoritmen må navigere i terrenget etter mål. For standardalgoritmer er all informasjon som er nødvendig for å tildele en treningsverdi, kjent. I motsetning til at for koevolusjonære algoritmer er informasjon ikke fullt kjent, så må ufullstendig eller "underliggende" informasjon ofte brukes. Det er fordi treningslandskapet kontinuerlig endres på grunn av tilstedeværelse av andre organismer eller andre betingede faktorer.

Denne forskjellen kan illustreres i form av eksempler fra biologisk evolusjon. En standard evolusjonær algoritme vil korrespondere med en organisme som har en spesifikk "egnethet" som forblir ganske konstant i de fleste situasjoner. For eksempel kan en ørkenplante forholde seg til slike medfødte evner som å bevare vann og behandle sollys. Et dataprogram kan modellere plantens tilstand ved hjelp av relaterte variabler, for eksempel plantens masse og mengden klorofyll som produseres i bladene. Disse variablene vil fullt ut bestemme den tilordnede egnethets(fitness) -verdien. I motsetning til dette vil en koevolusjonar prosess tilsvare at treningen endres over tid på grunn av faktorer som vekselvirkning med andre arter og detaljer i det fysiske miljøet. For eksempel kan kjemikalier i huden gi større eller mindre beskyttelse mot forskjellige rovdyr, og formen på planten kan vise seg å være mer eller mindre nyttig i ulike settinger.

For å modellere denne økte kompleksiteten genererer algoritmene en spørre-matrise hvor en rad er tilordnet hver kandidatløsning, og hver kolonne tilsvarer en annen faktor som påvirker egnethet, for eksempel samspill med en bestemt art. Mange celler i denne matrisen er ofte ikke kjent, enten på grunn av beregningsmessige eller andre praktiske begrensninger, så forskjellige metoder brukes for å tilordne hver prøveløsning (rad) en samlet verdi basert på begrenset kunnskap. Algoritmen fortsetter deretter som med tradisjonelle modeller. Mange har hevdet at ko-evolusjonære programmer kan finne løsninger på et bredt utvalg av problemer raskere i gjennomsnitt enn tilfeldige søk, og dermed overvinne restriksjonene i NFL-teoriene. Med andre ord eliminerer de behovet for programmerere å gi problem-spesifikk "aktiv informasjon" for å styre søk.

For å teste denne påstanden, måler Ewert og Marks ytelsen til forskjellige koevolusjonære algoritmer for en rekke problemer. De fant ut at de i beste fall kunne matche utførelsen av tradisjonelle "full-søk" -metoder, og de utførte vanligvis dårligere. Artikkelen deres beskriver også hvordan krav om det motsatte var basert på forskning som fokuserte på å løse svært enkle problemer eller som utformet eksperimenter på en måte som gir skjult informasjon for å hjelpe til med å finne mål. Derfor kan koevolusjonære prosesser ikke overvinne NFL-begrensninger, da de også krever problemsspesifikke informasjon for å kunne virke riktig.

Bilde 3. Ulike diett-oppskrifter for ulike bi-typer

Disse resultatene har direkte implikasjoner for Darwinistisk evolusjon. Biologer hevder ofte at koevolusjonært samspill mellom ulike arter eller arter og miljøet kan endre det underliggende fitness-landskap på en slik måte at de driver evolusjonære endringer. Et klassisk eksempel er den foreslåtte samutviklingen av bier og blomsterplanter -her.

Mange planter trenger insekter som bærere for pollen. Som et resultat plasserer tilstedeværelsen av insekter selektivt press på plantene for å produsere lukter, farger og nektar for å tiltrekke seg dem. I sin tur plasserer tilstedeværelsen av plantene selektive trykk på insektene for å bevege seg mot plantens signaler for å skaffe matforsyningen. I tillegg er insekter selektert for tykkere hår på beina for å fange mer pollen. De kan så gjødsle flere planter, noe som resulterer i større matforsyning. Slike scenarier kan høres troverdige, men de resulterer bare i trivielle tilpasninger til pre-eksisterende strukturer.

Bilde 4. Nødvendig i naturen -bien

I motsetning til dette krever komplekse innovasjoner, for eksempel nye kroppsplaner, radikale nyvinninger som igjen krever store mengder ny informasjon -her. Miljøet er ofte hevdet å gi denne nye informasjonen, som antas å være skjult i fitness-landskapene kombinert med koevolusjonerende interaksjoner. Imidlertid utfordrer denne undersøkelsen av Ewert og Marks direkte kravet. Søkerommet som svarer til biologiske former, er langt større enn det som kan søkes gjennom tilfeldige mutasjoner i avkom av noen art. Og naturlig utvalg kan ikke hjelpe uten å bli gitt store mengder informasjon om hvor nye former finnes. For koevolusjonære prosesser er ikke mer effektive for å løse problemer enn tradisjonelle evolusjonære algoritmer, og sistnevnte er ikke mer effektive i gjennomsnitt enn tilfeldige søk.

Tager: Bio-kompleksitet; Darwinistisk evolusjon; R. Marks; W.Dembski; W. Ewert;