Многокритериальные задачи. Паретовские решения

контрольная работа

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;

}

Делись добром ;)