MAOS-TSP: Project Portal

  • 0

MAOS-TSP: Project Portal

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

Related Information: 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 Contact

CkyUNmzUYAAdZOV

License Information: You can redistribute and/or modify it under the terms of the Creative Commons Non-Commercial 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.004 [Download | github]:

– Add a parameter “opt=[length]” to use the length of the shortest tour as another stopping criterion. (Based on the request by J. Bossek)

Version V1.0.003:

– 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:

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

For example, it 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
--------------------------------------------------------------------------------------------------
opt          integer    >0           None            The lower bound tour length for termination          
//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 and Jiming Liu. Multiagent optimization system for solving the traveling salesman problem (TSP). IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 39(2): 489-502, 2009. [pdf] [Code] [doi] [Bibtex]
@Article{xie2009multiagent,
Title = {Multiagent optimization system for solving the traveling salesman problem ({TSP})},
Author = {Xiao-Feng Xie and Jiming Liu},
Journal = {IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics},
Year = {2009},
Number = {2},
Pages = {489--502},
PDF={http://www.wiomax.com/team/xie/paper/TSMCB09.pdf},
DOI={10.1109/TSMCB.2008.2006910},
Code={http://www.wiomax.com/maos-tsp},
Volume = {39}
}

  • 0

MAOS-GCP: Project Portal

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-QAPMAOS-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
[1] Xiao-Feng Xie and Jiming Liu. Graph coloring by multiagent fusion search. Journal of Combinatorial Optimization, 18(2): 99-123, 2009. [pdf] [Code] [doi] [Bibtex]
@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}
}

  • 0

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.

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

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.

What’s New

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.

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

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.

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

References
[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. [pdf] [Code] [doi] [Bibtex]
@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}
}

  • 0

MAOS-FSP: Project Portal

MAOS-FSP [1] is a multiagent optimization system (MAOS) for solving the Flowshop Scheduling Problem (FSP). MAOS-FSP shares the MAOS kernel with other MAOS applications (e.g. MAOS-GCP and MAOS-TSP), and contains some modules that are specifically for tacking FSP.

Related Information: 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-FSP is free software; you can redistribute it and/or modify it under the Creative Commons Non-Commercial License 3.0.

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

What’s New

Version V1.0.001 [Download | Github]:

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

Directories & Files
binary	                           // the binary code of MAOS-FSP
source                             // the source code of MAOS-FSP
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
	|-----> FSP                // the setting directory for FSP solvers
                |-----> solver     // the directory containing solver script files (the name of each file is Solver_Name)
|-----> tasks                      // task directory
        |-----> FSP
                |-----> instance   // FSP instances (Problem_Name with the default suffix .txt) 
                |-----> solution   // the directory for storing solutions of FSP 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.

Command Line & Parameters

MAOS-FSP 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 FSP: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

FSP: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.

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

