– каф. «Управление и информатика в технических системах»

Научный руководитель – д. т.н., проф. , каф. «Управление и информатика в технических системах»

Москва 2010

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

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

Рис 1. Принципиальная схема классификатора слабо структурированных данных

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

Для целенаправленного поиска нейросетевых реализаций классификатора были сформированы следующие требования:

НЕ нашли? Не то? Что вы ищете?

§  Инвариантность к размерностям данных;

§  Размерность выходных данных не должна зависеть от размерности входных данных;

§  Компоненты векторов входных данных должны быть представимы действительными числами;

§  Сеть должна удовлетворительно работать с зашумленными входными данными;

§  Время обучения сети должно быть минимально возможным;

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

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

Рис. 2 Алгоритм первого этапа обучения сети

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

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

Рис. 3 Алгоритм второго этапа обучения сети

В качестве тестовой задачи рассматривалась задача классификации 3-х мерных данных, причем количество данных относящихся к разным данным было различным. Всего использовалось 3 класса данных: первый содержал 125 векторов, второй – 155 векторов, третий – 90 векторов (рис. 4). В ходе численного эксперимента классы кодировались в двоичной системе (1 означала принадлежность к классу, а 0 – отсутствие принадлежности). В проведенных исследованиях для генерации нормально распределенных чисел использовался алгоритм, предложенный Пьером Л'Экайером (Pierre L'Ecuyer), поскольку данный алгоритм по своему качеству намного выше стандартного линейного конгруэнтного генератора.

В экспериментах использовалась сеть со структурой 10-10-самоорганизующихся нейрона во входном слое, 10 нейронов во входном слое персептронной компоненты 8 нейронов в скрытом слое и 3 нейрона в выходном слое). Функция фаззификации была задана в форме обобщенной функции Гаусса.

Рис. 4 Распределение тестовых трехмерных данных

На 1000 тестовых данных, не участвовавших в обучении, было получено только 8 ошибочных решений об отнесении к конкретным кластерам. Для сравнения самостоятельный многослойный персептрон при классификации допустил 13 ошибок, а одиночная сеть Кохонена 57 ошибок.

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

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

§  Обеспечение регулировки параметров настройки нейронных сетей (выбор функции активации, критериев останова, количества слоев и нейронов в каждом слое и проч.)

§  Обеспечение наглядности представления данных и результатов

§  Обеспечение возможности выбора различных топологий нейронных сетей для их изучения

§  Обеспечение возможности легкой интеграции модулей ядра в другие ИС

§  Масштабируемость

§  Кроссплатформенность

Модуль ядра представляет собой динамическую библиотеку, написанную на языке программирования ISO/ANSI C++.

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

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

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

Список литературы:

1. А, , . Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP. – СПб.: Изд-во БХВ-Петербург, 2007.

2. Нейронные сети: полный курс. 2 изд.: пер. с англ. – М.: Изд. дом «Вильямс», 2006. – 1104 с.

3. Нейронные сети для обработки информации. М.: Финансы и статистика, 2004. – 344 с.

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

5. Волчихин В. И., Иванов : быстрое обучение искусственных нейронных сетей. Пенза: Изд-во Пенз. гос. ун-та, 2000. – 40 с.

Некоммерческая организация «Ассоциация московских вузов»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный технологический университет «Станкин »

Научно-информационный материал

Подраздел: 40.7.2.3.

НИМ 2.3.18.

СЕТЕВАЯ СИСТЕМА ТЕСТИРОВАНИЯ

Смирнов 1537

Москва 2010

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

Основная цель работы – программная разработка сетевой интерактивной системы организации тестирования учащихся. Среди основных задач, решаемых при разработке: 1) предоставление «учителю» удобной среды конструирования тестов с возможностью их загрузки в Интернет-базу данных; 2) предоставление пользователю-«ученику» возможности загрузки теста из базы данных в режиме прохождения теста; 3) свободная передача тестов от пользователя к пользователю с дальнейшей возможностью их использования и изменения.

Система тестирования реализована в форме Flash-приложения с элементами Adobe AIR – для работы с локальными файлами, для реализации связи с сервером используется AMF-php. Поддерживается HTML-разметка, позволяющая быстро, удобно и точно форматировать текстовую информацию при выводе на экран.

