POLITECHNIKA ŚLĄSKA

WYDZIAŁ AUTOMATYKI ELEKTRONIKI I INFORMATYKI

SPRAWOZDANIE

ALGORYTMY MRÓWKOWE

BIOCYBERNETYKA

Prowadzący ćwiczenie: mgr Jan Juszczyk

Autor: Katarzyna Tomaszewska

Grupa: IiAM2

Cel ćwiczenia

Celem ćwiczenia było dokładne zapoznanie i zrozumienie działania algorytmów mrówkowych.

Problem komiwojażera

Problem komiwojażera polega na znalezieniu najkrótszej drogi pomiędzy n miastami. Komiwojażer musi odwiedzić wszystkie n miast, ale każde może zaliczyć tylko raz.

Podczas laboratorium korzystaliśmy z uproszczonego algorytmy, oznacza to, że komiwojażer nie wraca do miasta początkowego.

Poniższy wykres przedstawia położenie wybranych miast o współrzędnych:

• miasto 1: [0, 0];

• miasto 2: [-1, -1];

• miasto 3: [-5, -5];

• miasto 4: [1, -1];

• miasto 5: [5, -5].

Poniższa tabela zawiera długości poszczególnych możliwych tras wraz z zaznaczoną najkrótszą trasą. Ponieważ miasta rozmieszczone są symetrycznie względem osi Y, istnieją 2 optymalne trasy rozwiązujące ten problem komiwojażera.

Kolejność odwiedzanych miast	Długość trasy
1-4-2-3-5	19,07
1-2-4-5-3	19,07
1-2-3-4-5	20,62
1-4-5-2-3	20,62
1-4-3-2-5	21,46
1-2-5-4-3	21,46
1-2-3-5-4	22,72
1-4-5-3-2	22,72
1-2-5-3-4	25,38
1-4-3-5-2	25,38

Poniższe schematy przedstawiają przebieg najkrótszej trasy:

Wartość feromonu na mrówkę wybrałam liczbę równą liczbie mrówek, czyli 10. Następnie podzieliłam tą wartość przez długość najkrótszej trasy, czyli 19,07. Otrzymaną wartość stanowi średnią wartość feromonu na ścieżkę: 0,52. Następnie średnią wartość feromonu na ścieżkę pomnożyłam razy 10, czyli uwzględniłam przejście daną ścieżką wszystkich mrówek, otrzymałam wartość 5,2.

Sposób dobierania parametrów

Dopierając wartości parowania feromonu oraz zerowego poziomu feromonu sugerowałam się powyższymi obliczeniami. W każdym z zestawów danych wartość feromonu na mrówkę wynosiła 10.

• pierwszy zestaw danych - parowanie feromonu 4, ponieważ maksymalna wartość feromonu na ścieżce wynosi 5.2, jednak nie ma pewności, że wszystkie mrówki przejdą tą ścieżką, dlatego wybrałam pierwszą liczbę całkowitą mniejszą od 5.2 (5 pominęłam ze względu na małą różnicę); zerowy poziom feromonu stanowi połowę wartości maksymalnej ilości feromonu na ścieżce; dane te stanowią odniesienie dla pozostałych przeprowadzonych prób;

• drugi zestaw danych - parowanie feromonu ponownie wynosi 4, a zerowy poziom feromonu zmieniłam na 4, ponieważ chciałam sprawdzić wpływ zerowego poziomu feromonu na częstość wybierania najkrótszej trasy;

• trzeci zestaw danych - podobnie jak w powyższym przykładzie w celu sprawdzenia wpływu na wybieranie najkrótszej trasy zamieniłam wartości z pierwszego zestawu, czyli parowanie feromonu 2.6, natomiast poziom zerowy feromonu 4;

• czwarty zestaw danych - zarówno wartość parowania feromonu, jak i zerowy poziom feromonu wynoszą 2.6;

• piąty zestaw danych - podwoiłam wartość danych z zestawu pierwszego, aby ocenić wpływ wielkości tych parametrów na wybór najkrótszej trasy przy niezmiennej ilości feromonu na mrówkę.

