ACO蟻群算法解決TSP旅行商問題
來源：程序員人生 發(fā)布時(shí)間：2015-05-25 09:28:43 閱讀次數(shù)：3639次
前言
蟻群算法也是1種利用了大自然規(guī)律的啟發(fā)式算法，與之前學(xué)習(xí)過的GA遺傳算法類似，遺傳算法是用了生物進(jìn)行理論，把更具適應(yīng)性的基因傳給下1代，最后就可以得到1個(gè)最優(yōu)解，常經(jīng)常使用來尋覓問題的最優(yōu)解。固然，本篇文章不會(huì)主講GA算法的，想要了解的同學(xué)可以查看，我的遺傳算法學(xué)習(xí)和遺傳算法在走迷宮中的應(yīng)用。話題重新回到蟻群算法，蟻群算法是1個(gè)利用了螞蟻尋覓食品的原理。不知道小時(shí)候有無發(fā)現(xiàn)，當(dāng)1個(gè)螞蟻發(fā)現(xiàn)了地上的食品，然后非常迅速的，就有其他的螞蟻集合過來，最后把食品抬回家，這里面其實(shí)有著非常多的道理的，在ACO中就用到了這個(gè)機(jī)理用于解決實(shí)際生活中的1些問題。
螞蟻找食品
首先我們要具體說說1個(gè)成心思的事情，就是螞蟻找食品的問題，理解了這個(gè)原理以后，對理解ACO算法就非常容易了。螞蟻?zhàn)鳛槟悄┬〉膭?dòng)物，在地上漫無目的的尋覓食品，起初都是沒有目標(biāo)的，他從螞蟻洞中走出，隨機(jī)的爬向各個(gè)方向，在這期間他會(huì)向外界播撒1種化學(xué)物資，姑且就叫做信息素，所以這里就能夠得到的1個(gè)條件，越多螞蟻?zhàn)哌^的路徑，信息素濃度就會(huì)越高，那末某條路徑信息素濃度高了，自然就會(huì)有越多的螞蟻感覺到了，就集聚集過來了。所以當(dāng)眾多螞蟻中的1個(gè)找到食品以后，他就會(huì)在走過的路徑中放出信息素濃度，因此就會(huì)有很多的螞蟻趕來了。類似下面的場景：
至于螞蟻是如何感知這個(gè)信息素，這個(gè)就得問生物學(xué)家了，我也沒做過研究。
算法介紹
OK，有了上面這個(gè)自然生活中的生物場景以后，我們再來切入文章主題來學(xué)習(xí)1下蟻群算法，百度百科中對應(yīng)蟻群算法是這么介紹的：蟻群算法是1種在圖中尋覓優(yōu)化路徑的機(jī)率型算法。他的靈感就是來自于螞蟻發(fā)現(xiàn)食品的行動(dòng)。蟻群算法是1種新的摹擬進(jìn)化優(yōu)化的算法，與遺傳算法有很多相似的地方。蟻群算法在比較早的時(shí)候成功解決了TSP旅行商的問題（在后面的例子中也會(huì)以這個(gè)例子）。要用算法去摹擬螞蟻的這類行動(dòng)，關(guān)鍵在于信息素的在算法中的設(shè)計(jì)，和路徑中信息素濃度越大的路徑，將會(huì)有更高的幾率被螞蟻所選擇到。
算法原理
要想實(shí)現(xiàn)上面的幾個(gè)摹擬行動(dòng)，需要借助幾個(gè)公式，固然公式不是我自己定義的，主要有3個(gè)，以下圖：
上圖中所出現(xiàn)的alpha，beita，p等數(shù)字都是控制因子，所以可沒必要理睬，Tij(n)的意思是在時(shí)間為n的時(shí)候，從城市i到城市j的路徑的信息素濃度。類似于nij的字母是城市i到城市j距離的倒數(shù)。就是下面這個(gè)公式。
所以所有的公式都是為第1個(gè)公式服務(wù)的，第1個(gè)公式的意思是指第k只螞蟻選擇從城市i到城市j的幾率，可以見得，這個(gè)受距離和信息素濃度的兩重影響，距離越遠(yuǎn)，去此城市的幾率自然也低，所以nij會(huì)等于距離的倒數(shù)，而且在算信息素濃度的時(shí)候，也斟酌到了信息素濃度衰減的問題，所以會(huì)在上次的濃度值上乘以1個(gè)衰減因子P。另外還要加上本輪搜索增加的信息素濃度（假設(shè)有螞蟻經(jīng)過此路徑的話），所以這幾個(gè)公式的整體設(shè)計(jì)思想還是非常棒的。
算法的代碼實(shí)現(xiàn)
由于本身我這里沒有甚么真實(shí)的測試數(shù)據(jù)，就隨意自己構(gòu)造了1個(gè)簡單的數(shù)據(jù)，輸入以下，分為城市名稱和城市之間的距離，用#符號做辨別標(biāo)識，大家應(yīng)當(dāng)可以看得懂吧
# CityName
1
2
3
4
# Distance
1 2 1
1 3 1.4
1 4 1
2 3 1
2 4 1
3 4 1
螞蟻類Ant.java:
package DataMining_ACO;
import java.util.ArrayList;
/**
* 螞蟻類，進(jìn)行路徑搜索的載體
*
* @author lyq
*
*/
public class Ant implements Comparable<Ant> {
// 螞蟻當(dāng)前所在城市
String currentPos;
// 螞蟻遍歷完回到原點(diǎn)所用的總距離
Double sumDistance;
// 城市間的信息素濃度矩陣，隨著時(shí)間的增多而減少
double[][] pheromoneMatrix;
// 螞蟻已走過的城市集合
ArrayList<String> visitedCitys;
// 還未走過的城市集合
ArrayList<String> nonVisitedCitys;
// 螞蟻當(dāng)前走過的路徑
ArrayList<String> currentPath;
public Ant(double[][] pheromoneMatrix, ArrayList<String> nonVisitedCitys) {
this.pheromoneMatrix = pheromoneMatrix;
this.nonVisitedCitys = nonVisitedCitys;
this.visitedCitys = new ArrayList<>();
this.currentPath = new ArrayList<>();
}
/**
* 計(jì)算路徑的總本錢(距離)
*
* @return
*/
public double calSumDistance() {
sumDistance = 0.0;
String lastCity;
String currentCity;
for (int i = 0; i < currentPath.size() - 1; i++) {
lastCity = currentPath.get(i);
currentCity = currentPath.get(i + 1);
// 通過距離矩陣進(jìn)行計(jì)算
sumDistance += ACOTool.disMatrix[Integer.parseInt(lastCity)][Integer
.parseInt(currentCity)];
}
return sumDistance;
}
/**
* 螞蟻選擇前往下1個(gè)城市
*
* @param city
* 所選的城市
*/
public void goToNextCity(String city) {
this.currentPath.add(city);
this.currentPos = city;
this.nonVisitedCitys.remove(city);
this.visitedCitys.add(city);
}
/**
* 判斷螞蟻是不是已又重新回到出發(fā)點(diǎn)
*
* @return
*/
public boolean isBack() {
boolean isBack = false;
String startPos;
String endPos;
if (currentPath.size() == 0) {
return isBack;
}
startPos = currentPath.get(0);
endPos = currentPath.get(currentPath.size() - 1);
if (currentPath.size() > 1 && startPos.equals(endPos)) {
isBack = true;
}
return isBack;
}
/**
* 判斷螞蟻在本次的走過的路徑中是不是包括從城市i到城市j
*
* @param cityI
* 城市I
* @param cityJ
* 城市J
* @return
*/
public boolean pathContained(String cityI, String cityJ) {
String lastCity;
String currentCity;
boolean isContained = false;
for (int i = 0; i < currentPath.size() - 1; i++) {
lastCity = currentPath.get(i);
currentCity = currentPath.get(i + 1);
// 如果某1段路徑的始末位置1致，則認(rèn)為有經(jīng)過此城市
if ((lastCity.equals(cityI) && currentCity.equals(cityJ))
|| (lastCity.equals(cityJ) && currentCity.equals(cityI))) {
isContained = true;
break;
}
}
return isContained;
}
@Override
public int compareTo(Ant o) {
// TODO Auto-generated method stub
return this.sumDistance.compareTo(o.sumDistance);
}
}
蟻群算法工具類ACOTool.java:
package DataMining_ACO;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
/**
* 蟻群算法工具類
*
* @author lyq
*
*/
public class ACOTool {
// 輸入數(shù)據(jù)類型
public static final int INPUT_CITY_NAME = 1;
public static final int INPUT_CITY_DIS = 2;
// 城市間距離鄰接矩陣
public static double[][] disMatrix;
// 當(dāng)前時(shí)間
public static int currentTime;
// 測試數(shù)據(jù)地址
private String filePath;
// 螞蟻數(shù)量
private int antNum;
// 控制參數(shù)
private double alpha;
private double beita;
private double p;
private double Q;
// 隨機(jī)數(shù)產(chǎn)生器
private Random random;
// 城市名稱集合,這里為了方便，將城市用數(shù)字表示
private ArrayList<String> totalCitys;
// 所有的螞蟻集合
private ArrayList<Ant> totalAnts;
// 城市間的信息素濃度矩陣，隨著時(shí)間的增多而減少
private double[][] pheromoneMatrix;
// 目標(biāo)的最短路徑,順序?yàn)閺募系那安客笠苿?dòng)
private ArrayList<String> bestPath;
// 信息素矩陣存儲圖,key采取的格式(i,j,t)->value
private Map<String, Double> pheromoneTimeMap;
public ACOTool(String filePath, int antNum, double alpha, double beita,
double p, double Q) {
this.filePath = filePath;
this.antNum = antNum;
this.alpha = alpha;
this.beita = beita;
this.p = p;
this.Q = Q;
this.currentTime = 0;
readDataFile();
}
/**
* 從文件中讀取數(shù)據(jù)
*/
private void readDataFile() {
File file = new File(filePath);
ArrayList<String[]> dataArray = new ArrayList<String[]>();
try {
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
String[] tempArray;
while ((str = in.readLine()) != null) {
tempArray = str.split(" ");
dataArray.add(tempArray);
}
in.close();
} catch (IOException e) {
e.getStackTrace();
}
int flag = ⑴;
int src = 0;
int des = 0;
int size = 0;
// 進(jìn)行城市名稱種數(shù)的統(tǒng)計(jì)
this.totalCitys = new ArrayList<>();
for (String[] array : dataArray) {
if (array[0].equals("#") && totalCitys.size() == 0) {
flag = INPUT_CITY_NAME;
continue;
} else if (array[0].equals("#") && totalCitys.size() > 0) {
size = totalCitys.size();
// 初始化距離矩陣
this.disMatrix = new double[size + 1][size + 1];
this.pheromoneMatrix = new double[size + 1][size + 1];
// 初始值⑴代表此對應(yīng)位置無值
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
this.disMatrix[i][j] = ⑴;
this.pheromoneMatrix[i][j] = ⑴;
}
}
flag = INPUT_CITY_DIS;
continue;
}
if (flag == INPUT_CITY_NAME) {
this.totalCitys.add(array[0]);
} else {
src = Integer.parseInt(array[0]);
des = Integer.parseInt(array[1]);
this.disMatrix[src][des] = Double.parseDouble(array[2]);
this.disMatrix[des][src] = Double.parseDouble(array[2]);
}
}
}
/**
* 計(jì)算從螞蟻城市i到j(luò)的幾率
*
* @param cityI
* 城市I
* @param cityJ
* 城市J
* @param currentTime
* 當(dāng)前時(shí)間
* @return
*/
private double calIToJProbably(String cityI, String cityJ, int currentTime) {
double pro = 0;
double n = 0;
double pheromone;
int i;
int j;
i = Integer.parseInt(cityI);
j = Integer.parseInt(cityJ);
pheromone = getPheromone(currentTime, cityI, cityJ);
n = 1.0 / disMatrix[i][j];
if (pheromone == 0) {
pheromone = 1;
}
pro = Math.pow(n, alpha) * Math.pow(pheromone, beita);
return pro;
}
/**
* 計(jì)算綜合幾率螞蟻從I城市走到J城市的幾率
*
* @return
*/
public String selectAntNextCity(Ant ant, int currentTime) {
double randomNum;
double tempPro;
// 總幾率指數(shù)
double proTotal;
String nextCity = null;
ArrayList<String> allowedCitys;
// 各城市幾率集
double[] proArray;
// 如果是剛剛開始的時(shí)候，沒有途經(jīng)任何城市，則隨機(jī)返回1個(gè)城市
if (ant.currentPath.size() == 0) {
nextCity = String.valueOf(random.nextInt(totalCitys.size()) + 1);
return nextCity;
} else if (ant.nonVisitedCitys.isEmpty()) {
// 如果全部遍歷終了，則再次回到出發(fā)點(diǎn)
nextCity = ant.currentPath.get(0);
return nextCity;
}
proTotal = 0;
allowedCitys = ant.nonVisitedCitys;
proArray = new double[allowedCitys.size()];
for (int i = 0; i < allowedCitys.size(); i++) {
nextCity = allowedCitys.get(i);
proArray[i] = calIToJProbably(ant.currentPos, nextCity, currentTime);
proTotal += proArray[i];
}
for (int i = 0; i < allowedCitys.size(); i++) {
// 歸1化處理
proArray[i] /= proTotal;
}
// 用隨機(jī)數(shù)選擇下1個(gè)城市
randomNum = random.nextInt(100) + 1;
randomNum = randomNum / 100;
// 由于1.0是沒法判斷到的，,總和會(huì)無窮接近1.0取為0.99做判斷
if (randomNum == 1) {
randomNum = randomNum - 0.01;
}
tempPro = 0;
// 肯定區(qū)間
for (int j = 0; j < allowedCitys.size(); j++) {
if (randomNum > tempPro && randomNum <= tempPro + proArray[j]) {
// 采取拷貝的方式避免援用重復(fù)
nextCity = allowedCitys.get(j);
break;
} else {
tempPro += proArray[j];
}
}
return nextCity;
}
/**
* 獲得給定時(shí)間點(diǎn)上從城市i到城市j的信息素濃度
*
* @param t
* @param cityI
* @param cityJ
* @return
*/
private double getPheromone(int t, String cityI, String cityJ) {
double pheromone = 0;
String key;
// 上1周期需將時(shí)間倒回1周期
key = MessageFormat.format("{0},{1},{2}", cityI, cityJ, t);
if (pheromoneTimeMap.containsKey(key)) {
pheromone = pheromoneTimeMap.get(key);
}
return pheromone;
}
/**
* 每輪結(jié)束，刷新信息素濃度矩陣
*
* @param t
*/
private void refreshPheromone(int t) {
double pheromone = 0;
// 上1輪周期結(jié)束后的信息素濃度，叢信息素濃度圖中查找
double lastTimeP = 0;
// 本輪信息素濃度增加量
double addPheromone;
String key;
for (String i : totalCitys) {
for (String j : totalCitys) {
if (!i.equals(j)) {
// 上1周期需將時(shí)間倒回1周期
key = MessageFormat.format("{0},{1},{2}", i, j, t - 1);
if (pheromoneTimeMap.containsKey(key)) {
lastTimeP = pheromoneTimeMap.get(key);
} else {
lastTimeP = 0;
}
addPheromone = 0;
for (Ant ant : totalAnts) {
if(ant.pathContained(i, j)){
// 每只螞蟻傳播的信息素為控制因子除以距離總本錢
addPheromone += Q / ant.calSumDistance();
}
}
// 將上次的結(jié)果值加上遞增的量，并存入圖中
pheromone = p * lastTimeP + addPheromone;
key = MessageFormat.format("{0},{1},{2}", i, j, t);
pheromoneTimeMap.put(key, pheromone);
}
}
}
}
/**
* 蟻群算法迭代次數(shù)
* @param loopCount
* 具體遍歷次數(shù)
*/
public void antStartSearching(int loopCount) {
// 蟻群尋覓的總次數(shù)
int count = 0;
// 選中的下1個(gè)城市
String selectedCity = "";
pheromoneTimeMap = new HashMap<String, Double>();
totalAnts = new ArrayList<>();
random = new Random();
while (count < loopCount) {
initAnts();
while (true) {
for (Ant ant : totalAnts) {
selectedCity = selectAntNextCity(ant, currentTime);
ant.goToNextCity(selectedCity);
}
// 如果已遍歷完所有城市，則跳出此輪循環(huán)
if (totalAnts.get(0).isBack()) {
break;
}
}
// 周期時(shí)間疊加
currentTime++;
refreshPheromone(currentTime);
count++;
}
// 根據(jù)距離本錢，選出所花距離最短的1個(gè)路徑
Collections.sort(totalAnts);
bestPath = totalAnts.get(0).currentPath;
System.out.println(MessageFormat.format("經(jīng)過{0}次循環(huán)遍歷，終究得出的最好路徑：", count));
System.out.print("entrance");
for (String cityName : bestPath) {
System.out.print(MessageFormat.format("-->{0}", cityName));
}
}
/**
* 初始化蟻群操作
*/
private void initAnts() {
Ant tempAnt;
ArrayList<String> nonVisitedCitys;
totalAnts.clear();
// 初始化蟻群
for (int i = 0; i < antNum; i++) {
nonVisitedCitys = (ArrayList<String>) totalCitys.clone();
tempAnt = new Ant(pheromoneMatrix, nonVisitedCitys);
totalAnts.add(tempAnt);
}
}
}
場景測試類Client.java:
package DataMining_ACO;
/**
* 蟻群算法測試類
* @author lyq
*
*/
public class Client {
public static void main(String[] args){
//測試數(shù)據(jù)
String filePath = "C:UserslyqDesktopiconinput.txt";
//螞蟻數(shù)量
int antNum;
//蟻群算法迭代次數(shù)
int loopCount;
//控制參數(shù)
double alpha;
double beita;
double p;
double Q;
antNum = 3;
alpha = 0.5;
beita = 1;
p = 0.5;
Q = 5;
loopCount = 5;
ACOTool tool = new ACOTool(filePath, antNum, alpha, beita, p, Q);
tool.antStartSearching(loopCount);
}
}
算法的輸出，就是在屢次搜索以后，找到的路徑中最短的1個(gè)路徑：
經(jīng)過5次循環(huán)遍歷，終究得出的最好路徑：
entrance-->4-->1-->2-->3-->4
由于數(shù)據(jù)量比較小，其實(shí)不能看出蟻群算法在這方面的優(yōu)勢，博友們可以再次基礎(chǔ)上自行改造，并用大1點(diǎn)的數(shù)據(jù)做測試，其中的4個(gè)控制因子也能夠調(diào)控。蟻群算法作為1種啟發(fā)式算法，還可以和遺傳算法結(jié)合，創(chuàng)造出更優(yōu)的算法。蟻群算法可以解決許多這樣的連通圖路徑優(yōu)化問題。但是有的時(shí)候也會(huì)出現(xiàn)搜索時(shí)間太長的問題。
參考文獻(xiàn)：百度百科.蟻群算法
我的數(shù)據(jù)發(fā)掘算法庫：https://github.com/linyiqun/DataMiningAlgorithm
我的算法庫：https://github.com/linyiqun/lyq-algorithms-lib
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
