System and method for solving multiobjective optimization problems
View Patent ↗A system and method for solving a set of optimization problems initializes a current region of solutions for the set of optimization problems, performs a reduction phase, and provides the optimal solutions within the current region. The reduction phase creates a random sample of points within the current region and identifies a subregion of the current region that very likely does not contain any optimal solutions. The identified subregion is then removed from the current region. If the current region does not satisfies one or more convergence criteria, the process loops back to create another random sample of points and repeats the above-described steps. If, however, the current region does satisfy the convergence criteria, the optimal solutions within the current region are provided to the output device.
1. A method for solving a set of optimization problems using one or more computers having an output device, the method comprising the steps of:
(a) initializing a current region of solutions for the set of optimization problems;
(b) creating a random sample of points within the current region;
(c) identifying a subregion of the current region wherein (1) all the randomly sampled points within the subregion (i) are non-optimal solutions to the set of optimization problems, and (ii) have a common characteristic that is not an effect of the random sampling, and (2) all points within the subregion have the common characteristic;
(d) removing the identified subregion from the current region;
(e) determining whether the current region satisfies one or more convergence criteria;
(f) repeating steps (b) through (e) whenever the convergence criteria are not satisfied; and
(g) providing the optimal solutions within the current region to the output device.
2. The method as recited in claim 1 , wherein:
the random sample of points is created using an unbiased random process, a biased random process, a single-variable inequities process, a shrinking a search rectangle process, a divide-and-conquer process, or a combination thereof;
the subregion is identified using one or more support vector machines, one or more decision trees, one or more learning logic formulas or rules, one or more subgroup discovery methods, any Machine Learning technique that can derive from randomly drawn samples of two populations a classification that reliably separates the two populations, or a combination thereof; or
the one or more convergence criteria comprise a significance criterion, a volume reduction criterion, a reduction factor criterion, a number of rounds, a number of function evaluations, an efficiency of the step of creating the random sample of points, the subregion cannot be identified, or a combination thereof.
3. The method as recited in claim 1 , wherein:
the set of optimization problems are provided by an optimization target;
the current region of solutions comprises a set of bounding vectors for a current geometric shape;
the subregion comprises an n-dimensional geometric shape wherein n=1 to 20 or more;
the random sample points having scale values significantly greater than zero are non-optimal solutions to the set of optimization problems; or
the provided solutions have scale values that are equal to or approximately equal to zero.
4. The method as recited in claim 1 , wherein the common characteristic is determined using one or more alternate random processes.
5. The method as recited in claim 1 , further comprising the steps of:
(b1) adjusting the random sampled points based on one or more previously identified and removed subregions; or
(b2) determining a total number of expected function evaluations for the method.
6. The method as recited in claim 1 , wherein the step of providing the solutions within the current region to the output device comprises the steps of:
(g1) determining a characterization of the points within the current region that (1) applies to all optimal and near optimal points, and (2) does not apply to the nonoptimal points;
(g2) deriving a compact approximate description of a solution space from the characterization, wherein the compact approximate description comprises one or more formulas, thresholds or geometric bodies; and
(g3) providing the compact approximate description of the solution space to the output device.
7. The method as recited in claim 6 , wherein the compact approximate description comprises a union of rectangles.
8. A method for solving a set of optimization problems using one or more computers having an output device, the method comprising the steps of:
(a) initializing a current region of solutions for the set of optimization problems;
(b) creating a random sample of points within the current region;
(c) computing h(x) for each xεS using
f
k
min
=
min
{
f
k
(
x
)
❘
x
∈
S
_
}
f
k
max
=
max
{
f
k
(
x
)
❘
x
∈
S
_
}
g
k
(
x
)
=
{
(
f
k
(
x
)
-
f
k
min
)
(
f
k
max
-
f
k
min
)
,
x
∈
S
_
and
f
k
max
>
f
k
min
0
,
x
∈
S
_
and
f
k
max
=
f
k
min
1
,
x
∈
(
S
-
S
_
)
d
(
x
,
y
)
=
max
k
{
g
k
(
x
)
-
g
k
(
y
)
}
,
y
∈
S
and
x
and
y
are
comparable
h
(
x
)
=
max
y
∈
S
{
d
(
x
,
y
)
❘
x
and
y
are
comparable
}
where: S contains the xεS for which all entries ƒ k (x) of ƒ(x) are finite,
for each index k, 1≦k≦m , 0≦g k (x)≦1,
0≦d(x,y)≦1,
d(x,x)=0, and
xεS and yεS are comparableif g(x)≧g(y);
(d) selecting a set of α and β pairs where 0<α<β<1 and α is not small;
(e) selecting a first α and β pair;
(f) determining a set S α − and S β + ; using
S α − ={xεS|h ( x )<α}
S β + ={xεS|h ( x )>β};
(g) determining whether one or more termination criteria are satisfied;
(h) whenever the termination criteria are not satisfied, discretizing S α − and S β + , obtaining a training set A and a training set B, computing one or more disjunctive normal form formulas that separate the sets A and B, defining a polyhedron P α,β and an associated significance q α,β from the disjunctive normal form formulas, expanding the sets S α − and S β + , and repeating step (g);
(i) determining whether all the α and β pairs have been processed whenever the termination criteria are satisfied;
(j) selecting the next α and β pair and repeating steps (f)-(i) whenever all the α and β pairs have not been processed;
(k) selecting the α and β pair having a highest significance and identifying an associated polyhedron as a subregion to be removed whenever all the α and β pairs have been processed;
(l) removing the subregion identified by the selected α and β pair from the current region;
(m) determining whether the current region satisfies one or more convergence criteria;
(n) repeating steps (b) through (m) whenever the convergence criteria are not satisfied;
(o) defining a set S to consist of all x determined in steps (b) through (n), and computing h(x) for each xεS using
f
k
min
=
min
{
f
k
(
x
)
❘
x
∈
S
_
}
f
k
max
=
max
{
f
k
(
x
)
❘
x
∈
S
_
}
g
k
(
x
)
=
{
(
f
k
(
x
)
-
f
k
min
)
(
f
k
max
-
f
k
min
)
,
x
∈
S
_
and
f
k
max
>
f
k
min
0
,
x
∈
S
_
and
f
k
max
=
f
k
min
1
,
x
∈
(
S
-
S
_
)
d
(
x
,
y
)
=
max
k
{
g
k
(
x
)
-
g
k
(
y
)
}
,
y
∈
S
and
x
and
y
are
comparable
h
(
x
)
=
max
y
∈
S
{
d
(
x
,
y
)
❘
x
and
y
are
comparable
}
where: S contains the xεS for which all entries ƒ k (x) of ƒ(x) are finite,
for each index k, 1≦k≦m, 0≦g k (x)≦1,
0≦d(x,y)≦1,
d(x,x)=0, and
xεS and yεS are comparable if g(x)≧g(y);
(p) selecting a second set of α and β pairs where 0<α<β<1 and both α and β are small;
(q) determining a second set S α − and S β + using
S α − ={ xεS|h ( x )<α}
S β + ={ xεS|h ( x )>β};
(r) discretizing S α − and S β + , obtaining a second training set A and a second training set B;
(s) computing one or more second disjunctive normal form formulas that separate the second sets A and B;
(t) defining polyhedra P i corresponding to the clauses of a formula F A′ of the second disjunctive normal form formulas that separates the second set A from the second set B;
(u) defining S i ={xεS|xεP i };
(v) enclosing each S i by a rectangle T i using:
a k i =min{ x k | xεS i }
b k i =max{ x k | xεS i }
T I ={ x|a i ≦ x≦b i }; and
(w) providing a compact approximate description of the solution space to the output device, wherein the compact approximate description comprises a union T of the rectangles T i .
9. The method as recited in claim 8 , wherein the selected α and β pair is selected using one or more tie breakers whenever multiple α and β pairs have the highest significance, wherein the tie breakers comprise a smaller stage number, a larger α value, or a smaller β value.
10. The method as recited in claim 8 , wherein:
the random sample of points is created using an unbiased random process, a biased random process, a single-variable inequities process, a shrinking a search rectangle process, a divide-and-conquer process, or a combination thereof or
the one or more convergence criteria comprise a significance criterion, a volume reduction criterion, a reduction factor criterion, a number of rounds, a number of function evaluations, an efficiency of the step of creating the random sample of points, the subregion cannot be identified, or a combination thereof.
11. The method as recited in claim 8 , wherein:
the set of optimization problems are provided by an optimization target;
the current region of solutions comprises a set of bounding vectors for a current geometric shape;
the subregion comprises an n-dimensional geometric shape wherein n=1 to 20 or more; or
the random sample points having scale values significantly greater than zero are non-optimal solutions to the set of optimization problems.
12. The method as recited in claim 8 , further comprising the steps of:
(b1) adjusting the random sampled points based on one or more previously identified and removed subregions; or
(b2) determining a total number of expected function evaluations for the method.
13. The method as recited in claim 8 , further comprising the steps of:
eliminating one or more nonoptimal points such that the rectangles are unbiased; or
generalizing the set of optimization problems using one or more integer variables or a set of conditional pareto optimality solutions.
14. A computer program embodied on a non-transitory computer readable storage medium that is executed using one or more computers having an output device for solving a set of optimization problems comprising:
(a) a code segment for initializing a current region of solutions for the set of optimization problems;
(b) a code segment for creating a random sample of points within the current region;
(c) a code segment for identifying a subregion of the current region wherein (1) all the randomly sampled points within the subregion (i) are non-optimal solutions to the set of optimization problems, and (ii) have a common characteristic that is not an effect of the random sampling, and (2) all points within the subregion have the common characteristic;
(d) a code segment for removing the identified subregion from the current region;
(e) a code segment for determining whether the current region satisfies one or more convergence criteria;
(f) a code segment for repeating steps (b) through (e) whenever the convergence criteria are not satisfied; and
(g) a code segment for providing the optimal solutions within the current region to the output device.
15. The computer program as recited in claim 14 , further comprising:
(b1) a code segment for adjusting the random sampled points based on one or more previously identified and removed subregions; or
(b2) a code segment for determining a total number of expected function evaluations for the method.
16. The computer program as recited in claim 14 , wherein the code segment for providing the solutions within the current region to the output device comprising:
(g1) a code segment for determining a characterization of the points within the current region that (1) applies to all optimal and near optimal points, and (2) does not apply to the nonoptimal points;
(g2) a code segment for deriving a compact approximate description of a solution space from the characterization, wherein the compact approximate description comprises one or more formulas, thresholds or geometric bodies; and
(g3) a code segment for providing the compact approximate description of the solution space to the output device.
17. A system for solving a set of optimization problems comprising:
a computer comprising one or more processors, a memory communicably coupled to the processors and a communications interface communicably coupled to the processor(s);
one or more output devices communicably coupled to the processor(s) via the communications interface;
an optimization target communicably coupled to the processor(s) via the communications interface; and
wherein the processor(s) perform the steps of:
(a) initializing a current region of solutions for the set of optimization problems;
(b) creating a random sample of points within the current region;
(c) identifying a subregion of the current region wherein (1) all the randomly sampled points within the subregion (i) are non-optimal solutions to the set of optimization problems, and (ii) have a common characteristic that is not an effect of the random sampling, and (2) all points within the subregion have the common characteristic;
(d) removing the identified subregion from the current region;
(e) determining whether the current region satisfies one or more convergence criteria;
(f) repeating steps (b) through (e) whenever the convergence criteria are not satisfied; and
(g) providing the optimal solutions within the current region to the output device.
18. The system as recited in claim 17 , wherein:
the processor(s) operate in parallel;
the random sample of points is created using an unbiased random process, a biased random process, a single-variable inequities process, a shrinking a search rectangle process, a divide-and-conquer process, or a combination thereof;
the subregion is identified using one or more support vector machines, one or more decision trees, one or more learning logic formulas or rules, one or more subgroup discovery methods, any Machine Learning technique that can derive from randomly drawn samples of two populations a classification that reliably separates the two populations, or a combination thereof; or
the one or more convergence criteria comprise a significance criterion, a volume reduction criterion, a reduction factor criterion, a number of rounds, a number of function evaluations, an efficiency of the step of creating the random sample of points, the subregion cannot be identified or a combination thereof.
19. The system as recited in claim 17 , wherein:
the set of optimization problems are provided by an optimization target;
the current region of solutions comprises a set of bounding vectors for a current geometric shape;
the subregion comprises an n-dimensional geometric shape wherein n=1 to 20 or more;
the random sample points having scale values significantly greater than zero are non-optimal solutions to the set of optimization problems; or
the provided solutions have scale values that are equal to or approximately equal to zero.
20. The system as recited in claim 17 , wherein the common characteristic is determined using one or more alternate random processes.
21. The system as recited in claim 17 , wherein the processor(s) further perform the steps of:
(b1) adjusting the random sampled points based on one or more previously identified and removed subregions; or
(b2) determining a total number of expected function evaluations for the method.
22. The system as recited in claim 17 , wherein the step of providing the solutions within the current region to the output device comprises the steps of:
(g1) determining a characterization of the points within the current region that (1) applies to all optimal and near optimal points, and (2) does not apply to the nonoptimal points;
(g2) deriving a compact approximate description of a solution space from the characterization, wherein the compact approximate description comprises one or more formulas, thresholds or geometric bodies; and
(g3) providing the compact approximate description of the solution space to the output device.
23. The system as recited in claim 22 , wherein the compact approximate description comprises a union of rectangles.
24. A system for solving a set of optimization problems comprising:
a computer comprising one or more processors, a memory communicably coupled to the processors and a communications interface communicably coupled to the processor(s);
one or more output devices communicably coupled to the processor(s) via the communications interface;
an optimization target communicably coupled to the processor(s) via the communications interface; and
wherein the processor(s) perform the steps of:
(a) initializing a current region of solutions for the set of optimization problems;
(b) creating a random sample of points within the current region;
(c) computing h(x) for each xεS using
f
k
min
=
min
{
f
k
(
x
)
❘
x
∈
S
_
}
f
k
max
=
max
{
f
k
(
x
)
❘
x
∈
S
_
}
g
k
(
x
)
=
{
(
f
k
(
x
)
-
f
k
min
)
(
f
k
max
-
f
k
min
)
,
x
∈
S
_
and
f
k
max
>
f
k
min
0
,
x
∈
S
_
and
f
k
max
=
f
k
min
1
,
x
∈
(
S
-
S
_
)
d
(
x
,
y
)
=
max
k
{
g
k
(
x
)
-
g
k
(
y
)
}
,
y
∈
S
and
x
and
y
are
comparable
h
(
x
)
=
max
y
∈
S
{
d
(
x
,
y
)
❘
x
and
y
are
comparable
}
where: S contains the xεS for which all entries ƒ k (x) of ƒ(x) are finite,
for each index k, 1≦k≦m , 0≦g k (x)≦1,
0≦d(x,y)≦1,
d(x,x)=0, and
xεS and yεS are comparableif g(x)≧g(y);
(d) selecting a set of α and β pairs where 0<α<β<1 and α is not small;
(e) selecting a first α and β pair;
(f) determining a set S α − and S β + using
S α − ={ xεS|h ( x )<α}
S β + ={ xεS|h ( x )<β};
(g) determining whether one or more termination criteria are satisfied;
(h) whenever the termination criteria are not satisfied, discretizing S α − and S β + , obtaining a training set A and a training set B, computing one or more disjunctive normal form formulas that separate the sets A and B, defining a polyhedron P α,β and an associated significance q α,β from the disjunctive normal form formulas, expanding the sets S α − , and repeating step (g);
(i) determining whether all the α and β pairs have been processed whenever the termination criteria are satisfied;
(j) selecting the next α and β pair and repeating steps (f)-(i) whenever all the α and β pairs have not been processed;
(k) selecting the α and β pair having a highest significance and identifying an associated polyhedron as a subregion to be removed whenever all the α and β pairs have been processed;
(l) removing the subregion identified by the selected α and β pair from the current region;
(m) determining whether the current region satisfies one or more convergence criteria;
(n) repeating steps (b) through (m) whenever the convergence criteria are not satisfied;
(o) defining a set S to consist of all x determined in steps (b) through (n), and computing h(x) for each xεS using
f
k
min
=
min
{
f
k
(
x
)
❘
x
∈
S
_
}
f
k
max
=
max
{
f
k
(
x
)
❘
x
∈
S
_
}
g
k
(
x
)
=
{
(
f
k
(
x
)
-
f
k
min
)
(
f
k
max
-
f
k
min
)
,
x
∈
S
_
and
f
k
max
>
f
k
min
0
,
x
∈
S
_
and
f
k
max
=
f
k
min
1
,
x
∈
(
S
-
S
_
)
d
(
x
,
y
)
=
max
k
{
g
k
(
x
)
-
g
k
(
y
)
}
,
y
∈
S
and
x
and
y
are
comparable
h
(
x
)
=
max
y
∈
S
{
d
(
x
,
y
)
❘
x
and
y
are
comparable
}
where: S contains the xεS for which all entries ƒ k (x) of ƒ(x) are finite,
for each index k, 1≦k≦m, 0≦g k (x)≦1,
0≦d(x,y)≦1,
d(x,x)=0, and
xεS and yεS are comparable if g(x)≧g(y);
(p) selecting a second set of α and β pairs where 0<α<β<1 and both α and β are small;
(q) determining a second set S α − and S β + using
S α − ={ xεS|h ( x )<}
S β + ={ xεS|h ( x )>β};
(r) discretizing S α − and S β + , obtaining a second training set A and a second training set B;
(s) computing one or more second disjunctive normal form formulas that separate the second sets A and B;
(t) defining a polyhedron P i corresponding to the clauses of a formula F A′ of the second disjunctive normal form formulas that separates the second set A from the second set B;
(u) defining S i ={xεS|xεP i };
(v) enclosing each S i by a rectangle T i using:
a k i =min{ x k | xεS i }
b k i =max{ x k | xεS i }
T i ={ x|a i ≦ x≦b i }; and
(w) providing a compact approximate description of the solution space to the output device, wherein the compact approximate description comprises a union T of the rectangles T i .
25. The system as recited in claim 24 , wherein the selected α and β pair is selected using one or more tie breakers whenever multiple α and β pairs have the highest significance, wherein the tie breakers comprise a smaller stage number, a larger α value, or a smaller β value.
26. The system as recited in claim 24 , wherein:
the processor(s) operate in parallel;
the random sample of points is created using an unbiased random process, a biased random process, a single-variable inequities process, a shrinking a search rectangle process, a divide-and-conquer process, or a combination thereof; or
the one or more convergence criteria comprise a significance criterion, a volume reduction criterion, a reduction factor criterion, a number of rounds, a number of function evaluations, an efficiency of the step of creating the random sample of points, the subregion cannot be identified, or a combination thereof.
27. The system as recited in claim 24 , wherein:
the set of optimization problems are provided by an optimization target;
the current region of solutions comprises a set of bounding vectors for a current geometric shape;
the subregion comprises an n-dimensional geometric shape wherein n=1 to 20 or more; or
the random sample points having scale values significantly greater than zero are non-optimal solutions to the set of optimization problems.
28. The system as recited in claim 24 , wherein the processor(s) further perform the steps of:
(b1) adjusting the random sampled points based on one or more previously identified and removed subregions; or
(b2) determining a total number of expected function evaluations for the method.
29. The system as recited in claim 24 , wherein the processor(s) further perform the steps of:
enlarging the sets such that the rectangles are unbiased; or
generalizing the set of optimization problems using one or more integer variables or a set of conditional pareto optimality solutions.