EFTA01125582.pdf

CULTURAL ALGORITHMS: A TUTORIAL DR. ROBERT G. REYNOLDS WAYNE STATE UNIVERSITY DETROIT, MICHIGAN EFTA01125582  OUTLINE • I. Ideational Theories of Cultural Evolution • II. Cultural Algorithms: A Computational Framework • III. General Features • IV. Suitable Problems • V. Designing Cultural Algorithms • Embedding a weak method into the Cultural Algorithm Framework: A Genetic Algorithm Example • IV. Example Applications • V. Future Directions EFTA01125583 Ideational Approaches to Cultural Evolution • Edward B. Tylor was the first to introduce the term "Culture" in his two volume book on Primitive Culture in 1881. • He described culture as "that complex whole which includes knowledge, belief, art, morals, customs, and any other capabilities and habits acquired by man as a member of society". • Early approaches to studying culture focused on classification of cultures worldwide into groups based upon "adhesions" between cultural elements. • George Murdoch (1957) produced a "catalog" of 565 cultures based upon 30 sample characteristics. • Research in Cybernetics and Systems Theory in 1960's spawned new views of culture as a system that interacted with its environment. It provided regulatory mechanisms that provide positive and negative feedback that can respectively amplify and counteract behavioral deviations of individuals within a cultural group. Flannery 1968. EFTA01125584 Ideational Approaches Continued • In the 1960's Cultural Ecology emerged as a discipline concerned with the nature of the interactions between the cultural system and its environment. • In the 1970's saw a new emphasis on how culture shaped the flow of information in a system, a generalization of the cultural ecology perspective. • Geertz (1973)"Culture is the fabric of meaning in terms of which human beings interpret their experience and guide their actions. • Durham(1990)"Culture is shared ideational phenomena (values, ideas, beliefs, and the like)". Less purposeful. EFTA01125585 CULTURAL ALGORITHMS ARE COMPUTATIONAL MODLES OF CULTURAL EVOLUTION BASIC PSEUDOCODE FOR CURTURAL ALGORITHMS IS A AS FOLLOWS: Begin t=0; Initialize Population POP(t); Initialize Belief Space BLF(t); repeat Evaluate Population POP(t); Adjust(BLF(t), Accept(POP(t))); Adjust(BLF(t)); Variation(POP(t) from POP(t-1)); until termination condition achieved End EFTA01125586  Belief Space Adjust Vote Promote f Acceptance Communication Influence Protocol Function Function Reproduce, erformance Modify Inherit Function Population Space The cultural algorithm components consists of a belief space and a population space. The components interacts through a communication protocol EFTA01125587  General Features • Dual Inheritance (at population and knowledge levels) • Knowledge are "beacons" that guide evolution of the population • Supports hierarchical structuring of population and belief spaces. • Domain knowledge separated from individuals(e.g. ontologies) • Supports self adaptation at various levels • Evolution can take place at different rates at different levels ("Culture evolves 10 times faster than the biological component"). • Supports hybrid approaches to problem solving. • A computational framework within which many all of the different models of cultural change can be expressed. EFTA01125588 Hybrid System: Weak Search Method + Knowledge-based Method Search Bias, Guide Knowledge Reproduce Performance Modify Function EFTA01125589 Can support the emergence of hierarchical structures in both the belief and population spaces • i ( GcNOCOP's GA ,.....population EFTA01125590  Suitable Problems • Significant amount of domain knowledge (e.g. constrained optimization problems). • Complex Systems where adaptation can take place at various levels at various rates in the population and belief space. • Knowledge is in different forms and needs to be reasoned about in different ways. • Hybrid systems that require a combination of search and knowledge based frameworks. • Problem solution requires multiple populations and multiple belief spaces and their interaction. • Hierarchically structured problem environments where hierarchically structured population and knowledge elements can emerge. EFTA01125591  II. Designing Cultural Algorithms • 1. Design of the knowledge component • A. Ontological knowledge (shared common concepts for a domain) representation • B. Constraint knowledge representation • C. Solution representation • D. Which will be modified? Update function for each modifiable component. • E. Knowledge Maintenance • 2. Design of the Population Component • A. State variables that determine solution behavior • B. How those variables are used to produce a problem solving strategy or behavior. • C. How such behavior is evaluated? EFTA01125592  Designing Cultural Algorithms: Embedding a Weak Method • Use Genetic Algorithms as an example population model. Show how it can be embedded in the Cultural Framework for a sequence of increasingly complex problems. • Whether you begin with the belief level or the population level depends on the problem. That is, which of the two is more constrained by the problem? • Classification Problems Vs. Construction Problems. With former often start with the belief space, with the latter the population space. In real world situations may have both, select the most constrained of the two. • In either case, iterate between the two adding detail as you go. EFTA01125593  The Genetic Algorithm(Davis,1991) • 1. Initialize a population of chromosomes • 2. Evaluate each chromosome in the population • 3. Create new chromosomes by mating current chromosomes: apply mutation and crossover as the parent chromosomes mate. • 4. Delete members of the population to make room for the new chromosomes. • 5. Evaluate the new chromosomes and insert them into the population. • 6. If time is up, stop and return the best chromosome; if not go to 3. EFTA01125594  A Classification Problem • Mastermind problem. • Guess the set of objects that the oracle has in mind. • Can only get information about whether a specific object is included or not. • Card Problem. EFTA01125595  Cards are divided into two independent categories: suit and face. Face Values all faces Ace King Queen Jack Suit Values all black red spades clubs hearts diamonds Based upon this a possible population is [Suit I Face] Generate examples at random Accept all examples No influence (scorecard) until termination Update using Mitchells Candidate Elimination Alg. Focus on Suit {all=##, b.#0, r=4#1,s=00,c=10,h=01,d=11} EFTA01125596  Static Version Spaces • Use Mitchells candidate elimination search procedure G set ={# # } ## S set = { 00 10 01 11 EFTA01125597  ## Negative examples pushes down G set #0 #1 G set = #O, #1 } 00 10 01 X11 ## Positive examples push up S set = { 00, 10 } G set = I #0, #1 S set = { #0 00 10 01 11 EFTA01125598  If an individual observes another individual, information is recorded in the graph. iz 0 0 Individual observed• Negative ( # # ) = f at ti ( 1 1 ) =i at t2 (11 ) = f at t2 = f at tl EFTA01125599  Classification Example • Generalize on positive examples and specialize with negative examples. When the arrows overlap then a maximally specific concept is identified. The most general concept or set description that is consistent with the negative examples. • Here factored the space into two independent subspaces. Information about guesses is used to update each space independently. • Then select a population representation to generate the guesses. • Suit'Card Suit = {club,spades, hearts, diamonds} Card = {2,..J,Q,K,A} • Performance function = oracle {right, or wrong} • Acceptance function all guesses made this generation. • Influence Function, generate only guesses consistent with the current S and G sets. • Reproduction and modification, mutate each parent to values within within the intersection of the S and G sets. EFTA01125600  A Construction Problem • In a construction problems the state variables are often not independent. • This means that the lattice may not be easily factored into sub-lattices and updated in parallel. Theoretically all parameter values can be used to organize the set. • The fan-out at a given level can be an exponential function of the problem size in the worst case. • Can also be multiple solutions. • Add operations in the belief space to compensate. • E.G. Merge , and stable classes. Can prove properties about the operators (e.g. merge does not lose information Sverdlik) EFTA01125601 Boole Problem: Infer the characteristic function for a unknown boolean multiplexer. Example: Characteristic function: F6 = A'0A11D0 + AOA'1D1 + A'0A1D2 + AOA1D3. For F6 (2 address lines, 4 data lines). Al AO 0 DO 1 Dl 0 D2 1 D3 0 EFTA01125602 Problem Representation Chromosome Description 11A 14 1 ro0 0 1 0 1 0 ('6 1 Version Space Description ## ###1 ##4 to 2Nt4 1# #1 oft . 17 °D EFTA01125603  RI(t) ej R1(41) 7 Modify relation Schematic Description of R2(t) R3(t) Ft2(t+1) R3(41) Cultural R2(40 (4S,S) Algorithm Pmmow 5 RAI+2) (1.3.0 to (2,4) Population of individuals ack • VIP Protocol Reproduce performance interconnects the 2 biological and cultural ,71 s*---1 Apply components operators "unfold" selected strategies EFTA01125604  "Segmentation" Stable class • Generating a homogeneous region with respect to the acceptance function. EFTA01125605  "Merging" S' • Maximally Specific Generalization EFTA01125606  Stable classes are combined In 2 steps: TRAIT POP! L ATM SPACE F6 Stable Schema 1. Positive Instances Stable classes Sx end Sy are combined IFF lal (a) 111111 Sx.Gset Sy.Gset inn (b) 111110 (c) 111010 II Sz is the resultant stable class, (hen: Mtn (d) 111011 Sz.Gset Sx.Gset Sy.Gset A Stable Class is comprised of: Sz.Sset Generalize(Sx. Sset, Sy.Sset) 1. G set SaPop Sx,Pop oSy.Pop 2. S set 3. Population Individual stable From previous example Initially tam stable classes from schema BELIEF SPACE • The G set of an instance Is the stable class Sa and Sb may be combined, as well as Sc and Sd. ance • The S set of an Instance is the Inst e is the instance • The population of an Instanc Sab.Gset ilflat A rel) EXAMPLE: For the Instance (a) Sab.Sset 111119 Sab.Pop (111111, 111110) 07 70 73 Sa.6set : 111tH Sz.Sset 111111 Scd.Gset 111Milit Sa.Pop (111111) Scd.Sset 111011 Std.Pop r (111010, 111011) EFTA01125607 Schema can be merged to share experiences. This can produce group schema. at tl - at t2 — after seeing Eci (negative) after seeing 1 EFTA01125608  1=t merge produces: EFTA01125609 • By making the relations between schemata explicit one can exploit nested collections of high performance • E.G. Clustering of successful cases in circuit design problem [Louis et al., FLAIRS 92] 111101 111010011 1111010011 1111010011 11110/0011 11110100 1111010011 111. 00•• 00001 111110.•6111100001 11111 00001 11111 00011 00011 00011 111110004'1 111110o011 1111100011 1111100011 1111100. Ulitt000ll 111 11111. 0.1 Figure 3: A closer look at the clustered cases reveals nested schenaats. • Cultural Algorithms can exploit collections of nested schemata which is necessary when dealing with complex non-linear systems. EFTA01125610 VGA Symbiosis The Version Spaces approach is now feasible for large problems. Since example generation is done automatically by the GA. THe Version Space guides the generation process using the VIP relation. Schema Theorem: dlen(H) m(H,t+1) >= m(H,t) f(H)[ 1 - Pc len -1 Pin °(1-1)] • The presence of the version space allows the GA system to retain experience outside of its own knowledge base and explore the space at a high rate, even in localized search. • In addition, the population size needed can be reduced markedly. • Interpretation of the results can be done at "high level", relative to accepted hypotheses in the version space. EFTA01125611 Hvperschema Theorem: m(H,t+1 I HS e PATHS(H,t+1)) >= m(H,t I HS e PATHS(H,t)) x avg(f'(H,t) I HS e PATHS(H,t)) x r avg(f(H,t) I HS e PATHS(H,t)) x r [ 1 - [ pm x avg(o(H) I HS E PATHS(H,t)] - [ avg(dlen(H) I HS e PATHS(H,t)1 Pc x len -1 ] EFTA01125612 Comparison of VGA on Boole with other systems, Wilson's Boole Classifier System (1988). Leaning Number of Instances Seen Accuracy of Task Test Results Boole SVGA Boole SVGA Fi, 15,000 1500 97.3% 100 % F11 30,000 3920 97.5% 100 % Quinlan's C4 System (1988). Darning Training Initial Accuracy of Tasks $•t (C,) Population (SVGA) Test Results CL SVGA F, 50 48 85.1% 90.91% F11 200 220 98.3% 100% EFTA01125613 Performance as a function of Genetic Operator Probability. Mutation. Probability of Average Number of Marginal Accuracy Mutation Reproductions of the Test Result 0.1 16.8 96.4% 0.2 14.8 100.0% 0.3 13.2 98.7% Crossover. 0 Probability of Average Number of Marginal Crossover Reproductions Accuracy of The Test Result 0.2 16 91.95% .0.5 16.8 96.38% 0.8 15.2 90.24% EFTA01125614 Experimental Results for F6 as a function of population size. Initial Average Average litAwber of Patterns In CPU Marginal Papule- Muter followink Sets Time Accuracy tion of In of Size Repro- Solution Overlapping Incorrect Seconds the Test ductiona Results 12 35.4 8 8 20.4 1.9 44.0% 24 25.0 8 8 5.8 1.8 73.4% 36 22.2 8 8 2.6 2.2 86.0% 48 18.6 8 8 1.6 2.5 90.9% 60 19.0 8 8 0.4 2.9 97.6% 72 17.2 8 8 0.4 3.1 97.6% 84 14.8 8 8 0.4 4.0 97.6% 96 13.0 8 8 0.4 4.2 97.6% 108 13.4 8 8 • 0.4 4.3 97.6% 120 12.6 8 8 0.0 5.3 100% EFTA01125615 Experimental Results of F11 as a function of population size. Initial Average Average Rueter of Patterns in the CPU Marginal Population Number of followirg sets Time Accuracy Size Repro• In of ducticne Solution Overlapping Incorrect Seconds the Test Results 22 80 16 24 9.4 2385.7 80.9% 44 48.6 15.8 24 9.6 1172.2 80.6% 66 37.0 15.8 23.8 12.6 785.3 75.9% 88 31.6 16 24 1.2 727.9 97.1% 110 26.0 16 24 0.0 725.5 100% 132 23.8 16 24 1.0 769.8 97.6% 154 22.2 16 24 0.2 695.5 99.5% 176 20.2 16 23.8 0.2 757.2 99.5% 198 19.8 16 24 0.0 791.1 100% 220 19.0 16 24 0.0 805.2 100% EFTA01125616 Comparison: • The VGA performs as well as C4 but does not need to generate the 200 examples by hand. • The VGA requires an order of magnitude fewer trials to solve the problem relative to the Classifier approach. • The VGA is much less sensitive to genetic operator probabilities which corresponds with behavior predicted by the Hyperschema Theorem. • Therefore the attention paid to possible symbiotic relationships among components in a hybrid learning system may result in a system capable of outperforming that of its components. EFTA01125617  Population Component • Genetic Algorithms • Often population model has an inherent knowledge structure associated with it. • Genetic Algorithms exploit schemata. The VGA model described earlier is nothing more than the explicit use of binary schemata to guide the generation of examples by the Genetic Algorithm population. • Exploits building blocks. In hierarchical problems building blocks at one level can be exploited and combined at the next level. • Need to allow our representation scheme to emerge based upon the level of complexity achieved in the mined building blocks. EFTA01125618  ROYAL ROAD PROBLEM begin for each target schema i at level 1 begin • ROYAL ROAD FUNCTION if ( mi < m* + 1 ) then function rr parti = ( mi )v; var else if ( m* < mi < b ) then i; { number of target schemata } parti = -( mi - m* )v; { number of levels in hierarchy } else { number of target schemata found at level j } parti = 0; mi; { number of correct bits in a target schema } b; { number of bits in a target schema end u, u*, v, m*; { parameters } { points for number of correct bits } for each level j in hierarchy Parti; bonus.. { points for correct target schemata } begin score; parti bonusj if Or > ) then bonus. = u* + ( nj - 1 )u; else bonus] = 0;' end score=0; for each target schema i at level 1 score = score + parti; for each level j in hierarchy score = score + bonus]; return(score); end; EFTA01125619  ROYAL ROAD PROBLEM • A SIMPLE EXAMPLE Parameters: i = 2, j = 2, u = .3, u* = 1, v = .02, m* = 4, b = 8 Goal: 0 0 0 0 0 0 0 0 bb 0 0 0 0 0 0 0 0 Individuali: 0000111 100111 111 1 1 score = .08 Individual2: 0000011100111 1 1 1 1 1 score = -.02 Individual3: 000000001100000000 score = 2.3 1-2 A 1 2 EFTA01125620  pATHEINDER • LOWEST LEVEL OF BELIEF SPACE 10# - NM 11# - NM A\ A\ A\ Once we acquire building blocks at one level we can Re-size the version space to exploit them EFTA01125621  PTIPPRIMENTS AND RFSI • HIERARCHY USING HOLLAND'S SUGGESTED PARAMETERS E 2 0 EEEE 222 A AAAA AAA 0 1012010110102E100002101 EFTA01125622  PATHFINDER • MULTILEVEL BELIEF SPACE • IT IS POSSIBLE TO CONVERT A NUMBER FROM ONE BASE TO A DIFFERENT BASE. • THE REPRESENTATION SPACE IS HIERARCHICAL, AND CONSTRUCTED DYNAMICALLY. Can move up and down the hierarchy of bases depending Upon how well two adjacent bases do. EFTA01125623 REAL-VALUED SCHEMA IN THE BELIEF SPACE ESCHELMAN AND SCHAEFFER PROPOSED INTERVAL SCHEMATA FOR REAL-VALUED VARIABLES. I I CAEP USED THIS AS BELIEF SPACE KNOWLEDGE TO GUIDE SEARCH USING AN EP POPULATION TO SOLVE UNCONSTRAINED REAL-VALUED FUNCTION OPTIMIZATION PROBLEMS. (CHUNG AND REYNOLDS 1994) FOR PROBLEMS WITH LARGE BASINS AND OR VALLEYS, LESS INFORMATION WAS GAINED FROM EACH INDIVIDUAL DURING A GENERATION. FUZZY SCHEMATA USED FUZZY INTERVALS TO DIRECT SEARCH IN THESE INSTANCES (ZHU AND REYNOLDS, 1998). EFTA01125624 TWO BASIC TYPES OF KNOWLEDGE IN THE BELIEF SPACE: NORMATIVE KNOWLEDGE: STANDARDS OF BEHAVIOR (E.G. 10 > x > 2) ACCEPTABLE RANGE OF VALUES FOR PARAMTER X IN A PARAMETER OPTIMIZATION PROBLEM SITUATIONAL KNOWLEDGE: INDIVIDUAL EXAMPLES OF PROBLEM SOLVING SUCCESS AND OR FAILURE. (E.G. F(0,1,0) HAS THE BEST OBSERVED PERFORMANCE SO FAR. EFTA01125625  Basic Idea of using Constarint-network Constraint-network infeasible Until quiescent and no better performance score has found Domain Range constraints EFTA01125626  Cultural Influence Elite Interval found by acceptable individuals 9 4--- lw- EFTA01125627  1 fi x,) accept updateE updateN 1 0.01 0.01 0.0001 I I 1 0.0 0.1 0.01 1 0 1 3 -0.1 0.2 0.05 o 0 0 4 -0.11 0.0605 0 0 0 5 -0.1 0.59 0.3581 0 0 0 Figure 3.8 Individuals in a population for updating Belie f Space Figure 3.9 shows a result of adjusting situational knowledge from the population in the figure 3.8. Since the best individual has better performance value (0.0001) than that of the current exemplar, the current exemplar is replaced with the current best. <0.01. 0.01>. in the population space. S: El Et 0.0 0.1 0.011 0.01 0.01 0.0001 Figure 3.9 An example result of Adjusting Situational Know ledge EFTA01125628 Figure 3.10 shows a result of adjusting normative know ledge according to the adjustment rules from the population in the figure 3.8. The top 2 individuals. <0.01, 0.01> with performance score 0.0001 and < 0.11. 0.1> with performance score 0.01 are used to adjust the curre nt normative knowledge from the population. N: NI N. NI N. -1.0 1.0 so x -1.0 1.0 x Do 0.0 0.01 0.01 0.0001 0.01 0.1 0.0001 0.01 Figure 3.10 An example result of Adjusting Normative Knowledge The individuals in figure 3.8 arc then become the parents for the next generation of the CAEP system and the process begins anew. EFTA01125629  Influence Function for Interval Schemata Use Cultural Algorithms as a framework in which to perform knowledge-based evolutionary learning Replace a, with empirical generalizations produced in the belief space. Mutation X = Xi + 6 1 • N, (0,1) I f T Interval size information 0 Directional knowledge How is this done? EFTA01125630  Adding Constraint Knowledge • With the addition of constraint knowledge, n one dimensional interval schemata are combined to produce an n-dimensional region. • Regional schemata result from imposing a grid system of a certain granularity on the space. • Grid squares are sampled by scouts. They can be classified based upon the problem characteristics they exhibit: e.g. feasible, infeasible, partially feasible, etc. • The influence function here cause individuals to migrate to or from cells as a function of their characteristics. • New cells are broken down into subregions, explored and exploited. • Knowledge base operations allow the fissioning and fusioning of cells. EFTA01125631 Regional Schema: an n-dimensional region defined as a combination of intervals that circumscribe a portion of n-dimensional space NOW WE EXTEND THIS BY ALLOWING 1. MULTIPLE M-DIMENSIONAL REGIONAL SCHEMATA 2. THE ORGANIZATION OF THESE SCHEMATA INTO A HIERARCHICAL STRUCTURE. 1 2 3 4 EFTA01125632 ACCEPTANCE FUNCTION : HERE, ALL INDIVIDUALS ARE USED TO UPDATE CONSTRAINT KNOWLEDGE. THE TOP 20% ARE USED TO UPDATE THE NORAMTIVE KNOWLEDGE. THESE 20% ARE CALLED THE EMINENT INDIVIDUALS. UPDATE: USE INFERENCE RULES TO ADJUST THE CLASSIFICATION OF ACTIVE CELLS. E.G. FEASIBLE, INFEASIBLE, SEMI-FEASIBLE. ADUST THE HIERARCHICAL STRUCTURE BASED UPON THIS INFORMATION. E.G. FISSION: SPLIT A SEMI-FEASIBLE CELL INTO SMALLER CELLS WHEN THE NUMBER OF INDIVIDUALS BECOMES TOO HIGH. FUSION: MERGE , RECOMBINE CHILDREN INTO THE ORIGINAL PARENT. THEN CAN DECOMPOSE THE PARENT IN A DIFFERENT WAY. E.G. CURRENT DECMPOSITION IS UNATTRACTIVE. E.G. INFEASIBLE CELL BECOMES SEMI- FEASIBLE. EFTA01125633 INFLUENCE FUNCTION: GUIDE THE MIGRATION OF INDIVIDUALS FROM LESS PRODUCTIVE CELLS, INFEASIBLE, TO ONES THAT ARE MORE PRODUCTIVE, SEMI-FEASIBLE AND FEASIBLE CELLS. SEMI- FEASIBLE AND FEASIBLE CELLS WITH EMINENT INDIVIDUALS ARE CALLED EMINENT. HIGHLIGHT THE MIGRATION TO EMINENT CELLS FROM ORDINARY ONES. 1. PERTURB INDIVIDUALS A LITTLE IN EMINENT CELLS. 2. MOVE INDIVIDUALS IN INFEASIBLE CELLS TO FEASIBLE ONES. 3. MOVE INDIVIDUALS FROM ORDINARY TO EMINENT CELLS. EFTA01125634  Implementation and test results To access the approaches, we used a nonlinear constrained optimization problem [Floudas 1990], which is given below: Problem Description Min -12x-7y+, Domain constraints: 0 <x <2, 0 <y <3 Problem constraints: y .≤--2x4+2 Global best point: x*=0.71751, y*=1.470 Global best value: -16.73889 Optimization goal.• < -16.70 EFTA01125635  ill ,a Oa a! MD &a • ill• la 4a *a • 5 7 Evolution of Constraint Knowledge Evolution of Normative Knowledge EFTA01125636  Cultural Algorithm Configuration: Embedding Other Methods • Population models used • Genetic Algorithms (Concept learning, optimization) • Genetic Programming (Evolving agent strategies) • Evolutionary Programming (Real valued function optimization) • Evolution Strategies (Robot soccer plays) • Memetic models (Evolution of agriculture) • Agent based modeling (Evolution of the state, Environmental Impact) EFTA01125637  Knowledge Models Used • Schemata • Binary valued (Maleticconcept learning, Boole problem, data mining) • Real-valued interval schemata (Chang:unconstrained optimization) • Fuzzy Real-valued schemata • Regional Schemata ((Xidong Jin)constrained optimization) • Semantic Networks (DLMS:Rychtyckyj) • Graphical Models (GP:Zannoni, Ostrowski) • Logical and Rule Based models (HYBAL(Sverdlik), Fraud Detection (Sternberg), Lazar (Data mining) EFTA01125638 EFTA01125639 1cojjeA oq).1蚀e~pIe3I80I0aeq3JV o琅O4a北duioj・ ijnsaii se iiu佴坨q4 S)JOA&40N 伟!0OS 0甲0AJ0SqO pU1 uoI靶uIJO」04℃4S ‘巅ouuijj pui snarnj舡）uomo1dmj . JO J0pO囚S OZIX0J/SI JO c0TPA . SW04SJcS pioog xojdmojJO U0T4flI0Aq ・ aT1TSaq)JOUOI)nIOAq  PS Pelationships Network; Phase 2 U 100 200 II I 4UU 600 600 700 100 200 300 400 500 600 700 x EFTA01125640  Future Directions • Integrating Multiple Representations and Population Models • Parallelization • Belief Space Evolution • Designing Cultural Systems • How does a Culture's structure and content reflect its problem solving environment (Saleem) EFTA01125641  A Selected Bibliography of Cultural Algorithms Book Chapters: Reynolds, R.G., "The Impact of Raiding on Settlement Patterns in the Northern Valley of Oaxaca: An Approach Using Decision Trees, Dynamics in Human and Primate Societies: Agent-Based Modelling of Social and Spatial Processes, T. Kohler and G. Gummerman, Editors, Oxford University Press, 1999. Reynolds, R.G., "An Overview of Cultural Algorithms", Advances in Evolutionary Computation, McGraw Hill Press, 1999. Reynolds, R. G., "Why Does Cultural Evolution Proceed at a Faster Rate Than Biological Evolution?", in Time, Process, and Structured Transformation in Archaeology, Sander van der Leeuw and James McGlade Editors, Routledge Press, New York, NY, 1997, pp. 269-282. Reynolds, R. G., "Introduction to Cultural Algorithms", in Proceedings of the Third Annual Conference on Evolutionary Programming, Anthony V. Sebald and Lawrence J. Fogel, Editors, World Scientific Press, Singapore, 1994, pp.131-139. Reynolds, R. G., "Learning to Cooperate Using Cultural Algorithms", in Simulating Societies, Nigel Gilbert and J. Doran, Editors, University College of London Press, 1994, pp. 223-244. Reynolds, R. G., "An Adaptive Computer Model for the Evolution of Plant Collecting and Early Agriculture in the Eastern Valley of Oaxaca", in Guila Naquitz: Archaic Foraging and Early Agriculture in Oaxaca, Mexico, K. V. Flannery, Editor, Academic Press, 1986. pp. 439-500. EFTA01125642 Reynolds, R. G., "Multidimensional Scaling of Four Guila Naquitz Living Floors", in Guila Naquitz: Archaic Foraging and Early Agriculture in Oaxaca, Mexico, K. V. Flannery, Editor, Academic Press, 1986. Book Chapters Co-Authored: Reynolds, R.G., and Chung, Chan-Jin, "Function Optimization using Evolutionary Programming with Self-Adaptive Cultural Algorithms", Lecture Notes on Artificial Intelligence, Springer-Verlag Press, 1997, pp. 184-198. Reynolds, R.G., and Chung, Chan-Jin, "A Cultural Algorithm to Evolve Multi-Agent Cooperation Using Cultural Algorithms", in Evolutionary Programming VI, P. J. Angeline, R. G. Reynolds, J. R. McDonnell, and R. Eberhart, Editors, Springer-Verlag Press, New York, NY, 1997, pp. 323-334. Reynolds, R.G., and Nazzal, Ayman, "Using Cultural Algorithms with Evolutionary Computing to Extract Site location Decisions From Spatio-Temporal Databases, in Evolutionary Programming VI, P. J. Angeline, R. G. Reynolds, J. R. McDonnell, and R. Eberhart, Editors, Springer-Verlag Press, New York, NY, 1997, pp. 323-334. Reynolds, R. G., and Chung, Chan-Jin, "A Test Bed for Solving Optimization Problems Using Cultural Algorithms", in Evolutionary Programming V, John R. McDonnell, and Peter Angeline, Editors, A Bradford Book, MIT Press, Cambridge Massachusetts, 1996, pp. 225-236. Reynolds, R. G., and Zannoni, Elena, "Extracting Design Knowledge from Genetic Programs Using Cultural Algorithms", in Evolutionary Programming V, Peter Angeline, Editor, A Bradford Book, MIT Press, Cambridge Massachusetts, 1996, pp. 217-224. EFTA01125643 Reynolds, R.G., Michalewicz Z., and Cavaretta M. J., "Using Cultural Algorithms for Constraint Handling in Genocop", in Evolutionary Programming IV, J. R. McDonnell, R.G. Reynolds, and David B. Fogel, Editors, a Bradford Book, MIT Press, Cambridge, Massachusetts, 1995. Reynolds, R.G., and Maletic J. I., "The Evolution of Cooperate using Cultural Algorithms", in Proceedings of the Third Annual Conference on Evolutionary Programming, Anthony V. Sebald and Lawrence J. Fogel, Editors, World Scientific Press, Singapore, 1994, pp.141-149. Reynolds R. G., Zannoni, E., and Posner, R. M., "Learning to Understand Software using Cultural Algorithms", in Proceedings of the Third Annual Conference on Evolutionary Programming, Anthony V. Sebald and Lawrence J. Fogel, Editors, World Scientific Press, Singapore, 1994, pp.150-157. Reynolds, R. G. , Brown, W., and Abinoja, E., "Guiding Parallel Bidirectional Search with Cultural Algorithms, in Proceedings of the Third Annual Conference on Evolutionary Programming, Anthony V. Sebald and Lawrence J. Fogel, Editors, World Scientific Press, Singapore, 1994, pp.167-174. Reynolds, R. G. and Zeigler, B.,"Information Processing Models for Hunter-Gatherer Decision Making", in Mathematical Models of Cultural Change, Colin Renfrew and Kenneth Cooke, Editors, Academic Press, December 1978. pp. 485-418. Journal Articles: Reynolds, R.G., Jin, X.*, "Regional Schemata for Real-Valued Constrained Function Optimization Using Cultural Algorithms, Journal of Natural Computing, T. Back, Editor, in press, to appear 2002. Reynolds, R.G., Goodhall, S.,and Whallon, R., "Transmission of Cultural Traits by Emulation: An Agent Based Model of Group Foraging Behavior", Journal of Memetics, March, 2001. EFTA01125644 Reynolds, R. G., and Zhu, Shinin, "Fuzzy Cultural Algorithms with Evolutionary Programming for Real-Valued Function Optimization", IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, Vol. 31, No. 1, February, 2001, pp. 1-18. Reynolds, R. G., and Chung, Chan-Jin*, "Knowledge-Based Self-Adaptation in Evolutionary Search", International Journal of Pattern Recognition and Artificial Intelligence, Vol. 14, No. 1, 2000. Reynolds, R.G., and Chung, Chan Jin*, "CAEP: An Evolution-Based Tool for real-Valued Function Optimization Using Cultural Algorithms", International Journal on Artificial Intelligence Tools, Vol. 7, No. 3, September, 1998, pp. 239-293. Reynolds, R. G., and Sternberg, Michael*, "Using Cultural Algorithms to Support the Re-Engineering of Rule-Based Expert Systems in Dynamic Performance Environments: A Fraud Detection Example", IEEE Transactions on Evolutionary Computation, Vol.1, No. 4, November, 1997, pp. 225-243. Reynolds, R. G., and Zannoni, E.*, "Learning to Control the Program Evolution Process in Genetic Programming Systems Using Cultural Algorithms", Journal of Evolutionary Computation, Vol. 5, No. 2, October, 1997, pp. 181-211. Reynolds, R. G., "Evolution-Based Approaches to Software Engineering: An Introduction", International Journal of Software Engineering and Knowledge Engineering, Vol. 5, No.2, June, 1995, pp. 161-164. Reynolds, R.G., and Sverdlik, W., "An Evolution-Based Approach to Program Understanding Using Cultural Algorithms", International Journal of Software Engineering and Knowledge Engineering