Информационное ядро Системы тестирования – SQL-база данных, обеспечивающая хранение информации об учителях, учениках, составе тестов (разделы, вопросы и варианты ответов). Операции с данными, хранящимися в SQL-базе данных, выполняются с использованием SQL-запросов, через AMF-php. При создании тестов поддерживается вставка таблиц, изображений, звуковых файлов, видео - и flash-объектов. Особое внимание уделено разграничению уровней доступа к информации базы данных по выделенным категориям пользователей (учитель, ученик и др.).

В Системе тестирования реализованы следующие режимы работы: 1) создание теста; 2) прохождение теста; 3) просмотр и анализ результатов тестирования; 4) создание/удаление тестов из локальной базы данных; 5) поиск и загрузка тестов из Интернет БД.

Существенное преимущество разработанной Системы тестирования – предоставление пользователю возможности работы, как в Интернет-режиме, так и в локальном режиме (с использованием локальной базы данных, копирование которой позволяет пользователям свободно обмениваться созданными тестами). Использование разработанной Системы тестирования должно способствовать совершенствованию форм контроля уровня знаний учащихся, повышению уровня обученности. Система тестирования может быть использована в работе любого образовательного учреждения, а также как средство самообразования.

Некоммерческая организация «Ассоциация московских вузов»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный технологический университет «Станкин »

Научно-информационный материал

Подраздел: 40.7.2.3.

НИМ 2.3.19.

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

– каф. «Управление и информатика в технических системах»

Научный руководитель – д. т.н., проф. , каф. «Управление и информатика в технических системах»

Москва 2010

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

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

·  обеспечивал бы руководство деятельностью команды;

·  управлял бы задачами отдельного разработчика и команды в целом;

·  указывал бы, какие артефакты следует разработать;

·  предоставлял бы критерии для отслеживания и изменения продуктов и функционирования проекта.

Наличие хорошо определенного и хорошо управляемого процесса – в этом отличие сверхпродуктивных проектов от неудавшихся. Использование унифицированного процесса (подхода) разработки ПО позволит решить множество современных проблем создания больших и сложных программных продуктов.

Унифицированный процесс – это больше чем единичный процесс, это обобщенный каркас процесса, который может быть специализирован для широкого круга программных систем, различных областей применения, уровней компетенции и размеров проекта. Унифицированный процесс компонентно-ориентирован, т. е. создаваемая программная система строится на основе программных компонентов, связанных хорошо определенными интерфейсами (UML – Unified Modeling Language – унифицированный язык моделирования).

Унифицированный процесс разработки ПО основан на трех основных идеях – унифицированный процесс управляется вариантами использования, т. е. частью функциональности системы, необходимой для получения пользователем значимого для него, ощутимого и измеримого результата (например, взаимодействие «человек-банкомат»), унифицированный процесс ориентирован на архитектуру, т. е. включает в себя наиболее важные статические и динамические аспекты системы, унифицированный процесс является итеративным и инкрементным.

Управляемый итеративный процесс имеет множество преимуществ:

·  управляемая итерация ограничивает финансовые риски затратами на одно приращение;

·  управляемая итерация снижает риск непоставки продукта на рынок в запланированные сроки;

·  управляемая итерация ускоряет темпы процесса разработки в целом.

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

На графике зависимости рисков от времени (рис. 1.) видно, что при итеративной разработке уменьшение опасных рисков начинается с самых ранних итераций.

Рис. 1. Серьезные риски при итеративной и водопадной разработках

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

Ведущей методологией, в которой инструментально поддерживаются все этапы жизненного цикла разработки программного обеспечения, является методология Rational Unified Process (RUP), созданная компанией Rational Software. Она опирается на проверенные практикой методы анализа, проектирования и разработки ПО и методы управления проектами. RUP обеспечивает прозрачность и управляемость процесса и позволяет создавать ПО в соответствии с требованиями заказчика на момент сдачи программного обеспечения, а также в соответствии с возможностями инструментальных средств поддержки разработки. Основа RUP — итеративный процесс разработки.

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

Список литературы:

1.  Дж. Рамбо. Унифицированный процесс разработки программного обеспечения. — СПб.: Изд-во Питер, 2002. — 496 с.

