Solve salesman problem, Shortest Path through Points, by using Python 3

I need to share
how to use Python3 to solve salesman problem, Shortest Path through Points,

Shortest Path.dyn (26.4 KB)

I use eploy Python genetic algorithm library as shown in the below link

import sys
import clr
import System
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *
dirAppLoc = System.Environment.GetFolderPath(System.Environment.SpecialFolder.LocalApplicationData) 
sys.path.append(dirAppLoc + r'\python-3.8.3-embed-amd64\Lib\site-packages')

clr.AddReference('System.Drawing')
import System.Drawing
from System.Drawing import *
from System.Drawing.Imaging import *
from System.IO import MemoryStream

import numpy as np
import matplotlib.pyplot as plt
from PIL import Image
import io
import math




import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt



def plt2arr(fig):
    """
    need to draw if figure is not drawn yet
    """
    fig.canvas.draw()
    rgba_buf = fig.canvas.buffer_rgba()
    (w,h) = fig.canvas.get_width_height()
    rgba_arr = np.frombuffer(rgba_buf, dtype=np.uint8).reshape((h,w,4))
    return rgba_arr

def convertToBitmap2(npImgArray):
    bitmap_ = None
    # remove alpha
    if npImgArray.ndim == 3 and npImgArray.shape[-1] == 4:
        npImgArray = npImgArray[:, :, :-1]
    # convert to PIL Image
    if npImgArray.ndim == 3:
        image = Image.fromarray(npImgArray, "RGB")
    else:
        image = Image.fromarray(npImgArray, "L")
    # convert to Python ByteArray
    byteIO = io.BytesIO()
    image.save(byteIO, format='BMP')
    byteArr = byteIO.getvalue()
    # convert to Net ByteArray
    netBytes = System.Array[System.Byte](byteArr)
    with MemoryStream(netBytes) as ms:
        bitmap_ = Bitmap(ms)
    return bitmap_


#num_points = 10


X=IN[0]
num_points=IN[1]
#points_coordinate = np.random.rand(num_points, 2)  # generate coordinate of points
#points_coordinate = np.array([[50 , 6],[100, 0.23430645],[0.26308841, 0.25977513],[53 , 600]])

#points_coordinate = np.array([[pt[0],pt[1]] for pt in IN[0]], dtype=np.float32) 


points_coordinate = np.array([[pt.X, pt.Y] for pt in IN[0]], dtype=np.float32) 

distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')


def cal_total_distance(routine):
    '''The objective function. input routine, return total distance.
    cal_total_distance(np.arange(num_points))
    '''
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])


from sko.GA import GA_TSP

ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=5000, prob_mut=1)
best_points, best_distance = ga_tsp.run()

points_coordinate

fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()


image_from_plot = plt2arr(fig)
bitmap1 = convertToBitmap2(image_from_plot)



OUT = bitmap1,best_points_coordinate.tolist()
9 Likes