使用蚁群算法遇到了问题

Question

有人能帮忙看看吗,我的这个蚁群算法迟迟收敛不下来,找不到正确答案
参数调了很久也没有用

import numpy as np
import matplotlib.pyplot as plt
import random
import copy
import matplotlib.animation as animation
coordinates = np.array(
    [[1.304,2.312],        
    [3.639,    1.315],        
    [4.177,    2.244],        
    [3.712,    1.399],        
    [3.488,    1.535],        
    [3.326,    1.556],        
    [3.238,    1.229],        
    [4.196,    1.044],        
    [4.312    ,0.79],        
    [4.386    ,0.57],        
    [3.007,    1.97],
    [2.562    ,1.756],        
    [2.788,1.491],
    [2.381    ,1.676],        
    [1.332,    0.695],
    [3.715    ,1.678],
    [3.918,    2.179],
    [4.061    ,2.37],
    [3.78,    2.212],
    [3.676,    2.578],
    [4.029,    2.838],
    [4.263    ,2.931],
    [3.429    ,1.908],
    [3.507,    2.376],
    [3.394,    2.643],
    [3.439,    3.201],
    [2.935,    3.24],
    [3.14,    3.55],
    [2.545,    2.357],
    [2.778,    2.826],
    [2.37,    2.975]])
#城市数量
city_num = coordinates.shape[0]
#蚁群数量
ant_num = 30
#信息启发因子:值越大，则蚂蚁会更多的选择以前走过的路径,值越小,则蚂蚁会更多的选择信息素浓度较高的路径    
ALPHA = 1.5
#下面的值越大,就越容易选择短路径
BETA = 2
#信息素挥发率
RHO = 0.5
#蚂蚁走一轮所留下的信息素总量
Q = 100
#迭代次数
MAX_GEN = 600
def getdistmat(coordinates):
    num = len(coordinates)
    distmat = np.zeros((num, num))
    for i in range(num):
        for j in range(i, num):
            distmat[i][j] = distmat[j][i] = np.linalg.norm(
                coordinates[i] - coordinates[j])
    return distmat
#初始化各个参数
distance_graph = getdistmat(coordinates)
pheromone_graph = np.ones((city_num, city_num))
#蚂蚁
class Ant(object):
    def __init__(self, ID):
        self.ID = ID
        self.__clean_data()  #一些初始化操作
    def __clean_data(self):
        self.path = []
        self.total_distance = 0.0
        self.move_count = 0
        self.current_city = -1
        self.open_table = [True for _ in range(city_num)]
        self.current_city = np.random.randint(0, city_num)#随机出生点
        self.open_table[self.current_city] = False
        self.path.append(self.current_city)
        self.move_count = 1
    def select_next_city(self):
        next_city = -1
        select_city_prob = [0.0 for _ in range(city_num)]
        total_prob = 0.0
        #计算概率
        for i in range(city_num):
            if self.open_table[i]:
                try:
                    select_city_prob[i] = pow(pheromone_graph[self.current_city][i],ALPHA) * pow((1.0 / distance_graph[self.current_city][i]), BETA)
                    total_prob += select_city_prob[i]
                    #轮盘赌分母 
                #除零错误   
                except ZeroDivisionError as e:
                    print('divided by zero.')
                    exit(1)
        #轮盘赌选择下一个城市
        if total_prob > 0.0:
            temp_prop = random.uniform(0.0,total_prob)
            for i in range(city_num):
                if self.open_table[i]:
                    temp_prop -= select_city_prob[i]
                    if temp_prop<= 0.0:
                        next_city = i
                        break
        return next_city
    def __cal_total_distance(self):
        temp_distance = 0.0
        for i in range(1,city_num):
            start,end = self.path[i],self.path[i-1]
            temp_distance += distance_graph[start][end]
        end = self.path[0]
        temp_distance += distance_graph[start][end]
        self.total_distance = temp_distance
    def _move(self,next_city):
        self.path.append(next_city)
        self.current_city = next_city
        self.open_table[next_city] = False
        self.move_count += 1
    #蚂蚁移动主函数
    def search_path(self):
        self.__clean_data()  #一些初始化操作
        while self.move_count < city_num:
            new_city = self.select_next_city()
            self._move(new_city)
        self.__cal_total_distance()
        self.path.append(self.path[0])
