Computers

Künstliche Intelligenz - Evolutionäres Rechnen

Evolutionäres Rechnen

Samuels Prüferprogramm war auch eine der ersten Bemühungen im Bereich des evolutionären Rechnens. (Sein Programm wurde „weiterentwickelt“, indem eine modifizierte Kopie mit der derzeit besten Version seines Programms verglichen wurde, wobei der Gewinner zum neuen Standard wurde.) Beim evolutionären Rechnen wird normalerweise eine automatische Methode zum Generieren und Bewerten aufeinanderfolgender „Generationen“ eines Programms verwendet , bis sich eine hochkompetente Lösung entwickelt.

Ein führender Befürworter des evolutionären Rechnens, John Holland , schrieb auch Testsoftware für den Prototyp der IBM 701 Computer. Insbesondere half er beim Entwurf einer „virtuellen“ Ratte für ein neuronales Netzwerk , die darauf trainiert werden konnte, durch ein Labyrinth zu navigieren. Diese Arbeit überzeugte Holland von der Wirksamkeit des Bottom-up-Ansatzes. Während seiner weiteren Beratung für IBM wechselte Holland 1952 an die University of Michigan , um in Mathematik zu promovieren . Bald wechselte er jedoch zu einem neuen interdisziplinären Programm für Computer und Informationsverarbeitung (später als Kommunikationswissenschaft bekannt), das von Arthur Burks, einem der Erbauer von ENIAC, entwickelt wurdeund sein Nachfolger EDVAC. In seiner Dissertation von 1959, wahrscheinlich der weltweit ersten Doktorarbeit in Informatik , schlug Holland einen neuen Computertyp vor - aMultiprozessor- Computer - das würde jedes künstliche Neuron in einem Netzwerk einem separaten Prozessor zuweisen . (1985 löste Daniel Hillis die technischen Schwierigkeiten beim Bau des ersten solchen Computers, der Thinking Machines Corporation mit 65.536 ProzessorenSupercomputer .)

Holland trat nach seinem Abschluss in die Fakultät in Michigan ein und leitete in den nächsten vier Jahrzehnten einen Großteil der Forschung zu Methoden zur Automatisierung des evolutionären Rechnens, ein Prozess, der heute unter dem Begriff bekannt ist genetische Algorithmen . Zu denim holländischen Labor implementierten Systemengehörten ein Schachprogramm , Modelle einzelliger biologischer Organismen und ein Klassifizierungssystem zur Steuerung eines simulierten Gasleitungsnetzes. Genetische Algorithmen sind jedoch nicht mehr auf „akademische“ Demonstrationen beschränkt. In einer wichtigen praktischen Anwendungkooperiertein genetischer Algorithmus mit einem Zeugen eines Verbrechens, um ein Porträt des Verbrechers zuerstellen.

Logisches Denken und Problemlösen

Die Fähigkeit, logisch zu argumentieren, ist ein wichtiger Aspekt der Intelligenz und war schon immer ein Schwerpunkt der KI-Forschung. Ein wichtiger Meilenstein in diesem Bereich war ein Theoremprüfungsprogramm, das 1955–56 von Allen Newell und J. Clifford Shaw von der RAND Corporation und Herbert Simon von der Carnegie Mellon University geschrieben wurde . DasDer Logiktheoretiker , wie das Programm bekannt wurde, sollte Theoreme aus Principia Mathematica (1910–13) beweisen , einem dreibändigen Werk der britischen Philosophen-Mathematiker Alfred North Whitehead und Bertrand Russell . In einem Fall war ein vom Programm entwickelter Beweis eleganter als der in den Büchern angegebene Beweis.

Newell, Simon und Shaw schrieben ein leistungsfähigeres Programm, das Allgemeiner Problemlöser oder GPS. Die erste Version von GPS lief 1957 und die Arbeit an dem Projekt dauerte etwa ein Jahrzehnt. GPS könnte eine beeindruckende Vielfalt von Rätseln mithilfe eines Trial-and-Error-Ansatzes lösen. Ein Kritikpunkt an GPS und ähnlichen Programmen, denen es an Lernfähigkeit mangelt , ist jedoch, dass die Intelligenz des Programms vollständig aus zweiter Hand ist und aus den Informationen stammt, die der Programmierer ausdrücklich enthält.

Englischer Dialog

Zwei der bekanntesten frühen KI-Programme, Eliza und Parry gab einen unheimlichen Anschein intelligenter Konversation. (Details von beiden wurden erstmals 1966 veröffentlicht.) Eliza, geschrieben von Joseph Weizenbaum vom AI Laboratory des MIT, simulierte einen menschlichen Therapeuten. Parry, geschrieben vom Psychiater Kenneth Colby von der Stanford University , simulierte einen menschlichen Paranoiker . Psychiater, die gefragt wurden, ob sie mit Parry oder einem menschlichen Paranoiker kommunizieren, konnten dies oft nicht sagen.Trotzdem konnten weder Parry noch Eliza vernünftigerweise als intelligent bezeichnet werden. Parrys Beiträge zum Gespräch wurden eingemacht - vom Programmierer im Voraus erstellt und im Speicher des Computers gespeichert . Auch Eliza verließ sich auf eingemachte Sätze und einfache Programmiertricks.

