1. Inledning

Antag att vi har en handelsresande som skall besöka ett antal städer. Varje stad skall besökas endast en gång. Hur skall den handelsresande köra för att minimera avståndet han behöver resa? Detta kallas Travelling Salesman Problem (TSP). Vår uppgift är att hitta en lösning baserad på artificiell intelligens metoder.

Utgångspunkten är ett tvådimensionellt koordinatsystem, där X-axeln och Y-axeln går från 0 till 99. I detta koordinatsystem placeras slumpmässigt 100 punkter. Punkterna skall vara unika och deras koordinater skall vara hela tal mellan 0 och 99. Uppgiften går på att finna den kortaste väg som startar och slutar i samma punkt och går genom varje annan punkt exakt en gång.

Metoden skall testas 100 gånger och medelvärdet av de erhållna avståndet skall räknas ut. Det finns inga begränsningar för hur mycket resurser i tid och rum som skall förbrukas för varje enskild körning av programmet.

2. Metoder

Lösningen baseras på Simulated Annealing (optimera sämre värden) och Hill Climbing (välja det bästa värdet) metoder. Lösningen består av två steg: att snabbt och effektivt ta fram en prototyp (relativt kort väg) och sedan vidareutveckla prototypen med hjälp av mer komplexa metoder som tar längre tid (Generate and Test problemlösningstekniken). I bild 1 kan man se den ursprungliga positionen med 20 städer (i paranteser anges distansen mellan städer).

Bild 1. Startposition [190.56]

Bild 2. Best-First Search [82.96]

2.1 Best-First Search

För att minska det stora avståndet som finns från början använder jag metoden Best-First Search. Det går ut på att man alltid väljer den närmast liggande punkten. Den punkt som ligger närmast till punkt 1 blir punkt 2, den punkt som ligger närmast till punkt 2 blir punkt 3 osv. Metoden fortsätter på det sättet genom alla givna punkter och vägen blir mycket kortare (bild 2).

2.2 Korsningshantering(Remove Cross)

Att ta bort alla korsningar är en annan snabb och effektiv metod för att hitta den kortare vägen. Med hjälp av triangelolikhetens teorem kan man bevisa att den väg som innehåller några korsningar alltid är längre än den väg som inte har några korsningar. För att hitta korsningar använder jag den räta linjens ekvation (tvåpunktformen):

y - y1 = (y2 - y1) / (x2 - x1) * (x - x1)

där (x1, y1) och (x2, y2) är två olika punkter på linjen.

I bild 2 kan man se en korsning mellan punkter 1, 5, 6 och 20. Som en korsning betraktas även sådan kombination av fyra punkter där en punkt ligger i mellan två andra punkter (t ex punkt 12 som ligger i mellan punkter 14 och 15 i bild 2).

Bild 2. Best-First Search [82.96]

Bild 3. Remove Cross [84.11]

En korsning kan tas bort genom att byta plats på två punkter. När man tar bort en korsning, skapas ofta en ny korsning, därför är det viktigt att inte lämna kvar nya korsningar (om Remove Cross inte klarar att ta bort alla korsningar på en gång, kan man anropa metoden flera gånger). I bild 3 har alla korsningar tagits bort och punkter 1, 2, 3, 4, 5 och 12, 13, 14 har ändrat sina positioner.

2.3 Lokala lösningar (Best-Local Search)

Ibland, när man tar bort en eller flera korsningar, skapas 'udda vinklar' där man onödigt förlorar en del distans. Punkter 3, 4, 5, 6 (bild 3) framställer en sådan vinkel.

Bild 3. Remove Cross [84.11]

Bild 4. Best-Local Search [81.37]