#主程序
def main():
    global pheromone_graph
    global distance_graph
    global coordinates
    #创建蚁群
    ants = [Ant(ID) for ID in range(ant_num)]
    #创建蚁群历史路径,用于绘图
    ants_history_path = [[] for i in range(ant_num)]
    best_ants = []
    #迭代开始
    for i in range(MAX_GEN):
        #信息素挥发
        pheromone_graph = (1 - RHO) * pheromone_graph
        for ID in range(len(ants)):
            ants[ID].search_path()
            k = copy.deepcopy(ants[ID].path)
            ants_history_path[ID].append(k)
            for i in range(1,len(ants[ID].path)):
                start,end = ants[ID].path[i-1],ants[ID].path[i]
                pheromone_graph[start][end] += Q/ants[ID].total_distance
                #因为信息素矩阵是对称矩阵,两边都要加
                pheromone_graph[end][start] += Q/ants[ID].total_distance
        #判断是否满足结束条件
        if max([ants[i].total_distance for i in range(ant_num)]) - min([ants[i].total_distance for i in range(ant_num)]) < 0.0001:
                break
    #找到最优路径
        best_ant = min(ants,key = lambda ant:ant.total_distance)
        k = copy.deepcopy(best_ant)
        best_ants.append(k)
    best_ant = min(best_ants,key = lambda ant:ant.total_distance)
    print('最短路径为:',best_ant.path,'最短距离为:',best_ant.total_distance)
    fig,ax= plt.subplots()
    ln = [ax.plot([], [], '.-')[0] for i in range(ant_num)]
    def init():
        ax.set_xlim(0,5)
        ax.set_ylim(0,5)
        return ln
    def animate(i):
        i= int(i)
        for j in range(ant_num):
            if i < len(ants_history_path[j]):
                x = [coordinates[ants_history_path[j][i][k]][0] for k in range(len(ants_history_path[0][0]))]
                y = [coordinates[ants_history_path[j][i][k]][1] for k in range(len(ants_history_path[0][0]))]
                ln[j].set_data(x,y)
        return ln
    ani = animation.FuncAnimation(fig,animate,init_func=init,
                                frames = np.linspace(0,len(ants_history_path[0]),len(ants_history_path[0])),
                                interval = 100,blit = True)
    plt.show()
    fig,ax= plt.subplots()
    ln, = ax.plot([], [], '.-')
    def init():
        ax.set_xlim(0,5)
        ax.set_ylim(0,5)
        return ln,
    def animate(i):
        i = int(i)
        if i < len(best_ants):
            x = [coordinates[best_ants[i].path[k]][0] for k in range(len(best_ants[0].path))]
            y = [coordinates[best_ants[i].path[k]][1] for k in range(len(best_ants[0].path))]
            ln.set_data(x,y)
        return ln,
    ani = animation.FuncAnimation(fig,animate,init_func=init,
                                frames = np.linspace(0,len(best_ants),len(best_ants)),
                                interval = 100,blit = True)
    plt.show()
main()

Answer 1

上午好☀️☀️☀️️
本答案参考ChatGPT-3.5

根据你的描述，你的问题是使用蚁群算法时遇到了收敛速度慢、无法找到正确答案的问题。下面给出一些可能的解决方案：

1. 问题分析：

   • 检查距离矩阵计算是否正确：可以通过打印距离矩阵来检查其是否正确计算，确保距离矩阵的值符合预期。
   • 检查参数设置是否合理：可以尝试调整蚂蚁数量、信息启发因子、信息素挥发率等参数来看是否有改善效果。
   • 检查蚁群算法的实现是否正确：可以对算法的各个步骤进行逐一检查，确保实现没有错误。

2. 参数调优：

   • 调整蚂蚁数量：可以尝试增加蚂蚁数量，增加蚂蚁在搜索过程中的多样性，提高搜索的全局性能。
   • 调整信息启发因子和信息素挥发率：可以尝试调整信息启发因子和信息素挥发率的值，以控制蚂蚁在选择路径时对信息素浓度和距离的依赖程度。尝试不同的值，找到一个平衡点。
   • 调整迭代次数：可以尝试增加迭代次数，给蚂蚁更多的搜索时间，增加搜索的全局性能。

3. 改进蚁群算法：

   • 局部搜索机制：考虑引入局部搜索机制，以增加蚂蚁在搜索过程中对当前最优解的探索。可以在搜索过程中，对蚂蚁的路径进行局部调整和优化。
   • 动态调整参数：可以考虑根据不同迭代阶段的性能情况来动态调整参数值。例如，在开始阶段增加信息素挥发率，以增加蚂蚁对新路径的探索；在后期逐渐减小信息素挥发率，以稳定搜索过程。
   • 多次迭代：可以尝试多次运行蚁群算法，每次运行结束后将最优路径保存下来，然后从最优路径开始下一次迭代。这样可以逐渐加强最优路径，提高收敛速度。

请注意，以上提供的解决方案仅供参考。在实际应用中，可能需要根据具体问题进行调整和优化。同时，还可以通过其他优化算法、模型参数的调整、问题约束的修改等方式来改进蚁群算法的性能。