AI Programmiersprachen

Im Verlauf ihrer Arbeit an Logic Theorist und GPS entwickelten Newell, Simon und Shaw ihre Information Processing Language (IPL), eine Computersprache, die auf die AI-Programmierung zugeschnitten ist. Das Herzstück von IPL war eine hochflexible Datenstruktur, die sie als Liste bezeichneten. Eine Liste ist einfach eine geordnete Folge von Datenelementen. Einige oder alle Elemente in einer Liste können selbst Listen sein. Dieses Schema führt zu stark verzweigten Strukturen.

1960 kombinierte John McCarthy Elemente von IPL mit demLambda-Kalkül (ein formales mathematisch-logisches System) zur Erzeugung der ProgrammierspracheLISP (List Processor), die nach wie vor die Hauptsprache für die KI-Arbeit in den USA ist. (Der Lambda-Kalkül selbst wurde 1936 vom Princeton-Logiker Alonzo Church erfunden, als er das abstrakte Entscheidungsproblem oder „Entscheidungsproblem“ für die Prädikatenlogik untersuchte - dasselbe Problem, das Turing angegriffen hatte, als er die universelle Turing-Maschine erfand .)

Die logische Programmiersprache PROLOG (Programmation en Logique) wurde von Alain Colmerauer an der Universität von Aix-Marseille, Frankreich, konzipiert, wo die Sprache erstmals 1973 implementiert wurde. PROLOG wurde vom Logiker Robert Kowalski, Mitglied der AI-Gruppe an der Universität von Aix-Marseille, weiterentwickelt Edinburgh . Diese Sprache verwendet eine leistungsfähige Theorem-beweisende Technik, die als bekannt istResolution , die 1963 vom britischen Logiker Alan Robinson im Argonne National Laboratory der US Atomic Energy Commission in Illinois erfunden wurde . PROLOG kann bestimmen, ob eine bestimmte Anweisung logisch aus anderen angegebenen Anweisungen folgt oder nicht. Angesichts der Aussagen "Alle Logiker sind rational" und "Robinson ist ein Logiker" bejaht ein PROLOG-Programm beispielsweise die Frage "Robinson ist rational?" PROLOG wird häufig für KI-Arbeiten verwendet, insbesondere in Europa und Japan.

Forscher am Institut für Computertechnologie der neuen Generation in Tokio haben PROLOG als Grundlage für hochentwickelte Logikprogrammiersprachen verwendet. Bekannt alsDiese Sprachen der fünften Generation werden auf nichtnumerischen Parallelcomputern verwendet, die am Institut entwickelt wurden.

Other recent work includes the development of languages for reasoning about time-dependent data such as “the account was paid yesterday.” These languages are based on tense logic, which permits statements to be located in the flow of time. (Tense logic was invented in 1953 by the philosopher Arthur Prior at the University of Canterbury, Christchurch, New Zealand.)

Microworld programs

To cope with the bewildering complexity of the real world, scientists often ignore less relevant details; for instance, physicists often ignore friction and elasticity in their models. In 1970 Marvin Minsky and Seymour Papert of the MIT AI Laboratory proposed that likewise AI research should focus on developing programs capable of intelligent behaviour in simpler artificial environments known as microworlds. Much research has focused on the so-called blocks world, which consists of coloured blocks of various shapes and sizes arrayed on a flat surface.

An early success of the microworld approach was SHRDLU, written by Terry Winograd of MIT. (Details of the program were published in 1972.) SHRDLU controlled a robot arm that operated above a flat surface strewn with play blocks. Both the arm and the blocks were virtual. SHRDLU would respond to commands typed in natural English, such as “Will you please stack up both of the red blocks and either a green cube or a pyramid.” The program could also answer questions about its own actions.Although SHRDLU was initially hailed as a major breakthrough, Winograd soon announced that the program was, in fact, a dead end. The techniques pioneered in the program proved unsuitable for application in wider, more interesting worlds. Moreover, the appearance that SHRDLU gave of understanding the blocks microworld, and English statements concerning it, was in fact an illusion. SHRDLU had no idea what a green block was.

Another product of the microworld approach was Shakey , ein mobiler Roboter, der am Stanford Research Institute von Bertram Raphael, Nils Nilsson und anderen in der Zeit von 1968 bis 1972 entwickelt wurde. Der Roboter besetzte eine speziell gebaute Mikrowelt, die aus Wänden, Türen und einigen einfach geformten Holzklötzen bestand. Jede Wand hatte eine sorgfältig gestrichene Fußleiste, damit der Roboter „sehen“ konnte, wo die Wand auf den Boden traf (eine Vereinfachung der Realität, die typisch für den Mikrowelt-Ansatz ist). Shakey hatte ungefähr ein Dutzend Grundfähigkeiten wie TURN, PUSH und CLIMB-RAMP.

Critics pointed out the highly simplified nature of Shakey’s environment and emphasized that, despite these simplifications, Shakey operated excruciatingly slowly; a series of actions that a human could plan out and execute in minutes took Shakey days.

Der größte Erfolg des Mikrowelt-Ansatzes ist eine Art Programm, das als Expertensystem bekannt ist und im nächsten Abschnitt beschrieben wird.