Многохромосомная оптимизация оценки качества программных средств

В настоящее время сложилась такая ситуация, что из общей стоимости программно-аппаратного комплекса (ПАК) на долю программного обеспечения (ПО) приходится до 95%. Отсюда следует, что конкурентоспособность ПО основывается на снижении его стоимости и повышении качества.

Методика получения оценки качества ПО и структура этой оценки описаны в соответствующих нормативных документах [1, 2]. Стоимость получения некоторой оценки качества определяется исходя из конкретных условий. Для создания конкурентоспособного ПО на этапе проектирования требуется определить оптимальную для заданных условий структуру оценки качества ПО.

Постановка задачи

Предлагаются два основных варианта формулировки задачи оптимизации качества ПО:

1. Разработать ПО с максимальным значением оценки качества Q при ограниченных затратах C:

где C_lim - максимально допустимое значение затрат.

2. Имеется готовое ПО со значением оценки качества Q ниже требуемого. Минимизировать затраты C, необходимые для получения оценки качества Q не ниже требуемого значения:
где Q_lim - минимально допустимое значение качества.

Выбор метода решения задачи

Согласно норматива [1] оценка качества ПО имеет сложную многоуровневую структуру. На элементарном уровне оценка качества ПО состоит из 245 оценочных элементов, а интегральное значение вычисляется по формуле :

где q_i e [0,1] - значение i-го оценочного элемента; l_i- весовой коэффициент i-го оценочного элемента; n - количество оценочных элементов.

Таким образом, решаемая задача обладает следующими особенностями.

Количество параметров достаточно велико (до 245).
Экспертный характер определения оценок обуславливает нечеткость значений параметров. Кроме того возможна неоднородность оценок, т.е. разные группы параметров могут оцениваться разными экспертами и отличаться шкалой значений.
Задачу можно охарактеризовать как многокритериальную, поскольку оптимальность решения определяется двумя критериями - качеством и стоимостью.
Оптимизируемая функция дискретна, недифференцируема, имеет сложный характер изменений и т.д.

Таблица 1
Методы оптимизации	Nпар=245	Нечеткость	Многокрите- риальность	Сложная функция
Градиентные	Удовл.	Неуд.	Неуд.	Неуд.
Квазиньютоновские	Удовл.	Удовл.	Неуд.	Неуд.
Прямого поиска	Неуд.	Неуд.	Удовл.	Удовл.
Многоэкстремальные	Неуд.	Неуд.	Удовл.	Неуд.
Нелинейное программирование	Неуд.	Неуд.	Удовл.	Неуд.
Безусловная оптимизация	Неуд.	Неуд.	Удовл.	Удовл.

Возникает вопрос, какой метод необходимо использовать, чтобы решить задачу оптимизации качества ПО. В работах [3,4] описаны результаты исследований различных методов численной оптимизации и приведены основные свойства рассмотренных методов. На основании этого был проведен анализ указанных методов. Результаты приведены в табл. 1.

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

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

Характерные особенности генетических алгоритмов [5,6]:

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

Генетический алгоритм решения задачи оптимизации

Решение задачи оптимизации с помощью генетических алгоритмов состоит из следующих этапов [7].

1. Формирование оценочной функции:

где x_i - i-ый управляемый параметр; l_i - весовой коэффициент i-го параметра; n - количество параметров.

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

Наиболее распространенным, классическим способом является бинарное кодирование. Оно бывает нескольких видов. Простейший случай, когда информация, хранящаяся в каждом гене, может быть представлена как логическая переменная, т.е. хромосома имеет вид вектора A = (a₁,...,a_n), a_i = {0,1}, i = 1,n-, n - количество генов в хромосоме. Такой способ кодирования удобен в тех случаях, когда значение параметра определяет наличие или отсутствие некоторого факта, принадлежность или непринадлежность к какому-либо множеству и т.д. Он применяется при решении различных задач размещения, разбиения, определения принадлежности и т.п.

