chapter2.ps

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

(the knowledge base or generalized into an analytical solution.) 108 436.94 T
0.77 (W) 126 406.94 P
0.77 (eak methods are algorithms that are broadly applicable and extendable to all prob-) 136.36 406.94 P
1.35 (lem solving instances. AI uses weak methods as general algorithmic shells in which to) 108 388.94 P
-0.28 (place knowledge as it is identi\336ed and codi\336ed. Interactive re\336nement and/or analytic gen-) 108 370.94 P
0.91 (eralization of the knowledge base is intended to lead to a strong method for the task. In) 108 352.94 P
-0.23 (order to be general, weak methods make no commitments to speci\336c operators that manip-) 108 334.94 P
0.4 (ulate a speci\336c representation \050W) 108 316.94 P
0.4 (inston 1983; Rich 1982\051 and thus make no commitment) 269.64 316.94 P
0.35 (to credit assignment. At most, they supply a general algorithm for traversing the problem) 108 298.94 P
0.85 (space in an orderly manner) 108 280.94 P
0.85 (. T) 240.62 280.94 P
0.85 (ask-speci\336c knowledge speci\336es how to traverse the prob-) 253.95 280.94 P
2.27 (lem space \322intelligently\323 \050W) 108 262.94 P
2.27 (inston 1983; Rich 1982\051. T) 251.88 262.94 P
2.27 (o understand AI\325) 389.71 262.94 P
2.27 (s reliance on) 474.85 262.94 P
(explicit knowledge it is \336rst important to understand the limitations of weak methods.) 108 244.94 T
1 F
(2.4.1  W) 108 208.94 T
(eak Methods) 149.32 208.94 T
0 F
0.27 (W) 126 182.94 P
0.27 (eak methods are problem solving and search techniques inspired by observations of) 136.36 182.94 P
2.28 (human performance \050Rich 1982; W) 108 164.94 P
2.28 (inston 1983\051. They include) 287.18 164.94 P
2 F
2.28 (generate and test) 428.55 164.94 P
0 F
2.28 (,) 515.72 164.94 P
2 F
2.28 (hill) 524 164.94 P
3.26 (climbing) 108 146.94 P
0 F
3.26 (,) 149.98 146.94 P
2 F
3.26 (means-ends analysis) 159.23 146.94 P
0 F
3.26 (,) 261.42 146.94 P
2 F
3.26 (constraint satisfaction) 270.67 146.94 P
0 F
3.26 (,) 380.88 146.94 P
2 F
3.26 (pr) 390.13 146.94 P
3.26 (oblem r) 400.35 146.94 P
3.26 (eduction) 440.14 146.94 P
0 F
3.26 (,) 481.44 146.94 P
2 F
3.26 (depth-\336rst) 490.7 146.94 P
0.26 (sear) 108 128.94 P
0.26 (ch) 128.21 128.94 P
0 F
0.26 (,) 139.53 128.94 P
2 F
0.26 (br) 145.79 128.94 P
0.26 (eadth-\336rst sear) 156.01 128.94 P
0.26 (ch) 228.78 128.94 P
0 F
0.26 ( and) 240.1 128.94 P
2 F
0.26 (best-\336rst sear) 263.94 128.94 P
0.26 (ch) 329.39 128.94 P
0 F
0.26 ( among others. In this section, I present a) 340.71 128.94 P
108 480.94 540 702 C
219.7 692.44 219.7 575.44 2 L
0.5 H
0 Z
0 X
0 K
N
0 12 Q
(Ef) 0 -270 212.47 611.44 TF
(fectiveness) 0 -270 212.47 622.54 TF
219.7 575.44 381.7 575.44 2 L
N
(Space of T) 264.7 560.05 T
(asks) 315.81 560.05 T
90 450 4.5 4.5 292.4 686.67 A
287.9 682.17 296.9 686.67 R
7 X
V
N
180 270 63 104.91 359.9 688.08 G
0 X
180 270 63 104.91 359.9 688.08 A
7 X
270 360 63 104.91 224.9 688.08 G
0 X
270 360 63 104.91 224.9 688.08 A
(Strong Method) 369.04 581.57 T
225.6 634.65 M
 241.18 642.52 258.98 632.31 276.46 630.66 D
 295.45 628.88 317.33 636.53 337.96 633.84 D
 351.35 632.09 364.3 629.7 377.71 630.38 D
