精华内容
下载资源
问答
  • 基本蚁群算法python代码,程序附带测试数据
  • 蚁群算法Python实现.zip

    2020-03-30 22:04:07
    蚁群算法Python 实现。除此之外,还有这些算法的集合:差分进化算法、遗传算法、粒子群算法、模拟退火算法、蚁群算法、免疫优化算法、鱼群算法
  • 蚁群算法python实现

    2020-05-29 16:18:27
    蚁群算法ACO python实现 1.0版本 sugarMei 2020 5-27 """ # 初始化参数 ''' alpha:信息素影响的强度大小 beta:可见度影响的强度大小 rho:信息素挥发因子 q:常数 用于计算每次一次遍历后的信息素强度变化程度 eta:...
    import tkinter
    from functools import reduce
    import time
    
    import numpy as np
    
    """
    蚁群算法ACO python实现
    1.0版本
    sugarMei
    2020 5-27
    
    """
    
    # 初始化参数
    '''
    alpha:信息素影响的强度大小
    beta:可见度影响的强度大小
    rho:信息素挥发因子
    q:常数 用于计算每次一次遍历后的信息素强度变化程度
    eta:从i城市到j城市的可见度
    distance_graph:城市i到j的距离dij
    pheromone:信息素矩阵 pij表示城市i到j城市的边的信息素的大小
    path:路径表 pj表示第j只蚂蚁的路径表
    length:记录一次循环中每个蚂蚁的路径长度li
    '''
    alpha, beta, rho, q, generation, generations = 1, 2, 0.5, 100, 0, 300
    cities, ants = 50, 75
    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 = np.zeros((cities, cities))
    # 画图
    root = tkinter.Tk()
    canvas = tkinter.Canvas(
        root,
        width=800,
        height=600,
        bg="#EBEBEB",  # 背景白色
        xscrollincrement=1,
        yscrollincrement=1
    )
    canvas.pack(expand=tkinter.YES, fill=tkinter.BOTH)
    r = 5
    nodes = []  # 节点坐标
    nodes2 = []  # 节点对象
    # 初始化城市节点
    filename = tkinter.PhotoImage(file="/Users/sugarmei/PycharmProjects/sugarmei/es/city.png")
    
    for i in range(len(distance_x)):
        # 在画布上随机初始坐标
        x = distance_x[i]
        y = distance_y[i]
        nodes.append((x, y))
        # 生成节点椭圆,半径为self.__r
        node = canvas.create_image(x, y, image=filename, tags="node")
        # node = canvas.create_oval(x - r,
        #                           y - r, x + r, y + r,
        #                           fill="#ff0000",  # 填充红色
        #                           outline="#000000",  # 轮廓白色
        #                           tags="node",
        #                           )
        nodes2.append(node)
        # 显示坐标
        canvas.create_text(x, y-20,  # 使用create_text方法在坐标(302,77)处绘制文字
                           text='',  # 所绘制文字的内容
                           fill='black'  # 所绘制文字的颜色为灰色
                           )
    
    
    def title(s):
        root.title(s)
    
    
    # 将节点按order顺序连线
    def line(order):
        # 删除原线
        canvas.delete("line")
    
        def line2(i1, i2):
            p1, p2 = nodes[i1], nodes[i2]
            canvas.create_line(p1, p2, fill="#000000", tags="line")
            return i2
    
        # order[-1]为初始值
        reduce(line2, order, order[-1])
    
    
    # 计算城市之间的距离
    for i in range(cities):
        for j in range(cities):
            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] = temp_distance
    eta = 1.0 / (distance_graph + np.diag([1e10] * cities))
    pheromone = np.ones((cities, cities))
    path = np.zeros((ants, cities), dtype=np.int)
    # 最佳路径
    best_path = []
    best_length = np.inf
    
    while generation < generations:
        # 初始化蚂蚁位置
        if ants < cities:
            path[:, 0] = np.random.permutation(cities)[:ants]
        else:
            path[:cities, 0] = np.random.permutation(cities)[:]
            path[cities:, 0] = np.random.permutation(cities)[:ants - cities]
        length = np.zeros(ants)
        # 计算第k只蚂蚁从i城市到达j城市的概率
        for k in range(ants):
            visited = path[k, 0]
            unvisited = set(range(cities))
            unvisited.remove(visited)
    
            for i in range(1, cities):
                l_unvisited = list(unvisited)
                prob_next_city = np.zeros(len(l_unvisited))
                for j in range(len(l_unvisited)):
                    prob_next_city[j] = pow(pheromone[visited][l_unvisited[j]], alpha) * pow(eta[visited][l_unvisited[j]],
                                                                                             beta)
                prob_next_city = prob_next_city / sum(prob_next_city)
                temp_prob = np.random.random()
                cur_prob = 0
                next_city = -1
                # 轮盘赌算法
                for p in range(len(prob_next_city)):
                    cur_prob += prob_next_city[p]
                    # 第p个城市赌成功
                    if cur_prob >= temp_prob:
                        next_city = l_unvisited[p]
                        break
                unvisited.remove(next_city)
                path[k, i] = next_city
                length[k] += distance_graph[visited][next_city]
                visited = next_city
            length[k] += distance_graph[visited][path[k, 0]]
        # 调整最短长度和最佳路径
        if length.min() < best_length:
            best_length = length.min()
            best_path = path[length.argmin()]
            line(best_path)
        root.title("ACO 第 " + str(generation) + " 次迭代" + " 当前最短长度:" + str(best_length))
        root.update()
    
        # time.sleep(10)
        # 本轮遍历一次全部城市结束 调整信息素强度
        tmp_pheromone = np.zeros((cities, cities))
        for i in range(ants):
            for j in range(cities - 1):
                # 使用了蚁环算法
                # length[i]为第i只蚂蚁当前次遍历的路径长度 作为整体信息进行信息素的更新
                tmp_pheromone[path[i, j]][path[i, j + 1]] += q / length[i]
                # 从j城市到i城市的距离dji与dij一致 因此信息素浓度一致
                if tmp_pheromone[path[i, j + 1]][path[i, j]] < tmp_pheromone[path[i, j]][path[i, j + 1]]:
                    tmp_pheromone[path[i, j + 1]][path[i, j]] = tmp_pheromone[path[i, j]][path[i, j + 1]]
            tmp_pheromone[path[i, cities - 1]][path[i, 0]] += q / length[i]
            # 蚁密算法
            # tmp_pheromone[path[i, j]][path[i, j + 1]] += q
            # tmp_pheromone[path[i, cities - 1]][path[i, 0]] += q
            # 蚁量算法 与当前城市之间距离成反比
            # tmp_pheromone[path[i, j]][path[i, j + 1]] += q / distance_graph[path[i, j]][path[i, j + 1]]
            # tmp_pheromone[path[i, cities - 1]][path[i, 0]] += q / distance_graph[path[i, cities - 1]][path[i, 0]]
        # 更新从i到j城市的路径的信息素浓度
        pheromone = (1 - rho) * pheromone + tmp_pheromone
        generation += 1
        print("当前迭代次数:", generation, "当前最短长度:", best_length)
    
    print("迭代次数:", generations)
    print("最佳路径:", best_path)
    print("最短长度:", best_length)
    
    
    展开全文
  • 遗传-蚁群算法python实现

    热门讨论 2020-05-31 11:58:56
    为了解决蚁群算法前期因缺乏信息素因素导致的收敛缓慢 利用了遗传算法前期快速收敛的特性 继续前期的遗传变异 旨在若干组的优秀解 为后面蚁群算法的初始化信息素浓度作一个很好的分布 author:sugarMei date:2020 5...
    import tkinter
    from functools import reduce
    import numpy as np
    import random
    import math
    
    """
    为了解决蚁群算法前期因缺乏信息素因素导致的收敛缓慢 
    利用了遗传算法前期快速收敛的特性 继续前期的遗传变异 
    旨在若干组的优秀解 为后面蚁群算法的初始化信息素浓度作一个很好的分布
    author:sugarMei
    date:2020 5-30
    version:1.0
    language:python
    """
    '''
    alpha:信息素影响的强度大小
    beta:可见度影响的强度大小
    rho:信息素挥发因子
    q:常数 用于计算每次一次遍历后的信息素强度变化程度
    eta:从i城市到j城市的可见度
    distance_graph:城市i到j的距离dij
    pheromone:信息素矩阵 pij表示城市i到j城市的边的信息素的大小
    path:路径表 pj表示第j只蚂蚁的路径表
    length:记录一次循环中每个蚂蚁的路径长度li
    prob:交叉概率
    mutationProb:变异概率
    population:种群规模
    '''
    # 初始化GA参数
    prob, mutationProb, population, gaIter, MaxGaIter = 0.8, 0.08, 200, 0, 100
    
    # 初始化ACA参数
    alpha, beta, rho, q, generation, generations = 1, 2, 0.4, 100, 0, 200
    cities, ants = 50, 75
    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 = np.zeros((cities, cities))
    
    # 计算城市之间的距离
    for i in range(cities):
        for j in range(cities):
            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] = temp_distance
    # 可见度矩阵
    eta = 1.0 / (distance_graph + np.diag([1e10] * cities))
    path = np.zeros((ants, cities), dtype=np.int)
    # 最佳路径
    best_path = []
    best_length = np.inf
    
    # 存放GA算法的输出:若干组优秀解
    gaOutput = np.zeros((population, cities))
    
    
    # 适应度值函数
    def myLength(index_path):
        fit = 0
        for i in range(cities - 1):
            tmp = distance_graph[index_path[i]][index_path[i + 1]]
            fit += tmp
        fit += distance_graph[index_path[-1]][index_path[0]]
        return fit
    
    
    # GA
    # 初始化种群
    pops = np.zeros((population, cities), dtype=np.int)
    temp = np.arange(cities)
    for i in range(population):
        np.random.shuffle(temp)
        pops[i] = temp
    
    
    # 交叉函数
    def cross(pop):
        numbers = np.uint8(population * prob) - 1
        if numbers % 2 != 0:
            numbers += 1
        index = random.sample(range(1, population), numbers)
        new_pops1 = np.zeros((population, cities), dtype=np.int)
        # 确保精英不会进去交配
        new_pops1[0] = pop[np.argmin(fits)]
        # 将不需要交叉的染色体直接复制到新的种群中
        for i in range(1, population):
            if not index.__contains__(i):
                new_pops1[i] = pop[i]
        # 交叉
        j = 0
        while j < numbers:
            # w需要交叉的位数
            w = 0
            if cities < 10:
                w = cities
            elif ((cities / 10) - np.floor(cities / 10)) >= np.random.random() and cities > 10:
                w = math.ceil(cities / 10) + 10
            else:
                w = math.floor(cities / 10) + 10
            p = np.random.randint(0, cities - w + 1)
            for i in range(w):
                x = pop[index[j + 1]].tolist().index(pop[index[j]][p + i - 1])
                y = pop[index[j]].tolist().index(pop[index[j + 1]][p + i - 1])
                # exchange
                pop[index[j + 1]][p + i - 1], pop[index[j]][p + i - 1] = pop[index[j]][p + i - 1], \
                                                                         pop[index[j + 1]][p + i - 1]
                pop[index[j + 1]][x], pop[index[j]][y] = pop[index[j]][y], \
                                                         pop[index[j + 1]][x]
    
            # 等待所有位置交叉完成 再重新赋值
            new_pops1[index[j]] = pop[index[j]]
            new_pops1[index[j + 1]] = pop[index[j + 1]]
            j += 2
        return new_pops1
    
    
    # 变异函数
    def mutation(per_pop):
        # 生成两个变异位置
        cross_points = np.random.randint(0, cities, 2)
        cross_point_1, cross_point_2 = cross_points[0], cross_points[1]
        # 交换位置
        per_pop[cross_point_1], per_pop[cross_point_2] = per_pop[cross_point_2], per_pop[cross_point_1]
        return per_pop
    
    
    # 选择函数
    def select(pop, fit):
        prob_fit = fit / sum(fit)
        cum_prob = np.cumsum(prob_fit)
        new_pop = np.zeros((population, cities))
        # fitness最小的个体被保留 必定进入下一代
        new_pop[0] = pop[np.argmin(fit)]
        for i in range(1, population):
            tmp = np.random.random()
            for j in range(population):
                # 被选中
                if tmp < cum_prob[j]:
                    new_pop[i] = pop[j]
                    break
        return new_pop.astype(int)
    
    
    def fitness(l, m, maxlen, minlen):
        fit = np.zeros(population)
        for i in range(len(l)):
            fit[i] = (1 - (l[i] - minlen) / (maxlen - minlen + 0.001)) ** m
        return fit
    
    
    m = 3
    
    # 主循环
    while gaIter < MaxGaIter:
        length = np.zeros(population)
        # 计算适应度值
        for i in range(population):
            length[i] = myLength(pops[i])
        # 归一化
        maxlen = max(length)
        minlen = min(length)
        fits = fitness(length, m, maxlen, minlen)
        # 选择
        pops = select(pops, fits)
    
        # 交叉操作
        pops = cross(pop=pops)
    
        # 变异
        for i in range(population):
            if mutationProb > np.random.random():
                pops[i] = mutation(pops[i])
        gaIter += 1
    # 输出所有的路径长度
    # print(pops)
    for a in pops:
        print(myLength(a))
    gaOutput = pops
    pheromone = np.zeros((cities, cities))
    # 每一条dij和dji路径 出现一次加k的信息素浓度
    #
    # k=0.6
    # k = q / length.mean()
    
    for i in range(int(population)):
        for j in range(cities - 1):
            pheromone[gaOutput[i][j]][gaOutput[i][j + 1]] += q / length[i]
            pheromone[gaOutput[i][j + 1]][gaOutput[i][j]] += q / length[i]
        pheromone[gaOutput[i][-1]][gaOutput[i][0]] += q / length[i]
        pheromone[gaOutput[i][0]][gaOutput[i][-1]] += q / length[i]
    print(pheromone)
    # 根据gaOutput 初始化信息素矩阵
    
    # 画图
    root = tkinter.Tk()
    canvas = tkinter.Canvas(
        root,
        width=800,
        height=600,
        bg="#EBEBEB",  # 背景白色
        xscrollincrement=1,
        yscrollincrement=1
    )
    canvas.pack(expand=tkinter.YES, fill=tkinter.BOTH)
    r = 5
    nodes = []  # 节点坐标
    nodes2 = []  # 节点对象
    # 初始化城市节点
    filename = tkinter.PhotoImage(file="/Users/sugarmei/PycharmProjects/sugarmei/es/city.png")
    
    for i in range(len(distance_x)):
        # 在画布上随机初始坐标
        x = distance_x[i]
        y = distance_y[i]
        nodes.append((x, y))
        # 生成节点椭圆,半径为self.__r
        node = canvas.create_image(x, y, image=filename, tags="node")
        # node = canvas.create_oval(x - r,
        #                           y - r, x + r, y + r,
        #                           fill="#ff0000",  # 填充红色
        #                           outline="#000000",  # 轮廓白色
        #                           tags="node",
        #                           )
        nodes2.append(node)
        # 显示坐标
        canvas.create_text(x, y - 20,  # 使用create_text方法在坐标(302,77)处绘制文字
                           text='',  # 所绘制文字的内容
                           fill='black'  # 所绘制文字的颜色为灰色
                           )
    
    
    def title(s):
        root.title(s)
    
    
    # 将节点按order顺序连线
    def line(order):
        # 删除原线
        canvas.delete("line")
    
        def line2(i1, i2):
            p1, p2 = nodes[i1], nodes[i2]
            canvas.create_line(p1, p2, fill="#000000", tags="line")
            return i2
    
        # order[-1]为初始值
        reduce(line2, order, order[-1])
    
    
    print(eta)
    while generation < generations:
        # 初始化蚂蚁位置
        if ants < cities:
            path[:, 0] = np.random.permutation(cities)[:ants]
        else:
            path[:cities, 0] = np.random.permutation(cities)[:]
            path[cities:, 0] = np.random.permutation(cities)[:ants - cities]
        length = np.zeros(ants)
        # 计算第k只蚂蚁从i城市到达j城市的概率
        for k in range(ants):
            visited = path[k, 0]
            unvisited = set(range(cities))
            unvisited.remove(visited)
    
            for i in range(1, cities):
                l_unvisited = list(unvisited)
                prob_next_city = np.zeros(len(l_unvisited), dtype=np.float64)
                for j in range(len(l_unvisited)):
                    prob_next_city[j] = pow(pheromone[visited][l_unvisited[j]], alpha) * pow(eta[visited][l_unvisited[j]],
                                                                                             beta)
                    # 解决精度问题
                    if prob_next_city[j] == 0.0:
                        prob_next_city[j] = 0.00001
    
                prob_next_city = prob_next_city / np.sum(prob_next_city, dtype=float)
                prob_next_city = np.cumsum(prob_next_city)
                temp_prob = np.random.random()
                next_city = -1
                # 轮盘赌算法
                for p in range(len(prob_next_city)):
                    # 第p个城市赌成功
                    if not math.isnan(prob_next_city[p]):
                        if prob_next_city[p] >= temp_prob:
                            next_city = l_unvisited[p]
                            break
    
                unvisited.remove(next_city)
                path[k, i] = next_city
                length[k] += distance_graph[visited][next_city]
                visited = next_city
            length[k] += distance_graph[visited][path[k, 0]]
        # 调整最短长度和最佳路径
        if length.min() < best_length:
            best_length = length.min()
            best_path = path[length.argmin()]
            line(best_path)
        root.title("ACO 第 " + str(generation) + " 次迭代" + " 当前最短长度:" + str(best_length))
        root.update()
    
        # time.sleep(10)
        # 本轮遍历一次全部城市结束 调整信息素强度
        tmp_pheromone = np.zeros((cities, cities))
        for i in range(ants):
            for j in range(cities - 1):
                # 使用了蚁环算法
                # length[i]为第i只蚂蚁当前次遍历的路径长度 作为整体信息进行信息素的更新
                tmp_pheromone[path[i, j]][path[i, j + 1]] += q / length[i]
                # 从j城市到i城市的距离dji与dij一致 因此信息素浓度一致
                if tmp_pheromone[path[i, j + 1]][path[i, j]] < tmp_pheromone[path[i, j]][path[i, j + 1]]:
                    tmp_pheromone[path[i, j + 1]][path[i, j]] = tmp_pheromone[path[i, j]][path[i, j + 1]]
            tmp_pheromone[path[i, cities - 1]][path[i, 0]] += q / length[i]
            # 蚁密算法
            # tmp_pheromone[path[i, j]][path[i, j + 1]] += q
            # tmp_pheromone[path[i, cities - 1]][path[i, 0]] += q
            # 蚁量算法 与当前城市之间距离成反比
            # tmp_pheromone[path[i, j]][path[i, j + 1]] += q / distance_graph[path[i, j]][path[i, j + 1]]
            # tmp_pheromone[path[i, cities - 1]][path[i, 0]] += q / distance_graph[path[i, cities - 1]][path[i, 0]]
        # 更新从i到j城市的路径的信息素浓度
        pheromone = (1 - rho) * pheromone + tmp_pheromone
        generation += 1
        print("当前迭代次数:", generation, "当前最短长度:", best_length)
    
    print("迭代次数:", generations)
    print("最佳路径:", best_path)
    print("最短长度:", best_length)
    
    
    展开全文
  • 蚁群算法Python实现

    万次阅读 多人点赞 2015-04-15 15:10:31
    计算完城市间的转移概率后,采用与遗传算法中一样的轮盘赌方法选择下一个待访问的城市。 当所有的蚂蚁完成一次循环后,各个城市间链接路径上的信息素浓度需进行更新,计算公式为 { τ i j ( t + 1 ) = ( 1 − ...

    解决的问题

    三维地形中,给出起点和重点,找到其最优路径。

    这里写图片描述

    作图源码:

    from mpl_toolkits.mplot3d import proj3d
    from mpl_toolkits.mplot3d import Axes3D
    import numpy as np
    
    height3d = np.array([[2000,1400,800,650,500,750,1000,950,900,800,700,900,1100,1050,1000,1150,1300,1250,1200,1350,1500],                   [1100,900,700,625,550,825,1100,1150,1200,925,650,750,850,950,1050,1175,1300,1350,1400,1425,1450],                    [200,400,600,600,600,900,1200,1350,1500,1050,600,600,600,850,1100,1200,1300,1450,1600,1500,1400],                   [450,500,550,575,600,725,850,875,900,750,600,600,600,725,850,900,950,1150,1350,1400,1450],                   [700,600,500,550,600,550,500,400,300,450,600,600,600,600,600,600,600,850,1100,1300,1500],                    [500,525,550,575,600,575,550,450,350,475,600,650,700,650,600,600,600,725,850,1150,1450],                    [300,450,600,600,600,600,600,500,400,500,600,700,800,700,600,600,600,600,600,1000,1400],                    [550,525,500,550,600,875,1150,900,650,725,800,700,600,875,1150,1175,1200,975,750,875,1000],                    [800,600,400,500,600,1150,1700,1300,900,950,1000,700,400,1050,1700,1750,1800,1350,900,750,600],                   [650,600,550,625,700,1175,1650,1275,900,1100,1300,1275,1250,1475,1700,1525,1350,1200,1050,950,850],                   [500,600,700,750,800,1200,1600,1250,900,1250,1600,1850,2100,1900,1700,1300,900,1050,1200,1150,1100],                   [400,375,350,600,850,1200,1550,1250,950,1225,1500,1750,2000,1950,1900,1475,1050,975,900,1175,1450],                    [300,150,0,450,900,1200,1500,1250,1000,1200,1400,1650,1900,2000,2100,1650,1200,900,600,1200,1800],                    [600,575,550,750,950,1275,1600,1450,1300,1300,1300,1525,1750,1625,1500,1450,1400,1125,850,1200,1550],                    [900,1000,1100,1050,1000,1350,1700,1650,1600,1400,1200,1400,1600,1250,900,1250,1600,1350,1100,1200,1300],                   [750,850,950,900,850,1000,1150,1175,1200,1300,1400,1325,1250,1125,1000,1150,1300,1075,850,975,1100],                    [600,700,800,750,700,650,600,700,800,1200,1600,1250,900,1000,1100,1050,1000,800,600,750,900],                    [750,775,800,725,650,700,750,775,800,1000,1200,1025,850,975,1100,950,800,900,1000,1050,1100],                    [900,850,800,700,600,750,900,850,800,800,800,800,800,950,1100,850,600,1000,1400,1350,1300],                    [750,800,850,850,850,850,850,825,800,750,700,775,850,1000,1150,875,600,925,1250,1100,950],                   [600,750,900,1000,1100,950,800,800,800,700,600,750,900,1050,1200,900,600,850,1100,850,600]])
    
    fig = figure()
    ax = Axes3D(fig)
    X = np.arange(21)
    Y = np.arange(21)
    X, Y = np.meshgrid(X, Y)
    Z = -20*np.exp(-0.2*np.sqrt(np.sqrt(((X-10)**2+(Y-10)**2)/2)))+20+np.e-np.exp((np.cos(2*np.pi*X)+np.sin(2*np.pi*Y))/2)
    ax.plot_surface(X, Y, Z, rstride=1, cstride=1, cmap='cool')
    ax.set_xlabel('X axis')
    ax.set_ylabel('Y axis')
    ax.set_zlabel('Z')
    ax.set_title('3D map')
    
    
    point0 = [0,9,Z[0][9]] 
    point1 = [20,7,Z[20][7]]
    
    ax.plot([point0[0]],[point0[1]],[point0[2]],'r',marker = u'o',markersize = 15)
    ax.plot([point1[0]],[point1[1]],[point1[2]],'r',marker = u'o',markersize = 15)
    
    x0,y0,_ = proj3d.proj_transform(point0[0],point0[1],point0[2], ax.get_proj())
    x1,y1,_ = proj3d.proj_transform(point1[0],point1[1],point1[2], ax.get_proj())
    
    label = pylab.annotate(
        "start", 
        xy = (x0, y0), xytext = (-20, 20),
        textcoords = 'offset points', ha = 'right', va = 'bottom',
        bbox = dict(boxstyle = 'round,pad=0.5', fc = 'yellow', alpha = 1),
        arrowprops = dict(arrowstyle = '->', connectionstyle = 'arc3,rad=0'),fontsize=15)
    label2 = pylab.annotate(
        "end", 
        xy = (x1, y1), xytext = (-20, 20),
        textcoords = 'offset points', ha = 'right', va = 'bottom',
        bbox = dict(boxstyle = 'round,pad=0.5', fc = 'yellow', alpha = 1),
        arrowprops = dict(arrowstyle = '->', connectionstyle = 'arc3,rad=0'),fontsize=15)
    def update_position(e):
        x2, y2, _ = proj3d.proj_transform(point0[0],point0[1],point0[2],ax.get_proj())
        label.xy = x2,y2
        label.update_positions(fig.canvas.renderer)
    
        x1,y1,_ =  proj3d.proj_transform(point1[0],point1[1],point1[2],ax.get_proj())
        label2.xy = x1,y1
        label2.update_positions(fig.canvas.renderer)
        fig.canvas.draw()
    
    fig.canvas.mpl_connect('button_release_event', update_position)

    基本原理

    • 蚂蚁k根据各个城市间链接路径上的信息素浓度决定其下一个访问城市,设Pkij(t)表示t时刻蚂蚁k从城市i转移到矩阵j的概率,其计算公式为

      Pkij=[τij(t)]α[ηij(t)]βsallowk[τis(t)]α[ηis(t)]β0sallowksallowk

      计算完城市间的转移概率后,采用与遗传算法中一样的轮盘赌方法选择下一个待访问的城市。

    • 当所有的蚂蚁完成一次循环后,各个城市间链接路径上的信息素浓度需进行更新,计算公式为

      {τij(t+1)=(1ρ)τij(t)+ΔτijΔτij=nk=1δτkij

      其中,Δτkij表示第k只蚂蚁在城市i与城市j连接路径上释放的信息素浓度;Δτij表示所有蚂蚁在城市i与城市j连接路径上释放的信息素浓度之和。

    • 蚂蚁释放信息素的模型
      Δτkij={Q/Lk,0,ki访j

    程序代码:

    import numpy as np
    import matplotlib.pyplot as plt
    %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] # 当前所在的城市
    
            #visited = set() #已访问过的城市,防止重复
            #visited.add(visiting) #增加元素
            unvisited = set(range(numcity))#未访问的城市
            unvisited.remove(visiting) #删除元素
    
    
            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[find(cumsumprobtrans>0)[0]] #下一个要访问的城市
    
                pathtable[i,j] = k
    
                unvisited.remove(k)
                #visited.add(k)
    
                length[i] += distmat[visiting][k]
    
                visiting = k
    
            length[i] += distmat[visiting][pathtable[i,0]] #蚂蚁的路径距离包括最后一个城市和第一个城市的距离
    
    
        #print length
        # 包含所有蚂蚁的一个迭代结束后,统计本次迭代的若干统计参数
    
        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
    
        #观察程序执行进度,该功能是非必须的
        if (iter-1)%20==0: 
            print iter-1
    
    
    # 做出平均路径长度和最优路径长度        
    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.close()
    
    
    #作出找到的最优路径图
    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,n = bestpath[i],bestpath[i+1]
        print m,n
        plt.plot([coordinates[m][0],coordinates[n][0]],[coordinates[m][1],coordinates[n][1]],'k')
    plt.plot([coordinates[bestpath[0]][0],coordinates[n][0]],[coordinates[bestpath[0]][1],coordinates[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.close()

    这里写图片描述

    这里写图片描述

    展开全文
  • 蚁群算法Python3可运行代码

    千次阅读 2019-03-31 23:13:01
    k = listunvisited[(np.where(cumsumprobtrans > 0)[0])[0]] # python3中原代码运行bug,类型问题;鉴于此特找到其他方法 # 通过where()方法寻找矩阵大于0的元素的索引并返回ndarray类型,然后接着载使用[0]提取...

    原理就不再赘述了,直接上代码:

    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()
    

    结果:

    展开全文
  • 参考文档:https://blog.csdn.net/golden1314521/article/details/45059719简单的修改下,能够在python3.6中运行代码如下:import numpy as np import matplotlib.pyplot as plt # %pylab coordinates = np.array([...
  • 蚁群算法python代码

    2017-03-16 04:09:48
    蚁群算法中TSP问题的一个用python解决的小DEMO
  • 蚁群算法代码python 详解版 博文链接:https://blog.csdn.net/quinn1994/article/details/80324308
  • 蚁群算法(详解)python

    万次阅读 多人点赞 2018-05-15 16:07:32
    代码参考来源:蚁群算法python实现因为要做数学建模,所以学一下蚁群算法。在CSDN中看到这个博客,但是不是很详细,基于此代码为模板,详解一下。旅行商问题(travelling salesman problem,TSP)是物流领域的典型...
  • python蚁群算法实现

    2018-02-14 09:09:44
    python蚁群算法实现
  • 分 数_ 任课教师签字_ 华北电力大学研究生结课作业 学 年 学 期20 10 学年第二学期 课 程 名 称人工智能与知识工程 学 生 姓 名张华壮 学 号2 10222 1007 题 目蚁群算法概述 提 交 时 间20 11/4/ 13 1 蚁群算法概述 ...
  • python实现蚁群算法

    2019-06-03 00:35:22
    蚁群算法实现,带有注释,并且可以实现可视化找到最佳路径。
  • 针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。 定义 各个蚂蚁在没有事先告诉他们食物在什么...
  • 蚁群算法介绍(python)

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

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

    2015-04-09 23:31:07
    非常简单的Python蚁群算法,智能算法入门,欢迎下载!
  • 蚁群算法.python代码

    2020-10-17 11:17:13
    """蚁群算法计算过程如下: (1)初始化。 (2)为每只蚂蚁选择下一个节点。 (3)更新信息素矩阵。 (4)检查终止条件 如果达到最大代数MAX_GEN,算法终止,转到第(5)步;否则,重新初始化所有的蚂蚁的Delt...
  • 使用python实现蚁群算法

    千次阅读 2018-06-26 19:33:04
    此次使用python实现蚁群算法是仿照蚁群优化算法的JAVA实现 中的蚁群算法实现方法,使用的也是其中的数据(此处为上传数据),如需更深一步了解蚁群算法原理和具体实现过程,请参考蚁群优化算法的JAVA实现和蚁群算法...
  • 蚁群算法原理及python代码实现

    千次阅读 多人点赞 2020-04-04 22:26:20
    蚁群算法(AG)是一种模拟蚂蚁觅食行为的模拟优化算法,它是由意大利学者Dorigo M等人于1991年首先提出,并首先使用在解决TSP(旅行商问题)上。之后,又系统研究了蚁群算法的基本原理和数学模型.蚁群算法的基本思想:...
  • 蚁群算法原理及其实现(python)

    万次阅读 多人点赞 2018-05-20 11:08:23
    蚁群算法(AG)是一种模拟蚂蚁觅食行为的模拟优化算法,它是由意大利学者Dorigo M等人于1991年首先提出,并首先使用在解决TSP(旅行商问题)上。之后,又系统研究了蚁群算法的基本原理和数学模型.蚁群算法的基本思想:#...
  • 采用了多线程和蚁群算法的思路,代码来自于其他博客,经过一定的修改
  • 蚁群算法原理与实现(python)

    千次阅读 2019-12-25 19:45:29
    文章目录蚁群算法的背景蚁群算法的思想蚁群算法python实现实例总结 蚁群算法的背景 古有牛顿在苹果树下被苹果砸中发现万有引力,三十年前有人观察蚂蚁觅食发明蚁群算法蚁群算法是意大利学者Dorigo、Maniezzo等人...
  • 写在前面 ...遗传算法详解与Python实现在上一篇博客里已经介绍,蚁群算法与遗传算法等仿生进化算法均有共通之处,读者只需要明白透彻其中一种算法的原理和细节,便能触类旁通。因此,今天介绍的是蚁群算
  • 采用蚁群算法计算货郎担通过 34 个城市一次回到原点的最短距离 可短时间解决这个 NP 难的 TSP 问题 内含运行文件生成的两张图 注释较详细

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,720
精华内容 688
关键字:

蚁群算法python

python 订阅