{ "cells": [ { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import scipy as scp\n", "from numpy import random\n", "from numpy import linalg\n", "from numba import jit\n", "\n", "ncity=100\n", "\n", "# random coordinates in 2D for n-cities\n", "R = random.random((ncity,2))\n", "city = range(ncity)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "\n", "def Distance(R1,R2):\n", " return linalg.norm(R1-R2)\n", "\n", "def TotalDistance(city, R):\n", " dist=0\n", " for i in range(len(city)-1):\n", " dist += Distance(R[city[i]],R[city[i+1]])\n", " dist += Distance(R[city[-1]],R[city[0]])\n", " return dist" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def Plot(city, R, dist):\n", " Pt = [R[city[i]] for i in range(len(city))]\n", " Pt += [R[city[0]]]\n", " Pt = array(Pt)\n", " title('Total distance='+str(dist))\n", " plot(Pt[:,0],Pt[:,1],'o-')\n", " show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from pylab import *\n", "%matplotlib inline\n", "Plot(city,R, TotalDistance(city,R))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "@jit(nopython=True)\n", "def FindASegment(R):\n", " nct = len(R) # number of cities\n", " while True:\n", " # Two cities n[0] and n[1] chosen at random\n", " n0 = int(nct*rand())\n", " n1 = int((nct-1)*rand())\n", " if n1>=n0 : n1 +=1\n", " if n1=3 : break\n", " n2 = (n0-1) % nct\n", " n3 = (n1+1) % nct\n", " return (n0,n1,n2,n3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def CostReverse(R, city, n0, n1, n2, n3):\n", " # cost for reverse move\n", " de = Distance(R[city[n2]],R[city[n1]])+Distance(R[city[n0]],R[city[n3]])\n", " de-= Distance(R[city[n2]],R[city[n0]])+Distance(R[city[n1]],R[city[n3]])\n", " return de\n", "\n", "def Reverse(R, city, n0, n1, n2, n3):\n", " newcity = copy(city)\n", " for j in range(n1-n0+1):\n", " newcity[n0+j] = city[n1-j]\n", " return newcity" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "@jit(nopython=True)\n", "def FindTSegment(R):\n", " (n0,n1,n2,n3) = FindASegment(R)\n", " nct = len(R)\n", " nn = nct - (n1-n0+1) # number for the rest of the cities\n", " n4 = (n1+1 + int(rand()*(nn-1)) ) % nct # city on the rest of the path\n", " n5 = (n4+1) % nct\n", " return (n0,n1,n2,n3,n4,n5)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def CostTranspose(R, city, n0,n1,n2,n3,n4,n5):\n", " de = -Distance(R[city[n1]], R[city[n3]])\n", " de-= Distance(R[city[n0]], R[city[n2]])\n", " de-= Distance(R[city[n4]], R[city[n5]])\n", " de+= Distance(R[city[n0]], R[city[n4]])\n", " de+= Distance(R[city[n1]], R[city[n5]])\n", " de+= Distance(R[city[n2]], R[city[n3]])\n", " return de\n", "\n", "\n", "def Transpose(R, city, n0,n1,n2,n3,n4,n5):\n", " nct = len(R)\n", " newcity = []\n", " # Segment in the range n0,...n1\n", " for j in range(n1-n0+1):\n", " newcity.append( city[ (j+n0)%nct ] )\n", " # is followed by segment n5...n2\n", " for j in range( (n2-n5)%nct + 1):\n", " newcity.append( city[ (j+n5)%nct ] )\n", " # is followed by segement n3..n4\n", " for j in range( (n4-n3)%nct + 1):\n", " newcity.append( city[ (j+n3)%nct ] )\n", " return newcity" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "nn = FindTSegment(R)\n", "de = CostTranspose(R, city, *nn)\n", "\n", "print(de)\n", "r1 = Transpose(R, city, *nn)\n", "print(r1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def TravelingSalesman(city, R, maxSteps, maxAccepted, Tstart, fCool, maxTsteps, Preverse=0.5):\n", " T = Tstart\n", " dist = TotalDistance(city,R)\n", " for t in range(maxTsteps):\n", " accepted = 0\n", " for i in range(maxSteps):\n", " if Preverse > rand():\n", " # Try reverse\n", " nn = FindASegment(R)\n", " de = CostReverse(R, city, *nn)\n", " if de < 0 or exp(-de/T) > rand():\n", " accepted += 1\n", " dist += de\n", " city = Reverse(R, city, *nn)\n", " else: \n", " # here we transpose\n", " nn = FindTSegment(R)\n", " de = CostTranspose(R, city, *nn)\n", " if de < 0 or exp(-de/T) > rand():\n", " accepted += 1\n", " dist += de\n", " city = Transpose(R, city, *nn)\n", " if accepted > maxAccepted: \n", " break \n", " T *= fCool\n", " Plot(city, R, dist)\n", " print(\"T=%10.5f , distance=%10.5f acc.steps=%d\" % (T, dist,accepted))\n", " if accepted == 0:\n", " break\n", " Plot(city, R, dist)\n", " return city " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from numpy import random\n", "\n", "ncity = 100\n", "maxSteps = 100*ncity\n", "maxAccepted = 10*ncity\n", "Tstart = 0.2\n", "fCool = 0.9\n", "maxTsteps = 100\n", "\n", "random.seed(0)\n", "\n", "R = random.random((ncity,2))\n", "city = range(ncity)\n", "\n", "ncity = TravelingSalesman(city, R, maxSteps, maxAccepted, Tstart, fCool, maxTsteps)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 2 }