Pareto Front Algorithm Vectorization

Question

First of all, here is my setup:

• xis a vector n x 1containing the values ​​of the first cost function.
• yis another vector n x 1containing the values ​​of the second cost function.
• ais a vector m x 1containing indices xand yfor verification, which is used to selectively exclude values ​​from the algorithm. If it is not needed, it can be replaced by 1:n.
• It is safe to assume that all combinations are (x,y)unique.

The task is to find the Pareto optimal set of pairs of values (x,y), that is, all pairs that do not dominate. The pair said to be dominant if there is another pair (u,v)such that u <= x && v <= yand one of these comparisons are strict: u < x || v < y. In other words, a pair dominates if the other pair is better in one value and no worse in another.

My research up to this point has given three working algorithms, which, unfortunately, all depend on the cycles. Here's how they work and how long I got to run them with x, yand alength 1e8:

• Sort xin ascending order. Add the first pair to the Pareto set.
• Scroll x. Add each pair to the Pareto set, where the ypair is lower than the previous pair y.

- 80.204052 .

 

• min(x). .
• , y , y.
• 1, 2 .

- 2.993350 .

 

• (x,y).
• (u,v) x >= u && y >= v.

- 105.924814 .

, , . , - . , , :

ap = a(y < min(y(x == min(x))) | x < min(x(y == min(y))));

, , min(x) min(y), . , , , . < <= , (, ). , :

0.800385 .

---

script, , , ,

for i=1:25
    x = randi(8,10,1);
    y = randi(8,10,1);
    a = 1:10;
    ap = a(y < min(y(x == min(x))) | x < min(x(y == min(y)))); %// algorithm here
    figure(1);
    subplot(5,5,i);
    plot(a,x,'b',a,y,'r',ap,x(ap),'b.',ap,y(ap),'r.','MarkerSize',20);
    axis([0,11,0,9]);
    set(gca,'XGrid','on','YGrid','on','XTick',1:10,'YTick',0:8);
    figure(2);
    subplot(5,5,i);
    plot(x,y,'b.',x(ap),y(ap),'ro','MarkerSize',10);
    axis([0,9,0,9]);
end

Answer 1

, ( ), , 30% :

>> testPareto(1e8);
Recursive:
Elapsed time is 4.507267 seconds.
Loop:
Elapsed time is 6.136856 seconds.
Vector:
Elapsed time is 7.246806 seconds.

, , Matlab. :

function testPareto(dim)

x = rand(dim, 1);
y = rand(dim, 1);

tic;
rR = paretoRecursive(x, y);
disp('Recursive:');
toc;

tic;
rL = paretoLoop(x, y);
disp('Loop:');
toc;

tic;
rV = paretoVector(x, y);
disp('Vector:');
toc;

end

function result = paretoLoop(x, y)
    result = zeros(numel(x), 2);
    off = 1;
    loop = true;
    while loop
        xmin = min(x);
        ymin = min(y(x == xmin));
        yfilter = y < ymin;
        result(off, :) = [xmin ymin];
        off = off + 1;
        if any(yfilter)
            x = x(yfilter);
            y = y(yfilter);
        else
            loop = false;
            result(off:end, :) = [];
        end
    end
end

function result = paretoRecursive(x, y)
    xmin = min(x);
    ymin = min(y(x == xmin));
    yfilter = y < ymin;
    if any(yfilter)
        result = [xmin ymin; paretoRecursive(x(yfilter), y(yfilter))];
    else
        result = [xmin ymin];
    end
end

function result = paretoVector(x, y)
    xmin = min(x);
    xfilter = x == xmin;
    ymin = min(y(xfilter));
    yfilter = y < ymin;
    if any(yfilter)
        [x, ind] = sort(x(yfilter));
        y = y(yfilter);
        y = y(ind);
        yfilter = [true; y(2:end) < cummin(y(1:end-1))];
        result = [xmin x(yfilter)'; ymin y(yfilter)']';
    else
        result = [xmin ymin];
    end
end