README.md 10.8 KB
Newer Older
nachorequeno's avatar
nachorequeno committed
1
# ParetoLib
2
[![pipeline status](https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/tempo/multidimensional_search/badges/master/pipeline.svg)](https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/tempo/multidimensional_search/commits/master)
3
[![coverage report](https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/tempo/multidimensional_search/badges/master/coverage.svg)](https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/tempo/multidimensional_search/-/jobs/artifacts/master/file/Tests/coverage/index.html?job=test)
4

nachorequeno's avatar
nachorequeno committed
5
**Multidimensional Pareto Boundary Learning Library for Python**
nachorequeno's avatar
nachorequeno committed
6

nachorequeno's avatar
nachorequeno committed
7
8
9
This library implements an algorithm for learning the boundary between an 
upward-closed set *X1* and its downward-closed component *X2* (i.e., *X=X1+X2*). 
Generally, the library supports spaces *X*  of dimension N.
nachorequeno's avatar
nachorequeno committed
10

nachorequeno's avatar
nachorequeno committed
11
12
13
14
15
16
17
18
19
20
21
22
23
24
The algorithm selects sampling points *x=(x1,x2,...,xN)* for which it submits membership queries 'is *x* in *X1*?' 
to an external *Oracle*.
Based on the *Oracle* answers and relying on monotonicity, the algorithm constructs 
an approximation of the boundary, called the Pareto front.

The algorithm generalizes binary search on the continuum from one-dimensional 
(and linearly-ordered) domains to multi-dimensional (and partially-ordered) ones. 

Applications include the approximation of Pareto fronts in multi-criteria optimization 
and parameter synthesis for predicates where the influence of parameters is monotone.
This library is based on the work-in-progress paper [1]. 

