Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов

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

Full description

Saved in:

Bibliographic Details
Published in:	Штучний інтелект
Date:	2011
Main Authors:	Бухановский, А.В., Нечаев, Ю.И.
Format:	Article
Language:	Russian
Published:	Інститут проблем штучного інтелекту МОН України та НАН України 2011
Subjects:	Концептуальные проблемы создания систем искусственного интеллекта
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/59832
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов / А.В. Бухановский, Ю.И. Нечаев // Штучний інтелект. — 2011. — № 3. — С. 42-54. — Бібліогр.: 31 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-59832
record_format	dspace
spelling	Бухановский, А.В. Нечаев, Ю.И. 2014-04-10T11:49:32Z 2014-04-10T11:49:32Z 2011 Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов / А.В. Бухановский, Ю.И. Нечаев // Штучний інтелект. — 2011. — № 3. — С. 42-54. — Бібліогр.: 31 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/59832 004.942 Рассматривается подход и концептуальный базис эволюционного моделирования на современном этапе развития учения о естественной генетике в задачах исследовательского проектирования. Сформулированы теоретические принципы формализации проблемы с использованием достижений интеллектуальных технологий и высокопроизводительных средств вычислений. Приведены примеры реализации разработанного подхода в практических приложениях исследовательского проектирования морских судов. Розглядається підхід і концептуальний базис еволюційного моделювання на сучасному етапі розвитку вчення про природну генетику в задачах дослідницького проектування. Сформульовані теоретичні принципи формалізації проблеми з використанням досягнень інтелектуальних технологій та високопродуктивних засобів обчислень. Наведені приклади реалізації розробленого підходу в практичних застосуваннях дослідницького проектування морських суден. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Концептуальные проблемы создания систем искусственного интеллекта Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов Еволюційне моделювання задач багатокритеріальної оптимізації в системі дослідницького проектування морських суден Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов
spellingShingle	Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов Бухановский, А.В. Нечаев, Ю.И. Концептуальные проблемы создания систем искусственного интеллекта
title_short	Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов
title_full	Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов
title_fullStr	Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов
title_full_unstemmed	Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов
title_sort	эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов
author	Бухановский, А.В. Нечаев, Ю.И.
author_facet	Бухановский, А.В. Нечаев, Ю.И.
topic	Концептуальные проблемы создания систем искусственного интеллекта
topic_facet	Концептуальные проблемы создания систем искусственного интеллекта
publishDate	2011
language	Russian
container_title	Штучний інтелект
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
format	Article
title_alt	Еволюційне моделювання задач багатокритеріальної оптимізації в системі дослідницького проектування морських суден
description	Рассматривается подход и концептуальный базис эволюционного моделирования на современном этапе развития учения о естественной генетике в задачах исследовательского проектирования. Сформулированы теоретические принципы формализации проблемы с использованием достижений интеллектуальных технологий и высокопроизводительных средств вычислений. Приведены примеры реализации разработанного подхода в практических приложениях исследовательского проектирования морских судов. Розглядається підхід і концептуальний базис еволюційного моделювання на сучасному етапі розвитку вчення про природну генетику в задачах дослідницького проектування. Сформульовані теоретичні принципи формалізації проблеми з використанням досягнень інтелектуальних технологій та високопродуктивних засобів обчислень. Наведені приклади реалізації розробленого підходу в практичних застосуваннях дослідницького проектування морських суден.
issn	1561-5359
url	https://nasplib.isofts.kiev.ua/handle/123456789/59832
citation_txt	Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов / А.В. Бухановский, Ю.И. Нечаев // Штучний інтелект. — 2011. — № 3. — С. 42-54. — Бібліогр.: 31 назв. — рос.
work_keys_str_mv	AT buhanovskiiav évolûcionnoemodelirovaniezadačmnogokriterialʹnoioptimizaciivsistemeissledovatelʹskogoproektirovaniâmorskihsudov AT nečaevûi évolûcionnoemodelirovaniezadačmnogokriterialʹnoioptimizaciivsistemeissledovatelʹskogoproektirovaniâmorskihsudov AT buhanovskiiav evolûcíinemodelûvannâzadačbagatokriteríalʹnoíoptimízacíívsistemídoslídnicʹkogoproektuvannâmorsʹkihsuden AT nečaevûi evolûcíinemodelûvannâzadačbagatokriteríalʹnoíoptimízacíívsistemídoslídnicʹkogoproektuvannâmorsʹkihsuden
first_indexed	2025-11-24T17:53:12Z
last_indexed	2025-11-24T17:53:12Z
_version_	1850484780293947392
fulltext	«Искусственный интеллект» 3’2011 42 1Б УДК 004.942 А.В. Бухановский, Ю.И. Нечаев Санкт-Петербургский государственный университет информационных технологий, механики и оптики, Россия nechaev@mail.ifmo.ru Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов Рассматривается подход и концептуальный базис эволюционного моделирования на современном этапе развития учения о естественной генетике в задачах исследовательского проектирования. Сформулированы теоретические принципы формализации проблемы с использованием достижений интеллектуальных тех- нологий и высокопроизводительных средств вычислений. Приведены примеры реализации разработанного подхода в практических приложениях исследовательского проектирования морских судов. Парадигма эволюционного моделирования в системе исследовательского проектирования морских судов Создание формальной системы эволюционного моделирования связано с решением задач многокритериальной оптимизации, описывающих поведение судна в сложной динамической среде с помощью нового подхода к интерпретации динамики внешней среды, осуществляется на основе реальных данных о климатических спектрах морского волнения [1]. В отличие от имеющихся исследований [2-8] разработанная концептуаль- ная модель эволюционного моделирования описывает существенные свойства ис- следуемой проблемной области в рамках нового подхода к решению задач многокри- териальной оптимизации [9-12]. Функциональный блок эаволюционного моделирования определяет построение и интерпретацию математической модели на базе интеллектуаль- ной системы (ИС) исследовательского проектирования. Решение задач многокритериаль- ной оптимизации ведется в рамках формального и строгого определения понятий и закономерностей естественной генетики [13] и формального аппарата теории систем [14]. Проблема оптимизации в задачах моделирования. Проблема оптимизации при мо- делировании поведения нелинейных динамических систем [15-17], особенно неста- ционарных систем, функционирующих в сложной динамической среде [15], [18], пред- ставляет большой теоретический и практический интерес в связи с созданием новой техники и технологий на базе достижений современной компьютерной математики и методов искусственного интеллекта [19]. Среди исследований в области оптимизации сложных динамических систем на современном этапе можно выделить следующие направления исследований [9]: – использование классических методов и моделей, адаптированных с учетом реаль- ных процессов взаимодействия объектов моделирования с внешней средой при различном уровне возмущающих воздействий; – использование нетрадиционных подходов к оптимизации, основанных на дости- жениях интеллектуальных технологий и высокопроизводительных средств вычислений. Эволюционное моделирование задач многокритериальной оптимизации… «Штучний інтелект» 3’2011 43 1Б Оба эти направления связаны с решением задач оптимизации в сложной динами- ческой среде, которая характеризуется НЕ-факторами [20]: неопределенность, неполнота, нелинейность, нестационарность. В этих условиях нельзя сразу отдать предпочтение какой-либо модели и использовать принцип конкуренции [18], позволяющий на основе генерации альтернатив выбирать предпочтительное решение. Принцип конкуренции сформулирован в рамках концепции мягких вычислений [21], объединяющей нечеткий логический базис с нейросетевыми моделями и генетическим алгоритмом (рис. 1). Реализация принципа конкуренции [18] предусматривает использование критериаль- ной базы оценки вариантов решения текущей задачи моделирования, сгенерированных в процессе эволюции объекта моделирования. Среди методов и моделей, используемых при реализации концепции мягких вычислений, следует выделить подход Беллмана – Заде [22], метод иерархий Саати [23], а также более простые оценки, основанные на модели выбора [24], функции выбора [25] и методе эталонов [26]. Поток информации, реализующий концептуальную модель эволюционного моде- лирования в системе исследовательского проектирования при интерпретации решений на основе интеллектуальных технологий и высокопроизводительных вычислительных средств, представлен на рис. 1. Поток информации в мультипроцессорной вычислительной среде Принцип конкуренции Принцип формализации нечетких знаний Реализация конкурирующей вычислительной технологии: параллельная обработка информации на базе традиционных и нейросетевых моделей Построение адаптивных моделей знаний и реализация механизма логического вывода в мультипроцессорной вычислительной среде Рисунок 1 – Организация параллельной обработки информации при функционировании системы исследовательского проектирования морских судов Исследования в области оптимизации показывают, что достаточно эффективным направлением, реализующим новые подходы к этой проблеме, являются эволюцион- ные модели, основанные на использовании генетического алгоритма [10-12], [19]. Суть эволюционного подхода сводится к следующему: – Фиксируется множество объектов Х, параметры которых связаны друг с другом посредством структуры, и необходимо выбрать наилучшие структуры на основе за- данного критерия оптимальности, который формируется на основе свойств объектов и может быть представлен в виде различных моделей, причем каждому объекту мно- жества Х сопоставляется определенное значение критерия F(X). – Множество объектов произвольно, и необходимо построить представление S ис- ходного множества объектов в другом множестве, обладающем некоторой структурой, в том числе и векторным пространством, причем связь между исследуемыми объектами описывается представлением : ХS, а объекты выступают в качестве потенциальных решений задачи поиска экстремума с помощью поискового алгоритма. Бухановский А.В., Нечаев Ю.И. «Искусственный интеллект» 3’2011 44 1Б – Процесс оптимизации на основе эволюционного моделирования состоит в по- строении множества объектов-решений, для которых выполняется следующее условие: X* = arg max F [ 1(S)]. (1) s S Алгоритмы оптимизации представляют собой дискретные процедуры, состоящие в преобразовании исходного множества решений путем отбора наилучших по критерию F (функции пригодности) решений и генетических операторов, основными из которых являются кроссовер и мутация. Функциональные блоки, с помощью которых реализуется процесс обработки ин- формации в задачах эволюционного моделирования, представлены на схеме рис. 2. Здесь выделена последовательность преобразования информации многокритериальной оптимизации – от базы данных ИС исследовательского проектирования – до выдачи практических рекомендаций для принятия обоснованного решения. Информационная среда анализа и интерпретации принятиярешений Анализатор Интерпретатор Распознавание Моделирование Визуализация Функциональные блоки исследовательского проектирования Компоненты информационной поддержки База знаний База данных Рисунок 2 – Функциональные блоки системы интеллектуальной поддержки конструктора, реализующие процедуру эволюционного моделирования на базе технологии интеллектуальных систем Ниже дается краткая характеристика принципов, при построении функциональ- ного блока эволюционного моделирования, использование которых ориентировано на новые поколения систем исследовательского проектирования морских судов с учетом реальных данных о климатических спектрах морского волнения в районе их эксплуа- тации [15], [27]. Принципы обработки информации, обеспечивающие быстродействие алгоритмов эволюционного моделирования в задачах исследовательского проектирования морских судов Повышение эффективности функционирования, достоверности оценки и прогноза исследуемой ситуации в вычислительном комплексе эволюционного моделировния, использующих интеллектуальные технологии, достигается в рамках парадигмы обра- ботки информации в мультипроцессорной вычислительной среде (рис. 3) [18]. Расши- рение функциональных возможностей системы обеспечивается на основе принципов открытости, сложности и конкуренции в рамках концепции мягких вычислений [15], [21]. Эволюционное моделирование задач многокритериальной оптимизации… «Штучний інтелект» 3’2011 45 1Б Нечеткий логический вывод Нейронная сеть Генетический алгоритм База знаний База данных Параметры состояния объекта и внешней среды Исполнительные механизмы Динами- ческий объект Функции принадлежности ДефазификацияМногокритериальный анализ Внешние воздействия Рисунок 3 – Поток информации при реализации концепции мягких вычислений Реализация принципа конкуренции [18] предусматривает использование кри- териальной базы оценки вариантов решения текущей задачи моделирования, сгенери- рованных в процессе эволюции объекта моделирования. Среди методов и моделей, ис- пользуемых при реализации концепции мягких вычислений, следует выделить подход Беллмана – Заде [22], метод иерархий Саати [23]. Необходимо отметить, что подход Беллмана – Заде и метод анализа иерархий реализуют алгоритм многокритериальной оптимизации в нечеткой среде. Причем первый из них основан на построении экспертной матрицы критериев и ограничений с последующей операцией минимаксной композиции, тогда как метод анализа иерархий предполагает построение иерархической структуры в виде матрицы парных сравнений. Решение задачи многокритериальной оптимизации в рамках подхода Беллмана – Заде состоит в достижении цели при заданных нечетких ограничениях. Пусть некото- рая альтернатива х обеспечивает достижение цели со степенью G(х) и удовлетворяет ограничениям со степенью С(х). Тогда степень принадлежности альтернативы х ре- шению задачи равна минимальному из этих чисел, т.е. (функция принадлежности) мо- жет быть интерпретирована в зависимости от числа целей i и ограничений j целей, а также их важности: G(х) = min {G(х), C(х)}. G(х) = min {G1(х), … , Gn(х), C1(х), … , Cm(х)}. (3) G(х) = min {1G1(х), … , nGn(х), 1C1(х), … , mCm(х)}. С учетом введенных обозначений функция D(x) выражается как         .1 ;)(inf )( o o GNy D XXxпри Xxприy x x   (4) В соответствии с определением нечеткое решение рассматриваемой задачи имеет вид: D(x) = min {G(x), C(x)};           .)( ;)(inf),(min )( o C o GNyC D XXxприx Xxприyx x x    (5) Метод анализа иерархий является одним из наиболее распространенных при ин- терпретации данных в ИС [23]. В отличие от подхода Беллмана – Заде, метод иерархий предполагает представление исходной информации в виде относительных весов приз- наков, определяющих текущую ситуацию. Cуть этого метода состоит в реализации Бухановский А.В., Нечаев Ю.И. «Искусственный интеллект» 3’2011 46 1Б последовательности операций анализа иерархической структуры. Выделенные в этой структуре элементарные подзадачи анализируются методом иерархий [23], с помощью которого выделяются приоритеты (веса) признаков в целях выбора наилучших из них с использованием алгебраической теории матриц и экспертных процедур: , ; 1 1 111 max                        mnmn ij m g g W         (6) где W – обратно симметричная матрица значений парных сравнений признаков от- носительно данного атрибута;  – нормированный вектор весов признаков; max – наи- большее собственное значение матрицы W;  – результат определения глобальных приоритетов признаков 1, …, N; N – число признаков; ij ( i=1,…,n, j=1,…,m) – относительный вес i-го признака по j-му атрибуту; gj – относительный вес j-го атрибута. Матрица (6) обладает свойством П – NI = 0, (7) где I – единичная матрица. Контроль надежности выводов, полученных при использовании метода анализа иерархий в задачах принятия решений реализуется с использованием индекса согласован- ности SI . Величина IS определяется для каждой матрицы парных сравнений по вектору приоритетов V . Вектор V вычисляется как собственный вектор матрицы парных сравнений. Процедура оценки индекса согласованности IS осуществляется по соответст- вующему максимальному собственному числу  : )/()( 1nnIS   , (8) где 1n  – число сравниваемых элементов (признаков или альтернатив), т.е. 1n  . Для обратносимметричных матриц, к которым относятся матрица парных сравнений (6), n , поэтому индекс согласованности – величина неотрицательная и конечная. Полученные индексы согласованности сравниваются с соответствующими сред- ними RS = RS(n), которые определяются при случайном выборе решения. Эти значения приведены в табл. 1. Таблица 1 – Критические значения индекса согласованности n 2 3 4 5 6 7 8 9 )(nRS 0,1 0,58 0,90 1,12 1,24 1,32 1,41 1,45 Оценкой надежности метода парных сравнений является отношение согласован- ности Sd : SSS RId / . (9) Если величина dS не превышает 0,2, то полученные результаты являются до- стоверными. Особенность этого метода состоит в тoм, что результаты парных сравнений для двух сложных объектов достаточно сложно передать в виде точных цифр. Назначение цифр нередко кажется искусственным и достаточно произвольным. Действительно, представление результата сравнения в виде разумных цифр требует глубокого по- нимания задачи – насколько свойства рассматриваемых объектов влияют на дости- жение поставленной цели. Эволюционное моделирование задач многокритериальной оптимизации… «Штучний інтелект» 3’2011 47 1Б При анализе альтернатив в сложных ситуациях находят применение нечеткие оценки и граф-интерпретации, позволяющие рассматривать формирование действий конструктора в виде комбинаторных задач на графах. Область допустимых решений в этом случае определяется уровнем нечеткости графа, соответствующим нечеткой оценке. Задаваясь такой оценкой, можно определить область допустимых решений, а затем в этой области вести поиск оптимальных решений на графах [15]. Путь на графе для конкретной ситуации объединяет совокупность вершин с опре- деленным порядковым номером. С каждым таким путем сопоставляются оценки, опреде- ляющие риск и временные затраты. Обозначив S = (S1,…,Sm) – множество всех путей в граф-модели плана реализации решения, можно установить экстремальный путь, опреде- ляемый соотношением: S*= index m min{G(S1),…, G(Sm), (10) где G(S1),…, G(Sm) – функция принадлежности множества путей. Концепция эволюционного моделирования в системе исследовательского проектирования Формальное описание общей модели эволюционного моделирования реализуется с помощью генетического алгоритма GA [11], [12]: GA = (Po, L, I, S, R, F, t), (11) где Po = (p1,…,pL); pL – решение задачи, представленное в виде хромосомы, кодиро- вание которой осуществляется с помощью кода Грея [16]; L – целое число (размер популяции); I – целое число (длина каждой хромосомы в популяции); R – отображение, определяющее рекомбинацию (кроссовер (crossover), мутация (mutation); F – функция оптимальности (fitness function); t – критерий остановки. При использовании GA в задачах оптимизации простой рандомизированный перебор при поиске минимума по методу Монте-Карло можно заменить на хранение популяции лучших с точки зрения функционала объектов и добавления новых объектов посредством мутации одного объекта, либо посредством кроссовера – обмена подоб- ными частями у двух случайных объектов. Мутация – это почти полный аналог случай- ного шага в методе Монте-Карло, а кроссовер и популяция привлечены из биологии, где естественный отбор оптимизирует генотип [13]. Поток информации при реали- зации GA в задаче оптимизации представлен на рис. 4. P(x)={i(x)\|(i=1,…,n)}. (12) Рисунок 4 – Парадигма преобразования информации при реализации GA Бухановский А.В., Нечаев Ю.И. «Искусственный интеллект» 3’2011 48 1Б Современные исследования GA в основном связаны с моделированием как средст- вом изучения поведения алгоритмов и придания им новых свойств. Структурно-ин- вариантный анализ позволяет применить к моделям GA практически тот же метод декомпозиции, что и для динамических систем. Из рисунка видно, что поиск более совершенных структур достигается с помощью GA, преобразующего текущую популяцию (БЗ). Это преобразование обеспечивается за счет селективного смещения в пользу более устойчивых структур. Таким образом, цель GA состоит в абстрактном и формальном объяснении процессов эволюции и адаптации, а также создания аппарата проектирования искусственных программных систем, содержащих механизмы эволюции естественных систем. GA отличаются от других оптимизационных и поисковых процедур. Это от- личие состоит в следующем [11], [12], [19]: – работа не с параметрами, а с закодированными множествами; – осуществление поиска из популяции точек, а не из единственной точки; – использование для оценки информации целевой функции, а не ее приращений; – использование вероятностных, а не детерминированных правил. Основными генетическими операторами в задачах эволюционного моделирова- ния являются кроссовер и мутация. Кроссовер (скрещивание) моделирует передачу наследственности хромосомами и обуславливает целенаправленное приближение хро- мосом к оптимальному решению. Однако использование классических операторов скре- щивания (одноточечных или многоточечных кроссоверов) в отдельных случаях является малоэффективным. В работе [10] предложены другие операторы рекомбинации (рис. 5), уменьшающие число переборов и время сходимости алгоритма оптимизации.                 5 4 3 2 1 a a a a a                 5 4 3 2 1 b b b b b                 5 4 3 2 1 c c c c c                 5 4 3 2 1 d d d d d                 3 2 1 2 1 c c c a a                 3 2 1 2 1 b b b c c                 2 1 3 2 1 d d a a a                 2 1 3 2 1 b b d d d H 11 H 12 H 21 H 22 H 3 H 4 H 5 H 6 Рисунок 5 – Оператор рекомбинации: аi bi ci di – значения генов Одна из проблем эволюционного моделирования состоит в построении решения, позволяющего избежать попадания в локальный экстремум. Эффективная процедура выхода из локального экстремума связана с хромосомной мутацией (хромосомной перестройкой) [10]: дефишенси (концевые нехватки хромосом), дупликация (удвоение участков хромосом), инверсия (перестройка части генов в обратном порядке), транс- локация – перенос части генов в той же хромосоме на новое место (образование изо- хромосомы) (рис. 6). Эволюционное моделирование задач многокритериальной оптимизации… «Штучний інтелект» 3’2011 49 1Б                 5 4 3 2 1 b b a a a                 2 1 5 4 3 a a b b a Транслокация хромосомы Результат транслокации Рисунок 6 – Оператор транслокации Данные типы перестроек играют важную роль в естественной эволюции, поз- воляя переходить к другим видам [10]. Построенные на их основе операторы мутации GA позволяет обходить локальные экстремумы. Комбинация операторов кроссовера и мутации образуют схему замещения М в виде вектор-функции М(Р), компонентами которой являются квадратичные формы: М(Р) =<p(t)TMp(t), [S(1)p(t)]TM S(2)p(t),…, [S(k)p(t)]TM S(k)p(t),…,[S(n)p(t)]TM S(n)p(t)>, (13) где М – матрица замещения; S(k) – матрица перестановок, зависящие от элемента популяции k. Групповая структура на множестве Х коммутирует со схемой замещения и задается матрицами S(k) в виде линейной группы матриц. Инвариантность схемы замещения относительно группы определяет симметрию GA. Другим эффективным направлением в совершенствовании методов оптимизации сложных систем, функционирующих в нестационарной динамической среде, является использование преимуществ нейросетевого логического базиса. Реализация этих пре- имуществ привела к разработке теории нейро-эволюционного моделирования, соче- тающего массовый параллелизм и нелинейное преобразование информации нейронных сетей с вычислительной технологией эволюционного моделирования. В рамках такой интеграции находят применение ансамбли нейронных сетей, а также интегрированные нейронные сети, использующие преимущества RBF-сетей, многослойного персептрона и самоорганизующихся карт Кохонена [28]. Последовательность операций, обеспечивающих процедуры эволюционного моделирования Рассмотрим особенности задачи эволюционного моделирования. Пусть Х – некоторое множество объектов (особей), среди которых надо найти оптимальный объект, а S – множество двоичных строк составленных из 0 или 1. Заданы отобра- жения F1:Х R, F2:ХS и F3:SХ, (14) где S – множество действительных чисел. Функцию F1 в GA называют функцией приспособленности. Задан оператор М1:S S, (15) переводящий s1 S в s2 S путем инверсии в выбранных позициях. Бухановский А.В., Нечаев Ю.И. «Искусственный интеллект» 3’2011 50 1Б Выбор позиций, подвергаемых инверсии, недетерминирован. Введем оператор мутации М2:ХХ, (16) определяемый как М2(х)=F3(М1(F2(х))), х Х. (17) Операцию кроссовера определим следующим образом. Пусть s1 S в s2 S, а P – множество номеров позиций, в которых строки различаются. Порождаемая при вы- полнении кроссовера строка обладает следующими свойствами: – строка может совпадать со строками s1 и s2 в позициях, не вошедших в р; – приблизительно половина позиций, вошедших в р, совпадает с позициями в строке s1, а другая половина позиций из P совпадает с позициями в строке s2. Требуется найти х Х такой, что F1(х)=max{F1(z)\| zX}, (18) т.е. ставится задача поиска строки с максимальным значением функции приспособлен- ности. Применяя последовательность «отбор – мутация» (рис. 7), можно направлять эволюцию элементов популяции к наиболее хорошим точкам пространства поиска. Формирование начальной популяции Вычисление мер пригодности Определение элитной хромосомы Условие окончания поиска Вывод решения Отбор хромосом для репликации Операция пересечения Мутация Объединение Формирование новой популяции Рисунок 7 – Обобщенная блок-схема генетического алгоритма При этом отбор производит селекцию подходящих элементов, а кроссовер и му- тация накладывают стохастический шум на процесс эволюции, осуществляя переход к исследованию новых областей и точек пространства. Нечеткая формальная система, обеспечивающая процедуры эволюционного моделирования Композиционная модель нечеткого вывода в динамической базе знаний ИС ис- следовательского проектирования описывает связь всех возможных состояний логи- ческой системы с управляющими воздействиями и формально записывается в виде (X,R,Y), где X={х1,…,xn}; Y={y1,…,ym} – базовые множества, на которых заданы входы Аi и выходы Bi нечеткой системы; R – нечеткое соответствие «вход – выход», которое строится на основе формализации нечетких стратегий. Принятие решений при функ- ционировании нечеткой системы знаний осуществляется на основе модели [15]: «if А1– then В1, else if A2 then B2,…, else if AN then BN». (19) Эволюционное моделирование задач многокритериальной оптимизации… «Штучний інтелект» 3’2011 51 1Б Здесь A1,…,AN – нечеткие подмножества, определенные на базовом множестве Х, а B1,…,BN – нечеткие подмножества из базового множества Y. Эти нечеткие подмно- жества задаются c помощью функций принадлежности Ai(x), Bi(y). (xX, yY).     n i m j iiiBiA yxyxBAR 1 1 )},()()({  (20) или )),(),(min()()(),( yxyxyx BABAR   (21) где A(x), B(y) – ФП элементов х, у множествам А и В. В качестве нечеткой импликации при реализации механизма логического вы- вода в ИС использованы алгоритмы Мамдани и Сугено [15], [29]. Алгоритмы преобразования информации при реализации механизма логического вывода в ИС представлены на основе продукционных моделей [15], [27]: <If X, then Y, else Z>; (22) (X  Y (Z)), где Х, Y, Z – нечеткие множества, определенные на универсальных мно- жествах U, V, W; множества X, Y, Z интерпретируются как нечеткий вход и нечет- кий выход некоторой системы, отношения между которыми определяются моделью нечеткой системы. При интерпретации модели (22) используются различные встроенные процедуры, основанные на применении аппарата статистического анализа, методов математического моделирования, методов качественного исследования дифференциальных уравнений на фазовой плоскости и др. Наряду с методами традиционной математики и аппаратом не- четкой логики здесь находят также широкое применение теория ИНС [28] и GA [11], [12]. Механизм, обеспечивающий логику функционирования и выработку решений по мере поступления информации о параметрах ДО и внешней среды, основан на выводе решений с помощью формальной процедуры [15], [27]: Fi : Sk (ti)  Uj (23) ( k =1,…,n; j = 1,…,J; i = 1,…,N), где Sk(ti) – ситуация в момент времени ti ; Uj – решение; Fi – множество правил. Практическое приложение. Рассмотрим применение нейро-эволюционного мо- делирования в задаче контроля динамики сложного объекта с использованием концепции нейро-нечеткой системы ANFIS [30]. Потенциально настраиваемыми параметрами моде- ли нечеткого вывода по Сугено в базе знаний адаптивной ИС, реализующей поддержку нейро-эволюционного моделирования, являются параметры функций принадлежности и коэффициенты в функциях, вычисляющих выход для нечетких логических правил. Необходимым условием применения GA является представление параметров за- дачи в форме хромосом, т.е. в виде наборов ген, которые могут принимать различные значения (аллели). В данном случае параметрами задачи является набор коэффициен- тов системы нечеткого вывода: pi, qi и ri. [16]. Для характеристики параметров системы применялось двоичное кодирование. Каждый параметр кодировался в виде 16 двоич- ных значений. Определялась допустимая область значений каждого коэффициента. Затем данная область разбивалась на 216 равных интервала, каждому из которых присваивался номер для кодирования в виде генов с применением кодов Грея. Длина получившейся хромосомы равна 16×N, где N – число кодируемых параметров системы. В задаче подбора параметров нечеткой системы шаги GA несколько отличались от шагов классической реализации. Рассмотрим эти шаги. Инициализация заключается Бухановский А.В., Нечаев Ю.И. «Искусственный интеллект» 3’2011 52 1Б в случайном выборе заданного количества хромосом. Исходная популяция была по- лучена посредством случайной модификации параметров системы, определенной ме- тодом экспертной оценки и кодирования их в виде хромосом. Начальная популяция, так же как и все последующие, представлена 100 хромосомами. Селекция хромосом заключалась в выборе тех хромосом, которые будут участвовать в создании потомков для следующей популяции. При разработке системы управления сложным ДО в нестационарной динами- ческой среде построение такой функции является нетривиальной задачей. Отбор хро- мосом осуществлялся по следующему принципу. Выбирается случайная хромосома и преобразуется в набор параметров системы нечеткого вывода. После чего производится имитационное моделирование поведения ДО. При этом в качестве параметров системы управления используется набор параметров, полученных из тестируемой хромосомы. Если параметры отвечают заданным критериям – хромосома отбирается для создания следующей популяции, в противном случае тестированию подвергается следующая слу- чайная хромосома. Такая селекция хромосом полностью отвечает принципу естествен- ного отбора и легко реализуема при наличии модели процесса. Для получения более адаптированных к различным условиям популяции хромосом имитационное моделиро- вание каждый раз проводилось с различными внешними условиями и характеристи- ками ДО. С целью уменьшения вероятности случайного отбора «плохой» хромосомы имитационное моделирование можно проводить несколько раз для одной хромосомы. На рис. 8 приведен график, отображающий результат уменьшения количества неудачных решений для каждой следующей популяции. Рисунок 8 – Результат уменьшения числа неудачных решений с ростом числа циклов обучения Для сравнения на рис. 8 горизонтальной линией обозначено количество неудач- ных решений для начального варианта системы, полученного на основе экспертных оценок. Как видно из приведенного графика, применение GA для задачи адаптации системы нечеткого вывода дает лучшие результаты по сравнению с подобранными на основе экспертных оценок параметрами на базе априорной информации. Нахождение хороших решений происходит за сравнительно небольшое время, что было достигнуто путем применения широкого набора оптимизационных техник программирования, в том числе и распараллеливания алгоритма. Применение генетических операторов. Для формирования новой популяции над отобранными хромосомами производится ряд генетических операций. В данной задаче применяются два основных оператора – скрещивание (crossover) и мутация. При этом скрещивание происходит при получении 100% новых хромосом. Мутация же произво- дится лишь над очень небольшим количеством ген. Оценивание приспособленности хромосом в популяции (так же, как и селекция) производится с помощью функции при- способленности, определяемой по общему количеству удачных решений для данной популяции. Эволюционное моделирование задач многокритериальной оптимизации… «Штучний інтелект» 3’2011 53 1Б Литература 1. Estimation of extreme wave heights / L.J. Lopatoukhin, V.A. Rozhkov, V.E. Ryabinin [etc.] // JCOMM Technical Report, WMO/TD. – 2000. – № 1041. – P. 1-12. 2. Ашик В.В. Проектирование судов / Ашик В.В. – Л. : Судостроение, 1985. 3. Гайкович А.И. Основы теории проектирования сложных систем / Гайкович А.И. – Санкт-Петербург : МОРИНТЕХ, 2001. 4. Захаров И.Г. Теория компромиссных решений при проектировании корабля / Захаров И.Г. – Л. : Судостроение, 1987. 5. Нарусбаев А.А. Введение в теоpию обоснования проектных решений / Нарусбаев А.А. – Л. : Судостроение, 1976. 6. Пашин В.М. Оптимизация судов / Пашин В.М. – Л. : Судостроение, 1983. 7. Худяков Л.Ю. Исследовательское проектирование кораблей / Худяков Л.Ю. – Л. : Судостроение, 1980. 8. Шауб П.А. Методы функционального проектирования в анализе и синтезе сложных систем / П.А. Шауб // Морская радиоэлектроника. – 2002. – № 1. – С. 44-48. 9. Богатырев М.Ю. Структурно-инвариантный анализ в информационно-управляющих системах / М.Ю. Богатырев // Управление и информационные технологии УИТ-2003 : труды всероссийской научной конференции, 2003. – Т. 2. – С.131-136. 10. Комарцова Л.Г. Двухэтапный алгоритм обучения нейронной сети на основе генетического поиска / Л.Г. Комарцова // Нейрокомпьютеры: разработка, применение. – 2001. – № 1. – С. 3-9. 11. Курейчик В.М. Генетический алгоритм: обзор и состояние / В.М. Курейчик // Новости искусст- венного интеллекта. – 1998. – № 3. – С. 14-63. 12. Скурихин A.Н. Генетические алгоритмы / А.Н. Скурихин // Новости искусственного интеллекта. – 1995. – № 4. – С. 6-46. 13. Goldberg D.E. Genetic and evolutionary algorithms in the real world / D.E. Goldberg // IIIiGAL Report. – 1999.– № 99013. 14. Месарович М. Общая теория систем: математические основы / М. Месарович, Я. Такахара. – М : Мир, 1978. 15. Бортовые интеллектуальные системы. Часть 2. Корабельные системы. – М. : Радиотехника, 2006. 16. Калюжный Д.А. Нейро-нечеткий контроль динамики летательного аппарата при посадке в морских условиях / Д.А. Калюжный, Ю.И. Нечаев // Информационно-измерительные и управляющие системы. – 2009.– Т. 2, № 2. – С. 34-40. 17. Нечаев Ю.И. Нейро-нечеткие технологии в интеллектуальной системе контроля посадки ле- тательных аппаратов корабельного базирования / Ю.И. Нечаев // Сборник Научных трудов ХI Всероссийской научно-технической конференции по нейроинформатике «Нейроинформатика- 2009». – М. : МИФИ, 2009. – С. 209-278. 18. Нечаев Ю.И. Математическое моделирование в бортовых интеллектуальных системах реального времени / Ю.И. Нечаев // Труды 5-й Всероссийской конференции «Нейроинформатика-2003». – М. : МИФИ, 2003. – Часть 2 : Лекции по нейроинформатике. – С. 119-179. 19. Нечаев Ю.И. Искусственный интеллект: концепции и приложения / Нечаев Ю.И. – Санкт- Петербург : ГМТУ, 2002. 20. Нариньяни А.С. Не-факторы: неточность и недоопределенность – различие и взаимосвязь / А.С. Нари- ньяни // Известия РАН. Теория и системы управления. – 2000. – № 5. – С. 44-56. 21. Zadeh L. Fuzzy logic, neural networks and soft computing / L. Zadeh // Соmmutation on the ASM-1994. – Vol. 37, № 3. – P. 77-84. 22. Беллман Р. Принятие решений в расплывчатых условиях / Р. Беллман, Л. Заде. – М. : Мир, 1976. 23. Саати Т. Принятие решений. Метод анализа иерархий / Саати Т. – М. : Радио и связь, 1993. 24. Воробьева Г.И. Модели выбора оптимальных форматов представления объектов в базах данных удаленного доступа / Г.И. Воробьева // Труды Х всероссийской конференции «Телематика-2003». – Санкт-Петербург, 2003. – Т. 1. – С. 233-235. 25. Юдин А.Д. Пополнение и синтез знаний в задачах теории принятия решений / А.Д. Юдин, Д.Б. Юдин // Изв. РАН. Техническая кибернетика. – 1992. – № 5. – С. 28-49. 26. Groppen V.O. Smart computing principles. Models and algorithms / V.O. Groppen // Proceedings of the fifth conference on evolutionary methods of design, optimization and control with applications to industrial and social problems. – Spain, Barselona, 2003. – P. 133-134. 27. Интеллектуальные системы в морских исследованиях и технологиях / [Александров В.Л., Матлах А.Т., Нечаев Ю.И., Поляков В.И., Ростовцев Д.М.] – Санкт-Петербург : ГМТУ, 2001. Бухановский А.В., Нечаев Ю.И. «Искусственный интеллект» 3’2011 54 1Б 28. Уоссермен Ф. Нейрокомпьютерная техника: теория и практика / Уоссермен Ф. – М. : Мир, 1992. 29. Asai K. Applied fuzzy system / Asai K., Sugeno M., Terano T. – New York : Academic Press, 1994. 30. Jang J.S.R. ANFIS: Adaptive-Network-Based Fuzzy Inference Systems / J.S.R. Jang // IEEE Trans. On systems, man and cybernetics. – 1993. – Vol. 23. – P. 665-685. 31. Романов С.В. Вопросы выбора альтернатив в задачах распознавания при структурно-графическом анализе данных / С.В. Романов // Сборник докладов Международной конференции по мягким вычислениям и измерениями SCM-2000. – Санкт-Петербург, 2000. – T. 1. – С. 108-112. Literatura 1. Lopatoukhin L.J. JCOMM Technical Report, WMO/TD. № 1041. 2000. P. 1-12. 2. Ashik V.V. Proektirovanie sudov. L.: Sudostroenie. 1985. 3. Gajkovich A.I. Osnovy teori iproektirovanija slozhnyh system. Sankt-Peterburg: MORINTEH. 2001 4. Zaharov I.G. Teorija kompromissnyh reshenij priproektirovanii korablja. L.: Sudostroenie. 1987. 5. Narusbaev A.A. Vvedenie v teopijuo bosnovanija proektnyh reshenij. L.: Sudostroenie. 1976. 6. Pashin V.M. Optimizacija sudov. L.: Sudostroenie. 1983. 7. HudjakovL.Ju. Issledovatel’skoe proektirovanie korablej. L.: Sudostroenie. 1980. 8. Shaub P.A. Morskaja radiojelektronika. № 1. 2002. S. 44-48. 9. BogatyrevM.Ju. Upravlenie iinformacionnye tehnologii UIT-2003: trudy vserossijskoj nauchnoj konferencii. T. 2. 2003. S. 131-136. 10. Komarcova L.G. Nejrokompjutery: razrabotka, primenenie. № 1. 2001. S. 3-9. 11. Kurejchik V.M. Novosti iskusstvennogo intellekta. № 3. 1998. S. 14-63. 12. Skurihin A.N. Novostii skusstvennogo intellekta. № 4. 1995. S. 6-46. 13. Goldberg D.E. Genetic and evolutionary algorithms in the real world. IIIiGAL Report. № 99013. 1999. 14. Mesarovich M. Obshhaj ateorija sistem: matematicheskie osnovy. M: Mir. 1978. 15. Bortovye intellektual’nye sistemy. Chast’ 2.Korabel’nye sistemy. M.: Radiotehnika. 2006. 16. KaljuzhnyjD.AInformacionno-izmeritel’nye I upravljajushhie sistemy. T 2. № 2. 2009. S. 34-40. 17. NechaevJu.I. SbornikNauchnyhtrudov HI Vserossijskoj nauchno-tehnicheskoj konferencii po nejroinformatike «Nejroinformatika-2009». M.: MIFI. 2009. S. 209-278. 18. NechaevJu.I. Trudy 5-j Vserossijskoj konferencii «Nejroinformatika-2003».Chast’ 2: Lekcii po nejroinformatike. M.: MIFI. 2003. S. 119-179. 19. NechaevJu.I. Iskusstvennyj intellekt: koncepcii i prilozhenija. Sankt-Peterburg: GMTU. 2002. 20. Narin'jani A.S. Izvestija RAN. Teorija I sistemy upravlenija.№ 5. 2000. S 44-56 21. Zadeh L. Sommutation on the ASM-1994. Vol. 37. № 3. P. 77-84. 22. Bellman R. Prinjatie reshenij v rasplyvchatyh uslovijah. M.: Mir. 1976. 23. Saati T. Prinjatie reshenij. Metod analizaierarhij. M.: Radio isvjaz’. 1993. 24. Vorob'eva G.I. Trudy Xvserossijskoj konferencii «Telematika-2003». Sankt-Peterburg. T. 1. 2003. S. 233-235. 25. Judin A.D. Izv. RAN. Tehnicheskaja kibernetika. № 5. 1992. S. 28-49. 26. Groppen V.O. Proceedings of the fifth conference on evolutionary methods of design, optimization and control with applications to industrial and social problems. Spain, Barselona. 2003. P. 133-134. 27. Intellektual’nyesistemy v morskihissledovanijahitehnologijah. Sankt-Peterburg: GMTU. 2001. 28. Uossermen F. Nejrokomp'juternajatehnika: teorijaipraktika.M.: Mir. 1992. 29. Asai K. Applied fuzzy system. New York: Academic Press. 1994. 30. Jang J.S.R. IEEE Trans. On systems, man and cybernetics. Vol. 23. 1993. P. 665-685. 31. Romanov S.V. Sbornik dokladov Mezhdunarodnoj konferencii po mjagkim vychislenijam i izmerenijami SCM-2000. Sankt-Peterburg. T. 1. 2000. S. 108-112. А.В. Бухановський, Ю.І. Нечаєв Еволюційне моделювання задач багатокритеріальної оптимізації в системі дослідницького проектування морських суден Розглядається підхід і концептуальний базис еволюційного моделювання на сучасному етапі розвитку вчення про природну генетику в задачах дослідницького проектування. Сформульовані теоретичні принципи формалізації проблеми з використанням досягнень інтелектуальних технологій та високо- продуктивних засобів обчислень. Наведені приклади реалізації розробленого підходу в практичних засто- суваннях дослідницького проектування морських суден. Статья поступила в редакцию 29.07.2011.

Эволюционное моделирование задач многокритериальной оптимизации в системе исследовательского проектирования морских судов

Institution

Similar Items