ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В УПРАВЛЕНИИ ПРОГРАММНЫМИ ПРОЕКТАМИ

Аннотация

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

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

Ключевые слова: программное обеспечение, управление программными проектами, генетические алгоритмы.

Программный проект включает в себя как концепцию, так и процесс разработки и внедрения оригинального программного обеспечения. Выполнение программного проекта раскладывается на несколько фундаментальных этапов: анализ требований, проектирование и кодирование, тестирование и отладка, внедрение. Сейчас более 70% проектов не достигают изначально согласованных критериев качественного внедрения: сроки, стоимость, потенциал, а каждый восьмой аннулируется до окончательного внедрения. [5]

Центральной проблемой реализации программных проектов является трудность в корректном определении необходимых трудозатрат для реализации того или иного проекта.  Отставание от запланированного графика вызывается изменением технического задания, команды проекта, отсутствием правильной оценки трудоемкости проекта.

Необходимо отметить, что увеличение объемов работ в связи с изменением технического задания непосредственно во время реализации проекта нельзя нивелировать добавлением программистов в команду с тем, чтобы сохранить ранее согласованный срок выполнения программного проекта, так как увеличение команды может привести к уменьшению суммарной производительности коллектива. [1]

Изменение, как в большую сторону, так и в меньшую сторону ранее согласованного срока выполнения работ может повлечь следующие негативные последствия для реализации программного проекта:

• Возникновение необходимости тратить дополнительные финансовые средства, стресс, вызванный неисполнением обязательств в срок, ухудшение качества управления проектом (при недооценке);
• Бесполезный расход ресурсов (при переоценке). [3]

Самым популярным способом оценки трудозатрат является экспертная оценка, однако этот метод имеет множество проблем:

• Основания для получения оценки не являются явными;
• Сложность поиска экспертов для каждого отдельного проекта;
• Связь между размером системы и трудозатратами не линейна (будет получена корректная оценка только в том случае, если предыдущие проекты эксперта были схожи по масштабу). [3]

Кроме оценки времени и стоимости с помощью экспертов применение находят следующие способы: алгоритмическая модель COCOMO II, в рамках которой трудозатраты выражаются в человеко-месяцах и метод функциональных точек. [3]

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

В связи с перечисленными проблемами управления программными продуктами генетический подход к оценке трудовых затрат на производство программного обеспечения является наиболее приемлемым. Эксперты обозначают генетические алгоритмы также как «Метод оптимизации, основанный на концепциях естественного отбора и генетики». [2, с. 86]

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

Блок-схема генетического алгоритма [7] представлена на рисунке 1.

Рисунок 1. Блок-схема генетического алгоритма

Данный подход требует описание системы следующим способом:

1.Граф приоритета задач

2.База данных сотрудников

3.Целевая функция

Рассмотрим случай двух сотрудников и с одинаковыми навыками. Приоритет задач 1, 2, 3, 4 представлен на рисунке 2.

Рисунок 2. Пример графа приоритета задач

Пусть сотрудник A может выполнить первую задачу с вероятностью совершения 50%, а вторую задачу с вероятностью 25%. Сотрудник B может сделать задачу под номером два с вероятностью в 75%, задачу номер три с вероятностью 50%, а задачу под номером 4 – 25%.

Выше перечисленный пример можно представить с помощью двумерного массива (таблица 1).

Таблица 1.

Вероятность выполнения заданий сотрудниками

Для отличия одного генома от другого и оценки генома будем использовать функцию компаратор:

,

где a_ij – геном A в i строке и j столбце, b_ij – геном B в i строке и j столбце, m – номер задания, n – номер сотрудника.

Целевая функция должна оцениваться в два этапа. На первом оценивается полнота задачи и сопоставление навыков, на втором оцениваются стоимость и продолжительность.

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

.

Сопоставление навыков. Комбинированный набор навыков сотрудников должен включать все навыки, необходимые для выполнения этой задачи:

.

Стоимость вычисляется для каждой задачи путем суммирования затрат каждого сотрудника на выполнение задачи. Затем общая стоимость рассчитывается путем суммирования затрат по всем задачам.

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

Наконец, эти два компонента объединяются, используя выбранные пользователем веса (W_time и W_money), как показано в уравнении [7].

Каждому сотруднику можно отдельно назначить лимит на объем рабочей нагрузки. Общие усилия суммируются по всем задачам и всем сотрудникам.

Эффективность применения генетических алгоритмов подтверждается в работе исследователей М.Б. Родькиной и Т.М. Леденевой. В результате проведенного тестирования было обнаружено наибольшее влияние на результат числа итераций метода. При этом существует такой объем итераций, что последующее увеличение этой метрики становится бессмысленным. Помимо этого, исследователи говорят о том, что объем поставленной задачи практически не оказывает влияние на максимальное количество популяций. [4, c. 177]

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

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

Список литературы:

1. Клименко А.Б., Клименко В.В. Методика оптимизации процесса разработки программного обеспечения // Вестник Таганрогского института управления и экономики. 2009. - № 1/2009.
2. Ковшов Е.Е., Горяева О.В. Применение генетического алгоритма при оценке рисков инновационных проектов // Российское предпринимательство. 2010. - № 11(3).
3. Кульдин С.П. Генетический подход к проблеме оценки сроков и трудоемкости разработки программного обеспечения с заданными требованиями к качеству // Прикладная информатика. - 2010. - № 5(29).
4. Родькина М.Б. Леденева Т.М. Модель задачи нахождения оптимального плана работ и генетический алгоритм для ее решения // Вестник ВГУ, серия: Системный анализ и информационные технологии. 2011. - №1.
5. Черняховская Л.Р., Малахова А.И. Интеллектуальная поддержка принятия решений в организационном управлении разработкой программных проектов // Математическое и программное обеспечение. Уфа. 2013. - Т. 17, № 5 (58).
6. Chang Carl K., Christensen Mark J., Zhang Tao, Genetic Algorithms for Project Management // Annals of Software Engineering 11. – 2001.