Próba dla pierwszego zestawu wybranych wartości parametrów:

• feromon na mrówkę: 10;

• parowanie feromonu: 4;

• zerowy poziom feromonu: 2,6.

przejście 1: przejście 2:

1	1	2	58,83328		1	1	2	40,74339
2	1	3	51,37501		2	1	3	25,9559
3	1	4	112,7419		3	1	4	162,2627
4	1	5	2		4	1	5	2
5	2	3	116,3413		5	2	3	144,1585
6	2	4	131,384		6	2	4	94,97246
7	2	5	115,1783		7	2	5	136,2998
8	3	4	76,92631		8	3	4	81,70816
9	3	5	156,1728		9	3	5	148,4826
10	4	5	97,01295		10	4	5	92,3035

przejście 3: przejście 4:

1	1	2	146,9284		1	1	2	35,40329
2	1	3	17,00063		2	1	3	60,57664
3	1	4	65,15652		3	1	4	123,8913
4	1	5	2		4	1	5	2
5	2	3	118,0399		5	2	3	133,7456
6	2	4	65,98061		6	2	4	115,4979
7	2	5	110,6662		7	2	5	115,9718
8	3	4	136,6307		8	3	4	65,9186
9	3	5	118,3807		9	3	5	141,4018
10	4	5	152,0395		10	4	5	114,7424

przejście 5: przejście 6:

1	1	2	112,2555		1	1	2	76,05748
2	1	3	28,16292		2	1	3	56,81725
3	1	4	79,94332		3	1	4	96,79799
4	1	5	2		4	1	5	2
5	2	3	112,4657		5	2	3	139,4834
6	2	4	68,82053		6	2	4	120,6925
7	2	5	122,2725		7	2	5	78,26721
8	3	4	120,3004		8	3	4	52,40381
9	3	5	130,2815		9	3	5	159,8779
10	4	5	129,3221		10	4	5	148,4166

przejście 7: przejście 8:

1	1	2	92,92436		1	1	2	106,1635
2	1	3	76,7681		2	1	3	71,30724
3	1	4	50,29716		3	1	4	41,10831
4	1	5	2		4	1	5	2
5	2	3	100,6912		5	2	3	77,16819
6	2	4	115,6833		6	2	4	112,7038
7	2	5	112,3334		7	2	5	99,85211
8	3	4	106,509		8	3	4	124,1629
9	3	5	109,5155		9	3	5	116,6678
10	4	5	139,4481		10	4	5	129,4157

przejście 9: przejście 10:

1	1	2	72,46179		1	1	2	78,90238
2	1	3	24,65501		2	1	3	53,23257
3	1	4	127,0831		3	1	4	90,45292
4	1	5	2		4	1	5	2
5	2	3	114,6501		5	2	3	128,5506
6	2	4	94,57733		6	2	4	135,1334
7	2	5	129,4929		7	2	5	122,3592
8	3	4	96,96342		8	3	4	99,80679
9	3	5	152,4907		9	3	5	116,5052
10	4	5	103,3163		10	4	5	79,94878

Lp.	Kolejność odwiedzanych miast	Ile razy wybrano daną trasę	Długość trasy
1	1-4-2-3-5	4	19,07
2	1-2-3-4-5	1	20,62
3	1-2-5-3-4	1	25,38
4	1-4-5-3-2	2	22,72
5	1-2-4-5-3	2	19,07

Dobrane wartości parametrów pozwoliły uzyskać w powyższych 10-ciu próbach pozytywny rezultat, to znaczy, że została wyznaczona najkrótsza trasa przejazdu zaliczająca wszystkie miasta (6-krotnie została wyznaczona najkrótsza trasa - trasa 1 + trasa 5).

Próba dla drugiego zestawu wybranych wartości parametrów:

• feromon na mrówkę: 10;

• parowanie feromonu: 4;

• zerowy poziom feromonu: 4.

przejście 1: przejście 2:

