Содержание к диссертации
Введение
Глава 1. Анализ подходов к формализации неопределенности в задачах принятия решений 9
1.1. Общая структура задачи принятия решений и ее особенности 9
1.1.1. Неопределенность информации и способы ее формализации в задачах принятия решений и управления 11
1.1.2. Общая характеристика задач многокритериальной оптимизации 15
1.2. Нечеткие и лингвистические модели представления информации ... 23
1.2.1. Понятие нечеткого множества 23
1.2.2. Нечеткие операции 28
1.3. Современная информационная технология как средство обеспечения интеллектуальности информационных систем 33
Выводы к первой главе 43
Глава 2. Разработка подходов к решению многокритериальных задач четкого и нечеткого математического программирования 45
2.1. Общая конструкция задач нечеткого математического программирования 45
2.2. Нечеткая логическая модель задачи многокритериальной оптимизации 56
2.3. Задача многокритериальной линейной оптимизации с нечеткими коэффициентами целевых функций 64
2.4. Управление инвестиционным портфелем при нечетких значениях доходности и рисков 72
Выводы ко второй главе 76
Глава 3. Взаимодействие целей в задачах многокритериальной оптимизации 78
3.1. Анализ взаимодействия целевых функций 78
3.2. Алгоритм решения многокритериальной задачи, учитывающий характер взаимодействия целевых функций 91
Выводы к третьей главе 99
Глава 4. Многокритериальная задача о назначениях при четких и нечетких коэффициентах целевой функции 100
4.1. Решение четкой многокритериальной задачи о назначениях с помощью генетического алгоритма 101
4.1.1. Генетический алгоритм решения многокритериальной задачи о назначениях 101
4.1.2. Исследование эффективности различных способов кодирования и операторов кроссовера 108
4.2. Генетический алгоритм решения многокритериальной задачи о назначениях при нечетких коэффициентах целевой функции 112
4.2.1. Нечеткая многокритериальная задача о назначениях 113
4.2.2. Генетический алгоритм решения задачи 114
4.2.3. Выбор рекомендуемой точки среди решений, найденных ГА 117
4.2.4. Эксперимент и обсуждение результатов 119
4.3. Программные реализации 122
Выводы к четвертой главе 132
Заключение 133
Список использованной литературы 134
Приложения 141
- Нечеткие и лингвистические модели представления информации
- Нечеткая логическая модель задачи многокритериальной оптимизации
- Алгоритм решения многокритериальной задачи, учитывающий характер взаимодействия целевых функций
- Генетический алгоритм решения многокритериальной задачи о назначениях при нечетких коэффициентах целевой функции
Введение к работе
Актуальность темы. Задачи математического программирования относятся к детерминированным моделям принятия решений. Необходимо заметить, что данный раздел «составляет» классику исследования операций и в теоретическом плане является хорошо «проработанным». Однако реальные прикладные задачи оказываются намного сложнее, чем предусмотрено классическими постановками. Эта сложность обусловливается необходимостью учета многих критериев при принятии решения, порождая класс задач многокритериальной оптимизации. Исключительное значение для решения таких задач играет принцип Парето, согласно которому оптимальное решение следует выбирать среди Парето-оптимальных точек, образующих область компромисса, причем выбор окончательного решения осуществляется с учетом дополнительной информации. Среди различных подходов, который носят в основном эвристический характер, можно выделить метод последовательного сужения множества Парето, основанный на количественной информации о важности критериев (В.Д. Ногин и др.). Заметим, что принцип Парето не является универсальным и применяется только при выполнении ряда аксиом. И даже если эти аксиомы выполняются, построение множества Парето может вызывать значительные трудности. В основе другого подхода к решению проблемы многокритериальности лежит идея последовательных уступок, основанная на ранжировании критериев в порядке убывающей важности и решении однокритериальной задачи, в которой самый важный критерий принимает экстремальное значение, а на остальные накладываются ограничений. Недостаток данного подхода заключается в усложнении ограничивающих условий и необходимости анализа различных вариантов задачи. Переход к однокритериальной задаче возможен и при агрегировании отдельных критериев в некоторый обобщенный (интегральный) критерий с помощью подходящей свертки. При внешней привлекательности такой подход порождает ряд вопросов: неясно, как определить вид функции агрегирования; трудно или невозможно обосновать принцип оценки ее параметров (весовых коэффициентов, показателей степеней и т.п.); проблематична интерпретация полученных результатов. Кроме перечисленных, существуют подходы, ориентированные на определенные классы задач. Так, для решения задач многокритериальных математического программирования с противоречивой системой ограничений применяются комитетные конструкции (Еремин И.И., Мазуров В.Д.), которые выступают аналогом смешанных стратегий использования допустимых решений, удовлетворяющих подсистемам условий В последние десятилетия в рамках математическої эграммирования появились направления, учитывающие особенности 11 єство исходной информации (нечеткое, возможностное, стохастическое, шггервальное программирование). Нечеткие модели оптимизационны -?адая: отличаются разнообразием подходов к их построению (R. F Z. Carlsson, Е. Canestrelli, М. Delgado, F. Herrera, HJ. Zimmermann, С.А. Орловский, A.B. Язенин и др.) и позволяют адекватно учитывать не1 v лъ данных при принятии решений. Необходимость дальнейшей разраОолси подходов к решению многокритериальных задач нечеткого математического программирования обусловливает актуальность дисссл ч ".тонной работы. Диссертационная работа выполнена в рамках одного из основных научных направлений ВГУ «Математическое моделирование, программное и информационное обеспечение, методы вычислительной и прикладной математики и их применение к фундаментальным исследованиям в естественных науках».
Цель и задачи исследования. Цель диссерта ионной работы заключается в разработке моделей и методов м гокритериальной оптимизации в условиях неопределенности, характеризующихся нечеткостью данных. Для достижения цели в работе решались следующие задачи.
1. Анализ подходов к формализации неопределенности и способах ее учета в моделях математического программирования.
2. Разработка оригинальных подходов к формированию моделей и методов для решения многокритериальных задач с четкими и нечеткими целевыми функциями.
3. Разработка методов оценки характера взаимодействия целевых функций в задачах многокритериальной оптимизации с целью их использования как на предварительном этапе математического моделирования, так и на этапе решения.
4. Экспериментальное исследование разрешимости четких и нечетких многокритериальных задач о назначении с помощью генетического алгоритма. Методы исследования базируются на основных положениях теории математического программирования и векторной оптимизации, теории нечетких множеств и нечеткой логики, дискретной математики, технологии эволюционного моделирования.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной.
1. Предложены альтернативные модели для многокритериальной задачи с нечеткими целевыми функциями, построенные на основе кванторных предикатов и (если-то)-правил и отличающиеся тем, что за счет формализации нечетких логических операций могут быть получены частные модели, обеспечивающие гибкость в формировании информационной среды для построения модели конкретной прикладной задачи.
2. Предложен метод решения задачи многокритериальной оптимизации для случая линейных целевых функций с нечеткими коэффициентами, основанный на свойствах операций и сравнении нечетких (треугольных и трапециевидных) чисел.
3. Разработан подход к формализации характера взаимодействия целевых функций в многокритериальных задачах, основанный на вычислении их градиентов. Для случая линейных целевых функций введен коэффициент, позволяющий определить характер их взаимодействия (кооперация, конфликт, независимость) и на его основе осуществить переход к соответствующим нечетким целевым функциям. Предложен метод для решения задачи многокритериальной оптимизации, учитывающий эффект взаимодействия целевых функций.
4. Для многокритериальной задачи о назначениях в четкой и в нечеткой постановках предложен генетический алгоритм нахождения решения, отличающийся использованием оригинальной процедуры оценки приспособленности особей в популяции.
Содержание диссертации соответствует пунктам 1,3 специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ Паспорта специальностей ВАК РФ.
Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации обоснованы корректным использованием математического аппарата, подтверждены результатами вычислительного эксперимента. Практическая значимость результатов работы заключается в том, что предложенный комплекс моделей (в общем случае) математического программирования позволяет учитывать такие факторы реальных прикладных задач, как многокритериальность и нечеткость, что обеспечивает высокую степень адекватности и формирует основу для обоснованного принятия решений. Предложен метод решения задачи о формировании инвестиционного портфеля при нечетких оценках рисков и доходности.
Реализация результатов исследования. Теоретические результаты диссертации в форме моделей, алгоритмов и программ используются в учебном процессе Воронежского государственного университета и Воронежского государственного технического университета при чтении спецкурсов, выполнении дипломных и курсовых работ.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях, семинарах и др. научных мероприятиях: Международная школа-семинар «Современные проблемы механики и прикладной математики» (2007, ВГУ), Всероссийская конференция «Интеллектуальные информационные системы» (2009, ВГТУ), VI-я всероссийская школа-семинар молодых ученых «Управление большими системами» (2009, УдГУ), 32-я международная школа-семинар «Системное моделирование социально-экономических процессов» имени академика С.С.Шаталина (2009, ЦЭМИ), ежегодные научные семинары профессорско-преподавательского состава, аспирантов и студентов Воронежского государственного университета (г. Воронеж, 2006 — 2009).
Публикации. Основные результаты диссертации опубликованы в 10 печатных изданиях, в том числе 2 — из списка изданий, рекомендованных ВАК РФ.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, приложений. Работа содержит 140 страниц текста, включает 48 рисунков и 6 таблиц. Список используемой литературы включает 103 наименования. В первой главе рассмотрены общие проблемы моделирования процесса принятия решений. Описаны важнейшие , факторы, влияющие на выбор оптимального решения: многокритериальность и неопределенность исходной информации. Во второй главе предложены . новые подходы к решению многокритериальных задач. Приведен метод решения задачи многокритериальной оптимизации для случая линейных целевых функций с нечеткими коэффициентами, предложена и реализована методика решения задачи о формировании инвестиционного портфеля. В третьей главе исследуется взаимодействие целевых функций в рамках задачи многокритериальной оптимизации. Введен коэффициент характеризующий взаимодействие как кооперацию, конфликт или независимость. Предложен метод решения задач многокритериальной оптимизации, учитывающий эффект взаимодействия целевых функций. В четвертой главе рассматривается многокритериальная задача о назначениях, в четкой и нечеткой постановке и ее решение с использование генетических алгоритмов. Исследуется эффективность различных операторов корссовера. Реализован оригинальный генетический .
Нечеткие и лингвистические модели представления информации
Основной характеристикой нечеткого множества выступает функция принадлежности. Элемент может принадлежать множеству в большей или меньшей степени. Пусть U - универсальное множество, обозначим через /и (х) є [0,1 J — степень принадлежности элемента хєії к нечеткому множеству А. По сути, /л U — [О, J J представляет собой обобщение понятия характеристической функции hA:U- {0,1} обычного множества А. Согласно [27] нечетким множеством А называется множество упорядоченных пар вида А = (/И2(х)/Х)- Значение /Лд(х)=0 означает отсутствие принадлежности элемента х к множеству А, 1- полную принадлежность. Понятие нечеткого множества играет существенную роль в формализации качественных либо приближенных понятий и представляет собой основу лингвистической модели представления информации. Теория нечетких множеств не призвана конкурировать с теорией вероятностей и статистическими методами.
Она заполняет пробел в области структурированной неопределенности там, где нельзя корректно применять вероятность. Носителем нечеткого множества А называется обычное множество Высотой нечеткого множества называется величина Нечеткое множество А нормально, если Зх є U(h(A) = 1), т.е. его высота равна 1, иначе нечеткое множество называется субнормальным. С помощью понятия нечеткого множества вводятся понятия нечеткой и лингвистической переменных. Нечеткая переменная описывается тройкой (a,U,A), где а — это название переменной, U - универсальное множество (область рассуждений), А - нечеткое множество на [/ с функцией принадлежности рА(х), описывающее ограничения на значение нечеткой переменной а .[27] Нечеткая величина — это нечеткая переменная, определенная на множестве действительных чисел М.[27] Лингвистической переменной называется кортеж (fi,T,U,G,M}, где /? - название переменной; Т = {tj,t2,...} - терм-множество или множество значений переменной /?, причем каждое из них является нечеткой переменной, заданной на универсальном множестве U числовой или нечисловой природы; G - синтаксическое правило, порождающее новые значения переменной /3; М - семантическое правило, которое ставит в соответствие каждой новой нечеткой переменной ее смысл, т.е. нечеткое подмножество универсального множества U. Нечетким числом А называется нечеткая величина А, функция принадлежности ілА(х) которой является выпуклой и унимодальной на Ш. Нечеткое число с модальным значением а можно рассматривать как значение высказывания «х приблизительно равно а». [27] Значения лингвистической переменной (термы) - это нечеткие переменные. Именно лингвистические переменные позволяют формально описывать качественные и приближенные понятия. Существует значительное число типовых форм кривых для задания функций принадлежности [19]. Наибольшее распространение получили: треугольная, трапециевидная и гауссова функции принадлежности, определяющие также типы нечетких чисел. Треугольным нечетким числом
А с центром в точке а, левой шириной / 0 и правой шириной г 0 называется нечеткое множество А с функцией принадлежности Трапециевидным нечетким числом А с отрезком толерантности [а,Ь] , левой шириной / 0 и правой шириной г 0 называется нечеткое множество А с функцией принадлежности Цд(х) Функция принадлежности гауссова типа описывается формулой и оперирует двумя параметрами.
Параметр а обозначает центр нечеткого множества, а параметр а отвечает за крутизну функции (рис. 1.5). В общем виде нечеткие числа и интервалы задаются с помощью так называемых L-R функций [27]. L-функция есть отображение L:M.+ — [0,1], удовлетворяющее следующим условиям: Пусть Цх) и R(x) - функции, удовлетворяющие перечисленным выше условиям. А есть унимодальное нечеткое число LR-типа, если существуют константы 1,г 0, такие, что функция принадлежности нечеткого числа А имеет вид
Нечеткая логическая модель задачи многокритериальной оптимизации
Коротко перечислим преимущества fuzzy-систем по сравнению с другими: возможность оперировать нечеткими входными данными: например, непрерывно изменяющиеся во времени значения (динамические задачи), значения, которые невозможно задать однозначно (результаты статистических опросов, рекламные компании и т.д.); возможность нечеткой формализации критериев оценки и сравнения: оперирование критериями «большинство», «возможно», «преимущественно» и т.д.; возможность качественной (лингвистической) оценки, как входных данных, так и выходных результатов: мы оперируем не только значениями данных, но и их степенью достоверности (не путать с вероятностью!) и ее распределением; возможность проведения быстрого моделирования сложных динамических систем и их сравнительный анализ с заданной степенью точности: оперируя принципами поведения системы, описанными fuzzy-методами, вы, во-первых, не тратите много времени на выяснение точных значений переменных и составление описывающих уравнений, во-вторых, можете оценить разные варианты выходных значений [48].
Что касается отечественного рынка коммерческих систем на основе нечеткой логики, то его формирование началось в середине 1995 года. Популярными являются следующие пакеты: CubiCalc 2.0 RTC - одна из мощных коммерческих экспертных систем на основе нечеткой логики, позволяющая создавать собственные прикладные экспертные системы; CubiQuick - дешевая «университетская» версия пакета CubiCalc; RuleMaker - программа автоматического извлечения нечетких правил из входных данных; FuziCalc - электронная таблица с нечеткими полями, позволяющая делать быстрые оценки при неточных данных без накопления погрешности; OWL - пакет, содержащий исходные тексты всех известных видов нейронных сетей, нечеткой ассоциативной памяти и т.д.
Сегодня элементы нечеткой логики можно найти в десятках промышленных изделий — от систем управления электропоездами и боевыми вертолетами до пылесосов и стиральных машин. Нечеткие экспертные системы для поддержки принятия решений находят широкое применение в медицине и экономике. Она применяется в автомобильной, аэрокосмической и транспортной промышленности, в области изделий бытовой техники, в сфере финансов, анализа и принятия управленческих решений и многих других.
Без применения нечеткой логики немыслимы современные ситуационные центры руководителей западных стран, где принимаются ключевые политические решения и моделируются разные кризисные ситуации. Одним из впечатляющих примеров масштабного применения нечеткой логики стало комплексное моделирование системы здравоохранения и социального обеспечения Великобритании (National Health Service - NHS), которое впервые позволило точно оценить и оптимизировать затраты на социальные нужды.
Не обошли средства нечеткой логики и программные системы, обслуживающие большой бизнес. Первыми, разумеется, были финансисты, задачи которых требуют ежедневного принятия правильных решений в сложных условиях непредвиденного рынка.
Вслед за финансистами когнитивными нечеткими схемами заинтересовались промышленные гиганты США. Motorola, General Electric, Otis Elevator, Pacific Gas & Electric, Ford и другие в начале 90-х начали инвестировать в разработку изделий, использующих нечеткую логику. Имея солидную финансовую «поддержку», фирмы, специализирующиеся на нечеткой логике, получили возможность адаптировать свои разработки для широкого круга применений. «Оружие элиты» вышло на массовый рынок.
Среди лидеров нового рынка выделяется американская компания Hyper Logic, основанная в 1987 году Фредом Уоткинсом (Fred Watkins). Сначала компания специализировалась на нейронных сетях, однако в скором времени целиком сконцентрировалась на нечеткой логике. Недавно вышла на рынок вторая версия пакета CubiCalc фирмы HyperLogic, которая является одной из мощнейших экспертных систем на основе нечеткой логики. Пакет содержит интерактивную оболочку для разработки нечетких экспертных систем и систем управления, а также runime модуль, позволяющий оформлять созданные пользователем системы в виде отдельных программ.
Кроме Hyper Logic среди «патриархов» нечеткой логики можно назвать фирмы IntelligenceWare, InfraLogic, Aptronix. Всего же на мировом рынке представлено более 100 пакетов, которые так или иначе используют нечеткую логику. В трех десятках СУБД реализована функция нечеткого поиска. Собственные программы на основе нечеткой логики анонсировали такие гиганты как IBM, Oracle и другие.
Эволюг\ионное моделирование. История эволюционных вычислений началась с разработки ряда различных кслс-. ШЬЫХ моделей. Основными из них были генетические алгоритмы и классификационные системы Холланда (Holland), опубликованные в началі 60-х годов и получившие всеобщее признание после выхода в свез сниги, ставшей классикой в этой области, - «Адаптация в естественных и искусственных системах» («Adaptation in Natural and Artifical Systems») [82]. В 60-70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идеи бионического поведения особей [51]. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию [6].
Большой вклад в развитие эволюционного программирования внесли Фогель (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих «школ» взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере. Таким образом, считается, что история эволюционного моделирования или эволюционных вычислений началась с работ Дж. Холланда, Л. Фогеля, М. Уолша, И. Букатовой, Л. Растригина и других ученых. «Все они взяли за основу ряд преобразований живого материала существующих в природе, упростили их, построив ряд принципов и моделей эволюционных процессов» [10].
Алгоритм решения многокритериальной задачи, учитывающий характер взаимодействия целевых функций
Чтобы привести задачу к виду обычной задачи линейного программирования, достаточно записать неравенства отдельно по левому и правому краям интервалов с учетом знаков неравенств. Полученная задача решается симплексным методом.
Таким образом, алгоритм решения задачи с нечеткими коэффициентами в форме трапециевидных (треугольных) нечетких чисел можно сформулировать в следующем виде: 1) Сформулировать модель задачи нечеткого математического программирования, определив подходящим образом параметры нечетких чисел. 2) Ввести дискретные а -уровни и зафиксировать один из них. 3) При заданном значении уровня а перейти к интервальному представлению коэффициентов ограничений. 4) Записать неравенства отдельно по левому и правому краям с учетом знаков неравенств (при этом размерность задачи увеличилась), в результате чего получим обычную задачу линейного программирования. 5) Решить задачу симплексным методом. Недостатком данного подхода является увеличение размерности задачи, но эта проблема не так велика в силу разработанности классических методов. Многокритериальность является особенностью реальных систем, при этом, критерии, которые необходимо оптимизировать, зачастую противоречат друг другу. Например, оптимальный проект для атомной станции должен быть и максимально безопасен, и максимально дешев. Если просто сформулировать эти два максимизируемых критерия в четких терминах, они будут противоречивы, потому что проект, который является 100%-но безопасным, будет делать станцию в сотни раз более дорогой, а самый дешевый проект, очевидно, не безопасен.
Модель многокритериальной задачи математического программирования имеет вид хєС, где С - это множество допустимых решений, определяемое системой уравнений и/или неравенств. При решении многокритериальной задачи отыскивается решение, обеспечивающее максимум каждого из частных критериев. Но такой максимум достигается лишь в идеальном случае. В реальных задачах возможно определить лишь компромиссное решение. Классические методы оптимизации (принцип максимума Понтрягина, метод динамического программирования Беллмана) [57] позволяют решать задачи только со скалярным критерием. При наличии векторного критерия применение этих методов оптимизации возможно только путем агрегирования частных критериев оптимизации в один обобщенный (интегральный) критерий или с помощью выбора из частных критериев одного - наиболее важного, в то время как остальные переводятся в ограничения. Необходимость перевода векторного критерия в скалярный критерий оптимизации привела к введению специальных функций предпочтения решений, т.е. акцент все больше переносится на определение преимущества того или иного решения. Наиболее часто при решении многокритериальных задач применяются аддитивные, мультипликативные и минимаксные критерии. Аддитивный обобщенный критерий определяется формулой где ос,- - весовой коэффициент целевой функции fi (х), V/ = 1,N (at є [0,l]\ и С учетом тех же обозначений мультипликативный обобщенный критерий имеет вид і=1 но существуют и другие определения. Например, в [1] мультипликативный критерий вводится формулой Минимаксный критерий имеет вид Основным недостатком аддитивного критерия является возможность компенсации одного критерия за счет других. Наоборот, мультипликативный критерий не обладает компенсационными свойствами, и если один из частных критериев принимает значение 0, то и обобщенный мультипликативный критерий также равен 0. К достоинствам минимаксного критерия можно отнести тот факт, что для него не происходит смещения оптимума при добавлении новых несущественных критериев, но в то же время он ухудшает чувствительность обобщенного критерия. Общим недостатком использования различных функций агрегирования, является то, что результат не всегда поддается интерпретации, поэтому возникает вопрос об адекватности полученного оптимального решения.
Для моделирования реальных ситуаций характерна зависимость выбора критерия (или группы критериев) оптимизации от состояния окружающей среды, т.е. в конкретной ситуации множество критериев должно выбираться оптимальным образом, а не вводиться волевым путем. Эту особенность легко учитывать с помощью введения на множестве возможных значений параметров, характеризующих состояние окружающей среды, нечеткого множества подходящих для оптимизации критериев [39]. Часто цели разрабатываемой системы, а значит и критерии трудно сформулировать в четких терминах, т.е. имеет место неопределенность. Ее природа может быть различной, поэтому при моделировании необходимо учитывать тип информации (вероятностная, интервальная, нечеткая информация), которая доступна при принятии решений. Этот факт оказывает существенное влияние на тип модели и способы обработки информации. В настоящее время нечеткая логика предлагает естественный подход к решению задачи многокритериальной оптимизации, когда мы не можем оптимизировать все противоречивые критерии на 100 %, а только каждый из них до некоторой степени. Для решения задач многокритериальной оптимизации на основе нечеткой логики был предложен ряд методов [76, 86], которые отражают особенности человеческих рассуждений.
Генетический алгоритм решения многокритериальной задачи о назначениях при нечетких коэффициентах целевой функции
Рассмотрим еще раз классическую многокритериальную задачу о назначениях. В ее формальной постановке ищется неизвестная матрица X размера NxN, состоящая из нулей и единиц. Если на месте [i,j] стоит единица, то /-й работник выполняет j -ю работу. Каждая работа выполняется одним работником, каждый работник назначается на одну работу. Матрицы С ,к = 1...К, задают требуемые критерии оптимизации. Например, коэффициенты Су могут означать затраты времени на выполнение / -м работником j -и работы, Су - оценку качества выполнения /-м работником, у-й работы и т.д. Направлением оптимизации критериев может являться как минимум, так и максимум. Для решения задач о назначениях, как правило, пользуются детерминированными методами, внося тем самым определенность в ситуации, где ее в действительности не существует. Поставленная выше задача является задачей чёткой, однако на практике скорее известно, что «исполнитель А выполнит работу В примерно за 3 часа», чем «А выполнит работу В за 3 часа». Более того, руководствуясь второй посылкой и назначив А на работу В, через 5 часов можно выяснить, что работа еще не сделана. Для учета такого рода неопределенностей воспользуемся аппаратом теории нечетких множеств. Зададим целевые коэффициенты критериев в виде гауссовых нечетких чисел. Выбор именно такой формы представления объясняется тем, что нечеткие множества, которые возникают в задаче о назначениях, являются по смыслу нормальными (максимальное значение функции принадлежности равно 1) и унимодальными (1 достигается в единственной точке), а также простотой определения арифметических операций. Напомним, что нечеткое число А называется гауссовым [98], если его функция принадлежности определяется как Операция сложения для гауссовых нечетких чисел вводится следующим образом. Пусть число А задается параметрами (аА, тА), а В — параметрами (ав,ов). Тогда их суммой будет нечеткое гауссово число с параметрами (аА + ав, тА+ов). Расстояние между данными гауссовыми нечеткими числами А и В определяется по формуле: На практике степень нечеткости может зависеть и от типа работы, и от назначаемого исполнителя. Например, если часть работ выполняются на открытом воздухе, а часть в помещении, то назначающий может учесть возможность непогоды, и увеличить значение ст. Для исполнителей увеличение а может объясняться неуверенностью в вновь нанятом рабочем.
Таким образом, окончательная постановка задачи имеет вид: N Здесь Сц - нечеткое гауссово число, заданное парой (а .а -), К — число критериев оптимизации, N — размерность задачи. При вычислении критериев подразумевается, что c xl = Cy, Ch-xO-O. Учитывая особенности поставленной задачи (отсутствие стандартных эффективных методов решения, желательность иметь сразу несколько результатов с целью сравнения и выбора компромиссного), для ее решения целесообразно использовать генетический алгоритм (ГА). Рассмотрим подробно основные этапы ГА, разработанные применительно к многокритериальной задаче о назначениях с нечеткими коэффициентами целевой функции. 1-й этап. Представление данных. Хромосома, представляющая неизвестную матрицу X, задается с помощью перестановочного кодирования. Суть кодирования заключается в следующем: особь — это вектор длиною N (N — размерность задачи), в которой на / -м месте стоит j Е [1..N], если Ху = 1. Таким образом решение будет записано как вектор-перестановка: х=( 1,2,4,3). Первая популяция создаётся случайным образом из различных перестановок длиной N. Дополнительно (с целью улучшения генетического материала) в первую популяцию вводятся особи, представляющие собой решения четких задач о назначениях по некоторым критериям в отдельности (вместо нечетких коэффициентов целевой функции Си в этих задачах используются значения соответствующих параметров щ;) 3-й этап.
Оценка особей популяции по критерию приспособленности. Так как рассматриваемая задача является нечеткой и многокритериальной, значение целевой функции не может служить для нее величиной критерия приспособленности. Для вычисления значений этого критерия предлагается следующий способ. 1) С помощью описанной ранее операцией сложения гауссовых чисел, для каждой особи популяции в соответствующей ей точке X рассчитывается значение целевой функции отдельно по каждому из критериев, образуя для нее набор из К гауссовых нечетких значений.
