PSO_TSP_Python

使用python 实现使用粒子群算法解决TSP问题，与matlab相比，更加的直观

# 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