Содержание к диссертации
Введение
1. Проблема обеспечения качества программно-аппаратных средств 8
1.1 .Структура программно-аппаратных систем 8
1.2. Структура показателей качества программно-аппаратных систем 10
1.2.1. Показатели качества технических средств 10
1.2.2. Показатели качества программных средств и информационного обеспечения 13
1.3. Обеспечение качества программно-аппаратных систем на этапах жизненного цикла 13
1.4. Методы оптимизации качества программно-аппаратных систем 18 1.4Л. Критерии оптимальности принимаемых решений 18
1.4.2. Нечеткость информации в определении качества 24
1.5. Задача управления качеством программно-аппаратных систем как многокритериальная многопараметрическая задача с нечеткой информацией 27
Выводы по главе 1 30
2. Генетическая модель программно-аппаратных систем 31
2.1 Синергетические и гомеостатические принципы оптимизации качества программно-аппаратных систем 31
2.2. Согласование требований по качеству ПАС на этапах жизненного цикла 32
2.3. Мультихромосомная модель оптимизации качества программно-аппаратных систем 36
2.3.1. Гиперграфовая модель качества ПАС 37
2.3.2. Мультихромосомная генетическая модель программно-аппаратных систем 38
2.3.3. Минимизация структуры мультихромосомной генетической модели ПАС 42 Выводы по главе 2 55
3. Программные средства оценки и многокритериальной оптимизации качества программно-аппаратных систем 56
3.1 Формализация задач оптимизации ПС 56
3.2. Алгоритм оптимизации качества программно-аппаратных систем 63
3.2.1. Основные этапы генетического алгоритма 64
3.2.2. Методы преобразования популяции, использующие эвристики 67
3.3. Программный комплекс MUGORT для оптимизации качества программно-аппаратных
систем 70
Выводы по главе 3 75
4. Оценка качества программно-аппаратных систем по комплексному показателю "надежность" 76
4.1. Анализ требований по надежности программно-аппаратных систем 76
4.1.1. Надежность технических средств ПАС 76
4.1.2. Надежность программного обеспечения 84
4.1.3. Надежность информационного обеспечения 84
4.1.4. Оценка комплексной надежности программно-аппаратных систем 87
4.1.5. Надежность ПАС как многомашинной вычислительной системы 88
4.2. Комплексная оптимизация надежности программно-аппаратной системы АСУ "Снабжение" 90
4.3. Оценка эффективности модели и алгоритмов мультихромосомной оценки качества ПАС 96
Выводы по главе 4 104
Заключение 105
Список использованных источников 106
Приложение 1 110
Приложение 2 132
- Показатели качества технических средств
- Согласование требований по качеству ПАС на этапах жизненного цикла
- Основные этапы генетического алгоритма
- Надежность информационного обеспечения
Введение к работе
* Актуальность проблемы
Программно-аппаратные системы интенсивно входят как в научные исследования, образование, управление промышленными объектами, так и в повседневную жизнь.
К таким системам всегда предъявлялись требования по их качеству. С глобальным внедрением программно-аппаратных систем требования к их качеству значительно возросли и приобретают интегрированный, комплексный характер. Программно-аппаратные системы - это компьютеры и различные технические >стройства со встроенными программно-аппаратными блоками, а также сети, построенные на основе компьютерных (вычислительных) комплексов (hardware), с установленными на них программными и информационными средствами (software). Причем, если ранее задачи обеспечения качества решались, как правило, в отдельности для технических средств, программного обеспечения и информационного обеспечения, то сейчас, в связи с наметившимися тенденциями объединения их в единые комплексы - программно-аппаратные системы, встает вопрос о комплексной оценке и обеспечении необходимого их качества.
Кроме того, требования рынка программно-технических средств ставят вопрос не' только о качестве самих программно-аппаратных систем, но и о методах и способах обеспечения качества и управления процессом обеспечения качества на этапах проектирования, производства и эксплуатации. Эти вопросы являются, в том числе, содержательной частью CALS-технологий (ИПИ-технологий). Требования к отдельным
аспектам обеспечения качества, управления и/или структура показателей качества
регламентируются серией государственных стандартов IS0-9000.
Проблема комплексной оценки и оптимизации показателей качества программно-аппаратных систем должна решаться в рамках этих аспектов. Немаловажную роль при этом играет и оптимальное сочетание цены (изделия, проектирования, производства) и качества.
Необходимость комплексной оценки качества программно-аппаратных систем на этапах жизненного цикла выдвигает ряд вопросов.
Во-первых, это структура обобщенных показателей качества, которая, естественно, должна строиться на установленных стандартами показателях качества технических средств и видов обеспечения (программного, информационного) и их связь с процессами проектирования и производства.
Во-вторых, это интеграция критериев оптимальности качества программно-аппаратных систем.
В-третьих, связь комплексных (интегральных) показателей качества с характеристиками процессов проектирования, производства и эксплуатации.
Совокупность поставленных вопросов приводит к необходимости решения многокритериальных, многопараметрических оптимизационных задач, В последние годы для решения подобных задач развивается аппарат генетических алгоритмов для поиска оптимальных характеристик, в том числе, с использованием принципов гомеостатики и синергетики для формулирования критериев оптимальности.
Все вышесказанное определяет актуальность разработки методов, моделей и алгоритмов оценки и управления качеством программно-аппаратных систем на этапах жизненного цикла, базирующихся на методах эволюционного моделирования (генетических алгоритмах) с использованием принципов гомеостатики и синергетики.
Объект исследования
* Объектами исследования являются программно-аппаратные системы, представляющие
собой системы обработки информации, к которым относятся компьютеры и
компьютеризированные комплексы и системы, в том числе объединяемые в сети, а также
др>гие технические изделия с встроенными программно-аппаратными блоками.
Состояние вопроса
Сформулированное направление исследований базируется на нескольких составных частях:
Структура показателей и методы оценки качества технических систем.
Структура показателей и методы оценки качества программного обеспечения.
Программные средства автоматизации оценки качества технических и программных средств.
Генетические алгоритмы как инструмент решения переборных оптимизационных задач.
Комплексные критерии оптимальности систем, использующие принципы гомеостатики.
Методы управления состоянием сложных систем, основанные на принципах синергетики.
Методы управления требованиями, в частности управление качеством, проектами,
* ресурсами в процессе проектирования и производства.
В каждом из указанных частных направлений в последние годы получены ф определенные научные достижения. В области оценки качества электронной аппаратуры это, в частности работы Брюнина В.Н., Абрамова В.А., Пролейко В.М., Мансурова Б.М. В области оценки качества программных средств - работы Кранкова Е.С., Липаева В.В„ Треногина Н.Г. В области оптимизации систем на основе генетических алгоритмов - работы Батищева Д.И., Норенкова И.П., Курейчика В.М. Однако, их совместное использование для решения поставленных задач в должной мере не разработано, хотя известны исследования по совместному решению некоторых из этих задач.
Совместное использование результатов исследований в отдельных направлениях позволяет сформулировать ряд подходов к решению поставленных вопросов.
Во-первых, использование методов и средств оценки качества технических и программных средств и принципов гомеостатики может привести к разработке интегрированной, комплексной структуры критериев оценки качества программно-аппаратных систем, которые обеспечат их обоснованный выбор на рынке товаров и управление качеством в процессе проектирования и производства.
Во-вторых, развитие аппарата эволюционного моделирования в сторону мультихромосомных генетических алгоритмов, позволяет решать многокритериальные оптимизированные задачи, к которым относятся и задачи управления качеством программно-аппаратных систем на основе интегрированных, комплексных оценок.
В-третьих, использование синергетического подхода позволяет управлять качеством
программно-аппаратных систем как сосредоточенных, так и сетевых структ>р
распределенного типа и/или многопроцессорных вычислительных комплексов, на основе
методов оптимизации качества технических, программных и информационных средств в
„ отдельности.
В-четвертых, использование показателя стоимости позволяет объединить в рамках единой комплексной задачи как качество самих программно-аппаратных систем, так и « задачи управления качеством на этапах проектирования, производства и эксплуатации с целью обеспечения конкурентоспособности на рынке товаров.
Предмет исследования
Предметом исследования являются методы, модели и алгоритмы решения задач оценки, управления качеством и оптимизации структуры программно-аппаратных систем. Цель работы
Общей целью работы является разработка элементов теории обеспечения качества -методов, моделей и алгоритмов, оценки и управления качеством программно-аппаратных систем на этапах жизненного цикла.
Для достижения поставленной цели необходимо решить следующие вопросы:
Разработать комплексную, интегрированную модель качества программно-аппаратных систем на основе оценки качества их компонентов - технических средств, программного и информационного обеспечения.
Разработать версию мультихромосомного генетического алгоритма оптимизации качества программно-аппаратных систем.
Разработать критерии оптимальности качества программно-аппаратных систем, основанных на принципах гомеостатики, как фактора решения многокритериальных, многопараметрических оптимизированных задач переборного типа.
Разработать основы метода управлением качеством программно-аппаратных систем в процессе их проектирования, производства и эксплуатации с использованием принципов гомеостатики.
Реализовать программно разработанные методы и алгоритмы для решения практических задач оптимизации качества программно-аппаратных систем.
Исследовать и обосновать эффективность разработанных алгоритмов и их использование для решения конкретных задач оценки и оптимизации качества программно-аппаратных систем.
Научная новизна
Сформулирована и поставлена математическая задача комплексной, интегрированной оценки качества программно-аппаратных систем и управления процессом обеспечения качества при их разработке, производстве и эксплуатации.
Разработана методика комплексной оптимизации качества программно-аппаратных систем на основе интегрированной оценки качества с использованием принципов гомеостатики.
Разработана математическая мультихромосомная генетическая модель качества, обобщающая комплексный, интегрированный характер системы показателей качества и позволяющая решать многокритериальные оптимизационные задачи >правления качеством программно-аппаратных систем.
Разработан и реализован программно мультихромосомный генетический алгоритм оптимизации качества программно-аппаратных систем, позволяющий решать многокритериальные оптимизационные переборные задачи.
Практическая значимость
Проведенный комплекс исследований, разработанные методы, модели и алгоритмы оценки и управления качеством программно-аппаратных систем позволяют:
1. Оценивать в условиях рыночной конкуренции качество программно-аппаратных систем на основе комплексных, интегрированных показателей и определять необходимую степень соотношения «цена-качество».
В процессе проектирования программно-аппаратных систем обеспечивать оптимальные характеристики их качества как составной части процесса управления требованиями, позволяющие находить компромиссные решения по сочетанию «стоимость-качество» в целях обеспечения конкурентоспособности продукции.
В процессе производства управлять процессом обеспечения качества программно-аппаратных систем как составной части управления заказами в направлении снижения производственных затрат и средств выполнения заказов.
В процессе эксплуатации поддерживать качество программно-аппаратных систем,
в частности многопроцессорных вычислительных комплексов и систем по ' комплексным, интегрированным критериям их оптимальности.
5. Разработанные программные средства решения многокритериальных,
многопараметрических, переборных оптимизированных задач могут быть
применены для решения подобных задач в других практических и научных
приложениях.
Внедрение результатов работы
Основные результаты работы отражены в 3 отчетах на госбюджетные НИР (119-ГБ-053-кач.ибез. 303-ГБ-53-ПТ и 56-ГБ-53-ЛС), зарегистрированных в соответствующих организациях, используются в работе предприятия ГУП НПЦ "ЭЛВИС" при разработке программно-аппаратных систем, в частности, аппаратуры Senesys Middle. Программные средства оптимизационных многокритериальных задач на основе мультихромосомных алгоритмов использованы в работе МИЭТ и при разработке АСУ "Снабжение" на предприятии ЗАО "НТЦ ЭЛИНС", что подтверждено соответствующими документами.
Кроме того, разработанные модели и алгоритмы используются в учебном процессе кафедры ИПОВС МИЭТ, что также подтверждено соответствующим документом.
Достоверность результатов
Достоверность полученных в диссертации результатов обусловлена корректной постановкой задачи, математическим обоснованием методов её решения, сравнением полученных результатов с ранее полученными решениями в процессе выполнения в МИЭТ и на предприятиях ЗАО "НТЦ ЭЛИНС" и ГУП НПЦ "ЭЛВИС" реальных работ, при выполнении которых проведена экспериментальная проверка разработанных методов, алгоритмов и программных средств в процессе обеспечения надежности АСУ «Снабжение».
Публикации
Основные результаты работы отражены в 11 публикациях, среди которых 6 статей в . сборниках трудов международных и респ>бликанских конференций, две публикации тезисов докладов на конференциях, а также в трех зарегистрированных соответствующих организациях технических отчетах по НИР.
Апробация работы
Основные положения и отдельные результаты работы докладывались на следующих конференциях:
Юбилейная международная конференция по информационным технологиям в на>ке, бизнесе, образовании (IT+SF'2002), Украина, Крым, 2002 г.
Юбилейная международная конференция по информационным технологиям в на)ке, бизнесе, образовании (IT+SF'2002), Украина, Крым, 2003 г.
»
Конференция «Микроэлектроника и информатика», Москва, МИЭТ, 2003 и 2004 гг.
Научная сессия МИФИ-2002 и 2003 гг.
Личный вклад автора в публикациях заключается в разработке комплексной модели оценки качества ПАС на основе оценок качества видов обеспечения и в процесс жизненного цикла, разработке мультихромосомной генетической модели и алгоритма оптимизации, а также их программной реализации.
Структура и объем работы
Диссертация состоит из введения, четырёх глав, основных выводов, списка используемых литературных источников, из 81 наименования и приложения. Она содержит 109 страниц основного текста, 69 страниц приложения, 30 рисунков и 20 таблиц.
На защиту выносится:
Результаты анализа методов и моделей оценки качества компонентов программно-аппаратных систем и сформулированная на этой основе задача комплексной интегрированной оценки и управления их качеством.
Метод оценки качества программно-аппаратных систем, основанный на комплексном подходе к оптимизации качества с использованием принципов гомеостатики как многокритериальной, многопараметрической задаче.
Мультихромосомная генетическая модель программно-аппаратных систем, позволяющая отразить комплексный интегрированный характер показателей качества
Мультихромосомный генетический алгоритм оптимизации, учитывающей специфику задачи оценки и управления качеством программно-аппаратных систем и позволяющий управлять их качеством на этапах жизненного цикла: проектировании, производстве, эксплуатации.
Программная реализация разработанных моделей и алгоритмов, которая может использоваться для решения широкого класса подобных оптимизационных задач.
Показатели качества технических средств
По количеству характеризуемых свойств показатели подразделяются на единичные и комплексные. Единичные показатели являются хорошим инструментом при решении задач управления производством и оценки различных свойств качества.
Комплексные показатели характеризуют несколько свойств и подразделяются на групповые, интегральные, определяющие.
Введение комплексного показателя обусловлено, с одной стороны, невозможностью с помощью единичных показателей оценить одновременно существующую сумму качества продукции, с другой стороны, противоположностью тенденций, отражаемых радом показателей. Часто, например, возникают противоречия между показателями материалоемкости и прочности, долговечности, виброустойчивости. Достижение высоких значений технических характеристик требует больших затрат как при проектировании, так и в производстве. Примером комплексного группового показателя качества .может служить коэффициент готовности кг, характеризующий одновременно его безотказность и ремонтопригодность.
Интегральные показатели, относящиеся также к комплексным показателям, отражают соотношение суммарного полезного эффекта от эксплуатации изделия и суммарных затрат на его создание и эксплуатацию.
Определяющий (обобщенный) показатель качества - показатель, по которому принимают решение оценивать качество продукции. Он может быть выражен главным показателем, наиболее полно отражающим основное назначение продукции, интегральным , показателем или средним взвешенным показателем качества продукции в единой размерности, в относительных безразмерных величинах или в баллах с учетом «веса» » каждого показателя. По применению для оценки уровня качества показатели подразделяются на базовые и относительные. Базовые показатели - показатели качества продукции, принятой за исходную при сравнительных оценках качества. Относительные показатели - показатели, представляющие отношение показателей качества оцениваемой продукции (единичных или комплексных) к соответствующим базовым показателям. По отношению к различным свойствам. В эту группу показателей сведены все показатели качества любого вида изделий, объединенные общим признаком. Таких показателей в этой группе несколько: назначения; надежности; эргономические; эстетические; технологичности; транспортабельности; стандартизации и унификации; патентно-правовые; экологические; безотказности. Показатели назначения характеризуют свойства продукции, определяющие основные функции и область применения. К этой подгруппе показателей относятся: - классификационные показатели; - показатели функциональной и технической эффективности; - конструктивные показатели; - показатели состава и структуры; Показатели надежности являются важнейшими показателями качества изделий. Они являются функциями времени и характеризуют способность изделия выполнять заданные функции, сохраняя свои эксплуатационные характеристики в заданных пределах в течение требуемого промежуточного времени. В соответствии с ГОСТ 27002-83 надежность -комплексное свойство, полностью характеризующееся четырьмя составляющими: безотказностью, долговечностью, сохраняемостью, ремонтопригодностью. Так показатели безотказности храктеризуют свойство аппаратуры непрерывно сохранять работоспособность н течение некоторого времени или некоторой выработки. Показатели долговечности характеризуют свойство объекта сохранять работоспособность до наступления предельного состояния при установленной системе технического обслуживания и ремонтов. Показатели сохраняемости характеризуют свойство объектов сохранять исправное и работоспособное состояние или свойство продуктов и материалов сохранять пригодное к потреблению состояние в течение и после хранения и (или) транспортирования. Показатели ремонтопригодности характеризуют свойство объекта, заключающееся в приспособленнсоти , его к предупреждению и обнаружению причин повреждения и их устранению путем « проведения ремонтов и технического обслуживания. Состав показателей надежности, общие требования и порядок расчета показателей надежности определены ГОСТ 27002-83. Эргономические показатели характеризуют систему «человек-изделие» (в частности «человек-машина») и учитывают комплекс гигиенических, антропометрических, физиологических и психологических свойств человека, проявляющихся в производственных и бытовых условиях [ГОСТ 16035-70, 16456-70]. Эстетические показатели характеризуют информационную выразительность, рациональность формы, целостность композиции и совершенство производственного исполнения продукции. Показатели технологичности характеризуют свойства продукции, определяющие оптимальное распределение затрат материалов, средств труда и времени при технологической подготовке производства, изготовлении и эксплуатации продукции. Номенклатуру показателей технологичности определяют с учетом комплекса стандартов ЕСТПП [ГОСТ 14201-73, 14202-73, 14205-83]. Показатели транспортабельности характеризуют приспособленность продукции к транспортированию, т.е. к перемещению в пространстве, не сопровождающемуся ее использованием или потреблением, а также к подготовительным и заключительным операциям, связанным с транспортированием. Наиболее полно транспортабельность характеризуется, как правило, показателями стоимости, учитывающими все виды затрат по , транспортированию. Показатели транспортабельности продукции выбираются применительно к конкретному виду транспорта или даже к конкретному виду транспортных средств. Показатели стандартизации и унификации характеризуют насыщенность продукции стандартными, унифицированными элементами и степень унификации с другими изделиями. Особенно важны эти показатели для аппаратуры восстанавливаемых систем, длительно находящихся в эксплуатации или хранении. Патентно-правовые показатели характеризуют степень обновления технологических решений, заложенных в продукцию, их патентную чистоту и возможность беспрепятственной реализации в стране и за рубежом. Экологические показатели характеризуют уровень вредных воздействий на окружающую среду, которые могут возникнуть как при потреблении, так и при эксплуатации продукции. Выбор и определение этих показателей зависит, прежде всего, от требований по охране окружающей среды.
Согласование требований по качеству ПАС на этапах жизненного цикла
Как уже указывалось, проблема оптимизации качества программно-аппаратных систем является одной из ключевых задач при их разработке. Однако, эти задачи решаются, как правило, отдельно для: - технических средств; - программных систем; - информационного обеспечения информационных систем; - вычислительных систем в целом. Кроме того, выделяются задачи обеспечения качества в процессах: - проектирования; - производства; - экспл атации. Практика настойчиво выдвигает задачу совместного качества программно-аппаратных систем на основе методов обеспечения качества каждого вида обеспечения в отдельности с учетом объединения требований всех этапов жизненного цикла. Трудность такого подхода заключается в необходимости сочетания различных подходов, серий стандартов по качеству, моделей, методов и алгоритмов, использ емых для решения каждой задачи в отдельности. С синергетической точки зрения имеется определенных «хаос» методов, моделей, алгоритмов, критериев оптимальности и управляемых параметров. Компоненты хаоса качества находятся в различной степени взаимосвязи. Они могут быть: - согласованными; - противоречивыми; - не согласованными, но и не противоречащими друг другу. Более того, для отдельных подсистем, компонентов ПАС сочетания критериев (показателей качества) могут образовывать различные устойчивые группы. Задача наведения «порядка» в системе обеспечения качества ПАС, выделения общих принципов оценки и оптимизации качества для всех этапов жизненного цикла подпадает под методологию синергетического подхода. Вопросы синергетического подхода к построению информационных систем подробно рассмотрены в работе В.В. К рейчика [79]. Мы будем использовать эти идеи применительно к задачам оптимизации качества программно-аппаратных систем. Синергетика определяет три этапа синтеза устойчивых структур в системах: - феноменологический - отыскание процессов, закономерностей существования структур аналогов хаоса и порядка; - модельный - создание комплексной модели; - иерархический - выработка представлений о системе как о составляющей процесса самоорганизации. Совокупность представлений о системе (системе комплексной оценки качества ПАС на этапах жизненного цикла) оформляется, как правило, в виде сети фреймов, гиперграфов и/или графов. Наличие в структуре критериев оценки качества компонентов ПАС противоречий не позволяет использовать традиционные критерии (min,max) оптимальности и приводит к идее гомеостатического подхода. По определению [79], гомеостатика изучает механизмы поддержания динамического постоянства неизменно важных параметров, функций, ритмов и брендов развития. Гомеостаз- механизм поддержания постоянства, а гомеостатика - теория гармонии и дисгармонии. В гомеостатике сосредоточены четыре составляющие: - внутреннее противоречие - иерархическая организация - иерархия гомеостазов - реализация в процессе оптимизации принципа регулируемого противоречия. Эти положения, на наш взгляд, полностью соответствуют проблеме компонентной оптимизации качества программно-аппаратных систем на этапах жизненного цикла изделий. Примем следующую последовательность применения принципов синергетики и гомеостатики к построению методики оценки качества ПАС: - формирование задачи и методов ее решения по согласованию требований по качеству ПАС на этапах жизненного цикла; - обоснование существования гомеостатического состояния процесса обеспечения качества ПАС; - построение гиперграфовой модели качества ПАС; - определение иерархии показателей качества компонентов ПАС в их взаимосвязи; - формирование эволюционного алгоритма обеспечения качества ПАС; - построение мультихромосомной модели качества ПАС; - анализ типа информации о показателях качества и формирование модели учета нечеткой информации. Существуют различные по степени детализации модели стадий жизненного цикла продукции. Наиболее полная иерархия рассматривается в документах по CALS-технологии и приводится, например в [65]. Для целей оценки качества ПАС примем упрощенную модель, представленную на рис. 2.1.
Как установлено выше, показатели оптимальности качества в связи с развитием рыночных отношений делятся на две группы: стоимостные и функциональные.
Под функциональными показателями (критериями) мы в данном случае будем понимать показатели тактико-технических требований к ПАС и потребительские свойства. Противоречия между критериями существуют в каждой группе, однако наиболее с щественными оказываются именно межгрупповые показатели. Условно назовем их « качество-стоимость».
Представим «качественные» зависимости между качеством и стоимостью на этапах жизненного цикла для компонентов ПАС.
Проектирование. Стоимость проектирования определяется стоимостью труда персонала, зависящей от квалификации и количества работников (в основном) , временем разработки, используемыми средствами разработки. Чем выше требования к ПАС должны быть обеспечены на этапе проектирования, тем выше стоимость проектирования. В наибольшей степени это относится к проектированию компонентов технических средств, в наименьшей - к проектированию информационного обеспечения. Хотя, видимо, в дальнейшем стоимость более качественного проектирования ИО будет возрастать в силу увеличения объема информации в ПАС, требований к ее защищенности, распределенного характера баз данных и т.п.
Основные этапы генетического алгоритма
После формирования начальной популяции производится ее ранжирование. В отличие от оптимизации по одному критерию, при многокритериальной оптимизации ранжирование популяции может быть проведено не единственным способом. В любом сл чае желательно, чтобы всем предпочтительным особям был назначен один и тог же ранг, а также, чтобы более приспособленные особи оказались бы рангом выше, чем менее приспособленные.
В [61] предложен следующий подход к ранжированию. Для особи х„ из поколения t и соответствующего ей вектора критериев Y„ обозначим r(t)u - число особей в популяции, более предпочтительных, чем х„. Текущее положение х„ в ряду особей задается как rank(xu,t)=r(t)„, что обеспечивает присвоение ранга 0 всем наиболее предпочтительным особям. В случае большой однородно распределенной популяции, состоящей из N особей, нормализованный ранг r(t)/N дает возможность оценить размеры части пространства поиска, содержащей особи, предпочтительные по отношению к данной. Эта оценка показывает, насколько легко текущее решение может быть улучшено путем чисто случайного поиска (перебора), кроме того, данная оценка является мерой стоимости особи, не зависящей от шкалы критериев. При обработке популяции с заданным ранжированием для формирования нового поколения особей различные эволюционные алгоритмы используют различные схемы отбора и репродукции.
Приспособленность особи отличается от ее предпочтительности, которая отражает результат процесса принятия решения. Процесс отбора определяет, какие особи в действительности влияют на производство следующего поколения, таким образом, приспособленность является частью стратегии поиска, а не процесса принятия решения.
Традиционный подход к назначению приспособленности, основанной на ранжировании популяции, состоит в следующем: - Популяция сортируется в соответствии с рангами; - Значение приспособленности присваивается, начиная с лучших особей (ранг 0) и заканчивая худшими (ранг = max r(,) N), путем интерполяции в соответствии с некоторой функцией, обычно линейной или экспоненциальной, но возможно и любой другой не бывающей. - Значения приспособленности, назначенные особям с одним и тем же рангом, усредняются таким образом, что все они производят потомство с одинаковой скоростью, поддерживая постоянное значение глобальной популяционной приспособленности. Назначение приспособленности, основанное на ранжировании, как видим, преобразует ландшафт стоимости, определенный рангом, в ландшафт приспособленности, также независимый от шкал критериев. Для МКГА НХ приспособленностью особи является степень ее принадлежности множеству допустимых решений. Как указано выше, обычно множество альтернатив Р, определяемое функцией предпочтительности и множество допустимых решений D на каждом шаге ГА не совпадают. При Парето-оптимизации для определения множества допустимых решений используется функция предпочтительности, поэтому степенью приспособленности особи считается ее значение функции предпочтительности, заданной формулой u.p(x) = iY(x)A...AU,Ym(x). Селекция особей в популяции осуществляется по наименьшему ат,„-уровню множества Р, заданному СПР, а выбор окончательного решения -но уровню атах Оператор скрещивания в генетическом алгоритме играет роль фактора насіедственности, закрепляющего у потомков лучшие признаки, полученные от родителей. Одной из особенностей предлагаемого генетического алгоритма является отход от традиционной схемы "размножения", используемой в большинстве реализованных ГА. Классическая схема предполагает ограничение численности потомков путем использования так называемой вероятности кроссовера. Такая модель придает численности потомков, t вообще говоря, недетерминированный характер. Предлагается отойти от вероятности кроссовера и использовать фиксированное число "родительских" совокупностей на каждом поколении, при этом каждая совокупность численностью N порождает такое же количество "потомков". Такой подход хорош тем, что делает процесс поиска более управляемым и предсказуемым в смысле вычислительных затрат. Системой скрещивания называют способ подбора пары "родительских" особей для создания двух "потомков". Система скрещивания МКГА НХ предполагает использование N "родителей" одновременно для формирования N потомков. Особи, отобранные для воспроизводства, подвергаются кроссоверу (иногда называемому рекомбинацией). Пусть особь состоит из L генов, тогда для кроссовера случайным образом выбирается N-1 из L-1 возможных точек разрыва, находящихся на границе между соседними генами в особи. Родительские структуры разрываются на N сегментов по этим точкам. Затем, случайным образом выбирается первый сегмент для первого потомка из N возможных, для второго случайный выбор производится из N-1 сегментов, и т.д., та же операция повторяется для последующих і сегментов. После окончания процесса будут сформированы N потомков. Например, есть 4 родительских структуры, каждая из которых состоит из 7 полей различного типа. Пусть из 6 возможных точек разрыва выбраны точки 1,3,4,6. Родители и их потомки показаны ниже.
Надежность информационного обеспечения
Основой надёжности работы ИО (СУБД) с данными является системный журнал или журнал транзакций. В файле журнала отображаются все изменения, производимые над данными всеми пользователями системы.
Таким образом, сбои оборудования/питания не могут привести к потере или порче данных. При следующем старте система просканирует журнал и базу в поисках возможных несоответствий. Все некорректные данные базы будут исправлены, и только после этого система начнет обрабатывать запросы прикладных задач. При исправлении последних изменений СУБД может столкнуться с тем, что часть из них достигла дискового пространства файлов полностью, некоторые изменения лишь частично записались на диск, а некоторые так и остались в буферах ядра системы, не затронув собственно файлы базы данных. Итак, современные СУБД при исправлении неполных/неверных данных может либо і вернуть их в то состояние, в котором они находились до изменений (откат изменений), либо продолжить модификацию данных следуя журналу транзакций (прокрутка вперёд).
При этом используется следующее простое правило: если пользователь получил «уведомление» о том, что его изменения перенесены в базу, то при следующем запуске системы новые данные обязаны находиться в базе. Режимы транзакций СУБД
В современных СУБД три основных стратегии (или режима) работы транзакций: 1. Оптимистичная. Модификации данных не поступают в базу, однако, поступают в системный журнал вместе со старым образом данных. При фиксации изменений транзакции система начинает перенос изменений из журнала в базу данных. При переносе очередного изменения Линтер сравнивает старый образ модифицируемых данных из журнала и из базы. Если образы совпадают (данные никто не менял), то это очередное изменение попадает в базу, в противном случае (кто-то уже успел раньше изменить и зафиксировать данные) откатывается вся транзакция, а приложению возвращается соответствующее сообщение. Этот режим работы транзакций при всех его недостатках обладает существенным достоинством - скоростью. Данные не блокируются, каждая задача работает исходя из оптимистичного предположения о том, что кроме неё с базой не работает никто, и никто никого не ждёт. А при возникшей коллизии транзакцию можно и повторить. Что очень удобно особенно в системах массового обслуживания 2. Пессимистичная. Это классический режим работы транзакций. Все изменения поступают сразу в базу данных, а также и в системный журнал. Однако эти изменения не видны другим транзакциям до тех пор, пока не пройдет ее фиксация. До тех пор работает аппарат блокировок, запрещающий модификацию читаемых или чтение модифицируемых данных. Тупиковые ситуации (взаимоблокировки) разрешаются обычно в пользу более высокоприоритетной транзакции, а при равном приоритете в пользу той транзакции, которая проработала большее время. 3. Стратегия read-only. і Удобный режим транзакций, которые не делают никаких изменений в базе данных, их функция - только чтение (например, отчеты за день, сведение данных для анализа и т п.). Обычно такие транзакции вовлекают в свою работу большие объемы данных, так что блокировка всех используемых данных может привести к длительной задержке прочих транзакций. В СУБД транзакция read-only не бчокирует данные Но при её появлении, все друтие транзакции, изменяя данные, оставляют (для неё и ей подобных) тот образ, который имели данные, когда транзакция read-only стартовата Таким образом, транзакция read-only получает базу данных именно на момент ее старта как бы моментальный «снимок» базы данных. Иерархия транзакций в современных СУБД В сегодняшних СУБД каждое приложение может использовать как обычные плоские транзакции, так и иерархические. Классические плоские транзакции представляют собой последовательность запросов, завершающуюся оператором фиксации/отката. Причем необходимость отката транзакции может . возникнуть и в середине транзакции. При этом из базы данных будет удалены все изменения, которые успела сделать транзакция. Приложение не может откатить лишь отдельные изменения, ему разрешено руководствоваться только одним принципом - «гаи все, гаи ничего» Несомненно, это слишком категоричный и, следовательно, не всегда приемлемый принцип. Особенно в системах с нечёткой логикой. Например, приложению (см. следующий рисунок) нужно произвести три действия А, В и D в одной транзакции. Причём действия А и D являются необходимыми, а вот для действия В есть «запасной вариант» - действие С. Так что приложение пытается в первую очередь выполнить действие В, и только если по какой-либо причине результаты отработки В «не устраивают» или возникла ошибка, то изменения, сделанные В, откатываются, и приложение предпринимает резервное действие С. Такую логику транзакции не удастся реализовать при помощи линейных транзакций. Для использования подобных транзакций СУБД Линтер предоставляет пользователю возможность иерархии транзакций. При этом действуют следующие правила: 1. Подчинённые (вложенные) транзакции действуют по линейному принципу. И могут работать зависимо или независимо друг от друга в любом из режимов (от оптимистичного до read-only). 2. Каждая из подчиненных транзакций может быть фиксирована/откатана независимо от других подчиненных транзакций. 3. Подчинённые транзакции «видят» изменения, сделанные прочими подчиненными транзакциями (имеющими общего предка). Полностью изолированы только транзакции различных иерархий. 4. Фиксация/откат головной транзакции приведёт к фиксации/откату всех подчиненных и не завершённых (на данный момент) транзакций. Подобный подход к системе использования транзакций гораздо более гибкий. Архивирование таблиц (базы данных) Утилиты архивирования СУБД позволяют сохранять (со сжатием) базы данных целиком/выборочно. При этом работа утилит не останавливает работу других пользователей СУБД. Утилита делает просто «сжатый снимок» базы данных на какой-то момент времени.