2.  Уокер Ройс. Управление проектами по созданию программного обеспечения. Унифицированный подход. — Изд-во Лори, 2002. — 431 с.

3.  Скотт Амблер. Гибкие технологии: экстремальное программирование и унифицированный процесс разработки. — СПб.: Изд-во Питер, 2005. — 412 с.

4.  Мартин, Ньюкирк, Косс. Быстрая разработка программ: принципы, примеры, практика. — М.: Изд-во Вильямс, 2004. — 752 с.

Некоммерческая организация «Ассоциация московских вузов»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный технологический университет «Станкин »

Научно-информационный материал

Подраздел: 40.7.2.3.

НИМ 2.3.20.

ЯЗЫК XML: СОСТАВ СТАНДАРТОВ И ПРИМЕНЕНИЕ В ИНФОРМАЦИОННЫХ СИСТЕМАХ, ЭЛЕКТРОННОМ БИЗНЕСЕ И УПРАВЛЕНИИ ПРОИЗВОДСТВОМ

, – каф. «Информационные системы»

Научный руководитель – д. т.н., проф. , каф. «Информационные системы»

Москва 2010

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

Cтандарт XML является обобщенным форматом данных. XML (англ. eXtensible Markup Language — расширяемый язык разметки) — рекомендованный Консорциумом Всемирной паутины язык разметки, фактически представляющий собой свод общих синтаксических правил. Он был специфицирован в 1998 году.

Целью создания XML было обеспечение совместимости при передаче структурированных данных между разными системами обработки информации, особенно при передаче таких данных через Интернет. Можно дать следующее определение понятия XML — это иерархическая структура, предназначенная для хранения любых данных, визуально структура может быть представлена как дерево.

Стандарт XML можно разделить на три группы. В первую группу попадают базовые стандарты, с помощью которых формируются XML-документы. Такими спецификациями принято считать рекомендации консорциума W3C: XML 1.0 и XML 1.1, Namespaces in XML 1.0 и 1.1, Canonical XML, XLink (XML Linking Language), XML Base, XML Infoset, XML Schema Part 1: Structures и XML Schema Part 2: Datatypes, XPath, XPointer, а также стандарт OASIS RELAX NG.

Вторая группа - это стандарты, относящиеся к обработке XML-документов: XSLT, DOM, XQuery, SOAP, WSDL и некоторые другие.

Третий класс XML-спецификаций составляют XML-приложения, или словари: XHTML, Docbook, XSL-FO, SVG, VoiceXML, MathML, SMIL. Словари, основанные на XML, сами по себе формально описаны, что позволяет программно изменять и проверять документы на основе этих словарей, не зная их семантики, то есть, не зная смыслового значения элементов.

Целесообразно расширить данную классификацию и добавить еще один вид XML-спецификаций - отраслевые XML-форматы, предназначенные для описания какой-либо конкретной отрасли, области бизнеса, хозяйственной или иной деятельности. В качестве примеров можно привести ACORD (Association for Cooperative Operations Research and Development) - страхование, ARTS (Association for Retail Technology Standards) - розничная торговля, HL7 (Health Level Seven) - здравоохранение, RosettaNet -поставки, UIG (Utility Industry Group) - коммунальные услуги, LISA (Localization Industry Standards Association) - переводческая деятельность, HR-XML - человеческие ресурсы, MISMO (Mortgage Industry Standards Maintenance Organization) – недвижимость, OFX/IFX (Open Financial Exchange/ Interactive Financial Exchange), FpML (Financial Products Markup Language) - финансы.

В России с учетом зарубежного опыта была создана общественная организация Некоммерческое партнерство "Стандарты электронного обмена информацией", цель которой - разработка национальных стандартов. [1]

Основная сфера применения стандартов платформы XML — это представление слабоструктурированных данных Web-сайтов в форме XML-документов.

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

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

XML обеспечивает интеграцию неоднородных информационных ресурсов, различных технологий управления данными и приложений. Одно из важных направлений этой деятельности связано с созданием единых средств для совместного использования слабоструктурированных данных Web-сайтов и данных, представленных в реляционных БД. Стремление к интеграции с SQL-ресурсами со стороны потребностей XML выразилось, в частности, в разработке языка запросов для XML - Quilt. [2]

