矢量化帕累托前算法

Question

首先，这里是我的设置：

• x是包含第一成本函数的值的n x 1载体。
• y是另一个包含第二个成本函数值的n x 1向量。
• a是包含x和y索引的m x 1向量，以用于选择性地排除算法中的值。除非需要，否则可以用1:n替代。
• 假设所有组合(x,y)都是唯一的是安全的。

任务是找到pareto最优值对组合(x,y)，也就是所有未被支配的对。如果存在另一对(u,v)，则一对称为支配，使得u <= x && v <= y和其中一个比较严格：u < x || v < y。换句话说，如果另一对在一个值中更好，而另一个中的另一个更糟，则一对是主导的。

我到目前为止的研究已经产生了三种工作算法，不幸的是它们都依赖于循环。下面是他们是如何工作的，什么时候我得到了与x，y和长度1e8的a运行它们：

升序

1. 排序x。将第一对添加到pareto集。
2. Loop through x。将每一对添加到帕雷托集合，其中y比先前帕雷托对的y低。

已用时间为80.204052秒。

 

1. 查找min(x)。将该对添加到pareto集。
2. 选择所有对，其中y低于先前添加的对y。
3. 转到第1步，除非第2步导致空集。

已用时间为2.993350秒。

 

1. 遍历所有对(x,y)。
2. 删除所有对(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秒。

---

下面是我使用来检查怎么算法确实，随意使用它

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