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

На правах рукописи

Голубин Алексей Владимирович

РАЗРАБОТКА ГИБРИДНЫХ ИНТЕЛЛЕКТУАЛЬНЫХ МОДЕЛЕЙ ЭВОЛЮЦИОННОГО ПРОЕКТИРОВАНИЯ

Специальности: 05.13.12 - Системы автоматизации проектирования 05.13.17 - Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва - Таганрог - 2006

Диссертация выполнена в Московском государственном техническом университете им. Н.Э.Баумана и Таганрогском государственном радиотехническом университете.

Научный руководитель: кандидат технических наук, доцент В.Б.Тарасов

Научный консультант: кандидат технических наук, доцент Л.А.Гладков

Официальные оппоненты: доктор технических наук, профессор С.М. Ковалев кандидат технических наук, доцент С.И.Родзин

Ведущая организация: ГУ РосНИИ информационных технологий и систем

Защита состоится «» августа 2006 г. в 1422 часов на заседании диссертационного совета Д 212.259.03 по защите диссертаций при Таганрогском Государственном Радиотехническом Университете по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в библиотеке Таганрогского государственного радиотехнического университета.

Автореферат разослан «£& » июля 2006 г.

автоматизированного проектирования, г. Москва

диссертационного доктор технически

Ученый секретарь

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

1. Анализ и разработка теоретических вопросов эволюционного проектирования. Реализация эволюционного проектирования с помощью эволюционных алгоритмов.

2. Исследование способов построения эволюционных алгоритмов на основе недарвиновских моделей эволюции.

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

4. Разработка способов автоматического подбора параметров и методов самоадаптащш эволюционного алгоритма под решаемую задачу.

5. Разработка алгоритма решения задачи комплексной организации управления запасами при оптимизации раскроя ленточного материала.

6. Создание программного обеспечения, реализующего разработанные алгоритмы.

7. Применение разработанного программного обеспечения для решения прикладных оптимизационных задач.

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

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

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

Внедрение и реа ш шцин результатов.

Теоретические и практические результаты, полученные в диссертационной работе, применялись при выполнении хоздоговорной тематики Отдела «Компьютерные системы автоматизации» НУК PIC МГТУ им. Н.Э.Баумана. Результаты диссертации также использованы при выполнении работ по грантам Российского фонда фундаментальных исследований (проекты №02-01-00784, 03-07-90012, 04-01-00306, 05-0100514).

Результаты исследований, проведенных в диссертационной работе, были внедрены на «ОАО Коломенский завод РТИ». Кроме того, результаты работы нашли применение в учебном процессе кафедры «Компьютерные системы автоматизации производства» МГТУ им. Н.Э.Баумана и кафедры САПР ТР'ГУ.

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

Апробация работы. Основные результаты работы докладывались на: Пятом международном симпозиуме «Интеллектуальные системы» (INTELS'2002, Калуга, 2002г.), Научных сессиях МИФИ-2003 и МИФИ-2005 (Москва, 2003г. и 2005г.), Международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке, технике и экономике - Ю1ИН-2003» (Ульяновск, 2003г.), Третьей международной научно-технической конференции «Измерение, контроль, информатизация» (Барнаул, 2003г.), Региональной студенческой конференции «Применение кибернетических методов в решении проблем общества XXI века» (Обнинск, 2003г.), IX-й Национальной

конференции по искусственному интеллекту с международным участием (КИИ-2004, Тверь, 2004г.), Международных научно-технических конференциях IEEE AIS'04 и CAD-2004 (Дивноморское, 2004г.), Ш-м Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2005г.), Международных научно-технических конференциях IEEE AIS'05 и CAD-2005 (Дивноморское, 2005г.).

Публикации. По теме диссертации автором опубликовано 16 работ, имеется авторское свидетельство об официальной регистрации программы для ЭВМ (Роспатент).

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и двух приложений. Объем диссертации составляет 175 страниц, в том числе 29 рисунков и 16 таблиц. Список литературы содержит 173 библиографических наименования.

На защиту выносятся:

1. Архитектура эволюционных алгоритмов на основе не дарвиновских моделей эволюции.

2. Архитектуры гибридных систем на основе эволюционных алгоритмов и нечеткой лотки.

3. Метод автоматического подбора параметров и адаптации параметров эволюционного алгоритма на основе баз знаний.

4. Архитектура инструментальной среды поддержки эволюционного проектирования.

5. Алгоритм решения задачи комплексной организации управления запасами при оптимизации раскроя ленточного материала.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе «Анализ проблем, перспектив и методов эволюционного проектирования» приводится постановка задач исследования и обзор методов их решения. Рассматриваются актуальные проблемы разработки САПР, варианты реализации ЭП и способы повышения его эффективности.

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

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

ЕВ - (Е, К, О, О),

где £ - множество моделей эволюции; А" - множество критериев ЭП; О -множество объектов ЭП; О - множество процедур ЭП.

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

С целью развития методов и технологий эволюционного моделирования в работе дан краткий обзор как основных эволюционных учений (ламаркизм, дарвинизм, сальтационизм, синтетическая теория эволюции), так и ряда современных направлений эволюционной теории (финализм, номогенез, симгенез, симбиогенез, информационная и экосистемная концепции эволюции, синтез макро- и микроэволюционных воззрений). В работе проведен обзор основных подходов к моделированию эволюции в информатике, а также описаны важнейшие понятия генетики, применяемые в информатике и принципы работы генетических алгоритмов (ГА), генетического программирования (ГП), эволюционных стратегий (ЭС), эволюционного программирования (ЭП). Значительный вклад в развитие эволюционного моделирования и генетических алгоритмов внесли: Дж.Холланд, Л.Дэйвис, Д.Голдберг, Д.Фогель, Д.И.Батищев, И.Л.Букатова, В.В.Емельянов, В.М.Курейчик, И.П.Норенков и др. В результате анализа эволюционных алгоритмов (ЭА) было выявлено, что ЭА на основе эволюции Дарвина являются «полуслепыми»: мутации малы и носят стохастический характер, кроссинговер является случайной рекомбинацией двух или более решений. В данном случае при создании нового индивида практически не используются знания предыдущих поколений, по сути, эволюция осуществляется методом проб и ошибок, запущенным параллельно.

В работе проводится обзор текущего состояния применения недарвиновских моделей эволюции при разработке генетических алгоритмов. На основе данного обзора отмечается, что построение ГА на основе моделей эволюций Ламарка и «эффекта Болдуина» позволяет устранить ряд недостатков ГА, повысив его эффективность в различные моменты генетического поиска. Также замечено, что в настоящее время в практике используется чрезвычайно узкий класс моделей эволюции и/или только отдельные элементы этих моделей. В результате делается вывод о необходимости расширения списка моделей эволюции, применяемых в ГА. Однако подчеркивается, что ни один ГА, основанный на различных моделях эволюции, не лишен недостатков. Как правило, в зависимости от применяемой модели эволюции, мы получаем выигрыш по одним параметрам и ухудшение по другим.

Одной из ведущих тенденций, определяющей развитие теоретических основ современной информатики в целом и алгоритмов эволюционного проектирования в частности стало распространение интегрированных и гибридных систем. Гибридные интеллектуальные системы рассматривались в работах А.В.Гаврилова, П.Джексона, А.П.Еремеева, A.B.Колесникова, Л.Г.Комарцовой, О.П.Кузнецова, Дж.Люгера, Л.Медскера, Г.С.Осипова, Э.В.Попова, С.И.Родзина,

Г'.В.Рыбиной, В.Б.Тарасова, И.Б.Фоминых, Н.Г.Ярушкиной и др. В настоящей работе введены понятия «внутренней» и «внешней» гибридизации. В частности, выдвинуто предположение, что построение гибридных ГА на основе различных моделей эволюции («внутренняя гибридизация») позволит получить синергетический эффект, т.е. компенсировать недостатки и усилить достоинства отдельных моделей эволюции. В последние годы такие гибридные алгоритмы получили широкое распространение только в отношении использования моделей эволюции Дарвина, Ламарка и Де Фриза, а также «эффекта Болдуина». Кроме того, проведенный обзор показал, что ГА обладает рядом недостатков, которые не могут быть устранены в рамках применения только эволюционных подходов. Поэтому в диссертации рассматриваются варианты использования разнородных методов и построения гибридных систем на их основе («внешняя гибридизация»), позволяющие обойти недостатки, присущие каждому из них в отдельности.

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

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

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

1. Построение эволюционных и генетических алгоритмов на основе недарвиновских моделей эволюции.

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

3. Разработка инструментальной среды, поддерживающей ЭП.

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

Формально генетический алгоритм можно описать в виде: ГА = (Р°, Е, Л, /, Л р./. I), где Р° = (а0/, ..., а°я) - исходная популяция; а", - решение задачи, представленное в виде хромосомы; Е - модели эволюции; Л — целое число (размер популяции); / -целое число (длина каждой хромосомы популяции); 5 - оператор отбора; р — отображение, определяющее рекомбинацию (кроссинговер, мутация); /— функция пригодности; г — критерий останова.

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

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

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

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

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

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

Для построения ГА на основе недарвиновских моделей эволюции во второй главе рассмотрены способы реализации основных генетических операторов при различных моделях эволюции:

• ламаркизм - создание потомка с помощью локальных методов;

• финализм - наличие цели (срока жизни) у каждого индивида, кодирование параметров внутри хромосомы;

• сальтационизм — макромутации в хромосоме, межвидовая селекция;

• симгенез - межвидовая гибридизация, межвидовой выбор родительской пары;

• номогенез - применение ГО без использования случайных процессов;

• экосистемная модель эволюции - проведение «экологических революций» в популяции;

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

• " синтез макро- и микроэволюционных воззрений - управление

несколькими популяциями.

В главе I было показано, что ни один из ГА, основанных на различных теориях эволюции, не лишен недостатков. Многие рассмотренные теории эволюции не являются законченными, поэтому совместное, использование нескольких теорий является необходимым. Предлагаемый в работе способ построения ГА на основе различных моделей эволюции состоит в рассмотрении ГА как иерархической

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

Рис. 1. Структура многоэволюционного ГА

На уровне популяций рассматриваются способы взаимодействия между популяциями при генетическом поиске. Каждая популяция может содержать в себе один или несколько видов хромосом и иметь свой набор параметров, который не зависит от других популяций. Взаимодействие популяций производится путем миграции особей на базе макроэволюции. В остальном, популяции выступают по отношению друг к другу к&к внешняя среда. Если в популяции содержатся хромосомы нескольких видов, то их поведение определяется одной из следующих теорий эволюций: сальтационизм, симгенез, экосистемная теория эволюции (ЭТЭ). Отметим, что ЭТЭ может использоваться одновременно с сальтационизмом и симгенезом. На уровне индивидов используются теории Ламарка, финализма, сальтационизма, СТЭ. Отметим, что выбранная теория эволюции уровня вида влияет и на уровень хромосом.

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

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

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

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

Генерация начальных популяций

I

Расчет функции пригодности

ЗЕ

Создание родительских пар

Все пары

—-^исспедованы?^--^

Нечеткая мутация и другие 5 Определение вероятности

генетические операторы кроссинговера с помощью

* правил БЗ

Расчет функции пригодности

Отбор

Нечеткий кроссинговер

Расчет основных статистических

параметров популяции *

Изменение параметров популяции с помощью правил БЗ

Рис. 2. Структурная схема нечеткого генетического алгоритма

В работе описаны нечеткие генетические операторы - нечеткий кроссинговер и нечеткая мутация, основанные на использовании элементов нечеткой логики.

Для определения нечеткого кроссинговера опишем 4 семейства функций: F, S, М+ и М~. Рассмотрим два гена с, е [а, Ь] и с2 е [а, Ь], подвергающихся рекомбинации.

Обозначим ои = min{ci, с2}, Р = шах{сь с2}; gmM - максимальное количество поколений в ГА; t —номер текущего поколения : 1 £t<gmax-l.

F = (FJ, .... Л*""*), 5 = (S!.....S*"ar), М = (Л/'.....AT""),

Vс, с' е [а, А]: /'(с, с')< с'), (с. с') — minie, с').

Vc, с' е [а, 6]: У(с, с')> с'), ^"""(с, с') -* тах(с, с').

Vс, с' е[а, Ь): Л/(с, с') > Л/~'(с, с'), V?. Л/""1*(с, с') — МИт{с, с'). Такую функцию будем называть М .

