12 Exploration Method of Various Routes with Genetic Algorithm 1010369 2001 2 5
( Genetic Algorithm: GA ) GA 2 3 Dijkstra Dijkstra i
Abstract Exploration Method of Various Routes with Genetic Algorithm Inoue Yusuke There is the shortest route decision in the navigation system for the car as one of the applications of the route search method. In this paper I would like to propose the technique of exploring route of denotation map file with a Genetic Algorithm (GA). When the feature of multi point search of GA is made the best use of, and it searches for the route, this technique is able not only to search for the shortest route but also decide the 2nd and the 3rd a short route. Such a route cannot be easily chosen by the Dijkstra method which has been used about the shortest route problem so far.in addition, this technique can decide two or more routes to which the route length is short and the node passed is not similar at the same time by introducing two or more evaluation functions which put different weight.moreover, the effectiveness of this technique was confirmed by doing the experiment which adjusted to the data of an actual map. key words genetic algorithm, shortest route, two or more routes, Dijkstra method ii
1 1 2 3 3 6 4 GA 8 4.1................................ 8 4.1.1............................... 8 4.1.2............................. 9 4.1.3............................ 10 4.2................................ 11 4.3................................... 12 4.4...................................... 13 4.5................................... 16 5 17 5.1................................. 17 5.2 2............................. 18 5.3.......................... 20 5.4...................................... 21 6 22 6.1................................... 22 6.2............................ 23 6.3...................................... 25 iii
7 26 27 28 A 29 B 32 iv
2.1 Dijkstra......................... 4 2.2 Dijkstra................... 4 3.1........................ 6 4.1 (a) (b)..... 8 4.2 a b............. 9 4.3................................... 10 4.4................................ 13 4.5.................................... 14 4.6................................... 15 4.7.................................... 16 5.1.................................... 18 5.2 2................................ 19 5.3......................... 19 5.4............................... 20 6.1.................................... 23 6.2 a b c d 24 v
5.1....................... 17 5.2.............................. 18 6.1....................... 24 vi
1 2 0 1 2 Depth First Search: DFS Breadth First Search: BFS [1] 1 Dijkstra Dijkstra [2] [3] Genetic Algorithm: GA [4] [5] 1
GA GA [6] 3 4 GA 5 Dijkstra GA 6 7 2
2 2 1 DFS BFS 1 DFS BFS DFS BFS Dijkstra Dijkstra Step 1 Step 2 2.1 a 2.1 b 3
Step 3 Step 4 2.1 c Step 5 Step 6 3 3 3 2 2 2 1 4 4 4 3 (a) (b) (c) 2.1 Dijkstra Dijkstra 2.2 V U p V q U 2.2 Dijkstra U V 4
U p p V p p V V p V p 2.2 q p V q q p 0 V q p p p q q p Dijkstra 5
3 John Holland GA 3.1 GA 3.1 6
GA 7
4 GA 4.1 4.1.1 1 4.1 0 1 2 3 0 1 2 3 2 1 NULL 2 0 NULL 3 2 1 2 NULL NULL (a) (b) 4.1 (a) (b) 8
4.1 4.1 b a 0 1 2 1 2 NULL 0 4.1.2 4.2 (a) (b) 4.2 a b 4.2 a 0 4 0 4 9
4.1 4.2 4.1.3 1 7 9 2 6 10 0 8 3 4 5 4.3 10
4.2 4.3 4.1.2 0 10 0 1 6 8 10 0 1 2 3 4 5 6 7 8 9 10 [ 1 6 4 2 5 8 8 6 10 7 9 ] 0 1 1 6 6 8 8 10 4.3 0 1 2 3 4 5 6 7 8 9 10 [ 1 7 4 2 3 2 1 6 7 10 8 ] 0 1 7 6 1 4.2 ( Fitness ) F itness = 1 N rlength(i) i 11
4.3 N rlength i i i-1 4.3 F = N i=1 f i F f i N p i p i = f i F (i = 1,2,,N) q i q i q i = i p j = 1 F j=1 i j=1 f j (i = 1,2,,N) r q i r q i <r<q i+1 (i = 0,1,,N-1, q 0 =0) i +1 N N q i+1 q i r 12
4.4 q i+1 q i = p i+1 4.4 q q 2 1 p N-1 p N p 1 p 2 p 3 p i 4.4 4.4 13
4.4 4.5 [] 0 1 2 3 4 5 6 7 8 9 10 Parent1 [ 4 2 3 7 6 9 8 1 10 8 3 ] Parent2 [ 2 4 7 8 5 2 1 9 8 10 7 ] P1 : 0 4 6 8 10 P2 : 0 2 7 9 10 Offspring1 [ 4 2 3 7 5 9 8 1 8 10 7 ] Offspring2 [ 2 4 3 8 6 7 1 9 10 8 3 ] O1 : 0 4 5 9 10 O2 : 0 2 3 8 10 4.5 0 1 4 2 2 1 0 1 4 4 1 6 2 5 1 4 2 1 14
4.4 4.5 Parent1 2 4.6 0 1 2 3 4 5 6 7 8 9 10 Parent1 [ 4 2 3 2 6 9 8 2 10 8 2 ] Parent2 [ 2 4 7 2 5 2 1 9 8 10 7 ] P1 : 0 4 6 8 10 P2 : 0 2 7 9 10 Offspring1 [ 4 2 3 2 5 2 8 2 8 10 7 ] Offspring2 [ 2 2 7 2 6 9 1 2 10 8 7 ] O1 : 0 4 5 2 3 2 3 O2 : 0 2 7 2 7 4.6 Offspring n M n M M 15
4.5 4.5 4.7 [ 4 2 3 7 5 9 8 1 8 10 7 ] [ 4 2 3 7 5 3 8 1 8 10 7 ] 4.7 4.7 16
5 5.1 63 102 5.1 A 5.1 50 40 20 30 5.1 5.1 A B Dijkstra 17
5.2 2 (m) 12000 A 9000 6000 J I 3000 B 0 5000 10000 15000 20000 (m) 5.1 5.2 0.0936s Dijkstra 0.0096s 5.2 Dijkstra Dijkstra CPU PentiumII-400MHz 5.2 2 GA 2 5.2 Dijkstra 18
5.2 2 (m) 12000 A 9000 6000 J I 3000 B 0 5000 10000 15000 20000 (m) 5.2 2 Dijkstra 5.2 Dijstra 60 Route length in generation change The best Route The second Route 55 50 Route length (Km) 45 40 35 30 25 0 20 40 60 80 100 Number of generations 5.3 5.3 19
5.3 50 100 5.3 5.1 I J 5.1 5.4 (m) 12000 A 9000 6000 J I 3000 B 0 5000 10000 15000 20000 (m) 5.4 A B I J Dijkstra 20
5.4 5.4 40 A Dijkstra GA Dijkstra 2 3 Dijkstra 21
6 Dijkstra GA 6.1 5.1 5.2 5.4 Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step3 22
6.2 Dijkstra GA 1 6.2 4 (m) 2500 Y 2000 1500 X 1000 500 0 500 1000 1500 2000 2500 (m) 6.1 6.1 X Y 111 174 X-Y 6.1 B 23
6.2 6.1 150 60 90 70 (m) (m) 2500 Y 2500 Y 2000 2000 1500 X 1500 X 1000 1000 500 500 0 500 1000 1500 2000 2500 (a) (m) 0 500 1000 1500 2000 2500 (c) (m) (m) (m) 2500 Y 2500 Y 2000 2000 1500 X 1500 X 1000 1000 500 500 0 500 1000 1500 2000 2500 (m) 0 500 1000 1500 2000 2500 (m) (b) (d) 6.2 a b c d 6.2 a d GA 24
6.3 6.3 Dijkstra Dijkstra Dijkstra 25
7 GA Dijkstra GA 1 GA GA 1 GA Dijkstra 26
1999 7 2001 3 GA 3 3 27
[1] 2000 [2] Brian W.Kernighan Dennis M.Ritchie C 1999. [3] 1989. [4] Melanie Mitchell 1997. [5] 1993. [6] (D-I) vol.j82-d-i no.8 pp.1102-1111 Aug.1999. 28
A 5 M Tstop Pc Pm M=50 T=20 10 Pc\Pm 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.1 393 693 693 626 570 715 626 635 636 0.2 693 673 693 620 590 639 542 680 664 0.3 648 659 618 673 393 693 673 582 693 0.4 635 639 693 393 393 693 416 620 601 0.5 555 695 693 597 693 795 464 673 709 0.6 540 693 393 494 416 420 693 468 704 0.7 693 680 639 589 333 393 614 597 693 0.8 633 693 718 393 525 704 464 810 788 0.9 625 608 608 583 525 555 542 620 704 29
M=50 T =30 10 Pc\Pm 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.1 455 412 455 433 524 484 409 522 493 0.2 412 438 455 533 455 635 445 649 286 0.3 445 455 462 452 455 315 423 505 462 0.4 460 455 455 513 455 452 423 420 462 0.5 412 462 466 455 501 431 445 455 465 0.6 445 462 446 635 315 452 473 455 315 0.7 484 462 462 513 462 474 455 583 445 0.8 455 455 446 494 516 455 402 454 513 0.9 455 412 430 467 445 640 440 525 315 M=50 T =40 10 Pc\Pm 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.1 319 319 319 319 319 315 305 319 655 0.2 490 319 276 319 290 315 369 305 320 0.3 319 394 476 305 447 315 319 276 486 0.4 319 422 315 319 456 490 319 319 371 0.5 319 319 319 315 319 319 319 451 404 0.6 319 342 305 319 487 387 286 319 319 0.7 319 328 319 342 313 305 490 319 305 0.8 305 319 410 319 319 319 319 319 319 0.9 319 315 305 315 305 319 319 490 367 30
M=50 T =50 10 Pc\Pm 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.1 319 319 305 290 319 315 305 368 655 0.2 490 319 276 319 315 315 369 319 320 0.3 319 394 476 319 447 315 319 276 457 0.4 319 422 422 319 490 456 490 319 371 0.5 319 319 315 319 290 451 319 453 319 0.6 338 305 319 487 448 286 319 319 319 0.7 319 328 315 319 342 313 319 338 319 0.8 305 319 410 319 319 319 319 319 319 0.9 305 490 305 315 276 319 319 490 367 Cost Time Time (s) M 50 T 40 Pc 0.2 Pm 0.3 19616 0.0936 Pc 0.2 Pm 0.3 21696 0.1337 M 50 T 50 Pc 0.3 Pm 0.8 38800 0.19603 Pc 0.9 Pm 0.5 116864 0.41998 31
B 6 M = 150 T=60 10 Pc\Pm 0.1 0.2 0.3 0.1 247,308,421,300,357 247,252,525,259,689 244,243,806,490,458 0.2 246,395,552,453,947 247,229,638,608,437 258,280,634,547,389 0.3 237,235,524,491,571 247,251,447,451,415 259,232,541,690,604 0.4 248,245,534,599,782 240,232,597,547,454 252,259,576,408,435 0.5 240,234,790,574,644 248,222,818,550,395 244,233,268,815,644 0.6 241,262,262,647,406 265,253,365,408,517 375,224,345,478,789 0.7 404,271,394,294,793 263,242,557,502,854 358,233,423,429,425 0.8 358,367,399,436,369 363,276,362,258,411 374,244,531,298,438 0.9 436,243,427,236,416 358,255,324,383,387 406,223,278,357,384 32
Pc\Pm 0.4 0.5 0.6 0.1 261,243,578,742,499 243,255,258,439,391 255,234,644,603,665 0.2 245,261,464,429,430 238,222,384,570,518 272,244,429,484,763 0.3 230,251,377,357,360 238,223,637,770,328 243,246,394,523,549 0.4 243,266,423,639,368 242,226,621,647,366 267,222,379,483,468 0.5 238,246,343,397,424 259,267,311,782,360 269,240,475,433,367 0.6 370,249,744,361,433 242,234,269,383,379 239,357,308,242,388 0.7 396,226,432,385,370 273,237,522,371,428 295,233,467,358,414 0.8 371,235,378,255,366 239,260,268,362,402 237,252,300,236,369 0.9 260,235,331,409,414 365,248,256,240,443 242,234,381,236,359 Pc\Pm 0.7 0.8 0.9 0.1 258,258,562,398,422 243,251,442,637,378 233,229,354,367,361 0.2 235,249,445,818,798 249,238,273,307,415 251,231,311,236,448 0.3 236,234,517,820,665 254,267,356,432,352 241,237,256,390,358 0.4 240,240,380,335,399 229,235,441,255,286 235,222,331,382,370 0.5 237,374,559,363,372 246,228,282,233,439 251,225,402,228,427 0.6 363,222,359,251,360 242,243,547,313,395 240,276,454,311,365 0.7 240,252,539,363,373 256,244,297,334,368 292,279,288,242,361 0.8 358,258,347,428,356 232,263,467,266,365 256,247,256,335,362 0.9 222,222,256,236,352 352,256,425,236,421 355,359,450,236,383 33