Активно развиваются технологии баз данных XML. Языками запросов также служат XPath, XSLT и XQuery. В качестве схемы базы данных при этом используется описание XML-документов средствами стандарта XML Schema. Стали появляться программные продукты, которые квалифицируются разработчиками как СУБД для баз данных XML. Проект стандарта XQuery обеспечил новый вариант пользовательского интерфейса в СУБД XML. Технология XML возникла естественным образом из языков описания документов, обладает большими семантическими возможностями и поэтому, как предполагается, придет на смену реляционной технологии. [3,4]

Можно ожидать, что технологии XML-ориентированных баз данных найдут применение и в решении проблемы "скрытого" Web. [2]

Стандарты XML используются в электронном бизнесе, электронных библиотеках, электронных изданиях и т. п., а также в управлении производством. Они обеспечивают новые возможности для представления, интеграции и оперирования информационными ресурсами в электронных библиотеках. В ряде разработок используются средства платформы XML для представления метаданных, определенные стандартами RDF, RDFS, OWL.

XML применяется также в системах управления документами, в этом случае становится возможной интеграция указанных систем в среду Web. Перспективное направление использования XML - XML-формат для передачи данных, относящихся к управленческой методике сбалансированной системы показателей (ССП). [2,3]

В настоящее время создается большое количество конкретизаций языка XML для разметки документов в различных предметных областях (например, для применения в химии, географии, астрономии, истории, издательском деле, электронном бизнесе и др.). [1]

XML — естественный результат развития Web-технологий, следствие стремления к более эффективному использованию уникальных возможностей открытой глобальной информационной среды, которую они поддерживают. Распространению стандартов XML-платформы способствует политика W3C, направленная на обеспечение доступности их спецификаций, создание ряда свободно распространяемых синтаксических анализаторов для языка, то большое внимание, которые создатели стандартов XML уделяют обеспечению преемственности для существующей HTML-платформы и накопленных на ее основе ресурсов.[5]

Список литературы.

1.  Курочкин данными на основе межотраслевого стандарта XML. Труды третьей всероссийской конференции «Стандартизация информационных технологий и интероперабельность». Октябрь 2009. С. 124-126.

2.  XML: сферы применения //Директор информационной службы. Апрель 2001. С. 10-12.

3.  , Новиков библиотеки - новый класс информационных систем. Российская Академия наук. - М.: Наука, МАИК «Наука/Интерпериодика», Программирование, 3, 2000. С. 3-8.

4.  Когаловский возможности и направления использования стандартов платформы XML. Сб. трудов Всероссийской практической конференции “Стандарты в проектах современных информационных систем”, Москва, 2001. - М.: Открытые системы, 2001. - С. 127-133.

5.  XML: возможности и перспективы. Часть 2. Базы данных XML, семантика XML-документов, перспективы // Директор информационной службы. Февраль 2001. С. 16-20.

Некоммерческая организация «Ассоциация московских вузов»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный технологический университет «Станкин »

Научно-информационный материал

Подраздел: 40.7.2.3.

НИМ 2.3.21.

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ ЭВОЛЮЦИОННОГО АЛГОРИТМА ПРИ РЕШЕНИИ ЗАДАЧИ ДВУМЕРНОЙ УПАКОВКИ ОБЪЕКТОВ

– каф.«Управление и информатика в технических системах»

Научный руководитель – д. т.н., проф. , каф. «Управление и информатикав технических системах»

Москва 2010

Введение

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

·  ребра упакованных в контейнере прямоугольных объектов параллельны ребрам контейнера;

·  упакованные объекты не пересекаются друг с другом;

·  упакованные объекты не пересекаются со сторонами контейнера.

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

Алгоритм получения решения задачи

Задача двумерной ортогональной упаковки объектов в контейнеры относится к классу задач 2DBPP (Two-Dimensional Bin Packing Problem) [1] и является NP-трудной задачей [2], для которой неизвестны алгоритмы решения полиномиальной сложности. При решении NP-трудных задач эффективным подходом к их решению является использование эволюционных алгоритмов.

Ниже перечислены основные достоинства и недостатки эволюционных алгоритмов.

Достоинства эволюционных алгоритмов:

·  поиск решения на широком диапазоне изменения целевой функции;

