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

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

License information: MAOS-QKP 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-QKP is a platform-independent software developed by JAVA version 1.5 or above.

What's New

Version: V1.0.001 [download (Binary & Source Codes)]:

Directories & Files

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].

Command Line & Parameters

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

Moreover, the "-cp" option is used for loading the binary file "../binary/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.

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.

The result file will be stored at the directory "myprojects/results".

The best solution (better than any previous solutions) will be stored at the directory "myprojects/tasks/QKP/solution" (of the QKPLIB format).

References

[1] Xiao-Feng Xie, Jiming Liu. A mini-swarm for the quadratic knapsack problem. IEEE Swarm Intelligence Symposium (SIS), Honolulu, HI, USA, 2007: 190-197. [DOI]