蚁群算法原理和代码实现(python)

作者: cfd1a409f338 | 来源:发表于2019-02-27 00:55 被阅读1次

蚁群算法原理和代码实现(python)
TSP解决之道——蚁群算法
蚁群算法简单介绍
Apriori 算法的研究
蚁群算法代码
6- OpenCV+TensorFlow 入门人工智能图像处理-
softmax回归
机器学习之初识KNN算法——针对泰坦尼克号生存记录建模的两种方法
蚁群算法解TSP(2)-核心代码
堆优化的A*算法-Python实现

蚁群算法(AG)是一种模拟蚂蚁觅食行为的模拟优化算法，它是由意大利学者Dorigo M等人于1991年首先提出，并首先使用在解决TSP（旅行商问题）上

第一蚁群优化算法被称为“蚂蚁系统”，它旨在解决推销员问题，其目标是要找到一系列城市的最短遍历路线。总体算法相对简单，要点如下:

一组蚂蚁，每只完成一次城市间的遍历

在每个阶段，蚂蚁根据一些规则选择从一个城市移动到另一个：它必须访问每个城市一次;一个越远的城市被选中的机会越少（能见度更低）

在两个城市边际的一边形成的信息素越浓烈，这边被选择的概率越大;如果路程短的话，已经完成旅程的蚂蚁会在所有走过的路径上沉积更多信息素每次迭代后，信息素轨迹挥发

总结后的要点即为 1. 状态转移 2. 信息素更新

下面我们开始数学表示：

先定义算法的关键参数，希望后面的公式结合参数意义思考

$m$ :蚂蚁数量

$M$ ：城市数量

$\rho$ : 信息素挥发因子，表示信息素的持久度，取值推荐为[0,1]

$Q$ : 常量，表示信息素浓度

$L_k$ 表示第k只蚂蚁在本次迭代中路程的代价

$\alpha$ : 信息素启发因子，表示在搜索中，信息量的相对重要程度

$\beta$ : 期望启发因子，表示在搜索中，启发式信息的相对重要程度

一般而言:

$m=1.5*M$

$\rho \in [0.2,0.5]$

$Q \in [10,100]$

$\alpha \in [0,5]$

$\beta \in [0,5]$

我们先以一只蚂蚁为主体，“我”即为一只蚂蚁

我现在的位置在一个“城市” $i$ ,我到其他城市 $j ,j \in [1,M]$ 的距离为 $d_{i,j}$ ,我面前到每一个城市的信息浓度为 $p_{i,j}$ ,我现在需要决定，我下一步需要前往的城市。影响我选择的因素有我到各个城市的距离 $d_{i,j}$ 和我面前的信息素的浓度 $p_{i,j}$ ,我需要一个公式计算出我选择每一个城市的概率 $q_{i,j}$ :

$q_{i,j}=p_{i,j}^\alpha \times (\frac{1}{d_{i,j}})^\beta$

好了，这个公式也满足我们的期望和上面解释的参数的实际意义。那我开始计算我面前每一个城市我选择它的概率，那么问题来了，我们如何选择呢，这里推荐使用的是轮盘法选择，增加随机性。将所有的概率相加的值 total_prob 轮次递减每一个城市的概率值，若total_prob 减至负数，恭喜你，我就选择这个城市了。这种选择方法满足高概率高可能的特性，且有随机性。

后面的每一个城市，我就这样玩了。直到我走完所有的城市。程序记录下了我走过的总路径长度和顺序即可。

当我走完所有的城市，我就对应一条搜索路径。将我的搜索路径和其他蚂蚁对比，选择长度最短的那个蚂蚁，以这个“最优蚂蚁”的查找路径，画出“最优蚂蚁”的蚂蚁，做出这一轮迭代的可视化结果。

当每一个蚂蚁都结束自己的查找时，我们有每一个蚂蚁的路径顺序，那我们现在就可以开始更新信息素分布了，show time

对于信息素浓度矩阵 $p_{i,j}$ ,迭代更新的公式为:

$p_{i,j}=\rho*p_{i,j}+\frac{Q}{sum}$

其中 $sum$ 为每一个蚂蚁走过的距离之和

现在，每一轮蚂蚁都对应一次迭代和信息素的更新和一次效果的可视化展示

万事俱备，之前代码了，那我们开始了

先初始化上述的关键参数，取值范围也满足推荐值

# 参数初始化

(ALPHA,BETA,RHO,Q)=(1.0,2.0,0.5,100.0)

# 城市，蚁群

(city_num,ant_num)=(50,50)

# 初始化城市的位置

distance_x = [

178,272,176,171,650,499,267,703,408,437,491,74,532,

416,626,42,271,359,163,508,229,576,147,560,35,714,

757,517,64,314,675,690,391,628,87,240,705,699,258,

428,614,36,360,482,666,597,209,201,492,294]

distance_y = [

170,395,198,151,242,556,57,401,305,421,267,105,525,

381,244,330,395,169,141,380,153,442,528,329,232,48,

498,265,343,120,165,50,433,63,491,275,348,222,288,

490,213,524,244,114,104,552,70,425,227,331]

# 城市距离和信息素

distance_graph=[[0.0 for col in range(city_num)] for raw in range(city_num)]

pheromone_graph=[[1.0 for col in range(city_num)] for raw in range(city_num)]

上面我们可以看出，"蚂蚁"也很有自己的主见啊，那我们为蚂蚁创建一个类吧

蚂蚁选择城市是根据信息素和距离，最后使用轮盘法确定城市的

# 选择下一个城市

def__choice_next_city(self):

next_city=-1

# 存储选择下一个城市的概率

select_city_prob=[0.0foriinrange(city_num)]

total_prob=0.0

# 获取下一个城市的概率

foriinrange(city_num):

ifself.open_table_city[i]:

try:

# 计算概率

select_city_prob[i]=pow(pheromone_graph[self.current_city][i],ALPHA)*pow(distance_graph[self.current_city][i],BETA)

total_prob+=select_city_prob[i]

exceptZeroDivisionErrorase:

print("分母为0")

sys.exit(1)

# 轮盘选择城市

iftotal_prob>0.0:

# 产生一个随机概率

temp_prob=random.uniform(0.0,total_prob)

foriinrange(city_num):

# 轮次递减

temp_prob-=select_city_prob[i]

iftemp_prob<0.0:

next_city=i

break

if(next_city==-1):

next_city=random.randint(0,city_num-1)

whileself.open_table_city[next_city]==False:

next_city=random.randint(0,city_num-1)

# 返回选择的下一个城市号

returnnext_city

每一轮迭代结束之后，我们需要进行信息素的更新

# 更新信息素

def __update_pheromone_gragh(self):

# 获取每只蚂蚁在其路径上留下的信息素

temp_pheromone = [[0.0 for col in range(city_num)] for raw in range(city_num)]

for ant in self.ants:

for i in range(1,city_num):

start, end = ant.path[i-1], ant.path[i]

# 在路径上的每两个相邻城市间留下信息素，与路径总距离反比

temp_pheromone[start][end] += Q / ant.total_distance

temp_pheromone[end][start] = temp_pheromone[start][end]

# 更新所有城市之间的信息素，旧信息素衰减加上新迭代信息素

for i in range(city_num):

for j in range(city_num):

pheromone_graph[i][j] = pheromone_graph[i][j] * RHO + temp_pheromone[i][j]