1	1	2	76,2704		1	1	2	78,38749
2	1	3	33,61723		2	1	3	41,84545
3	1	4	122,0394		3	1	4	107,7524
4	1	5	4		4	1	5	4
5	2	3	140,1596		5	2	3	132,619
6	2	4	81,79112		6	2	4	97,46186
7	2	5	131,8146		7	2	5	107,7611
8	3	4	101,2807		8	3	4	81,75783
9	3	5	123,2005		9	3	5	138,6686
10	4	5	131,2477		10	4	5	149,8545

przejście 3: przejście 4:

1	1	2	94,67543		1	1	2	91,04277
2	1	3	45,26068		2	1	3	54,04535
3	1	4	87,56938		3	1	4	74,54696
4	1	5	4		4	1	5	4
5	2	3	120,3834		5	2	3	101,4293
6	2	4	112,2832		6	2	4	116,108
7	2	5	95,57974		7	2	5	108,1025
8	3	4	87,91791		8	3	4	105,4374
9	3	5	153,5423		9	3	5	147,1453
10	4	5	135,5371		10	4	5	114,6502

przejście 5: przejście 6:

1	1	2	108,9979		1	1	2	88,37651
2	1	3	40,62743		2	1	3	30,70876
3	1	4	80,32674		3	1	4	113,0627
4	1	5	4		4	1	5	4
5	2	3	109,3959		5	2	3	138,5649
6	2	4	88,40496		6	2	4	90,12035
7	2	5	117,0969		7	2	5	109,5494
8	3	4	117,2798		8	3	4	80,44532
9	3	5	133,7992		9	3	5	149,2381
10	4	5	134,2006		10	4	5	141,8338

przejście 7: przejście 8:

1	1	2	83,90898		1	1	2	88,50093
2	1	3	44,43179		2	1	3	52,96768
3	1	4	100,592		3	1	4	75,44295
4	1	5	4		4	1	5	4
5	2	3	136,6735		5	2	3	107,5047
6	2	4	110,8853		6	2	4	99,381
7	2	5	99,95552		7	2	5	113,8487
8	3	4	75,94863		8	3	4	108,5253
9	3	5	149,9146		9	3	5	131,2722
10	4	5	136,2596		10	4	5	130,4353

przejście 9: przejście 10:

1	1	2	89,40373		1	1	2	84,49695
2	1	3	43,24375		2	1	3	33,12768
3	1	4	94,07748		3	1	4	110,7479
4	1	5	4		4	1	5	4
5	2	3	121,6801		5	2	3	126,6688
6	2	4	88,12081		6	2	4	98,65564
7	2	5	119,2153		7	2	5	120,5484
8	3	4	106,4252		8	3	4	97,8303
9	3	5	134,2822		9	3	5	144,9905
10	4	5	127,6318		10	4	5	117,3776

Lp.	Kolejność odwiedzanych miast	Ile razy wybrano daną trasę	Długość trasy
1	1-4-5-2-3	1	20,62
2	1-4-5-3-2	5	22,72
3	1-2-3-5-4	1	22,72
4	1-2-4-5-3	1	19,07
5	1-2-5-4-3	1	21,46
6	1-2-5-3-4	1	25,38

W powyższej próbie najczęściej wybieraną trasą była o długości 22,72, wybrana aż 6-krotnie. Nie jest to zarówno ani najkrótsza trasa, ani najdłuższa.

Próba dla trzeciego zestawu wybranych wartości parametrów:

• feromon na mrówkę: 10;

• parowanie feromonu: 2,6;

• zerowy poziom feromonu: 4.

przejście 1: przejście 2:

1	1	2	72,63998		1	1	2	102,2333
2	1	3	42,77783		2	1	3	46,53404
3	1	4	119,1354		3	1	4	82,67703
4	1	5	1,4		4	1	5	1,4
5	2	3	128,7758		5	2	3	78,12644
6	2	4	101,394		6	2	4	126,237
7	2	5	110,2668		7	2	5	115,6888
8	3	4	82,61095		8	3	4	100,1496
9	3	5	155,219		9	3	5	166,0405
10	4	5	126,0078		10	4	5	114,2044

przejście 3: przejście 4:

1	1	2	121,1525		1	1	2	93,61472
2	1	3	49,96658		2	1	3	51,00789
3	1	4	58,30002		3	1	4	85,88088
4	1	5	1,4		4	1	5	1,4
5	2	3	80,06349		5	2	3	108,2276
6	2	4	106,8437		6	2	4	86,87692
7	2	5	114,8247		7	2	5	131,8948
8	3	4	114,6626		8	3	4	114,7972
9	3	5	152,0895		9	3	5	124,7886
10	4	5	124,1744		10	4	5	128,4515

przejście 5: przejście 6:

1	1	2	88,41984		1	1	2	102,1795
2	1	3	36,54651		2	1	3	75,24438
3	1	4	109,7071		3	1	4	49,34508
4	1	5	4		4	1	5	4
5	2	3	148,251		5	2	3	110,6725
6	2	4	74,31655		6	2	4	113,0174
7	2	5	112,0236		7	2	5	94,41518
8	3	4	102,0457		8	3	4	99,24009
9	3	5	127,0651		9	3	5	124,8224
10	4	5	143,8481		10	4	5	155,3211

przejście 7: przejście 8:

1	1	2	86,04847		1	1	2	78,14465
2	1	3	50,62363		2	1	3	59,27827
3	1	4	96,77957		3	1	4	95,26168
4	1	5	1,4		4	1	5	1,4
5	2	3	120,4882		5	2	3	128,863
6	2	4	111,0945		6	2	4	98,13418
7	2	5	104,9855		7	2	5	111,3914
8	3	4	79,2349		8	3	4	84,36787
9	3	5	145,4107		9	3	5	133,9714
10	4	5	148,1658		10	4	5	144,0488

przejście 9: przejście 10:

1	1	2	76,19963		1	1	2	78,7179
2	1	3	34,36912		2	1	3	42,73845
3	1	4	124,9349		3	1	4	112,4835
4	1	5	1,4		4	1	5	1,4
5	2	3	133,7468		5	2	3	134,2495
6	2	4	84,04723		6	2	4	90,96622
7	2	5	134,2278		7	2	5	109,4796
8	3	4	97,09848		8	3	4	82,51297
9	3	5	130,5562		9	3	5	137,8352
10	4	5	129,1978		10	4	5	153,6602

Lp.	Kolejność odwiedzanych miast	Ile razy wybrano daną trasę	Długość trasy
1	1-4-5-3-2	3	22,72
2	1-2-5-3-4	2	25,38
3	1-2-5-4-3	1	21,46
4	1-2-4-5-3	1	19,07
5	1-4-5-2-3	1	20,62

Powyższa próba nie uzyskała oczekiwanych wyników. Dobrane parametry pozwoliły tylko raz uzyskać najkrótszą trasę, najczęściej wybieraną trasą była: 1-4-5-3-2 o długości 22,72. Po zamienieniu wartości parowania feromonu oraz zerowego poziomu feromonu algorytm nie działa prawidłowo, nie wskazuje jednoznacznie najlepszej trasy (trasa 1, która wybrana jest tylko 3 razy).

Próba dla czwartego zestawu wybranych wartości parametrów:

• feromon na mrówkę: 10;

• parowanie feromonu: 2,6;

• zerowy poziom feromonu: 2,6.

przejście 1: przejście 2:

1	1	2	107,1814		1	1	2	86,91496
2	1	3	51,32582		2	1	3	26,42076
3	1	4	64,91952		3	1	4	117,2317
4	1	5	2,6		4	1	5	2,6
5	2	3	97,81284		5	2	3	138,2323
6	2	4	86,83596		6	2	4	90,73207
7	2	5	122,3017		7	2	5	107,9545
8	3	4	117,2178		8	3	4	76,58502
9	3	5	123,6995		9	3	5	151,7519
10	4	5	136,8252		10	4	5	139,2955

przejście 3: przejście 4:

1	1	2	80,06896		1	1	2	85,47787
2	1	3	35,57394		2	1	3	42,29765
3	1	4	112,0101		3	1	4	90,83832
4	1	5	2,6		4	1	5	2,6
5	2	3	137,9779		5	2	3	126,0775
6	2	4	103,5151		6	2	4	77,05046
7	2	5	103,4429		7	2	5	117,7117
8	3	4	73,39308		8	3	4	104,4628
9	3	5	153,6622		9	3	5	123,0922
10	4	5	130,3337		10	4	5	138,5016

przejście 5: przejście 6:

4	1	5	2,6		4	1	5	2,6
5	2	3	123,906		5	2	3	129,3584
6	2	4	80,03458		6	2	4	108,5429
7	2	5	123,0736		7	2	5	121,1116
8	3	4	105,3856		8	3	4	83,51838
9	3	5	129,5933		9	3	5	142,7526
10	4	5	128,9651		10	4	5	114,3899

przejście 7: przejście 8:

1	1	2	116,879		1	1	2	127,3194
2	1	3	58,80771		2	1	3	28,7895
3	1	4	46,39337		3	1	4	74,13864
4	1	5	2,6		4	1	5	2,6
5	2	3	58,79597		5	2	3	96,4236
6	2	4	114,6877		6	2	4	88,30698
7	2	5	122,9783		7	2	5	113,8015
8	3	4	121,4028		8	3	4	127,5107
9	3	5	145,3469		9	3	5	141,3077
10	4	5	115,2839		10	4	5	128,846

przejście 9: przejście 10:

1	1	2	59,24654		1	1	2	56,97495
2	1	3	51,14585		2	1	3	60,05794
3	1	4	120,9496		3	1	4	104,9409
4	1	5	2,6		4	1	5	2,6
5	2	3	134,6735		5	2	3	144,5688
6	2	4	107,8415		6	2	4	122,5957
7	2	5	118,5489		7	2	5	87,30956
8	3	4	73,1738		8	3	4	52,98758
9	3	5	138,4527		9	3	5	149,3008
10	4	5	128,5764		10	4	5	142,4279

Lp.	Kolejność odwiedzanych miast	Ile razy wybrano daną trasę	Długość trasy
1	1-2-5-4-3	1	21,46
2	1-4-5-3-2	7	22,72
3	1-2-5-3-4	2	25,38

Najczęściej, bo aż 7-krotnie wybrana została trasa 2 (1-4-5-3-2). Nie jest to jednak najkrótsza trasa. W porównaniu do próby pierwszej zmieniono wartość parowania feromonu (parowanie feromonu=zerowy poziom feromonu). Można wnioskować, że wartość parowania feromonu ma wpływ na działanie algorytmu. Jeżeli jest równy lub mniejszy zerowemu poziomowi feromonu algorytm nie działa prawidłowo, tzn. nie znajduje najkrótszej trasy.

Próba dla piątego zestawu wybranych wartości parametrów:

• feromon na mrówkę: 10;

• parowanie feromonu: 8;

• zerowy poziom feromonu: 5,2.

przejście 1: przejście 2:

1	1	2	69,02707		1	1	2	111,7543
2	1	3	73,00356		2	1	3	45,7046
3	1	4	82,17044		3	1	4	65,56413
4	1	5	5,2		4	1	5	5,2
5	2	3	120,0813		5	2	3	116,6086
6	2	4	129,1983		6	2	4	111,9266
7	2	5	104,3688		7	2	5	88,25589
8	3	4	76,66406		8	3	4	99,25735
9	3	5	146,4029		9	3	5	150,0126
10	4	5	124,7526		10	4	5	142,7507

przejście 3: przejście 4:

1	1	2	93,00148		1	1	2	63,64371
2	1	3	58,71181		2	1	3	44,20898
3	1	4	73,84625		3	1	4	122,1363
4	1	5	5,2		4	1	5	5,2
5	2	3	111,4992		5	2	3	142,8378
6	2	4	134,3488		6	2	4	86,40489
7	2	5	81,27257		7	2	5	129,5961
8	3	4	77,73238		8	3	4	103,6508
9	3	5	161,6188		9	3	5	120,4173
10	4	5	144,4195		10	4	5	127,4013

przejście 5: przejście 6:

1	1	2	119,7331		1	1	2	87,76351
2	1	3	47,19412		2	1	3	32,79527
3	1	4	62,46328		3	1	4	114,17
4	1	5	5,2		4	1	5	5,2
5	2	3	108,1019		5	2	3	119,4976
6	2	4	99,09528		6	2	4	106,0739
7	2	5	106,9161		7	2	5	107,7671
8	3	4	111,392		8	3	4	89,29323
9	3	5	132,9097		9	3	5	167,3116
10	4	5	151,2812		10	4	5	122,3461

przejście 7: przejście 8:

1	1	2	63,45149		1	1	2	107,1491
2	1	3	60,51986		2	1	3	44,87928
3	1	4	97,94877		3	1	4	77,4622
4	1	5	5,2		4	1	5	5,2
5	2	3	137,0934		5	2	3	121,0187
6	2	4	111,4501		6	2	4	103,7452
7	2	5	121,4678		7	2	5	98,87035
8	3	4	88,94239		8	3	4	106,4095
9	3	5	118,6098		9	3	5	143,6052
10	4	5	132,3725		10	4	5	136,6041

przejście 9: przejście 10:

1	1	2	61,19007		1	1	2	55,61901
2	1	3	76,73302		2	1	3	82,83937
3	1	4	86,5045		3	1	4	86,85701
4	1	5	5,2		4	1	5	5,2
5	2	3	119,1127		5	2	3	123,9358
6	2	4	139,6324		6	2	4	115,8274
7	2	5	97,93728		7	2	5	115,1827
8	3	4	71,73986		8	3	4	68,62646
9	3	5	151,6509		9	3	5	134,1242
10	4	5	123,0415		10	4	5	137,6296

Lp.	Kolejność odwiedzanych miast	Ile razy wybrano daną trasę	Długość trasy
1	1-4-2-3-5	2	19,07
2	1-2-3-5-4	4	22,72
3	1-4-5-2-3	2	20,62
4	1-4-5-3-2	2	22,72

Po dwukrotnym zwiększeniu wartości parowania feromonu oraz zerowego poziomu feromonu algorytm nie działa prawidłowo. Najczęściej wybierano trasę o długości 22,72 (trasa 2 + trasa 4).

Rezultaty końcowe

Poniższa tabela przedstawia wyniki wszystkich prób, tzn. ile razy wybrano daną trasę o określonej kolejności miast w 50 przejściach komiwojażera.

Lp.	Kolejność odwiedzanych miast	Ile raz wybrano daną trasę	Długość trasy
1	1-4-5-3-2	19	22,72
2	1-4-2-3-5	6	19,07
3	1-2-5-3-4	6	25,38
4	1-2-3-5-4	5	22,72
5	1-2-4-5-3	4	19,07
6	1-4-5-2-3	4	20,62
7	1-2-5-4-3	3	21,46
8	1-2-3-4-5	1	20,62

Wnioski

Najczęściej wybieraną trasą jest trasa o kolejności odwiedzania miast: 1-4-5-3-2. Nie jest to ani trasa najkrótsza, ani najdłuższa, wynosi 22,72j. Prawie wszystkie trasy są stabilne oraz ich skuteczność wynosiła 60%. Wyjątkiem jest próba trzecia, która jest niestabilna (wartość zerowego poziomu feromonu była większa od wartości parowania feromonu). Najlepszy efekt podczas prób uzyskano dla pierwszego zestawu danych, których skuteczność wyniosła 60% dla najkrótszej trasy.

Problem komiwojażera o przedstawionym wyżej sposobie rozmieszczenia miast posiada most symetryczny, czyli dwa możliwe rozwiązania (najkrótsze trasy).

Rozwiązanie problemu komiwojażera za pomocą algorytmu mrówkowego nie gwarantuje znalezienia najkrótszej trasy, ponieważ algorytm ten stanowi przykład metody heurystycznej, czyli metody znajdowania rozwiązania, dla której nie ma gwarancji znalezienia rozwiązania optymalnego. Metody tej używa się również do znajdowania przybliżonych rozwiązań, na podstawie których później wylicza się ostateczny rezultat pełnym algorytmem.

---