·  получение набора решений удовлетворительного качества;

·  большой набор варьируемых параметров алгоритма.

Недостатки эволюционных алгоритмов:

·  эвристический характер не гарантирует оптимальности полученного решения;

·  относительно высокая вычислительная трудоемкость [3];

·  невысокая эффективность на заключительных фазах моделирования эволюции.

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

Представление объектов в контейнерах

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

Алгоритм размещения объектов

Универсальный алгоритм размещения объектов при представлении объектов на основе узловой модели содержит следующие этапы:

1.  Выбор размещаемого объекта из строки решения. Выбор контейнера, содержащего, как минимум, один пустой узел.

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

3.  Присоединение объекта к найденному узлу контейнера. Сортировка узлов контейнера в порядке убывания приоритета присоединения к ним объектов. Выбор следующего объекта для размещения. Переход к п.1.

Описанный выше алгоритм размещения объектов позволяет постепенно заполнять контейнеры объектами в порядке, определяемом положением узлов контейнеров.

Вычислительный эксперимент

Эффективность применения эволюционного алгоритма исследована на примерах из библиотеки OR-library [4] для наборов объектов, взятых из задач Fekete и Schepers [5]. Задачи решались на разработанном универсальном программном обеспечении Packer, функционирующем на платформе Microsoft Win32. В ходе тестирования была проведена серия из 100 экспериментов для 21 задачи упаковки с объемом выборки 40, 50, 100, 150, 250, 500 и 1000 объектов. Показателем качества размещения служит относительное отклонение от нижней границы, которое рассчитывается по следующей формуле:, (1)

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

На рис. 1 приведены диаграммы качества решения различных задач двумерной упаковки.

Рис. 1. Диаграммы качества размещения объектов

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

Список литературы

Waesher G., Haussner H., Shumann H. An improved typology of cutting and packing problems // European Journal of Operational research. 2007, 183, pp. 1109–1130. Gary, M., Johnson, D., Computers intractability: a guide to the theory of NP-completeness. San Francisco: W. H. Freeman, 1979. Курейчик методы решения оптимизационных задач. Таганрог: Изд-во ТРТУ, 1999. http://people. brunel. ac. uk/~mastjjb/jeb/info. html (Библиотека OR-library наборов объектов из задач Fekete и Schepers). Beasley J. E. A population heuristic for constrained two-dimensional non-guillotine cutting // EJOR. 2004. Vol. 156. P. 601-627.

Некоммерческая организация «Ассоциация московских вузовНекоммерческая организация

«Ассоциация московских вузов»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный технологический университет «Станкин»

НАУЧНО-ИНФОРМАЦИОННЫЕ МАТЕРИАЛЫ

Подраздел 40.7.2.5.

Организация и проведение секции «Метрологическая информатика» в рамках 1 тура студенческой научно-технической конференции «Автоматизация и информационные технологии (АИТ-2010)»

Москва 2010

СЕКЦИЯ «МеТРОЛОГИЧЕСКАЯ ИНФОРМАТИКА»

1. РАЗРАБОТКА ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНОЙ СИСТЕМЫ, ОСНОВАННОЙ НА ИНФРАКРАСНОМ ДАТЧИКЕ, И ИССЛЕДОВАНИЕ ЕЕ МЕТРОЛОГИЧЕСКИХ ХАРАКТЕРИСТИК..

2. РАЗРАБОТКА ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНОЙ СИСТЕМЫ ДЛЯ РЕГИСТРАЦИИ И ОТОБРАЖЕНИЯ ТЕМПЕРАТУРЫ..

3. КОМПЬЮТЕРИЗАЦИЯ ОТНОСИТЕЛЬНЫХ ИЗМЕРЕНИЙ НА ИНТЕРФЕРОМЕТРЕ КЕСТЕРСА..

4. Исследование автоматизированных способов восстановления рельефа поверхности ПО изображению с интерферометра Линника..

5. , Разработка и исследование измерительной головки для координатной измерительной машины..

6. РАЗРАБОТКА СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ КАЛИБРОВ РАСПОЛОЖЕНИЯ..

7. МЕТОД БЕСКОНТАКТНОГО ИЗМЕРЕНИЯ ФОРМЫ..

