Генетический алгоритм поиска оптимальной архитектуры программного обеспечения

Размещено на http://www.allbest.ru/

Генетический алгоритм поиска оптимальной архитектуры программного обеспечения

Д.А. Шеенок

Красноярский институт железнодорожного транспорта, Красноярск, Россия dmitryshkras@rambler.ru

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

Важным классом методов оптимизации, способных решать такие задачи оптимизации являются эволюционные алгоритмы и, в частности, генетические алгоритмы (ГА), основанные на имитации эволюционных процессов, происходящих в природе[1, с.32].

Основной задачей при проектировании, разработке или модернизации сложных программных систем, как и любых других сложных объектов, для разработки которых привлекаются ресурсы разного характера и объема, является создание соответствующего объекта с заданным уровнем качества в условиях ограниченности ресурсов[2, c.5].

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

Компоненты архитектуры программного обеспечения могут быть реализованы с использованием программной избыточности. Если вводится программная избыточность, то ее можно реализовать методом мультиверсионного программирования (NVP - N-version programming) или блока восстановления (RB - recovery block).

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

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

Smax, S S0,

Tsmin, TsTs0,

где S - критерий оценки коэффициента готовности системы, Ts - критерий оценки трудоемкости разработки системы, S0, Ts0 - предельные допустимые уровни критериев.

Критерии оптимизации заданы алгоритмически, согласно усовершенствованной модели надежности программного обеспечения алгоритмически. Основные обозначения модели надежности ПО следующие [3]:

1) М - число архитектурных уровней в архитектуре ПО;

2) Nj - число компонентов на уровне j, j{1,..,M};

3) Dij - множество индексов компонентов, зависящих от компонента i на уровне j, i{1,..,Nj}, j{1,..,M};

4) Fij - событие сбоя, произошедшего в компоненте i на уровне j, i{1,..,Nj}, j{1,..,M};

5) PUij - вероятность использования компонента i на уровне j, i{1,..,Nj}, j{1,..,M};

6) PFij - вероятность появления сбоя в компоненте i на уровне j, i{1,..,Nj}, j{1,..,M};

7) PLijnm - условная вероятность появления сбоя в компоненте m на уровне n при появлении сбоя в компоненте i на уровне j, i{1,..,Nj}, j{1,..,M}, n{1,..,Nm}, m{1,..,M};

8) TAij - относительное время доступа к компоненту i на уровне j, i{1,..,Nj}, j{1,..,M}, определяемое как отношение среднего времени доступа к компоненту i на уровне j к числу сбойных компонентов на малых уровнях архитектуры за одно и тоже время;

9) TCij - относительное время анализа сбоя в компоненте i на уровне j, i{1,..,Nj}, j{1,..,M}, определяемое как отношение среднего времени анализа сбоя в компоненте i на уровне j, i{1,..,Nj}, j{1,..,M}, к числу сбойных компонентов на всех уровнях архитектуры, анализируемых в одно и тоже время;

10) TEij - относительное время устранения сбоя в компоненте i на уровне j, i{1,..,Nj}, j{1,..,M}, определяемое как отношение среднего времени восстановления в компоненте i на уровне j, i{1,..,Nj}, j{1,..,M}, к числу сбойных компонентов на всех уровнях архитектуры, в которых происходит устранение сбоев в одно и тоже время;

11) TUij - относительное время использования компонента i на уровне j, i{1,..,Nj}, j{1,..,M}, определяемое как отношение среднего времени использования компонента i на уровне j, i{1,..,Nj}, j{1,..,M}, к числу компонентов на всех уровнях архитектуры, используемых в одно и тоже время;

12) Zij - множество версий компонента i, на уровне j, k=1,..,K;

13) Tij - трудоемкость разработки компонента i на уровне j;

14) Tkij - трудоемкость разработки версии k компонента i на уровне j, kZij в чел-часах;

15) NVXij - трудоемкость разработки среды исполнения версий (приемочного теста для RB или алгоритма голосования для NVP);

16) Bij - дихотомическая переменная, принимающая значение 1 (тогда NVPij=0, RBij=0), если в программном компоненте не используется программная избыточность, иначе равна 0.

17) NVPij - дихотомическая переменная, принимающая значение 1 (тогда Bij=0, RBij=0), если в программном компоненте используется программная избыточность по методу N-версионного программирования, иначе равна 0.

18) RBij - дихотомическая переменная, принимающая значение 1 (тогда Bij=0, NVPij=0), если в программном компоненте используется программная избыточность по методу блока восстановления, иначе равна 0.

19) TR - среднее время простоя системы в большой архитектуре телекоммуникационного ПО реального времени, определяемое как время, в течение которого система не может выполнять свои функции;

20) MTTF - среднее время появления сбоя в большой архитектуре телекоммуникационного ПО реального времени, определяемое как время, в течение которого сбоев в системе не происходит;

21) S - коэффициент готовности.

22) Ts - общая трудоемкость системы;

При построении мультиверсионного компонента из K версий методом N-версионного программирования (NVP, N-version programming) для любого K надежность равна[4]:

где pvij - вероятность безотказной работы алгоритма голосования, pkij - вероятность безотказной работы версии kZij.

При построении мультиверсионного компонента из K версий методом блока восстановления (RB, recovery block)[4]:

где pATij - вероятность безотказной работы приемочного теста для компонента i, i=1,..,N на уровне j, j=1,..,M; pkij - вероятность безотказной работы версии kZij.

Вероятность сбоя таких компонентов рассчитывается как PFij = 1 - Rij.

Трудоемкость разработки системы рассчитывается следующим образом:

Среднее время сбоя равно[3]:

Среднее время простоя системы равно[3]:

Коэффициент готовности равен:

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

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

Генетический алгоритм имеет следующий вид:

1. Инициализировать случайным образом популяцию решений и оценить их пригодность.

2. Выбрать часть популяции (родителей) для порождения потомков (применить оператор селекции).

3. Применить оператор скрещивания и породить новые решения.

4. Подвергнуть мутации новые решения (потомки).

5. Сформировать новую популяцию: выбрать решения из родителей и потомков.

6. Повторять пункты 2-5 пока не выполнится условие остановки.

Обычно применяют следующие критерии остановки:

1. Найдено решение с заданной точностью.

2. Закончился ресурс, отведенный на вычисления целевой функции.

3. Много поколений без улучшения (стагнация).

Для части компонентов архитектуры, участвующих в ГА и для которых возможно введение программной избыточности, могут быть изменены следующие характеристики:

1. Вариант Var вероятности сбоя компонента и соответствующей трудоемкости для достижения этой вероятности сбоя. Возможные варианты задаются аналитиком (Var>=0).

2. Метод реализации программной избыточности: мультиверсионное программирование (NVPij=1, RBij=0) или блок восстановления (NVPij=0, RBij=1). Если выбран метод NVP, то устанавливается значение 0, если RB, то 1.

3. Varv1..Varv10 - номер варианта вероятности сбоя для каждой версии компонента, аналогично пункту 2 (Var>=0, 0 - версии нет). Предельное количество версий программного компонента, если будет применена избыточность, задается аналитиком.

Также накладываются условия:

1. Количество версий должно быть больше либо равно 2.

2. Если все варианты равны 0, то считается, что программная избыточность не вводится (Bij=1).

Для другой части компонентов, участвующих в ГА, недопустимо введение программной избыточности. Поэтому для них изменяется только вариант Var вероятности сбоя компонента и соответствующей трудоемкости для достижения этой вероятности сбоя (Var>0).

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

Таблица 1

генетический алгоритм поиск программный

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

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

Разрыв происходит в случайно выбранных точках. Причем вероятность разрыва особи между генами одного программного компонента и вероятность разрыва между генами разных компонентов различны. Таким образом, реализуется скрещивание с использованием различной вероятности разрыва выраженных и невыраженных генов. Гены метода избыточности и вариантов вероятности сбоя версии компонента не проявляют себя в данной особи, если значение гена введения избыточности B=0. И, наоборот, при B=1, не проявляется ген варианта вероятности сбоя компонента. Количество точек разрыва задается исходя из длины хромосомы.

Мутация особей популяции происходит с заданной вероятностью. Кроме вероятности применения мутации к каждой особи, используется вероятность применения мутации к каждому ее гену, величину которой задают от 1 до 10% [5]. При мутации генов вариантов надежности, вероятность выбора ближнего по номеру варианта задается более высокой, чем более дальнего варианта. Так как варианты, заданные аналитиком, упорядочиваются по уровню надежности, особь представляет собой аллели в шкале порядка.

Для каждого полученного потомка рассчитываются значения S и T. Алгоритм расчета критериев оптимальности по полученной в ГА особи для последующего использования в определении пригодности особи, изображен на рисунке 1.

Задача многокритериальной (векторной) оптимизации заключается в поиске множества Парето. С точки зрения математики решения множества Парето не могут быть предпочтены друг другу, поэтому после формирования множества Парето задача может считаться математически решенной[6, с.58].

Полученные значения записываются в множество Парето-оптимальных решений. ГА заканчивает работу при соблюдении одного из заданных критериев останова.

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

Рисунок 1 - Алгоритм расчета критериев оптимальности

Литература

1. Галушин П.В. Асимптотический вероятностный генетический алгоритм решения сложных задач глобальной оптимизации: Автореф. диссертации на соискание ученой степени кандидата технических наук / Красноярск: СибГАУ, 2012. - 20 с.

2. Борисенко, М.Л., Использование нечеткой модели при оптимизации характеристик программных средств с помощью многокритериального генетического алгоритма: Дис. канд. техн. наук: Москва, 2002 - 153 с.

3. Русаков, М.А., Многоэтапный анализ архитектурной надежности в сложных информационно-управляющих системах: Дис. канд. техн. наук: Красноярск, 2005 - 168 с.

4. Новой, А.В., Система анализа архитектурной надежности программного обеспечения.: Дис. канд. техн. наук: Красноярск, 2011 - 131 с.

5. Панченко, Т.В. генетические алгоритмы [Текст]: учебно-методическое пособие / под ред. Ю.Ю. Тарасевича. - Астрахань: Издательский дом «Астраханский университет», 2007. - 83 c.

6. Сергиенко, Р.Б., Автоматизированное формирование нечетких классификаторов самонастраивающимися коэволюционными алгоритмами: Дис. канд. техн. наук: Красноярск, 2010 - 192 с.

Размещено на Allbest.ru