chapter6.ps

收集了遗传算法、进化计算、神经网络、模糊系统、人工生命、复杂适应系统等相关领域近期的参考论文和研究报告

        translate rotate scale /h exch def /w exch def
        /bitmapsave save def 
        
        /is w string def
        
        ws 0 w getinterval is copy pop 
        /cf currentfile def 
        w h 8 [w 0 0 h neg 0 h] 
        {ip} {gip} {bip} true 3 colorimage
        bitmapsave restore 
        grestore
        } bind def
/BITMAPTRUECOLOR { 
        gsave
        translate rotate scale /h exch def /w exch def
        /bitmapsave save def 
        /is w string def
        /gis w string def
        /bis w string def
        /cf currentfile def 
        w h 8 [w 0 0 h neg 0 h] 
        { cf is readhexstring pop } 
        { cf gis readhexstring pop } 
        { cf bis readhexstring pop } 
        true 3 colorimage 
        bitmapsave restore 
        grestore
        } bind def
/BITMAPTRUEGRAYc { 
        gsave
        translate rotate scale /h exch def /w exch def
        /bitmapsave save def 
        
        /is w string def
        
        ws 0 w getinterval is copy pop 
        /cf currentfile def 
        w h 8 [w 0 0 h neg 0 h] 
        {ip gip bip w gray} image
        bitmapsave restore 
        grestore
        } bind def
/ww FMLOCAL
/r FMLOCAL
/g FMLOCAL
/b FMLOCAL
/i FMLOCAL
/gray { 
        /ww exch def
        /b exch def
        /g exch def
        /r exch def
        0 1 ww 1 sub { /i exch def r i get .299 mul g i get .587 mul
			b i get .114 mul add add r i 3 -1 roll floor cvi put } for
        r
        } bind def
/BITMAPTRUEGRAY { 
        gsave
        translate rotate scale /h exch def /w exch def
        /bitmapsave save def 
        /is w string def
        /gis w string def
        /bis w string def
        /cf currentfile def 
        w h 8 [w 0 0 h neg 0 h] 
        { cf is readhexstring pop 
          cf gis readhexstring pop 
          cf bis readhexstring pop w gray}  image
        bitmapsave restore 
        grestore
        } bind def
/BITMAPGRAY { 
	8 {fakecolorsetup} COMMONBITMAP
	} bind def
/BITMAPGRAYc { 
	8 {fakecolorsetup} COMMONBITMAPc
	} bind def
/ENDBITMAP {
	} bind def
end 
	/ALDsave FMLOCAL
	/ALDmatrix matrix def ALDmatrix currentmatrix pop
/StartALD {
	/ALDsave save def
	 savematrix
	 ALDmatrix setmatrix
	} bind def
/InALD {
	 restorematrix
	} bind def
/DoneALD {
	 ALDsave restore
	} bind def