8. ПРИМЕНЕНИЕ ДЕТЕРМИНИРОВАННОГО ХАОСА ДЛЯ ОБЕСПЕЧЕНИЯ КОНФИДЕНЦИАЛЬНОСТИ ПЕРЕДАЧИ..

9. РАЗРАБОТКА СИСТЕМЫ ДЛЯ ИЗМЕРЕНИЯ ВЕЛИЧИНЫ УГЛОВОГО ОТКЛОНЕНИЯ ПЛАТФОРМЫ В ДВУХ НАПРАВЛЕНИЯХ..

10. ИССЛЕДОВАНИЕ ОПТИЧЕСКОГО МЕТОДА ИЗМЕРЕНИЯ ЛИНЕЙНЫХ РАЗМЕРОВ..

11. Разработка информационно-измерительной системы для измерения поверхностных неровностей..

12. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СИСТЕМЫ АВТОМАТИЧЕСКОГО ПРОЕКТИРОВАНИЯ СПЕЦИАЛЬНЫХ СРЕДСТВ ИЗМЕРЕНИЙ..

13. Требования к методикам анализа эффективности инвестиций в ИТ-инфраструктуру предприятия..

14. МЕТРОЛОГИЧЕСКИЕ ВОПРОСЫ ВИБРОДИАГНОСТИКИ ШПИНДЕЛЬНЫХ УЗЛОВ..

15. Измерительная информационная система для распознавания типов поверхностей..

16. ПРИБОРА ДЛЯ КОНТРОЛЯ В ВОЗДУШНОЙ СМЕСИ

17. ОЦЕНКА ПОГРЕШНОСТИ МЕТОДА НАНОИНДЕНТИРОВАНИЯ ПРИ ОПРЕДЕЛЕНИИ МЕХАНИЧЕСКИХ СВОЙСТВ МАТЕРИАЛОВ..

18. РАЗРАБОТКА ПРИБОРА КОНТРОЛЯ АМПЛИТУДНЫХ ПАРАМЕТРОВ ИЗЛУЧЕНИЯ ВИДИМОЙ ЧАСТИ СПЕКТРА..

19. ПОСТРОЕНИЕ СИМУЛЯТОРА КИМ В BLENDER..

20. ПРИМЕНЕНИЕ ХАОСА ДЛЯ ОБЕСПЕЧЕНИЯ ПОМЕХОУСТОЙЧИВОСТИ ПЕРЕДАЧИ МОДУЛИРОВАННЫХ СИГНАЛОВ

Некоммерческая организация «Ассоциация московских вузов»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный технологический университет «Станкин »

Научно-информационный материал

Подраздел: 40.7.2.5.

НИМ 2.5.1.

РАЗРАБОТКА ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНОЙ СИСТЕМЫ, ОСНОВАННОЙ НА ИНФРАКРАСНОМ ДАТЧИКЕ, И ИССЛЕДОВАНИЕ ЕЕ МЕТРОЛОГИЧЕСКИХ ХАРАКТЕРИСТИК

– каф. «Измерительные информационные системы и технологии»

Научный руководитель – зав. каф. «Измерительные информационные системы и технологии»,

проф.

Москва 2010

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

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

В качестве передатчика сигнала используется ИК-диод, соединенный с источником питания (батарейка типа AAA) через ключ (двухконтактная кнопка без фиксации). Все элементы закреплены на опорной конструкции и представляют собой единый блок, принципиальная схема которого представлена на рис. 1.

Рис. 1. Принципиальная схема инфракрасного передатчика

Наиболее интересным компонентом системы является приемник инфракрасного сигнала. В качестве него используется манипулятор от игровой консоли NintendoWii – Wii Remote Control, который обладает светочувствительной матрицей, необходимой для регистрации ИК-диода в пространстве. Выбор был сделан не случайно – данное устройство обладает целым рядом преимуществ:

·  качественная светочувствительная матрица с разрешением 1024x768 пикселей;

·  возможность регистрации до 4-х ИК-диодов одновременно;

·  наличие программного обеспечения (драйверов), позволяющего получать и обрабатывать с помощью персонального компьютера информацию, передаваемую Wii Remote Control;

·  соединение с компьютером по средствам технологии беспроводной связи Bluetooth;

