Onaturligt urval

För att bli en professionell antenndesigner kan du följa en av två vägar: du kan anmäla dig till högskole- och forskarnivåkurser om elektromagnetism, fördjupa dig i den empiriska studien av antennformer och lära dig hos en etablerad tekniker som är villig att förmedla disciplinens noga bevarade hemligheter.

Eller så kan du göra som Jason Lohn gjorde: låt evolutionen göra jobbet.

Den här historien var en del av vårt februarinummer 2005

• Se resten av frågan
• Prenumerera

Fysiker vet mycket om Maxwells ekvationer och andra principer som styr trådlös kommunikation. Men antenndesign är fortfarande ganska mycket en mörk konst, säger Lohn, en datavetare som arbetar vid NASA Ames Research Center utanför Mountain View, CA. Fältet är så ekorreligt. Allt du lär dig är genom försök och misstag, skolan för hårda slag.

Så varför inte automatisera trial and error? Antenndesign, tror Lohn, är ett av många tekniska problem som bäst skulle kunna lösas med evolutionära algoritmer, en framväxande klass av mjukvara som producerar massor av olika konstruktioner, som avvisar de mindre passande för att välja den mest funktionella. De resulterande designerna verkar ofta lite omänskliga – oeleganta och kusliga.

Evolutionära algoritmer, även kända som genetiska algoritmer eller GA, tar sin utgångspunkt från biologisk evolution, som kan förvandla en krypande reptil till en svävande fågel utan någon form av framåtblickande ritning. Vid sexuell reproduktion skapar blandningen av varje förälders gener – i kombination med slumpmässig genetisk mutation – organismer med nya egenskaper, och de mindre vältränade organismerna tenderar att inte föra sina gener vidare till efterföljande generationer. Evolutionära algoritmer fungerar ungefär på samma sätt, men inuti en dator. När Lohn skapar en ny antenn, till exempel, börjar han med en population av slumpmässigt genererade mönster och graderar deras relativa prestanda. Design som kommer nära förinställda mål vinner rätten att blanda sina egenskaper med andra framgångsrika kandidaters egenskaper. Design som gör dig besviken går vägen för arkeopteryxen: glömskan.

Att odla antenner tar såklart tid. De flesta konstruktioner är rent av hemska, och det krävs ett stort antal beräkningscykler för att hitta anständiga prestanda. Ändå, när du har en dator som kan generera och testa 1 000 generationer i timmen, dyker intressanta idéer upp*. Lohn, en doktorsexamen som inte har gått en kurs i elektromagnetism sedan sin grundutbildning, förväntar sig att åtminstone en av hans teams antenndesigner ska gå ut i rymden i år som en del av NASA:s Space Technology 5-uppdrag, som kommer att testa en trio av miniatyrer. satelliter. Hans favorit datordesignade antenn: en korkskruv som är liten nog att passa i ett vinglas, men ändå kan skicka en bredstrålad radiovåg från rymden till jorden. Det liknar ingenting som någon vettig radioingenjör skulle bygga på egen hand.

Evolutionära algoritmer är ett utmärkt verktyg för att utforska de mörka hörnen av designutrymmet, säger Lohn. Du visar [dina designs] för personer med 25 års erfarenhet i branschen och de säger: 'Wow, fungerar det verkligen?' Det lite läskiga svaret är att ja, det gör de verkligen, som Lohn konstaterade efter månader av tester. Om vi ​​har tur kan vi ha så många som sex antenndesigner som går ut i rymden 2005, säger Lohn.

Inte alla problem kommer att ge efter för det evolutionära synsättet. Men de som kommer att dela ett gemensamt särdrag: de sitter alla bortom vad matematikern John von Neumann kallade komplexitetsbarriären, skiljelinjen mellan problem som kan lösas med traditionella, reduktionistiska metoder och de som kräver en mer intuitiv, kasta upp. -och-se-vad-pinnar tillvägagångssätt. Tills nyligen var det ett dyrt förslag att korsa denna barriär. Men dagens datorer är tillräckligt snabba för att sålla bland miljontals offbeat-designer i hopp om att hitta en som fungerar. Kombinera det med moderna designers växande skicklighet i att tillämpa evolutionära algoritmer, säger David Goldberg, chef för Illinois Genetic Algorithms Laboratory vid University of Illinois i Urbana-Champaign, och du får vad ingenjörer kärleksfullt kallar skalbarhet: förmågan att hantera både miniatyr och stora designutmaningar.