1 X
N
0 X
(W) 386.62 628.17 T
(eak Method) 396.98 628.17 T
127.12 507.52 523.69 540.56 R
7 X
V
1 10 Q
0 X
1.23 (Figur) 127.12 533.9 P
1.23 (e 1: Comparison of the effectiveness of weak and str) 150.82 533.9 P
1.23 (ong methods over the variety of) 382.92 533.9 P
1.82 (tasks that can be attempted. Str) 127.12 523.9 P
1.82 (ong methods ar) 271.53 523.9 P
1.82 (e specialized for a set of tasks and mor) 341.07 523.9 P
1.82 (e) 519.25 523.9 P
(effective while weak methods ar) 127.12 513.9 T
(e general acr) 262.95 513.9 T
(oss tasks but less effective.) 317.72 513.9 T
0 0 612 792 C
FMENDPAGE
%%EndPage: "18" 5
%%Page: "19" 5
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
(19) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
0.55 (few representative weak methods with typical properties. In order to simplify the discus-) 108 533.69 P
(sion, the operators for the task are assuemd to connect the search space as a tree.) 108 515.69 T
1 F
(2.4.1.1  Generate and T) 108 479.69 T
(est) 226.49 479.69 T
0 F
0.38 (Generate and test \050Nerwell and Simon 1972\051 is the weakest of the weak methods. All) 126 453.69 P
0.5 (other weak methods can be considered specializations of this one method by virtue of its) 108 435.69 P
0.89 (minimal commitments. The algorithm for a generate and test is shown in Figure 2. T) 108 417.69 P
0.89 (wo) 525.34 417.69 P
0.51 (components are needed to de\336ne a generate and test search: a generator and a tester) 108 399.69 P
0.51 (. The) 514.84 399.69 P
0.02 (generator is a function that returns one objects from the search space) 108 381.69 P
2 F
0.02 (S) 440.67 381.69 P
0 F
0.02 ( at each invocation.) 446.67 381.69 P
1.55 (A generator) 108 363.69 P
1.55 (\325) 166.94 363.69 P
1.55 (s properties are typically dependent on the problem and the quality of the) 170.28 363.69 P
1.05 (operators that or) 108 345.69 P
1.05 (ganize the set of objects. W) 188.5 345.69 P
1.05 (inston \0501983\051 suggests that good generators) 325.86 345.69 P
(should possess the following properties:) 108 327.69 T
(1.) 162 297.69 T
2 F
2.44 (Completeness:) 180 297.69 P
0 F
2.44 ( they eventually produce all positions in a search) 250.62 297.69 P
(space.) 180 279.69 T
(2.) 162 249.69 T
2 F
1.89 (Non-r) 180 249.69 P
1.89 (edundancy) 208.21 249.69 P
0 F
1.89 (: they never damage ef) 260.16 249.69 P
1.89 (\336ciency by proposing the) 376.74 249.69 P
(same solution twice.) 180 231.69 T
(3.) 162 201.69 T
2 F
1.6 (Informedness) 180 201.69 P
0 F
1.6 (: they use possibility limiting information to restrict) 244.62 201.69 P
(the solutions they propose accordingly) 180 183.69 T
(.) 364.43 183.69 T
0.64 (Random search, the weakest generator possible, selects a single element of) 108 153.69 P
2 F
0.64 (S) 477.11 153.69 P
0 F
0.64 ( with a uni-) 483.11 153.69 P
-0.24 (form probability) 108 135.69 P
-0.24 (. It therefore does not require an operator set to traverse the space and thus) 185.94 135.69 P
0.57 (the set of operators,) 108 117.69 P
2 F
0.57 (O,) 207.87 117.69 P
0 F
0.57 ( is null. Note that random search only embodies the completeness) 219.52 117.69 P
0.19 (principle for good generators but neither of the other two. Because of this minimal ability) 108 99.69 P
143.68 541.69 504.32 702 C
159.99 602.16 489.75 693.56 R
7 X
0 K
V
5 12 Q
0 X
(function Generate-and-Test;) 159.99 685.56 T
(begin) 159.99 670.56 T
(obj := Generate\050\051;) 179.82 655.56 T
(while not\050Tester\050obj\051\051) 179.82 640.56 T
(obj := Generate\050\051;) 345.33 640.56 T
(return obj;) 179.82 625.56 T
(end;) 159.99 610.56 T
156.61 567 490.6 582.75 R
7 X
V
1 10 Q
0 X
(Figur) 156.61 576.08 T
(e 2: Algorithm for Generate and T) 180.31 576.08 T
(est weak method.) 326.51 576.08 T
0 0 612 792 C
FMENDPAGE
%%EndPage: "19" 6
%%Page: "20" 6
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
(20) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
0.02 (to reach everything in the space, random search is often used as a comparison to proposed) 108 416.69 P
-0.24 (methods since if a search performs better than random, then some characteristic of the task) 108 398.69 P
(environment must be present in the generator) 108 380.69 T
(.) 324.52 380.69 T
0.37 (The tester in a generate and test method is very simple. Often it is just a function that) 126 350.69 P
0.4 (takes an object returned by the generator and uses the evaluation function to determine if) 108 332.69 P
0.12 (the object is an acceptable solution. This may involve transforming the object returned by) 108 314.69 P
0 (the generator into a more appropriate representation for evaluation. How integrated a gen-) 108 296.69 P
1.66 (erator and tester are determines their ef) 108 278.69 P
1.66 (\336ciency for solving the problem or locating an) 305.55 278.69 P
0.49 (acceptable solution from the search space. Some of the other weak methods specify their) 108 260.69 P
0.19 (traversal of the search space more explicitly to improve performance while still maintain-) 108 242.69 P
(ing a general applicability) 108 224.69 T
(.) 232.13 224.69 T
1 F
(2.4.1.2  Hill Climbing) 108 188.69 T
0 F
0.12 (In hill climbing, the evaluation function plays an important role in the search. Given a) 126 162.69 P
-0.25 (current object, this weak method, shown in Figure 3, evaluates each child of the object and) 108 144.69 P
0.81 (selects the one that the evaluation function judges to be best. Thus, it is always the case) 108 126.69 P
0.13 (that the progression of current positions leads to a series of values returned by the evalua-) 108 108.69 P
116.1 424.69 531.9 702 C
122.29 503.58 524.48 696.94 R
7 X
0 K
V
5 12 Q
0 X
(function Hill-Climber\050obj\051;) 122.29 688.94 T
(begin) 122.29 673.94 T
(best := null;) 142.12 658.94 T
(while \050not \050Tester\050obj\051\051 and not\050best = obj\051 do) 142.12 643.94 T
(begin) 142.12 628.94 T
(best := obj;) 160.12 613.94 T
(for opr in) 160.12 598.94 T
6 F
(O) 239.27 598.94 T
5 F
( do) 246.47 598.94 T
(if \050evaluate\050opr\050obj\051\051 >= evaluate\050best\051\051 then) 178.12 583.94 T
(best := opr\050obj\051;) 196.12 568.94 T
(switch\050obj, best\051;) 160.12 553.94 T
(end;) 142.12 538.94 T
(return obj;) 142.12 523.94 T
(end;) 122.29 508.94 T
125.52 462.94 522.79 488.25 R
7 X
V
1 10 Q
0 X
0.05 (Figur) 125.52 481.58 P
0.05 (e 3: Algorithm for hill climbing weak method. the switch function switches the values of) 149.22 481.58 P
(its arguments so that each has the others value.) 125.52 471.58 T
0 0 612 792 C
FMENDPAGE
%%EndPage: "20" 7
%%Page: "21" 7
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
(21) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
1.97 (tion function that never decreases. Consider the landscape model of the search space.) 108 510.06 P
2.77 (Assuming a maximal value from the evaluation function is preferred, a hill climber) 108 492.06 P
0.14 (traverses the terrain of the landscape so that each step it takes is either up a hill or along a) 108 474.06 P
1.25 (plateau, hence its name. Because the evaluation function determines which child of the) 108 456.06 P
-0 (current object is the most pro\336table to investigate next, this weak method has the property) 108 438.06 P
0.61 (of informedness. However) 108 420.06 P
0.61 (, if the evaluation function de\336nes a non-monotonic landscape) 236.31 420.06 P
2.19 (over the search space, then, depending on the initial position in the space, this weak) 108 402.06 P
(method halts on some local extrema of the space. Thus, this generator is not complete.) 108 384.06 T
1 F
(2.4.1.3  Depth First Sear) 108 348.06 T
(ch) 232.04 348.06 T
0 F
0.78 (Depth-\336rst search, described in Figure 4, is a stronger form of search that assumes a) 126 322.06 P
-0.14 (generator that traverses the search space in a particular manner) 108 304.06 P
-0.14 (. The generator begins at an) 407.48 304.06 P
0.4 (initial position in the search space and expands all of the children of the current structure) 108 286.06 P
0.28 (by calling the algorithm recursively for each child before returning to its parent. Thus the) 108 268.06 P
1.5 (generator moves away from the initial object until the boundary of the search space is) 108 250.06 P
0.66 (seen. Then the algorithm backs up a single operator application and continues. Note that) 108 232.06 P
0.73 (this generator ful\336lls the completeness and non-redundancy principles of a good genera-) 108 214.06 P
1.19 (tor) 108 196.06 P
1.19 (. However) 120.67 196.06 P
1.19 (, it doesn\325) 171.33 196.06 P
1.19 (t possess a mechanism for integrating information learned in the) 221.14 196.06 P
0.29 (search to curb future choices. This is because this weak method only uses the tester func-) 108 178.06 P
2.04 (tion to determine if the current structure is a solution. Thus no information is passed) 108 160.06 P
0.38 (between the tester and the generator since the tester is a simple binary function. On aver-) 108 142.06 P
0.44 (age, when searching for a single position in the space, depth-\336rst search visits half of the) 108 124.06 P
(positions in the search space before identifying the desired object.) 108 106.06 T
112.21 518.06 535.79 702 C
120.37 595.41 526.77 698.06 R
7 X
0 K
V
5 12 Q
0 X
(function Depth-First\050obj\051;) 120.37 690.06 T
(begin) 120.37 675.06 T
(if Tester\050obj\051 then) 140.2 660.06 T
(return obj;) 158.2 645.06 T
(else) 140.2 630.06 T
(for opr in) 158.2 615.06 T
6 F
(O) 237.35 615.06 T
5 F
( do Depth-First-Search\050opr\050obj\051\051;) 244.55 615.06 T
(end;) 120.37 600.06 T
120.93 556.45 524.53 581.06 R
7 X
V
1 10 Q
0 X
0.58 (Figur) 120.93 574.4 P
0.58 (e 4: Recursive algorithm for depth-\336rst sear) 144.63 574.4 P
0.58 (ch. O is the set of operators that de\336nes the) 335.55 574.4 P
(connectivity of the sear) 120.93 564.4 T
(ch space. The connectivity of the space is assumed to be a tr) 219.29 564.4 T
(ee.) 472.56 564.4 T
0 0 612 792 C
FMENDPAGE
%%EndPage: "21" 8
%%Page: "22" 8
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
(22) 528.01 712 T
108 90 540 702 R
7 X
V
1 F
0 X
(2.4.1.4  Br) 108 381.81 T
(eadth-First Sear) 160.09 381.81 T
(ch and Beam Sear) 243.48 381.81 T
(ch) 336.21 381.81 T
0 F
0.52 (Breadth \336rst search also traverses the search space in an orderly fashion, as in depth-) 126 355.81 P
0.34 (\336rst search, but does so in a dif) 108 337.81 P
0.34 (ferent manner) 259.42 337.81 P
0.34 (. In this weak method, all of the positions in) 326.04 337.81 P
0.36 (the space at the same depth away from the initial structure are expanded and evaluated at) 108 319.81 P
1.52 (the same time. If a desired solution is found among them, the search is ended and the) 108 301.81 P
0.08 (object is returned. If not, all objects at the next depth are investigated. Note that this weak) 108 283.81 P
1.49 (method also possesses the properties of completeness and non-redundancy) 108 265.81 P
1.49 (, but as with) 476.89 265.81 P
(depth \336rst search, its operation can not be ef) 108 247.81 T
(fected by previously rejected.) 319.96 247.81 T
0.71 (One disadvantage to breadth-\336rst search is that it can require a signi\336cant amount of) 126 217.81 P
0.6 (space. Consider a set of) 108 199.81 P
2 F
0.6 (b) 227.59 199.81 P
0 F
0.6 ( operators in the set of operators,) 233.59 199.81 P
2 F
0.6 (O) 398.36 199.81 P
0 F
0.6 (. In this space, breadth-\336rst) 407.01 199.81 P
0.49 (search would need to evaluate) 108 181.81 P
2 F
0.49 (b) 258 181.81 P
2 10 Q
0.41 (i) 263.99 186.61 P
0 12 Q
0.49 (positions at depth) 270.26 181.81 P
2 F
0.49 (i) 359.36 181.81 P
0 F
0.49 (, an exponential growth of space. T) 362.69 181.81 P
0.49 (o) 534 181.81 P
0.17 (avoid this, a variant of this weak method, called) 108 163.81 P
2 F
0.17 (beam sear) 342.4 163.81 P
0.17 (ch) 391.76 163.81 P
0 F
0.17 ( \050Lowerre and Reddy 1980\051,) 403.08 163.81 P
1.27 (allows at most a \336xed number) 108 145.81 P
1.27 (,) 258.1 145.81 P
2 F
1.27 (n) 265.37 145.81 P