MAOS-TSP: Project Portal
URL: http://www.adaptivebox.net/doi/MAOS-TSP
(Current Version: V1.0.003)

Basic Description What's New Directories & Files Command Line & Parameters Output Information References Contact

MAOS-TSP [1] is a multiagent optimization system (MAOS) for solving the Traveling Salesman Problem (TSP).

MAOS-TSP shares the MAOS kernel with other MAOS applications (e.g. MAOS-GCP and MAOS-QKP), and contains some modules that are specifically for tacking TSP.

License Information: MAOS-TSP is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License 3.0.

System Requirements: MAOS-TSP is a platform-independent software developed by JAVA version 1.5 or above.

What's New

Version: V1.0.003 [download (Binary & Source Codes)] (Last Modified: May 18, 2010):

  • Solver "STD_PRB_3Opt_2L_REAX+SEAX_1J": 1) Two-level representation for 3-opt: reduce the time complexity of Tour Segment Inversion from O(n) to O(sqrt(n)); 2) Locking common edges during the sub-cycles bridging process in the generalized EAX; 3) Sorting in k Nearest Neighbors: reduce the time complexity from O(nlog(n)) to O(n+klog(k)).

    • Version: V1.0.002 [download (Binary & Source Codes)] (Last Modified: May 22, 2009):

  • Solver "STD_PRB_3Opt_REAX+SEAX": It implements the solver for original MAOS-TSP algorithm [1]. This solver has shown to be competitive in solving middle-scale TSP instances (1000 - 6000 nodes) as comparing to some state-of-the-art algorithms, without using explicit local search (e.g. LK variants) during the runtime cycles.
    • // It has found the best-so-far solution (located in myprojects/tasks/TSP/solution) for the open instance fdp3256 in the VLSI Data Sets.

  • Setting parameters: TSP:Problem, N, T, Tcon, Solver.

    • Directories & Files
    		 

    binary	                           // the binary code of MAOS-TSP
source                             // the source code of MAOS-TSP
myprojects                         // user directory
|-----> examples.bat               // commandline examples
|-----> results                    // the directory for storing runtime results
|-----> setting                    // the setting directory  
	|-----> kernel             // the setting directory for MAOS Kernel
	|-----> TSP                // the setting directory for TSP solvers
                |-----> solver     // the directory containing solver script files (the name of each file is Solver_Name)
                                   // Examples: "STD_PRB_3Opt_REAX+SEAX" and "STD_PRB_3Opt_2L_REAX+SEAX_1J"
|-----> tasks                      // task directory
        |-----> TSP
                |-----> instance   // GCP instances of the TSPLIB format (Problem_Name with the default suffix .tsp) 
                                   // Example: rl1323.tsp (Problem_Name is rl1323)
                |-----> solution   // the directory for storing solutions of TSP instances
                                   // For a normal solution, the file name is Problem_Name.(objective value).tour
                                   // If objective value is removed from the file name, the solution is considered as optimal.
                                   // Example: fdp3256.tour

// Typical benchmark instances can be found in the TSPLIB and VLSI data sets.

    Command Line & Parameters

    MAOS-TSP is executed on the command line (Enter the directory "myprojects", and execute maosKernel.MAOSExecuter). Here is a typical example (See the file "myprojects/Examples.bat" for more examples), in which a user should specify JAVA options, general parameters, problem instance, and solver instance: 

    $ cd myprojects
$ java -server -Xmx512M -cp ../binary/MAOS_SEQ.jar maosKernel.MAOSExecuter TSP:Problem=rl1323 N=300 T=500 Tcon=100 DUP_TIMES=5 solver=STD_PRB_3Opt_2L_REAX+SEAX_1J

//java: the JAVA executor, JAVA Runtime Environment Version 1.5 or above is preferred
//maosKernel.MAOSExecuter: the main execution entrance of the MAOS program

    JAVA Options (See "java -help" for more information):

    There are two recommended optional parameters for java:
    
  -server: select the "server" VM, which is normally faster than the "client" VM
  -Xmx: set maximum Java heap size. Using a large enough size may prevent from the "out of memory" error

Moreover, the "-cp" option is used for loading the binary file "../binary/MAOS_SEQ.jar".

    General Parameters: 

    NAME         VALUE_type   Range      Default_Value   Description

TSP:Problem  String      *	     <Problem_Name>  The problem instance to be solved
--------------------------------------------------------------------------------------------------
N            integer     >1          300 	     The number of agents
T            integer     >0          500	     Terminate condition: The maximum learning cycles
Tcon         integer     >0          100             Terminate condition: The number of cycles as the best state is unvaried

DUP_TIMES    integer     >0          10		     Number of trials
--------------------------------------------------------------------------------------------------
Solver       String      *	     <Solver_Name>   The name of the script of the actual solver

//The explanation of Problem_Name and Solver_Name can be found in Directories & Files.

    Output Information

    For the output, we provide screen output, output a file for the running result, and stored the best solution ever found.

    Screen Output: 

    [Initialization information]: provide the parsing information during the initialization.
[Runtime information]: The program outputs runtime information, i.e., the current best evaluation values, execution time, at every "Tout" cycles.
[Summary information]: At the end, it outputs the input variables, response values, and evaluation values <Vcon, Vopt> of the best solution.
    Result File: 
    The result file will be stored at the directory "myprojects/results".
    Solution File: 
    The best solution (better than any previous solutions) will be stored at the directory "myprojects/tasks/TSP/solution" (of the TSPLIB format).

    References

    [1] Xiao-Feng Xie, Jiming Liu. Multiagent optimization system for solving the traveling salesman problem (TSP). IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2009, 39(2): 489-502. [DOI]

    Return to homepage

    Maintained by AdaptiveBox StUdIo, under a Creative Commons Attribution 3.0 License.