Metoden Best-Local Search betraktar varje fem punkter i en sträcka som en liten distans och testar om det inte finns något kortare sätt att gå genom dom (t ex sträckan 2, 3, 4, 5, 6 i bild 3). Den första punkten (2) och den femte punkten (6) kan inte placeras om, men det kan man göra med andra tre punkter som ligger i mellan (punkter 3, 4, 5). Möjligheten att placera om tre punkter skapar sex olika alternativ. Varje alternativ mätes och det bästa värdet väljs ut (bild 4). Denna metod upprepas för varje punkt på hela vägen.

2.4 Optimering (Optimize)

Metoder Remove Cross och Best-Local Search kompletterar varandra på ett bra sätt, därför kombineras de i en metod Optimize för att ta bort alla möjliga korsningar och udda vinklar. Eftersom nya korsningar och udda vinklar dyker upp hela tiden under optimeringen, krävs det att man kör metoden flera gånger. Testkörningar visade att fyra gånger ger det mest optimala resultatet i vårt fall.

Bild 4. Best-Local Search [81.37]

Bild 5. Prototype Search [79.69]

2.5 Skapa en prototyp (Prototype Search)

Eftersom metoden Best-First kan returnera olika värden beroende på startpunkten, testar jag denna metod från varje punkt. Dessutom använder jag också metoden Best-First2 som söker efter den närmaste punkten i två riktningar. Det ökar sannolikheten att man hittar den mest optimala lösningen. Både Best-First1 och Best-First2 skapar 200 olika kombinationer av den ursprungliga vägen, och varje kombination optimeras med Optimize (Remove Cross och Best-Local). Den kortaste vägen väljs ut som en prototyp (bild 5) och skickas vidare för mer komplexa sökningar.

2.6 Söka genom flera närmaste punkter (Jump Search)

En enkel test visade att människor kan hitta bättre lösningar än prototypen, dock är skillnaden mellan alla lösningar liten. Om man jämför prototypen och människans lösningar kan man inse att människan ibland gör "fel" och hoppar till någon annan punkt än den som ligger närmast eller nästnärmast, alltså människan accepterar tillfälliga förluster för att vinna i ett längre perspektiv. Det är logiskt för människans tänkande, men det är inte tydligt för en dator.

Bild 5. Prototype Search [79.69]

Bild 6. Jump Search [78.58]

För att tillåta programmet att göra "felaktiga" drag använder jag en metod kallad Jump Search. Metoden testar några närmast liggande "grannar" till varje punkt genom att hoppa dit, sedan optimera vägen och se om denna kombination kan leda till en bättre lösning. I vårt fall hoppar den från punkt 11 till punkt 13 (bild 5) och detta leder till en bättre lösning (bild 6).

Jump Search har några variabler som kan skapa extra variation för att testa så många alternativ som möjligt inom den rimliga sökrymden. Dels är det "djupet" av ett hopp (vilken granne som skall "besökas"), dels vänder man på ordningen av städer för att undvika begränsningar av "enkelriktad väg" (funktionen Invert). En anrop av Jump Search metoden skapar, optimerar och testar runt 100 olika alternativ.

2.7 Den andra delen av sökningen (Final Search)

Slutligen finns det en metod kallad Final Search som anropar metoden Jump Search flera gånger och med olika variabler. Syftet men Final Search metoden är att simulera "människans hand", dvs att först följa "den närmaste punktens" logik, sedan hoppa till någon längre bort liggande punkt, fortsätta följa den kortaste vägen och sedan hoppa igen, osv (bild 7).

Bild 6. Jump Search [78.58]

Bild 7. Final Search [77.08]

Final Search anropar Jump Search metoden 20 gånger, dvs den skapar, optimerar och testar runt 2000 olika variationer av den ursprungliga prototypen. Ordningen av anrop och variabelvärde framgår från olika testkörningar. Final Search tar mycket längre tid än Prototype Search, men den skapar väsentliga förbättringar i den avslutande sökningsfasen.

3. Resultat

Medelvärdet efter 100 körningar är 780,41 enheter. Det tar 6 timmar att köra 100 gånger på en Unix arbetsstation på DSV.

