前言
最近初學(xué)蟻群算法，用eil51.tsp數(shù)據(jù)集做訓(xùn)練黑滴。從一開始的44x，經(jīng)過各種優(yōu)化后紧索，終于基本穩(wěn)定在最優(yōu)解426袁辈，偶爾次優(yōu)解427、428這樣子珠漂。期間積累了不少心得和數(shù)據(jù)晚缩，現(xiàn)借這篇文章給大家分享一下，其中如果有說得不對的地方希望大家能批評指點媳危，也希望路過的大神們能留下你們的寶貴意見荞彼。
閱讀對象
-蟻群算法初學(xué)者
-TSP規(guī)模在100以內(nèi)的優(yōu)化探討
Let's Begin
為什么選擇eil51.tsp
1.規(guī)模較少，方便測試和觀察數(shù)據(jù)
2.沒有重復(fù)點
初學(xué)蟻群算法待笑，很容易會碰到以下兩個問題：
1.alpha鸣皂，beta因子設(shè)定。這些因子的設(shè)定沒有固定值滋觉，要根據(jù)實際問題去估算签夭，是一個經(jīng)驗參數(shù)，實際環(huán)境中椎侠，要不停調(diào)優(yōu)來觀察出一個合理值第租。
2.容易陷入局部最優(yōu)。下面我們主要針對這個問題來探討蟻群算法的優(yōu)化我纪。
先貼一下普通蟻群算法主要部分代碼：
/**
* 選擇下一個城市
* @return mixed
*/
public function move()
{
$roulette_wheel = 0.0;
foreach ($this->unvisit_tsp_points as $tsp_point_no => $tsp_point) {
$roulette_wheel += pow($this->get_pheromone($tsp_point), $this->alpha) * pow($this->get_heuristic($tsp_point), $this->beta);
}
$random_value = lcg_value();
$wheel_value = 0;
$choose_tsp_point = false;
foreach ($this->unvisit_tsp_points as $tsp_point_no => $tsp_point) {
$wheel_value += (pow($this->get_pheromone($tsp_point), $this->alpha) * pow($this->get_heuristic($tsp_point), $this->beta) / $roulette_wheel);
if ($wheel_value >= $random_value) {//使用輪盤法來決定下一個城市
unset($this->unvisit_tsp_points[$tsp_point_no]);
$choose_tsp_point = $tsp_point;
$this->path[] = $choose_tsp_point;
$this->current_tsp_point = $choose_tsp_point;
break;
}
}
return $choose_tsp_point;
}
/**
* 更新信息素
*
* @return void
*/
private function update_pheromones()
{
$pheromone_deltas = array(); //保存每條邊本次循環(huán)信息素增量
foreach ($this->tsp_points as $i_no => $tsp_point_i) {
foreach ($this->tsp_points as $j_no => $tsp_point_j) {
$pheromone_deltas[$i_no][$j_no] = 0;
$pheromone_deltas[$j_no][$i_no] = 0;
}
}
foreach ($this->ants as $ant) {
$len = $ant->path_len;
for ($i = 0; $i < count($ant->path); $i++) {
$j = $i + 1;
if ($j == count($ant->path)) {
$j = 0;
}
$i_no = $ant->path[$i]->no;
$j_no = $ant->path[$j]->no;
$pheromone_deltas[$i_no][$j_no] += $this->q / $len; //累加每個經(jīng)過這條邊的螞蟻產(chǎn)生的信息素慎宾。單個螞蟻產(chǎn)生的信息素計算公式是： 信息素因子Q/路徑長度
$pheromone_deltas[$j_no][$i_no] += $this->q / $len;
}
}
foreach ($this->tsp_points as $i_no => $tsp_point) {
foreach ($tsp_point->pheromones as $j_no => $pheromone) {
$new_pheromone = (1 - $this->rou) * $pheromone + $pheromone_deltas[$i_no][$j_no];//原路徑信息素?fù)]發(fā)丐吓，然后加上本次信息素增量
$this->tsp_points[$i_no]->pheromones[$j_no] = $new_pheromone;
$this->tsp_points[$j_no]->pheromones[$i_no] = $new_pheromone;
}
}
}
參數(shù)設(shè)定
循環(huán)次數(shù)：200
螞蟻數(shù)目：35
alpha：2.3
beta：4.5
信息素因子Q：1
信息素蒸發(fā)系數(shù)：0.05
默認(rèn)信息素濃度：0.5
運行效果：
本次最優(yōu)解:444 在第40次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:447 在第46次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:447 在第42次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:450 在第150次搜索命中最優(yōu)解 耗時:6秒
本次最優(yōu)解:452 在第130次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:447 在第12次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:450 在第104次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:452 在第154次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:445 在第53次搜索命中最優(yōu)解 耗時:6秒
本次最優(yōu)解:444 在第57次搜索命中最優(yōu)解 耗時:5秒
可以看出普通螞蟻搜索質(zhì)量是比較差的，而且很早就收斂趟据，可以看出即使增加搜索次數(shù)券犁，也很難得到更優(yōu)解。那增加螞蟻數(shù)量呢汹碱，于是嘗試把螞蟻數(shù)量增加到50個粘衬，和問題規(guī)模相當(dāng)，得到的結(jié)果如下：
本次最優(yōu)解:444 在第34次搜索命中最優(yōu)解 耗時:8秒
本次最優(yōu)解:458 在第52次搜索命中最優(yōu)解 耗時:7秒
本次最優(yōu)解:444 在第26次搜索命中最優(yōu)解 耗時:7秒
本次最優(yōu)解:455 在第40次搜索命中最優(yōu)解 耗時:8秒
本次最優(yōu)解:444 在第38次搜索命中最優(yōu)解 耗時:8秒
本次最優(yōu)解:444 在第41次搜索命中最優(yōu)解 耗時:7秒
本次最優(yōu)解:454 在第24次搜索命中最優(yōu)解 耗時:7秒
本次最優(yōu)解:453 在第29次搜索命中最優(yōu)解 耗時:8秒
本次最優(yōu)解:456 在第33次搜索命中最優(yōu)解 耗時:7秒
本次最優(yōu)解:444 在第31次搜索命中最優(yōu)解 耗時:8秒
可以看出咳促，除了增加了耗時之前稚新，搜索結(jié)果并沒有明顯差別，實在是吃力不討好啊跪腹。
先來簡單分析一下褂删，螞蟻選擇路徑時，主要是依靠信息素濃度冲茸、啟發(fā)式值和alpha屯阀、beta之間的運算結(jié)果，結(jié)果越大的越容易被選中轴术。所以难衰，alpha、beta參數(shù)的設(shè)定膳音，信息素濃度召衔、啟發(fā)式值的計算，都會影響路徑的選擇祭陷。正常情況下，蟻群算法采用正反饋機制趣席，使得搜索過程不斷收斂兵志，最終逼近最優(yōu)解，而正反饋機制宣肚，實際上是通過信息素濃度來實現(xiàn)的想罕。我們先隨機抽取其中一次試驗的信息素來看看。
NODE pheromones
1 {2:0.0128} {3:0.0151} {4:0.0083} {5:0.0087} {6:0.0089} {7:0.0083} {8:0.0109} {9:0.0103} {10:0.0083} {11:0.0098} {12:0.0086} {13:0.0083} {14:0.0125} {15:0.0117} {16:0.0089} {17:0.0110} {18:0.0101} {19:0.0085} {20:0.0089} {21:0.0096} {22:1.2419} {23:0.0089} {24:0.0090} {25:0.0083} {26:0.0099} {27:0.0438} {28:0.0112}{29:0.0093} {30:0.0088} {31:0.0131} {32:1.2343} {33:0.0083} {34:0.0083} {35:0.0086} {36:0.0103} {37:0.0083} {38:0.0098} {39:0.0132} {40:0.0201} {41:0.0083} {42:0.0092}{43:0.0212} {44:0.0098} {45:0.0087} {46:0.0102} {47:0.0083} {48:0.0181} {49:0.0086} {50:0.0083} {51:0.0100}
2 {1:0.0128} {3:0.0260} {4:0.0165} {5:0.0148} {6:0.0110} {7:0.0087} {8:0.0100} {9:0.0258} {10:0.0156} {11:0.0222} {12:0.0093} {13:0.0122} {14:0.0161} {15:0.0133} {16:1.0576} {17:0.0174} {18:0.0173} {19:0.0083} {20:0.0280} {21:0.0122} {22:0.5342} {23:0.0083} {24:0.0125} {25:0.0144} {26:0.0122} {27:0.0145} {28:0.0114}{29:0.6710} {30:0.0176} {31:0.0221} {32:0.0150} {33:0.0092} {34:0.0089} {35:0.0116} {36:0.0220} {37:0.0110} {38:0.0095} {39:0.0144} {40:0.0550} {41:0.0114} {42:0.0134}{43:0.0375} {44:0.0084} {45:0.0084} {46:0.0248} {47:0.0105} {48:0.0115} {49:0.0288} {50:0.0090} {51:0.0117}
3 {1:0.0151} {2:0.0260} {4:0.0123} {5:0.0105} {6:0.0133} {7:0.0125} {8:0.0090} {9:0.0083} {10:0.0112} {11:0.0117} {12:0.0135} {13:0.0135} {14:0.0678} {15:0.0104} {16:0.0193} {17:0.0150} {18:0.0127} {19:0.0098} {20:0.9396} {21:0.0144} {22:0.0191} {23:0.0118} {24:0.0086} {25:0.0132} {26:0.0214} {27:0.0114} {28:0.6758}{29:0.0099} {30:0.0091} {31:0.1485} {32:0.0087} {33:0.0101} {34:0.0098} {35:0.0136} {36:0.5010} {37:0.0150} {38:0.0090} {39:0.0167} {40:0.0717} {41:0.0102} {42:0.0117}{43:0.0221} {44:0.0088} {45:0.0094} {46:0.0090} {47:0.0131} {48:0.0540} {49:0.0118} {50:0.0097} {51:0.0152}
4 {1:0.0083} {2:0.0165} {3:0.0123} {5:0.0112} {6:0.0098} {7:0.0083} {8:0.0092} {9:0.0083} {10:0.0083} {11:0.0084} {12:0.0099} {13:0.0175} {14:0.0095} {15:0.0088} {16:0.0090} {17:1.1505} {18:1.1923} {19:0.0126} {20:0.0105} {21:0.0106} {22:0.0084} {23:0.0084} {24:0.0085} {25:0.0136} {26:0.0085} {27:0.0092} {28:0.0083}{29:0.0083} {30:0.0083} {31:0.0084} {32:0.0083} {33:0.0083} {34:0.0083} {35:0.0104} {36:0.0141} {37:0.0118} {38:0.0083} {39:0.0085} {40:0.1676} {41:0.0208} {42:0.0127}{43:0.0109} {44:0.0094} {45:0.0089} {46:0.0096} {47:0.0320} {48:0.0085} {49:0.0084} {50:0.0083} {51:0.0087}
5 {1:0.0087} {2:0.0148} {3:0.0105} {4:0.0112} {6:0.0147} {7:0.0083} {8:0.0088} {9:0.0144} {10:0.0140} {11:0.0472} {12:0.1119} {13:0.0090} {14:0.0183} {15:0.0139} {16:0.0179} {17:0.0134} {18:0.0138} {19:0.0112} {20:0.0155} {21:0.0188} {22:0.0101} {23:0.0085} {24:0.0135} {25:0.0083} {26:0.0098} {27:0.0101} {28:0.0113}{29:0.0106} {30:0.0236} {31:0.0134} {32:0.0118} {33:0.0112} {34:0.0089} {35:0.0139} {36:0.0296} {37:0.0326} {38:1.1449} {39:0.0224} {40:0.1908} {41:0.0105} {42:0.0243}{43:0.0141} {44:0.0095} {45:0.0139} {46:0.0102} {47:0.0150} {48:0.0091} {49:0.8963} {50:0.0098} {51:0.0113}
6 {1:0.0089} {2:0.0110} {3:0.0133} {4:0.0098} {5:0.0147} {7:0.0111} {8:0.0099} {9:0.0083} {10:0.0085} {11:0.0095} {12:0.0092} {13:0.0092} {14:0.1515} {15:0.0085} {16:0.0096} {17:0.0085} {18:0.0151} {19:0.0085} {20:0.0129} {21:0.0083} {22:0.0130} {23:0.0232} {24:0.0128} {25:0.0099} {26:0.0098} {27:1.1193} {28:0.0102}{29:0.0086} {30:0.0115} {31:0.0107} {32:0.0098} {33:0.0084} {34:0.0130} {35:0.0128} {36:0.0105} {37:0.0090} {38:0.0083} {39:0.0130} {40:0.0225} {41:0.0083} {42:0.0088}{43:0.0433} {44:0.0090} {45:0.0086} {46:0.0107} {47:0.0108} {48:1.1907} {49:0.0106} {50:0.0083} {51:0.0136}
7 {1:0.0083} {2:0.0087} {3:0.0125} {4:0.0083} {5:0.0083} {6:0.0111} {8:0.0097} {9:0.0083} {10:0.0083} {11:0.0084} {12:0.0089} {13:0.0086} {14:0.0226} {15:0.0084} {16:0.0090} {17:0.0083} {18:0.0086} {19:0.0083} {20:0.0097} {21:0.0094} {22:0.0123} {23:1.2869} {24:0.0096} {25:0.0102} {26:1.1580} {27:0.0106} {28:0.0086}{29:0.0084} {30:0.0083} {31:0.0088} {32:0.0085} {33:0.0083} {34:0.0083} {35:0.0118} {36:0.0155} {37:0.0083} {38:0.0083} {39:0.0098} {40:0.0153} {41:0.0083} {42:0.0092}{43:0.1015} {44:0.0083} {45:0.0083} {46:0.0118} {47:0.0083} {48:0.0156} {49:0.0083} {50:0.0083} {51:0.0085}
8 {1:0.0109} {2:0.0100} {3:0.0090} {4:0.0092} {5:0.0088} {6:0.0099} {7:0.0097} {9:0.0083} {10:0.0084} {11:0.0085} {12:0.0084} {13:0.0085} {14:0.0115} {15:0.0083} {16:0.0085} {17:0.0083} {18:0.0091} {19:0.0084} {20:0.0086} {21:0.0086} {22:0.0154} {23:0.0095} {24:0.0106} {25:0.0087} {26:1.2362} {27:0.0103} {28:0.0123}{29:0.0085} {30:0.0083} {31:0.8345} {32:0.0087} {33:0.0090} {34:0.0083} {35:0.0083} {36:0.0108} {37:0.0083} {38:0.0083} {39:0.0106} {40:0.0183} {41:0.0085} {42:0.0083}{43:0.0130} {44:0.0086} {45:0.0084} {46:0.0099} {47:0.0085} {48:0.4887} {49:0.0084} {50:0.0087} {51:0.0084}
9 {1:0.0103} {2:0.0258} {3:0.0083} {4:0.0083} {5:0.0144} {6:0.0083} {7:0.0083} {8:0.0083} {10:0.0104} {11:0.0099} {12:0.0097} {13:0.0084} {14:0.0086} {15:0.0083} {16:0.0407} {17:0.0085} {18:0.0086} {19:0.0104} {20:0.0154} {21:0.2215} {22:0.0094} {23:0.0083} {24:0.0095} {25:0.0096} {26:0.0101} {27:0.0084} {28:0.0133}{29:0.0090} {30:0.0931} {31:0.0150} {32:0.0115} {33:0.0084} {34:0.0133} {35:0.0129} {36:0.0144} {37:0.0108} {38:0.0800} {39:0.0195} {40:0.0128} {41:0.0114} {42:0.0140}{43:0.0180} {44:0.0085} {45:0.0089} {46:0.0122} {47:0.0083} {48:0.0104} {49:1.2366} {50:0.8469} {51:0.0088}
10 {1:0.0083} {2:0.0156} {3:0.0112} {4:0.0083} {5:0.0140} {6:0.0085} {7:0.0083} {8:0.0084} {9:0.0104} {11:0.0087} {12:0.0083} {13:0.0105} {14:0.0117} {15:0.0095} {16:0.0107} {17:0.0093} {18:0.0105} {19:0.0085} {20:0.0140} {21:0.0094} {22:0.0083} {23:0.0097} {24:0.0084} {25:0.0094} {26:0.0083} {27:0.0084} {28:0.0084}{29:0.0086} {30:1.0156} {31:0.0101} {32:0.0083} {33:0.1005} {34:0.0139} {35:0.0110} {36:0.0163} {37:0.0088} {38:0.0100} {39:1.0896} {40:0.0155} {41:0.0083} {42:0.0095}{43:0.0116} {44:0.0096} {45:0.0131} {46:0.0097} {47:0.0084} {48:0.0088} {49:0.3354} {50:0.0092} {51:0.0084}
11 {1:0.0098} {2:0.0222} {3:0.0117} {4:0.0084} {5:0.0472} {6:0.0095} {7:0.0084} {8:0.0085} {9:0.0099} {10:0.0087} {12:0.0086} {13:0.0091} {14:0.0115} {15:0.0083} {16:0.0141} {17:0.0093} {18:0.0085} {19:0.0083} {20:0.0092} {21:0.0093} {22:0.0098} {23:0.0087} {24:0.0121} {25:0.0083} {26:0.0086} {27:0.0090} {28:0.0127}{29:0.0103} {30:0.0132} {31:0.0116} {32:1.2624} {33:0.0101} {34:0.0089} {35:0.0104} {36:0.0160} {37:0.0087} {38:1.1994} {39:0.0130} {40:0.0132} {41:0.0084} {42:0.0094}{43:0.0105} {44:0.0092} {45:0.0084} {46:0.0151} {47:0.0087} {48:0.0153} {49:0.0100} {50:0.0084} {51:0.0153}
12 {1:0.0086} {2:0.0093} {3:0.0135} {4:0.0099} {5:0.1119} {6:0.0092} {7:0.0089} {8:0.0084} {9:0.0097} {10:0.0083} {11:0.0086} {13:0.0142} {14:0.0086} {15:0.0090} {16:0.0095} {17:0.0140} {18:0.0109} {19:0.0086} {20:0.0083} {21:0.0084} {22:0.0084} {23:0.0083} {24:0.0083} {25:0.0084} {26:0.0086} {27:0.0094} {28:0.0083}{29:0.0118} {30:0.0104} {31:0.0102} {32:0.0084} {33:0.0083} {34:0.0095} {35:0.0106} {36:0.0110} {37:0.0193} {38:0.0091} {39:0.0091} {40:0.0188} {41:0.0087} {42:0.0099}{43:0.0103} {44:0.0087} {45:0.0095} {46:1.1515} {47:1.2702} {48:0.0083} {49:0.0086} {50:0.0083} {51:0.0173}
13 {1:0.0083} {2:0.0122} {3:0.0135} {4:0.0175} {5:0.0090} {6:0.0092} {7:0.0086} {8:0.0085} {9:0.0084} {10:0.0105} {11:0.0091} {12:0.0142} {14:0.0416} {15:0.0085} {16:0.0091} {17:0.0105} {18:0.0142} {19:0.0091} {20:0.0087} {21:0.0088} {22:0.0134} {23:0.0090} {24:0.0103} {25:1.1442} {26:0.0093} {27:0.0154} {28:0.0083}{29:0.0118} {30:0.0112} {31:0.0106} {32:0.0086} {33:0.0086} {34:0.0164} {35:0.0089} {36:0.0120} {37:0.0105} {38:0.0083} {39:0.0100} {40:0.1019} {41:1.2258} {42:0.0100}{43:0.0169} {44:0.0121} {45:0.0083} {46:0.0142} {47:0.0125} {48:0.0100} {49:0.0086} {50:0.0100} {51:0.0084}
14 {1:0.0125} {2:0.0161} {3:0.0678} {4:0.0095} {5:0.0183} {6:0.1515} {7:0.0226} {8:0.0115} {9:0.0086} {10:0.0117} {11:0.0115} {12:0.0086} {13:0.0416} {15:0.0083} {16:0.0120} {17:0.0116} {18:0.0389} {19:0.0105} {20:0.0258} {21:0.0084} {22:0.0264} {23:0.0089} {24:0.3895} {25:1.2991} {26:0.0113} {27:0.0129} {28:0.0146}{29:0.0134} {30:0.0122} {31:0.0195} {32:0.0084} {33:0.0083} {34:0.0110} {35:0.0324} {36:0.0260} {37:0.0086} {38:0.0130} {39:0.0097} {40:0.0977} {41:0.0103} {42:0.0101}{43:0.3529} {44:0.0099} {45:0.0130} {46:0.0147} {47:0.0099} {48:0.0268} {49:0.0093} {50:0.0083} {51:0.0102}
15 {1:0.0117} {2:0.0133} {3:0.0104} {4:0.0088} {5:0.0139} {6:0.0085} {7:0.0084} {8:0.0083} {9:0.0083} {10:0.0095} {11:0.0083} {12:0.0090} {13:0.0085} {14:0.0083} {16:0.0100} {17:0.0200} {18:0.0103} {19:0.0083} {20:0.0084} {21:0.0139} {22:0.0083} {23:0.0083} {24:0.0083} {25:0.0086} {26:0.0083} {27:0.0083} {28:0.0083}{29:0.0088} {30:0.0114} {31:0.0109} {32:0.0084} {33:0.0126} {34:0.0110} {35:0.0091} {36:0.0124} {37:0.0268} {38:0.0098} {39:0.0109} {40:0.0269} {41:0.0104} {42:0.0139}{43:0.0112} {44:1.2513} {45:1.2414} {46:0.0098} {47:0.0093} {48:0.0086} {49:0.0098} {50:0.0083} {51:0.0083}
16 {1:0.0089} {2:1.0576} {3:0.0193} {4:0.0090} {5:0.0179} {6:0.0096} {7:0.0090} {8:0.0085} {9:0.0407} {10:0.0107} {11:0.0141} {12:0.0095} {13:0.0091} {14:0.0120} {15:0.0100} {17:0.0103} {18:0.0121} {19:0.0086} {20:0.0758} {21:0.3638} {22:0.0105} {23:0.0083} {24:0.0083} {25:0.0094} {26:0.0115} {27:0.0127} {28:0.0110}{29:0.0349} {30:0.0785} {31:0.0169} {32:0.0113} {33:0.0087} {34:0.0110} {35:0.0111} {36:0.0257} {37:0.0105} {38:0.0333} {39:0.0121} {40:0.0161} {41:0.0123} {42:0.0122}{43:0.0128} {44:0.0092} {45:0.0084} {46:0.0093} {47:0.0089} {48:0.0125} {49:0.0175} {50:0.8344} {51:0.0094}
17 {1:0.0110} {2:0.0174} {3:0.0150} {4:1.1505} {5:0.0134} {6:0.0085} {7:0.0083} {8:0.0083} {9:0.0085} {10:0.0093} {11:0.0093} {12:0.0140} {13:0.0105} {14:0.0116} {15:0.0200} {16:0.0103} {18:0.0138} {19:0.0116} {20:0.0092} {21:0.0124} {22:0.0118} {23:0.0083} {24:0.0084} {25:0.0089} {26:0.0083} {27:0.0105} {28:0.0117}{29:0.0083} {30:0.0086} {31:0.0090} {32:0.0083} {33:0.0101} {34:0.0109} {35:0.0144} {36:0.0120} {37:1.2927} {38:0.0087} {39:0.0119} {40:0.0132} {41:0.0092} {42:0.0138}{43:0.0229} {44:0.0296} {45:0.0088} {46:0.0088} {47:0.0210} {48:0.0100} {49:0.0143} {50:0.0096} {51:0.0087}
18 {1:0.0101} {2:0.0173} {3:0.0127} {4:1.1923} {5:0.0138} {6:0.0151} {7:0.0086} {8:0.0091} {9:0.0086} {10:0.0105} {11:0.0085} {12:0.0109} {13:0.0142} {14:0.0389} {15:0.0103} {16:0.0121} {17:0.0138} {19:0.0084} {20:0.0115} {21:0.0094} {22:0.0096} {23:0.0086} {24:0.0134} {25:0.0502} {26:0.0087} {27:0.0115} {28:0.0090}{29:0.0083} {30:0.0085} {31:0.0093} {32:0.0092} {33:0.0090} {34:0.0083} {35:0.0085} {36:0.0199} {37:0.0096} {38:0.0103} {39:0.0111} {40:0.0244} {41:0.0093} {42:0.0109}{43:0.0223} {44:0.0085} {45:0.0086} {46:0.0114} {47:1.2087} {48:0.0128} {49:0.0088} {50:0.0099} {51:0.0105}
19 {1:0.0085} {2:0.0083} {3:0.0098} {4:0.0126} {5:0.0112} {6:0.0085} {7:0.0083} {8:0.0084} {9:0.0104} {10:0.0085} {11:0.0083} {12:0.0086} {13:0.0091} {14:0.0105} {15:0.0083} {16:0.0086} {17:0.0116} {18:0.0084} {20:0.0083} {21:0.0083} {22:0.0096} {23:0.0083} {24:0.0088} {25:0.0085} {26:0.0084} {27:0.0083} {28:0.0092}{29:0.0087} {30:0.0095} {31:0.0083} {32:0.0083} {33:0.0084} {34:0.0109} {35:0.0164} {36:0.0095} {37:0.0123} {38:0.0083} {39:0.0108} {40:0.0219} {41:1.2981} {42:1.2429}{43:0.0109} {44:0.0091} {45:0.0098} {46:0.0115} {47:0.0087} {48:0.0085} {49:0.0104} {50:0.0083} {51:0.0086}
20 {1:0.0089} {2:0.0280} {3:0.9396} {4:0.0105} {5:0.0155} {6:0.0129} {7:0.0097} {8:0.0086} {9:0.0154} {10:0.0140} {11:0.0092} {12:0.0083} {13:0.0087} {14:0.0258} {15:0.0084} {16:0.0758} {17:0.0092} {18:0.0115} {19:0.0083} {21:0.0927} {22:0.0211} {23:0.0083} {24:0.0137} {25:0.0083} {26:0.0151} {27:0.0114} {28:0.0109}{29:0.2476} {30:0.0118} {31:0.0101} {32:0.0145} {33:0.0097} {34:0.0163} {35:1.0772} {36:0.0147} {37:0.0120} {38:0.0109} {39:0.0100} {40:0.0367} {41:0.0117} {42:0.0133}{43:0.0155} {44:0.0103} {45:0.0083} {46:0.0103} {47:0.0101} {48:0.0150} {49:0.0109} {50:0.0083} {51:0.0108}
21 {1:0.0096} {2:0.0122} {3:0.0144} {4:0.0106} {5:0.0188} {6:0.0083} {7:0.0094} {8:0.0086} {9:0.2215} {10:0.0094} {11:0.0093} {12:0.0084} {13:0.0088} {14:0.0084} {15:0.0139} {16:0.3638} {17:0.0124} {18:0.0094} {19:0.0083} {20:0.0927} {22:0.0116} {23:0.0090} {24:0.0090} {25:0.0083} {26:0.0095} {27:0.0106} {28:0.0105}{29:1.2625} {30:0.0167} {31:0.0128} {32:0.0084} {33:0.0090} {34:0.5027} {35:0.0136} {36:0.0318} {37:0.0093} {38:0.0125} {39:0.0353} {40:0.0218} {41:0.0085} {42:0.0122}{43:0.0101} {44:0.0085} {45:0.0137} {46:0.0084} {47:0.0083} {48:0.0121} {49:0.0168} {50:0.0350} {51:0.0087}
22 {1:1.2419} {2:0.5342} {3:0.0191} {4:0.0084} {5:0.0101} {6:0.0130} {7:0.0123} {8:0.0154} {9:0.0094} {10:0.0083} {11:0.0098} {12:0.0084} {13:0.0134} {14:0.0264} {15:0.0083} {16:0.0105} {17:0.0118} {18:0.0096} {19:0.0096} {20:0.0211} {21:0.0116} {23:0.0086} {24:0.0136} {25:0.0122} {26:0.0111} {27:0.0129} {28:0.5343}{29:0.0169} {30:0.0112} {31:0.0387} {32:0.0127} {33:0.0084} {34:0.0085} {35:0.0109} {36:0.0969} {37:0.0083} {38:0.0091} {39:0.0121} {40:0.0239} {41:0.0125} {42:0.0102}{43:0.0298} {44:0.0085} {45:0.0091} {46:0.0095} {47:0.0091} {48:0.0270} {49:0.0083} {50:0.0096} {51:0.0087}
23 {1:0.0089} {2:0.0083} {3:0.0118} {4:0.0084} {5:0.0085} {6:0.0232} {7:1.2869} {8:0.0095} {9:0.0083} {10:0.0097} {11:0.0087} {12:0.0083} {13:0.0090} {14:0.0089} {15:0.0083} {16:0.0083} {17:0.0083} {18:0.0086} {19:0.0083} {20:0.0083} {21:0.0090} {22:0.0086} {24:1.1093} {25:0.0090} {26:0.0106} {27:0.0091} {28:0.0084}{29:0.0113} {30:0.0093} {31:0.0093} {32:0.0083} {33:0.0084} {34:0.0083} {35:0.0100} {36:0.0136} {37:0.0083} {38:0.0083} {39:0.0115} {40:0.0157} {41:0.0083} {42:0.0095}{43:0.0122} {44:0.0092} {45:0.0092} {46:0.0102} {47:0.0089} {48:0.1532} {49:0.0130} {50:0.0083} {51:0.0091}
24 {1:0.0090} {2:0.0125} {3:0.0086} {4:0.0085} {5:0.0135} {6:0.0128} {7:0.0096} {8:0.0106} {9:0.0095} {10:0.0084} {11:0.0121} {12:0.0083} {13:0.0103} {14:0.3895} {15:0.0083} {16:0.0083} {17:0.0084} {18:0.0134} {19:0.0088} {20:0.0137} {21:0.0090} {22:0.0136} {23:1.1093} {25:0.0222} {26:0.0109} {27:0.0120} {28:0.0094}{29:0.0094} {30:0.0086} {31:0.0084} {32:0.0086} {33:0.0086} {34:0.0105} {35:0.0097} {36:0.0099} {37:0.0083} {38:0.0100} {39:0.0128} {40:0.0237} {41:0.0084} {42:0.0092}{43:1.0109} {44:0.0125} {45:0.0093} {46:0.0085} {47:0.0098} {48:0.0100} {49:0.0108} {50:0.0083} {51:0.0083}
25 {1:0.0083} {2:0.0144} {3:0.0132} {4:0.0136} {5:0.0083} {6:0.0099} {7:0.0102} {8:0.0087} {9:0.0096} {10:0.0094} {11:0.0083} {12:0.0084} {13:1.1442} {14:1.2991} {15:0.0086} {16:0.0094} {17:0.0089} {18:0.0502} {19:0.0085} {20:0.0083} {21:0.0083} {22:0.0122} {23:0.0090} {24:0.0222} {26:0.0129} {27:0.0108} {28:0.0083}{29:0.0149} {30:0.0083} {31:0.0083} {32:0.0143} {33:0.0103} {34:0.0095} {35:0.0119} {36:0.0120} {37:0.0087} {38:0.0087} {39:0.0123} {40:0.0218} {41:0.0107} {42:0.0103}{43:0.0152} {44:0.0083} {45:0.0085} {46:0.0118} {47:0.0117} {48:0.0145} {49:0.0083} {50:0.0105} {51:0.0116}
26 {1:0.0099} {2:0.0122} {3:0.0214} {4:0.0085} {5:0.0098} {6:0.0098} {7:1.1580} {8:1.2362} {9:0.0101} {10:0.0083} {11:0.0086} {12:0.0086} {13:0.0093} {14:0.0113} {15:0.0083} {16:0.0115} {17:0.0083} {18:0.0087} {19:0.0084} {20:0.0151} {21:0.0095} {22:0.0111} {23:0.0106} {24:0.0109} {25:0.0129} {27:0.0087} {28:0.0093}{29:0.0131} {30:0.0099} {31:0.0800} {32:0.0098} {33:0.0087} {34:0.0085} {35:0.0156} {36:0.0131} {37:0.0083} {38:0.0083} {39:0.0087} {40:0.0180} {41:0.0142} {42:0.0086}{43:0.0429} {44:0.0084} {45:0.0111} {46:0.0092} {47:0.0083} {48:0.0187} {49:0.0083} {50:0.0103} {51:0.0083}
27 {1:0.0438} {2:0.0145} {3:0.0114} {4:0.0092} {5:0.0101} {6:1.1193} {7:0.0106} {8:0.0103} {9:0.0084} {10:0.0084} {11:0.0090} {12:0.0094} {13:0.0154} {14:0.0129} {15:0.0083} {16:0.0127} {17:0.0105} {18:0.0115} {19:0.0083} {20:0.0114} {21:0.0106} {22:0.0129} {23:0.0091} {24:0.0120} {25:0.0108} {26:0.0087} {28:0.0103}{29:0.0094} {30:0.0083} {31:0.0122} {32:0.0327} {33:0.0087} {34:0.0088} {35:0.0122} {36:0.0172} {37:0.0097} {38:0.0089} {39:0.0103} {40:0.0259} {41:0.0086} {42:0.0084}{43:0.0122} {44:0.0088} {45:0.0091} {46:0.0200} {47:0.0094} {48:0.1040} {49:0.0087} {50:0.0083} {51:1.2139}
28 {1:0.0112} {2:0.0114} {3:0.6758} {4:0.0083} {5:0.0113} {6:0.0102} {7:0.0086} {8:0.0123} {9:0.0133} {10:0.0084} {11:0.0127} {12:0.0083} {13:0.0083} {14:0.0146} {15:0.0083} {16:0.0110} {17:0.0117} {18:0.0090} {19:0.0092} {20:0.0109} {21:0.0105} {22:0.5343} {23:0.0084} {24:0.0094} {25:0.0083} {26:0.0093} {27:0.0103}{29:0.0088} {30:0.0099} {31:1.2946} {32:0.0083} {33:0.0083} {34:0.0108} {35:0.0176} {36:0.0275} {37:0.0088} {38:0.0083} {39:0.0096} {40:0.0245} {41:0.0089} {42:0.0089}{43:0.0169} {44:0.0084} {45:0.0085} {46:0.0095} {47:0.0085} {48:0.0087} {49:0.0083} {50:0.0087} {51:0.0084}
29 {1:0.0093} {2:0.6710} {3:0.0099} {4:0.0083} {5:0.0106} {6:0.0086} {7:0.0084} {8:0.0085} {9:0.0090} {10:0.0086} {11:0.0103} {12:0.0118} {13:0.0118} {14:0.0134} {15:0.0088} {16:0.0349} {17:0.0083} {18:0.0083} {19:0.0087} {20:0.2476} {21:1.2625} {22:0.0169} {23:0.0113} {24:0.0094} {25:0.0149} {26:0.0131} {27:0.0094}{28:0.0088} {30:0.0111} {31:0.0109} {32:0.0083} {33:0.0092} {34:0.0092} {35:0.0139} {36:0.3085} {37:0.0083} {38:0.0086} {39:0.0134} {40:0.0232} {41:0.0111} {42:0.0192}{43:0.0108} {44:0.0086} {45:0.0111} {46:0.0096} {47:0.0089} {48:0.0089} {49:0.0129} {50:0.0092} {51:0.0083}
30 {1:0.0088} {2:0.0176} {3:0.0091} {4:0.0083} {5:0.0236} {6:0.0115} {7:0.0083} {8:0.0083} {9:0.0931} {10:1.0156} {11:0.0132} {12:0.0104} {13:0.0112} {14:0.0122} {15:0.0114} {16:0.0785} {17:0.0086} {18:0.0085} {19:0.0095} {20:0.0118} {21:0.0167} {22:0.0112} {23:0.0093} {24:0.0086} {25:0.0083} {26:0.0099} {27:0.0083}{28:0.0099} {29:0.0111} {31:0.0177} {32:0.0084} {33:0.0134} {34:1.1570} {35:0.0125} {36:0.0224} {37:0.0083} {38:0.0777} {39:0.0752} {40:0.0239} {41:0.0083} {42:0.0123}{43:0.0095} {44:0.0094} {45:0.0114} {46:0.0083} {47:0.0083} {48:0.0083} {49:0.0203} {50:0.0102} {51:0.0097}
31 {1:0.0131} {2:0.0221} {3:0.1485} {4:0.0084} {5:0.0134} {6:0.0107} {7:0.0088} {8:0.8345} {9:0.0150} {10:0.0101} {11:0.0116} {12:0.0102} {13:0.0106} {14:0.0195} {15:0.0109} {16:0.0169} {17:0.0090} {18:0.0093} {19:0.0083} {20:0.0101} {21:0.0128} {22:0.0387} {23:0.0093} {24:0.0084} {25:0.0083} {26:0.0800} {27:0.0122}{28:1.2946} {29:0.0109} {30:0.0177} {32:0.0106} {33:0.0121} {34:0.0100} {35:0.0208} {36:0.0241} {37:0.0118} {38:0.0170} {39:0.0195} {40:0.0254} {41:0.0124} {42:0.0089}{43:0.0618} {44:0.0083} {45:0.0122} {46:0.0110} {47:0.0088} {48:0.0111} {49:0.0083} {50:0.0083} {51:0.0093}
32 {1:1.2343} {2:0.0150} {3:0.0087} {4:0.0083} {5:0.0118} {6:0.0098} {7:0.0085} {8:0.0087} {9:0.0115} {10:0.0083} {11:1.2624} {12:0.0084} {13:0.0086} {14:0.0084} {15:0.0084} {16:0.0113} {17:0.0083} {18:0.0092} {19:0.0083} {20:0.0145} {21:0.0084} {22:0.0127} {23:0.0083} {24:0.0086} {25:0.0143} {26:0.0098} {27:0.0327}{28:0.0083} {29:0.0083} {30:0.0084} {31:0.0106} {33:0.0097} {34:0.0088} {35:0.0104} {36:0.0083} {37:0.0084} {38:0.0112} {39:0.0095} {40:0.0191} {41:0.0083} {42:0.0114}{43:0.0171} {44:0.0083} {45:0.0085} {46:0.0145} {47:0.0106} {48:0.0107} {49:0.0088} {50:0.0085} {51:0.0103}
33 {1:0.0083} {2:0.0092} {3:0.0101} {4:0.0083} {5:0.0112} {6:0.0084} {7:0.0083} {8:0.0090} {9:0.0084} {10:0.1005} {11:0.0101} {12:0.0083} {13:0.0086} {14:0.0083} {15:0.0126} {16:0.0087} {17:0.0101} {18:0.0090} {19:0.0084} {20:0.0097} {21:0.0090} {22:0.0084} {23:0.0084} {24:0.0086} {25:0.0103} {26:0.0087} {27:0.0087}{28:0.0083} {29:0.0092} {30:0.0134} {31:0.0121} {32:0.0097} {34:0.0088} {35:0.0084} {36:0.0086} {37:0.0100} {38:0.0086} {39:1.1508} {40:0.0162} {41:0.0094} {42:0.0262}{43:0.0132} {44:0.0109} {45:1.2843} {46:0.0084} {47:0.0083} {48:0.0111} {49:0.0150} {50:0.0085} {51:0.0086}
34 {1:0.0083} {2:0.0089} {3:0.0098} {4:0.0083} {5:0.0089} {6:0.0130} {7:0.0083} {8:0.0083} {9:0.0133} {10:0.0139} {11:0.0089} {12:0.0095} {13:0.0164} {14:0.0110} {15:0.0110} {16:0.0110} {17:0.0109} {18:0.0083} {19:0.0109} {20:0.0163} {21:0.5027} {22:0.0085} {23:0.0083} {24:0.0105} {25:0.0095} {26:0.0085} {27:0.0088}{28:0.0108} {29:0.0092} {30:1.1570} {31:0.0100} {32:0.0088} {33:0.0088} {35:0.0084} {36:0.0143} {37:0.0101} {38:0.0137} {39:0.0155} {40:0.0099} {41:0.0083} {42:0.0085}{43:0.0119} {44:0.0144} {45:0.0088} {46:0.0090} {47:0.0119} {48:0.0084} {49:0.0097} {50:0.8574} {51:0.0086}
35 {1:0.0086} {2:0.0116} {3:0.0136} {4:0.0104} {5:0.0139} {6:0.0128} {7:0.0118} {8:0.0083} {9:0.0129} {10:0.0110} {11:0.0104} {12:0.0106} {13:0.0089} {14:0.0324} {15:0.0091} {16:0.0111} {17:0.0144} {18:0.0085} {19:0.0164} {20:1.0772} {21:0.0136} {22:0.0109} {23:0.0100} {24:0.0097} {25:0.0119} {26:0.0156} {27:0.0122}{28:0.0176} {29:0.0139} {30:0.0125} {31:0.0208} {32:0.0104} {33:0.0084} {34:0.0084} {36:1.2952} {37:0.0083} {38:0.0135} {39:0.0173} {40:0.0589} {41:0.0083} {42:0.0162}{43:0.0168} {44:0.0084} {45:0.0097} {46:0.0097} {47:0.0085} {48:0.0161} {49:0.0083} {50:0.0086} {51:0.0118}
36 {1:0.0103} {2:0.0220} {3:0.5010} {4:0.0141} {5:0.0296} {6:0.0105} {7:0.0155} {8:0.0108} {9:0.0144} {10:0.0163} {11:0.0160} {12:0.0110} {13:0.0120} {14:0.0260} {15:0.0124} {16:0.0257} {17:0.0120} {18:0.0199} {19:0.0095} {20:0.0147} {21:0.0318} {22:0.0969} {23:0.0136} {24:0.0099} {25:0.0120} {26:0.0131} {27:0.0172}{28:0.0275} {29:0.3085} {30:0.0224} {31:0.0241} {32:0.0083} {33:0.0086} {34:0.0143} {35:1.2952} {37:0.0118} {38:0.0118} {39:0.0269} {40:0.0763} {41:0.0131} {42:0.0149}{43:0.0393} {44:0.0116} {45:0.0083} {46:0.0088} {47:0.0103} {48:0.0167} {49:0.0237} {50:0.0116} {51:0.0134}
37 {1:0.0083} {2:0.0110} {3:0.0150} {4:0.0118} {5:0.0326} {6:0.0090} {7:0.0083} {8:0.0083} {9:0.0108} {10:0.0088} {11:0.0087} {12:0.0193} {13:0.0105} {14:0.0086} {15:0.0268} {16:0.0105} {17:1.2927} {18:0.0096} {19:0.0123} {20:0.0120} {21:0.0093} {22:0.0083} {23:0.0083} {24:0.0083} {25:0.0087} {26:0.0083} {27:0.0097}{28:0.0088} {29:0.0083} {30:0.0083} {31:0.0118} {32:0.0084} {33:0.0100} {34:0.0101} {35:0.0083} {36:0.0118} {38:0.0084} {39:0.0183} {40:0.0377} {41:0.0096} {42:0.0119}{43:0.0104} {44:1.1586} {45:0.0088} {46:0.0133} {47:0.0096} {48:0.0086} {49:0.0110} {50:0.0083} {51:0.0094}
38 {1:0.0098} {2:0.0095} {3:0.0090} {4:0.0083} {5:1.1449} {6:0.0083} {7:0.0083} {8:0.0083} {9:0.0800} {10:0.0100} {11:1.1994} {12:0.0091} {13:0.0083} {14:0.0130} {15:0.0098} {16:0.0333} {17:0.0087} {18:0.0103} {19:0.0083} {20:0.0109} {21:0.0125} {22:0.0091} {23:0.0083} {24:0.0100} {25:0.0087} {26:0.0083} {27:0.0089}{28:0.0083} {29:0.0086} {30:0.0777} {31:0.0170} {32:0.0112} {33:0.0086} {34:0.0137} {35:0.0135} {36:0.0118} {37:0.0084} {39:0.0205} {40:0.0154} {41:0.0083} {42:0.0115}{43:0.0106} {44:0.0083} {45:0.0085} {46:0.0136} {47:0.0083} {48:0.0091} {49:0.0172} {50:0.0132} {51:0.0090}
39 {1:0.0132} {2:0.0144} {3:0.0167} {4:0.0085} {5:0.0224} {6:0.0130} {7:0.0098} {8:0.0106} {9:0.0195} {10:1.0896} {11:0.0130} {12:0.0091} {13:0.0100} {14:0.0097} {15:0.0109} {16:0.0121} {17:0.0119} {18:0.0111} {19:0.0108} {20:0.0100} {21:0.0353} {22:0.0121} {23:0.0115} {24:0.0128} {25:0.0123} {26:0.0087} {27:0.0103}{28:0.0096} {29:0.0134} {30:0.0752} {31:0.0195} {32:0.0095} {33:1.1508} {34:0.0155} {35:0.0173} {36:0.0269} {37:0.0183} {38:0.0205} {40:0.0581} {41:0.0103} {42:0.0229}{43:0.0165} {44:0.0111} {45:0.0131} {46:0.0175} {47:0.0116} {48:0.0110} {49:0.0094} {50:0.0094} {51:0.0086}
40 {1:0.0201} {2:0.0550} {3:0.0717} {4:0.1676} {5:0.1908} {6:0.0225} {7:0.0153} {8:0.0183} {9:0.0128} {10:0.0155} {11:0.0132} {12:0.0188} {13:0.1019} {14:0.0977} {15:0.0269} {16:0.0161} {17:0.0132} {18:0.0244} {19:0.0219} {20:0.0367} {21:0.0218} {22:0.0239} {23:0.0157} {24:0.0237} {25:0.0218} {26:0.0180} {27:0.0259}{28:0.0245} {29:0.0232} {30:0.0239} {31:0.0254} {32:0.0191} {33:0.0162} {34:0.0099} {35:0.0589} {36:0.0763} {37:0.0377} {38:0.0154} {39:0.0581} {41:0.0165} {42:1.0846}{43:0.2616} {44:0.0181} {45:0.0164} {46:0.0201} {47:0.0320} {48:0.0159} {49:0.0147} {50:0.0136} {51:0.0117}
41 {1:0.0083} {2:0.0114} {3:0.0102} {4:0.0208} {5:0.0105} {6:0.0083} {7:0.0083} {8:0.0085} {9:0.0114} {10:0.0083} {11:0.0084} {12:0.0087} {13:1.2258} {14:0.0103} {15:0.0104} {16:0.0123} {17:0.0092} {18:0.0093} {19:1.2981} {20:0.0117} {21:0.0085} {22:0.0125} {23:0.0083} {24:0.0084} {25:0.0107} {26:0.0142} {27:0.0086}{28:0.0089} {29:0.0111} {30:0.0083} {31:0.0124} {32:0.0083} {33:0.0094} {34:0.0083} {35:0.0083} {36:0.0131} {37:0.0096} {38:0.0083} {39:0.0103} {40:0.0165} {42:0.0103}{43:0.0106} {44:0.0085} {45:0.0083} {46:0.0088} {47:0.0092} {48:0.0088} {49:0.0105} {50:0.0083} {51:0.0083}
42 {1:0.0092} {2:0.0134} {3:0.0117} {4:0.0127} {5:0.0243} {6:0.0088} {7:0.0092} {8:0.0083} {9:0.0140} {10:0.0095} {11:0.0094} {12:0.0099} {13:0.0100} {14:0.0101} {15:0.0139} {16:0.0122} {17:0.0138} {18:0.0109} {19:1.2429} {20:0.0133} {21:0.0122} {22:0.0102} {23:0.0095} {24:0.0092} {25:0.0103} {26:0.0086} {27:0.0084}{28:0.0089} {29:0.0192} {30:0.0123} {31:0.0089} {32:0.0114} {33:0.0262} {34:0.0085} {35:0.0162} {36:0.0149} {37:0.0119} {38:0.0115} {39:0.0229} {40:1.0846} {41:0.0103}{43:0.0154} {44:0.1213} {45:0.0109} {46:0.0093} {47:0.0090} {48:0.0086} {49:0.0086} {50:0.0084} {51:0.0105}
43 {1:0.0212} {2:0.0375} {3:0.0221} {4:0.0109} {5:0.0141} {6:0.0433} {7:0.1015} {8:0.0130} {9:0.0180} {10:0.0116} {11:0.0105} {12:0.0103} {13:0.0169} {14:0.3529} {15:0.0112} {16:0.0128} {17:0.0229} {18:0.0223} {19:0.0109} {20:0.0155} {21:0.0101} {22:0.0298} {23:0.0122} {24:1.0109} {25:0.0152} {26:0.0429} {27:0.0122}{28:0.0169} {29:0.0108} {30:0.0095} {31:0.0618} {32:0.0171} {33:0.0132} {34:0.0119} {35:0.0168} {36:0.0393} {37:0.0104} {38:0.0106} {39:0.0165} {40:0.2616} {41:0.0106}{42:0.0154} {44:0.0114} {45:0.0114} {46:0.0145} {47:0.0128} {48:0.4875} {49:0.0084} {50:0.0136} {51:0.0103}
44 {1:0.0098} {2:0.0084} {3:0.0088} {4:0.0094} {5:0.0095} {6:0.0090} {7:0.0083} {8:0.0086} {9:0.0085} {10:0.0096} {11:0.0092} {12:0.0087} {13:0.0121} {14:0.0099} {15:1.2513} {16:0.0092} {17:0.0296} {18:0.0085} {19:0.0091} {20:0.0103} {21:0.0085} {22:0.0085} {23:0.0092} {24:0.0125} {25:0.0083} {26:0.0084} {27:0.0088}{28:0.0084} {29:0.0086} {30:0.0094} {31:0.0083} {32:0.0083} {33:0.0109} {34:0.0144} {35:0.0084} {36:0.0116} {37:1.1586} {38:0.0083} {39:0.0111} {40:0.0181} {41:0.0085}{42:0.1213} {43:0.0114} {45:0.0163} {46:0.0086} {47:0.0091} {48:0.0083} {49:0.0088} {50:0.0083} {51:0.0087}
45 {1:0.0087} {2:0.0084} {3:0.0094} {4:0.0089} {5:0.0139} {6:0.0086} {7:0.0083} {8:0.0084} {9:0.0089} {10:0.0131} {11:0.0084} {12:0.0095} {13:0.0083} {14:0.0130} {15:1.2414} {16:0.0084} {17:0.0088} {18:0.0086} {19:0.0098} {20:0.0083} {21:0.0137} {22:0.0091} {23:0.0092} {24:0.0093} {25:0.0085} {26:0.0111} {27:0.0091}{28:0.0085} {29:0.0111} {30:0.0114} {31:0.0122} {32:0.0085} {33:1.2843} {34:0.0088} {35:0.0097} {36:0.0083} {37:0.0088} {38:0.0085} {39:0.0131} {40:0.0164} {41:0.0083}{42:0.0109} {43:0.0114} {44:0.0163} {46:0.0089} {47:0.0093} {48:0.0084} {49:0.0110} {50:0.0121} {51:0.0084}
46 {1:0.0102} {2:0.0248} {3:0.0090} {4:0.0096} {5:0.0102} {6:0.0107} {7:0.0118} {8:0.0099} {9:0.0122} {10:0.0097} {11:0.0151} {12:1.1515} {13:0.0142} {14:0.0147} {15:0.0098} {16:0.0093} {17:0.0088} {18:0.0114} {19:0.0115} {20:0.0103} {21:0.0084} {22:0.0095} {23:0.0102} {24:0.0085} {25:0.0118} {26:0.0092} {27:0.0200}{28:0.0095} {29:0.0096} {30:0.0083} {31:0.0110} {32:0.0145} {33:0.0084} {34:0.0090} {35:0.0097} {36:0.0088} {37:0.0133} {38:0.0136} {39:0.0175} {40:0.0201} {41:0.0088}{42:0.0093} {43:0.0145} {44:0.0086} {45:0.0089} {47:0.0105} {48:0.0150} {49:0.0118} {50:0.0083} {51:1.3039}
47 {1:0.0083} {2:0.0105} {3:0.0131} {4:0.0320} {5:0.0150} {6:0.0108} {7:0.0083} {8:0.0085} {9:0.0083} {10:0.0084} {11:0.0087} {12:1.2702} {13:0.0125} {14:0.0099} {15:0.0093} {16:0.0089} {17:0.0210} {18:1.2087} {19:0.0087} {20:0.0101} {21:0.0083} {22:0.0091} {23:0.0089} {24:0.0098} {25:0.0117} {26:0.0083} {27:0.0094}{28:0.0085} {29:0.0089} {30:0.0083} {31:0.0088} {32:0.0106} {33:0.0083} {34:0.0119} {35:0.0085} {36:0.0103} {37:0.0096} {38:0.0083} {39:0.0116} {40:0.0320} {41:0.0092}{42:0.0090} {43:0.0128} {44:0.0091} {45:0.0093} {46:0.0105} {48:0.0086} {49:0.0087} {50:0.0092} {51:0.0168}
48 {1:0.0181} {2:0.0115} {3:0.0540} {4:0.0085} {5:0.0091} {6:1.1907} {7:0.0156} {8:0.4887} {9:0.0104} {10:0.0088} {11:0.0153} {12:0.0083} {13:0.0100} {14:0.0268} {15:0.0086} {16:0.0125} {17:0.0100} {18:0.0128} {19:0.0085} {20:0.0150} {21:0.0121} {22:0.0270} {23:0.1532} {24:0.0100} {25:0.0145} {26:0.0187} {27:0.1040}{28:0.0087} {29:0.0089} {30:0.0083} {31:0.0111} {32:0.0107} {33:0.0111} {34:0.0084} {35:0.0161} {36:0.0167} {37:0.0086} {38:0.0091} {39:0.0110} {40:0.0159} {41:0.0088}{42:0.0086} {43:0.4875} {44:0.0083} {45:0.0084} {46:0.0150} {47:0.0086} {49:0.0110} {50:0.0084} {51:0.0133}
49 {1:0.0086} {2:0.0288} {3:0.0118} {4:0.0084} {5:0.8963} {6:0.0106} {7:0.0083} {8:0.0084} {9:1.2366} {10:0.3354} {11:0.0100} {12:0.0086} {13:0.0086} {14:0.0093} {15:0.0098} {16:0.0175} {17:0.0143} {18:0.0088} {19:0.0104} {20:0.0109} {21:0.0168} {22:0.0083} {23:0.0130} {24:0.0108} {25:0.0083} {26:0.0083} {27:0.0087}{28:0.0083} {29:0.0129} {30:0.0203} {31:0.0083} {32:0.0088} {33:0.0150} {34:0.0097} {35:0.0083} {36:0.0237} {37:0.0110} {38:0.0172} {39:0.0094} {40:0.0147} {41:0.0105}{42:0.0086} {43:0.0084} {44:0.0088} {45:0.0110} {46:0.0118} {47:0.0087} {48:0.0110} {50:0.0149} {51:0.0088}
50 {1:0.0083} {2:0.0090} {3:0.0097} {4:0.0083} {5:0.0098} {6:0.0083} {7:0.0083} {8:0.0087} {9:0.8469} {10:0.0092} {11:0.0084} {12:0.0083} {13:0.0100} {14:0.0083} {15:0.0083} {16:0.8344} {17:0.0096} {18:0.0099} {19:0.0083} {20:0.0083} {21:0.0350} {22:0.0096} {23:0.0083} {24:0.0083} {25:0.0105} {26:0.0103} {27:0.0083}{28:0.0087} {29:0.0092} {30:0.0102} {31:0.0083} {32:0.0085} {33:0.0085} {34:0.8574} {35:0.0086} {36:0.0116} {37:0.0083} {38:0.0132} {39:0.0094} {40:0.0136} {41:0.0083}{42:0.0084} {43:0.0136} {44:0.0083} {45:0.0121} {46:0.0083} {47:0.0092} {48:0.0084} {49:0.0149} {51:0.0083}
51 {1:0.0100} {2:0.0117} {3:0.0152} {4:0.0087} {5:0.0113} {6:0.0136} {7:0.0085} {8:0.0084} {9:0.0088} {10:0.0084} {11:0.0153} {12:0.0173} {13:0.0084} {14:0.0102} {15:0.0083} {16:0.0094} {17:0.0087} {18:0.0105} {19:0.0086} {20:0.0108} {21:0.0087} {22:0.0087} {23:0.0091} {24:0.0083} {25:0.0116} {26:0.0083} {27:1.2139}{28:0.0084} {29:0.0083} {30:0.0097} {31:0.0093} {32:0.0103} {33:0.0086} {34:0.0086} {35:0.0118} {36:0.0134} {37:0.0094} {38:0.0090} {39:0.0086} {40:0.0117} {41:0.0083}{42:0.0105} {43:0.0103} {44:0.0087} {45:0.0084} {46:1.3039} {47:0.0168} {48:0.0133} {49:0.0088} {50:0.0083}
當(dāng)前循環(huán)次數(shù)：40
從上面結(jié)果可以看出霉涨，大部分路徑的信息素在算法進行到五分之一時按价，都已經(jīng)快蒸發(fā)沒了，這就導(dǎo)致螞蟻很難再嘗試其他路徑笙瑟，導(dǎo)致陷入局部最優(yōu)楼镐。對于這種情況，我的解決方案是:
1.設(shè)定信息素濃度的上下限
2.對路徑最優(yōu)的螞蟻進行信息素獎勵往枷，即每次更新信息素后框产，再對路徑最短的螞蟻重復(fù)一次更新信息素的過程凄杯，目的是加快收斂。
3.每循環(huán)N次（例如10）秉宿，就對非最優(yōu)路徑的信息素進行重置戒突。
下面是相關(guān)代碼：
/**
* 更新信息素
*
* @return void
*/
private function update_pheromones()
{
$pheromone_deltas = array(); //保存每條邊本次循環(huán)信息素增量
foreach ($this->tsp_points as $i_no => $tsp_point_i) {
foreach ($this->tsp_points as $j_no => $tsp_point_j) {
$pheromone_deltas[$i_no][$j_no] = 0;
$pheromone_deltas[$j_no][$i_no] = 0;
}
}
foreach ($this->ants as $ant) {
$len = $ant->path_len;
if ($this->best_ant == null || $len < $this->best_ant->path_len) {
$this->best_ant = $ant;
}
for ($i = 0; $i < count($ant->path); $i++) {
$j = $i + 1;
if ($j == count($ant->path)) {
$j = 0;
}
$i_no = $ant->path[$i]->no;
$j_no = $ant->path[$j]->no;
$pheromone_deltas[$i_no][$j_no] += $this->q / $len; //累加每個經(jīng)過這條邊的螞蟻產(chǎn)生的信息素。單個螞蟻產(chǎn)生的信息素計算公式是： 信息素因子Q/路徑長度
$pheromone_deltas[$j_no][$i_no] += $this->q / $len;
}
}
foreach ($this->tsp_points as $i_no => $tsp_point) {
foreach ($tsp_point->pheromones as $j_no => $pheromone) {
$new_pheromone = (1 - $this->rou) * $pheromone + $pheromone_deltas[$i_no][$j_no];//原路徑信息素?fù)]發(fā)描睦，然后加上本次信息素增量
//設(shè)置信息素濃度上下限
if ($new_pheromone < $this->min_pheromone) {
$new_pheromone = $this->min_pheromone;
}
if ($new_pheromone > $this->max_pheromone) {
$new_pheromone = $this->max_pheromone;
}
$this->tsp_points[$i_no]->pheromones[$j_no] = $new_pheromone;
$this->tsp_points[$j_no]->pheromones[$i_no] = $new_pheromone;
}
}
$best_ant = $this->best_ant;
for ($i = 0; $i < count($best_ant->path); $i++) {
$j = $i + 1;
if ($j == count($best_ant->path)) {
$j = 0;
}
$i_no = $best_ant->path[$i]->no;
$j_no = $best_ant->path[$j]->no;
$new_pheromone = $this->tsp_points[$i_no]->pheromones[$j_no] + $this->q_best / $best_ant->path_len;
if ($new_pheromone < $this->min_pheromone) {
$new_pheromone = $this->min_pheromone;
}
if ($new_pheromone > $this->max_pheromone) {
$new_pheromone = $this->max_pheromone;
}
$this->tsp_points[$i_no]->pheromones[$j_no] = $new_pheromone;
$this->tsp_points[$j_no]->pheromones[$i_no] = $new_pheromone;
}
}
相關(guān)變量設(shè)定
$min_pheromone=0.3;
$max_pheromone=5;
$q_best=10;
運行結(jié)果：
本次最優(yōu)解:431 在第99次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:426 在第31次搜索命中最優(yōu)解 耗時:6秒
本次最優(yōu)解:429 在第155次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:426 在第25次搜索命中最優(yōu)解 耗時:6秒
本次最優(yōu)解:426 在第11次搜索命中最優(yōu)解 耗時:6秒
本次最優(yōu)解:426 在第33次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:435 在第31次搜索命中最優(yōu)解 耗時:5秒
本次最優(yōu)解:436 在第36次搜索命中最優(yōu)解 耗時:6秒
本次最優(yōu)解:426 在第23次搜索命中最優(yōu)解 耗時:6秒
本次最優(yōu)解:428 在第85次搜索命中最優(yōu)解 耗時:5秒
可以看出膊存，經(jīng)過上述優(yōu)化后，其運行結(jié)果和之前相比已經(jīng)有大幅度的提升忱叭，但運行結(jié)果還不是太穩(wěn)定膝舅，而要越穩(wěn)定的逼近最優(yōu)解，其優(yōu)化難度就越高窑多。以蟻群算法來說仍稀，各參數(shù)的設(shè)定對搜索結(jié)果影響非常大，但多參數(shù)調(diào)優(yōu)又是一個非常復(fù)雜繁瑣的事情埂息。這里對小規(guī)模問題推薦一個優(yōu)化方法：鄰域搜索技潘。鄰域搜索的目的是消除附近有交叉的路徑，對于100以內(nèi)的問題千康，使用2-opt鄰域搜索即可享幽，相關(guān)代碼如下：
/**
* 2-opt鄰域搜索優(yōu)化
*
* @return void
*/
public function two_op_search()
{
$total = count($this->path);
for ($i = 0; $i < $total; $i++) {
for ($j = $total - 1; $j > $i; $j--) {
$i_pre = ($i - 1 + $total) % $total;
$j_next = ($j + 1) % $total;
if ($i_pre == $j) {
continue;
}
$i_no = intval($this->path[$i]->no);
$i_pre_no = intval($this->path[$i_pre]->no);
$j_no = intval($this->path[$j]->no);
$j_next_no = intval($this->path[$j_next]->no);
$len1 = $this->tsp_points[$i_pre_no]->get_distance($i_no) + $this->tsp_points[$j_no]->get_distance($j_next_no);
$len2 = $this->tsp_points[$i_pre_no]->get_distance($j_no) + $this->tsp_points[$i_no]->get_distance($j_next_no);
if ($len2 < $len1) {
$start = $i;
$end = $j;
while ($start < $end) {
$tmp = $this->path[$start];
$this->path[$start] = $this->path[$end];
$this->path[$end] = $tmp;
$start++;
$end--;
}
}
}
}
}
在螞蟻構(gòu)造完路徑后，調(diào)用two_op_search函數(shù)對路徑進行優(yōu)化拾弃。下面是添加了鄰域搜索后的運行結(jié)果：
本次最優(yōu)解:426 在第171次搜索命中最優(yōu)解 耗時:11秒
本次最優(yōu)解:427 在第31次搜索命中最優(yōu)解 耗時:11秒
本次最優(yōu)解:426 在第11次搜索命中最優(yōu)解 耗時:11秒
本次最優(yōu)解:427 在第22次搜索命中最優(yōu)解 耗時:11秒
本次最優(yōu)解:426 在第9次搜索命中最優(yōu)解 耗時:12秒
本次最優(yōu)解:426 在第13次搜索命中最優(yōu)解 耗時:11秒
本次最優(yōu)解:426 在第26次搜索命中最優(yōu)解 耗時:11秒
本次最優(yōu)解:426 在第23次搜索命中最優(yōu)解 耗時:11秒
本次最優(yōu)解:427 在第82次搜索命中最優(yōu)解 耗時:11秒
本次最優(yōu)解:426 在第5次搜索命中最優(yōu)解 耗時:11秒
從結(jié)果可以看出值桩，經(jīng)過鄰域搜索優(yōu)化后，已經(jīng)穩(wěn)定在最優(yōu)解或次優(yōu)解豪椿。但也發(fā)現(xiàn)另外的問題奔坟，就是用時比之前大幅提高。對于這個問題搭盾，由于我們觀察到經(jīng)過鄰域搜索優(yōu)化后咳秉，已經(jīng)能在算法運行初期就能得到最優(yōu)解，所以我們嘗試降低搜索次數(shù)和螞蟻數(shù)量鸯隅。以下是將搜索次數(shù)改成100澜建，螞蟻數(shù)量改成15后的運行結(jié)果：
本次最優(yōu)解:427 在第30次搜索命中最優(yōu)解 耗時:3秒
本次最優(yōu)解:427 在第21次搜索命中最優(yōu)解 耗時:2秒
本次最優(yōu)解:427 在第41次搜索命中最優(yōu)解 耗時:2秒
本次最優(yōu)解:427 在第55次搜索命中最優(yōu)解 耗時:2秒
本次最優(yōu)解:427 在第28次搜索命中最優(yōu)解 耗時:3秒
本次最優(yōu)解:426 在第21次搜索命中最優(yōu)解 耗時:2秒
本次最優(yōu)解:426 在第20次搜索命中最優(yōu)解 耗時:3秒
本次最優(yōu)解:426 在第35次搜索命中最優(yōu)解 耗時:3秒
本次最優(yōu)解:426 在第27次搜索命中最優(yōu)解 耗時:2秒
本次最優(yōu)解:426 在第21次搜索命中最優(yōu)解 耗時:3秒
可以看出，減少搜索次數(shù)和螞蟻數(shù)量蝌以，并沒有降低解的質(zhì)量炕舵。但搜索速度卻能大大提高。
優(yōu)化過程到此完畢跟畅。
后話
這是本人學(xué)習(xí)蟻群算法的一點優(yōu)化心得咽筋，文章中的各個參數(shù)都是本人大致猜想+粗略優(yōu)化得出，實際參數(shù)設(shè)定上還有很大的優(yōu)化空間碍彭。
對于蟻群算法的優(yōu)化晤硕，網(wǎng)上也有多個版本悼潭，例如精英蟻群算法，最大最小蟻群算法等舞箍。文中所用的優(yōu)化手段舰褪，也是參照了這些增強型算法。畢竟蟻群算法的目的是快速搜索出最優(yōu)解疏橄，所以所有的優(yōu)化手段應(yīng)該都從加快收斂占拍、提高求解精度這兩方面出發(fā)的。
最后希望本文能給蟻群算法初學(xué)者提供一些經(jīng)驗捎迫。
