|
Альтернативы из множества Парето называются парето-решениями, эффективными, или недоминируемыми (непревосходимыми) решениями. При решении многокритериальных задач используется принцип Парето, заключающийся в том, что наилучшее решение следует выбирать среди альтернатив, принадлежащих множеству Парето). Этот принцип выполняется в большинстве практических ситуаций, когда альтернативы оцениваются по противоречивым критериям. Он позволяет сузить исходное множество альтернатив, причем окончательный выбор остается за пользователем. Альтернативы, входящие во множество Парето, попарно не сравнимы друг с другом, т.е. по одним критериям лучше одна альтернатива, по другим другая и т.д., и их невозможно улучшить одновременно по всем критериям. Поэтому изучение множества Парето позволяет найти компромисс между различными противоречивыми требованиями, что весьма важно при разработке САПР. При этом пользователь может судить о том, какова "цена" увеличения одного из критериев, и как это скажется на ухудшении остальных. Построение множества Парето является необходимым при решении многокритериальных задач выбора в больших системах (управление, проектирование промышленных и транспортных объектов и т.п.). Отметим еще одну важную особенность альтернатив из множества Парето: каждая из них представляет целый класс (группу) решений, превосходящих остальные по одному или нескольким критериям. Поиск решения многокритериальных задач выбора еще более усложняется, если изучаемая система взаимодействует с окружающей средой. В этом случае решение зависит от так называемых неконтролируемых метров. Например, для измерительных систем это могут быть влияющие величины. Неконтролируемое изменение состояния окружающей среды являются дополнительным источником неоднозначности выбора наилучшего решения. Рассмотрим два подхода, позволяющих получить обоснованные решения. 79 |
93 p n j p jj KxKxd /1 1 0)()( ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ −= ∑ = . При 2=p получаем Евклидово расстояние, при 1=p расстояние Хемминга и т.д. (см. §5.2). Выбор параметра p зависит от условий задачи и предпочтений ЛПР. Отметим, что если в качестве точки отсчета использовать не абсолютный максимум, а абсолютный минимум, то в выражении (58) операция min изменится на max. Обзор методов многокритериальной оптимизации можно найти в [14,24,52]. Выделение множества Парето. Наряду с рассмотренными методами, использующими свертку в пространстве критериев, применяются и другие подходы, относящиеся к методам второй группы, основанные на свертке в множестве альтернатив, при которых пытаются уменьшить число возможных вариантов решений, исключив заведомо плохие. Один из подходов, обладающий большой общностью, был предложен итальянским экономистом В.Парето в 1904 г. и называется методом, основанным на принципе Парето. Для уменьшения числа альтернатив исходного множества выделяют множество Парето, являющееся подмножеством исходного. Определим множество Парето в виде: { })()(),()(,: xKxjKxKxiKXxXxx jjii >∃≥∀∈∀∈= ππππ , (59) т.е. альтернатива принадлежит множеству Парето, если она не хуже других по всем критериям и хотя бы по одному критерию лучше. Альтернативы из множества Парето называются парето-решениями, эффективными, или недоминируемыми (непревосходимыми) решениями. При решении многокритериальных задач используется принцип Парето, заключающийся в том, что наилучшее решение следует выбирать среди альтернатив, принадлежащих множеству Парето. Этот принцип выполняется в большинстве практических ситуаций, когда альтернативы оцениваются по противоречивым критериям. Он позволяет сузить исходное множество альтернатив, причем окончательный выбор остается за ЛПР. Альтернативы, входящие в множество Парето, попарно не сравнимы друг с другом, т.е. по одним критериям лучше одна альтернатива, по другим другая и т.д., и их невозможно улучшить одновременно по всем критериям. Поэтому изучение множества Парето позволяет найти компромисс между различными противоречивыми требованиями, что весьма важно при разработке САПР. При этом ЛПР может судить о том, какова “цена” увеличения одного из критериев, и как это скажется на ухудшении остальных. Построение множества Парето является необходимым при решении многокритериальных задач выбора в больших системах (управление, проектирование промышленных и транспортных объектов и т.п.). Отметим еще одну важную особенность альтернатив из множества Парето: каждая из них представляет целый класс (группу) решений, превосходящих остальные по одному или нескольким критериям. Поясним это примером. Пусть имеется учебная группа (множество альтернатив), требуется выбрать наилучшего студента (альтернативу) по ряду критериев, например, умение решать задачи, успеваемость, манера поведения, внешний вид, умение говорить и т.п. Предположим, что Андрей лучше всех решает задачи, а по остальным критериям не выделяется. Зато Вера, Галя, Ира, Катя, Лариса имеют высокие значения остальных критериев, так что они в среднем превосходят Андрея, причем Вера лучше всех по успеваемости, а по остальным критериям не хуже других студенток. Тогда Андрей обязательно попадает в 94 множество Парето, так как он уникальный (единственный) по первому критерию, а от группы студенток в Парето попадает один представитель – Вера, хотя остальные студентки превосходят Андрея по нескольким критериям (число критериев здесь не имеет значения). После того как построено множество Парето, для определения наилучшего решения (из оставшихся) применяются методы первой группы: метод свертки, метод главного критерия и т.п. либо графические методы, например, метод диаграмм (см. Приложение 2). Схема поиска наилучшего решения представлена на рис. 19. исходное множество генерирует с учетом альтернатив условий задачи X множество Парето строит π⊂ X ЛПР Наилучшее решение выбирает, используя ∗ x ∈ π методы первой группы Рис. 19. Схема поиска наилучшего решения. Поиск решения многокритериальных задач выбора еще более усложняется , если изучаемая система взаимодействует с окружающей средой. В этом случае решение зависит от так называемых неконтролируемых параметров. Например, для измерительных систем это могут быть влияющие величины (температура, влажность, давление и т.п.),для транспортных – погода, состояние дороги и т.п. Неконтролируемое изменение состояния окружающей среды являются дополнительным источником неоднозначности выбора наилучшего решения. Рассмотрим два подхода, позволяющих получить обоснованные решения. 1. Подход, основанный на принципе наихудшей реакции окружающей среды (метод гарантированного результата). Подход применяется, когда среда ведет себя |