矢量化帕累託前算法

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