Содержание к диссертации
Введение
ГЛАВА 1. Обзор современного состояния моделей и методов управления проектами в условиях нечеткой неопределенности 10
1.1. Характеристика объекта исследования 10
1.2. История развития управления проектами в России 16
1.3. Теоретические основы моделей и методов управления проектами 19
1.4. Известные подходы к учету неопределенности в управлении проектами 35
1.5. Выводы и постановка цели и задач исследования 50
ГЛАВА 2. Нечеткие модели и численные алгоритмы сетевого анализа 53
2.1. Модификация метода альфа-уровневого принципа обобщения для
нахождения критического пути на основе нечетких чисел (L - R) -типа 53
2.1.1. Линейное отображение модифицированного метода а -уровневого принципа обобщения 53
2.1.2. Описание модификации метода альфа-уровневого принципа обобщения 58
2.1.3. Сравнение результатов предлагаемого подхода и известных методов.64
2.2. Нахождение критического пути с использованием предложенного подхода 90
2.2.1. Случай «устойчивого» критического пути 90
2.2.2. Случай «неустойчивого» критического пути 92
ГЛАВА 3. Решение задачи оптимального распределения ресурсов в условиях нечеткой неопределенности 98
3.1. Формулировка задачи оптимизации ресурсов проекта в условиях нечеткости 98
3.2. Решение задачи оптимизации ресурсов проекта с использованием генетического алгоритма 103
3.3. Тестовый пример. Вычислительный эксперимент по оптимизации на тестовом примере 111
3.4. Программная реализация 124
3.4.1. Функциональные блоки программного комплекса 126
3.4.2. Интерфейсная часть программного комплекса 129
3.5. Выводы 133
Заключение 135
Литература 136
- Теоретические основы моделей и методов управления проектами
- Выводы и постановка цели и задач исследования
- Описание модификации метода альфа-уровневого принципа обобщения
- Тестовый пример. Вычислительный эксперимент по оптимизации на тестовом примере
Введение к работе
Актуальность темы. От строительства дома до организации спортивных соревнований применяются модели и методы теории управления проектами. Управление проектами неразрывно связано с распределением ограниченных ресурсов по его операциям. При этом результатом подобного распределения является экономия или прибыль. Важной проблемой управления проектами является учет неопределенности при задании временных ресурсов.
Долгое время инструментальным способом учета неопределенности выступала теория вероятностей и математическая статистика. Продолжительность выполнения операций проекта рассматривали как случайную величину. Существенный недостаток подхода заключался в невозможности получения аналитических выражений для распределений вероятностей и других характеристик событий проекта. Кроме того, статистических данных для оценки вероятностных характеристик событий проекта на практике оказывалось недостаточно.
Другим известным способом учета неопределенности выступает теория нечетких множеств. Нечеткая информация о продолжительности выполнения операции может быть получена от эксперта в ситуации, когда отсутствуют нормативные и статистические данные. Главным отличием данного подхода от вероятностного является возможность построения аналитических зависимостей характеристик проекта, что важно для принятия управленческих решений.
Другой важной проблемой управления проектами является полный учет издержек при оптимизации ресурсов проекта. Данная задача относится к многоцелевым задачам оптимизации, т.к. совокупные издержки при выполнение проекта могут быть представимы в виде суммы внутренних и внешних издержек, зависящих от времени выполнения проекта и конфликтующих между собой по ограниченным ресурсам (чаще всего стоимостным). До настоящего времени все известные подходы к решению задачи оптимального распределения ограниченных ресурсов учитывали, как правило, лишь один из видов издержек.
Проблемами управления проектами занимались такие зарубежные ученые, как: Czamecki М.Т., Dinsmore Р.С., Fleming Q.W., Pennypacker J.S., Lientz B.P., Kerzner H. и другие. В России данными проблемами занимается институт проблем управления им. В.А.Трапезникова Российской Академии Наук. К наиболее известным ученым в данной области можно отнести: Новикова Д.А., Буркова В.Н., Баркалова С.А., Рыбальского В.И., Познякова В.В., Голуба Л.Г. и др.
Цели и задачи исследования. Целью работы является исследование и разработка моделей и методов учета нечеткой неопределенности в задачах управления проектами и оптимизации ресурсного обеспечения проекта.
Для достижения этой цели были поставлены следующие задачи.
-
Рассмотреть и проанализировать существующие подходы к решению задачи оптимального распределения ресурсов проекта в условиях неопределенности.
-
Разработать метод нахождения критического пути сетевого графа проекта в условиях нечеткой неопределенности.
-
Разработать модель и алгоритм решения задачи оптимального распределения ресурсов в условиях нечеткой неопределенности с критериями и ограничениями модели оптимизации.
-
Разработать программный комплекс для решения задачи управления проектами в условиях нечеткой неопределенности и провести вычислительный эксперимент.
Методы исследования. При выполнении работы использованы основные положения и методы теории нечетких множеств, теории графов, численных методов, вычислительных методов линейной алгебры, эволюционного моделирования, объектно-ориентированного программирования.
Тематика работы соответствует следующим пунктам паспорта специальности 05.13.18 "Математическое моделирование, численные методы и комплексы программ": п.2 "Развитие качественных и приближенных аналитических методов исследования математических моделей", п.З "Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий" и п.4 "Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента".
Научная новизна работы. В диссертации получены следующие результаты, характеризующиеся научной новизной.
-
Разработана модификация метода нахождения критического пути, отличающаяся применением модифицированного альфа-уровневого принципа обобщения.
-
Предложена модель оптимального распределения ресурсов проекта, отличающаяся многоцелевым характером задач оптимизации в условиях нечеткой неопределенности.
-
Разработан численный алгоритм оптимального распределения ресурсов, построенный на принципах эволюционных (генетических) алгоритмов, отличающийся новым подходом к реализации операторов селекции и кроссовера.
-
Разработан программный комплекс, включающий модуль для решения задачи оптимального распределения ресурсов в задаче управления проектами в условиях нечеткой неопределенности.
Практическая значимость работы заключается в разработке математических и программных инструментов решения задач управления проектами в условиях экспертного (нечеткого) оценивания параметров проекта, что позволяет использовать существующий аппарат теории нечетких множеств при решении широкого круга практических проектных задач.
Реализация и внедрение результатов работы. В результате выполнения данной диссертационной работы был разработан комплекс программ, включающий модуль для решения задачи оптимального распределения ресурсов проекта в условиях нечеткой неопределенности. Данный комплекс программ был успешно протестирован и внедрен на следующих предприятиях города Воронежа: ЗАО «Инлайн Груп Центр», «ВМЗ» - филиал ФГУП «ГКНПЦ им. М.В.
Хруничева», ОАО «Турбонасос». Программный комплекс отправлен в отдел регистрации программ для ЭВМ, баз данных и топологий ИМС Федерального бюджетного учреждения «Федеральный институт промышленной собственности», номер - 2012617754.
Апробация работы. Результаты диссертационной работы докладывались и обсуждались: на IX-XI Международных научно-методических конференциях «Информатика: проблемы, методология, технологии» (Воронеж, 2009-2011); на IV Международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования» (Воронеж, 2011); на Международной конференции «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2009); на Региональной научно-практической конференции студентов, аспирантов и молодых ученых «Инновационные технологии на базе фундаментальных научных разработок» (Воронеж, 2011); на ХП-ХШ Международной научно-технической конференции «Кибернетика и высокие технологии XXI века» (Воронеж, 2011-2012); на Воронежской зимней математической школе «Современные методы теории функций и смежные проблемы» (Воронеж, 2009).
Публикации. Основные результаты диссертации опубликованы в 16 научных работах, в том числе 2 в изданиях, рекомендованных ВАК РФ.
В работах, опубликованных в соавторстве и приведенных в автореферате, лично соискателю принадлежат: метод решения задачи линейного программирования с нечеткими параметрами целевой функции и ограничений [1, 8]; подход к нахождению общего времени выполнения проекта, минимизирующего его затраты, в условиях нечеткой неопределенности [6]; подходы к решению задачи функционально-стоимостного анализа проектов [9]; модель оптимизации распределения ресурсов проекта в условиях нечеткой неопределенности [11]; подход к разработке пользовательских интерфейсов [12,13].
Структура. Основная часть диссертационной работы, посвященной достижению поставленной цели, состоит из введения, трех глав, заключения, списка литературы, включающего 132 наименования, и приложения. Основная часть изложена на 148 страницах и содержит 58 рисунков и 41 таблицу.
Теоретические основы моделей и методов управления проектами
С повышением сложности современных проектов потребовалась разработка более четких и эффективных методов планирования, обеспечивающих оптимизацию всего процесса осуществления проекта. При этом оптимизация интерпретируется как минимизация продолжительности выполнения проекта с учетом экономических факторов использования имеющихся ресурсов [105]. По мере развития ЭВМ и информационных технологий, в 60-е гг. XX в. возникает новая область теоретических и прикладных исследований - организационное управление, в которую входят методы управления проектами, получившие в дальнейшем название методов сетевого анализа или сетевых методов (методы сетевого планирования) [6, 25, 67, 82, 115]: - метод критического пути с детерминированной технологией сетевого планирования, СРМ (Critical Path Method), 1957 год [40, 87]; - сетевая технология оценки и просмотра планов с учетом случайного характера времени выполнения операций проекта, PERT (Program Evaluation and Review Technique), 1958 год [40, 87]; - сетевая детерминированная технология МРМ (Metra Potential Method)," 1958 год; . - сетевые технологии с возможностью обратных связей GAN (Generalized Activity Networks), 1962 год; - стохастическая сетевая технология GERT (Graphical Evaluation and Review Technique), 1966 год [45, 111, 124]. Метод критического пути был разработан компанией Е. I. du Pont de Nemours & Company для управления проектами строительства, впоследствии был обобщен компанией Mauchly Associates. Метод PERT был предложен консалтинговой компанией по заказу военно-морского министерства США для календарного планирования научно-исследовательских и опытно-конструкторских работ программы создания ракет «Поларис».
В обоих методах временные аспекты планов занимают ключевое место в том смысле, что метод PERT и СРМ, в конечном счете, задают календарный план проекта. Несмотря на то, что оба метода возникли независимо друг от друга, их сходство просто поразительно. Сначала главным отличием одного метода от другого являлось то, что метод СРМ работал с детерминированными величинами оценок продолжительностей операции, а метод PERT со случайными. В настоящее время оба метода составляют единый метод сетевого планирования и управления (СПУ) проектами.
Суть разнообразных сетевых технологий определяется следующим образом. Операциям проекта ставятся в соответствие дуги (технология СРМ) или вершины (технология МРМ) графа. Соответственно отражаются события начала (окончания) операций: вершины графа в двухточечной модели СРМ или дуги в одноточечной модели МРМ. Граф будет отражать последовательность выполнения отдельных работ и наступление событий в. едином комплексе. Если проставить параметры графа: время, необходимое для завершения соответствующей операции, или размер ресурса то получится сеть. Изображение такой сети называют сетевым графиком (сетевой моделью), а ее исследование сетевым анализом.
Сетевой анализ — это метод планирования работ проектного характера, т.е. работ, операции в которых, как правило, не повторяются [115]. Анализ такой сети обеспечивается той или иной сетевой технологией, которая представлена соответствующим комплексом математических моделей и методов. Сетевое планирование и управление проектами состоит из трех основных этапов: структурное моделирование проекта, календарное (временное) планирование проекта, включающее его функционально-стоимостной анализ и оперативное управление проектом.
Первым делом на этапе структурного планирования происходит разбиение всего проекта на отдельные операции. Логическая последовательность выполнения операций может быть проиллюстрирована с помощью графа [115]. После чего определяются оценки длительности выполнения операции.
После того как операции определены и сделаны оценки времени их выполнения, на этапе структурного моделирования строится сетевая модель, отображающая взаимосвязи между операциями и порядок их выполнения.
Построение сетевой модели на этапе структурного планирования предоставляет возможность провести анализ операций проекта и внести корректировки (улучшения) в структуру проекта еще до момента его реализации. Более того, сетевая модель играет огромную роль при разработке календарного плана выполнения проекта и функционально-стоимостного анализа.
Важнейшей задачей этого этапа является определение критических опе раций, составляющих критический путь на сетевой модели. Критический путь определяет непрерывную последовательность критических операций, связывающих исходное и завершающееся события сети. Другими словами критический путь задает все критические операции проекта. Заключительным этапом календарного планирования проекта является построение календарного графика, который определяет моменты времени начала и окончания каждой операции, а также демонстрирует ее связь с другими операциями проекта. Более того, календарный график должен предоставлять возможность определять критические операции (с точки зрения времени), которые требуют к себе пристального внимания для успешного окончания проекта в директивный срок.
Выводы и постановка цели и задач исследования
Будем доказывать равенство (2.5) с левого слагаемого. По условию L(f(X",X")) = L(al X" +а2 X" +Ь). Операция умножения интервала на константу не определена, поэтому в представленном подходе предлагается вместо интервала брать точку, представимую как линейную комбинацию концов данного интервала. Так как отображение L линейное, то оно обладает свойством ассоциативности, поэтому справедливо:
Рассмотрим последнее слагаемое правой части выражения (2.7). Применение линейного отображения L по а-уровням к константе будет константой. Это объясняется тем, что отображение L на каждом а -уровне определено, как линейная комбинация левой xL (а) и правой xR(a) границы а-интервала Xа с некоторыми нормированными коэффициентами Д, Д2. В случае с константой, на всех от-уровнях левая и правая части числа будут совпадать и равны самому числу, а, из условия нормировки, сумма коэффициентов Д, Р2 даст 1, следовательно, применение отображениях даст само число, поэтому выражения Д6) перепишется в виде L(b) = b. На основе рассуждений, приведенных выше, равенство (2,7) можно переписать в следующем виде: Да, -Х"+а2 -Х2 +b) = at . L(X?) + a2 -L(X) + b. (2.10) А это есть правое слагаемое исходного равенства (2.5): f(L(X?, Ха2 )) = ar L{Xax ) + а2- L(Xa2 ) + b. (2.11) Таким образом, мы доказали на каждом а-уровне справедливость данного утверждения, значит равенство (2.5) выполняется. Следует отметить, строгое равенство справедливо только в линейном случае. Если решаемая задача нелинейная, то в этом случае ограничение (2.4) на применение предполагаемого линейного отображения модифицированного метода ог-уровневого принципа обобщения должно являться приблизительным равенством:
Описание модификации метода альфа-уровневого принципа обобщения Важнейшей задачей этапа календарного планирования и функционально-стоимостного анализа является определение критических операций, составляющих критический путь на сетевой модели. Как было сказано в главе 1 классические подходы к определению критического пути в.условиях нечеткой неопределенности не обеспечивают решение задачи оптимального распределения ресурсов. Существенным недостатком предложенных подходов является тот факт, что они все работают с широким носителем нечеткого числа. В этой связи предлагается модификация метода а -уровневого принципа обобщения [62]. Предлагаемая модификация, лишенная недостатков известных методов, представленных в обзоре главы 1, и позволяющая характеризовать решение произвольной исходной задачи управления, позволяет получать модифицированное решение и сводится к известному решению [67] детерминированных задач на выделенных а -уровнях.
Будем использовать понятие нечеткого треугольного числа, которое представляет собой частный случай нечеткого числа (L- R) -типа, описант ное в главе 1.
Пусть X - нечеткий числовой параметр с функцией принадлежности /л% (х) є [0; 1]. Для описания нечетких параметров будем использовать функции принадлежностей нечеткого числа (L -R)-типа, указанные в главе 1, а также их удобные частные случаи - треугольные числа. При решении задач с нечеткими параметрами известным приемом является переход к интервальной неопределенности [77], при котором нечеткому параметру X ставится в соответствие множество четких интервалов {Xа} (рис. 2.3). срезы треугольного числа Здесь число а задает or-уровень (ar-срез) нечеткого числа. Напомним его вид Xа s{x;fi% (х) а}. ОМ- мода нечеткого треугольного числа. В соответствии с теоремой о декомпозиции [83] любое выпуклое нечеткое число (Z-Я)-типа может быть разложено по п or-уровням. Были выбраны следующие дискретные а-уровни: 0; 0,2; 0,4; 0,6; 0,8; 1 (и = 6). Переход к полной определенности может быть осуществлен путем выбора, каким-либо образом, точки х(а)еХа. В этом случае на каждом а 60 уровне можно записать исходную задачу в четком виде, заменяя нечеткие параметры на соответствующие значения х(а). Для вычисления х(а) используем линейное отображение L, введенное ранее. Напомним его вид: ДХ) = Д -xL(a) + j32 xR(a) = x(a), (2.14) где Д,/?2 - нормированные коэффициенты, xL{a), xR(a) - соответственно левый и правый концы четкого а-интервала Xа, которые определяются как функции обратные к функции принадлежности /л% (х).
Распишем общий вид функции принадлежности ц% (х). Пусть х представляет собой нечеткое треугольное число с модой в точке М (например, рис. 2.3). Тогда значение функции принадлежности /л% (х) будет определяться соответствующим значением левой и правой частей треугольного числа, которые можно записать с помощью уравнения прямой. В общем виде функция принадлежности будем иметь вид (рис. 2.3): где М - мода треугольного числа. До настоящего момента мы не рассматривали возможные варианты определения нормированных коэффициентов /?,, /?2, а только упомянули, что от их выбора зависит, насколько точно сохранится исходная экспертная оценка после применения линейного отображения L. Рассмотрим несколько подходов к вычислению нормированных коэффициентов /?,, /?2 и оценим их влияние на точность полученных результатов. 1. Один из возможных способов выбора данных коэффициентов основан на отношение «пропорции» (рис. 2.4).
Описание модификации метода альфа-уровневого принципа обобщения
В общем случае, при принятии решения важно обращать внимание на центр тяжести. Небольшое смещение вправо, например, может лишь означать, что есть шансы на то, что время увеличится, но в основном, большее смещение влево будет определять, что общее время проекта также будет со смещенным центром тяжести вправо. Так, если бы в нашем случае, tJ(1) было со смещенным центром тяжести вправо, то, наверняка, конечное значение общей длительности проекта, имело бы смещенный центр тяжести вправо. Аналогично рассмотрим t3(2). Значение данного события были симметричны, и, как результат, конечное значение, полученное по данному пути, было симметричным. Сравним результат с предыдущим, полным решением, полученным по принципу обобщения: Линейное отображение L, введенное ранее, подтвердило предположение о том, что значение, полученное после применение его к исходным данным, равно значению, полученному после применения к результирующим данным, что означает, что данный линейный оператор не теряет исходную экспертную информацию.
Нечеткое число (L - К) -типа, задаваемое экспертом, целесообразно интерпретировать как меры возможного отклонения от моды влево и вправо. Эти отклонения можно рассматривать как риск или успех. Модифицированное решение показывает характеристику превышения одного отклонения над другим, степень асимметрии, т.е. превышение риска над успехом (или наоборот). Как правило, такой характеристики достаточно для принятия решений во многих задачах.
Если нечеткое число (L- R) -типа симметрично, то модифицированное решение просто показывает моду, что вполне логично. Именно это мы видим, сравнивая полное и модифицированное решения. Таким образом, модифицированное решение имеет право на использование в практических задачах и им можно заменить полное решение, если последнее трудно получить. В нашей задаче функционально-стоимостного анализа проекта, в частности на этапе нахождения критического пути на сетевом графе проекта, целесообразно использовать модифицированное решение по следующей причине.
С ростом размерности задачи, использование принципа обобщения для ее решения (т.е. нахождения продолжительности проекта) вызывает серьезные вычислительные трудности, а использование а-уровневого принципа обобщения создает трудности при решении оптимизационных задач нахождения концов соответствующих а -интервалов.
Стоит отметить, что решение, полученное для средневзвешенного значения для а-уровневого принципа обобщения (рис. 2.19) и решение, полученное нашим методом (рис. 2.22) практически совпадают в смысле (2.4), а это означает, что, во-первых, дает основание.использовать введенное линейное отображение L при решении задач, так как он сохраняет исходную экспертную информацию, а, во-вторых, предложенный подход является альтернативным способом решения задачи с нечеткими числами. Отличие лишь в том, что в первом случае производится поиск общего решения, и на основе него мы можем найти модифицированное, а в нашем случае сразу происходит поиск модифицированного решения.
Полученное сравнение также показывает, что операции максимума и минимума не оказывают влияние на нечеткое число (L - R) -типа, т.к. после применение отображения L результаты не исказились.
Применение линейного отображения L для операции умножения Решение задачи в разделе 2.1.3 показало, что применение линейного отображения L к операции сложения позволили сохранить исходную экспертную оценку и не исказить результаты. Так как основными операциями при решение задачи оптимального распределения ресурсов являются сложе 84 ние и умножение, то проверим применение линейного отображения L к операции умножения. Если рассматривать частный случай, когда заданы два четких числа, то будет выполняться выражение (2.1), то есть строгое равенство. Рассмотрим теперь ситуацию, когда заданы два нечетких треугольных числа. Пусть заданы два нечетких треугольных числа:
Как было отмечено выше, применение линейного отображения к нелинейным операциям, а в данном случае использовалась операция умножения, которая является нелинейной, мы получаем неравенство (2.12), то есть обеспечивается лишь приблизительное равенство. При этом важно отметить, что с увеличением носителя нечеткого числа, увеличивается разрыв носителя результата, которое также представлено нечетким числом. В качестве подтверждения этого следуем обратиться к таблицам 2.13 и 2.16 соответственно. При этом стоит отметить, что относительная погрешность, меняется, не очень сильно, по сравнению с абсолютной погрешностью. Для уменьшения абсолютной погрешности, как раз, следует использовать отображение L, которое сужает носитель нечеткого числа.
Мы проверили основные операции, которые будем использовать в нашем алгоритме. Как оказалось, две операции: сложение и функция максимума/минимума, вообще не искажают исходную экспертную информацию, а третья операция умножение дает незначительные расхождения. Но эти расхождения можно уменьшить за счет использования /.-отображения, который после применения к исходным данным снижает носитель нечеткого числа и тем самым, потери, исходной экспертной информации не происходит. Поэтому можно использовать данный подход для нахождения критического пути.
Для оценки пригодности предложенного подхода на основе линейного оператора L модифицированного метода а -уровневого принципа обобщения предлагается решить задачу нахождения критического пути. .
Пусть задан некоторый проект, характеризуемый операциями, описанными в таблице 2.17. Продолжительность каждого этапа проекта была оценена экспертами в виде нечеткого треугольного числа.
Тестовый пример. Вычислительный эксперимент по оптимизации на тестовом примере
Четвертый этап работы алгоритма - кодирование фенотипов с помощью кодов Грея. Как было сказано ранее число двоичных разрядов для кода Грея будет определяться динамически исходя из размера пространства поиска. В нашем случае мы видим, что максимальное по количеству элементов (24 элемента) пространство поиска при а= 0.4. Тогда для кодирования 24 элементов нам будет необходимо 5 бит, т.к. 23 = 32 комбинации (4 бит будет недостаточно, т.к. 24 = 16). Далее выполняем кодирование пространств поиска, двигаясь от минимального значения к максимальному. Например, при а — 0 значению 4.5 будет соответствовать код Грея - 00000, а числу 5 - 00001. Напомним, что коды Грея, соответствующие двум соседним целым числам, отличаются только одним битом. В результате процесса кодирования получим данные, представленные в таблице 3.4 (для а = 0). Полная таблица кодов Грея и соответствующих значений пространства поиска представлена в приложение А.
Переходим к пятому этапу - генерации начальной выборочной популяции особей или генотипов. Как было сказано ранее в качестве размера популяции установим 50 хромосом. Для формирования значений генов будем последовательно случайным образом выбирать значение 0 или 1 на основе имеющихся кодов Грея. Этот процесс соответствует процессу подбрасывания монеты, и в случае выпадения «орла» выбираем 1, а в случае выпадения «решки» - нуль. В результате сгенерируем последовательности бит, например, где знаком «» показано разделение по числу разрядов кодов Грея исходя из того, что для каждого кода выделено только 5 бит.
Полный результат генерации начальной популяции представлен в приложение Б. Переходим к следующему этапу - декодированию генотипов по всей популяции, то есть для каждой хромосомы. Декодирование выполняется на основе таблицы кодов Грея (приложение А), используемой для кодирования. В результате этого шага мы получаем четкие значения длительностей выполнения операций проекта, которые будут использованы нами на следующем шаге - оценки функции приспособленности каждой хромосомы.
Напомним, что в нашем примере функция приспособленности имеет-вид (3.5), то есть представляет собой суммарные издержки по проекту. Для вычисления функции приспособленности каждой хромосомы необходимо выполнить следующие действия:
Выполним поиск критического пути классическим методом, исполь зуя значения длительностей выполнения операций, полученных при декодировании хромосом на предыдущем шаге. В результате полу чим критические пути, представленные в приложение В. В качестве примера приведем критический путь для хромосомы № 1 (таблица 3.5). Таблица 3.5. Критический путь для первой хромосомы а-уровень Критический путь Длина критического пути, ТКР
Вычислим внутренние издержки на выполнение операций, лежащих на критическом пути. Для этого сначала рассчитаем стоимость выполнения критических операций на основание их длительностей выполнения по формуле:
Далее вычислим внутренние издержки как сумму стоимостей на выполнение критических операций. Полученные значения представлены в приложение В в столбце «Внутренние издержки». Значение внутренних издержек для хромосомы № 1 приведем в таблице 3.6.
Полученные значения внешних издержек по популяции представлены в приложение В в столбце «Внешние издержки». Значение внешних издержек для хромосомы № 1 приведем в таблице 3.7.
Получим аддитивную свертку двух конфликтующих критериев (внутренние и внешние издержки). Полученные результаты представлены в приложение В в столбце «Суммарные издержки». Значение суммарных издержек для хромосомы № 1 приведем в таблице 3.8..
Далее вычисляем среднее значение функции приспособленности по популяции для оценки завершенности процесса поиска. Для этого воспользуемся формулой: N (3.27) где yt — значение функции приспособленности /-ой хромосомы, N = 50 — размер популяции. В результате получим значение - 8488. Для оценки завершенности процесса поиска будем использовать формулу: 117 1Д,-Лн.і (3-28) гДе Ут-\ Ут средние значения функций приспособленности по популяции на предыдущей и текущей итерации соответственно. Очевидно, что на первой итерации поиск не прекратился. Следующим шагом работы алгоритма является этап - селекция хромосом текущей популяции. В качестве оператора селекции использовался гено-типный аутбридинг, преимущества которого были представлены при описании алгоритма в разделе 3.2. В результате был сформирован родительский пул, представленный в таблице 3.9. Полная информация о парах родительских хромосом представлена в приложение Г.
На следующем шаге алгоритма выполняется процедура скрещивания выбранных родительских хромосом. Для скрещивания используется TV-точечный кроссовер. Точки деления для кроссовера определяются кратно длине кода Грея, то есть, кратно 5. В результате применения данного оператора к каждой паре родительских хромосом рождается новая хромосома, у которой часть аллелей заимствована у одной родительской особи, а другая -у второй. Результат скрещивания хромосом родительской пары (41, 22) представлены в таблице 3.10. Жирным цветом выделены заимствованные участки. Полная информация о скрещивание всех родительских пар представлена в приложение Д.
