MAOS-QKP: Project Portal

MAOS-QKP is a multiagent optimization system (MAOS) for solving the Quadratic Knapsack Problem (QKP).

Related Information: MAOS-QKP shares the MAOS kernel with other MAOS applications (e.g. Graph Coloring Problem (GCP) and Traveling Salesman Problem (TSP)). Please find other related code and software in our Source Code Library.

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

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

Version: V1.0.001 [Download | Github]:

• Solver “STD_NLDUX”: It implements the original MAOS-QKP algorithm [1].
• Setting parameters: QKP:Problem, N, T, Tcon, Solver.

binary	                           // the binary code of MAOS-QKP
source                             // the source code of MAOS-QKP
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
	|-----> QKP                // the setting directory for QKP solvers
                |-----> solver     // the directory containing solver script files (the name of each file is Solver_Name)
                                   // Example: STD_NLDUX (Solver_Name is STD_NLDUX)
|-----> tasks                      // task directory
        |-----> QKP
                |-----> instance   // QKP instances of the B&S format (Problem_Name with the default suffix .txt) 
                                   // Example: jeu_100_025_01.txt (Problem_Name is jeu_100_025_01)
                |-----> solution   // the directory for storing solutions of QKP instances
                                   // For a normal solution, the file name is Problem_Name.(objective value).sln
                                   // If objective value is removed from the file name, the solution is considered as optimal.
                                   // Example: jeu_100_025_01.sln

// For your convenience, here are the benchmark instances and their solutions used in [1].

MAOS-QKP 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 -cp ../binary/MAOS_BIN.jar maosKernel.MAOSExecuter QKP:Problem=jeu_100_025_01 N=500 T=500 DUP_TIMES=10 solver=STD_NLDUX

//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_BIN.jar".

General Parameters:

NAME         VALUE_type   Range      Default_Value   Description

QKP:Problem  String      *	     <Problem_Name>  The problem instance to be solved
--------------------------------------------------------------------------------------------------
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          2		     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.

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/QKP/solution" (of the QKPLIB format).

[1] Xiao-Feng Xie and Jiming Liu. A mini-swarm for the quadratic knapsack problem. In IEEE Swarm Intelligence Symposium, pages 190-197, Honolulu, HI, USA, 2007.

@InProceedings{Xie:2007p190,
Title = {A mini-swarm for the quadratic knapsack problem},
Author = {Xiao-Feng Xie and Jiming Liu},
Year = {2007},
Pages = {190--197},
Address = {Honolulu, HI, USA},
PDF={http://www.wiomax.com/team/xie/paper/SIS07.pdf},
DOI={10.1109/SIS.2007.368045},
Code={http://www.wiomax.com/maos-qkp},
Booktitle = {IEEE Swarm Intelligence Symposium}
}