References
[1] Xiao-Feng Xie. Round-table group optimization for sequencing problems. International Journal of Applied Metaheuristic Computing, 3(4): 1-24, 2012. [pdf] [Code] [doi] [Bibtex]
@Article{Xie2012a,
Title = {Round-table group optimization for sequencing problems},
Author = {Xiao-Feng Xie},
Journal = {International Journal of Applied Metaheuristic Computing},
Year = {2012},
Number = {4},
Pages = {1-24},
PDF={http://www.wiomax.com/team/xie/paper/IJAMC12.pdf},
DOI={10.4018/jamc.2012100101},
Code={http://www.wiomax.com/maos-qap},
Volume = {3}
}

  • 0

MAOS-QAP: Project Portal

MAOS-QAP [1] is a cooperative group optimization system (MAOS) for solving the Quadratic Assignment Problem (QAP).

Related Information: MAOS-QAP shares the MAOS kernel with other MAOS applications (e.g. MAOS-GCP and MAOS-TSP), and contains some modules that are specifically for tacking QAP. 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-QAP is free software; you can redistribute it and/or modify it under the Creative Commons Non-Commercial License 3.0.

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

What’s New

Version V1.0.001 [Download | Github]:

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

Directories & Files
binary	                           // the binary code of MAOS-QAP
source                             // the source code of MAOS-QAP
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
	|-----> QAP                // the setting directory for QAP solvers
                |-----> solver     // the directory containing solver script files (the name of each file is Solver_Name)
|-----> tasks                      // task directory
        |-----> QAP
                |-----> instance   // QAP instances (Problem_Name with the default suffix .txt) 
                |-----> solution   // the directory for storing solutions of QAP 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.

Command Line & Parameters

MAOS-QAP 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 QAP: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

QAP: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.

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

References
[1] Xiao-Feng Xie. Round-table group optimization for sequencing problems. International Journal of Applied Metaheuristic Computing, 3(4): 1-24, 2012. [pdf] [Code] [doi] [Bibtex]
@Article{Xie2012a,
Title = {Round-table group optimization for sequencing problems},
Author = {Xiao-Feng Xie},
Journal = {International Journal of Applied Metaheuristic Computing},
Year = {2012},
Number = {4},
Pages = {1-24},
PDF={http://www.wiomax.com/team/xie/paper/IJAMC12.pdf},
DOI={10.4018/jamc.2012100101},
Code={http://www.wiomax.com/maos-qap},
Volume = {3}
}

  • 0

Social Cognitive Optimization (SCO): Project Portal

sco_logoSocial Cognitive Optimization (SCO) [1, 2] is an optimization algorithm for solving the (constrained) numerical optimization problem. SCO is an agent-based model based on the observational learning mechanism in human social cognition. In CGOS [3], SCO was hybridized with differential evolution (DE) to obtain better results than individual algorithms on a common set of benchmark problems.

Related Information: Please find other related code and software in our Source Code Library.

Basic Description What’s New Problem to be solved Setting Parameters Output Information References Contact

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

Problem to be solved: (constrained) numerical optimization problem (NOP), or called the nonlinear programming problem.

System Requirements: SCO is a platform-independent software developed by JAVA version 1.4 or above.

Command line (examples): $ java SCO Problem=<Problem_Name> [NAME=VALUE] …

What’s New

Version V1.0.001 [Download | Github]:

It implements the original SCO algorithm [1] & [2].

  • Setting parameters: Problem, N, T, NL.

Problem to be solved

The problem to be solved is (constrained) numerical optimization problem (NOP), including nonlinear programming problems.

To implement your own problem instance, you need create a JAVA source file, normally placed in the directory problem/unconstrained (if the problem has no constraint) or problem/constrained (if the problem has constraints).

Implementation Tips: 1) all the variable bounds must be specified; 2)  any equality constraint should be relaxed by a small tolerance value (e.g., ε=1E-4 for problem.constrained.Michalewicz_G3); and 3) problem.ProblemEncoder and problem.UnconstrainedProblemEncoder are the parental classes of all constrained (e.g., problem.constrained.Michalewicz_G1) and unconstrained (e.g., problem.unconstrained.GoldsteinPrice) problems, respectively.

More detailed description on the problem and implementation can be found here.

Setting parameters [NAME=VALUE]
NAME         VALUE_type  Range      Default_Value   Description
Problem      String      *	    <Problem_Name>  The problem to be solved
//For example: problem.constrained.Michalewicz_G2 is the default value
------------------------------------------------------------------------------------------------------

N            integer     >5         70              General: The number of agents
T            integer     >1         2000            General: The maximum learning cycles
NL           integer     >1         3*N             For the library: The number of Points

//The total number of evaluation times is N*T+NL
//The program outputs runtime information of the best solution every "Tout" cycles.

Output Information

[Parsing information]: provide the parsing information for all input parameters.

[Setting information]: show the information of all setting parameters for the algorithm.

[Runtime information]: The program outputs runtime information, i.e., the evaluation values <Vcon, Vopt> of the best solution, at every “Tout” cycles.
//Vopt: the value of objective function; Vcon: the weighted constraint violation value (≥0): it is not outputted if Vcon≡0 since there is no violation

[Summary information]: At the end, it outputs the input variables, response values, and evaluation values <Vcon, Vopt> of the best solution.

References
[1] Xiao-Feng Xie, Wen-Jun Zhang, and Zhi-Lian Yang. Social cognitive optimization for nonlinear programming problems. In International Conference on Machine Learning and Cybernetics (ICMLC), pages 779-783, Beijing, China, 2002. [pdf] [Code] [doi] [Bibtex]
@InProceedings{Xie:2002p779,
Title = {Social cognitive optimization for nonlinear programming problems},
Author = {Xiao-Feng Xie and Wen-Jun Zhang and Zhi-Lian Yang},
Booktitle = {International Conference on Machine Learning and Cybernetics (ICMLC)},
Year = {2002},
PDF={http://www.wiomax.com/team/xie/paper/ICMLC02A.pdf},
DOI={10.1109/ICMLC.2002.1174487},
Code={http://www.wiomax.com/sco},
Address = {Beijing, China},
Pages = {779--783}
}
[2] Xiao-Feng Xie and Wen-Jun Zhang. Solving engineering design problems by social cognitive optimization. In Genetic and Evolutionary Computation Conference (GECCO), pages 261-262, Seattle, WA, USA, 2004. [pdf] [Code] [doi] [Bibtex]
@InProceedings{Xie:2004p261,
Title = {Solving engineering design problems by social cognitive optimization},
Author = {Xiao-Feng Xie and Wen-Jun Zhang},
Booktitle = {Genetic and Evolutionary Computation Conference (GECCO)},
Year = {2004},
Pages = {261--262},
PDF={http://www.wiomax.com/team/xie/paper/GECCO04_SCO.pdf},
DOI={10.1007/978-3-540-24854-5_27},
Code={http://www.wiomax.com/sco},
Address = {Seattle, WA, USA}
}
[3] Xiao-Feng Xie, Jiming Liu, and Zun-Jing Wang. A cooperative group optimization system. Soft Computing, 18(3): 469-495, 2014. [pdf] [doi] [Bibtex]
@Article{xie2014cooperative,
Title = {A cooperative group optimization system},
Author = {Xie, Xiao-Feng and Liu, Jiming and Wang, Zun-Jing},
Journal = {Soft Computing},
Year = {2014},
Number = {3},
Pages = {469--495},
Volume = {18},
PDF={http://www.wiomax.com/team/xie/paper/SOCO14.pdf},
DOI={10.1007/s00500-013-1069-8},
Publisher = {Springer}
}

  • 0

Dissipative Particle Swarm Optimization (DPSO)

The dissipative particle swarm optimization (DPSO) is developed according to the self-organization of dissipative structure. The negative entropy is introduced into the particle swarm to construct an opening dissipative system that is far-from-equilibrium so as to driving the evolutionary process towards better fitness.

  • Xiao-Feng Xie, Wen-Jun Zhang, and Zhi-Lian Yang. A dissipative particle swarm optimization. In Congress on Evolutionary Computation (CEC), pages 1456-1461, Honolulu, HI, USA, 2002. [PDF] [Code] [DOI] [Bibtex]
    @InProceedings{Xie:2002p1456,
    Title = {A dissipative particle swarm optimization},
    Author = {Xiao-Feng Xie and Wen-Jun Zhang and Zhi-Lian Yang},
    Booktitle = {Congress on Evolutionary Computation (CEC)},
    Year = {2002},
    Address = {Honolulu, HI, USA},
    PDF={http://www.wiomax.com/team/xie/paper/CEC02.pdf},
    DOI={10.1109/CEC.2002.1004457},
    Code={http://www.wiomax.com/dpso},
    Pages = {1456--1461}
    }

  • 0

DEPSO Algorithm: Project Portal

depso_logoDEPSO [1], or called DEPS, is an algorithm for (constrained) numerical optimization problem (NOP). DEPSO combines the advantages of Particle Swarm Optimization (PSO) and Differential Evolution (DE). It is incorporated into cooperative group optimization (CGO) system [2].

The DEPSO paper has been cited over 400 times with various applications. DEPSO was also implemented (by Sun Microsystems Inc.) into NLPSolver (Solver for Nonlinear Programming), an extension of Calc in Apache OpenOffice.

Related Information: Please find other related code and software in our Code Library.

Basic Description What’s New Problem to be solved Setting Parameters Output Information References Contact

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

System Requirements: DEPSO is a platform-independent software developed by JAVA version 1.4 or above.

Command line (examples): $ java DEPSO Problem=<Problem_Name> [NAME=VALUE] …

What’s New


Version V1.0.004: [Github]

  • Allow dynamically accessing problem instance.

Version V1.0.003: [download].

  • The adaptive constraints relaxing (ACR) rule [3] might tackle the problem with equality constraints more efficiently than the basic constraint-handling (BCH) rule does.
  • Newly introduced parameters: isACR.

Version V1.0.002:

  • Bug fixed (Reported by Miklos Espak, Nov 16, 2010): ProblemEncoder.java

Version V1.0.001:

  • For boundary-handling, the cycled version [4] instead of the periodic version [5] is considered, so that all new solutions are generated within the original search space, as well as the agents are searching within a virtually infinite space. In addition, the limitation of maximal velocity is no longer required.

Version V1.0.000:

  • It implements the original DEPSO algorithm [1].
  • Setting parameters: Problem, N, T, Tout, FACTOR, CR, c1, c2, weight.

Problem to be solved

The problem to be solved is (constrained) numerical optimization problem (NOP), including nonlinear programming problems.

To implement your own problem instance, you need create a JAVA source file, normally placed in the directory problem/unconstrained (if the problem has no constraint) or problem/constrained (if the problem has constraints).

Implementation Tips: 1) all the variable bounds must be specified; 2)  any equality constraint should be relaxed by a small tolerance value (e.g., ε=1E-4 for problem.constrained.Michalewicz_G3); and 3) problem.ProblemEncoder and problem.UnconstrainedProblemEncoder are the parental classes of all constrained (e.g., problem.constrained.Michalewicz_G1) and unconstrained (e.g., problem.unconstrained.GoldsteinPrice) problems, respectively.

More detailed description on the problem and implementation can be found here.

Setting parameters [NAME=VALUE]
NAME    VALUE_type   Range      Default_Value   Description
Problem  String      *		<Problem_Name>  The problem to be solved
//For example: problem.constrained.Michalewicz_G2 is the default value
-----------------------------------------------------------------------------------------

N        integer     >5         70 		The number of agents
T        integer     >1         2000		The maximum learning cycles
//The total number of evaluation times is about N*T

isACR    boolean                false           Constraint-handling: BCH(false), ACR(true)
//Basic constraint-handling (BCH) rule or adaptive constraints relaxing (ACR) rule

Tout     integer     >0         100		The output interval (not important)
//The program outputs runtime information of the best solution every "Tout" cycles.

FACTOR   real        (0, 1.2]   0.5  	        DE: scale constant
CR       real        [0, 1]     0.9  	        DE: crossover constant
//The parameters of DE operator, there are two suggested settings for DE:
// 1) FACTOR=0.5, CR=0.9; 2) FACTOR=0.5, CR=0.1

c1       real        [0, 2]     1.494           PSO: learning factor for pbest
c2       real        [0, 2]     1.494           PSO: learning factor for gbest
weight   real        [0, 1]     0.729           PSO: inertia weight
//The parameters of PSO operator, default values: c1=c2=1.494, weight=0.729

Output Information

[Parsing information]: provide the parsing information for all input parameters.

[Setting information]: show the information of all setting parameters for the algorithm.

[Runtime information]: The program outputs runtime information, i.e., the evaluation values <Vcon, Vopt> of the best solution, at every “Tout” cycles.
//Vopt: the value of objective function; Vcon: the weighted constraint violation value (≥0), which is not outputted if Vcon≡0 since there is no violation

[Summary information]: At the end, it outputs the input variables, response values, and evaluation values <Vcon, Vopt> of the best solution.

References
[1] Wen-Jun Zhang and Xiao-Feng Xie. DEPSO: Hybrid particle swarm with differential evolution operator. In IEEE International Conference on Systems, Man, and Cybernetics, pages 3816-3821, Washington, DC, USA, 2003. IEEE. [pdf] [Code] [doi] [Bibtex]
@InProceedings{Zhang:2003p3816,
Title = {{DEPSO}: Hybrid particle swarm with differential evolution operator},
Author = {Wen-Jun Zhang and Xiao-Feng Xie},
Booktitle = {IEEE International Conference on Systems, Man, and Cybernetics},
Year = {2003},
PDF={http://www.wiomax.com/team/xie/paper/SMCC03.pdf},
DOI={10.1109/ICSMC.2003.1244483},
Code={http://www.wiomax.com/depso},
Address = {Washington, DC, USA},
Pages = {3816--3821},
Publisher = {IEEE}
}
[2] Xiao-Feng Xie, Jiming Liu, and Zun-Jing Wang. A cooperative group optimization system. Soft Computing, 18(3): 469-495, 2014. [pdf] [doi] [Bibtex]
@Article{xie2014cooperative,
Title = {A cooperative group optimization system},
Author = {Xie, Xiao-Feng and Liu, Jiming and Wang, Zun-Jing},
Journal = {Soft Computing},
Year = {2014},
Number = {3},
Pages = {469--495},
Volume = {18},
PDF={http://www.wiomax.com/team/xie/paper/SOCO14.pdf},
DOI={10.1007/s00500-013-1069-8},
Publisher = {Springer}
}
[3] Xiao-Feng Xie, Wen-Jun Zhang, and De-Chun Bi. Handling equality constraints by adaptive relaxing rule for swarm algorithms. In Congress on Evolutionary Computation (CEC), pages 2012-2016, Portland, OR, USA, 2004. [pdf] [doi] [Bibtex]
@InProceedings{Xie:2004p2012,
Title = {Handling equality constraints by adaptive relaxing rule for swarm algorithms},
Author = {Xiao-Feng Xie and Wen-Jun Zhang and De-Chun Bi},
Year = {2004},
Pages = {2012--2016},
Booktitle = {Congress on Evolutionary Computation (CEC)},
PDF={http://www.wiomax.com/team/xie/paper/CEC04_ECH.pdf},
DOI={10.1109/CEC.2004.1331143},
Address = {Portland, OR, USA}
}
[4] Xiao-Feng Xie and Jiming Liu. A compact multiagent system based on autonomy oriented computing. In IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT), pages 38-44, Compiegne, France, 2005. IEEE. [pdf] [doi] [Bibtex]
@InProceedings{Xie:2005p1406,
Title = {A compact multiagent system based on autonomy oriented computing},
Author = {Xiao-Feng Xie and Jiming Liu},
Booktitle = {IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT)},
Address = {Compiegne, France},
Year = {2005},
PDF={http://www.wiomax.com/team/xie/paper/IAT05.pdf},
DOI={10.1109/IAT.2005.6},
Pages = {38--44},
Publisher = {IEEE}
}
[5] Xiao-Feng Xie and Wen-Jun Zhang. SWAF: Swarm algorithm framework for numerical optimization. In Genetic and Evolutionary Computation Conference (GECCO), pages 238-250, Seattle, WA, USA, 2004. Springer. [pdf] [doi] [Bibtex]
@InProceedings{Xie:2004p238,
Title = {{SWAF}: Swarm algorithm framework for numerical optimization},
Author = {Xiao-Feng Xie and Wen-Jun Zhang},
Booktitle = {Genetic and Evolutionary Computation Conference (GECCO)},
Year = {2004},
PDF={http://www.wiomax.com/team/xie/paper/GECCO04_SWAF.pdf},
DOI={10.1007/978-3-540-24854-5_21},
Address = {Seattle, WA, USA},
Pages = {238--250},
Publisher = {Springer}
}

  • 0

Particle Swarm Optimization (PSO) Software

Particle swarm optimization (PSO) is a population-based stochastic optimization technique inspired by swarm intelligence. The underlying motivation for the development of PSO algorithm was social behavior of animals such as bird flocking, fish schooling, and swarm theory. The fundamental to the development of PSO is a hypothesis that social sharing of information among peers offers an evolutionary advantage. One of reasons that PSO is attractive is that there are very few parameters to be adjusted.

The following PSO software are provided in the Code Library:

  • DPSO (Dissipative Particle Swarm Optimization) [Project Portal & Code | Doc]: It is a PSO variant that was developed according to the self-organization of dissipative structure. The negative entropy is introduced to construct an opening dissipative system that is far-from-equilibrium so as to driving the irreversible evolution process towards a better fitness.
  • DEPSO (or called DEPS) [Project Portal & Code | Doc]: It is an algorithm that hybridizes the advantages of both PSO and Differential Evolution (DE) for solving (constrained) numerical optimization problem (NOP).

PSO has been incorporated into the cooperative group optimization (CGO) system for realizing various competitive hybrid algorithms.


  • 0

Polymath8: Bounded Gaps between Primes

The Polymath8 project, led by the Fields Medalist Dr. Terence Tao and in collaboration with a team of top mathematicians, was launched to optimize the records of the bounded gaps between primes based on the breakthrough work of “Bounded gaps between primes” by Dr. Yitang Zhang. He proved that there are infinitely many pairs of primes with a finite gap, and thus resolved a weak form of the twin prime conjecture.

Introduction

In number theory, an admissible k-tuple is a set of k distinct integers that do not include the complete modulo set of residue classes (i.e. the values 0 through p – 1) of any prime pk.

Zhang showed that in some k0 values, for every admissible k0-tuple, there are infinitely many positive integers n to shift the k0-tuple such that each shifted k0-tuple contains at least two primes, and thus the width H of the admissible k0-tuple establishes the upper bound for the gap between primes.

Zhang initally showed any k0 ≥ 3,500,000 (which leads to H ≤ 70,000,000) is adequate for the bounding purpose. A polymath8 project was then started to find smaller k0 values and smaller H(k0) values for them.

Code & Data
  • Here is the code K0Finder (Java, bash, and maple are required), and a k0 Table, for optimal k0 of MPZ(i)(ϖ, δ) in different settings of cϖ, cδ, i.
  • Here is the code KTupleFinder (Java) for minimizing the width value H of an admissible k-tuple for a given k.
Publications

Polymath8a authors: Wouter Castryck, Etienne Fouvry, Gergely Harcos, Emmanuel Kowalski, Philippe Michel, Paul Nelson, Eytan Paldi, Janos Pintz, Andrew V. Sutherland, Terence Tao, Xiao-Feng Xie

Polymath8b authors: Ignace Bogaert, Aubrey de Grey, Gergely Harcos, Emmanuel Kowalski, Philippe Michel, James Maynard, Paul Nelson, Pace Nielsen, Eytan Paldi, Andrew V. Sutherland, Terence Tao, Xiao-Feng Xie

Other Information

rnoti-jj-15-cov1– Media coverage: Notices of the AMSDer Spiegel

– Polymath8 project for finding bounded intervals with primes.

New bounds on gaps between primes by Andrew V. Sutherland.

– A new database has been set for collecting narrow admissible k-Tuples.

– The theoretical progress can be found in the blog of Terence Tao.