·  питание от двух батареек типа AA и небольшие размеры устройства.

Первый пункт наиболее важен с метрологической точки зрения, так как точность определения положения ИК-диода в наибольшей степени зависит именно от разрешения светочувствительной матрицы. 1 пиксель в данном случае будет определять цену деления измерительного устройства, причем, так как матрица имеет различное разрешение по осям x и y, то цена деления по этим осям будет различна.

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

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

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

Таким образом, мы получаем полностью автономную и довольно мобильную измерительную установку, уже настроенную на взаимодействие с персональным компьютером, схема компоновки которой (расположение элементов в пространстве) изображена на рис. 2.

Рис. 2. Схема расположения элементов измерительной системы в пространстве.

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

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

2)  К каждой из меток подносится ИК-передатчик и нажимается кнопка, которая «включает» ИК-диод.

3)  Двумерные координаты ИК-диода фиксируются светочувствительной матрицей приемника и передаются в компьютер.

4)  На основании обработки полученной информации определяются масштабирующие коэффициенты по каждой из осей (x и y), которые позволяют получить координаты ИК-диода на измерительной поверхности.

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

Стоит отметить, что помимо достоинств данная система обладает рядом существенных недостатков:

1)  Низкая точность измерений, которая ограничена разрешением светочувствительной матрицы приемника. Кроме того, на точность определения координат ИК-иода сильно влияет размер области его свечения.

2)  Разная чувствительность по осям x и y, так как матрица имеет размер 1024х768.

3)  Необходимость проведения калибровки каждый раз при смене измерительной поверхности.

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

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

·  цена деления по осям (так как производитель Wii Remote Control не указывает физический размер матрицы, то придется определять этот параметр экспериментально);

·  линейность/нелинейность функции преобразования;

·  виды погрешностей, влияющих на результат измерения, и их величины;

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

Некоммерческая организация «Ассоциация московских вузов»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный технологический университет «Станкин »

Научно-информационный материал

Подраздел: 40.7.2.5.

НИМ 2.5.2.

РАЗРАБОТКА ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНОЙ СИСТЕМЫ ДЛЯ РЕГИСТРАЦИИ И ОТОБРАЖЕНИЯ ТЕМПЕРАТУРЫ

–каф. «Измерительные информационные системы и технологии»

Научный руководитель – преп. каф. «Измерительные информационные системы и технологии»

Москва 2010

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

Рис. 1 – Изображение собаки в инфракрасном диапазоне, полученное с помощью тепловизора.

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

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

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

Ниже приведена классификация наиболее распространенных методов измерения температуры:

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

В ходе работы была создана экспериментальная установка, измеряющая температуру в рабочем пространстве при помощи четырех датчиков температуры компании Analog Devices TMP36GT9, позволяющая передавая результаты измерения посредством интерфейса USB в компьютер. Также было разработано специальное программное обеспечение (в среде Borland C++ Builder 6.0), позволяющее графически отобразить получаемые в режиме реального времени с устройства данные в виде цветовых градаций от зеленого до красного на экране компьютера.

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

Некоммерческая организация «Ассоциация московских вузов»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный технологический университет «Станкин »

Научно-информационный материал

Подраздел: 40.7.2.5.

НИМ 2.5.3.

КОМПЬЮТЕРИЗАЦИЯ ОТНОСИТЕЛЬНЫХ ИЗМЕРЕНИЙ НА ИНТЕРФЕРОМЕТРЕ КЕСТЕРСА

–каф. «Измерительные информационные системы и технологии»

Научный руководитель – преп.

Москва 2010

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

Целью работы, описанной в данной статье, является компьютеризация процесса относительных измерений на интерферометре Кестерса. Интерферометр Кестерса предназначен для измерения длины концевых мер 1 и 2-го разрядов. Относительные измерения позволяют сделать вывод о разности длин двух концевых мер (эталонной и поверяемой). Эти измерения проводятся в белом свете, а разность длин мер определяют по смещению ахроматической полосы (самая темная полоса на каждой из мер) на контролируемой мере. Измерения в белом свете широко используются по причине простоты их реализации, а также надежности и доступности применяемых источников света.

Из за большого объема эта статья размещена на нескольких страницах:
1 2 3 4 5