#?encoding:utf-8

‘‘‘
	Solution?for?Travelling?Salesman?Problem?using?PSO?（Particle?Swarm?Optimization）
	Discrete?PSO?for?TSP

	References:?
		http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.258.7026&rep=rep1&type=pdf
		http://www.cs.mun.ca/~tinayu/Teaching_files/cs4752/Lecture19_new.pdf
		http://www.swarmintelligence.org/tutorials.php

	References?are?in?the?folder?“references“?of?the?repository.
‘‘‘

from?operator?import?attrgetter
import?random?sys?time?copy


#?class?that?represents?a?graph
class?Graph:

	def?__init__（self?amount_vertices）:
		self.edges?=?{}?#?dictionary?of?edges
		self.vertices?=?set（）?#?set?of?vertices
		self.amount_vertices?=?amount_vertices?#?amount?of?vertices


	#?adds?a?edge?linking?“src“?in?“dest“?with?a?“cost“
	def?addEdge（self?src?dest?cost?=?0）:
		#?checks?if?the?edge?already?exists
		if?not?self.existsEdge（src?dest）:
			self.edges[（src?dest）]?=?cost
			self.vertices.add（src）
			self.vertices.add（dest）


	#?checks?if?exists?a?edge?linking?“src“?in?“dest“
	def?existsEdge（self?src?dest）:
		return?（True?if?（src?dest）?in?self.edges?else?False）


	#?shows?all?the?links?of?the?graph
	def?showGraph（self）:
		print（‘Showing?the?graph:\n‘）
		for?edge?in?self.edges:
			print（‘%d?linked?in?%d?with?cost?%d‘?%?（edge[0]?edge[1]?self.edges[edge]））

	#?returns?total?cost?of?the?path
	def?getCostPath（self?path）:
		
		total_cost?=?0
		for?i?in?range（self.amount_vertices?-?1）:
			total_cost?+=?self.edges[（path[i]?path[i+1]）]

		#?add?cost?of?the?last?edge
		total_cost?+=?self.edges[（path[self.amount_vertices?-?1]?path[0]）]
		return?total_cost


	#?gets?random?unique?paths?-?returns?a?list?of?lists?of?paths
	def?getRandomPaths（self?max_size）:

		random_paths?list_vertices?=?[]?list（self.vertices）

		initial_vertice?=?random.choice（list_vertices）
		if?initial_vertice?not?in?list_vertices:
			print（‘Error:?initial?vertice?%d?not?exists!‘?%?initial_vertice）
			sys.exit（1）

		list_vertices.remove（initial_vertice）
		list_vertices.insert（0?initial_vertice）

		for?i?in?range（max_size）:
			list_temp?=?list_vertices[1:]
			random.shuffle（list_temp）
			list_temp.insert（0?initial_vertice）

			if?list_temp?not?in?random_paths:
				random_paths.append（list_temp）

		return?random_paths


#?class?that?represents?a?complete?graph
class?CompleteGraph（Graph）:

	#?generates?a?complete?graph
	def?generates（self）:
		for?i?in?range（self.amount_vertices）:
			for?j?in?range（self.amount_vertices）:
				if?i?!=?j:
					weight?=?random.randint（1?10）
					self.addEdge（i?j?weight）


#?class?that?represents?a?particle
class?Particle:

	def?__init__（self?solution?cost）:

		#?current?solution
		self.solution?=?solution

		#?best?solution?（fitness）?it?has?achieved?so?far
		self.pbest?=?solution

		#?set?costs
		self.cost_current_solution?=?cost
		self.cost_pbest_solution?=?cost

		#?velocity?of?a?particle?is?a?sequence?of?4-tuple
		#?（1?2?1?‘beta‘）?means?SO（12）?prabability?1?and?compares?with?“beta“
		self.velocity?=?[]

	#?set?

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-04-30?20:49??tsp_pso-master\
?????文件??????????11??2015-04-30?20:49??tsp_pso-master\.gitignore
?????文件?????????486??2015-04-30?20:49??tsp_pso-master\README.md
?????目錄???????????0??2015-04-30?20:49??tsp_pso-master\images\
?????文件????????8358??2015-04-30?20:49??tsp_pso-master\images\graph.png
?????文件???????18998??2015-04-30?20:49??tsp_pso-master\images\output_graph.png
?????目錄???????????0??2015-04-30?20:49??tsp_pso-master\references\
?????文件??????521034??2015-04-30?20:49??tsp_pso-master\references\paper.pdf
?????文件???????88917??2015-04-30?20:49??tsp_pso-master\references\slides.pdf
?????文件????????9647??2015-04-30?20:49??tsp_pso-master\tsp_pso.py