THE UNIVERSIT Y OF MI CHI GAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program Quarterly Report No. 3 15 October 1962 - 15 January 1963 MACHINE ADAPTIVE SYSTEMS John H. Holland J. Willison Crichton Marion R. Finley PM Project 05089 undeir; contract *ith: DEPARTMENT OF THE ARMY U. S. ARMY SIGNAL SUPPLY AGENCY CONTRACT NO. DA-36-039-SC-89085 FORT MONMOUTH, NEW JERSEY administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR February 1965

TABLE OF CONTENTS Page ADAPTATION IN TREE-SEARCH ENVIRONMENTS by John H. Holland 1 NERVE-NET SIMULATION by J. Willison Crichton and Marion R. Finley 4 PERSONNEL 6 OBJECTIVES FOR NEXT QUARTERLY PERIOD 7 ii

ADAPTATION IN TREE-SEARCH ENVIRONMENTS John H. Holland

The investigation of adaptation in tree-search environments continues. The following case has been considered analytically: Utilities (pay-offs) are assigned to each termination of the tree by independent "assignments" satisfying a given distribution function. The adaptive system is assumed to be operating in parallel fashion, so that at each time step it can make several simultaneous "plays" (tracing a path to its termination) —these plays amount to sampling amongst the set of possible paths (even in a game like checkers there may be 1040 paths, so that in most cases of practical interest there will be only a relatively limited sample upon which to base a strategy). Each play costs an amount, x, in units of pay-off; the maximum possible number of plays at any given time-step t+l is deterdfi mined as the integral part of A*/x where A* = (accumulated pay-off to time t+l) minus (expenditures for plays to time t). One can show that the optimum strategy in such a case is to devote a given fraction, y(t)>0, of current assets, A*, at each time-step to further sampling, while employing the remainder [l-y(t)]A* for plays along the best path so far discovered (extremum of samples already taken), The ratio y(t) can be determined in closed form as a function of t for many distributions and a recursive definition can be given for any welldefined distribution. The ratio y(t) represents the best possible strategy for adaptation for the given "random" assignment of utilities to the search tree. Such trees represent, in a certain sense, the worst possible tree-search environments an adaptive system can encounter. Any regularities in the 2

assignment (such as correlation between utilities assigned to various branches) offer the adaptive system opportunities for more rapidly accumulating pay-off. The given rate of accumulation thus sets a lower bound on the rate of adaptation; an adaptive system must do at least as well in any tree-search environment characterized by the given distribution if it is not to be characterized as "inefficient" (since the system employing y(t) will achieve this rate and hence will be more efficient). 5

NERVE-NET SIMULATION J. Willison Crichton Marion R. Finley

In the last quarterly period the debugging of the main program was completed. The first of a series of experiments (the series is to be described in detail in a forthcoming report) was conducted. Initial results have led to the formulation of more specific hypotheses concerning basic parameters, and experiments are now in progress to test and further develop these hypotheses. The following is a breakdown of our use of IBM 7090 time during the quarter: improving SCALP, 28 runs totalling 27 minutes; debugging simulation programs, 29 runs totalling 91 minutes; valid production runs, 6 runs totalling 38 minutes. This makes a total of 63 runs, totalling 2.6 hours. Each production run involved five related experiments using the three neuron model. So far these have been of an exploratory character. These production runs have been of two basic types, the one involving distinct probabilities of stimulation for the two input neurons, the other involving the same probability of stimulation for the two input neurons but with one stimulus being periodically suppressed. The principal implication of these runs seems to be that a positive bias is required for synapse levels in two respects: (1) the range of possible synapse values should include more positive than negative values; (2) the probabilities of synapse change should be markedly greater for changes u_ than for changes down (of the order of a factor of two). Runs being planned for the immediate future are aimed at a more exact determination of these parameters. 5

PERSONNEL The following is a summary of the research hours worked under this contract for the period 15 October to 15 January. J. H. Holland 120 J. W. Crichton 344 M. R. Finley 464 Total man hours 928 6

OBJECTIVES FOR NEXT QUARTERLY PERIOD In the adaptive system theory research, the search for those regularities which will provide opportunities for the adaptive system to exhibit behavior more efficient than the merely random or enumerative, will be continued. Certain simple statistical regularities in the search-tree which can be isolated will be considered in detail. (Holland) In the nerve-net simulation experiments, the next quarterly period will be devoted to the completion of the second stage of experimentation, the two-cycle experiment which simulates the interaction of two cell-assemblies. (Finley and Crichton) 7

DISTRIBUTION LIST (One copy unless otherwise noted) OASD (R&E), Room 3E1065 Director The Pentagon U.S. Naval Research Laboratory Washington 25, D.C. Washington 25, D.C. Attn: Technical Library Attn: Code 2027 Chief, Research and Development Commanding Officer and Director OCS, Department of the Army U.S. Navy Electronics Laboratory Washington 25, D.C. San Diego 52, California Commanding General Aeronautical Systems Division U. S. Army Materiel Command Wright-Patterson Air Force Base, Ohio Washington 25, D.C. Attn: ASAPRL Attn: R&D Directorate Air Force Cambridge Research Commanding General 3 Laboratories U. S. Army Electronics Command L. G. Hanscom Field Fort Monmouth, N.J. Bedford, Massachusetts Attn: AMSEL-AD Attn: CRZC Attn: CRXL-R Commander 10 ASTIA Hq., Electronic Systems Division Arlington Hall Station L. G. Hanscom Field Arlington 12, Virginia Bedford, Massachusetts Attn: TIPCR Attn: ESAT Commanding General APSC Scientific/Technical Liaison USA Combat Developments Command Office Fort Belvoir, Virginia U.S. Naval Air Development Center Attn: CDCMR-E Johnsville, Pennsylvania Commanding Officer Commanding Officer USA Communication and Electronics U.S. Army Electronics Materiel Combat Development Agency Support Agency Fort Huachuca, Arizona Fort Monmouth, New Jersey Attn: SELMS-ADJ Chief, U.S. Army Security Agency 2 Arlington Hall Station Director, Fort Monmouth Office Arlington 12, Virginia USA Communication and Electronics Combat Development Agency Deputy President Fort Monmouth, New Jersey U.S. Army Security Agency Board Arlington Hall Station Arlington 12, Virginia

DISTRIBUTION LIST (Concluded) Corps of Engineers Liaison Office Professor Heinz Von Foerster U.S. Army Electronics Research 215 Electrical Engineering Research and Development Laboratory Laboratory Fort Monmouth, New Jersey University of Illinois Urbana, Illinois Marine Corps Liaison Office US. Army Electronics Research Dr. Saul Amarel and Development Laboratory RCA Laboratories Fort Monmouth, New Jersey Princeton, New Jersey Commanding Officer IBM Research Laboratory U.S, Army Electronics Research Bethesda, Maryland and Development Laboratory Attns Dr. A. Babbitt Fort Monmouth, New Jersey Attn: Logistics Laboratory Sterling Perkes Attn: Director, Research/Engineering Department of Electrical Engineering Attn: Technical Documents Center University of Utah Attnm SELRA/SL-NPE 4 Salt Lake City, Utah Attn; Technical Information Div. 3 Attn: Mr. Anthony V. Campi 14 Commanding General U.S. Army Materiel Command Washington 25, D.C. Attnt R&D Directorate Research Division Electronics Branch