Precis som ångmaskinen skapade mekanisk hävstång för att utföra större uppgifter, börjar genetiska algoritmer ge individer en slags intellektuell hävstång som kommer att omforma arbetet, säger Goldberg. Genom att automatisera en del av tankens tunga lyft frigör vi oss för att arbeta på en högre, mer kreativ nivå. Sådan frihet har naturligtvis ett pris. Det kräver att ingenjörer inser omöjligheten att titta in i varje mörkt hörn och lita på ännu ett lager av mekanisk assistans. Men fler och fler av dem tar det språnget.

Från leksaker till verktyg
Att på mikrosekunder på en dator återge en process som tar miljontals år i naturen är en idé som länge går före förmågan att förverkliga den. John H. Holland, en 76-årig professor i datavetenskap vid University of Michigan, säger att han först kom på idén när han bläddrade igenom Michigans matematikbiblioteks öppna stackar i början av 1950-talet.

Då och då plockade jag upp en bok som såg intressant ut och läste den, säger han. Den vanan ledde honom till The Genetical Theory of Natural Selection, en bok från 1930 av den brittiske matematikern som blev biolog Ronald Fisher. Inspirerad av ärtväxtexperimenten från den österrikiska munken Gregor Mendel från 1800-talet, arbetade Fisher fram matematiska beskrivningar av naturligt urval på individuella geners nivå. Även om forskare inte skulle knäcka biokemin bakom den processen förrän på 1950-talet, stämde Fishers arbete ändå med vad bönder och herdar hade vetat i århundraden: sexuell reproduktion säkerställer variation och nyhet.

Det är verkligen där de genetiska algoritmerna kom ifrån, säger Holland. Jag började undra om man kunde föda upp program på det sätt som folk skulle, säg, föda upp bra hästar och föda upp bra majs.

Holland skrev sin första uppsats om adaptiva algoritmer 1962. Men det var inte förrän i slutet av 1970-talet som han och hans doktorander hade samlat på sig beräkningsresurserna för att omsätta idén. Holland tillskriver en av hans studenter, Edward Codd, att ha övertygat sin tidigare arbetsgivare, IBM, att sälja en lågprisstordator till forskargruppen i Michigan. (Codd skulle fortsätta att vinna AM Turing Award, datavetenskapens motsvarighet till Nobelpriset, för att ha designat de första relationsdatabaserna.) Redan då begränsade dock datorns ynka 32 kilobyte minne storleken och omfattningen av forskarnas initiala experiment.

En av de första forskarna som gav evolutionära algoritmer en seriös provkörning var Goldberg, som arbetade under Holland som doktorand i början av 1980-talet. Goldberg återupplivade ett problem som han hade ställts inför under sina dagar i naturgasindustrin: minimera strömförbrukningen för en långdistansledning, givet variationer i regional efterfrågan. Hans evolutionära algoritmer gav lösningar lika effektiva som de som produceras av den befintliga mjukvaran för vätskemekanik som används av pipelinedesigners. Men när Goldberg matade sina algoritmer med större och mer komplicerade problem, började de snubbla: de fastnade för att utforska evolutionära återvändsgränder eller spotta ut hopplöst vilda lösningar. Jag förstod problemen jag löste bättre än verktygen jag använde för att lösa dem, och det störde mig, säger Goldberg.

