DNA-computing en evolutionary algorithms

Abstract

Toen in 1994 de paper Molecular computation of solutions to combinatorial problems van professor Adleman verscheen, opende dit een heel nieuw onderzoeksveld binnen de informatica: DNA computing. Hierbij zou met behulp van DNA en verscheidene laboratorium technieken combinatorische problemen opgelost kunnen worden. Er werd ook al snel duidelijk dat DNA verschillende specifieke voordelen biedt ten op zichte van de hedendaagse computers. In het afgelopen decennium heeft er veel onderzoek plaatsgevonden in dit domein en is men reeds tot enkele belangrijke vaststellingen gekomen. Ook de nadelen en beperkingen van werken op moleculair niveau zijn grondig besproken waarbij men kan concluderen dat DNA computing nog een lange weg te gaan heeft alvorens ze effectief kan toegepast worden. Het domein waarin DNA computing kan toegepast worden hoort bij het meest recente onderzoek. Dankzij een abstractie van DNA computing zou het dan mogelijk zijn een vergelijkende studie te maken met andere toepassingen. Een apart onderdeel van DNA computing is het opstellen van de structuur van het DNA zelf. De keuze van DNA als representatie voor allerlei data blijkt niet altijd evident en vooral probleem afhankelijk te zijn. Een algemene beschrijving voor het ontwerpen van DNA strengen wordt beschreven in het domein van de Code Word Design . Voor elk probleem zullen er een reeks beperkingen gelegd kunnen worden op de structuur van het DNA. Er bestaan verschillende beperkingen waaraan een verzameling DNA strengen moeten voldoen. Ook elke streng op zich moet structure free zijn. De zoektocht naar geschikte representaties is moeilijk. De verzameling mogelijke strengen DNA waaruit men kan kiezen is immens groot zodat een goed zoekalgoritme geen overbodige luxe is. Het genetisch algoritme biedt hiervoor een geschikte oplossing. Dit heuristisch algoritme, gebaseerd op de natuurlijke evolutie, kent haar sterkte vooral in het zoeken naar oplossingen in een reusachtige, al dan niet oneindige verzameling elementen. Het werd in de jaren 60 ontworpen door John Holland en wordt steeds meer en meer gebruikt in verschillende domeinen waarbij vooral artificiële intelligentie in het oog springt. De bedoeling van het algoritme bestaat erin vanuit een generatie mogelijke oplossingen te evolueren naar een superieure generatie dat een globaal optimum benadert voor het gegeven probleem. De elementen die instaan voor de volgende generatie worden gekozen op basis van een natuurlijke selectie methode. Vervolgens zullen gekende natuurlijke operaties gebruikt worden om de evolutie uit te voeren. Uiteindelijk zal elk element een score of fitness krijgen aan de hand van een welgekozen fitness functie. Via parameters wordt probabiliteit aan het algoritme toegevoegd om de evolutie theorie concreter te benaderen. De basis van dergelijk algoritme is eenvoudig maar de implementatie ervan is eerder complex en probleem afhankelijk. Een correcte implementatie zal veel afhangen van de gekozen methoden en parameters hoewel het vaak onmogelijk is op voorhand te bepalen welke methoden of parameters tot het optimale resultaat zullen leiden. 8 Voor dit proefschrift werd een dergelijk genetisch algoritme ontwikkeld dat het code word design voor het 3-bit majority probleem oplost. Gedurende de implementatie werd al gauw duidelijk dat het ontwerpen van een stabiel en correct genetisch algoritme niet vanzelfsprekend is. Het programma zal uiteindelijk een degelijke oplossing geven voor het code word design van het 3-bit majority probleem. Het resultaat, bestaande uit strengen DNA, dient als input voor een algoritme dat het 3-bit majority probleem oplost met DNA computing. Dit algoritme stelt een concrete oplossing voor vertrekkende vanuit een meer algemene oplossing dat het n-bit majority probleem oplost via DNA computing. Met het resultaat is het dan mogelijk het algoritme met DNA computing in de praktijk uit te voeren. Enkele jaren geleden heeft men aan het Limburgs Universitair Centrum getracht dit uit te voeren maar kende toen geen succes. Een mogelijke reden hiervoor zou te wijten zijn aan het toen ontwikkelde code word design .