Содержание к диссертации
Введение
1. Эволюционное проектирование логических схем ...11
1.1. Эволюционная электроника 11
1.2. Особенности эволюционных алгоритмов 15
1.3. Постановка задачи синтеза комбинационных схем 17
1.4. Основные логические элементы и их полный набор 18
1.5. Анализ методов проектирования комбинационных логических схем 21
1.6. Эволюционные методы проектирования 33
1.7. Выводы 38
2. Особенности эволюционного проектирования комбинационных логических схем 40
2.1. Алгоритм эволюционного проектирования комбинационных логических схем 40
2.2. Особенности системы кодирования комбинационных схем в строку хромосомы 43
2.3. Алгоритм формирования начальной популяции для задачи поиска комбинационных схем 45
2.4. Особенности использования генетических операторов при эволюционном проектировании комбинационных логических схем 47
2.5. Особенности управления эволюционным процессом 50
2.6. Выводы 54
3. Реализация и управление процессом эволюционного поиска 55
3.1. Входные данные 55
3.2. Выбор кандидатов для очередного этапа скрещивания 55
3.3. Функция рекомбинации 61
3.4. Вычисление значения функции пригодности 63
3.5. Критерий завершения процесса 68
3.6. Выходные данные 70
3.7. Выводы 73
4. Экспериментальные исследования 74
4.1. Цель и средства экспериментальных исследований 74
4.2. Сведения об инструментальной среде 75
4.3. Результаты вычислительных экспериментов поведения функций пригодности для различных параметров генетического алгоритма 82
4.4. Сравнение результатов 96
4.5. Экспериментальное исследование возможности творческого проектирования ПО
4.6. Вычислительный эксперимент с промышленными бенчмарками 114
4.7. Выводы 116
Заключение 117
Литература 119
Приложение 1 130
- Постановка задачи синтеза комбинационных схем
- Алгоритм формирования начальной популяции для задачи поиска комбинационных схем
- Выбор кандидатов для очередного этапа скрещивания
- Результаты вычислительных экспериментов поведения функций пригодности для различных параметров генетического алгоритма
Введение к работе
В современных условиях жесткой конкуренции и значительного ускорения темпов технического прогресса необходимо при минимальных сроках проектирования обеспечить высочайшее качество проектируемых изделий большой функциональной сложности. Решение сложных задач проектирования сегодня уже невозможно без применения помощи систем автоматизированного проектирования (САПР). Постоянное усложнение и увеличение задач, решаемых проектировщиком, обуславливает потребность в постоянном развитии САПР, совершенствовании и внедрении накопленных, а также разработке новых методов и средств, способных существенно повысить качество проектирования [1-5].
В области системного и логического проектирования еще очень большая доля работ выполняется не машинной, а проектировщиком, вследствие чего результаты в значительной степени зависят от индивидуальных способностей специалиста. Однако при проектировании больших интегральных схем (БИС) появилась необходимость выполнять за короткий срок точно и безошибочно большой объем работ по логическому проектированию сложного устройства, что в свою очередь вызвало усиление требования автоматизации этого процесса.
Сегодня накопление опыта и сложных форм знаний проектировщика становятся частью основы для подхода к созданию современных полнофункциональных САПР и отдельных модулей САПР, отвечающим всем жестким требованиям. В итоге в настоящее время компьютер в паре с пользователем должен лучше опытного эксперта, проектировщика выполнять всевозможные процедуры проектирования, традиционно относимые к области интеллектуальной деятельности человека. Акад. Г.С. Поспелов писал: «Способность компьютера выдавать творческие результаты - это не что иное, как овеществленные знания в машине и интеллект человека».
БИС обрабатывает данные, представленные в двоичном виде. Поскольку операции, используемые при обработке, описываются как логические функции, средства представления логических функций в БИС являются основой логического проектирования.
Обычно логическая функция реализуется комбинационной схемой. Основу комбинационных схем составляют вентили, реализующие логическую функцию. Конкретная реализация этих вентилей зависит от процесса изготовления и типа схемы.
Известно [6-13], построению комбинационных логических схем предшествует операция получения и упрощения структурной формулы, полученной в свою очередь из функции представленной в виде таблицы состояний. В настоящее время для получения и упрощения структурной формулы используют несколько основных методов. Это диаграммы Карно и метод Квайна - Мак-Класски.
Оба метода механически по своей структуре. Диаграммы Карно возможно использовать для минимизации функций содержащих до пяти-шести переменных. Метод Квайна - Мак-Класски возможно использовать для функций с любым количеством элементов, и притом его легко реализовать программно.
Оба метода, и карты Карно, и процедура Квайна - Мак-Класски, разрешают получить двухуровневые схемы. Заметим, что наилучшим решением является комбинационная схема с минимальной задержкой прохождения сигналов в ней. Тем не менее, довольно часто требуется получить минимизацию количества логических элементов в схеме, при этом, не утратив скорости прохождения сигналов. Для минимизации количества логических элементов часто необходимо получить многоуровневую комбинационную схему. Поэтому совместно с методами Карно и Квайна - Мак-Класски используют различные алгебраические манипуляции над логическими выражениями. Помимо этого метод Квайна - Мак-Класски не эффективен в смысле минимизации вычислительных
затрат. Верхняя граница количества основных операций равна —, где п -
количество входящих элементов в таблице истинности. Это означает, что вычислительные затраты для реализации этого метода растут экспоненциально с количеством входов таблицы истинности. Также этот метод накладывает ограничение на используемые логические элементы в схемах: доступны только основные -элементы, такие как: AND, OR, NOT. Для использования элементов XOR приходится генерировать решение опытному эксперту [6].
В связи с этим возникает необходимость построения таких методов поиска комбинационных схем, которые были бы способны отыскивать решения при практически полном отсутствии предположений о характере исследуемой функции. Этим требованиям в значительной степени удовлетворяют эволюционные вычисления, которые представляют собой алгоритмы поиска, оптимизации или обучения, основанных на некоторых формализованных принципах естественного эволюционного процесса развития живых организмов.
Использование эволюционных .вычислений для нахождения решений в различных задачах является одним из альтернативных путей повышения интеллектуальности систем проектирования. Способность эволюционных алгоритмов к нахождению нестандартных и неожиданных решений подтверждается результатами большого числа исследований [14-25].
В настоящее время эти алгоритмы находят всё более широкое применение в силу своей способности решать слабо формализованные задачи. Это область задач на сегодняшний день требует интуитивных знаний о предмете проектирования и решается с привлечением экспертов для каждой конкретной задачи отдельно, где нет сформулированных, чётких правил, что изменение какого-либо параметра приведёт к определенным последствиям, что фактически, и соответствует задаче получение комбинационной схемы из таблицы истинности.
Цель диссертационной работы заключается в разработке и исследовании методов и алгоритмов, обладающих малой трудоемкостью и обеспечивающих гарантированное качество при решении задач синтеза комбинационных логических схем на основе эволюционного подхода.
Для достижения поставленной цели были решены следующие основные задачи:
1. Разработаны и исследованы алгоритмы синтеза комбинационных
логических схем на основе эволюционного подхода.
2. Разработан и исследован принцип кодирования, хранения и
" модификации альтернативных решении на различных этапах синтеза
комбинационных логических схем.
Разработаны модифицированные генетические операторы, ориентированные на задачу синтеза комбинационных схем.
Найден метод оценки качества получаемых альтернативных решений.
Разработан комплекс программ эволюционного проектирования на основе предложенных алгоритмов.
Методы исследования. Методы исследования основаны на теории алгоритмов, алгоритмах эволюционных вычислений.
Научная новизна заключается в следующем:
Сформулированы принципы, стратегии и методы синтеза комбинационных схем на основе эволюционного подхода.
Разработан генетический алгоритм синтеза комбинационных логических схем.
Разработана методика перехода от генотипа к фенотипу при синтезе комбинационных логических схем.
4. Построены модифицированные операторы генетического поиска, ориентированные на задачу синтеза комбинационных логических схем.
Практическую ценность представляют:
Практическая ценность результатов диссертационной работы определяется созданием комплекса алгоритмов синтеза комбинационных схем, позволяющих использовать разработанные методы, отвечающие конкретным задачам САПР. Алгоритмы реализованы на языке С# под ОС
ГА)
- Windows. Проведенные экспериментальные исследования, показали
преимущество предложенных алгоритмов и методик для решения задачи синтеза комбинационных схем, по сравнению с известными методами. Разработанные алгоритмы позволяют получать набор оптимальных решений. Время получения лучших результатов работы алгоритмов, соответствует полиномиальному времени 0(п), которое требуют эффективные итерационные алгоритмы.
Реализация результатов работы.
Основные теоретические и практические результаты
диссертационной работы использованы в госбюджетной работе №12353
«Разработка теории и принципов построения интеллектуальных систем
автоматизированного проектирования на основе эволюционной адаптации
нейросетевых моделей и методов принятия решений», а также в научно-
т исследовательской работе №12388 по теме «Разработка теорем и
принципов принятия решений при разбиении сложных математических объектов на части на основе моделирования эволюции и фрактальных множеств».
Материалы диссертации были использованы в лабораторных, практических работах и при чтении следующих курсов на кафедре САПР
ТРТУ: «Математическая логика и теория алгоритмов», «Эволюционное моделирование и генетические алгоритмы».
Внедрение в учебный процесс ряда теоретических и практических результатов диссертационной работы позволило повысить качество подготовки специалистов в области проектирования САПР и информационных технологий.
Публикации. По теме диссертации опубликовано 6 печатных работ.
Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 129 стр., 57 рис., 24 табл., список литературы из 112 наименований, 30 стр. приложений и актов об использовании.
Во ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, сформулированы цели, приведены сведения о полученных научных и практических результатах, реализации и внедрении результатов работы, апробации, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ дано определение эволюционной электроники, приведена постановка задачи синтеза комбинационных логических схем. Произведен анализ существующих методов синтеза комбинационных логических схем.
Во ВТОРОЙ ГЛАВЕ рассматриваются методы эволюционного проектирования комбинационных логических схем. Предложена методика кодирования решений, позволяющая учитывать специфику решаемой задачи. Рассмотрен модифицированный алгоритм формирования начальной популяции. Рассмотрены особенности использования генетических операторов при эволюционном проектировании комбинационных логических схем.
':
В ТРЕТЬЕЙ ГЛАВЕ рассмотрен алгоритм выбора кандидатов на очередной этап скрещивания, рассмотрен пример работы алгоритма.
Разработан алгоритм функции рекомбинации. Предложен алгоритм
вычисления целевой функции, который включает в себя разработанный
алгоритм нахождения дерева внутри матрицы пространства поиска
решения. Определены основные критерии останова поиска. Показана
на примерах, информативность выходных данных после работы предложенных алгоритмов.
В ЧЕТВЕРТОЙ ГЛАВЕ приведены результаты экспериментальных исследований. Описаны функциональные особенности программных средств, реализующих синтез комбинационных схем на основе предложенных алгоритмов, методик и подходов. Поставлены цели экспериментальных исследований. Проведены серии экспериментов для определения оптимальных параметров алгоритма. Выполнено сравнение предложенного подхода с известными наборами тестовых данных. По результатам исследований определены оптимальные управляющие параметры для алгоритмов.
В ЗАКЛЮЧЕНИИ приведены основные результаты, полученные в диссертационной работе.
В ПРИЛОЖЕНИИ приведены акты об использовании результатов диссертационной работы.
Постановка задачи синтеза комбинационных схем
Постановка задачи синтеза комбинационных схем описана кортежем: Х, D, Q , где X - является множеством всех решений, D -ограничения, накладываемые на множество X для получения допустимых решений и Q - целевая функция (ЦФ), с помощью которой можно определить наилучшее (оптимальное) решение [31-33]. Здесь X -множество всех возможных хромосом в популяции. Эти хромосомы могут быть нерелевантными, т.е. кодировать в себе недопустимые решения, или решения, не приводящие ни к какому результату. Обозначим популяцию на шаге ГА t как Pt, а хромосому с номером / - ht. Тогда можно записать, что популяция на шаге t Pt ={hit ... ,hnj, где t-[l,TJ, n=[l,N], T - количество итераций ГА и N - количество хромосом в популяции. Параметр Т может варьироваться в заданных пределах. Тогда X можно записать в следующей форме:
Решение представляется в виде неоднородной хромосомы. Исходя из этого условия, каждый ген может приминать только ограниченное количество значений, чтобы удовлетворять условию hczK, т.е. принадлежать области допустимых решений. Для генов, кодирующих номера входов это значения от 1 до к, где к - количество строк матрицы в которой осуществляется поиск решения. Для гена, кодирующего логический элемент, это значения от 1 до 5 (номера возможных логических элементов).
Целевая функция является многопараметрической. Во-первых она зависит от количества логических элементов. Второй составляющей целевой функции является количество связей (WIRE). Целевая функция описывается в следующем виде: количество логических элементов в альтернативном решении; Q2 представляет собой количество связей между логическими элементами в альтернативном решении.
Оптимизация задачи синтеза комбинационных схем сводится к минимизации критерия Q, т.е. Q(X) — min.
В БИС в качестве основных элементов используются несколько базовых вентилей, реализующих логические функции. Конкретная реализация этих вентилей зависит от процесса изготовления и типа схемы. Основные типы вентилей с точки зрения логических функций представлены в табл. 1.2.
В таблице наряду с названием логического элемента и логическим символом приведена его функция в виде логического выражения. Следует обратить внимание на то, что кружок означает логическое отрицание (дополнение). Три типа логических схем — И, ИЛИ, НЕ, — представленные в табл. 1.2, соответствуют операциям булевой алгебры — умножению, сложению и дополнению. С точки зрения возможности реализации произвольной логической функции эти три типа элементов образуют полный набор. Как следует из рис. 1.1, используя только элементы И и НЕ, можно получить элемент ИЛИ, поэтому сами по себе элементы И и НЕ составляют полный набор.
Тождественность схем, показанная на рис. 1.1, легко выводится из законов де Моргана [34-36]. Аналогично с помощью элементов ИЛИ и НЕ можно получить элемент И, поэтому одни только элементы ИЛИ и НЕ также образуют полный набор.
На рис. 1.2 показан способ формирования элементов И-НЕ (ДЛИНЕ) с помощью элемента ИЛИ-НЕ (И-НЕ). Если учесть, что элемент НЕ является особым случаем элемента И-НЕ и ИЛИ-НЕ (с одним входом), то, применяя только элементы И-НЕ, ИЛИ-НЕ, можно соответственно легко получить элементы И и ИЛИ, поэтому элементы И-НЕ и ИЛИ-НЕ сами по себе являются полными наборами.
Этот элемент характеризуется тем, что если на один из его входов подать 1, то выход принимает также значение 1. Только на одних элементах ИСКЛЮЧАЮЩЕЕ ИЛИ нельзя реализовать логическое произведение, поэтому этот элемент не может составлять полный набор, однако, полный набор можно получить объединением элементов И и ИСКЛЮЧАЮЩЕЕ ИЛИ. Далее, если на одном из входов элемента ИСКЛЮЧАЮЩЕЕ ИЛИ зафиксировать 1, то можно реализовать элемент НЕ, а принимая во внимание тождественность, показанную на рис. 1.1, можно получить полный набор путем объединения элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и ИЛИ. Элемент ИСКЛЮЧАЮЩЕЕ ИЛИ часто реализуется в виде сложного элемента с использованием элементов типа И-НЕ, как видно из рис. 1.3.
Однако операция исключающей логической суммы может быть реализована и на одном элементе, поэтому этот элемент и включен в число базовых логических элементов.
Учитывая тождественность схем, показанную на рис. 1.1 и рис. 1.2, можно, как следует из табл. 1.2, использовать различные символы для вентилей даже с одной и той же логической функцией. Кружок, означающий отрицание, в табл. 1.2 используется не только на входе, но и » на выходе вентиля. Таким образом, этот символ можно расценивать просто как логический элемент НЕ. Далее, как следует из табл. 1.2, разница между элементами И и ИЛИ заключается лишь в том, какой реальной физической величине соответствует 1 и 0. Обычно представление, при котором 1 соответствует физически большей величине, называется положительной логикой, а представление с противоположным соответствием называется отрицательной логикой. В этом смысле элементы И и НЕ-И положительной логики в отрицательной логике оказываются элементами ИЛИ и НЕ-ИЛИ. Это обусловлено двойственностью логики.
Алгоритм формирования начальной популяции для задачи поиска комбинационных схем
Для начала создания популяции должны быть определены типы элементов (табл.2.1), которые могут присутствовать в схеме, размер популяции, а также размерность матрицы (рис.2.2), в пространстве которой необходимо будет найти решение. Каждая хромосома популяции состоит их генов - триплетов, информация в триплеты заносится случайным образом на основании данных указанных выше. Для генерации каждого члена первой популяции необходимо выполнить следующие действия: 1. Узнать какие логические элементы могут присутствовать в будущей логической схеме. 2. Получить количество входов в таблице истинности 3. Получить размерность матрицы т, в которой будет осуществляться поиск решения 4. Для каждого элемента матрицы m[i,j] выполнить генерацию триплета на основании данных полученных в пунктах 1 и 2. Пример работы алгоритма генерации "члена начальной популяции" для таблицы истинности (табл.2.2) показан на рис.2.6. Мутации представляют собой процесс изменения содержания генов в хромосоме особи. Мутации формируют новый генетический материал и таким образом вводят в набор решений, заданных начальной популяцией, радикально отличающиеся решения. Оператор кроссинговера не способен выполнять эту функцию, так как он обладает свойствами преемственности только уже существующей наследственной информации. Мутация же, напротив, формирует гены, отсутствовавшие в начальной популяции или удалённые из популяции во время процесса селекции. Эти новые гены придают генофонду необходимое разнообразие, позволяют расширить поле поиска оптимума, ускорить его получение, а в ряде случаев сделать его вообще возможным, так как не все элементы оптимума могут присутствовать в начальном наборе решений [82, 83]. Оператор мутации является случайным в том смысле, что не зависит ни от гена, содержащегося в хромосоме, ни от количественных значений фенотипа особи и её степени приспособленности, поэтому оператор рулетки не может быть применён для выбора кандидата при проведении процедуры мутации.
Процедура модифицированного оператора мутации производится по следующему алгоритму: 1. Генерируется случайное число ТМ, равномерно распределённое в интервале [0;п], где п - число триплетов в хромосоме; 2. Триплет с индексом ТМ полностью заменяется на новый, случайно сгенерированный. Пример работы модифицированного оператора мутации показан рисунке 2.7. Оператор кроссинговера является основным генетическим оператором, именно он определяет наследственность информации в ГА. Кроссинговер производит структурированный и рандомизированный обмен информацией между различными вариантами решений (индивидами). Качество решения, полученного ГА в высокой степени зависит от типа используемого оператора кроссинговера.
В данном алгоритме применяется на выбор одноточечный или двухточечный оператор кроссинговера [68, 82]. Алгоритм работы двухточечного оператора кроссинговера можно представить следующим образом: 1. Генерируется случайное число ТК1 (первая точка кроссинговера), равномерно распределённое в интервале [0;п-1], где п - число генов в хромосоме; 2. Генерируется случайное число ТК2, равномерно распределённое на интервале [1;п], где п - число генов в хромосоме; 3. Определяется вторая точка кроссинговера: if ((ТК2+=ТК1) п) ТК2=п; 4. Создание матрицы соответствия на основе интервала [ТК1;ТК2] хромосом родительской пары А и В; 5. Получение пары потомков А и В на основе матрицы соответствия. Пример работы модифицированного оператора кроссинговера показан на рисунке 2.8. Общая схема работы генетических операторов показана на рисунке 2.9. 2.5. Особенности управления эволюционным процессом Существует ряд параметров, определяющих ход, скорость и направление эволюционного процесса [91, 92]. К ним относятся размер популяции, генетическое давление и репродукция.
Размер популяции задается в начале эволюционного процесса. Если размер популяции мал, то скорость эволюционного процесса велика, но при этом мала вероятность того, что в начальной популяции альтернативных решений будут такие, которые могут быть использованы для эффективного поискового процесса. Если размер популяции велик, то вероятность наличия в начальной популяции решений, пригодных для организации поискового процесса, повышается.
Выбор кандидатов для очередного этапа скрещивания
При использовании генетических алгоритмов элементы популяции потомков могут полностью или частично замещать популяцию родительских элементов на каждом шаге формирования популяции альтернативных решений. Обычно при выборе элементов популяции, подлежащих замещению, используются методы селекции, опирающиеся на оценку пригодности конкретного альтернативного решения для удовлетворения проектных требований. При этом альтернативные решения могут выбираться из популяции методом голосования. В этом случае любой элемент популяции может выбираться многократно, однако элементы, лучше удовлетворяющие проектным требованиям, имеют более высокую вероятность быть выбранными в качестве родителей для последующей репродукции [95]. В качестве альтернативы методу голосования может проводиться сортировка имеющейся популяции альтернативных решений и только лучшие из них допускаются к репродукции. Когда группа элитных решений определена, каждый ее элемент может быть использован для формирования потомков.
В случае нахождения хорошего технического решения при использовании любого из указанных типов селекции, оно может быть утеряно, если вся популяция альтернативных решений заменяется популяцией потомков. Если одно и то же альтернативное решение оказывается в различных поколениях, то это означает, что оно было найдено вновь, а не выжило в процессе эволюционного отбора.
Методы селекции, основанные на использовании элитизма, копируют один или несколько наилучших элементов популяции альтернативных решений в новую популяцию и эти клонированные копии не являются объектами для дальнейших операций [96]. В данном селекционном процессе хромосомы сортируются в соответствии с пригодностью альтернативных решений, и один или несколько элементов популяции сохраняются. В методе генитора [97] только единственное альтернативное решение, имеющее наихудшую пригодность, подвергается замене при каждом формировании нового поколения. Между этими двумя экстремальными методами селекции находятся методы селекции, позволяющие заменить только часть популяции, к примеру, нижнюю половину списка альтернативных решений, при каждом формировании новой популяции. При использовании любого из этих методов селекции найденное лучшее альтернативное решение не будет потеряно, поскольку оно в любом случае будет скопировано в новую популяцию. Это приводит к частичному перекрытию популяций решений, которые содержат идентичные альтернативные решения, поскольку альтернативные решения, копируемые в новую популяцию, не подвергаются в ней изменениям. Эта задержка лучших альтернативных решений в популяции приводит к более гладким изменениям средней величины функции пригодности в популяции.
Отбор альтернативных решений для последующей репродукции может быть организован различными методами. В работе [60] рассмотрены следующие шесть схем селекции: детерминированная селекция. Вероятность выбора из популяции элемента с номером / вычисляется как отношение значения функции пригодности этого элемента к сумме значений функций пригодности всех элементов популяции: где N- число элементов в популяции. Тогда ожидаемое число потомков для каждого альтернативного решения вычисляется следующим образом: К{=РД. Согласно процентному отношению ожидаемого числа потомков для каждого альтернативного решения вся популяция сортируется в порядке убывания ожидаемого числа потомков. остаточная стохастическая схема без перемещения. В этом методе селекции также рассчитывается ожидаемое число потомков (3.1), но в этом случае используется вероятностный подход: каждый элемент популяции может дать потомство с вероятностью Kj. После броска монеты к репродукции допускаются элементы для которых отбор был успешным; остаточная стохастическая схема с перемещением; стохастическая схема с перемещением (обыкновенная рулетка); стохастические схемы без перемещения; стохастическая турнирная схема. Вероятность селекции вычисляется по стандартной схеме. Лучшие пары выбираются на основе рулетки.
Затем в каждой паре альтернативное решение с лучшим значением функции пригодности объявляется победителем и переходит в новую популяцию.
Наиболее простым из перечисленных выше методов селекции является отбор на основе колеса рулетки [60, 83, 84, 95]. В данной работе для выбора кандидатов на очередной этап используется именно этот метод, как наиболее полно выражающий процесс естественного отбора. В этом методе выбор очередного варианта осуществляется стохастически, но вероятность назначения того или иного варианта находится в прямой зависимости от значения целевой функции.
Его работа организована следующим образом. Для каждого элемента популяции альтернативных решений вычисляется значение целевой функции. Затем колесо рулетки разбивается на сектора, количество которых равно числу элементов популяции альтернативных решений. Площадь каждого сектора пропорциональна отношению величины функции пригодности данного элемента к суммарному значению функций пригодности всех элементов популяции. Очевидно, что чем больше величина этого отношения, тем больше площадь соответствующего ему сектора на колесе рулетки.
Результаты вычислительных экспериментов поведения функций пригодности для различных параметров генетического алгоритма
Рассмотрим влияние размера популяции на скорость нахождения решения. Размер популяции является основополагающим параметром генетического алгоритма: выбор малого размера популяции может привести к невозможности нахождения решения, поскольку не будет достигнуто разнообразие популяции; выбор большого размера популяции может привести к невозможности окончания работы алгоритма за заданное время. Для этого установим и зафиксируем следующие параметры: количество итераций, вероятность оператора мутации и вероятность оператора кроссинговера. В вычислительном эксперименте полагалось, что количество итераций эволюционного процесса равно ста пятидесяти, вероятность мутации - двадцать пять процентов, оператора кроссинговера - пятьдесят процентов, размерность матрицы пространства поиска решения - три. Начнем эксперимент с размером популяции равным ста. После каждой итерации будем наращивать размер популяции на сто хромосом.
Мы произвели двадцать запусков генетического алгоритма, полученные данные показаны в таблице и обобщены графиком.
Анализ полученных экспериментальных результатов показывает, что при увеличении размера популяции время нахождения решения вначале уменьшается, достигая минимального значения при размере популяции 1300 альтернативных решений, и затем вновь увеличивается. Полученные данные позволяют сделать вывод о том, что при размерах популяции порядка 1000-1400 хромосом, поиск решения занимает наименьшее время, так как разнообразие популяции близко к оптимуму. Увеличение размера популяции приводит к увеличению времени поиска решения, поскольку пространство для работы оператора селекции становится слишком велико и при применении функции рекомбинации в популяции сохраняются решения со значением функции пригодности ниже требуемой.
Рассмотрим далее влияние величины вероятности мутации на время нахождения решения. Для этого размер популяции альтернативных решений был установлен в 1200 особей. Количество генераций - 150. Вероятность оператора кроссинговера установим равной 50%. Проведем вычислительный эксперимент для случайной и жесткой генерации выходов искомой логической схемы. Результаты расчетов, зависимости времени нахождения решения от вероятности мутации, показаны на рис. 4.7.
Анализ данных, представленных на рис. 4.7 показывает, что зависимость времени нахождения решения от вероятности мутации является немонотонной функцией. Показано, что наиболее эффективной является мутация со значением порядка 45-75 процентов. Увеличение вероятности мутации начинает сопровождаться увеличением времени поиска решения. Меньшее значение вероятности мутации, заранее влечет к длительному поиску решения.
Таким образом, было установлено, что вероятность мутации существенно влияет на скорость эволюционного процесса. При вероятности мутации, меньше 45%, она практически не оказывает влияния на эволюционный процесс и количество итераций, необходимых для получения приемлемых решений, резко возрастает. Вероятность мутации, большая 75% начинает приводить к разрушению популяции решений. Это объясняется тем, что при чрезмерном увеличении вероятности мутации в популяции потомков уменьшается доля альтернативных решений, представляющих интерес с точки зрения удовлетворения проектным требованиям и процесс эволюционного поиска заходит в тупик.
Рассмотрим далее свойства алгоритма эволюционного проектирования, использующего оператор двухточечного кроссинговера. Исследуем влияние изменения вероятности оператора кроссинговера на время поиска приемлемого решения. Для этого установим размер популяции альтернативных решений в 1200 особей. Количество генераций - 150. Вероятность оператора мутации установим равной 45%. Проведем вычислительный эксперимент для случайной и жесткой генерации выходов искомой логической схемы. Результаты расчетов, зависимости времени нахождения решения от вероятности применения оператора кроссинговера, показаны на рис. 4.8.
Анализ данных, представленных на рис. 4.8 показывает, что наиболее эффективным является использование оператора кроссинговера с вероятностью порядка 45-70 процентов. Увеличение вероятности использования оператора кроссинговера вызывает резкое увеличение времени поиска решения. При установке меньшего значения, также увеличивается время поиска, но не значительно. Таким образом, было установлено, что вероятность оператора кроссинговера влияет на скорость эволюционного процесса. При вероятности мутации, больше 70%, она практически не оказывает влияния на эволюционный процесс и количество итераций, необходимых для получения приемлемых решений, резко возрастает. Это объясняется тем, что при чрезмерном увеличении вероятности оператора кроссинговера в популяции потомков происходит разрушение альтернативных решений, представляющих интерес с точки зрения удовлетворения проектным требованиям и процесс эволюционного поиска заходит в тупик.
Рассмотрим теперь влияние размерности матрицы пространства поиска решения на скорость нахождения решения. Для этого установим размер популяции альтернативных решений в 1200 особей. Количество генераций - 150. Вероятность оператора мутации установим равной 45%. Вероятность оператора кроссинговера - 35%. Начнем вычислительный эксперимент с размерности матрицы равным трем. После каждого нахождения решения, в заданном пространстве, будем увеличивать размерность матрицы на единицу. Результаты расчетов, зависимости времени нахождения решения от пространства поиска схемы внутри матрицы, показаны на рис. 4.9.
