ρMNK-Landscapes: Multiobjective NK-landscapes with objective correlation


| Description | Format | Generator, evaluation functions | Instances |

Description

The four main parameters of the family of ρMNK-landscapes are:

  • ρ: the objective correlation coefficient
  • M: the number of objective functions
  • N: the length of bit strings
  • K: the number of epistatic links (non-linearity)


The multiobjective NK-landscapes with and without objective correlation are described is details in:

  • S. Verel, A. Liefooghe, L. Jourdan, C. Dhaenens. Analyzing the Effect of Objective Correlation on the Efficient Set of MNK-Landscapes. Learning and Intelligent OptimizatioN (LION 5), Lecture Notes in Computer Science (LNCS), Rome, Italy, 2011
  • S. Verel, A. Liefooghe, L. Jourdan, C. Dhaenens. Pareto Local Optima of Multiobjective NK-Landscapes with Correlated Objectives. evoCOP conference, Lecture Notes in Computer Science (LNCS), Turino, Italy, 2011
  • H. Aguirre, K. Tanaka, Working Principles, Behavior, and Performance of MOEAs on MNK-Landscapes, European Journal of Operational Research, vol. 181, pp. 1670-1690, 2007


Format

The syntax of ρMNK-landscapes instances is inspired by the DIMACS Max-Sat format.

An instance is described by the following four sections that must appear in the order shown:

a) Comment section

  1. The section is optional and should be used to give additional information concerning the instance (the name, the source, a general description, etc.)
  2. Each line of the section starts with the letter "c" (lower case)
  3. The section is made of an arbitrary number of consecutive lines

b) Problem section

  1. The section is used to describe the problem type
  2. The section is made of a single line that starts with the letter "p" (lower case)
  3. The line format is the following:
     p rMNK <rho> <M> <N> <K>

where <rho> is a real number that gives objective correlation coefficient, <M> is a positive integer that gives the number of objective functions, <N> is a positive integer that gives the length of bit strings, and <K> is a positive integer that gives the number of epistatic links. These fields are separated by blank or by TAB characters

c) Links section

  1. The section is used to describe the epistatic structure between variables
  2. The sections starts with this line: p links
  3. The following lines gives the structure
  4. The bits are numbered from 0 to N-1. a number l_{m,i,j} means that the fitness contribution i of objective function m depends on the bit l_{m,n,j}.
  5. One column for each objective function
  6. The links are then in order of fitness contribution:

l_{1,0,0} ... l_{M,0,0}
l_{1,0,1} ... l_{M,0,1}
...
l_{1,0,K} ... l_{M,0,K}
...
...
l_{1,N-1,K} ... l_{M,N-1,K}

d) Contribution section

  1. The section is used to describe the fitnes contribution f_{m,i}
  2. The sections starts with this line: p tables
  3. The following lines gives the contribution of each possible bit sub-string
  4. A number y_{m,i,x_i,x_{i1},..., x_{iK}} means that f_{m,i}(x_i,x_{i1},..., x_{iK}) = y_{m,i,x_i,x_{i1},..., x_{iK}}
  5. One column for each objective function
  6. The links are then in order of fitness contribution:

y_{1,0,0...0} ... ... y_{M,0,0...0}
y_{1,0,0...1} ... ... y_{M,0,0...1}
... ...
y_{1,0,1...1} ... ... y_{M,0,1...1}
... ...
... ...
y_{1,N-1,1...1} ... ... y_{M,N-1,1...1}

Example

One example for an instance with a negative objective correlation -0.9, two objectives, a bit string of length 3, and a epistatic degree K=1.

The bit 0 is linked to himself and to the bit 1. The bit 1 is linked to himself and to the bit 0. The bit 2 is linked to himself and to the bit 1.

With K=1, 4 values are needed for each fitness contribution. For the first objective, with x_0x_1=00, f_{1,0}(x_0x_1)=0.2, or with x_1x0=10, f_{1,1}(x_1x_0)=0.5. Notice that the links give the order of bits to compute the fitness contribution.

c
c Example of instance
c
c
p rMNK -0.9 2 3 1
p links
0 0
1 1
1 1
0 0
2 2
1 1
p tables
0.2 0.3
0.8 0.2
0.0 0.9
0.3 0.6
0.8 0.2
0.3 0.7
0.5 0.8
0.3 0.7
0.6 0.4
0.0 0.9
0.2 0.4
0.7 0.3

Source code of generator and evaluation functions

The source code of a instance generator (in R) and the multiobjective fitness functions (in C, C++, java, and under paradiseo framework) are available on the svn of the project:

svn checkout http://svn.code.sf.net/p/mocobench/code/trunk/rmnk/generator mocobench

For more details on project svn, see the sourceforge repository.

You can download the generator which is written in R: rmnkGenerator.R
If you need to install R, please visit the official page of R project

You can also browse the svn repository to download one of the multiobjective fitness function written in C, C++, java, or under paradiseo framework: browse generator repository.

The paradiseo source code is plugged (or can be plugged) with classical multiobjective algorithms (NSGAII, Pareto LS, etc.).


Data files of instances

All instance files are available on the svn of the project. See svn to access directly with svn.

If you want to access only to some instances, you can browse the repository: browse instances repository.

File names are normalized: rmnk_<rho>_<M>_<N>_<K>_<seed>.dat
where <rho>, <M>, <N>, and <K> are the main parameters of the instance, and <seed> is the random seed used to produce the instance with rmnkGenerator.R.

If you don't want to download the instances, you can produce them (and others) with the available scripts written in bash, or in python. They both use the generator in R.