Содержание к диссертации
Введение
Глава 1. Архитектуры микропроцессорных систем. методы и средства проектирования 11
1.1 Анализ архитектур микропроцессорных систем. Уровни и методы проектирования систем 11
1.1.1 Основные подходы канализу архитектур 11
1.1.2 Архитектуры функционально распределённых встраиваемых микропроцессорных систем 15
1.1.3 Уровни и методы проектирования систем 19
1.2 Существующие подходы к решению задачи аппаратно-программного разбиения системы 25
1.3 Постановка задачи оптимизации в условиях неопределённости 31
1.4 Анализ задачи и методов её решения 35
1.5 Анализ генетических алгоритмов 44
1.5.1 Общая характеристика генетических алгоритмов и проблемы, возникающие при их разработке 44
1.5.2 Схемы работы генетических алгоритмов. Параллельные генетические алгоритмы 47
1.5.3 Функция пригодности особей популяции 50
1.5.4 Кодирование параметров решения задачи 50
1.5.5 Решение проблемы ложных значений в генах 51
1.5.6 Метод выбора брачных пар 52
1.5.7 Оператор отбора 53
1.5.8 Оператор кроссовера 57
1.5.9 Оператор мутации 59
1.5.10 Общие модификации операторов 61
Выводы по главе 62
Глава 2. Разработка модели и метода оптимизации . 68
2.1 Оптимизационная модель ФР ВМС 68
2.1.1 Проблема оценки времени выполнения задачи . 68
2.1.2 Модель выполнения задачи ФР ВМС 70
2.1.3 Расчёт характеристик ФР ВМС 72
2.2 Алгебра нечётких интервалов и их сравнение 75
2.2.1 Функция формы нечёткого интервала. Выбор и обоснование 75
2.2.2 Алгебра нечётких интервалов 79
2.2.3 Сравнение нечётких интервалов 89
2.3 Разработка метода оптимизации 94
2.3.1 Основные особенности и схема работы генетического алгоритма. Реализованные методы и операторы 94
2.3.2 Общие параметры генетического алгоритма 95
2.3.3 Оператор отбора 97
2.3.4 Метод выбора брачных пар 99
2.3.5 Оператор кроссовера 100
2.3.6 Оператор мутации 103
2.3.7 Механизм избавления от непригодных решений . 104
2.3.8 Миграции 106
Выводы по главе 107
Глава 3. Разработка инструментальных средств автоматизированного проектирования 111
3.1 Архитектура САПР SoftCAD 111
3.2 Основные структуры данных, методы и алгоритмы 113
3.2.1 Основные потоки данных в САПР SoftCAD 113
3.2.2 База данных САПР SoftCAD 114
3.2.3 Классы, типы и структуры данных, используемые для реализации генетического алгоритма
и оптимизационной модели 123
3.2.4 Файл HacTpoeKSoftCAD.INI 141
3.2.5 Реализация операторов и механизмов генетического алгоритма 143
3.2.6 Классы и структуры данных, используемые для реализации операций над нечёткими интервалами 151
3.3 Порядок работы. Пользовательский интерфейс 155
3.3.1 Назначение САПР SoftCAD 155
3.3.2 Состав САПР SoftCAD ; 156
3.3.3 Интерфейс САПР SoftCAD 157
3.3.3.1 Обзор рабочей среды САПР SoftCAD 157
3.3.3.2 Загрузка и сохранение данных 159
3.3.3.3 Настройка параметров модели и
популяций 160
3.3.3.4 Моделирование. Получение результатов 175
3.3.3.5 Состав отчётности о ходе эволюции популяций и её результатах 180
3.3.3.6 Получение справочных данных. Дополнительные возможности 183
Выводы по главе 186
Глава 4. Исследование модели, метода оптимизации и инструментальных средств 189
4.1 Параметры и условия моделирования 189
4.2 Задача формирования изображений 191
4.2.1 Описание ФР ВМС «Модуль формирования изображений» 191
4.2.2 Параметры ФР ВМС «Модуль формирование изображений» 194
4.2.2.1 Аппаратная конфигурация и дополнительные ресурсы 194
4.2.2.2 Список функций 195
4.2.2.3 Стоимостные параметры 196
4.2.2.4 Временные параметры 198
4.2.2.5 Ёмкостные параметры 204
4.2.2.6 Надёжностные параметры 205
4.2.2.7 Параметры массы 205
4.2.2.8 Параметры габаритов (площади) 206
4.3 Результаты моделирования 206
4.3.1 Исследование генетического алгоритма 206
4.3.2 Оптимальные схемы работы генетического алгоритма 208
4.3.3 Результаты моделирования для ФР ВМС
«Модуль формирования изображений» 210
4.3.4 Оценка эффективности САПР SoftCAD 212
Выводы по главе 218
Заключение 221
Библиографический список
- Анализ архитектур микропроцессорных систем. Уровни и методы проектирования систем
- Оптимизационная модель ФР ВМС
- Архитектура САПР SoftCAD
- Описание ФР ВМС «Модуль формирования изображений»
Введение к работе
Для последних лет характерно широкое распространение встраиваемых систем: сегодня практически любое достаточно сложное электронное устройство оснащается микропроцессорной системой, управляющей его функционированием. Требования, предъявляемые к быстродействию, надёжности, стоимости и другим параметрам встраиваемых систем, являются обычно крайне высокими, что ставит задачу их оптимального проектирования.
Для встраиваемых систем характерна неэффективность при использовании мощных микропроцессорных ядер, что связано с их повышенным энергопотреблением и тепловыделением. Поэтому часто применяют функционально распределённые встраиваемые микропроцессорные системы (ФР ВМС): часть функций системы реализуется программно, на сравнительно маломощном процессоре (или процессорах), а часть - аппаратно, с применением либо заказных специализированных СБИС, либо, всё чаще, программируемых логических интегральных схем (ПЛИС). Всё более распространёнными становятся «системы на кристалле» (СнК), интегрирующие процессоры и программируемую логику. Ввиду высоких требований, предъявляемых к встраиваемым системам, существует проблема оптимального распределения функций задачи (класса задач) между программной и аппаратной частью системы, а на дальнейшем уровне детализации - по конкретным вычислительным модулям.
Исторически функциональное распределение использовалось не только во встраиваемых системах. В 80-е годы прошлого века для специализированных применений разрабатывались проблемно ориентированные системы (ПОС), состоящие из ЭВМ общего назначения («базовой машины») и функционально ориентированных процессоров (ФОП), предназначенных для эффективной реализации сложных функций [78]. Активные работы в этом направлении проводились на кафедре «Вычислительная техника» Ленинградского государствен- ного электротехнического института (ныне Санкт-Петербургский государственный электротехнический университет) под руководством Балашова Е. П. и Пузанкова Д. В.
Под проблемной ориентацией понималась степень соответствия архитектурных решений ПОС специфике класса задач. Функциональная ориентация рассматривалась в качестве одного из возможных средств проблемной ориентации. Она предполагала включение в состав ПОС дополнительных аппаратных средств, ориентированных на реализацию функций, являющихся специфическими для данного класса задач. Этот подход позднее стал широко использоваться во встраиваемых системах.
Наиболее интенсивные исследования в области ФР ВМС стали проводиться с конца 80-х и начала 90-х годов прошлого века. Основные результаты нашли отражение в работах Kalavade A., Lee Е., Gupta R., Micheli G., Ernst R., Henkel J., Peng Z., Kuchcinski K., Vahid F., Gong J., Gajski D. и др. [108, 110, 112, 113, 115, 116,119,123].
В ранних работах, посвященных проектированию встраиваемых систем, вводились и обсуждались характеристики хороших аппаратно-программных решений, но автоматизация процесса их получения не предполагалась. Появляющиеся алгоритмы автоматизации в зависимости от целей, которые ставились при проектировании системы, делились в основном на два класса: аппа-ратно-ориентированные и программно-ориентированные. Степень функциональной детализации варьировалась от уровня операций до уровня тел циклов, процедур или целых задач.
К середине 90-х годов стали появляться усложнённые и усовершенствованные методики, предполагающие многокритериальные оценки получаемых решений, динамическую функциональную детализацию и т.д. Однако основные усилия были сосредоточены на создании динамически реконфигурируемых архитектур встраиваемых систем и разработках САПР сквозного проектирования.
Появились программные системы, поддерживающие проектирование сложных микропроцессорных архитектур с произвольной топологией внутренних соединений и произвольным сочетанием центральных процессоров и аппаратных блоков [10, 72,82,99, 105, 109, Ш, 114, 117, 118]. Большой вклад в разработку таких систем, базирующуюся на проводимых фундаментальных и прикладных исследованиях в области анализа структур вычислительных комплексов, внесла лаборатория вычислительных комплексов МГУ в лице Смелянского Р. Л., Костенко В. А. и др. [35, 37, 72, 82, 95].
Однако практически во всех используемых подходах и моделях не учитывается, что значениям параметров проектируемых систем всегда сопутствует фактор неопределённости. Это может быть следствием неполноты, недостатка информации, разброса возможных значений, а также протяжённости во времени. Возможность неявной подмены неопределённых величин точными числовыми значениями обеспечивается уточнением данных в процессе проектирования, что может сопровождаться большими временными, людскими и финансовыми затратами; выбором наиболее представительных (обычно средних) точек, которые не всегда могут достаточно адекватно заменить весь диапазон значений; сужением или пересмотром временных интервалов, для которых выполняются оценки, что не всегда возможно или удобно. Поэтому, учитывая имеющиеся тенденции к уменьшению сроков разработки встраиваемых микропроцессорных систем, представление моделей и средств проектирования для условий неопределённости проектной информации является крайне актуальным.
Целью работы является разработка и исследование модели, метода и средств автоматизированного проектирования ФР ВМС в условиях неопределённости проектной информации для повышения качества проектирования, снижения временных и финансовых затрат. Исходя из этой цели, были поставлены и решены следующие задачи:
Выбор и модификация оптимизационной модели ФР ВМС.
Выбор способа формализации неопределённости.
Разработка математического аппарата для выполнения алгебраических операций над нечёткими данными и их сравнения,
Разработка метода оптимизации ФР ВМС.
Разработка специализированной САПР ФР ВМС. Исследование и настройка метода оптимизации.
Объектом исследования в работе является автоматизация проектирования ФР ВМС, предметом исследования служат применяемые для этого модели и методы.
Методы исследования базируются на теории вычислительных систем, теории надёжности, теории нечётких интервалов (НИ), теории оптимизации, эволюционном моделировании, теории алгебраических систем и строятся на сочетании формальных и содержательных методов.
Достоверность научных положений, выводов и рекомендаций подтверждена непротиворечивостью применяемых моделей и методов, результатами экспериментальных исследований, результатами использования созданной специализированной САПР в проектной организации и вузе.
Анализ архитектур микропроцессорных систем. Уровни и методы проектирования систем
Многие сферы применения вычислительной техники характеризуются повышенными требованиями к быстродействию, что до сих пор является основным побудительным мотивом технического прогресса в этой области [8]. Уже на ранних этапах развития средств вычислительной техники в качестве перспективных способов существенного увеличения быстродействия рассматривались различные варианты многопроцессорности и параллельной обработки данных [8, 41, 50, 71, 78]. Принципиально важными решениями, реализованными в рамках этих подходов, явились 1) конвейерная организация выполнения команд, 2) включение в систему команд векторных операций, позволяющих с помощью одной команды обрабатывать целые массивы данных, 3) распределение вычислений среди многих процессоров. Сейчас многопроцессорные технологии стали активно применять и для однокристальных процессоров, поскольку их производители испытывают существенные трудности в плане дальнейшего наращивания тактовых частот: плотность упаковки транзисторов на кристалле возросла настолько, что стало возможным создание многоядерных процессоров [6].
В настоящее время архитектуры систем, ориентированных на повышенное быстродействие, представлены четырьмя основными направлениями [8]: I) симметричные мультипроцессорные системы (SMP-системы, Symmetric Multi-Processing systems), 2) системы с массовым параллелизмом (МРР системы, Massively Parallel Processing systems), 3) кластерные системы, 4) векторно-конвейерные системы.
Симметричные мультипроцессорные системы. Для систем SMP-архитектуры характерно, что все процессоры имеют прямой и равноправный доступ к любой точке общей памяти, SMP-системы первоначально строились из нескольких однородных процессоров и массива общей памяти, к которой процессоры подключались через общую системную шину. Однако такая архитектура оказалась непригодной для создания масштабных вычислительных систем прежде всего из-за большого число конфликтов при обращении к общей шине. Частично проблема была решена разделением памяти на блоки, подключение к которым с помощью коммутаторов позволило распараллелить обращения от различных процессоров. Для современных процессоров с иерархической организацией памяти проблема обострилась: в многопроцессорных системах, построенных на базе микропроцессоров со встроенной кэш-памятью, нарушается принцип равноправного доступа к любой точке памяти и требуются механизмы, обеспечивающие актуальность данных для всех процессоров. Современные системы с SMP-архитектурой создаются обычно из сравнительно небольшого количества однородных серийно выпускаемых микропроцессоров и массива общей памяти, подключение к которой производится либо с помощью общей шины, либо с помощью коммутатора.
Системы с массовым параллелизмом. Недостатки, присущие многопроцессорным системам с общей шиной, полностью устраняются в системах с массовым параллелизмом. МРР-системы представляют собой многопроцессорные системы с распределённой памятью, в которых с помощью некоторой коммуникационной среды объединяются однородные вычислительные узлы. Каждый узел обладает всем необходимым для независимого функционирования, включая один или несколько процессоров, собственную оперативную память, подсистемы ввода/вывода и т.д. Оперативная память в МРР-системах имеет трёх уровневую структуру: 1) кэш-память процессора, 2) локальная оперативная память узла, 3) оперативная память других узлов. Процессоры имеют прямой доступ только к своей локальной памяти, доступ к памяти других узлов обычно выполняется при помощи передачи сообщений. Системы с распределённой памятью хорошо подходят для параллельного выполнения независимых программ, написание же эффективных параллельных программ для таких систем является более сложной задачей, чем для SMP-систем.
Кластерные системы. Кластерные системы логически развивают идеи, которые заложены в архитектуре МРР-систем, представляя собой наборы связанных полноценных компьютеров, выступающих в роли узлов кластера и используемых в качестве единого вычислительного ресурса. При этом каждый из узлов может функционировать под управлением своей собственной операционной системы. Кластер может включать компьютеры разного типа и различной мощности. Разработано множество диспетчерских систем пакетной обработки заданий, позволяющих отправить задание на обработку кластеру в целом, а не отдельному компьютеру. Узким местом подобных систем является пропускная способность коммуникационной среды.
Векторно-конвейерные системы. Название им дали два принципа, заложенные в архитектуре процессоров: 1) конвейерная организация обработки потока команд, 2) введение в систему команд векторных операций, позволяющих оперировать с массивами данных.
Классический векторный процессор имеет отдельные модули скалярной и векторной обработки [78]. Модуль скалярной обработки обеспечивает выборку команд из памяти и выполнение скалярных команд. Векторные команды поступают для выполнения в модуль векторной обработки. В его состав входят несколько конвейерных операционных устройств, обеспечивающих высокую производительность при обработке векторных данных.
Оптимизационная модель ФР ВМС
Методы случайного поиска (метод слепого поиска, или метод Монте-Карло, метод случайных направлений, методы поиска с самообучением) [19, 35, 57, 101] осуществляют более или менее хаотичные перемещения по пространству поиска с фиксацией лучшего найденного решения. Так, метод Монте-Карло заключается в многократном случайном выборе допустимых вариантов решения и запоминании наилучшего из них. Хотя ясно, что Vs 0 вероятность Р( p((U, Х)т) - р є) — 0 при х -» со, где р — оптимальное значение функции p(U, X), однако за разумное количество итераций метод не сможет обеспечить нахождение оптимального решения и, отличаясь непредсказуемым поведением, редко используется самостоятельно [101]. Даже более сложные методы случайного поиска не могут рассматриваться в качестве надёжных и перспективных.
Таким образом, интерпретация задачи (1.1) в качестве задачи нелинейного программирования оказалась непродуктивной. Однако задача получения оптимальной аппаратно-программной конфигурации, подразумевая выбор из крайне большого числа вариантов, может быть отнесена к классу комбинаторных, для которых существуют свои методы решения (хотя в расчёте на худшую задачу они всегда неэффективны).
Для представления задачи (1.1) воспользуемся моделью двудольного графа G = (F, U, Е), где F = (f,,..., f„) - вершины, соответствующие функциям задачи, 0 = ( ,..., ,..., ,..., , ) - вершины, соответствующие вычислительным модулям, Е- ребра, соединяющие вершины классов F и U (рис. 1.2). Наличие связи означает, что соответствующая функция fj может выполняться в модуле Uj с качеством Wjj. Решением задачи является граф G1, степени всех вершин класса F у которого равны единице. Тогда Будем считать, что целевая функция подлежит минимизации.
Поскольку задача аппаратно-программного разбиения является NP-полной [117], актуальным является вопрос о применении методов, более эффективных, чем полный перебор, т.е. методов сокращённого перебора.
Одним из наиболее распространённых методов решения комбинаторных задач является метод ветвей и границ [19, 21, 25, 33, 57, 59, 68, 73]. Метод основан на идее последовательного разбиения всего множества допустимых решений на подмножества и вычислении оценок (границ), позволяющих отбрасывать подмножества, заведомо не содержащие оптимальное решение задачи.
В нашем случае разбиение на подмножества может происходить на основе перебора рёбер, инцидентных вершинам класса F, и выполняться последовательно от вершины к вершине, давая каждый раз столько же подмножеств, сколько рёбер инцидентно очередной вершине fj. Так, по вершине f„ (см. рис. L2) можно выполнить разбиение на три подмножества, в каждое соответственно войдёт ребро с весом wnl, \vnd , wn(tI]+d +d j. Известно, что ключевым фактором, определяющим эффективность метода, является способ оценки под множеств решений. В нашем случае таких оценок будет две - для нижней и верхней границы. Способ их вычисления достаточно очевиден: для каждой из оставшихся свободными вершин класса F следует делать выбор соответственно либо лучшей, либо худшей по целевому критерию альтернативы. При этом для вычисления нижней границы целесообразно использовать функцию из (1.4а), вычисляющую значение целевого критерия без учёта ограничений (штрафа), верхней- из (1.46), которая вычисляет значение целевого критерия с учётом возможного штрафа. Решение, соответствующее нижней границе, скорее всего, нарушает ограничения, верхней— возможно, нет, но оптимум в данном подмножестве обязательно будет лежать в диапазоне этих границ. Подмножество решений будет отброшено как бесперспективное, если его нижняя граница окажется больше верхней хотя бы одного другого подмножества. Для организации сравнения можно вычислять своего рода «рекорд» — минимальное значение верхней границы для всех подмножеств — и сравнивать с ним значения нижних границ всех подмножеств решений. Однако совсем не обязательно, что подмножество, несущее текущий рекорд, будет содержать оптимальное решение. Поэтому стратегия поиска решения может заключаться в выполнении последовательного ветвления по всем конечным подмножествам дерева, исключая «обрубленные» (указанным выше способом), и в их последующей оценке.
В начальной стадии работы алгоритма ветвление по каждому из подмножеств, скорее всего, будет вестись без отсева бесперспективных подмножеств, и только когда в части подмножеств закрепится достаточно много рёбер с большим весом, оценки снизу перестанут быть чрезмерно низкими. Несмотря на то, что при продвижении в глубину вычисление границ упрощается, при очень жёстких ограничениях, как представляется, сложность решения задачи таким способом будет мало отличаться от сложности полного перебора.
Архитектура САПР SoftCAD
САПР SoftCAD была разработана в среде Delphi в рамках технологии объектно-ориентированного программирования и проектировалась в качестве MDI-приложения Windows. Основная функциональность и данные инкапсулированы в классах, распределённых по модулям.
Архитектуру САПР образуют четыре основных блока (рис. 3.1): 1) блок ввода параметров оптимизационной модели и ГА, 2) блок операций над НИ, 3) блок реализации оптимизационной модели и ГА, 4) блок моделирования и выдачи результатов.
В состав блоков входят как модули форм, поддерживающие функционирование визуального интерфейса с пользователем (табл. 3.1), так и модули, не связанные с формами (табл. 3.2).
Отдельно нужно отметить модуль данных DataModuIe, который связан с формой DM, доступной только на этапе проектирования. Он относится к блоку ввода параметров, и содержит компоненты для связи с базой данных (БД) и ряд функций по её обслуживанию: создание структуры таблиц и сохранение (считывание) популяций.
Во время работы САПР основная работа с данными и методами оптимизационной модели сосредоточена в объекте SysMod класса TSysMod, который создаётся в единственном экземпляре (о составе класса см. п. 3.2.3). Изменения состояния этого объекта соответствуют в целом этапам применения созданной САПР.
Загрузка данных в поля и структуры объекта SysMod может быть выполнена двумя способами: 1. Ввод данных «с нуля». 2. Загрузка из БД, после чего данные могут быть модифицированы. В ходе моделирования объект SysMod а) служит источником данных, б) хранит промежуточные данные, в том числе и вспомогательные, и в) сохраняет полученные результаты, т.е. преобразованную популяцию, имею щую в своем составе найденное оптимальное решение (или решения).
Сохранение в БД параметров и популяций может быть выполнено как до, так и после моделирования, причём популяции, прошедшие эволюцию, могут быть сохранены под другим именем.
База данных САПР SoftCAD состоит из набора файлов (таблиц) формата Paradox. Рассмотрим их назначение и структуру.
Файл БД model (табл. 3.3) всегда содержит только одну запись, храня часть полей класса TSysMod. Соответствующие данные в программе вводятся на вкладках Общие, Стоимость и надёжность (группа опций Детализация: стоимость и надёжность СнК), Популяции формы Параметры модели и генетического алгоритма.
Файл БД nomenclature (табл. 3.4) предназначен для хранения части полей класса TSysMod, отвечающих за описание параметров номенклатуры процессоров, специализированных СБИС и ПЛИС. Количество записей и их порядок соответствуют общему количеству и порядку вычислительных устройств. Эти данные в программе вводятся на вкладках Номенклатура и Интеграция формы Параметры модели и генетического алгоритма.
Файл БД triangular_matrix (табл. 3.8) хранит поля структуры TTrianguIarMatrixItem. Количество записей соответствует количеству точек вызовов функций для всех задач. Соответствующие данные в программе вводятся на вкладке Функции (группа опций Детализация: вызовы функций) формы Параметры модели и генетического алгоритма.
Файл БД cost_rel__modules (табл. 3.9) хранит часть полей класса TSysMod: в первой записи - стоимость, во второй - часы наработки на отказ. Количество полей определяется количеством процессоров, специализированных СБИС и ПЛИС. Соответствующие данные в программе вводятся на вкладке Стоимость и надёжность (группа опций Детализация; стоимость и надёжность модулей) формы Параметры модели и генетического алгоритма.
Файл БД cost_functions (табл. 3.10) хранит часть полей класса TSysMod. Количество записей равно количеству функций, количество полей - количеству процессоров, специализированных СБИС и ПЛИС. Данные вводятся на вкладке Стоимость и надёжность (группа опций Детализация: стоимость реализации функций) формы Параметры модели и генетического алгоритма.
Описание ФР ВМС «Модуль формирования изображений»
Известно [18, 22, 35], что несмотря на общую наглядность работы ГА, он требует определённых усилий при настройке под конкретный класс задач и под отдельную задачу в классе. И даже после настройки высокую степень уверенности в получении оптимального решения может дать только неоднократный прогон алгоритма (исключая случаи тестовых задач с заранее известными решениями). Тем не менее, для сравнительной оценки различных вариантов ГА можно применять ряд критериев, позволяющих выявить по крайней мере наиболее неудачные варианты настроек.
В ходе экспериментов были использованы следующие критерии успешности работы алгоритма:
1) получение оптимального решения,
2) количество вычислений целевой функции (ЦФ), которые потребовались для получения оптимального решения (с применением порогового значения),
3) количество поколений, сменившихся до момента обнаружения оптимального решения (с применением порогового значения),
4) количество поколений, сменившихся до схождения к оптимальному решению при заданном проценте схождения,
5) время работы до схождения к оптимальному решению при заданном проценте схождения (здесь также сказывается вычислительная сложность реализации различных операторов алгоритма).
Если алгоритм при данных настройках стабильно выдаёт только хорошее, но не оптимальное решение, то такие настройки не могут быть рекомендованы к использованию. Поэтому первый критерий позволяет отбросить заведомо непригодные варианты.
Второй и третий критерии являются сходными, однако второй учитывает также и размер популяции и поэтому является более информативным.
Четвёртый и пятый основаны на признаке вырождения популяции к одному (лучшему) решению. Не всегда разумно требовать 100%-го схождения. Во многих случаях достаточно 90-95% или даже меньших значений. Критерий с использованием времени учитывает также и вычислительную сложность реализации применённых операторов и механизмов ГА. В качестве основного был выбран второй критерий (о его целесообразности см. также в [107]).
В соответствии с этим критерием для популяции определяется максимальное количество вычислений ЦФ К. Тогда количество итераций I алгоритма для популяции размерности N будет 1 = —. Минимальное количество вычислений N функции К, которое должно быть назначено для успешного применения ГА, зависит от функции: чем сложнее функция, тем большим должно быть значение К. При проведении тестирования оптимальный результат (или результаты) определялся заранее, многократным прогоном алгоритма при различных его параметрах.
Для учёта различий в ходе работы ГА, вызванными разными начальными популяциями, в целом вероятностным ходом работы алгоритма, осуществлялся запуск алгоритма с одними и теми же настройками десять раз и фиксировалось количество U 10 успешных запусков ГА. Эффективность ГА измерялась как —. Алгоритм прекращал работу, если было найдено оптимальное решение или если истекало заданное число I итераций; в первом случае фиксировался успех, во втором — неуспех. Для тестирования ГА использовались три тестовые задачи: 1. Реальная задача проектирования (см. п. 4.2). 2. Тестовая задача размерности 5 + 10 (количество модулей плюс количество функций). 3. Тестовая задача размерности 5 + 50.