Vс, с' е [а, Ь]: М(с, с')< с'). V/, Af™"*(с, с') Mt,Jc, с').

Такую функцию будем называть ЛГ (см. рис.3).

М™ - «редел функции М, M!im =

Рис. 3. Направление функций Р, в, М+, М

Семейство функций Р и 5 могут быть определены с использованием параметризированной треугольной нормы Т4, сходящейся к минимуму, и параметризированной треугольной конормы С74, сходящейся к максимуму, соответственно. Семейство функций М определяются на основе параметризированного оператора осреднения.

Пусть есть две хромосомы С/ = (с/', с21'.. с„") и С2' = (с,2', с22'.. сп2'), выбранные на поколении I для операции кроссинговера, и хромосома С* обладает лучшей функцией пригодности по сравнению с С2\ Тогда, если О' является 1-й функцией, принадлежащей семейству функцией Р, 8 или М, то генерацию потомка // = (Л,1, А2' .. Л„') можно выразить формулой: /¡¡' = 0'(С1И> с,2')> 1 =1,...,п. Если использовать в качестве функции О' функцию из семейства И, 5 или М, то получим соответственно Р-, 5- или М-кроссинговер. Применяя различные виды треугольных норм и конорм, мы можем получать различные виды оператора кроссинговера.

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

материал. Для ее реализации предлагается нечеткий эвристический кроссинговер.

г

Введем обозначение: Х-——1—, где/! - значения ФП хромосом С] и А + Л

С2'. Гены потомков, создаваемые нечетким эвристическим кроссинговером, являются нечеткими величинами с функциями принадлежности, описываемыми кривой Гаусса (рис.4), и имеющими следующие параметры: первый потомок МОц = с''; с/и = Я*| с," - с/'|, второй потомок МОц = с2"; ¿¿¡2 = (I -).)*\ с," - с,2'\.

кроссинговера

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

Оператор мутации совместно с кроссинговером обеспечивают разнообразие в популяции. Классическая битовая мутация не подходит для НГА. В работе предлагаются вещественная мутация с элементами имитации отжига и нечеткая мутация. Пусть С = (ci, с2 .. с„) - мутируемая хромосома, Ci е[а, Ь] - мутируемый ген на поколении t, а с/ е [а, Ь] - этот же ген после мутации.

Тогда вещественная мутация с элементами имитации отжига определяется следующей формулой:

ct = с> + X'r~(bi- с,), если / = +1 или с/ = с, + /r-fcv-"j, если/ =-1, где х £ {-1, +1} - случайная величина, выбираемая при каждой мутации, определяющая направление мутации; г = r0-exp(l/s), re [0, 1] — величина, определяющая силу мутации; r0s[0, 1] — максимально возможная величина мутации, определяемая перед запуском алгоритма; s - множитель, определяющий степень изменения мутации в зависимости от поколения.

Нечеткая мутация определяется следующим образом: с^ = с, + г{Ь, - с,),

где re [0, 1] - значение нечеткой переменной, определяющее силу мутации и вычисляемое с помощью правил базы знаний.

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

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

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

Рис.5. Структура самонастраивающегося ГА

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

1. Разнообразие генотипа (вО): а) хэммингово расстояние (при битовом кодировании); б) евклидово расстояние (при вещественном кодировании); в) на основе гистограммы частотности значений генов; г) дисперсия значений генов.

2. Разнообразие фенотипа.

3. Изменение лучшей хромосомы.

4. Среднее изменение функции пригодности (ФП) популяции.

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

В качестве правил БЗ предлагается использовать модифицированные продукционные правила. Модифицированное продукционное правило может быть представлено в виде:

IF (условие) THEN (событие 1) WAIT At THEN (событие 2). Событие 1 и событие 2 представляют собой события начала и окончания некоторого действия, имеющего временную протяженность At. Действие может прерываться другими действиями и событиями.

Примеры обычного и модифицированного продукционного правила: lF(AFbts<s = не игменшось) THEN (Критерий останова^ Истина, /) lF(AFav^Ma4o)ancl(GD=Maio)T!IEN(BepcmmHocmb мутации-увеличить,!) WAIT5 поколений THEN (Вероятность мутации-уменьшить, 1)

Использование модифицированных продукционных правил дает возможность сократить количество запусков БЗ за счет установки времени действия ГО и позволяет планировать последовательность действий генетического поиска, упрощая создание базы правил.

В общем случае существует 3 уровня, где возможна адаптация параметров ГА: 1) уровень популяции - адаптация параметров, применяемых для всей популяции; 2) индивидуальный уровень — ориентируется на адаптацию параметров под конкретные хромосомы; 3) компонентный уровень - динамическая адаптация отдельных операторов каждых хромосом.

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

В третьей главе «Инструментальная среда поддержки эволюционного проектирования «GenSearch» описывается структура и принципы работы разработанной инструментальной среды (ИС) «GenSearch». На рис.6 представлена общая структура ИС «GenSearch», реализованной на основе объектно-ориентированного подхода.

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

1) устанавливаемые для всех популяций и не изменяемые во время работы ГА: а) количество запусков генетического алгоритма; б) функция пригодности;

2) устанавливаемые для всех популяций, которые могут изменяться блоком определения и корректировки параметров ГА (БОИ):

а) точность представления генотипа и расчета функции пригодности;

б) количество популяций в многопопуляционном алгоритме;

в) размер популяции; г) количество потомков; д) количество поколений (критерий останова для каждой отдельной популяции может задаваться отдельно);

3) устанавливаемые для каждой популяции в отдельности, которые могут изменяться БОП: а) способ кодирования (битовое, вещественное, нечеткое); б) список и параметры ГО; в) метод локальной оптимизации.

Блок определения кодировки Блок определения ГО

Блок выбора набора и

_последовательности ГО_

*

Блок выбора эволюции

♦ ~~

Блок определения многопоточности ЭС

Рис.6. Структура ИС «СепЗеагсЬ»

Генетический оператор может быть либо выбран из внутренней библиотеки ГО, либо быть реализован внешней процедурой. Генетический оператор в ИС рассматривается как черный ящик, на вход которого подается популяция родителей, а на выходе получаем популяцию потомков, В инструментальной среде выделены 4 класса ГО: а) ГО создания начальной популяции; б) ГО выбора родительской пары; в) ГО рекомбинации; г) ГО отбора (селекции).

Внешний (5лои определения параметров

Пользователь

Блок анализа исходных данных

Конструктор ГА

£ло* определения и корректировки параметров ГА

Для исключения появления запрещенных комбинаций в хромосомах и в связи со сложностью описания правил проверки на их отсутствие, в ИС имеется возможность подключить внешний механизм проверки и коррекции хромосом после выполнения ГО из внутренней библиотеки.

Схема цикла выполнения ГО в ИС «ОепБеагсИ» изображена на рис.7. Первым ГО является оператор класса выбора родительской пары, последним — оператор класса селекции. Между ними возможно любое количество операторов выбора родительской пары, рекомбинации, селекции. Такой подход позволяет реализовать практически любой вариант генетического поиска при имеющемся наборе ГО.

Рис. 7. Схема организации генетического поиска в ИС «Оеп8еагсЬ»

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

Изучение нечеткого ГА проводилось на непрерывных многопараметрических тестовых функциях, характеризующихся различным количеством оптимизируемых параметров, числом экстремумов (как локальных, так и глобальных), видом области поиска: многоэкстремальная функция (Р1), функция N переменных (в данном исследовании N = 10) (Г2), функция Растригина я=10 (РЗ). Исследовались 3 основные характеристики НГА: 1) нечеткое кодирование; 2) нечеткие ГО: мутация и кроссинговер; 3) адаптация параметров на индивидуальном и популяционном уровне с использованием БЗ.

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

нечеткий кроссинговср производит 4 потомка для каждой пары родителей, что приводит к двукратному увеличению расчетов функции пригодности. В связи с этим и с незначительным отличием в производительности нечеткого кроссинговера от эвристического окончательно рекомендуется использовать эвристический кроссинговер. Исследования мутации дая функций П и ¥2 не выявило преимущества предлагаемой схемы нечеткой мутации, тогда как для функции РЗ результаты при использовании нечеткой мутации оказались лучше.

Исследование эффективности подбора параметров ГА с помощью базы знаний на популяционном и индивидуальном уровне проводилось в двух режимах:

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

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

Сравнение полученных результатов позволит сделать вывод о возможности базы знаний подобрать наиболее близкие к оптимальным параметрам. Результаты исследований эффективности подбора параметров ГА с помощью базы знаний приведены на рис.8 (для функции РЗ на гистограмме при работе без ГА с худшими начальными параметрами значение ФП показано «-3», вместо «-53» для увеличения масштаба и улучшения читаемости диаграммы).

Р1 (т!п(Р)"-1) Р2(т!п(Р)»0| р3(тах(р)« О)

□ Без БЗ- луч.нач.усл. 0 Без БЗ - худ.нач.усл.

ИАдаптация на уровне популяции

- лучначусл. □Адаптация на уровне популяции

- худ.нач.усл.

■ Адаптация на попул. и индивид.

уровне - луч начусл. б Адаптация на попул. и индивид. уровне - худ.нач.усл._

Рис.8. Сравнительная гистограмма среднего значения ФП для различных вариантов использования базы знания

Для функций и Р2 при начале работы с наиболее подходящими параметрами результаты во всех режимах практически одинаковы, но за счет наличия в БЗ правил по определению* критерия останова количество вычислений функций сократилось почти в 2 раза, а время работы практически на 40%. При начале работы с наименее подходящими

параметрами отсутствие БЗ приводит к неудовлетворительным результатам. Использование БЗ с подбором параметров на индивидуальном уровне дает результаты, значительно лучшие, чем при использовании адаптации только на популяцнонном уровне. Следует отметить, что при различных начальных условиях при использовании БЗ практически не произошло увеличения времени работы ГА, но ухудшились результаты работы ГА- Это свидетельствует о том, что БЗ подобрала параметры, не являющиеся наиболее подходящими, хотя она сделала это достаточно быстро. Для функции /'5 ситуация немного отличается. Во всех режимах работы результаты работы ГА были практически одинаковыми за исключением режима без БЗ с началом работы при наименее подходящих параметрах. Но использование БЗ позволило сократить почти в 3 раза количество вычислений функций при подходящих начальных параметрах. При наименее подходящих параметрах БЗ смогла найти практически лучшие параметры, но на это пришлось потратить почти в 2 раза больше времени.

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

Оптимизируемой величиной для ГА является ФП, которую необходимо минимизировать

ФП = а,*5„ол + + а + а4*Хтр, где: - стоимость отходов полотна; — затраты на хранение заготовок, размещенных в данной хромосоме; 5,„т/, - штраф за невыполнение заказа в срок; Бтр - штраф за перепроизводство заготовок, размещенных в данной хромосоме; я>, а:, аз, - весовые коэффициенты, определяющие значимость производственных факторов.

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

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

:1Г^ГТб" .................... ;

; ]рШЦ

, о *---.-.-1-.----.-:-:

I 0 10 20 30 40 50 60 70 80 50 100

N количества блоков в портфеле заказа

Рис.9. Эффективность применения нечеткого ГА при решении задачи управления запасами при оптимизации раскроя ленточного материала

В заключении содержатся основные выводы и результаты диссертации.

В приложении 1 приведена копия авторского свидетельства (Роспатент) на инструментальную среду «ОепЗеагсЬ». В приложении 2 приведены копии актов о внедрении.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