Goldberg fokuserade sin avhandling och sedan ytterligare ett halvt decenniums arbete på att göra genetiska algoritmer mer förutsägbara. Han fann att justering av parametrarna för varje ny algoritm – till exempel storleken på startpopulationen eller mutationshastigheten – jämnade ut några rynkor. Men för det mesta lämnade hans forskning honom med en nykter insikt: evolutionära algoritmer var ofta mer komplexa än de problem de försökte lösa. Så småningom lärde sig Goldberg att undvika vad han kallar problem med nål i höstacken, som kräver en enda, bästa lösning; dessa tenderade att få evolutionära algoritmer att snurra utom kontroll. Istället siktade han på vänligare problem som hade en rad genomförbara lösningar, beroende på hur du närmade dig dem. Om det finns dussintals nålar utspridda på ett sådant sätt att den [evolutionära algoritmen] kan bryta ned höstacken i mindre höstackar, garanterar du åtminstone dig själv en chans till ett bättre resultat, säger Goldberg.

Goldberg dokumenterade sitt arbete i en lärobok från 1989, en volym som skulle inspirera andra datorkunniga ingenjörer att börja sitt eget mixtrande. I mitten av 1990-talet hade ingenjörer vid General Electric Research Center i Niskayuna, NY, byggt in evolutionära metoder i ett internt designverktyg kallat EnGENEous, som användes för att hitta den mest effektiva formen för fläktbladen i de använda GE90 jetmotorerna på Boeings 777-flygplan. EnGENEous tillät GE90-teamet att eliminera ett steg i motorns kompressor, vilket innebar en minskning av motorvikt och tillverkningskostnader utan att göra några uppoffringar av aerodynamisk prestanda. Efter denna initiala framgång öppnades slussarna för att använda dessa typer av verktyg i många olika applikationer inom alla GE:s verksamheter, säger Pete Finnigan, laboratoriechef för avancerade mekaniska designapplikationer vid forskningscentret. Ingenjörer på Rolls Royce, Honda och Pratt och Whitney har följt efter och införlivat genetiska algoritmer i sina egna designprocesser.

Flagga bedrägeri
Men medan datorer har blivit tillräckligt kraftfulla för att tillämpa evolutionära principer på alla möjliga problem, har höstackarna förökat sig i en ännu mer dramatisk takt. Tänk på konsumentbedrägerier. Kreditkortsföretag uppskattar att 0,07 USD per 100 USD som debiteras kreditkort går förlorade på grund av bedrägerier, vilket kostar industrin mer än 1 miljard USD per år bara i USA. Ändå är det fortfarande fenomenalt svårt att skriva traditionell programvara för att identifiera bedrägliga avgifter. Varför? Eftersom personerna som begår bedrägeriet är experter på att ändra sitt beteende för att undvika upptäckt. Det är helt enkelt inte möjligt att skriva ett program som förutser alla möjliga bedrägerier.

Men evolutionära algoritmer kan åtminstone göra datoriserad bedrägeriupptäckt mer sannolikt att lyckas, hävdar de artificiella intelligensforskarna som grundade New York City-baserade Searchspace. Företaget säljer en mängd olika program som delar upp höstacken genom att leta efter avvikande aktivitet inom exakt definierade delar av befintliga kontodata, säger Michael Recce, Searchspaces chefsforskare. Programvaran använder verktyg som kallas sentinels, programmerade med regler för upptäckt av bedrägeri. Flera debiteringar på samma betalkort i en enda butik på en och samma dag kan till exempel automatiskt höja en röd flagga.

Men personen som samlar ihop dessa köp kan helt enkelt vara en glömsk julshoppare, inte en tjuv. Så vaktposterna väger in en mängd olika faktorer, såsom en persons tidigare aktivitet i den butiken, för att undvika falska positiva resultat och endast flagga konton som mänskliga experter håller med om är misstänkta. Säger Recce, Du kan ställa in fitnesskriterierna på ett sätt som ger både minimal bedrägeriförlust och minimal förlust av goda kunder.