Bäst distans är 703,78 enheter, sämst - 850,59 enheter. Medelvärdet varierade huvudsakligen mellan 782 och 776 enheter. Bilder 8, 9 och 10 är ett exempel med 100 städer (i paranteser anges avståndet mellan städer). Körningsresultat finns i bilagor.

  Bild 8. Startposition [5023,06]

  Bild 9. Prototype Search [826,78]

  Bild 10. Final Search [775,32]

4. För- och nackdelar

En fördel med dessa metoder är att de inte använder random funktion i sina sökningar. Det ger en stabil kombination av slumpmässiga placeringar som leder till att man metodiskt kan bearbeta metoder och koden utan att vara beroende på hur bra alla städer placeras (användning av slumpmässig sökning ändrar random värdet). Den andra fördelen är att metoden Remove Cross bara är baserad på en algoritm, därför den är mer effektiv.

Final Search har dock en nackdel. Den tar längre tid än man skulle önska pga att den anropar metoden Jump Search samma antal gånger i alla situationer, oberoende om det krävs eller inte. Det saknas alltså en bra feedback för att veta om värdet blir bättre efter varje anrop av Jump Search.

En viktig fördel med alla dessa metoder är att det finns ett stort utrymme för förbättringar och nya idéer. Nedan följer några av dem (som jag skulle gärna testa själv med bättre tidsresurser):

• Best-First: använda Best-First i fyra riktningar. Redan Best-First2 (två riktningar) var en förbättring till Best-First1. Man kan starta Best-First sökningen från t ex fyra hörn eller dela upp hela området i fyra zoner.

• Best-Local: använda Best-Local med sex eller sju punkter. Det kommer säkert att kräva mer rader i koden och mer körningstid, men det finns en stor chans att denna kommer att returnera ett finare värde.

• Optimize: ändra ordning och antal varv i Optimize. Testkörningar visar att värdet kan ändras beroende på dessa faktorer.

• Optimize: skapa nya metoder som kan samverka med Remove Cross och Best-Local för att öka effektivitet och eventuell snabbhet.

• Jump Search: använda Jump Search med flera städer. Det ger metoden mer variation, som leder till att flera kombinationer testas.

• Final Search: skicka flera prototyper till Final Search, inte bara det bästa värdet. Enligt Simulated Annealing metoden, kan den nästbästa prototypen leda till ett bättre värde än den bästa prototypen.

• Final Search: utveckla användning av Jump Search metoden i Final Search. Den kombination som används i koden nu (1, 3, 1, 2, 3, 4, 1, 2, 3, 4) har tagits fram med hjälp av flera testkörningar. Det kan visa sig att det finns både snabbare och mer effektiva kombinationer.

Metod

Prototype

Final Search

Medelvärde

807

787

786

785

784

783

782

780

Tid (timmar)

0:30

1:40

2:05

2:25

2:40

2:55

3:30

6:00

Körning

Starposition

Prototype

Final Search

Medelvärde

1

5380.15

836.96

813.07

813.07

2

5081.92

810.42

783.82

798.44

3

4708.74

785.72

777.06

791.32

4

5221.64

800.63

784.37

789.58

5

5339.52

796.67

778.94

787.45

6

5172.13

759.31

756.95

782.37

7

5340.73

772.31

752.38

778.08

8

5074.85

837.21

798.74

780.67

9

5672.79

788.74

779.86

780.58

10

5253.86

818.77

796.42

782.16

11

5301.06

800.29

778.87

781.86

12

5493.28

756.31

744.40

778.74

13

5067.75

810.17

776.81

778.59

14

5034.99

801.05

799.13

780.06

15

5212.55

806.24

773.90

779.65

16

5027.65

786.39

748.49

777.70

17

5070.67

839.41

790.24

778.44

18

5180.51

820.34

777.22

778.37

19

4778.52

812.47

785.01

