蚁群算法解决tsp问题

# -*- coding: utf-8 -*-


# -*- 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）