Численные методы построения множества Парето

 

Задача выделения всех эффективных точек в общем виде еще не решена, но разработано довольно много различных методов отыскания эффективных точек для двухкритериальных и линейных многокритериальных задач [4].

Рассмотрим простейший случай (два критерия). Имеем задачу:

 

 (2.1)

 

Каждой точке   соотношения

 

 (2.2)

 

ставят в соответствие некоторую точку   в плоскости критериев. Соотношения (2.2) определяют отображение множества  на .

Множество носит  название множества достижимости. Множество Парето представляет собой лишь часть границы множества достижимости.

Приближенное построение множества Парето сводится к последовательному решению задач математического программирования. Опишем одну из возможных схем расчета.

Фиксируем некоторые желательные значения критериев и :

 

 

Значения C ₁ и С₂ следует выбрать так, чтобы они принадлежали множеству достижимости. Теперь решаем две оптимизационные задачи:

 

1)        

2)        

 

Решив эти задачи, определим точки а и b ( рис.2.1). Проведя через них прямую 1, получим простейшую аппроксимацию множества Парето. Для уточнения аппроксимации решаем следующие задачи:

 

3)        

4)        

 

Находим еще две точки - c и d, принадлежащие этому множеству. Значения С₃ и С₄ снова должны принадлежать множеству достижимости.

Через точки а, с, d и b проводим ломаную 2, которая будет следующим приближением. Очень часто подобной информации о структуре множества Парето уже бывает достаточно для решения практических задач.

Если множество Парето выпукло, то, увеличивая количество точек, которые определяются описанным способом, строим многогранник, аппроксимирующий это множество с любой степенью точности. Однако практика дает примеры множеств Парето, которые не являются выпуклыми. Тогда задача их аппроксимации резко усложняется.

 

Рис.2.1 Аппроксимация множества Парето.

 

Таким образом, с помощью расчета множества Парето можно существенно сократить коли Таким образом, предлагается заменить исходную задачу задачей дискретной оптимизации на графе. При этом искомому маршруту будет соответствовать оптимальный путь в графе.

Описание программы

 

Программа для расчета множества Парето написана на языке С++. В файле data. txt хранятся исходные данные о пикселях: порядковый номер пикселя, значения рисков и значения стоимостей. Число пикселей 23. Элементы множества Парето выделяются по определению множества Парето.

При расчете множества Парето в программе осуществляется перебор всех возможных решений.

В результате выполнения программы происходит не более n сравнений решений, где n - число пикселей. Данные организованы в виде списка. Если при сравнении получаем доминируемое решение, то его удаляем из списка и в дальнейшем в сравнении не участвует, что приводит к сокращению числа операций.