Эволюционный подход к прогнозированию оценки стоимости ПО

Эволюционный подход к прогнозированию оценки стоимости ПО Итак, одной из самых популярных моделей, используемых для оценки сложности проектируемого ПО, является COnstructive COst Model (COCOMO), предложенная Boehm. Эта модель разработана на основе фактически регрессии 63 проектов ПО (НАСА) . Модель позволяет определить математическую зависимость между сложностью ПО, выраженную в килостроках кода, и затратами на его разработку, которые оцениваются в человеко-месяцах. Ядром модели является следующая формула Ef=aLb , где L - длина кода ПО в килостроках; Ef – оценка сложности проекта в человеко-месяцах; a и b - коэффициенты (параметры) модели, которые для различных типов ПО имеют различные значения. Например, эта формула для проектов НАСА различной сложности может иметь следующий вид Здесь KLOG представляет сложность ПО в килостроках – L. Для других проектов коэффициенты a и b могут иметь другие значения. Основная проблема модель COCOMO заключается в том, что она не обеспечивает реальных оценок на затраты при проектировании ПО в современных условиях. Т.е. оценка программного обеспечения на основе существующих параметров не всегда дает точный результат; из-за этого часто требуется настройка параметров для получения более точных результатов. Поэтому в настоящее время идет активный поиск новых моделей (или развития и модификаций существующих). Это ограничение модели COCOMO можно преодолеть путем применения методов искусственного интеллекта, таких как искусственные нейронные сети, генетические алгоритмы и другие метаэвристики. В данном разделе (лекции) для определения значений коэффициентов a и b используется генетический алгоритм. Фактически задача сводится к машинному обучению на заданной обучающей выборке. В данном случае обучающая выборка строится на основе следующей таблицы, которая дает реальные данные для 18 проектов НАСА, на основе которых мы ищем зависимость между L и Ef. Таблица экспериментальных данных проектов НАСА Номер проекта L Ef При этом данные по 13 проектам (из 18) можно использовать в качестве обучающего множества, а данные остальных 5 проектов – в качестве тестового множества (для проверки - тестирования) полученных значений коэффициентов a и b. Напомним, что для того, чтобы применить генетический алгоритм для решения некоторой проблемы необходимо, прежде всего, определить: 1. Кодирование (представление потенциального решения); 2. Для определенного кодирования выбрать или разработать генетические операторы кроссовера, мутации и репродукции. 3. Фитнесс-функцию из условия задачи. 4. Определить параметры ГА: число особей в популяции, значения вероятностей кроссовера Pc и Pm . 1. В данном случае потенциальное решение представляется вектором значений параметров (a,b). Значения каждого параметра лежат в некотором диапазоне: a  [ La , U b ] b  [ Lb , U b ] Для кодирования значений вектора (a,b) можно использовать как двоичное кодирование, так и непосредственное представление потенциального решения в виде вектора вещественных чисел (a,b). Вероятно, второй вариант предпочтительней. В случае двоичного кодирования можно использовать стандартный 1-точечный (или однородный) кроссовер и стандартный оператор мутации. В случае вещественного кодирования следует использовать какой-либо вещественный кроссовер (например, в виде линейной комбинации родительских векторов) и вещественную мутацию. Значения параметров ГА следует подобрать экспериментально в ходе эксперимента. В ГА использовались следующие параметры Фитлесс-функция В качестве фитнесс-функции в данном случае нужно взять различие между реальными значениями стоимостей проектов и модельными значениями (оценками) стоимостей этих же проектов, которые вычислены согласно приведенной формуле с найденными с помощью ГА коэффициентами a и b. Это различие (расстояние между оценками) можно оценить по-разному - в различной метрике. Можно взять, например, метрику абсолютных значений (Манхэттен – метрика городских кварталов), где это различие определяется с помощью следующей формулы , Здесь Efforti - реальная (измеренная) стоимость i-го проекта в человеко-месяцах и Estimated Efforti -модельная оценка того же проекта, вычисленная с помощью приведенной Формулы с найденными путем применения ГА коэффициентами a и Для оценки различия можно использовать и другие метрики, например: среднее значение относительной погрешности (MMRE) ; b. Корень квадратный среднеквадратичной ошибки (RMS) ; Отклонение (дисперсия) (VAF) ; Евклидово расстояние С помощью ГА найдены оптимальные значения коэффциентов a=2,022817 , b= 0,897183. Таким образом, для оценки затрат проекта можно использовать формулу Ef= 2,022817·L0,897183 . При этом имеет место следующие оценки стоимости проект ов Следующая таблица показывает полученные экспериментальные результаты Рисунок показывает различия оценок для проектов НАСА , которые выполнены с помощью ГА и методики СОСОМО. Здесь синим цветом показыны реальные стоимости (измеренные) проектов НАСА, красным стоимости, вычисленные по методике СОСОМО, и желтым –оценки, полученные с помощью ГА. Отметим, что оценки, полученные с помощью ГА, точнее, чем по стандартной методике СОСОМО. Особенно наглядно это видно из следующего графика для значений ошибок в метрике Манхэттена Результаты с использованием другой фитнесс-функции Следует отметить, что по данным разных авторов (из других литературных источников) полученные значения коэффициентов a и b могут существенно отличаться. Особенно это характерно, если используются в фитнесс-функции различные метрики для оценки расстояний между реальными и модельными значениями. Далее, для сравнения представлены аналогичные результы, полученные с использованием в фитнессфункции отклонения (дисперсии) В ГА использовались следующие параметры В этом случае с помощью ГА найдены оптимальные значения коэффциентов a=4,9067 , b= 0,7311. Таким образом, для оценки затрат проекта можно использовать формулу Ef=4,9067L0,7311 . При этом значение фитесс-функции получено VAF=96,3138. На следующем рисунке представлены реальные (измеренные) и модельные (вычисленные согласно полученной модели) значения затрат на проекты. На следующем рисунке представлено изменение фитнесс-функции. Далее, на рисунках показан процесс сходимости для искомых параметров a и b. Уточнение модели Далее рассмотрим развитие модели, которое позволяет учитывать кроме сложности (в килостроках кода ПО) и особенности используемой методики проектирования. Эти особенности добавим в виде дополнительного столбца Me в исходную базовую таблицу и получим расширенную таблицу. Данные получены из литературы. Как и сложность в кило-строках, эти данные определены (измерены) для каждого проекта и являются входными параметрами. Учет влияние методики проектирования Me можно попробовать внести путем дополнительных слагаемых в формулу методики СОСОМО. Тем самым мы делаем эту модель не только мультипликативной и степенной, а и аддитивной в надежде на повышение качества модели (точности прогноза). Итак, сначала рассмотрим модель в виде следующей формулы Ef=a·Lb +c·Me. Далее, как и ранее, с помощью ГА будем искать значения коэффициентов a, b, c. В данном случае, как и предыдущем, ГА работает в режиме регрессии. В качестве целевой функции также будем использовать вариацию VAF=[1 – var(Ef -Efm)/var(Ef)]×100% Как и ранее, в ГА можно использовать двоичное и вещественное кодирование и представленные прежде генетические операторы. В результате работы ГА найдены следующие значения коэффициентов a=3,1938 , b=0,8209 , c=-0,1918, что в результате дает формулу Ef=3,1938·L0,8209 -0,1918·Me. Согласно этой формуле(модели) выполнена оценка стоимости каждого проекта (в человеко-месяцах), которая приведена в следующей таблице наряду с реальной стоимостью. Здесь во втором столбце Ef приведены реальные (измеренные) затраты на проекты (в человекомесяцах), а в третьем столбце Efm представлены модельные затраты, вычисленные в соответствии с полученной формулой. Следует отметить, что по сравнению с предыдущей моделью качество (точность прогноза) немного улучшилось. Поэтому эксперименты были продолжены путем ввода в модель дополнительной константы d. Номер проекта Ef Efm То есть исследовалась модель Ef=a·Lb +c·Me+d. Далее, как и ранее, с помощью ГА будем искать значения коэффициентов a, b, c, d. Аналогично предыдущим моделям в ГА можно использовать двоичное и вещественное кодирование и представленные прежде генетические операторы. В результате работы ГА найдены следующие значения коэффициентов a=3,3602 , b=0,8116 , c=-0,4524, d=17, 8025, что в результате дает формулу Ef=3,3602·L0,8116 -0,4524·Me+17, 8025. На следующем рисунке показаны значения оценок стоимости проектов – реальные и модельные, полученные в соответствии с последней формулой. Синим показаны реальные значения, красным – модельные. Далее показан график изменения фитнесс-функции Var в зависимости от номера поколения (фактически определяет сходимость ГА) В следующих рисунках показаны графики сходимости искомых параметров a, b, c, d в процессе работы ГА. Согласно этой формуле(модели 2) выполнена оценка стоимости каждого проекта (в человеко-месяцах), которая приведена в следующей таблице наряду с реальной стоимостью. Номер проекта Ef Efm Ниже в таблице показаны параметры ГА, которые использовались в процессе поиска параметров модели. Различные фитнесс-функции Отметим, что в настоящее время при решении рассматриваемой задачи в качестве фитнесс-функции используется гораздо большее число метрик, которые представлены в следующей таблице. Заметим, что различные метрики, естесственно , дают различные различные значения для различия между реальными и модельными оценками значения стоимостей проектов, некоторые из которых представлены в следующей таблице. Обзор В следующей табл. представлены параметры ГА, которые использовались различными авторами, при решении этой задачи. Отметим, что в качестве фитнесс-функции чаще используется MSE или MRE. Генетические операторы кроссовера, мутации и отбора родителей, как правило, применяются стандартные. Более характерно большое число особей в популяции - обычно мощность популяции равна 1000. В следующей таблице также показаны основные аспекты применения различных методов вычислительного интеллекта, основанных на нейронных сетях и линейной регресси, для решения рассмтариваемой задачи Следует отметить, что часто для решения задачи оценки ПО часто используются гибридные ГА, где они применяются в сочетании с другими методами. Это показано вследующих 2 таблицах. Таким образом, генетические алгоритмы широко используются для построения моделей оценок стоимости проектов по разработке программного обеспечения и позволяют построить более адекватные модели т.е. повысить точность прогнозов.