MAOS-GCP: Project Portal
Category : Software
MAOS-GCP [1] is a multiagent 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 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 | Github]:
- 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.
- 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
|
---|
@Article{xie2009graph,
Title = {Graph coloring by multiagent fusion search},
Author = {Xiao-Feng Xie and Jiming Liu},
Journal = {Journal of Combinatorial Optimization},
Year = {2009},
Number = {2},
Pages = {99--123},
PDF={http://www.wiomax.com/team/xie/paper/JOCO09.pdf},
DOI={10.1007/s10878-008-9140-6},
Code={http://www.wiomax.com/maos-gcp},
Volume = {18}
}