wie een beetje de ontwikkelingen in de genetica en celbiologie volgt, kan alleen maar perplex staan hoe geniaal de natuur in elkaar zit. dat is ook computerwetenschappers niet ontgaan. zij laten zich al vanaf het begin inspireren door biologische processen. dat levert niet alleen hinderlijke virussen op, maar ook dynamische, flexibele computersystemen die zichzelf kunnen corrigeren en verbeteren. over artificieel leven, cellulaire automaten en genetisch programmeren.
Biologie inspireert computerwetenschap
Zowel computersystemen als de taken die ze uitvoeren worden steeds complexer. Er is dan ook een groeiende bezorgdheid over de gevolgen van het falen van een hardware- of softwarecomponent (defect in de elektronica, een fout in het programma, een computervirus enzovoort). Hoewel hedendaagse computersystemen een zekere mate van fouttolerantie en redundantie bezitten, is de architectuur van hardware en software weinig flexibel, zodat een kleine storing of een kleine wijziging van de omgeving vaak een dramatisch effect heeft op de werking van het systeem.
Biologische systemen daarentegen kunnen zich aanpassen, komen tot zelfdiagnose en kunnen zichzelf herstellen. Hun opbouw en eigenschappen zijn dan ook een inspiratiebron om robuuste computersystemen en algoritmen te bouwen die aanpasbaar en fouttolerant zijn en over redundantie en zelfherstellend vermogen beschikken. Concepten uit de biologie en de natuur worden gebruikt bij de ontwikkeling van algoritmen die in staat zijn te leren (artificiële neurale netwerken), die gebaseerd zijn op aanpassing en evolutie (evolutionaire en genetische algoritmen) of die steunen op zelforganisatie (cellulaire automaten). Computervirussen en cyberaanvallen van buitenaf kunnen bestreden worden met technieken die gebaseerd zijn op concepten uit de immunologie. Ten slotte kunnen de interessante eigenschappen van biologische systemen uitgebuit worden door informatieverwerkende systemen en computers te bouwen met biochemische bouwstenen. De eerste stappen in deze richting zijn reeds gezet (DNA-computing, bio-elektronica). Nancy Forbes geeft in haar boek Imitation of Life een vrij volledig overzicht van deze ontwikkelingen. In dit artikel bespreken we enkele daarvan.
Computervirussen en cyberaanvallen kunnen bestreden worden met technieken die gebaseerd zijn op concepten uit de immunologie
Een algoritme is een formele beschrijving van een oplossingsstrategie. Klassiek wordt een algoritme opgesteld door de manier, waarop we het probleem ‘met de hand’ zouden oplossen, te formaliseren. Typisch daarbij is dat er heel wat probleemspecifieke kennis wordt gebruikt. Men kan zich echter ook laten leiden door de manier waarop de natuur problemen oplost. Dit heeft geleid tot een klasse nieuwe krachtige algoritmen, zoals artificiële neurale netwerken en evolutionaire algoritmen. Het succes van beide types algoritmen is onder meer te danken aan het feit dat er weinig probleemspecifieke kennis wordt gebruikt, waardoor ze breed inzetbaar zijn.
Artificiële neurale netwerken bootsen na hoe onze hersenen informatie verwerken. We weten dat dit gebeurt door een netwerk van onderling verbonden neuronen die met elkaar communiceren via elektrische signalen. Walter Pitts en Warren McCullough ontwikkelden in 1943 de volgende geïdealiseerde beschrijving van de werking van neuronen. Op een neuron komen verscheidene verbindingen toe. Bij het contactpunt (synaps) wordt het elektrische signaal omgezet in een biochemisch signaal, waarvan de sterkte bepaald wordt door de sterkte van de synaptische contacten. De interne potentiaal in het neuron wordt bepaald door de combinatie van de toekomende biochemische signalen, die gezien kan worden als een gewogen som van de inkomende elektrische signalen. Indien deze interne potentiaal een drempelwaarde overschrijdt, ontstaat een elektrisch signaal op de verbinding die vanuit het neuron vertrekt.
In 1949 stelde Donald Hebbs dat de sterkte van de synaptische contacten dynamisch verandert. Indien twee cellen regelmatig gelijktijdig actief zijn, wordt de synaptische verbinding tussen deze twee neuronen sterker, wat de informatie-uitwisseling tussen deze twee neuronen beter en efficiënter maakt. Indien daarentegen de twee cellen zelden samen actief zijn, worden de synaptische verbindingen zwakker. Dit zelfversterkende effect kan als een vorm van leren gezien worden.
Artificiële neurale netwerken zijn algoritmen die dit leerproces nabootsen. Hierbij wordt de werking van een eenvoudig netwerk van neuronen gesimuleerd. Invoerkanalen brengen de invoergegevens naar een aantal neuronen. Elk neuron berekent de gewogen som van zijn invoer en dit resultaat wordt door een invoer-uitvoerfunctie getransformeerd tot het uitvoersignaal van het neuron. Een neuraal netwerk bestaat uit een aantal lagen van neuronen (invoer- en uitvoerlaag, met daartussen één of meer verborgen lagen). De uitvoer van een laag kan worden teruggekoppeld naar een voorgaande laag. De werking van het neurale netwerk wordt dus bepaald door de structuur van het netwerk, de gebruikte invoer-uitvoerfunctie(s), en de gewichten van de inkomende verbindingen. Vooraleer het algoritme gebruikt kan worden, is er een leerfase waarin het algoritme getraind wordt aan de hand van een reeks trainingsgegevens met gekende invoer en uitvoer. In deze fase passen de gewichten van de neuronen zich aan totdat het neurale netwerk alle trainingsgegevens correct verwerkt. Daarna kan het netwerk worden gebruikt om nieuwe invoer te verwerken. Indien de trainingsgegevens voldoende representatief zijn voor de gegevens die later aangeboden worden, zal het netwerk goed werken. Artificiële neurale netwerken bewijzen hun nut vooral voor taken zoals patroonherkenning en classificatie, bijvoorbeeld het herkennen van handgeschreven letters.
Waar artificiële neurale netwerken gebaseerd zijn op biologische principes op het microniveau, zijn evolutionaire algoritmen geïnspireerd door biologische concepten op macroniveau. Evolutionaire algoritmen steunen op Darwins theorie van natuurlijke selectie en ‘survival of the fittest’. Ingo Rechenberg, Hans-Paul Schwefel en David Fogel legden de basis voor deze algoritmen omstreeks 1960. Een evolutionair algoritme werkt met een verzameling (populatie) van kandidaat-oplossingen. Voor iedere kandidaat (individu) wordt de kwaliteit bepaald door evaluatie van een fitheidsfunctie, die aangeeft in hoeverre deze kandidaat een goede oplossing is. Uit een individu kan een nieuw individu worden gecreëerd door een mutatie, dat wil zeggen. Een nieuwe kandidaat-oplossing wordt gecreëerd die lichtjes afwijkt van het oorspronkelijke individu. Nadat mutatie op (een deel van) de populatie is toegepast, wordt de ‘fitheid’ van alle (oorspronkelijke en nieuwe) individuen geëvalueerd en worden de minst goede individuen verwijderd, zodat de populatiegrootte constant blijft. Door het samenspel van mutatie en selectie worden opeenvolgende generaties van kandidaat-oplossingen gecreëerd die steeds beter worden.
Evolutionaire algoritmen steunen op Darwins theorie van natuurlijke selectie en ‘survival of the fittest’
Evolutionaire algoritmen zijn bijvoorbeeld erg krachtig voor complexe zoekproblemen (zoek in een zeer grote ‘zoekruimte’ een element dat aan bepaalde eigenschappen voldoet) of optimalisatieproblemen (zoek een element waarvoor een doelfunctie een maximum bereikt). Klassieke algoritmen voor deze problemen worden zeer rekenintensief of onbetrouwbaar als de zoekruimte zeer groot is of indien bepaalde eigenschappen niet voldaan zijn (bijvoorbeeld indien de doelfunctie grillig verloopt).
Enkele jaren later voegde John Holland een belangrijk ingrediënt toe aan deze nabootsing van de natuur, namelijk de recombinatie van genetisch materiaal bij voortplanting, cfr. de theorie van Mendel. Dit leidde tot genetische algoritmen, waarbij de kandidaat-oplossingen worden voorgesteld op een manier die kan worden geïnterpreteerd als een genetische code. Uit paren van kandidaat-oplossingen (‘ouders’) worden ‘kinderen’ gecreëerd, door de genetische codes van de ouders te recombineren. Vermits de genetische code de eigenschappen van de kandidaat-oplossing beschrijft, worden op deze manier ook de eigenschappen van de kandidaat-oplossingen gecombineerd. Door de individuen van een populatie te transformeren met selectie, kruising, mutatie en andere genetische operatoren (?), ontstaat een nieuwe generatie van kandidaat-oplossingen, die hopelijk beter is (dat wil zeggen een hogere fitheid heeft). Een genetisch algoritme steunt op een subtiel samenspel van de verschillende operatoren. Hierbij zorgt selectie voor het elimineren van zwakke kandidaat-oplossingen, mutatie voor het exploreren van de zoekruimte en kruising voor de exploitatie van bepaalde eigenschappen van kandidaat-oplossingen. Hoewel het instellen van de parameters van een genetisch algoritme vrij heuristisch is, werd ook een theoretisch kader ontwikkeld dat aangeeft wanneer en waarom genetische algoritmen goed werken. Een belangrijk voordeel van genetische algoritmen is dat ze voor een brede klasse van problemen gebruikt kunnen worden, zonder te steunen op veel probleemspecifieke kennis.
De kracht van deze aanpak werd onlangs aangetoond door John Koza, die het ‘genetisch programmeren’ ontwikkelde als een variante van genetische algoritmen. Hij gebruikte deze techniek bij het ontwerp van elektronische circuits. Elk kandidaat-circuit bestaat uit een aantal met elkaar verbonden elektronische componenten (weerstanden, capaciteiten …). De kwaliteit van het circuit werd bepaald door met een numeriek simulatieprogramma na te gaan hoe goed het circuit een bepaalde taak (bijvoorbeeld filteren van hoge frequenties) uitvoert. Op deze manier konden heel wat door ingenieurs ontwikkelde en gepatenteerde circuits opnieuw automatisch worden ontworpen. Voor sommige taken waren de door genetisch programmeren bekomen circuits zelfs beter dan de bestaande circuits en werden daarvoor een aantal patentaanvragen ingediend.
Von Neumann legde in 1948 de basis voor cellulaire automaten. De automaat bestaat uit een rooster van cellen, waarbij iedere cel zich in een beperkt aantal toestanden kan bevinden. Deze toestand wijzigt in iedere tijdstap volgens een stel regels dat rekening houdt met de huidige toestand van de cel en zijn onmiddellijke buren. Von Neumann wou hiermee inzicht verkrijgen in (een beperkt deel van) de werking van natuurlijke organismen, namelijk de logische regels voor overgang naar een andere toestand, zelfregulatie, zelfreproductie en het ontstaan van globale patronen onder invloed van lokale regels. Een bekend voorbeeld van een cellulaire automaat is John Conways Game of Life. Cellen liggen hierin regelmatig geordend en kunnen zich in de toestand ‘levend’ of ‘dood’ bevinden. Leven ontstaat in cellen die grenzen aan een beperkt aantal levende cellen, maar wanneer een cel volledig omgeven is door leven stikt ze en sterft. Gebaseerd op deze eenvoudige lokale regels ontstaan hierbij complexe patronen, waarvan sommige uitsterven en anderen blijven groeien. Het dynamische gedrag en de complexiteit van de globale patronen die ontstaan kunnen deels worden verklaard door de theorie van niet-lineaire dynamische systemen en de chaostheorie. Cellulaire automaten kunnen worden beschouwd als de eerste poging om iets dat lijkt op ‘leven’ (in de betekenis van evolutie en zelforganisatie) te simuleren in een computer.
Cellulaire automaten kunnen beschouwd worden als de eerste poging om iets dat lijkt op ‘leven’ te simuleren in een computer
Het onderzoek naar artificiële neurale netwerken, evolutionaire algoritmen en cellulaire automaten heeft geleid tot een nieuw onderzoeksdomein ‘artificieel leven’, waarin men onderzoekt of de combinatie van biologie en computerwetenschappen kan leiden tot digitale levensvormen in het interne ‘ecosysteem’ van de computer. Het doel is het exploreren van het fenomeen ‘leven’ door artificieel biologische fenomenen te creëren, die niet gebonden zijn aan de aardse vorm van leven, die gebaseerd is op koolstofchemie. Natuurlijk komen hierbij slechts enkele eigenschappen van leven aan bod, maar het voordeel is dat er snelle en grootschalige simulaties mogelijk zijn, die niet of bijna niet uit te voeren zijn met niet-virtuele experimenten. Deze aanpak kan toepassingen hebben in bijvoorbeeld robotica. Zoals bij cellulaire automaten gebruikt artificieel leven een bottom up aanpak, waarbij lokaal gedrag (en bijhorende regels) tot globaal emergent gedrag kan leiden.
Computervirussen, inbraken in computersystemen en dergelijke zijn een echte plaag geworden door de vele ‘contacten’ tussen computers (netwerken, e-mail, uitwisselen van bestanden …). Om computers te beschermen tegen infecties en indringers, worden nu technieken ontwikkeld die geïnspireerd zijn op het biologische immuunsysteem. Een immuunsysteem maakt onderscheid tussen ‘eigen’ en ‘niet-eigen’ bestanddelen, werkt gedistribueerd zonder centrale controle, evolueert en past zich aan de omgeving aan, bestaat uit meerdere beschermingslagen, is fouttolerant en heeft een geheugen. Een ‘digitaal immuunsysteem’ maakt bijvoorbeeld onderscheid tussen ‘eigen’ en ‘niet-eigen’ bestanddelen (programma’s in dit geval) door informatie over de normale interactie tussen een gebruikersprogramma en het besturingssysteem op te slaan in een databank. Als een programma een afwijkend gedrag vertoont (bijvoorbeeld meer bestanden leest dan normaal) kan het besmet zijn met een computervirus. Men maakt ook gebruik van een digitaal equivalent van detectie van indringers via receptoren op T-cellen. Een aantal van deze technieken worden al ingebouwd in commerciële beveiligingssoftware.
Tot nu toe hebben we beschreven hoe biologische concepten gebruikt worden bij het ontwerp van algoritmen, die verder geïmplementeerd worden in klassieke software en uitgevoerd worden op klassieke computers. Moleculaire biologie kan echter ook gebruikt worden om tot volstrekt nieuwe manieren van informatieverwerking te komen.
Het DNA codeert informatie in de vorm van een bepaalde sequentie van moleculen, en deze code kan worden geïnterpreteerd als een beschrijving van bepaalde bewerkingen. Een voorbeeld is de productie van een specifieke proteïne, waarbij tijdens de evolutie van eiwitsequenties DNA-segmenten bewerkingen ondergaan (splitsen, kopiëren enzovoort). Deze bewerkingen vertonen een analogie met rekenkundige en logische bewerkingen in computerprogramma’s. Het is dus mogelijk om stukjes DNA samen te stellen die een bepaald eenvoudig algoritme kunnen uitvoeren. Hiervoor moet iedere algoritmische stap vertaald worden naar de taal van het DNA.
Een op DNA gebaseerde berekening gebeurt in reageerbuisjes in het laboratorium, met een grote verzameling DNA-ketens. Hierop worden laboratoriumtechnieken van de moleculaire biologie (recombinante DNA-technieken) uitgevoerd, bijvoorbeeld fusie van enkelvoudige DNA-ketens in dubbelstrengige DNA-ketens waarbij complementaire baseparen gebonden zijn, het vinden van ketens met een bepaalde (korte) sequentie van baseparen enzovoort. Het onderzoek naar DNA-computing begon in 1993 onder inspiratie van Leonard Adleman, die later een belangrijke test voor het concept uitvoerde door DNA-computing te gebruiken voor het oplossen van (een variante van) het handelsreizigersprobleem. Dit is een klassiek probleem in de computerwetenschappen, dat het probleem beschrijft van een handelsreiziger die een reeks steden moet bezoeken. Uitgaande van een verzameling mogelijke wegen tussen de verschillende steden moet een pad worden gevonden waarbij alle steden precies éénmaal bezocht worden. De oplossing van Adleman illustreert mooi het concept van DNA-computing. Elke stad kreeg als codenaam een bepaalde nucleotide-sequentie van lengte 6, bijvoorbeeld AGCTAT. De verbinding tussen twee steden kreeg als code de sequentie bestaande uit de eerste drie letters van het beginpunt en de laatste drie letters van het eindpunt. Steden en verbindingen werden ook gecodeerd met de complementaire sequenties. Enkelvoudige DNA-ketens die de oorspronkelijke codes bevatten werden gemengd met DNA-ketens die de complementaire codes bevatten. Er zal dan een binding ontstaan tussen een keten die een verbinding voorstelt met een bepaalde stad als eindpunt en een keten die deze stad als beginpunt bevat, maar complementair gecodeerd zijn. Herhaalde bindingen zorgen ervoor dat op het einde van het experiment enkel de goede oplossingen in het reageerbuisje overblijven. Men onderzoekt verder nog of DNA-computing nuttig kan zijn in cryptografie.
Waar DNA-computing een radicaal andere manier van informatieverwerking betekent, kunnen biomaterialen ook worden gebruikt in computersystemen met een klassieke organisatie en structuur. De huidige computersystemen bestaan uit silicon-halfgeleiders waarin elektrische componenten worden ingebouwd. Stilaan worden hiervan echter de technologische limieten bereikt. Bio-elektrische componenten, zoals de proteïne bacteriorhodopsin, kunnen nog veel kleiner zijn (nanometerschaal, dat is ± honderd maal kleiner dan de huidige componenten), en kunnen honderd tot duizend maal sneller schakelen. Hoewel biomaterialen lang als te onstabiel en fragiel werden beschouwd om in elektronica gebruikt te worden, zijn er recent interessante resultaten geboekt. Zo zijn er twee soorten geheugens ontwikkeld die gebruik maken van bacteriorhodopsin en zijn de eerste resultaten geboekt in de ontwikkeling van eenvoudige bouwstenen, zoals schakelaars en oscillatoren, in levende cellen (bijvoorbeeld E. Colli). Dit is een eerste stap om op moleculaire schaal geïntegreerde circuits te bouwen. Ook wordt gewerkt rond het ontwerpen van chips (of elektronische circuits) gebaseerd op principes uit de biologie: evolvable hardware (hardware die zichzelf aanpast aan de omstandigheden), embryonic hardware (systemen met zelfherstellend en zelfreplicerend vermogen) en immunotronics (met detectie en herstellen van fouten, zelfs indien deze fouten niet gekend zijn). Voor de eerste twee concepten zijn ook de eerste prototypes al ontwikkeld.
Steeds meer concepten en modellen uit de biologie en biochemie worden met succes gebruikt in de computerwetenschappen en de informatica. Ze zorgen er vooral voor dat computersystemen en algoritmen meer flexibel, dynamisch aanpasbaar en breed inzetbaar worden.
Nancy Forbes, Imitation of Life. How biology is inspiring computing (Cambridge MA: MIT Press 2004).
Dirk Roose is als computerwetenschapper verbonden aan de KU Leuven.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License