3. Разработаны архитектуры гибридных интеллектуальных систем, объединяющих методы и средства эволюционных алгоритмов и нечеткой логики. Описаны способы реализации основных операторов гибридного нечеткого генетического алгоритма. Тестирование нечеткого генетического алгоритма на непрерывных функциях показало, что его использование позволяет повысить качество решения и уменьшить время работы (по сравнению с классическим ГА).

4. Разработаны методы автоматического подбора параметров и адаптации эволюционного алгоритма под решаемую задачу на основе баз знаний. Описаны различные уровни применения данных методов. Использование этих методов позволяет упростить подбор параметров ГА (сделав настройку ГА доступным для неспециалиста) и улучршть эффективность работы ГА за счет применения различных ГО в разные моменты поиска.

5. Разработан алгоритм решения задачи комплексной организации управления запасами при оптимизации раскроя ленточного материала. Использование нечеткого генетического алгоритма позволяет сократить общие расходы на 11-14% в зависимости от числа блоков в портфеле заказов и на 5-20% сократить время расчета. Внедрение на ОАО «Коломенский завод РТИ» позволило сократить время выполнения текущего портфеля заказов на 6-9% и получить годовой экономический эффект в размере 375 ООО рублей.

6. Создана и введена в эксплуатацию инструментальная программная среда «GenSearch» для поддержки эволюционного проектирования. Инструментальная среда реализована в среде Borland Delphi в рамках объектно-ориентированного подхода, что облегчает ее дальнейшее сопровождение и интеграцию с другими системами. Ее преимущество по сравнению с другими средами заключается в возможности выбора модели эволюции и гибкой настройки всех этапов генетического поиска с использованием БЗ.

Основные положения и результаты диссертации опубликованы в следующих работах:

1. Комарцова Л.Г., Голубин A.B. Исследование свойств генетических алгоритмов оптимизации// Труды МГТУ №580: Методы исследования и проектирования сложных технических систем: Сборник статей. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - С.77-87.

2. Голубин A.B. Определение параметров генетического алгоритма для оптимизации многопараметрических функций// Прогрессивные технологии, конструкции и системы в приборо- и машгаюстроении: Сборник статей. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - С.65-67.

3. Комарцова Л.Г., Голубин A.B. Использование Конструктора для определения параметров генетического алгоритма// Труды Пятого Международного симпозиума «Интеллектуальные системы» (TNTELS'2002). - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - С.283-286.

4. Комарцова Л.Г., Голубин A.B. Адаптация параметров генетических алгоритмов при поиске решений// Научная сессия МИФИ-2003. Интеллектуальные системы и технологии. Сборник научных трудов,-М.: МИФИ, 2003. -Т.З. - С. 124-125.

5. Комарцова Л.Г., Воеводин Ю.Ю., Голубин A.B. Исследование алгоритмов оптимизации для повышения эффективности обучения нейронных сетей// Системы искусственного интеллекта и нейроинформатика: Труды международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке, технике и экономике (КЛИН-2003) / Под общ. ред. Л.И.Волгина.- Ульяновск: УлГТУ, 2003. - Т.З. -С.79-81.

6. Комарцова Л.Г., Голубин A.B., Родионов A.B. Механизмы создания интеллектуальных САПР с использованием новых информационных технологий// Измерение, контроль, информатизация: Материалы третьей международной научно-технической конференции/ Под ред. А.Н.Тушева - Барнаул, АГТУ, 2003. - С.133.

7. Голубин A.B. Подход к решению оптимизационных задач на основе генетического алгоритма// Региональная студенческая конференция «Применение кибернетических методов в решении проблем общества XXI-го века». Тезисы докладов. - Обнинск: ИАТЭ, 2003. -С.34-36.

8. Голубин A.B. Программный комплекс «GenSearch» и методы повышения эффективности, реализованные в нем// Труды девятой Национальной конференции по искусственному интеллекту с международным участием (КИИ-2004). - М.: Физматлит, 2004. - С. 643-648.

9. Голубин A.B. Определение параметров генетического алгоритма с помощью программного комплекса «GenSearch» // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'04) и «Интеллектуальные САПР» (CAD-2004). - М.: Физматлит, 2005. - Т.З. - С.39.

10. Голубин A.B. Использование генетических алгоритмов при управлении запасами и оптимизации раскроя ленточного материала //Научная сессия МИФИ-2005. Интеллектуальные системы и технологии. Сборник научных трудов.- М.: МИФИ, 2005. - Т.З. -С.89-90.

11. Голубин A.B. Адаптация параметров генетических алгоритмов с помощью нечетких экспертных систем// Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сборник научных трудов Ш-го Международного научно-практического семинара. -М.: Физматлит, 2005. С.249-253.

12. Голубин A.B., Тарасов В.Б. Нечеткие генетические алгоритмы // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'05) и «Интеллектуальные САПР» (CAD-2005). - М.: Физматлит, 2005. - Т. I. - С.39-45.

13. Голубин A.B. Инструментальная среда исследования генетических алгоритмов «GenSearch»// Программные продукты и системы. Приложение к Международному журналу «Проблемы теории и практики управления». - 2005. - №3. — С.37-42.

14. Голубин A.B. Гибридные генетические алгоритмы: истоки и перспективы// Новости искусственного интеллекта. - 2006. - №1. -С.101-118.

15. Голубин A.B. Структура инструментальной среды исследования генетических алгоритмов «GenSearch»// Программные продукты и системы. Приложение к Международному журналу «Проблемы теории и практики управления». - 2006. - №2. - С.9-15.

16. Тарасов В.Б., Голубин A.B. Эволюционное проектирование: на границе между проектированием и самоорганизацией // Известия ТРТУ. - 2006. - №3. - С. 120-125.

В работах, опубликованных в соавторстве, автору принадлежат следующие результаты: [1] - проведены исследования операторов кроссинговера и мутации на тестовых непрерывных функциях; [3-5] -разработан алгоритм кодирования параметров конструктора ГА и создано программное обеспечение; [7] - предложен способ обучения нейронной сети с применением конструктора ГА; [12] - разработаны нечеткие генетические операторы кроссинговера и мутации; [16] — предложен способ проведения межвидовой гибридизации в ГА.

