MAOS-GCP [1] is a cooperative group optimization system (MAOS) for solving the Graph Coloring Problem (GCP).

Related Information: MAOS-GCP shares the MAOS kernel with other MAOS applications (e.g. MAOS-TSP, MAOS-FSP, MAOS-QAP, MAOS-QKP), and contains some modules that are specifically for tacking GCP. Please find other related code and software in our Source Code Library.

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

License information: MAOS-GCP is free software; you can redistribute it and/or modify it under the terms of the Creative Commons Non-Commercial License 3.0.

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

What’s New

Version: V1.0.001 [download]:

  • Solver “DS_GGBX_STD_QT”: It implements the original MAOS-GCP algorithm [1]. Based on the MAOS framework, the Quasi-Tabu local search rule and the grouping-based recombination search rule are used for tackling neutrality and ruggedness in the GCP landscape, respectively.

// It has found the best-so-far solutions (located in myprojects/tasks/GCP/solution) for two open instances, i.e., KColor=150 for C2000.5, KColor=223 for DSJC1000.9.

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

Directories & Files
 
binary	                           // the binary code of MAOS-GCP
source                             // the source code of MAOS-GCP
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
	|-----> GCP                // the setting directory for GCP solvers
                |-----> solver     // the directory containing solver script files (the name of each file is Solver_Name)
                                   // Examples: "DS_GGBX_STD_QT"  (Solver_Name is DS_GGBX_STD_QT)
|-----> tasks                      // task directory
        |-----> GCP
                |-----> instance   // GCP instances of the DIMACS standard format (Problem_Name with the default suffix .col) 
                                   // Example: le450_15c.col (Problem_Name is le450_15c)
                |-----> solution   // the directory for storing solutions of GCP instances
                                   // For a normal solution, the file name is Problem_Name_k(KColor).(objective value).sln
                                   // If objective value is removed from the file name, the solution is considered as optimal.
                                   // Example: le450_15c_k15.sln (Problem_Name=le450_15c, KColor=15)

// Typical benchmark instances can be found from here (Note that each .b file of the compressed format should be translated by binformat.shar).

Command Line & Parameters

MAOS-GCP 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 -cp ../binary/MAOS_INT.jar maosKernel.MAOSExecuter GCP:problem=le450_15c,kColor=15 N=25 T=50 solver=DS_GGBX_STD_QT

//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 is one recommended optional parameter for java:
  -server: select the "server" VM, which is normally faster than the "client" VM

The "-cp" option is used for loading the binary file "../release/MAOS_INT.jar".

General Parameters:

NAME         VALUE_type   Range      Default_Value   Description

GCP:Problem  String      *	     <Problem_Name>  The problem instance to be solved
    KColor   integer     >1          *               The number of colors for the problem instance
--------------------------------------------------------------------------------------------------
N            integer     >1          100 	     The number of agents
T            integer     >0          500	     Terminate condition: The maximum learning cycles
Tcon         integer     >0          -1              Terminate condition: The number of cycles as the best state is unvaried
                                                     //If Tcon==-1, then Tcon=T

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/GCP/solution".

References

[1] Xiao-Feng Xie, Jiming Liu. Graph coloring by multiagent fusion search. Journal of Combinatorial Optimization, 2009, 18(2): 99-123. [DOI]