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