精华内容
下载资源
问答
  • 使用蚁群算法进行智能避障,并且不断比较出路程,然后寻找出最短路径。此代码有所优化。使用蚁群算法进行智能避障,并且不断比较出路程,然后寻找出最短路径。此代码有所优化。
  • 蚁群算法介绍(python)

    千次阅读 2019-09-27 23:01:17
    蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是仿照蚂蚁寻找食物的最短路径行为来设计的仿生算法,是一种概率型算法,适用于优化组合问题。 特点 对图的对称性和目标函数无特殊要求 可以解决各种对称...

    蚁群算法

    什么是蚁群算法

    蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是仿照蚂蚁寻找食物的最短路径行为来设计的仿生算法,是一种概率型算法,适用于优化组合问题。
    在这里插入图片描述

    特点

    • 对图的对称性和目标函数无特殊要求
    • 可以解决各种对称不对称,线性和非线性的问题
    • 鲁棒性、扩展性强、全局性

    应用领域

    TSP(商旅问题)
    路径优化问题
    调度问题
    着色问题
    聚类分析
    网络路由
    数据挖掘
    工业PCB 板
    其它组合优化

    原理

    1、蚂蚁在路径上释放信息素。

    2、碰到还没走过的路口,就随机挑选一条路走。同 时,释放与路径长度有关的信息素。

    3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰 到该路口时,就选择信息素浓度较高路径。

    4、最优路径上的信息素浓度越来越大。

    5、最终蚁群找到最优寻食路径。

    在这里插入图片描述
    如上图所示,t0时刻有两只蚂蚁从蚁穴出发,分别向不同方向往前走,(三角形ABC是等边三角形),蚂蚁在沿途会留下信息素。
    t1时刻,蚂蚁2到达B处,蚂蚁1到达C处;蚂蚁2准备回到A处面临两个选择,一个往A方向走,一个往B方向走,而路径AB间信息素浓度大于BC间的所以选择了AB 路径。
    同理,t2时刻时蚂蚁1也做出了同样的选择。因此随着时间的推移AB间的信息素堆积就会越来越多,而BC,AC间就会随着时间推移信息素挥发后就越来越少。最终得出最短的路径AB

    数学模型

    访问某个节点的概率:
    在这里插入图片描述
    在这里插入图片描述
    信息素更新方程
    在这里插入图片描述
    在这里插入图片描述

    TSP应用例子

    问题简单描述就是:假设一个旅行商人,他要遍历n个城市,但是每个城市只能遍历一次,最终还要回到最初所在的城市,要求制定一个遍历方案,使经过的总路程最短。

    # -*- coding: utf-8 -*-
    import random
    import copy
    import time
    import sys
    import math
    import tkinter  # //GUI模块
    import threading
    from functools import reduce
    
    # 参数
    '''
    ALPHA:信息启发因子,值越大,则蚂蚁选择之前走过的路径可能性就越大
          ,值越小,则蚁群搜索范围就会减少,容易陷入局部最优
    BETA:Beta值越大,蚁群越就容易选择局部较短路径,这时算法收敛速度会
         加快,但是随机性不高,容易得到局部的相对最优
    '''
    (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)]
    
    
    # ----------- 蚂蚁 -----------
    class Ant(object):
    
        # 初始化
        def __init__(self, ID):
    
            self.ID = 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_city = [True for i in range(city_num)]  # 探索城市的状态
    
            city_index = random.randint(0, city_num - 1)  # 随机初始出生点
            self.current_city = city_index
            self.path.append(city_index)
            self.open_table_city[city_index] = False
            self.move_count = 1
    
        # 选择下一个城市
        def __choice_next_city(self):
    
            next_city = -1
            select_citys_prob = [0.0 for i in range(city_num)]  # 存储去下个城市的概率
            total_prob = 0.0
    
            # 获取去下一个城市的概率
            for i in range(city_num):
                if self.open_table_city[i]:
                    try:
                        # 计算概率:与信息素浓度成正比,与距离成反比
                        select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) * pow(
                            (1.0 / distance_graph[self.current_city][i]), BETA)
                        total_prob += select_citys_prob[i]
                    except ZeroDivisionError as e:
                        print('Ant ID: {ID}, current city: {current}, target city: {target}'.format(ID=self.ID,
                                                                                                    current=self.current_city,
                                                                                                    target=i))
                        sys.exit(1)
    
            # 轮盘选择城市
            if total_prob > 0.0:
                # 产生一个随机概率,0.0-total_prob
                temp_prob = random.uniform(0.0, total_prob)
                for i in range(city_num):
                    if self.open_table_city[i]:
                        # 轮次相减
                        temp_prob -= select_citys_prob[i]
                        if temp_prob < 0.0:
                            next_city = i
                            break
    
            # 未从概率产生,顺序选择一个未访问城市
            # if next_city == -1:
            #     for i in range(city_num):
            #         if self.open_table_city[i]:
            #             next_city = i
            #             break
    
            if (next_city == -1):
                next_city = random.randint(0, city_num - 1)
                while ((self.open_table_city[next_city]) == False):  # if==False,说明已经遍历过了
                    next_city = random.randint(0, city_num - 1)
    
            # 返回下一个城市序号
            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.open_table_city[next_city] = False
            self.total_distance += distance_graph[self.current_city][next_city]
            self.current_city = next_city
            self.move_count += 1
    
        # 搜索路径
        def search_path(self):
    
            # 初始化数据
            self.__clean_data()
    
            # 搜素路径,遍历完所有城市为止
            while self.move_count < city_num:
                # 移动到下一个城市
                next_city = self.__choice_next_city()
                self.__move(next_city)
    
            # 计算路径总长度
            self.__cal_total_distance()
    
    
    # ----------- TSP问题 -----------
    
    class TSP(object):
    
        def __init__(self, root, width=800, height=600, n=city_num):
    
            # 创建画布
            self.root = root
            self.width = width
            self.height = height
            # 城市数目初始化为city_num
            self.n = n
            # tkinter.Canvas
            self.canvas = tkinter.Canvas(
                root,
                width=self.width,
                height=self.height,
                bg="#EBEBEB",  # 背景白色
                xscrollincrement=1,
                yscrollincrement=1
            )
            self.canvas.pack(expand=tkinter.YES, fill=tkinter.BOTH)
            self.title("TSP蚁群算法(n:初始化 e:开始搜索 s:停止搜索 q:退出程序)")
            self.__r = 5
            self.__lock = threading.RLock()  # 线程锁
    
            self.__bindEvents()
            self.new()
    
            # 计算城市之间的距离
            for i in range(city_num):
                for j in range(city_num):
                    temp_distance = pow((distance_x[i] - distance_x[j]), 2) + pow((distance_y[i] - distance_y[j]), 2)
                    temp_distance = pow(temp_distance, 0.5)
                    distance_graph[i][j] = float(int(temp_distance + 0.5))
    
        # 按键响应程序
        def __bindEvents(self):
    
            self.root.bind("q", self.quite)  # 退出程序
            self.root.bind("n", self.new)  # 初始化
            self.root.bind("e", self.search_path)  # 开始搜索
            self.root.bind("s", self.stop)  # 停止搜索
    
        # 更改标题
        def title(self, s):
    
            self.root.title(s)
    
        # 初始化
        def new(self, evt=None):
    
            # 停止线程
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
    
            self.clear()  # 清除信息
            self.nodes = []  # 节点坐标
            self.nodes2 = []  # 节点对象
    
            # 初始化城市节点
            for i in range(len(distance_x)):
                # 在画布上随机初始坐标
                x = distance_x[i]
                y = distance_y[i]
                self.nodes.append((x, y))
                # 生成节点椭圆,半径为self.__r
                node = self.canvas.create_oval(x - self.__r,
                                               y - self.__r, x + self.__r, y + self.__r,
                                               fill="#ff0000",  # 填充红色
                                               outline="#000000",  # 轮廓白色
                                               tags="node",
                                               )
                self.nodes2.append(node)
                # 显示坐标
                self.canvas.create_text(x, y - 10,  # 使用create_text方法在坐标(302,77)处绘制文字
                                        text='(' + str(x) + ',' + str(y) + ')',  # 所绘制文字的内容
                                        fill='black'  # 所绘制文字的颜色为灰色
                                        )
    
            # 顺序连接城市
            # self.line(range(city_num))
    
            # 初始城市之间的距离和信息素
            for i in range(city_num):
                for j in range(city_num):
                    pheromone_graph[i][j] = 1.0
    
            self.ants = [Ant(ID) for ID in range(ant_num)]  # 初始蚁群
            self.best_ant = Ant(-1)  # 初始最优解
            self.best_ant.total_distance = 1 << 31  # 初始最大距离
            self.iter = 1  # 初始化迭代次数
    
        # 将节点按order顺序连线
        def line(self, order):
            # 删除原线
            self.canvas.delete("line")
    
            def line2(i1, i2):
                p1, p2 = self.nodes[i1], self.nodes[i2]
                self.canvas.create_line(p1, p2, fill="#000000", tags="line")
                return i2
    
            # order[-1]为初始值
            reduce(line2, order, order[-1])
    
        # 清除画布
        def clear(self):
            for item in self.canvas.find_all():
                self.canvas.delete(item)
    
        # 退出程序
        def quite(self, evt):
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
            self.root.destroy()
            print(u"\n程序已退出...")
            sys.exit()
    
        # 停止搜索
        def stop(self, evt):
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
    
        # 开始搜索
        def search_path(self, evt=None):
    
            # 开启线程
            self.__lock.acquire()
            self.__running = True
            self.__lock.release()
    
            while self.__running:
                # 遍历每一只蚂蚁
                for ant in self.ants:
                    # 搜索一条路径
                    ant.search_path()
                    # 与当前最优蚂蚁比较
                    if ant.total_distance < self.best_ant.total_distance:
                        # 更新最优解
                        self.best_ant = copy.deepcopy(ant)
                # 更新信息素
                self.__update_pheromone_gragh()
                print(u"迭代次数:", self.iter, u"最佳路径总距离:", int(self.best_ant.total_distance))
                # 连线
                self.line(self.best_ant.path)
                # 设置标题
                self.title("TSP蚁群算法(n:随机初始 e:开始搜索 s:停止搜索 q:退出程序) 迭代次数: %d" % self.iter)
                # 更新画布
                self.canvas.update()
                self.iter += 1
    
        # 更新信息素
        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]
    
        # 主循环
        def mainloop(self):
            self.root.mainloop()
    
    
    # ----------- 程序的入口处 -----------
    
    if __name__ == '__main__':
        
        TSP(tkinter.Tk()).mainloop()
    
    
    

    结果
    在这里插入图片描述

    展开全文
  • 蚁群算法 matlab—python

    2019-08-14 09:57:53
    蚁群算法: >> %%%蚁群算法解决TSP问题%%%%%%% clear all; %清除所有变量 close all; %清图 m=50;% m 蚂蚁个数 Alpha=1; %%Alpha 表征信息素重要程度的参数 Beta=5; %Beta 表征启发式因子重要程度的参数 Rho=...

    TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次(通过禁忌表),而且最后要回到原来出发的城市,要求路径的总和最小

    蚁群算法(AG)是一种模拟蚂蚁觅食行为的模拟优化算法,首先使用在解决TSP(旅行商问题)上。

    人工蚁群与真实蚁群对比:

    相同点不同点
    都是为了寻找最短路径问题人工蚁群具有记忆功能
    都存在个体间的信息交互问题人工蚁群的选择并不盲目性
    都采用根据当前的信息进行随机选择策略人工蚂蚁生活在离散的时间环境中

    代码部分:
    蚁群算法实现核心有两点:1,蚂蚁如何选择下一个城市;2,城市间路径信息素如何更新。

    a. 计算城市之间的转移概率:
    在这里插入图片描述

    % 计算城市之间的转移概率
    for k = 1:length(allow)
    P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta;
    %等式的分子
    End
    P = P/sum(P);  %上面等式的分母部分
    
    

    在计算出来城市之间的转移概率之后还要用轮盘赌法的原因:
    在得到剩下去城市概率,产生一个随机数,基于随机数决定去下面哪一个城市。例如:剩3个城市,概率为:0.1,0.2,0.7,累计概率为:0.1,0.3,0.7,产生一个随机数,随机数为0.21(介于0.1到0.3之间),则去城市2(偏向于选择最大的)。此过程则为轮盘赌,又可说其服从蚁群算法会优先去概率大的地方,但还是随机走。
    原文:https://blog.csdn.net/Sue_qx/article/details/82149965

    蚁群算法:

    >> %%%蚁群算法解决TSP问题%%%%%%%
    
    clear all; %清除所有变量
    close all; %清图
    m=50;% m 蚂蚁个数
    Alpha=1; %%Alpha 表征信息素重要程度的参数
    Beta=5; %Beta 表征启发式因子重要程度的参数
    Rho=0.1; %%Rho 信息素蒸发系数
    NC_max=200; %%最大迭代次数
    Q=100; %%信息素增加强度系数
    C=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1004;4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2367;3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975];                %%31个省会坐标
    %% 主要符号说明
    %% C n个城市的坐标,n*2的矩阵
    %% NC_max 最大迭代次数
    %% m 蚂蚁个数
    %% Alpha 表征信息素重要程度的参数
    %% Beta 表征启发式因子重要程度的参数
    %% Rho 信息素蒸发系数
    %% R_best 各代最佳路线
    %% L_best 各代最佳路线的长度
    
    %% 第一步:变量初始化
    n=size(C,1);%n表示问题的规模(城市个数)         //求出城市的个数
    D=zeros(n,n);%D表示完全图的赋权邻接矩阵        //用来生成n行n列的零
    for i=1:n
         for j=1:n
             if i~=j % ~=相当于C中的!=,即不等于
                D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;    % //D在这里表示的是距离(一个城市到 下一个城市)  当执行一次i,执行n次j时表示的是第一个城市到其他城市的距离。
             else 
                D(i,j)=eps; %i=j时不计算,应该为0,但后面的启发因子要取倒数,用eps(浮点相对精度)表示                           意思是同一个省会城市之间的距离为零
             end
             D(j,i)=D(i,j); %对称矩阵
         end
    end
    Eta=1./D; %Eta为启发因子,这里设为距离的倒数
    Tau=ones(n,n); %Tau为信息素矩阵                //矩阵n*n全部赋值为1
    Tabu=zeros(m,n);%存储并记录路径的生成          //矩阵n*n全部赋值为0
    NC=1; %迭代计数器,记录迭代次数
    R_best=zeros(NC_max,n); %各代最佳路线
    L_best=inf.*ones(NC_max,1); %各代最佳路线的长度   //Inf*ones(1,N) 1、inf代表正无穷,是一个数字                        2、ones(1,N)代表建立一个矩阵,这个矩阵元素全是1,矩阵的尺寸是1行×N列
                          % 3、两者相乘的结果为一个矩阵,该矩阵尺寸也为1行×N列,只不过元素全为正无穷inf 
    L_ave=zeros(NC_max,1); %各代路线的平均长度     //比如a=zeros(3,5);就是创建一个3行5列的0矩阵
    
    
    while NC<=NC_max %停止条件之一:达到最大迭代次数,停止
      
    %%第二步:将M只蚂蚁放到N个城市上
       Randpos=[]; %随即存取
       for i=1:(ceil(m/n))                        % //ceil 是向离它最近的大整数圆整. 如a = [-1.9, -0.2, 3.4, 5.6, 7, 2.4+3.6i]  圆整后:a=[-1,0, 4, 6, 7 ,3+4i]
           Randpos=[Randpos,randperm(n)];          %//randperm的函数功能:随机打乱一个数字序列
       end
       Tabu(:,1)=(Randpos(1,1:m))';
    
    %//蚂蚁重复城市的次数,比如5个蚂蚁放到4个城市,需要重复两遍才能放完蚂蚁,每次循环产生n个1---n的随机数,相当于随机n个城市,产生城市序列(城市序号出现的次数代表的是有几只蚂蚁在这座城市)
    % 循环结束
    % Tabu一句表示将m个蚂蚁随机,每个蚂蚁放到前面产生的城市序列中,每个蚂蚁一个城市,需要m个,所以提取前面1:m个序列                         
    % '表示转置,没有多大用处,可能参与后面的计算方便。
    % 我感觉如果m,n很大的话,你这样做会产生很大的浪费,计算很多的随机数,这样的话更好,一句就得:(如果变量Randpos后面没有用到的话,如果用到了,还要用你的程序)
    
    
    
    
        
         %%第三步:m只蚂蚁按概率函数选择下一座城市,完成各自的周游
         for j=2:n %所在城市不计算
             for i=1:m  %一只一只访问城市
                 visited=Tabu(i,1:(j-1)); %记录已访问的城市,避免重复访问
                 J=zeros(1,(n-j+1)); %待访问的城市
                 P=J; %待访问城市的选择概率分布
                 Jc=1; 
                 for k=1:n
                   if length(find(visited==k))==0 %开始时置0
                        J(Jc)=k;
                        Jc=Jc+1;   %访问的城市个数自加1
                   end
                 end
                 %下面计算待选城市的概率分布
                 for k=1:length(J)  
                    P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);  
                 end  
                 P=P/(sum(P)); %按概率原则选取下一个城市
                 Pcum=cumsum(P); %cumsum,元素累加即求和
                 Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线
                 to_visit=J(Select(1));
                 Tabu(i,j)=to_visit;
              end
          end
    if NC>=2  % 迭代次数NC
       Tabu(1,:)=R_best(NC-1,:);
    end
    
    %%第四步: 记录本次迭代最佳路线长度
    L=zeros(m,1);%开始距离为0,m*1的列向量
    for i=1:m
       R=Tabu(i,:);
       for j=1:(n-1)
          L(i)=L(i)+D(R(j),R(j+1)); %原距离加上第j个城市到第j+1个城市的距离
       end
          L(i)=L(i)+D(R(1),R(n));   %一轮下来后走过的距离
       end
    L_best(NC)=min(L);  %最佳距离取最小
    pos=find(L==L_best(NC));
    R_best(NC,:)=Tabu(pos(1),:);%此轮迭代后的最佳路线
    L_ave(NC)=mean(L);%此轮迭代后的平均距离
    NC=NC+1; %迭代继续
    
    
    %%第五步:更新信息素
    Delta_Tau=zeros(n,n); %开始时信息素为n*n的矩阵
    for i=1:m
      for j=1:(n-1)
        Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i); %此次循环在路径(i,j)上的信息素增量 
      end
      Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i); %此次循环在整个路径上的信息素增量
    end
    
    Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发,更新后的信息素
    
    
    %%第六步:禁忌表清零
    Tabu=zeros(m,n);  %%直到最大的迭代次数
    end
    
    %%第七步:输出结果
    Pos=find(L_best==min(L_best)); %找到最佳路径(非0为真)
    Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径
    Shortest_Length=L_best(Pos(1)) %最大迭代次数后最短距离
    
    figure(1)
    plot(L_best)
    xlabel('迭代次数')
    ylabel('目标函数值')
    title('适应度进化曲线')
    
    figure(2)
    subplot(1,2,1)    %绘制第一个子图形
    %% subplot(m,n,p)生成m*n个子图,当前激活第p个子图
    %画路线图
    %%============================================================
    %% DrawRoute.m
    %%画路线图
    %%————————————————————————————
    %% C Coordinate 节点坐标,由一个N*2的矩阵存储
    %% R Route 路线
    %%============================================================
    N=length(R);
    scatter(C(:,1),C(:,2));
    hold on
    %% scatter(X,Y) 中 X和Y是数据向量,以X中数据为横坐标,以Y中数据位纵坐标描绘散点图,点的形状默认使用圈
    
    plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)],'g')
    hold on
    
    for ii=2:N
    plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'g')
    hold on 
    end
    
    title('旅行商问题优化结果')
     
    subplot(1,2,2)  %绘制第二个子图
    plot(L_best)
    hold on  %保持图形
    plot(L_ave,'r')
    title('平均距离和最短距离')   %标题
    

    在这里插入图片描述
    在这里插入图片描述

    MATLAB中cumsum函数问题参考链接:https://blog.csdn.net/weixin_43283397/article/details/99546762


    以下两个代码均为转载,欢迎访问原博客
    蚁群算法Python3可运行代码
    蚁群算法原理及其实现(python)


    import numpy as np
    import matplotlib.pyplot as plt
    import pylab
    
    coordinates = np.array([[565.0, 575.0], [25.0, 185.0], [345.0, 750.0], [945.0, 685.0], [845.0, 655.0],
                            [880.0, 660.0], [25.0, 230.0], [525.0, 1000.0], [580.0, 1175.0], [650.0, 1130.0],
                            [1605.0, 620.0], [1220.0, 580.0], [1465.0, 200.0], [1530.0, 5.0], [845.0, 680.0],
                            [725.0, 370.0], [145.0, 665.0], [415.0, 635.0], [510.0, 875.0], [560.0, 365.0],
                            [300.0, 465.0], [520.0, 585.0], [480.0, 415.0], [835.0, 625.0], [975.0, 580.0],
                            [1215.0, 245.0], [1320.0, 315.0], [1250.0, 400.0], [660.0, 180.0], [410.0, 250.0],
                            [420.0, 555.0], [575.0, 665.0], [1150.0, 1160.0], [700.0, 580.0], [685.0, 595.0],
                            [685.0, 610.0], [770.0, 610.0], [795.0, 645.0], [720.0, 635.0], [760.0, 650.0],
                            [475.0, 960.0], [95.0, 260.0], [875.0, 920.0], [700.0, 500.0], [555.0, 815.0],
                            [830.0, 485.0], [1170.0, 65.0], [830.0, 610.0], [605.0, 625.0], [595.0, 360.0],
                            [1340.0, 725.0], [1740.0, 245.0]])
    
    
    def getdistmat(coordinates):
        num = coordinates.shape[0]
        distmat = np.zeros((52, 52))
        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
    
    
    distmat = getdistmat(coordinates)
    numant = 40  # 蚂蚁个数
    numcity = coordinates.shape[0]  # 城市个数
    alpha = 1  # 信息素重要程度因子
    beta = 5  # 启发函数重要程度因子
    rho = 0.1  # 信息素的挥发速度
    Q = 1
    iter = 0
    itermax = 250
    etatable = 1.0 / (distmat + np.diag([1e10] * numcity))  # 启发函数矩阵,表示蚂蚁从城市i转移到矩阵j的期望程度
    pheromonetable = np.ones((numcity, numcity))  # 信息素矩阵
    pathtable = np.zeros((numant, numcity)).astype(int)  # 路径记录表
    distmat = getdistmat(coordinates)  # 城市的距离矩阵
    lengthaver = np.zeros(itermax)  # 各代路径的平均长度
    lengthbest = np.zeros(itermax)  # 各代及其之前遇到的最佳路径长度
    pathbest = np.zeros((itermax, numcity))  # 各代及其之前遇到的最佳路径长度
    
    while iter < itermax:
        # 随机产生各个蚂蚁的起点城市
        if numant <= numcity:  # 城市数比蚂蚁数多
            pathtable[:, 0] = np.random.permutation(range(0, numcity))[:numant]
        else:  # 蚂蚁数比城市数多,需要补足
            pathtable[:numcity, 0] = np.random.permutation(range(0, numcity))[:]
            pathtable[numcity:, 0] = np.random.permutation(range(0, numcity))[:numant - numcity]
        length = np.zeros(numant)  # 计算各个蚂蚁的路径距离
        for i in range(numant):
            visiting = pathtable[i, 0]  # 当前所在的城市
            unvisited = set(range(numcity))  # 未访问的城市,以集合的形式存储{}
            unvisited.remove(visiting)  # 删除元素;利用集合的remove方法删除存储的数据内容
            for j in range(1, numcity):  # 循环numcity-1次,访问剩余的numcity-1个城市
                # 每次用轮盘法选择下一个要访问的城市
                listunvisited = list(unvisited)
                probtrans = np.zeros(len(listunvisited))
                for k in range(len(listunvisited)):
                    probtrans[k] = np.power(pheromonetable[visiting][listunvisited[k]], alpha) \
                                   * np.power(etatable[visiting][listunvisited[k]], alpha)
                cumsumprobtrans = (probtrans / sum(probtrans)).cumsum()
                cumsumprobtrans -= np.random.rand()
                k = listunvisited[(np.where(cumsumprobtrans > 0)[0])[0]]  # python3中原代码运行bug,类型问题;鉴于此特找到其他方法
                # 通过where()方法寻找矩阵大于0的元素的索引并返回ndarray类型,然后接着载使用[0]提取其中的元素,用作listunvisited列表中
                # 元素的提取(也就是下一轮选的城市)
                pathtable[i, j] = k  # 添加到路径表中(也就是蚂蚁走过的路径)
                unvisited.remove(k)  # 然后在为访问城市set中remove()删除掉该城市
                length[i] += distmat[visiting][k]
                visiting = k
            length[i] += distmat[visiting][pathtable[i, 0]]  # 蚂蚁的路径距离包括最后一个城市和第一个城市的距离
            # 包含所有蚂蚁的一个迭代结束后,统计本次迭代的若干统计参数
        lengthaver[iter] = length.mean()
        if iter == 0:
            lengthbest[iter] = length.min()
            pathbest[iter] = pathtable[length.argmin()].copy()
        else:
            if length.min() > lengthbest[iter - 1]:
                lengthbest[iter] = lengthbest[iter - 1]
                pathbest[iter] = pathbest[iter - 1].copy()
            else:
                lengthbest[iter] = length.min()
                pathbest[iter] = pathtable[length.argmin()].copy()
        # 更新信息素
        changepheromonetable = np.zeros((numcity, numcity))
        for i in range(numant):
            for j in range(numcity - 1):
                changepheromonetable[pathtable[i, j]][pathtable[i, j + 1]] += Q / distmat[pathtable[i, j]][
                    pathtable[i, j + 1]]  # 计算信息素增量
            changepheromonetable[pathtable[i, j + 1]][pathtable[i, 0]] += Q / distmat[pathtable[i, j + 1]][pathtable[i, 0]]
        pheromonetable = (1 - rho) * pheromonetable + changepheromonetable  # 计算信息素公式
        iter += 1  # 迭代次数指示器+1
        print("iter:", iter)
    
    # 做出平均路径长度和最优路径长度
    fig, axes = plt.subplots(nrows=2, ncols=1, figsize=(12, 10))
    axes[0].plot(lengthaver, 'k', marker=u'')
    axes[0].set_title('Average Length')
    axes[0].set_xlabel(u'iteration')
    
    axes[1].plot(lengthbest, 'k', marker=u'')
    axes[1].set_title('Best Length')
    axes[1].set_xlabel(u'iteration')
    fig.savefig('average_best.png', dpi=500, bbox_inches='tight')
    plt.show()
    
    # 作出找到的最优路径图
    bestpath = pathbest[-1]
    plt.plot(coordinates[:, 0], coordinates[:, 1], 'r.', marker=u'$\cdot$')
    plt.xlim([-100, 2000])
    plt.ylim([-100, 1500])
    
    for i in range(numcity - 1):
        m = int(bestpath[i])
        n = int(bestpath[i + 1])
        plt.plot([coordinates[m][0], coordinates[n][0]], [coordinates[m][1], coordinates[n][1]], 'k')
    plt.plot([coordinates[int(bestpath[0])][0],coordinates[int(n)][0]],[coordinates[int(bestpath[0])][1],coordinates[int(n)][1]],'b')
    ax = plt.gca()
    ax.set_title("Best Path")
    ax.set_xlabel('X axis')
    ax.set_ylabel('Y_axis')
    
    plt.savefig('best path.png', dpi=500, bbox_inches='tight')
    plt.show()
    
    

    这篇博客里的代码好玩

    # -*- coding: utf-8 -*-
    import random
    import copy
    import time
    import sys
    import math
    import tkinter #//GUI模块
    import threading
    from functools import reduce
    
    
    # 参数
    '''
    ALPHA:信息启发因子,值越大,则蚂蚁选择之前走过的路径可能性就越大
          ,值越小,则蚁群搜索范围就会减少,容易陷入局部最优
    BETA:Beta值越大,蚁群越就容易选择局部较短路径,这时算法收敛速度会
         加快,但是随机性不高,容易得到局部的相对最优
    '''
    (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)]
    
    
    
    #----------- 蚂蚁 -----------
    class Ant(object):
    
        # 初始化
        def __init__(self,ID):
    
            self.ID = 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_city = [True for i in range(city_num)] # 探索城市的状态
    
            city_index = random.randint(0,city_num-1) # 随机初始出生点
            self.current_city = city_index
            self.path.append(city_index)
            self.open_table_city[city_index] = False
            self.move_count = 1
    
        # 选择下一个城市
        def __choice_next_city(self):
    
            next_city = -1
            select_citys_prob = [0.0 for i in range(city_num)]  #存储去下个城市的概率
            total_prob = 0.0
    
            # 获取去下一个城市的概率
            for i in range(city_num):
                if self.open_table_city[i]:
                    try :
                        # 计算概率:与信息素浓度成正比,与距离成反比
                        select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) * pow((1.0/distance_graph[self.current_city][i]), BETA)
                        total_prob += select_citys_prob[i]
                    except ZeroDivisionError as e:
                        print ('Ant ID: {ID}, current city: {current}, target city: {target}'.format(ID = self.ID, current = self.current_city, target = i))
                        sys.exit(1)
    
            # 轮盘选择城市
            if total_prob > 0.0:
                # 产生一个随机概率,0.0-total_prob
                temp_prob = random.uniform(0.0, total_prob)
                for i in range(city_num):
                    if self.open_table_city[i]:
                        # 轮次相减
                        temp_prob -= select_citys_prob[i]
                        if temp_prob < 0.0:
                            next_city = i
                            break
    
            # 未从概率产生,顺序选择一个未访问城市
            # if next_city == -1:
            #     for i in range(city_num):
            #         if self.open_table_city[i]:
            #             next_city = i
            #             break
    
            if (next_city == -1):
                next_city = random.randint(0, city_num - 1)
                while ((self.open_table_city[next_city]) == False):  # if==False,说明已经遍历过了
                    next_city = random.randint(0, city_num - 1)
    
            # 返回下一个城市序号
            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.open_table_city[next_city] = False
            self.total_distance += distance_graph[self.current_city][next_city]
            self.current_city = next_city
            self.move_count += 1
    
        # 搜索路径
        def search_path(self):
    
            # 初始化数据
            self.__clean_data()
    
            # 搜素路径,遍历完所有城市为止
            while self.move_count < city_num:
                # 移动到下一个城市
                next_city =  self.__choice_next_city()
                self.__move(next_city)
    
            # 计算路径总长度
            self.__cal_total_distance()
    
    #----------- TSP问题 -----------
    
    class TSP(object):
    
        def __init__(self, root, width = 800, height = 600, n = city_num):
    
            # 创建画布
            self.root = root
            self.width = width
            self.height = height
            # 城市数目初始化为city_num
            self.n = n
            # tkinter.Canvas
            self.canvas = tkinter.Canvas(
                    root,
                    width = self.width,
                    height = self.height,
                    bg = "#EBEBEB",             # 背景白色
                    xscrollincrement = 1,
                    yscrollincrement = 1
                )
            self.canvas.pack(expand = tkinter.YES, fill = tkinter.BOTH)
            self.title("TSP蚁群算法(n:初始化 e:开始搜索 s:停止搜索 q:退出程序)")
            self.__r = 5
            self.__lock = threading.RLock()     # 线程锁
    
            self.__bindEvents()
            self.new()
    
            # 计算城市之间的距离
            for i in range(city_num):
                for j in range(city_num):
                    temp_distance = pow((distance_x[i] - distance_x[j]), 2) + pow((distance_y[i] - distance_y[j]), 2)
                    temp_distance = pow(temp_distance, 0.5)
                    distance_graph[i][j] =float(int(temp_distance + 0.5))
    
        # 按键响应程序
        def __bindEvents(self):
    
            self.root.bind("q", self.quite)        # 退出程序
            self.root.bind("n", self.new)          # 初始化
            self.root.bind("e", self.search_path)  # 开始搜索
            self.root.bind("s", self.stop)         # 停止搜索
    
        # 更改标题
        def title(self, s):
    
            self.root.title(s)
    
        # 初始化
        def new(self, evt = None):
    
            # 停止线程
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
    
            self.clear()     # 清除信息
            self.nodes = []  # 节点坐标
            self.nodes2 = [] # 节点对象
    
            # 初始化城市节点
            for i in range(len(distance_x)):
                # 在画布上随机初始坐标
                x = distance_x[i]
                y = distance_y[i]
                self.nodes.append((x, y))
                # 生成节点椭圆,半径为self.__r
                node = self.canvas.create_oval(x - self.__r,
                        y - self.__r, x + self.__r, y + self.__r,
                        fill = "#ff0000",      # 填充红色
                        outline = "#000000",   # 轮廓白色
                        tags = "node",
                    )
                self.nodes2.append(node)
                # 显示坐标
                self.canvas.create_text(x,y-10,              # 使用create_text方法在坐标(302,77)处绘制文字
                        text = '('+str(x)+','+str(y)+')',    # 所绘制文字的内容
                        fill = 'black'                       # 所绘制文字的颜色为灰色
                    )
    
            # 顺序连接城市
            #self.line(range(city_num))
    
            # 初始城市之间的距离和信息素
            for i in range(city_num):
                for j in range(city_num):
                    pheromone_graph[i][j] = 1.0
    
            self.ants = [Ant(ID) for ID in range(ant_num)]  # 初始蚁群
            self.best_ant = Ant(-1)                          # 初始最优解
            self.best_ant.total_distance = 1 << 31           # 初始最大距离
            self.iter = 1                                    # 初始化迭代次数
    
        # 将节点按order顺序连线
        def line(self, order):
            # 删除原线
            self.canvas.delete("line")
            def line2(i1, i2):
                p1, p2 = self.nodes[i1], self.nodes[i2]
                self.canvas.create_line(p1, p2, fill = "#000000", tags = "line")
                return i2
    
            # order[-1]为初始值
            reduce(line2, order, order[-1])
    
        # 清除画布
        def clear(self):
            for item in self.canvas.find_all():
                self.canvas.delete(item)
    
        # 退出程序
        def quite(self, evt):
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
            self.root.destroy()
            print (u"\n程序已退出...")
            sys.exit()
    
        # 停止搜索
        def stop(self, evt):
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
    
        # 开始搜索
        def search_path(self, evt = None):
    
            # 开启线程
            self.__lock.acquire()
            self.__running = True
            self.__lock.release()
    
            while self.__running:
                # 遍历每一只蚂蚁
                for ant in self.ants:
                    # 搜索一条路径
                    ant.search_path()
                    # 与当前最优蚂蚁比较
                    if ant.total_distance < self.best_ant.total_distance:
                        # 更新最优解
                        self.best_ant = copy.deepcopy(ant)
                # 更新信息素
                self.__update_pheromone_gragh()
                print (u"迭代次数:",self.iter,u"最佳路径总距离:",int(self.best_ant.total_distance))
                # 连线
                self.line(self.best_ant.path)
                # 设置标题
                self.title("TSP蚁群算法(n:随机初始 e:开始搜索 s:停止搜索 q:退出程序) 迭代次数: %d" % self.iter)
                # 更新画布
                self.canvas.update()
                self.iter += 1
    
        # 更新信息素
        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]
    
        # 主循环
        def mainloop(self):
            self.root.mainloop()
    
    #----------- 程序的入口处 -----------
    
    if __name__ == '__main__':
    
        print (u"""
    --------------------------------------------------------
        程序:蚁群算法解决TPS问题程序
        作者:许彬
        日期:2015-12-10
        语言:Python 2.7
        说明:转载程序,大家可访问原博客
    --------------------------------------------------------
        """)
        TSP(tkinter.Tk()).mainloop()
    
    
    展开全文
  • 蚁群算法路径规划三维与二维环境

    千次阅读 2019-04-13 19:14:36
    需要的加Q1104498813
    展开全文
  • 蚁群算法原理及python代码实现

    千次阅读 多人点赞 2020-04-04 22:26:20
    蚁群算法(AG)是一种模拟蚂蚁觅食行为的模拟优化算法,它是由意大利学者Dorigo M等人于1991年首先...蚁群算法的基本思想:蚁群算法的基本原理:1、蚂蚁在路径上释放信息素。2、碰到还没走过的路口,就随机挑选一条路走...

    本文转载自:https://blog.csdn.net/fanxin_i/article/details/80380733

    蚁群算法(AG)是一种模拟蚂蚁觅食行为的模拟优化算法,它是由意大利学者Dorigo M等人于1991年首先提出,并首先使用在解决TSP(旅行商问题)上。
    之后,又系统研究了蚁群算法的基本原理和数学模型.
    蚁群算法的基本思想:


    蚁群算法的基本原理:

    1、蚂蚁在路径上释放信息素。

    2、碰到还没走过的路口,就随机挑选一条路走。同时,释放与路径长度有关的信息素。

    3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时,就选择信息素浓度较高路径。

    4、最优路径上的信息素浓度越来越大。

    5、最终蚁群找到最优寻食路径。

    人工蚁群与真实蚁群对比:

    基于TSP问题的基本蚁群算法:

    TSP求解中,假设蚁群算法中的每只蚂蚁是具有以下特征的简单智能体:

    每次周游,每只蚂蚁在其经过的支路(i,j)上都留下信息素。

    ‚蚂蚁选择城市的概率与城市之间的距离和当前连接支路上所包含的信息素余量有关。

    ƒ为了强制蚂蚁进行合法的周游,直到一次周游完成后,才允许蚂蚁游走已访问过的城市(这可由禁忌表来控制)。

    基本蚁群的两个过程:

    (1)状态转移

    (2)信息素更新

    (1)状态转移

    为了避免残留信息素过多而淹没启发信息,在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后,要对残留信息进行更新处理。

    由此,t+n时刻在路径(i,j)上的信息量可按如下规则进行调整: 

    (2)信息素更新模型

    蚁周模型(Ant-Cycle模型)

    蚁量模型(Ant-Quantity模型)

    蚁密模型(Ant-Density模型)

    区别:

    1.蚁周模型利用的是全局信息,即蚂蚁完成一个循环后更新所有路径上的信息素;

    2.蚁量和蚁密模型利用的是局部信息,即蚂蚁完成一步后更新路径上的信息素。

    蚁群算法基本流程:

    蚁群算法中主要参数的选择:

    蚁群算法中主要参数的理想选择如下:

    国内外,对于离散域蚁群算法的改进研究成果很多,例如自适应蚁群算法、基于信息素扩散的蚁群算法等,这里仅介绍离散域优化问题的自适应蚁群算法。

    自适应蚁群算法:对蚁群算法的状态转移概率、信息素挥发因子、信息量等因素采用自适应调节策略为一种基本改进思路的蚁群算法。

    自适应蚁群算法中两个最经典的方法:蚁群系统(AntColony System, ACS)和最大-最小蚁群系统(MAX-MINAnt System, MMAS)。

    蚁群系统对基本蚁群算法改进:

    ①蚂蚁的状态转移规则不同;

    ②全局更新规则不同;


    ③新增了对各条路径信息量调整的局部更新规则

    下面是Python实现求50个城市之间最短距离的代码

    # -*- coding: utf-8 -*-
    import random
    import copy
    import time
    import sys
    import math
    import tkinter #//GUI模块
    import threading
    from functools import reduce
     
     
    # 参数
    '''
    ALPHA:信息启发因子,值越大,则蚂蚁选择之前走过的路径可能性就越大
          ,值越小,则蚁群搜索范围就会减少,容易陷入局部最优
    BETA:Beta值越大,蚁群越就容易选择局部较短路径,这时算法收敛速度会
         加快,但是随机性不高,容易得到局部的相对最优
    '''
    (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)]
     
     
     
    #----------- 蚂蚁 -----------
    class Ant(object):
     
        # 初始化
        def __init__(self,ID):
            
            self.ID = 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_city = [True for i in range(city_num)] # 探索城市的状态
            
            city_index = random.randint(0,city_num-1) # 随机初始出生点
            self.current_city = city_index
            self.path.append(city_index)
            self.open_table_city[city_index] = False
            self.move_count = 1
        
        # 选择下一个城市
        def __choice_next_city(self):
            
            next_city = -1
            select_citys_prob = [0.0 for i in range(city_num)]  #存储去下个城市的概率
            total_prob = 0.0
     
            # 获取去下一个城市的概率
            for i in range(city_num):
                if self.open_table_city[i]:
                    try :
                        # 计算概率:与信息素浓度成正比,与距离成反比
                        select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) * pow((1.0/distance_graph[self.current_city][i]), BETA)
                        total_prob += select_citys_prob[i]
                    except ZeroDivisionError as e:
                        print ('Ant ID: {ID}, current city: {current}, target city: {target}'.format(ID = self.ID, current = self.current_city, target = i))
                        sys.exit(1)
            
            # 轮盘选择城市
            if total_prob > 0.0:
                # 产生一个随机概率,0.0-total_prob
                temp_prob = random.uniform(0.0, total_prob)
                for i in range(city_num):
                    if self.open_table_city[i]:
                        # 轮次相减
                        temp_prob -= select_citys_prob[i]
                        if temp_prob < 0.0:
                            next_city = i
                            break
     
            # 未从概率产生,顺序选择一个未访问城市
            # if next_city == -1:
            #     for i in range(city_num):
            #         if self.open_table_city[i]:
            #             next_city = i
            #             break
     
            if (next_city == -1):
                next_city = random.randint(0, city_num - 1)
                while ((self.open_table_city[next_city]) == False):  # if==False,说明已经遍历过了
                    next_city = random.randint(0, city_num - 1)
     
            # 返回下一个城市序号
            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.open_table_city[next_city] = False
            self.total_distance += distance_graph[self.current_city][next_city]
            self.current_city = next_city
            self.move_count += 1
            
        # 搜索路径
        def search_path(self):
     
            # 初始化数据
            self.__clean_data()
     
            # 搜素路径,遍历完所有城市为止
            while self.move_count < city_num:
                # 移动到下一个城市
                next_city =  self.__choice_next_city()
                self.__move(next_city)
     
            # 计算路径总长度
            self.__cal_total_distance()
     
    #----------- TSP问题 -----------
            
    class TSP(object):
     
        def __init__(self, root, width = 800, height = 600, n = city_num):
     
            # 创建画布
            self.root = root                               
            self.width = width      
            self.height = height
            # 城市数目初始化为city_num
            self.n = n
            # tkinter.Canvas
            self.canvas = tkinter.Canvas(
                    root,
                    width = self.width,
                    height = self.height,
                    bg = "#EBEBEB",             # 背景白色 
                    xscrollincrement = 1,
                    yscrollincrement = 1
                )
            self.canvas.pack(expand = tkinter.YES, fill = tkinter.BOTH)
            self.title("TSP蚁群算法(n:初始化 e:开始搜索 s:停止搜索 q:退出程序)")
            self.__r = 5
            self.__lock = threading.RLock()     # 线程锁
     
            self.__bindEvents()
            self.new()
     
            # 计算城市之间的距离
            for i in range(city_num):
                for j in range(city_num):
                    temp_distance = pow((distance_x[i] - distance_x[j]), 2) + pow((distance_y[i] - distance_y[j]), 2)
                    temp_distance = pow(temp_distance, 0.5)
                    distance_graph[i][j] =float(int(temp_distance + 0.5))
     
        # 按键响应程序
        def __bindEvents(self):
     
            self.root.bind("q", self.quite)        # 退出程序
            self.root.bind("n", self.new)          # 初始化
            self.root.bind("e", self.search_path)  # 开始搜索
            self.root.bind("s", self.stop)         # 停止搜索
     
        # 更改标题
        def title(self, s):
     
            self.root.title(s)
     
        # 初始化
        def new(self, evt = None):
     
            # 停止线程
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
     
            self.clear()     # 清除信息 
            self.nodes = []  # 节点坐标
            self.nodes2 = [] # 节点对象
     
            # 初始化城市节点
            for i in range(len(distance_x)):
                # 在画布上随机初始坐标
                x = distance_x[i]
                y = distance_y[i]
                self.nodes.append((x, y))
                # 生成节点椭圆,半径为self.__r
                node = self.canvas.create_oval(x - self.__r,
                        y - self.__r, x + self.__r, y + self.__r,
                        fill = "#ff0000",      # 填充红色
                        outline = "#000000",   # 轮廓白色
                        tags = "node",
                    )
                self.nodes2.append(node)
                # 显示坐标
                self.canvas.create_text(x,y-10,              # 使用create_text方法在坐标(302,77)处绘制文字
                        text = '('+str(x)+','+str(y)+')',    # 所绘制文字的内容
                        fill = 'black'                       # 所绘制文字的颜色为灰色
                    )
                
            # 顺序连接城市
            #self.line(range(city_num))
            
            # 初始城市之间的距离和信息素
            for i in range(city_num):
                for j in range(city_num):
                    pheromone_graph[i][j] = 1.0
                    
            self.ants = [Ant(ID) for ID in range(ant_num)]  # 初始蚁群
            self.best_ant = Ant(-1)                          # 初始最优解
            self.best_ant.total_distance = 1 << 31           # 初始最大距离
            self.iter = 1                                    # 初始化迭代次数 
                
        # 将节点按order顺序连线
        def line(self, order):
            # 删除原线
            self.canvas.delete("line")
            def line2(i1, i2):
                p1, p2 = self.nodes[i1], self.nodes[i2]
                self.canvas.create_line(p1, p2, fill = "#000000", tags = "line")
                return i2
            
            # order[-1]为初始值
            reduce(line2, order, order[-1])
     
        # 清除画布
        def clear(self):
            for item in self.canvas.find_all():
                self.canvas.delete(item)
     
        # 退出程序
        def quite(self, evt):
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
            self.root.destroy()
            print (u"\n程序已退出...")
            sys.exit()
     
        # 停止搜索
        def stop(self, evt):
            self.__lock.acquire()
            self.__running = False
            self.__lock.release()
            
        # 开始搜索
        def search_path(self, evt = None):
     
            # 开启线程
            self.__lock.acquire()
            self.__running = True
            self.__lock.release()
            
            while self.__running:
                # 遍历每一只蚂蚁
                for ant in self.ants:
                    # 搜索一条路径
                    ant.search_path()
                    # 与当前最优蚂蚁比较
                    if ant.total_distance < self.best_ant.total_distance:
                        # 更新最优解
                        self.best_ant = copy.deepcopy(ant)
                # 更新信息素
                self.__update_pheromone_gragh()
                print (u"迭代次数:",self.iter,u"最佳路径总距离:",int(self.best_ant.total_distance))
                # 连线
                self.line(self.best_ant.path)
                # 设置标题
                self.title("TSP蚁群算法(n:随机初始 e:开始搜索 s:停止搜索 q:退出程序) 迭代次数: %d" % self.iter)
                # 更新画布
                self.canvas.update()
                self.iter += 1
     
        # 更新信息素
        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]
     
        # 主循环
        def mainloop(self):
            self.root.mainloop()
     
    #----------- 程序的入口处 -----------
                    
    if __name__ == '__main__':
     
        print (u""" 
    --------------------------------------------------------
        程序:蚁群算法解决TPS问题程序 
        作者:许彬 
        日期:2015-12-10
        语言:Python 2.7 
    -------------------------------------------------------- 
        """)
        TSP(tkinter.Tk()).mainloop()
        
    
    展开全文
  • 蚁群算法代码python 详解版 博文链接:https://blog.csdn.net/quinn1994/article/details/80324308
  • 通过进行三维环境建模,设置可通行区域与禁飞区域,在利用蚁群算法规划无人机的飞行路径,实现三维环境下的路径规划
  • 基本蚁群算法python代码,程序附带测试数据
  • %蚁群算法求解VRP问题有约束函数 Shortest_Route_1=Shortest_Route; %提取最优路线 cc=find(Shortest_Route_1==qidian); xx_1=[]; best_route_2=[]; for i=1:length(cc)-1 if i~=...
  • 蚁群算法的二维路径规划,可以用在机器人的路径规格中,程序详细
  • 5.1 介绍 蚁群优化(ACO)是群体智能的一部分,它模仿蚂蚁的合作行为来解决复杂的组合优化问题。它的概念是由Marco Dorigo[1]和他的同事提出的,当他们观察到这些...蚁群算法是一组被称为人工蚂蚁的软件代理,它们为...
  • python实现蚁群算法

    2019-06-03 00:35:22
    蚁群算法实现,带有注释,并且可以实现可视化找到最佳路径
  • 蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是...
  • python蚁群算法实现

    2018-02-14 09:09:44
    python蚁群算法实现
  • 基于蚁群算法的二维路径规划matlab代码.zip
  • 写在前面 ...遗传算法详解与Python实现在上一篇博客里已经介绍,蚁群算法与遗传算法等仿生进化算法均有共通之处,读者只需要明白透彻其中一种算法的原理和细节,便能触类旁通。因此,今天介绍的是蚁群算
  • 蚁群算法python实现

    2020-05-29 16:18:27
    蚁群算法ACO python实现 1.0版本 sugarMei 2020 5-27 """ # 初始化参数 ''' alpha:信息素影响的强度大小 beta:可见度影响的强度大小 rho:信息素挥发因子 q:常数 用于计算每次一次遍历后的信息素强度变化程度 eta:...
  • 机器人路径规划_蚁群算法

    万次阅读 2015-12-17 16:24:02
    机器人路径规划_蚁群算法 原理 蚁群算法是模拟自然界中蚂蚁的觅食行为而形成的一种群体智能化算法。蚂蚁个体之间信息的传递是通过一种称为信息素的化学物质进行的。蚂蚁在寻找食物的过程中会释放一定量的信息...
  • 蚁群算法(详解)python

    万次阅读 多人点赞 2018-05-15 16:07:32
    代码参考来源:蚁群算法python实现因为要做数学建模,所以学一下蚁群算法。在CSDN中看到这个博客,但是不是很详细,基于此代码为模板,详解一下。旅行商问题(travelling salesman problem,TSP)是物流领域的典型...
  • 这个代码是关于蚁群算法求最短路径的问题,希望对大家有所帮助
  • 1 蚁群算法(ant colony algorithm,ACA)起源和发展历程\ Marco Dorigo等人在研究新型算法的过程中,发现蚁群在寻找食物时,通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标,于是在1991年在其博士...
  • 蚁群算法.python代码

    2020-10-17 11:17:13
    """蚁群算法计算过程如下: (1)初始化。 (2)为每只蚂蚁选择下一个节点。 (3)更新信息素矩阵。 (4)检查终止条件 如果达到最大代数MAX_GEN,算法终止,转到第(5)步;否则,重新初始化所有的蚂蚁的Delt...
  • 附解析思路及源码,需要的小伙伴加油哟
  • 遗传-蚁群算法python实现

    热门讨论 2020-05-31 11:58:56
    为了解决蚁群算法前期因缺乏信息素因素导致的收敛缓慢 利用了遗传算法前期快速收敛的特性 继续前期的遗传变异 旨在若干组的优秀解 为后面蚁群算法的初始化信息素浓度作一个很好的分布 author:sugarMei date:2020 5...
  • 我是在三维网格地图中实现的路径搜索,用的点而不是边来标记信息素的,主要是觉得边要麻烦一些,感兴趣的可以自己实现边标记信息素。蚂蚁在三维地图中走,每次可以上下,左右,斜着走,且都算作等效的一步距离。
  • 1 蚁群算法(ant colony algorithm,ACA)起源和发展历程\ Marco Dorigo等人在研究新型算法的过程中,发现蚁群在寻找食物时,通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标,于是在1991年在其博士...
  • 蚁群算法基本思想蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径问题。根据昆虫学家的观察,发现自然界的蚂蚁虽然视觉不发达,但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径,并且能在环境发生...
  • 蚁群算法Python实现

    万次阅读 多人点赞 2015-04-15 15:10:31
    作者:金良(golden1314521@gmail.com) csdn博客: http://blog.csdn.net/u012176591解决的问题三维地形中,给出起点和重点,找到其最优路径。作图源码:from mpl_toolkits.mplot3d import proj3d from mpl_...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 661
精华内容 264
关键字:

蚁群算法路径规划python

python 订阅