Многокритериальные задачи. Паретовские решения
3.2 Алгоритм поиска парето-оптимальных решений
Шаг 1. Положить P(Y) =Y , i =1, j = 2 . Тем самым образуется так называемое текущее множество парето-оптимальных векторов, которое в начале работы алгоритма совпадает с множеством Y , а в конце составит искомое множество парето-оптимальных векторов. Алгоритм устроен таким образом, что искомое множество парето-оптимальных векторов получается из Y последовательным удалением заведомо неоптимальных векторов.
Шаг 2. Проверить выполнение неравенства . Если оно оказалось истинным, то перейти к Шагу 3. В противном случае перейти к Шагу 5.
Шаг 3. Удалить из текущего множества векторов P(Y) вектор , так как он не является парето-оптимальным. Затем перейти к Шагу 4.
Шаг 4. Проверить выполнение неравенства j < N . Если оно имеет место, то положить j = j +1 и вернуться к Шагу 2. В противном случае - перейти к Шагу 7.
Шаг 5. Проверить справедливость неравенства . В том случае, когда оно является истинным, перейти к Шагу 6. В противном случае - вернуться к Шагу 4.
Шаг 6. Удалить из текущего множества векторов P(Y) вектор и перейти к Шагу 7.
Шаг 7. Проверить выполнение неравенства i < N -1. В случае истинности этого неравенства следует последовательно положить i = i +1 , а затем j = i +1. После этого необходимо вернуться к Шагу 2. В противном случае (т.е. когда) вычисления закончить. К этому моменту множество парето-оптимальных векторов построено полностью.
Вначале реализуем вспомогательные методы:
// поэлементное сравнение вектора v1 с вектором v2
private void Compare(List<int> v1, List<int> v2)
{
more = 0;
less = 0;
equal = 0;
for (int i = 0; i < v1.Count; i++)
{
if (v1[i] > v2[i])
more++;
else if (v1[i] < v2[i]) less++;
else equal++;
}
}
// возвращает истину если v1 >= v2
private bool MoreOrEqual()
{
if (more >= 0 && less == 0)
return true;
else return false;
}
Далее напишем рекурсивную процедуру удаления доминируемых решений, опираясь на алгоритм, описанный выше:
// y - список решений
public void DeleteDominated(List<List<int>> y)
{
foreach (List<int> yi in y)
{
foreach (List<int> gj in y)
{
if (!Equals(gj, yi))
{
Compare(gj, yi);
if (MoreOrEqual())
{
y.Remove(yi);
DeleteDominated(y);
return;
}
Compare(yi, gj);
if (MoreOrEqual())
{
y.Remove(gj);
DeleteDominated(y);
return;
}
}
}
}
}
И наконец получаем метод, возвращающий список парето-оптимальных решений:
public List<List<int>> GetParetoList(List<List<int>> y)
{
DeleteDominated(y);
return y;
}