%%EndProlog
%%BeginSetup
(3.0) FMVERSION
1 1 612 792 0 1 17 FMDOCUMENT
0 0 /Times-Roman FMFONTDEFINE
1 0 /Times-Bold FMFONTDEFINE
2 0 /Times-Italic FMFONTDEFINE
3 0 /Times-BoldItalic FMFONTDEFINE
4 0 /Helvetica FMFONTDEFINE
5 0 /Helvetica-Bold FMFONTDEFINE
6 1 /Symbol FMFONTDEFINE
7 0 /Helvetica-Oblique FMFONTDEFINE
8 0 /Courier FMFONTDEFINE
9 0 /Helvetica-BoldOblique FMFONTDEFINE
32 FMFILLS
0 0 FMFILL
1 .1 FMFILL
2 .3 FMFILL
3 .5 FMFILL
4 .7 FMFILL
5 .9 FMFILL
6 .97 FMFILL
7 1 FMFILL
8 <0f1e3c78f0e1c387> FMFILL
9 <0f87c3e1f0783c1e> FMFILL
10 <cccccccccccccccc> FMFILL
11 <ffff0000ffff0000> FMFILL
12 <8142241818244281> FMFILL
13 <03060c183060c081> FMFILL
14 <8040201008040201> FMFILL
16 1 FMFILL
17 .9 FMFILL
18 .7 FMFILL
19 .5 FMFILL
20 .3 FMFILL
21 .1 FMFILL
22 0.03 FMFILL
23 0 FMFILL
24 <f0e1c3870f1e3c78> FMFILL
25 <f0783c1e0f87c3e1> FMFILL
26 <3333333333333333> FMFILL
27 <0000ffff0000ffff> FMFILL
28 <7ebddbe7e7dbbd7e> FMFILL
29 <fcf9f3e7cf9f3f7e> FMFILL
30 <7fbfdfeff7fbfdfe> FMFILL
%%EndSetup
%%Page: "104" 1
%%BeginPaperSize: Letter
%%EndPaperSize
612 792 0 FMBEGINPAGE
108 72 540 81 R
7 X
0 K
V
0 12 Q
0 X
(104) 306.01 73 T
108 90 540 648 R
7 X
V
0 X
(CHAPTER VI) 288.85 640 T
(THE EMERGENCE OF PROBLEM DECOMPOSITIONS AND HIGH-LEVEL) 129.46 604 T
(REPRESENT) 269.51 586 T
(A) 335.86 586 T
(TIONS) 343.18 586 T
1 F
(6.0  The Emergence of Pr) 108 544 T
(oblem Decompositions and High-Level Repr) 237.68 544 T
(esentations) 464.01 544 T
0 F
0.68 (In this chapter) 126 518 P
0.68 (, modular programs are induced using genetic program with additional) 195.49 518 P
0.62 (mutation operators designed to allow decompositions to emer) 108 500 P
0.62 (ge naturally from the prob-) 407.61 500 P
0.08 (lem solving process. Each created module serves as an abstract addition to the representa-) 108 482 P
1.06 (tional language that re\337ects some constraints of the task environment. The evolutionary) 108 464 P
0.55 (weak method described in this chapter acquires appropriate modules and abstractions for) 108 446 P
-0 (the task in spite of an absence of explicit knowledge describing how to create modules for) 108 428 P
(the tasks.) 108 410 T
1 F
(6.1  Pr) 108 374 T
(oblem Decomposition) 141.43 374 T
0 F
0.56 (Often, a dif) 126 350 P
0.56 (\336cult problem can be decomposed into several more simple subproblems,) 181.86 350 P
1.18 (each of which may be more easily solved than the complete problem. In programming,) 108 332 P
0.83 (humans build programs by identifying functions that solve reoccurring subproblems and) 108 314 P
(thereby reduce the overall size of the code.) 108 296 T
1.1 (Simon \0501969\051 ar) 126 266 P
1.1 (gues that problem decomposition is an important aspect of problem) 206.61 266 P
-0.1 (solving. Simon\325) 108 248 P
-0.1 (s \0501969\051 parable of the two watchmakers T) 183.88 248 P
-0.1 (empus and Hora relates another) 388.52 248 P
0.97 (advantage for problem decomposition. In this parable, the two watchmakers build prod-) 108 230 P
0.48 (ucts of similar complexity \0501000 parts\051 using dif) 108 212 P
0.48 (fering design philosophies. T) 343.36 212 P
0.48 (empus con-) 483.89 212 P
1.64 (structs the entire watch directly from the primitive components. Consequently) 108 194 P
1.64 (, if he is) 496.43 194 P
0.45 (interrupted before completing a watch, say by a customer calling on the phone, the inter-) 108 176 P
-0.11 (mediate state is lost and T) 108 158 P
-0.11 (empus must rebuild the entire watch from the individual compo-) 231.53 158 P
0.05 (nents. Hora\325) 108 140 P
0.05 (s method of construction, on the other hand, uses stable intermediate modules) 166.68 140 P
0.92 (which are individually created, assembled into lar) 108 122 P
0.92 (ger and lar) 352.11 122 P
0.92 (ger modules and eventually) 405.01 122 P
0.45 (into the completed product. When Hora is interrupted, only the work for the module cur-) 108 104 P
FMENDPAGE
%%EndPage: "104" 2
%%Page: "105" 2
612 792 0 FMBEGINPAGE
108 63 540 702 R
7 X
0 K
V
108 711 540 720 R
V
0 12 Q
0 X
(105) 522.01 712 T
108 90 540 702 R
7 X
V
0 X
0.55 (rently being constructed is lost. Simon\325) 108 694 P
0.55 (s moral for computational problem solving is that) 298.64 694 P
0.3 (the identi\336cation and solidi\336cation of subproblems carries with it bene\336ts of stability and) 108 676 P
(speed.) 108 658 T
0.83 (Fodor \0501983\051 elevates modularity to a property of the mind. Fodor hypothesizes that) 126 628 P
0.46 (the mind itself is modular) 108 610 P
0.46 (, that the mind can be compartmentalized such that the individ-) 232.62 610 P
0.55 (ual compartments do very little intercommunication. Fodor ar) 108 592 P
0.55 (gues that this compartmen-) 408.1 592 P
(talization need not correspond with the apparent modularity of the brain.) 108 574 T
-0.02 (Means-ends analysis \050Rich 1982; W) 126 544 P
-0.02 (inston 1983\051, a standard AI weak method, embod-) 299.32 544 P
-0.06 (ies a problem decomposition approach to solving problems. In means-ends analysis, prob-) 108 526 P
0.5 (lem speci\336c knowledge is used to determine both how to decompose a problem and how) 108 508 P
2.16 (to solve each identi\336ed sub-problem, possibly by further decomposition. The General) 108 490 P
0.5 (Problem Solver \050GPS\051 \050Newell and Simon 1963\051 uses this weak method as its core com-) 108 472 P
0.16 (putational mechanism. As in all weak methods, GPS uses task-speci\336c knowledge, in this) 108 454 P
(case to determine the decomposition of problems and their eventual solutions.) 108 436 T
0.49 (SOAR \050Newell 1990; Laird, Rosenbloom and Newell 1986a; Laird, Rosenbloom and) 126 406 P
0.57 (Newell 1986b\051 is in a sense the ultimate version of GPS. It uses task-speci\336c knowledge) 108 388 P
-0.11 (together with a technique called) 108 370 P
2 F
-0.11 (chunking) 263.65 370 P
0 F
-0.11 ( to determine decompositions of the task. When-) 307.62 370 P
1.88 (ever no production rule is available in SOAR to ful\336ll any of the current outstanding) 108 352 P
1.09 (goals, a default production rule creates appropriate subgoals. Whenever SOAR solves a) 108 334 P
0.08 (subgoal, the conditions that lead to the subgoal\325) 108 316 P
0.08 (s creation are \322chunked\323 together with the) 337.06 316 P
0.01 (resulting state changes into a new production rule. When a similar set of conditions occur) 108 298 P
0.01 (,) 537 298 P
0.59 (SOAR uses the new \322chunk\323 rather than recreating the subgoal. Given a particular prob-) 108 280 P
0.36 (lem space, SOAR always creates the same decompositions because of its static, task-spe-) 108 262 P
(ci\336c knowledge for when to create subgoals and hence new chunks.) 108 244 T
1.24 (Connectionist researchers are also investigating the bene\336ts of modularity) 126 214 P
1.24 (. W) 490.19 214 P
1.24 (ork by) 507.79 214 P
0.25 (Jacobs, Jordan and Barto \0501990; 1991\051, Nolan and Hinton \0501991\051 and Jacob, Jordan, Hin-) 108 196 P
0.3 (ton and Nolan \0501991\051 demonstrates techniques for problem decomposition in connection-) 108 178 P
2.89 (ist networks. For instance, Jacob, Jordan and Barto \0501990; 1991\051 begin with a pre-) 108 160 P
2.42 (determined architecture that has two parallel subnets and a mechanism for switching) 108 142 P
0.26 (between them. Each of the two subnets is appropriate for one portion of their problem. In) 108 124 P
0.43 (the end, the network learns to switch to the appropriate network based on which instance) 108 106 P
FMENDPAGE
%%EndPage: "105" 3
%%Page: "106" 3
612 792 0 FMBEGINPAGE
108 63 540 702 R
7 X
0 K
V
108 711 540 720 R
V
0 12 Q
0 X
(106) 522.01 712 T
108 90 540 702 R
7 X
V
0 X
-0.16 (of the problem the input belongs. Jordan and Jacobs \0501993\051 extend this method to a hierar-) 108 694 P
(chical or) 108 676 T
(ganization of subnets and decision components.) 149.41 676 T
-0 (In all of the above work, the decompositions of the problem are pre-determined by the) 126 646 P
0.26 (programmer either completely or in part. In the case of SOAR, the discovered chunks are) 108 628 P
0.36 (merely productions representing the transitive closure over the several levels of the prob-) 108 610 P
-0.06 (lem space environment. A run of SOAR does not determine an appropriate decomposition) 108 592 P
0.28 (but merely bene\336ts from one the programmer provides as explicit knowledge. In the con-) 108 574 P
0.73 (nectionist work, the architectures determine the decomposition of the problem implicitly) 108 556 P
0.91 (when the input to the network does not do so explicitly) 108 538 P
0.91 (. The networks must only assign) 380.19 538 P
-0 (appropriate roles to the subnets consistent to their architectural restrictions. While the net-) 108 520 P
0.36 (work training method must determine the computational roles for the individual architec-) 108 502 P
2.09 (tural components, this is far easier than automatically determining a suitable problem) 108 484 P
(decomposition.) 108 466 T
1 F
(6.2  The Genetic Library Builder) 108 430 T
0 F
0.24 (The Genetic Library Builder \050GLiB\051 \050Angeline and Pollack 1993a; Angeline and Pol-) 126 406 P
1.23 (lack 1992\051 is an extended genetic program that uses a form of emer) 108 388 P
1.23 (gent intelligence to) 445.6 388 P
0.95 (construct solutions with task-speci\336c decompositions without relying on explicit knowl-) 108 370 P
0.36 (edge. As with the emer) 108 352 P
0.36 (gence of task-speci\336c features of the last chapter) 220.13 352 P
0.36 (, the only modi\336-) 455.63 352 P
3.56 (cation to the evolutionary algorithm is the addition of weak representation-speci\336c) 108 334 P
0.21 (operators. No explicit knowledge describing how to extract appropriate modules from the) 108 316 P
(programming language representation is available.) 108 298 T
2.06 (The Genetic Library Builder \050GLiB\051 is a dynamic genetic algorithm using Koza\325) 126 268 P
2.06 (s) 535.33 268 P
0.5 (genetic programming paradigm) 108 250 P
0.5 (as the base evolutionary weak method. Individuals of the) 262.55 250 P
0.25 (population in both GPP and GLiB represent programs in a task-speci\336c language that use) 108 232 P
1.72 (a LISP expression tree syntax. Both also use a crossover operator that exchanges ran-) 108 214 P
0.28 (domly selected subtrees between parents to create the novel genotypes. The principal dif-) 108 196 P
-0.03 (ference between GPP and GLiB is the addition of two novel mutation operators that allow) 108 178 P
0.8 (task decompositions to emer) 108 160 P
0.8 (ge. These operators, named) 247.09 160 P
2 F
0.8 (compr) 384.84 160 P
0.8 (ession) 415.04 160 P
0 F
0.8 ( and) 445.02 160 P
2 F
0.8 (expansion) 469.93 160 P
0 F
0.8 (, are) 518.56 160 P
-0.13 (similar to the) 108 142 P
2 F
-0.13 ( fr) 171.04 142 P
-0.13 (eeze) 181.47 142 P
0 F
-0.13 ( and) 202.11 142 P
2 F
-0.13 (unfr) 225.17 142 P
-0.13 (eeze) 244.72 142 P
0 F
-0.13 ( operators of the last chapter) 265.36 142 P
-0.13 (. Both are applied probabilis-) 400.28 142 P
(tically to evolving individuals, as are all evolutionary operators.) 108 124 T
FMENDPAGE
%%EndPage: "106" 4
%%Page: "107" 4
612 792 0 FMBEGINPAGE
108 63 540 702 R
7 X
0 K
V
108 711 540 720 R
V
0 12 Q
0 X
(107) 522.01 712 T
108 90 540 702 R
7 X
V
1 F
0 X
(6.2.1  Compr) 108 485.88 T
(ession of Modules) 174.41 485.88 T
0 F
1.72 (Compression begins by randomly selecting a subtree from the parent. This subtree) 126 459.88 P
0.25 (becomes the body of a new function, called a) 108 441.88 P
2 F
0.25 (module) 330.06 441.88 P
0 F
0.25 (, that is added to the) 365.37 441.88 P
2 F
0.25 (genetic library) 466.46 441.88 P
0.25 (,) 537 441.88 P
0 F
-0.19 (a logical storehouse for the de\336nitions of all modules in the system. This library associates) 108 423.88 P
-0.29 (the chosen subtree with a unique identi\336er that becomes the module\325) 108 405.88 P
-0.29 (s name. The subtree is) 434.23 405.88 P
0.1 (then extracted from the parent and replaced by the newly de\336ned module\325) 108 387.88 P
0.1 (s name. When a) 463.11 387.88 P
0.94 (genetic program with a compressed module is evaluated, the de\336nition of the module is) 108 369.88 P
0.41 (retrieved from the genetic library and executed as though the original subtree were in the) 108 351.88 P
0.77 (genetic program at the point the module\325) 108 333.88 P
0.77 (s name appears. Thus the compression operator) 307.86 333.88 P
(performs only a syntactic modi\336cation to the genetic program rather than a semantic one.) 108 315.88 T
0.66 (A compression operation begins with the selection of a random position in the geno-) 126 285.88 P
-0.09 (type. This position identi\336es the root of the subtree to be compressed. When the module is) 108 267.88 P
0.79 (de\336ned, the subtree is extracted from the genotype and replaced with a unique symbolic) 108 249.88 P
0.61 (name as shown in Figure 24. GLiB binds the extracted subtree to the module\325) 108 231.88 P
0.61 (s symbolic) 487.74 231.88 P
-0.2 (name by entering the pair into the \322genetic library) 108 213.88 P
-0.2 (.\323 This library is the collection of all cre-) 345.43 213.88 P
0.33 (ated modules and serves only as a symbol reference table. During a genotype\325) 108 195.88 P
0.33 (s execution) 485.37 195.88 P
0.28 (GLiB retrieves the de\336nitions of compressed modules from the genetic library) 108 177.88 P
0.28 (. This form) 485.8 177.88 P
0.42 (of compression is identical to Koza\325) 108 159.88 P
0.42 (s) 282.99 159.88 P
2 F
0.42 (encapsulation) 291.08 159.88 P
0 F
0.42 ( operator \050Koza 1992\051 although Koza) 358.37 159.88 P
(takes this operator no further) 108 141.88 T
(.) 245.9 141.88 T
108 90 540 702 C
132.77 493.88 515.23 702 C
144.12 516.94 501.77 549 R
7 X
0 K
V
3 12 Q
0 X
1.59 (Figure 24:) 144.12 541 P
2 F
1.59 (Cr) 203.26 541 P
1.59 (eation of a compr) 215.49 541 P
1.59 (essed module fr) 304.75 541 P
1.59 (om a randomly selected) 382.76 541 P
(subtr) 144.12 529 T
(ee of a genotype. Newfunc\325) 168.33 529 T
(s de\336nition is added to the library) 297.02 529 T
(.) 458.95 529 T