Соискатель (J^-C^-— А.В.Голубин

Подписано к печати 24.07.2006г. Заказ № 60

Типография ООО «Инлайт»

Объем 1 п.л. Тираж 100 экз.

МГТУ им. Н.Э.Баумана

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

1. АНАЛИЗ ПРОБЛЕМ, ПЕРСПЕКТИВ И МЕТОДОВ ЭВОЛЮЦИОННОГО ПРОЕКТИРОВАНИЯ.

1.1. Некоторые современные тенденции развития САПР.

1.2. Эволюционное проектирование.

1.3. Применение принципов эволюции при построении алгоритмов оптимизации.

1.3.1. Теории эволюции естественных систем.

1.3.2. Эволюционное моделирование.

1.3.3. Генетические алгоритмы на основе недарвиновских моделей эволюции.

1.3.4. Гибридные алгоритмы на основе объединения различных теорий эволюции.

1.4. Создание гибридных моделей на основе различных методик и информационных технологий.

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

1.6. Выводы по главе 1.

2. МНОГОЭВОЛЮЦИОННЫЙ НЕЧЕТКИЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ

2.1. Построение генетических алгоритмов на основе различных моделей эволюции.

2.1.1. Вид и межвидовая гибридизация в генетических алгоритмах.

2.1.2. Способы реализации основных моделей эволюции в ГА.

2.2. Построение гибридной системы на основе различных моделей эволюции.

2.3. Гибридные модели с использованием ГА и нечеткой логики.

2.3.1. Нечеткое кодирование.

2.3.2. Нечеткие генетические операторы.

2.3.3. Использование баз знаний для подбора параметров.

2.4. Выводы по главе 2.

3. ИНСТРУМЕНТАЛЬНАЯ СРЕДА ПОДДЕРЖКИ ЭВОЛЮЦИОННОГО ПРОЕКТИРОВАНИЯ «GENSEARCH». ф 3.1. Требования к программным продуктам, реализующим генетические алгоритмы.

3.2. Основные характеристики инструментальной среды «GenSearch».Ill

3.3. Структура инструментальной среды «GENSEARCH».

3.4. Выводы по главе 3.

4. ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ И ОЦЕНКА ИХ ЭФФЕКТИВНОСТИ ПРИ РЕШЕНР1И ТЕСТОВЫХ И ПРАКТИЧЕСКИХ ЗАДАЧ.

4.1. Цели и методы проводимых исследований.

4.2. Исследование эффективности нечеткого генетического.

4.2.1. Нечеткое кодирование.

4.2.2. Кроссинговер.

4.2.3. Мутация.

4.2.4. Подбор параметров с использованием базы знаний.

4.3. Исследование эффективности разработанного алгоритма на практической производственной задаче.

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

4.3.2. Существующие способы решения.

4.3.3. Предлагаемый способ решения.

4.3.4. Программная реализация предлагаемого решения.

4.4. Выводы по главе 4.

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

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

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

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

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

1. Анализ и разработка теоретических вопросов эволюционного проектирования. Реализация эволюционного проектирования с помощью эволюционных алгоритмов.

2. Исследование способов построения эволюционных алгоритмов на основе недарвиновских моделей эволюции.

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

4. Разработка способов автоматического подбора параметров и методов самоадаптации эволюционного алгоритма под решаемую задачу.

5. Разработка алгоритма решения задачи комплексной организации управления запасами при оптимизации раскроя ленточного материала.

6. Создание программного обеспечения, реализующего разработанные алгоритмы.

7. Применение разработанного программного обеспечения для решения прикладных оптимизационных задач.

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

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

1. Эволюционный алгоритм на базе недарвиновских моделей эволюции;

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

3. Метод автоматического подбора параметров эволюционного алгоритма на основе баз знаний;

4. Архитектура инструментальной среды поддержки эволюционного проектирования.

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

Внедрение и реализация результатов. Теоретические и практические результаты, полученные в диссертационной работе, применялись при выполнении хоздоговорной тематики Отдела «Компьютерные системы автоматизации» НУК РК МГТУ им. Н.Э.Баумана. Результаты диссертации также использованы при выполнении работ по грантам Российского фонда фундаментальных исследований (проекты №0201-00784, 03-07-90012, 04-01-00306, 05-01-00514).

Результаты исследований, проведенных в диссертационной работе, были внедрены на «ОАО Коломенский завод РТИ». Кроме того, результаты работы нашли применение в учебном процессе кафедры «Компьютерные системы автоматизации производства» МГТУ им. Н.Э.Баумана и кафедры САПР ТРТУ.

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

Апробация работы. Основные результаты работы докладывались на: Пятом международном симпозиуме «Интеллектуальные системы» (INTELS' 2002, Калуга, 2002г.), Научной сессии МИФИ-2003 (Москва, 2003г.), Третьей международной научно-технической конференции «Измерение, контроль, информатизация» (Барнаул, 2003), Региональной студенческой конференции «Применение кибернетических методов в решении проблем общества XXI века» (Обнинск, 2003), Международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке, технике и экономике» (КЛИН-2003, Ульяновск, 2003), Девятой Национальной конференции по искусственному интеллекту с международным участием (КИИ-2004, Тверь, 2004г.), Международных научно-технических конференциях IEEE AIS'04 и CAD-2004 (Дивноморское, 2004г.), Научной сессии МИФИ-2005 (Москва, 2005г.), Ш-м Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2005г.), Международных научно-технических конференциях IEEE AIS'05 и CAD-2005 (Дивноморское, 2005г.).

Публикации. По теме диссертации автором опубликовано 16 работ, включается 3 публикации в журналах, рекомендованных ВАК РФ, имеется авторское свидетельство об официальной регистрации программы для ЭВМ (Роспатент). Диссертация состоит из введения, четырех глав, заключения, списка литературы и двух приложений. Объем диссертации составляет 175

4.4. Выводы по главе 4

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

2. Разработанные алгоритмы также подтвердили свою эффективность при решении рассмотренной в диссертационной работе прикладной производственной задачи по управлению запасами при оптимизации раскроя ленточного материала. При этом экономия средств составляет 11—14 %, а экономия временных затрат 5-20% по сравнению с классическими алгоритмами генетического поиска.

154

ЗАКЛЮЧЕНИЕ

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

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

3. Разработаны архитектуры гибридных интеллектуальных систем, объединяющих методы и средства эволюционных алгоритмов и нечеткой логики. Описаны способы реализации основных операторов гибридного нечеткого генетического алгоритма. Тестирование нечеткого генетического алгоритма на непрерывных функциях показало, что его использование позволяет повысить качество решения и уменьшить время работы (по сравнению с классическим ГА).

4. Разработаны методы автоматического подбора параметров и адаптации эволюционного алгоритма под решаемую задачу на основе баз знаний. Описаны различные уровни применения данных методов. Использование этих методов позволяет упростить подбор параметров ГА (сделав настройку ГА доступным для неспециалиста) и улучшить эффективность работы ГА за счет применения различных ГО в разные моменты поиска.

5. Разработан алгоритм решения задачи комплексной организации управления запасами при оптимизации раскроя ленточного материала. Использование нечеткого генетического алгоритма позволяет сократить общие расходы на 11—14% в зависимости от числа блоков в портфеле заказов и на 5-20% сократить время расчета. Внедрение на ОАО «Коломенский завод РТИ» позволило сократить время выполнения текущего портфеля заказов на 6—9% и получить годовой экономический эффект в размере 375 ООО рублей.

6. Создана и введена в эксплуатацию инструментальная программная среда «GenSearch» для поддержки эволюционного проектирования. Инструментальная среда реализована в среде Borland Delphi в рамках объектно-ориентированного подхода, что облегчает ее дальнейшее сопровождение и интеграцию с другими системами. Ее преимущество по сравнению с другими средами заключается в возможности выбора модели эволюции и гибкой настройки всех этапов генетического поиска с использованием БЗ.

1. Аверкин А.Н., Батыршин И.З., Блишун А.Ф. и др. Нечеткие множества в моделях управления и искусственного интеллекта/ Подред. Д.А.Поспелова. - М.: Наука, 1986.

2. Аверкин А.Н., Прокопчина С В . Мягкие вычисления и измерения // Интеллектуальные системы (МГУ). - 1997. - Т.2, вып. 1-4. — 93-114.

3. Алиев Р.А., Алиев P.P. Теория интеллектуальных систем и ее применение. — Баку: Чашыоглы, 2001.

4. Афонин П.В. Гибридные системы интеллектуального имитационного моделирования // Новости искусственного интеллекта. - 2006. - №1.

5. Афонин П.В. Гибридные системы интеллектуального имитационного моделирования на основе бионических подходов и многоагентныхмоделей// Диссертация на соискание ученой степени кандидататехнических наук. - М.: МГТУ им. Н.Э.Баумана, 2005.

6. Балашов Е.П. Эволюционный синтез систем. — М.: Радио и связь, 1985.

7. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. — Воронеж: Изд-во ВГТУ, 1995.

8. Бендат Дж., Пирсол А. Измерение и анализ случайных процессов. - М: Мир, 1974.

9. Берг Л.С. Номогенез или эволюция на основе закономерностей // Труды по теории эволюции. — Л.: Наука, 1977. — 95-311

10. Берштейн Л.С., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных интеллектуальных системах. -Ростов-на-Дону: Изд-во РГУ, 1999.

11. Берштейн Л.С., Коровин Я., Мелихов А.Н., Сергеев Н.Е. Функционально-структурное исследование ситуационно-фреймовойсети экспертной системы с нечеткой логикой// Известия РАН:Техническая кибернетика. — 1994. — №2. — 71-83.

12. Большая советская энциклопедия. Т.2. - М.: Изд-во СЭ, 1978.

13. Большая советская энциклопедия. Т.29. — М.: Изд-во СЭ, 1978.

14. Борель Э., Дельтейл Р., Юрон Р. Вероятности, ошибки / Пер. с франц. - М . : Статистика, 1972.

15. Букатова И.Л., Михасев Ю.И., Шаров A.M. Эвоинформатика. Теория и практика эволюционного моделирования. — М.: Наука, 1991.

16. Вагин В.Н., Еремеев А.П. Некоторые базовые принципы построения интеллектуальных систем поддержки принятия решений реальноговремени // Известия РАН: Теория и системы управления. - 2001. -№6.-С.114-123.

17. Варшавский В.А., Поспелов Д.А. Оркестр играет без дирижера. Размышления об эволюции некоторых технических систем иуправлении ими. — М.: Наука, 1984.

18. Волкова В.Н., Денисов А.А. Основы теории систем и системного анализа. - СПб: СПбГТУ, 2001.

19. Вороновский Г.А., Махотило К.В., Петрашев Н., Сергеев А. Генетические алгоритмы, искусственные нейронные сети ипроблемы виртуальной реальности. Харьков: Основа, 1997.

20. Воронцов Н.Н. Развитие эволюционных идей в биологии. - М.: Прогресс-Традиция, 1999.158

21. Гаврилов А.В. Гибридные интеллектуальные системы. — Новосибирск: Изд-во НГТУ, 2003.

22. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация // Пер. с англ. - М.: Мир, 1985.

23. Гладков Л.А. Печеткие генетические алгоритмы//Новости искусственного интеллекта. — 2005. — №4. — 45-52.

24. Гладков Л.А., Зинченко Л.А., Курейчик В.В., Курейчик В.М., Лебедев Б.К., Нужнов Е.В., Сорокин Н. Методы генетическогопоиска. - Таганрог: Изд-во ТРТУ, 2002.

25. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Учебное пособие. — М.: Физматлит, 2006.

26. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы: Учебное пособие/ Под ред.В.М.Курейчика. - Ростов-на-Дону: Ростиздат, 2004.

27. Голубин А.В. Гибридные генетические алгоритмы: истоки и перспективы // Новости искусственного интеллекта. — 2006. — №1.

28. Голубин А.В. Определение параметров генетического алгоритма для оптимизации многопараметрических функций // Прогрессивныетехнологии, конструкции и системы в приборо- и машиностроении:Сборник статей.- М.: Изд-во МГТУ им. Н.Э.Баумана, 2001.- 65-67.

29. Голубин А.В. Программный комплекс «GenSearch» и методы повышения эффективности, реализованные в нем // Труды ДевятойНациональной конференции по искусственному интеллекту смеждународным участием (КИИ-2004). - М.: Физматлит, 2004. -С.643-648.

30. Голубин А.В., Тарасов В.Б. Нечеткие генетические алгоритмы // Труды Международных научно-технических конференций«Интеллектуальные системы» (AIS'O5) и «Интеллектуальные САПР»(CAD-2005). - М . : Физматлит, 2005, Т.1. - 39-45.

31. Голубовский М.Д. Век генетики: эволюция идей и понятий. — СПб: Борей арт, 2000.

32. Грант В. Эволюционный процесс. Критический обзор эволюционной теории: Пер. с англ. - М . : Мир, 1991.

33. Дарвин Ч. Происхождение видов путем естественного отбора. Соч., т.З. - М.-Л.: Академия, 1939.159

34. Джексон П. Введение в экснертные системы: Учеб. пособие: Пер. с англ. — М.: Изд. дом «Вильяме», 2001.

35. Дубинин Н.П. Избранные труды. Т.1. Проблемы гена и эволюции. - М.: Наука, 2000.

36. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. - М . : Физматлит, 2003.

37. Емельянов В.В., Ясиновский СИ. Введение в интеллектуальное имитационное моделирование сложных дискретных систем ипроцессов. Язык РДО. - М.: АНВИК, 1998.

38. Емельянов В.В., Ясиновский СИ. Гибридная система для планирования производства на основе генетических алгоритмов,методов имитации и экспертных систем // Известия ТРТУ. - 1996. -№3.-С4-9.

39. Еремеев А.П. Об интеграции моделей в интеллектуальных системах поддержки принятия решений// Труды 9-й национальнойконференции по искусственному интеллекту КИИ'2004 (Тверь, 28сентября-2 октября 2004 г.).- М.: Физматлит, 2004.- Т.2. - 815-823.

40. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений: Пер. с англ. - М.: Мир, 1976.

41. Зинченко Л.А. Курейчик М.В. Синергетическое эволюционное проектирование // Труды восьмой национальной конференции поискусственному интеллекту (КР1И-2002). - М.: Физматлит. - 2002. -Т.2. - С 876-884.160

42. Интеллектуальные системы: Коллективная монография/ Под ред. В.М.Курейчика. — М.: Физматлит, 2005.

43. Карпов В.Э. Эволюционное моделирование. Проблемы формы и содержания// Повости искусственного интеллекта. - 2003.- №5. -С.35-46.

44. Ковалев СМ., Родзин СИ. Информационные технологии: интеллектуализация обучения, моделирование эволюции,распознавание речи. - Ростов-на-Дону: Изд-во СКНЦ ВШ, 2002.

45. Колесников А.В. Гибридные интеллектуальные системы. Теория и технология разработки/ Под ред. A.M. Яшина.- СПб.: СПбГТУ, 2001.

46. Комарцова Л.Г. Двухэтапный алгоритм обучения нейронной сети на основе генетического поиска// Пейрокомпьютеры. Разработка иприменение.- 2001.- №1.-СЗ-9.

47. Комарцова Л.Г. Исследование конструктора генетических алгоритмов // Известия ТРТУ. - 2003. - N^i2. - 120-124.

48. Комарцова Л.Г. Исследование нейросетевых и гибридных методов и технологий в интеллектуальных системах поддержки принятиярешений // Диссертация на соискание ученой степени докторатехнических наук. - Калуга: КФ МГТУ им. Н.Э.Баумана, 2003.

49. Комарцова Л.Г., Голубин А.В. Адаптация параметров генетических алгоритмов при поиске решений// Сборник научных трудов. Паучнаясессия МИФИ-2003. - М.: Изд-во МИФИ, 2003. - Т.З. - С124-125.

50. Комарцова Л.Г., Голубин А.В. Использование Конструктора для определения параметров генетического алгоритма // Труды ПятогоМеждународного симпозиума "Интеллектуальные системы" (INTELS2002). -М.: Изд-во МГТУ им. П.Э. Баумана, 2002. - 283-286.

51. Комарцова Л.Г., Голубин А.В. Исследование свойств генетических алгоритмов оптимизации // Труды МГТУ №580: Методыисследования и проектирования сложных технических систем:Сборник статей. М.: Изд-во МГТУ им. И.Э.Баумана.- 2001.- 77-87.161

52. Кордюм В.А. Эволюция и биосфера. — Киев: Наукова думка, 1982.

53. Корнеев В.В., Гареев А.Ф. и др. Базы данных. Интеллектуальная обработка информации. - М. Нолидж, 2000.

54. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР.-М.: Энергоатомиздат, 1987.

55. Красилов В.А. Теория эволюции: необходимость нового синтеза // Эволюционные исследования. Макроэволюция. - Владивосток:ДВНЦ АН СССР, 1984. - 4-12.

56. Кузнецов В.А. Задачи раскроя в целлюлозно-бумажной промышленности. СПб.: СПбЛТА, 2000.

57. Кузнецов О.П. Пеклассические парадигмы в искусственном интеллекте// Известия РАП: Теория и системы управления. - 1995. -№5.-С.З-23.

58. Курейчик В.В. Построение моделей эволюции// Интеллектуальные системы/ Под ред. В.М.Курейчика. - М.: Физматлит, 2005. - 47-56.

59. Курейчик В.В. Эволюционные методы решения оптимизационных задач. - Таганрог: Изд-во ТРТУ, 1999.

60. Курейчик В.В. Эволюционные, синергетические и гомеостатические методы принятия решений: Монография. - Таганрог: Изд-во ТРТУ,2001.

61. Курейчик В.В., Пужнов Е.В. Об интегрированной инструментальной среде поддержки генетических алгоритмов// Новости искусственногоинтеллекта.-2003. - № 5 . - С . 13-19.

62. Курейчик В.М. Генетические алгоритмы. - Таганрог: Изд-во ТРТУ, 1998.

63. Курейчик В.М. и др. Самонастраиваюп.;ийся генетический алгоритм // Труды 8-й национальной конференции по искусственномуинтеллекту КИИ-2002 (Тверь, 28 сентября -2 октября 2004 г.). - М.:Физматлит, 2004. - Т. 1. - 400-408.

64. Курейчик В.М., Родзин СИ. Эволюционные вычисления: генетическое и эволюционное программирование // Новостиискусственного интеллекта. - 2003. - №5. - 13-19.

65. Курейчик В.М., Тарасов В.Б. Введение в интеллектуальные системы автоматизированного проектирования// Известия ТРТУ. — 1997. —№3.-С.41-49.162

66. Ламарк Ж.Б. Философия зоологии, Т. 1,2.- М.-Л.: Академия, 1939.

67. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС. - Таганрог: Изд-воТРТУ, 2000.

68. Липовецкий А.И. Свойства прямоугольных укладок и алгоритмы оптимального раскроя // Управляющие системы. Вып. 25. -Новосибирск: ИМ СОАН СССР, 1984.

69. Люгер Дж.Ф. Искусственный интеллект. Стратегии и методы решения сложных проблем: Пер с англ. — М.: Изд. Дом «Вильяме»,2003.

70. Мелихов А.Н., Берштейн Л.С., Коровин Я. Ситуационные советующие системы с нечеткой логикой. - М . : Наука, 1990.

71. Мищенко В.А., Городецкий Л.М., Гурский Л.И. и др. Интеллектуальные системы автоматизированного проектированиябольших и сверхбольших интегральных микросхем. - М.: Радио исвязь, 1988.

72. Моисеев Н.Н. Универсальный эволюционизм (Позиция и следствия) // Избранные труды. — М.: Тайдекс Ко, 2003.

73. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерногораскроя // Информационные технологии. - 2000. - }ё9. - 15-20.

74. Мухачева А.С., Чиглицев А.В., Смагин М.А., Мухачева Э.А. Задачи двухмерной упаковки: развитие генетических алгоритмов на базесмешанных процедур локального поиска оптимального решения //Приложение к журналу «Информационные технологии».-2001.-Хо9.

75. Назаров В.И. Эволюция не по Дарвину: смена эволюционной модели. Учебное пособие. — М.: КомКнига, 2005.

76. Нильсон Н. Принципы искусственного интеллекта: Пер. с англ. - М.: Издательский Дом «Вильяме», 2001.

77. Норенков И.П. Разработка систем автоматизированного проектирования. — М.: Изд-во МГТУ им. Н.Э.Баумана, 1994.

78. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации// Информационные технологии. — 1999. —163

79. Норенков И.П., Косачевский О.Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации //Информационные технологии. - 1999. - J\r«2. - 2-7. 80. Осипов Г.С. Динамика в системах, основанных на знаниях// Известия РАН: Теория и системы управления. — 1998. — №5. — 24-28.

81. Попов Э.В. Особенности разработки и использования экспертных систем// Искусственный интеллект: в 3-х кн. Кн.1. Системы общенияи экспертные системы: Справочник/ Под ред. Э.В.Попова. - М.:Радио и связь, 1990. - 261-290.

82. Попов Э.В. Экспертные системы. Решение неформализованных задач в диалоге с ЭВМ. - М.: Паука, 1987.

83. Попов Э.В. Экспертные системы. Состояние, проблемы, перспективы // Известия АП СССР: Техническая кибернетика. — 1989. —№5.

84. Попов Э.В., Фоминых И.Б., Кисель Е.Б., Шапот М.Д. Статические и динамические экспертные системы: Учебное пособие. - М . : Финансыи статистика, 1996.

85. Поспелов Г.С. Искусственный интеллект — основа новой информационной технологии. - М.: Паука, 1988.

86. Поспелов Д.А. Моделирование рассуждений. Опыт анализа мыслительных актов. - М.: Радио и связь, 1989.

87. Редько В.Г. Эволюционная кибернетика. — М.: Паука, 2001.

88. Реклейтис А., Рейвиндран А. и др. Оптимизация в технике. - В 2-х кн.-М. : Мир, 1988.

89. Родзин СИ. Гибридные интеллектуальные системы на основе алгоритмов эволюционного программирования// Повостиискусственного интеллекта. - 2000. - №3. - 159-170.

90. Родзин СИ. Эволюционные стратегии: концепция и результаты // Перспективные информационные технологии и интеллектуальныесистемы. - 2002. - №2. - 4-12.164

91. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с нольск. И.Д.Рудинского. — М.: Горячая линия — Телеком, 2004.

92. Рыбина Г.В. Архитектуры интегрированных экспертных систем: современное состояние и тенденции// Новости искусственногоинтеллекта. - 2002. - №4. - 10-17.

93. Рыбина Г.В. Нринцины создания автоматизированной технологии проектирования интегрированных экспертных систем// Новостиискусственного интеллекта. - 1993. - No4. — 105-116.

94. Седенков В.М. Эволюционное проектирование сложных объектов. - Мн., 1997.

95. Скурихин А.Г. Генетические алгоритмы// Новости искусственного интеллекта. - 1995. - №4. - 6-46.

96. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов // Киев: Наукова думка, 1976.

97. Тарасов В.Б. Восходящее и нисходящее проектирование многоагентных систем // Труды международной конференции«Проблемы управления и моделирования в сложных системах»(Самара, 14-18 июня 1999). — Самара: Самарский научный центрРАН, 1999.-С.268-274.

98. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. - М.:Эдиториал УРСС, 2002.

99. Тарасов В.Б., Соломатин Н.М. Развитие прикладных интеллектуальных систем: анализ основных этапов, концепций ипроблем/ЛЗестник МГТУ им. Н.Э.Баумана: Сер.«Приборостроение».-1994.-Xol.-C.5-14165

100. Фогель Л., Оуэне А., Уолш М. Искусственный интеллект и эволюционное моделирование: Пер. с англ. - М.: Мир, 1969.

101. Фоминых И.Б. Интеграция нейронных и символьно-логических моделей в интеллектуальных технологиях//Труды YII-йИациональной конференции по ИИ. - М.: Физматлит, 2000. - Т.2. -С.588-596.

102. Фоминых И.Б. Принципы построения гибридных интеллектуальных систем реального времени // Труды Международного конгресса«Искусственный интеллект в XXI-M веке». — М.: Физматлит, 2001. —Т.2.-С.570-583.

103. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. — М.: Наука, 1969.

104. Чичварин Н.В. Экспертные компоненты САПР. - М.: Машиностроение, 1991.

105. Шмальгаузен И.И. Проблема дарвинизма.-Л.: Иаука, 1969.

106. Шмальгаузен И.И. Факторы эволюции. - М.: Иаука, 1968.

107. Шумский А. Байесова регуляризация обучения // Иаучная сессия МИФИ-2002. Сб. научных трудов 4-й Всероссийской конференции"Пейроинформатика-2002".-В 2 частях.Ч.1.-М.: Изд-во МИФИ, 2002.

108. Ярушкина И.Г. Гибридные системы, основанные на мягких вычислениях: определение, архитектура, возможности//Программные продукты и системы. - 2002. - N23. - 19-22

109. Ярушкина П.Г. Основы теории нечетких и гибридных систем. - М.: Финансы и статистика, 2004.

110. Ясиновский С И . Логический вывод в гибридных системах // Вестник МГТУ. Сер. Приборостроение. - 1994. -Х«1. - 88-99.

111. Angeline P.G. Adaptive and Self-Adaptive Evolutionary Computations // Computational Intelligence: A Dynamic Systems Perspective. -Piscataway, NJ: IEEE Press, 1995. -P.152-163.166

112. Back Т., Schwefel Н.-Р. An Overview of Evolutionary Algorithms for Parameter Optimization// Evolutionary Computation. - 1993. -Vol.1. -P. 1-23.

113. Bentley P. Evolutionary Design by Computers. - San Francisco: Morgan Kaufmann Publishers Inc., 1999.

114. Bowden R.O., Hall J.D. Simulation Optimization Research and Development // Proc. 1998. Winter Simulation Conference, Washington,D.C.,p.l693-1698.

115. Brian J.R. A Lamarckian Evolution Strategy for Genetic Algorithms // Practical Handbook of Genetic Algorithms. Vol. 3/ L. Chambers (ed.). -Boca Raton: CRC Press, 1999. - P . 1-16.

116. Claudio M., Waibel M., Floreano D. Measures of Diversity for Populations and Distances Between Individuals with HighlyReorganizable Genomes// Evolutionary Computation. - 2004. - Vol. 12,№4.-P.495-515.

117. Davis L. Handbook of Genetic Algorithms. - New York: Van Nostrand Reinhold, 1991.

118. DeJong K,A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Doctoral Dissertation, University of Michigan, UniversityMicrofilms 76-9381, 1975.

119. Fogel D.B. Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. — New York: IEEE Press, 1995.

120. Fogel L.J. Artificial Intelligence through Simulated Evolution. - New York: John Wiley, 1966.

121. Gero J.S. Computers and Creative Design // The Global Design Studio, National University of Singapore, 1996.-P. 11-19.

122. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine 1.earning. - New York: Addison-Wesley Publishing Company, Inc., 1989.

123. Goldberg D.E., Korb В., Deb K. Messy Genetic Algorithms: Motivation, Analysis and First Results//Complex Systems.- 1989.-Vol.3.- P.493-530.167

124. Grefenstette JJ, Lamarckian Learning in Multi-agent Environments // Proceedings of the Fourth International Conference on GeneticAlgorithms. -San Mateo, CA: Morgan Kaufmann, 1991. - P.303-310.

125. Grefenstette J.J. Optimization of Control Parameters for Genetic Algorithms // IEEE Transactions on Systems Man and Cybernetics. —1986.-Vol.l6,№l.-P.122-128.

126. Hart W.E., Belew R.K. Optimization with Genetic Algorithm Hybrids that Use Local Search // Adaptive Individuals in Evolving Populations. -Cambridge MA: Addison-Wesley, 1996. - P.483-496.

127. Herrera F., Lozano F. Adaptation of Genetic Algorithm Parameters Based on Fuzzy Logic Controllers // Genetic Algorithms and Soft Computing. -Berlin: Physica-Verlag, 1999.-P.95-125.

128. Herrera F., Lozano F. Fuzzy Genetic Algorithms: Issues and Models // Technical Report DECSAI-98116, Dept. of Computer Science and A.I.,University of Granada, June 1998.

129. Hinton G., Nolan S. How learning can guide evolution. Complex Systems, -1987.-Vol .1.-P. 495-502.

130. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and ArtificialIntelligence. — Ann Arbor: University of Michigan Press, 1975.

131. Houck C. R., Joines J. A., Kay M.G. Utilizing Lamarckian Evolution and the Baldwin Effect in Hybrid Genetic Algorithms // Technical ReportNCSU-IE Technical Report 96-01, North Carolina State University, 1996.

132. Houck C.R., Joines J.A., Kay M.G., Wilson J.R. Empirical Investigation of the Benefits of Partial Lamarckianism// Evolutionary Computation. —1997.-Vol.5,.NoL-P.31-60.145. htpp://www.uni-koblenz.se/kyt/Leam/Textbook/nodel95.html

133. Jung J.S.-R., Sun C.T., Mizutani E. Neuro-Fuzzy and Soft Computing. - Englewood Cliffs: Prentice Hall, 1997.

134. Kasabov N. Evolving Connectionist Systems. - Berlin: Springer Verlag, 2003.

135. Keller J.M., Yager R.R., Tahani H. Neural Network Implementation of Fuzzy Logic// Fuzzy Sets and Systems. - 1992. - Vol.45, №1. - P. 1-12.

136. Kewley R.H., Embrechts M.Jr.J. Fuzzy-Genetic Decision Optimization for Positioning of Military Combat Units, 1998.168

137. Kirkpatrick S., Gellat C D . Vecchi M. Optimization by Simulated Annealing. - Science. - 1983. - Vol. 220.

138. Kosko B. Neural Networks and Fuzzy Systems. - Englewood Cliffs: Prentice Hall, 1992.

139. Koza J.R. Genetic Programming. - Cambridge: The MIT Press, 1992.

140. Koza J.R. Genetic Programming, 2. - Cambridge: The MIT Press, 1992.

141. Lamma E., Periera L.M., Riguzzi F. Belief Revision by Lamarckian Evolution, Technical Report DEIS-LIA-00-004, University of Bologna,2000. LIA Series, №44.

142. Lee A.M., Takagi H. Dynamic Control of Genetic Algorithms using Fuzzy Logic Techniques// Proceedings of the Fifth InternationalConference on Genetic Algorithms. - San Mateo: Morgan Kaufmann,1993.-P.76-83.

143. Li Т.Н., Lucasius C.B., Kateman G. Optimization of Calibration Data with the Dynamic Genetic Algorithm // Analitica Chimica Acta. - 1992. -P.76-83.

144. Li Y., Tan K. C, Gong M. Model Reduction in Control Systems by Means of Global Structure Evolution and Local Parameter Learning//Evolutionary Algorithms in Engineering Applications. - New York:Springer-Verlag, 1996.

145. Lin C.-T., Lee G.C.S. Neural Fuzzy Systems. A Neuro-Fuzzy Synergism to Intelligent Systems. - Upper Saddle River, NJ: Prentice Hall, 1997.

146. Lis J. Parallel Genetic Algorithm with the Dynamic Control Parameter // Proceedings of IEEE International Conference on EvolutionaryComputation, 1996. - P . 324-329.

147. Liu D., Teng H. An Improved BL-algorithm for Genetic Algorithm of the Orthogonal Packing of Rectangles // European Journal of OperationResearch. - 1999. -Vol.112. -P.413-420.

148. Medsker L.R. Hybrid Intelligent Systems. - Dordrecht: Kluwer Academic Publ., 1995.

149. Michalewicz Z., Genetic Algorithms + Data Structures = Evolutionary Programs. - Berlin: Springer-Verlag, 1992.

150. Michalewicz Z., Nazhiyath G., Michalewicz M. A Note on Usefulness of Geometrical Crossover for Numerical Optimization Problems // Proc. of169the 5*"^ Annual Conference on Evolutionary Programming. - Cambridge,MA: MIT Press, 1996. - P. 305-312.

151. Michalski R.S. Learning and Evolution: An Introduction to Non- Darwinian Evolutionary Computation // Parallel Problem Solving fromNature. Lecture Notes in Computer Science. - Heidelberg: Springer-Verlag, 1999. - Vol. 956. - P.21-30.

152. Mizumoto M. Pictorial Representations of Fuzzy Connectives. Part I: Cases of Compensatory Operators and Self-Dual Operators// Fuzzy Setsand Systems. - 1989. - Vol.32. - P.45-79.

153. Pham Q.T. Competitive Evolution: a Natural Approach to Operator Selection //Progress in Evolutionary Computation. Lecture Notes inArtificial Intelligence. - Heidelberg: Springer-Verlag, 1995. - Vol. 956. -P.49-60

154. Practical Handbook of Genetic Algorithms/ I. Chambers (ed.). Vol.2. - Washington, USA: CRC Press, 2001.

155. Schlierkamp-Voosen D., Muhlenbein. H. Strategy Adaptation by Competing Subpopulations // Parallel Problem Solving from Nature. Vol

156. Lecture Notes in Computer Science. - Berlin: Springer-Verlag, 1994. - Vol.866.-РЛ99-208.

157. Voigt H.M. Fuzzy Evolutionary Algorithms. Technical Report tr-92-038. International Computer Science Institute (ICSI), Berkley, 1992.

158. Whitley D., Gordon V. S., Mathias K. Lamarckian Evolution, the Baldwin Effect and Function Optimization // Parallel Problem Solving FromNature. Vol. 3. Lecture Notes in Computer Science. - Berlin: Springer-Verlag, 1994. - Vol.866. - P.6-15.

159. Zadeh L.A. Fuzzy Sets // Information and Control. - 1965. -Vol.8. P.338-353.