Более сложным является случай, когда кодируется вектор B=(b₁, ...,b_i, ...,b_n) с целочисленными неотрицательными компонентами [7]. Для такого кодирования необходимо определить максимальное число двоичных символов u, которое достаточно для представления в двоичном коде любого значения b_i из области его допустимых значений [0,K_i]. Параметр символьной модели u должен удовлетворять неравенству K<2u , где

. Запись произвольного целого неотрицательного числа с помощью b_i = (0 # b_i < 2u) двоичных символов определяется соотношением:

где a₁={0,1}; u - длина двоичного слова, кодирующего целое число bi.

Тогда символьная запись целочисленного кода bi для фиксированного значения управляемой переменной х_i в обычном двоичном коде запишется в виде следующей бинарной комбинации:

А хромосома представляет собой набор таких бинарных комбинаций:

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

Применяются также явные способы кодирования.

Целочисленное кодирование - это явный способ представления информации, т.е. значения параметров никаким трансформациям не подвергаются [5,6]. Такой способ кодирования удобно использовать при решении задач с целочисленными параметрами, в особенности если значения параметров изменяются в относительно больших пределах и двоичное кодирование применять неудобно, поскольку оно создает слишком большие области поиска и очень громоздкое представление значений параметров.

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

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

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

Особым случаем являются задачи размещения, составления расписаний и т.п., т.е. такие, для которых верно следующее: хромосома имеет вид вектора A={a_i}, a_i e D, i = 1,n-, причем A e R v"i,j: a_i є a_j, где D - множество возможных значений генов, R - множество жизнеспособных решений. В качестве примера можно привести задачу коммивояжера (явное представление), где каждый путь в решении должен встречаться только единожды. В принципе для таких задач могут применяться все вышеописанные способы кодирования решений.

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

3. Выбор подходящих генетических операторов: кроссинговера, мутации, селекции.

Кроссинговер - это процесс взаимного обмена участками хромосом, в результате которого "родительские" гены передаются "потомству" не по одиночке, а в сочетаниях, отличных от тех, в которых они имели место в "родительских" хромосомах. При этом сочетания генов и направление их изменений носят случайный характер [5-7].

Мутация - процесс изменения качественных признаков особей в результате появления новых значений в отдельных генах или целиком во всей хромосоме. Тем самым в каждом поколении мутации поставляют в хромосомный набор популяции множество различных генетических вариаций, присущих особям, которые называются мутантами mkt, k > 1 [5-7].

Подходящие генетические операторы выбираются исходя из особенностей решаемой задачи.

4. Выполнение генетического алгоритма [6]:

procedure GA;
	begin
		t=0; /* номер популяции */
		инициализировать популяцию P(t);
		оценить хромосомы в P(t);
	while условие завершения не удовлетворено do
		begin
		t=t+1; P(t)=выбрать из P(t-1);
		изменить хромосомы в P(t);
		оценить хромосомы в P(t);
		end;
	end;

Оптимизация качества ПО с помощью генетического алгоритма

На первом этапе формируется генетическая модель и устанавливаются следующие соответствия для задачи оптимизации качества ПО. Роль генов играют оценочные элементы. Локусы - номера оценочных элементов. Аллели - возможные значения оценочных элементов, удовлетворяют условию:

 eu(q_i)e[0,1], i = 1,n-..

Хромосома - возможное решение задачи, набор оценочных элементов. Длина хромосомы n=245 - общее число оценочных элементов в оценке качества ПО.

Популяция - набор возможных решений, т.е. набор оценок качества ПО, различающихся в общем случае как по интегральному значению, так и по значениям отдельных оценочных элементов. Размер популяции определяется исходя из специфики конкретной задачи и применяемого алгоритма поиска решения. Часто размер популяции находится экспериментальным путем. Размер популяции должен быть достаточным, чтобы она была репрезентативной, т.е. - обеспечивалась необходимая вероятность возникновения любого возможного решения и необходимого разнообразия решений, но не слишком большим, чтобы можно было осуществить поиск решения, т.е. найти требуемое решение или убедиться в невозможности его получения при заданных условиях за приемлемое время и при использовании приемлемых вычислительных ресурсов. В задачах, подобных исследуемой, размер популяции обычно колеблется в пределах 50 - 200 особей. Значение жизненного цикла популяции T также определяется условиями конкретной задачи оптимизации и особенностями метода решения.

Поскольку значения параметров системы - вещественные числа, причем шаг изменения не оговорен, применяется явное кодирование - вещественными числами.

Кроссинговер - классический оператор, поскольку он не меняет порядок генов в хромосоме, что обусловлено спецификой задачи [5,6].

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

Точка разрыва родительских хромосом, которая может находится в любом месте хромосомы между какой-либо парой ее генов, называется точкой кроссинговера a. Она делит "материнскую" и "отцовскую" хромосомы случайным образом на два участка:L1m,L1oт, содержащие гены от 1 до a , и L2m,L2oт, содержащие гены от (a+1) до n.

Мутация - случайная точечная ("uniform-random"), поскольку в условиях отсутствия приоритетов обеспечивает наиболее ровное распределение мутаций по всей длине хромосомы [6].

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

Система, подлежащая оптимизации, описывается некоторым набором параметров - множеством P={p₁, . . . , p_n}, называемым в формулировке задачи оптимизации множеством управляемых переменных [7].

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

Однако в данном случае предлагается представить множество P оптимизируемых параметров системы посредством не одной, а нескольких хромосом, предварительно разбив множество P на подмножества P₁. . . P_k, такие что ;i, j e [1,k], i є j, P_i " P_j = \,

и поставив в соответствие каждому подмножеству P_i отдельную хромосому.

Согласно нормативу [1], оценка качества ПО на макроуровне состоит из шести групп показателей качества: надежность, сопровождаемость, удобство применения, эффективность, универсальность и корректность. Поэтому очевидным является разбиение множества показателей качества на шесть подмножеств, соответствующих шести вышеперечисленным группам показателей качества. Таким образом формируется шесть хромосом различной длины: L₁=23, L₂=20, L₃=62, L₄=19, L₅=51, L₆=70 (длина хромосом определяется количеством оценочных элементов в каждой группе показателей качества согласно нормативу [1]).

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

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

Рис.1. Маскировка участков хромосомы:участки I, III и VI "маскируются", т.е. не подвергаются изменениям в процессе оптимизации и не учитываются при формировании оценки.

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

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

Это существенно облегчает процесс проектирования - его можно осуществлять несколькими группами разработчиков, причем четкая временная и этапная синхронизация не требуется. Например, оценочные элементы, составляющие группу показателей качества "корректность", в большинстве определяют качество сопроводительной документации, что при современном уровне сложности и многофункциональности ПО весьма актуально. И фактически сразу после формирования ТЗ можно провести оптимизацию фактора "корректность" и определить оптимальную структуру оценки качества ПО по этому фактору. В результате группа разработчиков сопроводительной документации может выполнять большую часть работы независимо от других групп проектировки ПО.

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

Кроме того, оценки качества по каждой группе могут иметь неоднородный характер, т.е. каждой группе показателей качества в этом случае соответствует своя, отличная от других, шкала значений (несмотря на то, что для всех оценочных элементов диапазон значений в данном случае одинаков - [0,1], количество возможных значений в этом диапазоне не обязательно одинаково для каждой группы оценок, в частности, когда каждую группу оценок формирует отдельная группа экспертов) или способ кодирования информации.

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

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

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

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

Применяемый алгоритм может быть описан следующим образом:

procedure EVANS;
begin
	выбрать количество хромосом;
repeat
   procedure GA;
   begin
	. . . . . . . . . . 
   end;
until оптимизированы все хромосомы;
end.

Экспериментальные исследования

Были проведены исследования по оптимизации программного комплекса "Эволюция". Этот программный комплекс был оценен по 4 группам показателей и для всех оценок Q_i0 были определены значения стоимостей C_i0 согласно коэффициентам, заданным ранее. Каждая группа показателей качества программного комплекса была представлена отдельной хромосомой.

Значения всех генов - действительные числа в диапазоне [0,1]. Значение качества каждой хромосомы вычислялось по формуле:

где Q - качество полученного решения; C - стоимость полученного решения; q_i - значение i-го гена; l_i - значение весового коэффициента i-го гена; C_i - значение стоимостного коэффициента i-го гена.

Таблицы весовых и стоимостных коэффициентов были заданы заранее.

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

где C_lim - максимально допустимое значение стоимости.

В качестве программы оптимизации был использован программный пакет EVANS.

Проведение эксперимента осуществлялось в несколько этапов. На первом этапе была произведена оптимизация качества по каждой группе показателей с учетом того, что начальное значение стоимости принималось как предельное, т.е. C_lim = C_i0. Уже при этом предельном значении стоимости были получены более высокие значения оценок качества, чем стартовые - Q_i > Q_i0.

Затем предельное значение стоимости Сlim изменялось с шагом 0,1 от максимальной стоимости, т.е. 0,4, 0,5, 0,6 и т.д. (отсчет проводился с 0,4*C_max, поскольку для всех групп показателей качества выполнялось неравенство C_i0 > 0). Максимальная стоимость - это стоимость получения оценки качества при максимальных (равных 1) значениях всех показателей. Максимальная стоимость определяется по формуле:

где С_i - стоимостной коэффициент i-го оценочного элемента.

В результате проведенных исследований была выявлена следующая закономерность. Когда предельное значение стоимости попадало в диапазон [0,4 - 0,5] от максимальной, значение оценки качества, получаемое в результате оптимизации, стабилизировалось и при дальнейшем увеличении предельного значения стоимости не изменялось. Существенное увеличение значения оценки качества, получаемого в результате оптимизации, опять наблюдалось только с момента, когда значение предельной стоимости приближалось к 0,9 от максимальной, т.е. фактически стремилось к максимуму.

Таким образом для задач такого класса с аналогичной системой коэффициентов можно дать следующие рекомендации: если предельно допустимая стоимость проекта не может достигать величины 0,9 от максимальной, она может быть ограничена диапазоном 0,4 - 0,5 от максимальной без существенного ухудшения получаемого значения оценки качества проекта.

Таблица 2
Хромосома № 1		Длина 23 гена		*C0=0,311Cmax**		Q=0,308696
Clim	0,311	0,4	0,5	0,6	0,7	0,8	0,9
Qср	0,6373912	0,6452173	0,6452174	0,6456522	0,6456522	0,6456523	0,6517393
Хромосома № 2		Длина 20 генов		*C0=0,368(3)Cmax**		Q=0,34
Clim	0,3684	0,4	0,5	0,6	0,7	0,8	0,9
Qср	0,352	0,365	0,365	0,365	0,365	0,365	0,381
Хромосома № 4		Длина 19 генов		*C0=0,381875Cma**x		Q=0,5578945
Clim	0,381875	0,4	0,5	0,6	0,7	0,8	0,9
Qср	0,6289473	0,6463159	0,6463157	0,6463159	0,6463157	0,6463157	0,6689474
Хромосома № 6		Длина 70 генов		*C0=0,381(6)Cmax**		Q=0,38
Clim	0,3817	0,4	0,5	0,6	0,7	0,8	0,9
Qср	0,611143	0,6135713	0,6137144	0,6134285	0,6135715	0,6131430	0,6234287

В табл. 2 и на диаграммах 1 - 4 (рис.2) отражены данные по испытаниям соответствующих хромосом, описывающих факторы качества: 1 - "надежность", 2 - "сопровождаемость", 4 - "эффективность", 6 - "корректность".

Литература

Оценка качества программных средств. Общие положения. ГОСТ 28195-89. М.: Издательство стандартов, 1989.
РЕКОМЕНДАЦИИ. Система автоматизированного проектирования. Показатели оценки качества программно-методических комплексов. Р 50-12-87. М.: Издательство стандартов, 1988.
Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985
Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. MA: Addison-Wesley, 1989.
Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975
Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Воронеж, 1995.