Searchspace är rutinmässigt värd för piloter, huvudsakligen programvarubake-offs som ställer sina algoritmer mot potentiella kunders befintliga system för upptäckt av bedrägerier. Deltagarna tar in blindprover av historisk data för att se om Searchspaces vaktposter planterar röda flaggor på alla rätt ställen. Utan undantag, säger Recce, dyker vaktposterna upp inte bara de förflaggade kontona utan också några fler skurkar som lurar i bakgrundsljudet. Jag tror inte att det har varit en av de där presentationerna där vi inte har behövt pausa saker ett ögonblick så att en chef kunde gå ut och ringa ett snabbt telefonsamtal, säger Recce och ler.

Patently original
Nu när evolutionära algoritmer överlista människor, vill vissa forskare höja ribban ännu högre. Vid Stanford University, till exempel, utforskar professorn i biomedicinsk informatik John Koza – ännu en holländsk skyddsling – ett närbesläktat område som kallas genetisk programmering. Evolutionära algoritmer har fasta uppsättningar instruktioner och varierar bara den data de manipulerar. Genetiska program är mer som sexuella organismer, som kan förbättras med tiden genom att blanda kodbitar sinsemellan. De upptäckter som hittills gjorts av Kozas program sträcker sig från nya datoriserade metoder för att sortera proteiner till banbrytande design för elektroniska kretsar.

Kretsdesignerna kom från Kozas arbete med Matthew Streeter från Carnegie Mellon University och Martin Keane från Econometrics, ett konsultföretag för marknadsföringsstrategi baserad i Chicago. Tillsammans byggde forskarna ett program som ritar schematiska kretsscheman. Deras första utmaning var att se om det genetiska tillvägagångssättet kunde härröra från scratch-kretsdesigner som redan patenterats av tidigare ingenjörer. Programmet hade små problem med att skapa enkla mönster som matchade de som patenterades på 1930- och 1940-talen. Faktum är att Koza började hänvisa till programmet som en uppfinningsmaskin och skapade en webbsida som spårar de senaste upptäckterna av mänsklig konkurrenskraftig programvara.

När Kozas grupp testade den fjärde eller femte versionen av deras program började dock något ännu mer överraskande hända: programmet sparkade ut kretsdesigner som inte publicerats någonstans i patentlitteraturen. Två av dessa konstruktioner – ett par kontrollerkretsar som reglerar återkoppling – var så originella att Koza och hans kollegor har tagit patent på dem.

Lika stolt som han är över sin mjukvara, kommer Koza inte att lägga ansvaret för de nya designerna till själva programmet. Patenten krediterar Keane, Koza och Streeter, i den ordningen. Men det finns några nya pseudofilosofiska gåtor som lurar här: Om något är uppfunnit utan någon människa i närheten, är det verkligen en uppfinning? Vem är uppfinnaren? Och om uppfinningen faktiskt fungerar, spelar det någon roll om vi inte förstår hur?

På den sista punkten, säger NASA:s Lohn, finns det två skolor. En säger att jag bara behöver något som gör X, Y och Z, och om evolutionen ger mig X, Y och Z, är det allt jag bryr mig om. Den andra skolan vill veta vad som finns där och hur det fungerar. Vi kan inte riktigt hjälpa dessa människor, eftersom vi ofta ser utvecklade mönster som är helt obegripliga.

Det finns ännu inget behov för människor att känna avundsjuka på mänsklig konkurrenskraftig programvara, säger Koza, eftersom det slutliga målet helt enkelt är att överlåta ingenjörernas svåraste slit till datorer. Han förutser en tid inom en snar framtid – kanske om 20 år – då genetiska algoritmer som körs på ultrasnabba datorer kommer att ta över grundläggande designuppgifter inom så olika områden som elektronik och optik. Men även då, tror Koza, kommer mänsklig och maskinell intelligens att fungera i partnerskap. Vi har aldrig nått den plats där datorer har ersatt människor, säger Koza. I särskilt trånga områden, ja – men historiskt har människor gått vidare för att arbeta med svårare problem. Jag tror att det kommer att fortsätta att vara fallet.

Sam Williams är en frilansande teknikskribent baserad i Staten Island, NY. Han är en frekvent bidragsgivare till Salon.

Dölj