chapter2.ps

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

        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 13 FMDOCUMENT
0 0 /Times-Roman FMFONTDEFINE
1 0 /Times-Bold FMFONTDEFINE
2 0 /Times-Italic FMFONTDEFINE
3 1 /Symbol FMFONTDEFINE
4 0 /Times-BoldItalic FMFONTDEFINE
5 0 /Courier FMFONTDEFINE
6 0 /Courier-Oblique 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: "15" 1
%%BeginPaperSize: Letter
%%EndPaperSize
612 792 0 FMBEGINPAGE
108 72 540 81 R
7 X
0 K
V
0 12 Q
0 X
(15) 312.01 73 T
108 90 540 648 R
7 X
V
0 X
(CHAPTER II) 291.19 640 T
(BACKGROUND) 281.69 604 T
1 F
(2.0  Backgr) 108 562 T
(ound) 166.08 562 T
0 F
-0.09 (This chapter describes background relating to weak methods, strong methods and evo-) 126 536 P
0.24 (lutionary algorithms. It is ar) 108 518 P
0.24 (gued that evolutionary algorithms consist a new type of weak) 243.01 518 P
0.36 (method, called the evolutionary weak method, that adapts its task-independent method of) 108 500 P
-0.16 (search based on information garnered in previous portions of the problem space. First, this) 108 482 P
(chapter begins with a general discussion of search and intelligence.) 108 464 T
1 F
(2.1  Sear) 108 428 T
(ch and Intelligence) 152.09 428 T
0 F
1.23 (Search has always been an integral part of machine intelligence from the \336rst com-) 126 404 P
-0.21 (puter chess programs to the current sur) 108 386 P
-0.21 (ge in learning methods. In general, search is used in) 293.06 386 P
0.44 (two distinct ways. In a standard search, an object with speci\336c properties is to be located) 108 368 P
0.86 (from a known set of objects. For problem solving search, an initial object, a goal object) 108 350 P
0.22 (and a set of operators is provided with the objective being the identi\336cation of an ordered) 108 332 P
1.92 (list of operators that transform the initial object into the goal object. Problem solving) 108 314 P
0.04 (search can be equated as a standard search merely by realizing that the set of objects to be) 108 296 P
(searched is all possible orderings of the operators.) 108 278 T
-0.28 (Let the set of possible search objects be denoted by) 126 248 P
2 F
-0.28 (S) 372.31 248 P
0 F
-0.28 (.) 378.31 248 P
2 F
-0.28 (S) 384.02 248 P
0 F
-0.28 (, in and of itself, is unor) 390.02 248 P
-0.28 (ganized) 502.7 248 P
0.31 (and can contain any form of object from numbers or mathematical equations to computer) 108 230 P
0.67 (programs. T) 108 212 P
0.67 (o or) 166.45 212 P
0.67 (ganize) 185.89 212 P
2 F
0.67 (S) 220.86 212 P
0 F
0.67 (, a set of operators,) 226.85 212 P
2 F
0.67 (O) 324.45 212 P
0 F
0.67 (, can be de\336ned so that) 333.11 212 P
2 F
0.67 (o) 450.03 212 P
2 10 Q
0.56 (i) 456.03 209 P
3 12 Q
0.67 (\316) 461.86 212 P
2 F
0.67 (O, o) 474.08 212 P
2 10 Q
0.56 (i) 495.4 209 P
2 12 Q
0.67 (: S) 498.18 212 P
3 F
0.67 (\256) 515.5 212 P
2 F
0.67 ( S) 527.34 212 P
0 F
0.67 (.) 537 212 P
0.23 (These operators set up an ordering over the set of objects, usually called the) 108 194 P
2 F
0.23 (sear) 477.93 194 P
0.23 (ch space) 498.14 194 P
0 F
2.21 (or) 108 176 P
2 F
2.21 (pr) 123.2 176 P
2.21 (oblem space) 133.42 176 P
0 F
2.21 (. Selecting a set of bene\336cial operators is typically done with some) 195.24 176 P
(understanding of the task and intended representation of the objects.) 108 158 T
0.1 (Often, the search space is described as a Cartesian space, with each point representing) 126 128 P
-0.1 (a single member of the set of objects and each operator of) 108 110 P
2 F
-0.1 (O) 387.18 110 P
0 F
-0.1 ( denoting a dimension orthog-) 395.84 110 P
FMENDPAGE
%%EndPage: "15" 2
%%Page: "16" 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
(16) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
0.58 (onal to the rest. Thus if |) 108 694 P
2 F
0.58 (O) 228.12 694 P
0 F
0.58 (| =) 236.78 694 P
2 F
0.58 (n) 253.1 694 P
0 F
0.58 (, the search space is an) 259.1 694 P
2 F
0.58 (n) 374.8 694 P
0 F
0.58 (-dimensional space. At times the) 380.79 694 P
0.67 (connectivity of the search space is described as a graph or tree with operators serving as) 108 676 P
0.92 (edges between nodes which represent the various objects. In either case, the) 108 658 P
2 F
0.92 (distance) 486.11 658 P
0 F
0.92 ( or) 526.09 658 P
2 F
1.25 (depth) 108 640 P
0 F
1.25 ( between objects is the number of operator applications required to transform one) 134.65 640 P
0.17 (search space object into the other) 108 622 P
0.17 (. In the event that more than one path through the search) 267.71 622 P
(space connect two objects, their distance is the minimum path distance.) 108 604 T
0.3 (Next, an) 126 574 P
2 F
0.3 ( evaluation function) 166.93 574 P
0 F
0.3 (,) 263.47 574 P
2 F
0.3 (f) 269.76 574 P
0 F
0.3 (: S) 273.1 574 P
3 F
0.3 (\256) 289.69 574 P
2 F
0.3 (I) 304.82 574 P
4 F
0.3 (R) 306.81 574 P
0 F
0.3 (, de\336nes the \322correctness\323 of each point in the) 316.81 574 P
0.2 (search space. A threshold of this value identi\336es those points in the space that are consid-) 108 556 P
0.16 (ered solutions. This function may be any computable function including a simple boolean) 108 538 P
1 (function that returns something equivalent to TRUE when a desired object is evaluated.) 108 520 P
1.18 (The evaluation function and the) 108 502 P
2 F
1.18 (n) 269.48 502 P
0 F
1.18 (-dimensional search space combine to de\336ne an) 275.47 502 P
2 F
1.18 (n+) 515.92 502 P
0 F
1.18 (1-) 530.01 502 P
0.92 (dimensional space, often called a) 108 484 P
2 F
0.92 (landscape) 274.46 484 P
0 F
0.92 (, where the value returned by the evaluation) 323.09 484 P
0.55 (function serves to de\336ne the height of each point in the search space. Often, descriptions) 108 466 P
0.8 (of the operation of search methods are in terms of how they traverse the connectivity of) 108 448 P
(the search space or the \322terrain\323 of the landscape.) 108 430 T
1 F
(2.2  Optimization and Satis\336cing) 108 394 T
0 F
0.77 (When a search is performed to locate global extrema of the evaluation function over) 126 370 P
-0.07 (the search space with an extremely lar) 108 352 P
-0.07 (ge number of solutions, such as the space of all pos-) 290.54 352 P
0.77 (sible tours through a collection of cites in the T) 108 334 P
0.77 (raveling Salesperson Problem \050TSP\051, the) 341.38 334 P
0.06 (search is typically called an) 108 316 P
2 F
0.06 (optimization) 243.87 316 P
0 F
0.06 (. Finding the extrema of such lar) 303.84 316 P
0.06 (ge space is often) 460.22 316 P
0.09 (an NP-Hard problem \050Gurari 1989\051, requiring at least an exponentially increasing number) 108 298 P
0.08 (of search space points to be investigated as the problem is scaled up. When the number of) 108 280 P
0.09 (objects that must be investigated in order to \336nd the optimal element increases by a facto-) 108 262 P
(rial, the situation is called) 108 244 T
2 F
( combinatorial explosion) 231.59 244 T
0 F
(.) 351.53 244 T
-0 (Arti\336cial intelligence researchers combat combinatorial explosion in two ways. Often,) 126 214 P
1.19 (a tractable subproblem can be de\336ned and solved more ef) 108 196 P
1.19 (\336ciently that the original NP-) 394.64 196 P
-0.24 (Hard problem. Another way to avoid combinatorial explosion is to settle for less than opti-) 108 178 P
1.29 (mal solutions. In many cases,) 108 160 P
2 F
1.29 (near) 258.71 160 P
0 F
1.29 (optimal solutions, solutions within some reasonable) 284.99 160 P
1.37 (percentage of optimal, can be found consistently and quickly) 108 142 P
1.37 (. Simon \0501969\051 called this) 410.27 142 P
1.02 (approach) 108 124 P
2 F
1.02 (satis\336cing) 155.98 124 P
0 F
1.02 ( to indicate that the solution satis\336es minimal requirements and suf-) 204.62 124 P
(\336ces to solve the problem in the environment.) 108 106 T
FMENDPAGE
%%EndPage: "16" 3
%%Page: "17" 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
(17) 528.01 712 T
108 90 540 702 R
7 X
V
1 F
0 X
(2.3  The Cr) 108 694 T
(edit Assignment Pr) 165.75 694 T
(oblem) 263.47 694 T
0 F
1.74 (The problem solving ability of an algorithm is chie\337y determined by how \322intelli-) 126 670 P
0.38 (gently\323 the algorithm traverses the possible solutions in the problem space. One possibil-) 108 652 P
0.5 (ity is to perform) 108 634 P
2 F
0.5 (cr) 190.64 634 P
0.5 (edit assignment) 200.18 634 P
0 F
0.5 ( \050Minsky 1963\051 on the representational components of) 275.65 634 P
0.85 (each solution encountered and bias future solutions towards or) 108 616 P
0.85 (ganizations of representa-) 414.4 616 P
0.12 (tional pieces that perform well together) 108 598 P
0.12 (. Credit assignment typically refers to the rating of) 296.83 598 P
0.43 (a structure\325) 108 580 P
0.43 (s components as being bene\336cial or harmful to solving the problem. The term) 162.05 580 P
-0.05 (is most associated with machine learning programs, however) 108 562 P
-0.05 (, a search algorithm also uses) 399.66 562 P
0.02 (an implicit form of credit assignment when selecting which element in the search space to) 108 544 P
1.28 (visit next. Poor search algorithms, such as random search, use inaccurate credit assign-) 108 526 P
0.39 (ment, if any) 108 508 P
0.39 (, to guide them through the search space. A more \322intelligent\323 search mecha-) 165.63 508 P
1.75 (nism embodies an accurate credit assignment mechanism for the task and manipulates) 108 490 P
(only problematic representational components to traverse the space.) 108 472 T
-0.26 (Exactly how to assign credit to components of a particular representation is often a dif-) 126 442 P
2.47 (\336cult problem. Occasionally) 108 424 P
2.47 (, if enough assumptions are made, analytical solutions to) 248.41 424 P
-0.19 (credit assignment for a particular problem type and representation can be de\336ned, as in the) 108 406 P
(case of neural networks and back-propagation \050Rumelhart, Hinton and W) 108 388 T
(illiams 1986\051.) 459.91 388 T
1 F
(2.4  W) 108 352 T
(eak and Str) 140.32 352 T
(ong Methods) 199.41 352 T
0 F
-0.12 (At a very high level, AI problem solving methods can be split into two distinct catego-) 126 328 P
0.58 (ries:) 108 310 P
2 F
0.58 (weak) 132.23 310 P
0 F
0.58 (and) 160.46 310 P
2 F
0.58 ( str) 177.77 310 P
0.58 (ong) 193.57 310 P
0 F
0.58 (. A strong method is one that contains a signi\336cant amount of task-) 211.57 310 P
1.24 (speci\336c knowledge in order to solve it. In contrast, a weak method requires little or no) 108 292 P
1.23 (knowledge about a task. As the name implies, strong methods are more powerful algo-) 108 274 P
-0.27 (rithms than weak methods. Strong and weak methods dif) 108 256 P
-0.27 (fer in their approach to task appli-) 378.43 256 P
(cability and task ef) 108 238 T
(fectiveness, as shown in Figure 1.) 198.72 238 T
0.53 (Strong methods can take the form of an analytic solution or an expert system using a) 126 208 P
0.46 (lar) 108 190 P
0.46 (ge knowledge base. Because their content is directed toward solving a particular prob-) 120.44 190 P
0.25 (lem, they tend to be narrowly applicable, as shown in the \336gure. However) 108 172 P
0.25 (, their task-spe-) 465.23 172 P
1.93 (ci\336c knowledge often allows these techniques to \336nd accurate solutions with minimal) 108 154 P
0.18 (computational ef) 108 136 P
0.18 (fort. Analytic methods and rulebases supply the same sort of strength for) 188.91 136 P
0.86 (solving a particular task since they contain the same information at the knowledge-level) 108 118 P
0.31 (\050Newell 1982\051. However) 108 100 P
0.31 (, general analytic methods and lar) 227.7 100 P
0.31 (ge rulebases are not easily cre-) 390.92 100 P
FMENDPAGE
%%EndPage: "17" 4
%%Page: "18" 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
(18) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
0 (ated with current techniques. Knowledge-based AI techniques requires the programmer to) 108 472.94 P
0.27 (extract the task-speci\336c knowledge out of a domain or an expert so it can be inserted into) 108 454.94 P