778.72

20

5394.10

804.16

779.71

778.77

21

5295.33

821.99

803.16

779.93

22

4958.72

820.68

777.05

779.80

23

5557.48

784.14

766.01

779.20

24

5015.97

799.54

777.92

779.15

25

5722.08

765.98

762.41

778.48

26

5069.73

793.64

756.39

777.63

27

5218.12

808.44

787.66

778.00

28

5203.21

743.03

726.82

776.17

29

5243.31

846.03

820.89

777.71

30

4904.30

845.35

810.21

778.80

31

5246.22

810.71

790.52

779.18

32

5306.64

866.13

817.11

780.36

33

5156.08

820.87

812.08

781.32

34

5264.82

805.41

780.56

781.30

35

5257.70

802.97

796.08

781.72

36

5017.76

813.04

756.23

781.01

37

4965.80

763.58

742.50

779.97

38

4858.00

807.67

778.25

779.93

39

5816.15

783.96

777.68

779.87

40

5216.36

809.15

794.54

780.24

41

5195.12

746.32

729.46

779.00

42

5046.57

835.63

793.56

779.35

43

5141.91

784.69

756.38

778.81

44

5566.80

778.37

753.66

778.24

45

4951.21

846.57

827.24

779.33

46

5249.88

817.58

789.15

779.54

47

4766.29

832.69

816.28

780.32

48

5028.95

804.80

758.77

779.87

49

5516.48

807.42

787.83

780.04

50

4666.47

757.47

740.38

779.24

51

5289.09

794.07

771.99

779.10

52

5210.46

842.24

799.91

779.50

53

4745.08

817.33

773.16

779.38

54

5553.14

831.75

795.74

779.68

55

5322.81

763.21

752.08

779.18

56

5234.18

787.49

736.44

778.42

57

4635.31

808.56

768.41

778.24

58

5074.96

834.26

803.42

778.68

59

5238.51

820.94

798.49

779.01

60

5038.58

811.87

781.95

779.06

61

5260.74

822.92

781.95

779.11

62

5219.87

766.25

753.53

778.70

63

5148.09

835.71

795.06

778.96

64

5368.75

785.12

748.17

778.48

65

4980.89

772.36

753.34

778.09

66

4750.18

800.67

784.64

778.19

67

5770.07

797.20

764.69

777.99

68

5465.39

851.50

818.19

778.58

69

4974.41

792.70

765.96

778.40

70

5318.00

806.69

743.33

777.89

71

5127.36

762.83

730.03

777.22

72

5314.35

795.50

771.13

777.14

73

5508.00

805.21

801.95

777.48

74

4842.43

785.70

762.11

777.27

75

5346.86

845.64

825.71

777.91

76

5252.31

840.20

818.16

778.44

77

5216.34

804.27

772.54

778.37

78

5175.39

805.09

774.54

778.32

79

5535.80

795.90

771.77

778.24

80

5048.32

813.15

788.26

778.36

81

5034.02

813.28

776.02

778.33

82

5374.28

820.88

812.90

778.75

83

4972.84

726.91

703.78

777.85

84

5394.51

818.97

809.61

778.23

85

5277.66

831.65

799.23

778.47

86

4802.13

811.25

793.81

778.65

87

5250.29

780.07

766.72

778.52

88

5073.72

828.65

810.49

778.88

89

5714.98

839.86

809.39

779.22

90

5051.40

818.24

791.30

779.36

91

5370.60

814.49

812.33

779.72

92

4970.01

868.74

850.59

780.49

93

5023.21

788.85

770.70

780.38

94

5028.91

782.65

774.86

780.33

95

4983.37

812.22

793.90

780.47

96

5276.74

821.82

808.94

780.76

97

5270.74

766.90

754.90

780.50

98

4656.11

819.09

779.53

780.49

99

4960.32

792.69

772.38

780.41

100

4848.71

812.33

780.42

780.41