[1] [Learning Monotone Partitions of Partially-Ordered Domains (Work in Progress) 2017.〈hal-01556243〉] (https://hal.archives-ouvertes.fr/hal-01556243/)

nachorequeno's avatar
nachorequeno committed
25
26
## Installation

27
28
29
30
31
32
33
34
35
This library requires Python 2.7.9 or Python 3.4+. 
If you have the python tool 'pip' installed, just download the Wheel artifact (*.whl file) 
from the Download->Artifact section in Gitlab and run:

$ pip install *.whl --user 

If you prefer to compile and install the source code by yourself, then execute the following steps. 
The dependencies of the tool are listed in requirements.txt. 
You can run the following command for installing them:
nachorequeno's avatar
nachorequeno committed
36

nachorequeno's avatar
- Tests    
nachorequeno committed
37
$ pip install -r requirements.txt
nachorequeno's avatar
nachorequeno committed
38
39
40

Afterwards you need to run:

nachorequeno's avatar
- Tests    
nachorequeno committed
41
$ python setup.py build
42

nachorequeno's avatar
- Tests    
nachorequeno committed
43
$ python setup.py install
nachorequeno's avatar
nachorequeno committed
44

nachorequeno's avatar
nachorequeno committed
45
for installing the library. In order to run all the tests, you must execute:
nachorequeno's avatar
nachorequeno committed
46

nachorequeno's avatar
nachorequeno committed
47
$ python setup.py test
48
49
50

or

nachorequeno's avatar
nachorequeno committed
51
52
$ cd Tests

nachorequeno's avatar
- Tests    
nachorequeno committed
53
$ pytest
nachorequeno's avatar
nachorequeno committed
54

nachorequeno's avatar
nachorequeno committed
55
from the root of the project folder.
nachorequeno's avatar
nachorequeno committed
56
57
58
59
60
61
62
63


For users that don’t have write permission to the global site-packages directory or 
do not want to install our library into it, Python enables the selection of the target 
installation folder with a simple option:

$ pip install -r requirements.txt --user

64
65
$ python setup.py build

nachorequeno's avatar
nachorequeno committed
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
$ python setup.py install --user

In Unix/Mac OS X environments:, the structure of the installation folders will be the following:

|Type of file |  Installation directory|
|------------ | --------------------------|
| modules | userbase/lib/pythonX.Y/site-packages |
| scripts | userbase/bin |
| data | userbase |
| C headers | userbase/include/pythonX.Y/distname |

And here are the values used on Windows:

| Type of file |  Installation directory |
|------------ | --------------------------|
| modules | userbase\PythonXY\site-packages |
| scripts | userbase\Scripts |
| data | userbase |
| C headers | userbase\PythonXY\Include\distname |

The advantage of using this scheme compared to the other ones described in [2] is that the 
user site-packages directory is under normal conditions always included in sys.path, which 
means that there is no additional step to perform after running the setup.py script to 
finalize the installation.

[2] Installing Python Modules (Legacy version) (https://docs.python.org/2/install/)

nachorequeno's avatar
nachorequeno committed
93
## Running
nachorequeno's avatar
nachorequeno committed
94

nachorequeno's avatar
nachorequeno committed
95
### Definition of the Oracle
nachorequeno's avatar
nachorequeno committed
96
97
98
99
100
101
The learning algorithm requires the existence of an external *Oracle* that guides 
the multidimensional search.
The *Oracle* determines the membership of a point *x=(x1,x2,...,xN)* to any of 
the two closures (*X1* or *X2*). 
The complete space is denoted by *X = X1 + X2*.

102
103
104
105
106
107
108
For the moment, our library only supports three kinds of *Oracles* for inferring 
the Pareto's front and learning the membership of a point *x* to any of the two closures.
Nevertheless, the number of *Oracles* can be enlarged easily by implementing
an abstract interface (ParetoLib/Oracle/Oracle.py). 

The first *Oracle*, named *OracleFunction*, is a 'proof of concept'.
It defines the membership of point *x* to the closure *X1* based on polynomial constraints.
nachorequeno's avatar
nachorequeno committed
109
110
111
112
For instance, *x1 = x2* may define the boundary. Every point *x* having the coordinates
*x1 > x2* will belong to *X1*, while every point *x* having *x1 < x2* will belong to *X2*

The second *Oracle*, named *OraclePoint*, defines the membership of point *x*
requenoj's avatar
requenoj committed
113
114
to the closure *X1* based on a cloud of points that denote the border. For instance, next image shows the Pareto front,
which is internally stored in a NDTree data structure [3]. 
nachorequeno's avatar
nachorequeno committed
115

nachorequeno's avatar
nachorequeno committed
116
![alt text][paretofront]
nachorequeno's avatar
nachorequeno committed
117

118
The third *Oracle*, named *OracleSTL*, defines the membership of point *x* depending
119
120
121
122
123
124
on the success in evaluating a Signal Temporal Logic (STL) [4] formula over a signal.
The STL formula is parametrized with a set of variables which correspond to the coordinates
of the point *x* (i.e., the number of parameters in the STL formula is equal to the dimension of *x*). 
Every point *x* satisfying the STL formula will belong to *X1*, while every point *x* 
falsifying it will belong to *X2*.

125
126
127
128
129
130

Finally, the last *Oracle*, named *OracleSTLe*, defines the membership of point *x* depending
on the success in evaluating a quantitative measure over a signal by using an extension of 
Signal Temporal Logic (STLe) [5]. The STLe formula is parametrized similarly to a STL formula
used by the *OracleSTL*.

131
The last image shows the partitioning that is learnt by our algorithm thanks to
132
133
134
the *Oracle* guidance. The green side corresponds to *X1* and the red side corresponds 
to *X2*. A gap in blue may appear between the two closures, which corresponds to the border 
and can be set arbitrarily small depending on the accuracy required by the user.
nachorequeno's avatar
nachorequeno committed
135

nachorequeno's avatar
nachorequeno committed
136
![alt text][multidim_search]
nachorequeno's avatar
nachorequeno committed
137
138


139
140
Samples of *OracleFunction*, *OraclePoint*, *OracleSTL* and *OracleSTLe* definitions 
can be found in Tests/Oracle/Oracle* and Tests/Search/Oracle* folders.
nachorequeno's avatar
nachorequeno committed
141

nachorequeno's avatar
nachorequeno committed
142
143
[paretofront]: https://gricad-gitlab.univ-grenoble-alpes.fr/requenoj/multidimensional_search/blob/master/doc/image/pareto_front.png "Pareto front"
[multidim_search]: https://gricad-gitlab.univ-grenoble-alpes.fr/requenoj/multidimensional_search/blob/master/doc/image/multidim_search.png "Upper and lower closures"
nachorequeno's avatar
nachorequeno committed
144
145

[3] [ND-Tree-based update: a Fast Algorithm for the Dynamic Non-Dominance Problem] (https://ieeexplore.ieee.org/document/8274915/)
requenoj's avatar
requenoj committed
146
147

[4] [Monitoring Temporal Properties of Continuous Signals] (https://doi.org/10.1007/978-3-540-30206-3_12)
nachorequeno's avatar
nachorequeno committed
148

149
150
[5] [Specification and Efficient Monitoring Beyond STL] (pending)

nachorequeno's avatar
nachorequeno committed
151
152
### Running the multidimensional search
The core of the library is the algorithm implementing the multidimensional search of the Pareto boundary.
153
154
155
156
157
158
It is implemented by the module ParetoLib.Search.Search, which encapsulates the complexity of the learning 
process in three functions (i.e., *Search2D*, *Search3D* and *SearchND*) depending on the dimension of 
the space *X*.

The learning algorithm is compatible for any dimension *N*, and for any *Oracle* defined according to the 
template ParetoLib.Oracle.Oracle. For the moment, ParetoLib includes support for *OracleFunction*, 
159
*OraclePoint*, *OracleSTL* and *OracleSTLe* oracles.
160

161
The input parameters of the learning process are the following:
162
163
164
* xspace: the N-dimensional space that contains the upper and lower closures, 
represented by a list of minimum and maximum possible values for each dimension
 (i.e., min_cornerx, max_cornerx, etc.).
nachorequeno's avatar
nachorequeno committed
165
* oracle: the external knowledge repository that guides the learning process.
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
* epsilon: a real representing the maximum desired distance between a point *x* 
of the space and a point *y* of the Pareto front.
* delta: a real representing the maximum area/volume contained in the border
 that separates the upper and lower closures; delta is used as a stopping criterion
 for the learning algorithm (sum(volume(cube) for all cube in border) < delta).
* max_step: the maximum number of cubes in the border that the learning algorithm 
will analyze, in case of the stopping condition *delta* is not reached yet. 
* sleep: time in seconds that each intermediate 2D/3D graphic must be shown in the screen 
(i.e, 0 for not showing intermediate results).
* blocking: boolean that specifies if the intermediate 2D/3D graphics must be explicitly
 closed by the user, or they are automatically closed after *sleep* seconds.
* simplify: boolean that specifies if the number of cubes in the 2D/3D graphics must
be minimized. 
* opt_level: an integer specifying which version of the learning algorithm to use
 (i.e., 0, 1 or 2; use 2 for fast convergence).
181
* parallel: boolean that specifies if the user desires to take advantage of the 
182
183
multithreading capabilities of the computer.
* logging: boolean that specifies if the algorithm must print traces for
nachorequeno's avatar
nachorequeno committed
184
debugging options.
185
186
187
188
189
190
               
   
As a result, the function returns an object of the class *ResultSet* with the distribution
of the space *X* in three subspaces: a lower closure, an upper closure and a border which 
 contains the Pareto front.
A set of running examples for 2D, 3D and ND can be found in doc/examples and in Test/test_Search.py.
nachorequeno's avatar
nachorequeno committed
191

nachorequeno's avatar
nachorequeno committed
192
```python
193
194
from ParetoLib.Oracle.OracleFunction import OracleFunction
from ParetoLib.Search.Search import Search2D, EPS, DELTA, STEPS
nachorequeno's avatar
nachorequeno committed
195
196

# File containing the definition of the Oracle
nachorequeno's avatar
nachorequeno committed
197
nfile='Tests/Search/OracleFunction/2D/test0.txt'
nachorequeno's avatar
nachorequeno committed
198
199
200
201
202
203
204
human_readable=True

# Definition of the n-dimensional space
min_x, min_y = (0.0, 0.0)
max_x, max_y = (1.0, 1.0)

oracle = OracleFunction()
nachorequeno's avatar
nachorequeno committed
205
oracle.from_file(nfile, human_readable)
nachorequeno's avatar
nachorequeno committed
206
207
208
209
210
211
212
rs = Search2D(ora=oracle,
              min_cornerx=min_x,
              min_cornery=min_y,
              max_cornerx=max_x,
              max_cornery=max_y,
              epsilon=EPS,
              delta=DELTA,
nachorequeno's avatar
nachorequeno committed
213
              max_step=STEPS,
nachorequeno's avatar
nachorequeno committed
214
              sleep=0,
215
216
              blocking=False,
              simplify=False,
nachorequeno's avatar
nachorequeno committed
217
218
              opt_level=0,
              parallel=False,
219
              logging=False)
nachorequeno's avatar
nachorequeno committed
220
221
```                          

nachorequeno's avatar
nachorequeno committed
222
### Saving and plotting the results
223
The result of the learning process is saved in an object of the *ResultSet* class.
nachorequeno's avatar
nachorequeno committed
224
225
226
227
This object is a data structure composed of three elements: the upper closure (*X1*), the
lower closure (*X2*), and the gap between X1 and X2 representing the precision error of the
learning process. 
The size of this gap depends on the accuracy of the learning process, which can be tuned by 
228
the EPS and DELTA parameters during the invocation of the learning method.
nachorequeno's avatar
nachorequeno committed
229
230

The ResultSet class provides functions for:
231
232
- Testing the membership of a point *y* to any of the closures.
- Plotting 2D and 3D spaces.
nachorequeno's avatar
nachorequeno committed
233
- Exporting/Importing the results to text and binary files. 
nachorequeno's avatar
nachorequeno committed
234
235