TravelingSalesperson.py 文件源码

def TSP(stops, Alg, steps, param, seed=None,
        coordfile='xycoords.txt'):
    '''A wrapper function that attempts to optimize the traveling
    salesperson problem using a specified algorithm. If coordfile
    exists, a preexisting set of coordinates will be used. Otherwise,
    a new set of "stops" coordinates will be generated for the person to
    traverse, and will be written to the specified file.'''

    # Create the distance matrix, which will be used to calculate
    # the fitness of a given path
    if os.path.isfile(coordfile):
        coords = scipy.genfromtxt(coordfile)
        distMat = DistanceMatrix(coords)
    else:
        distMat = GenerateMap(stops, fname=coordfile, seed=seed)

    if Alg == 'HC':
        # param is the number of solutions to try per step
        bestSol, fitHistory = hc.HillClimber(steps, param, distMat, seed)
    elif Alg == 'SA':
        # param is a placeholder
        bestSol, fitHistory = sa.SimulatedAnnealing(
            steps, param, distMat, seed)
    elif Alg == 'MC3':
        # param is the number of chains
        bestSol, fitHistory = mc3.MCMCMC(steps, param, distMat, seed)
    elif Alg == 'GA':
        # param is the population size
        bestSol, fitHistory = ga.GeneticAlgorithm(steps, param, distMat, seed)
    else:
        raise ValueError('Algorithm must be "HC", "SA", "MC3", or "GA".')

    outfname = coordfile + '-' + Alg + '-' + \
        str(steps) + '-' + str(param) + '.txt'
    scipy.savetxt(outfname, scipy.array(bestSol), fmt='%i')
    return bestSol, fitHistory