авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

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

Pages:     | 1 ||

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

-- [ Страница 2 ] --
  • с одной стороны подсистема моделирования ядра ПГП содержит дескриптор компонента и формирует среду исполнения оператора (необходимые для его работы данные и параметры);
  • с другой стороны компонент содержит интерфейсный объект ядра ПГП, предоставляющий доступ к данным подсистемы моделирования ядра ПГП (множеству альтернативных решения (особей) и управляющих параметров ГА).

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

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

Алгоритм метаэволюционного моделирования состоит в следующем:

  1. Выбор вершины «Начало алгоритма» и помещение её в очередь обработки.
  2. Извлечение первого элемента очереди (вершины).
  3. Если выбран элемент «Конец работы алгоритма», то очередь очищается и выполняется переход к шагу 8,.
  4. Если выбранная вершина находится в состоянии «готово», то выполняется ГО, связанный с данной вершиной, и осуществляется переход к шагу 6.
  5. Если выбранная вершина находится в состоянии «выполняется» или в состоянии «ожидание», то вершина помещается в конец очереди и осуществляется возврат к шагу 2.
  6. Если выбранная вершина находится в состоянии «завершено» и предусмотрен условный выбор исходящей дуги, то производится выбор дуги, а инцидентная ей вершина графа МетаГА помещается в конец очереди. В противном случае в конец очереди помещаются вершины графа, инцидентные всем исходящим дугам.
  7. Проверка состояния очереди обработки. Если очередь пуста, то подсистеме пользовательского интерфейса сообщается о возникновении недопустимой ситуации, поскольку последним обработанным элементом должен быть элемент «Конец работы алгоритма». Выполняется переход к шагу 8. В противном случае выполняется возврат к шагу 2.
  8. Вывод лучшего решения.

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

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

Предложены следующие стратегии определения точек разрыва:

  • задано число точек разрыва – n. Расположение точек разрыва определяется с помощью алгоритма построения множества Кантора;
  • задана глубина рекурсии k. Число точек разрыва и их местоположение определяется с помощью алгоритма построения множества Кантора, выполняемого k раз;
  • не задана ни глубина рекурсии k, ни число точек разрывов n. В этом случае глубина рекурсии принимается равной kmax. Число течек разрыва и их местоположение определяется с помощь алгоритма построения множества Кантора, применяемого kmax раз.

Предложены следующие стратегии формирования потомков с помощью алгоритма построения множества Кантора:

  • применение ГО после определения всех точек разрыва. Получается стандартное число потомков;
  • применение ГО на каждой итерации построения множества Кантора. Число потомков увеличивается в k раз по сравнению со стандартным способом выполнения ГО.

В четвёртой главе приведены результаты вычислительного эксперимента по определению затрат процессорного времени и памяти вычислительной системы при выполнении ГА разработанного средствами интегрированной инструментальной ПГП и ГА, реализованного на языке С++, которые выполнялись при фиксированных значениях параметров алгоритма: размер популяции |P| = 100; вероятность применения оператора кроссинговера PОК = 0,6; вероятность применения оператора мутации PОМ = 0,4; вероятность применения оператора инверсии PОИ = 0,6.

Обобщенные результаты по определению затрат процессорного времени (Тср) и памяти вычислительной системы (Mem) при выполнении ГА средствами интегрированной инструментальной ПГП и ГА, реализованного на языке С++, приведены в табл. 1 и на рис. 5 - 6.

Обобщенные результаты сравнения размещения тестовых схем ibm01-ibm13 алгоритмами Capo 8.6, Feng Shui 2.0, Dragon 2.23 и ГА, разработанного с использованием ПГП, приведены в табл. 2 и на рис. 7. Отрицательное приращение суммарной длины проводников (L) показывает, что разработанному ГА удалось найти размещение с лучшими значениями оцениваемого критерия по сравнению с результатами, полученными другими алгоритмами. Приведенные результаты обусловили следующие выводы.

Дополнительные расходы времени, затраченные ПГП на выполнение ГА, не превосходят 6% по сравнению с реализацией данного алгоритма на языке программирования С++. Расходы памяти вычислительной системы, затраченные ПГП на выполнение ГА, складываются из двух частей: память для хранения данных ГА, объем которой зависит от размерности задачи и дополнительные память для хранения служебной информации ПГП. Основная доля дополнительных затрат памяти не зависит от размерности задачи и убывает с ростом числа размещаемых элементов, что свидетельствует об эффективном использовании подсистемой данного ресурса. Качество размещений, полученных ГА, разработанным с использованием интегрированной инструментальной подсистемы, в среднем на 6,38% превосходит результаты, полученные с использованием известных алгоритмов Capo 8.6, Feng Shui 2.0, Dragon 2.23, что говорит об эффективности предложенного алгоритма и разработанной ПГП в целом.

Таблица 1 Сравнение затрат процессорного времени
и памяти вычислительной системы.

 Рис. 3. Дополнительные затраты-10

Рис. 3. Дополнительные затраты процессорного времени при выполнении ГА средствами ПГП по сравнению с ГА, реализованным на языке С++.

Рис. 4. Дополнительные затраты памяти при выполнении ГА средствами ПГП
по сравнению с ГА, реализованным на языке С++.

Таблица 2 Сравнение результатов размещения тестовых схем ibm01-ibm13
разными алгоритмами.

Рис. 5. Приращение длины проводников при размещении
тестовых схем ibm01-imb13 различными алгоритмами.

В заключении сформулированы основные выводы и результаты диссертационной работы.

В приложении приведены акты об использовании результатов диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В ходе выполнения диссертационной работы получены следующие результаты:

  1. Построена открытая архитектура интегрированной инструментальной подсистемы, позволяющая реализовать различные модели эволюционного поиска проектных решений и сократить время их программной реализации.
  2. Разработаны лингвистические средства, структура и семантика формального описания генетических процедур поиска проектных решений ЭВА, позволяющие сводить задачи конструкторского проектирования ЭВА к оптимизационным задачам эволюционного моделирования.
  3. Предложены модели представления метаэволюционного и макроэволюционных алгоритмов, реализация которых в интегрированной инструментальной подсистеме позволяет формулировать и использовать нетривиальные процедуры генетического поиска проектных решений.
  4. Разработан механизм расширения, позволяющий интегрировать в подсистему новые операторы преобразования кодовых строк решений.
  5. Предложены стратегии определения точек разрыва и формирования потомков с помощью алгоритма построения множества Кантора, которые реализованы в модифицированных генетических операторах.
  6. Разработан программный комплекс, реализующий интегрированную инструментальную подсистему генетического поиска. Проведенный вычислительный эксперимент подтвердил низкий уровень дополнительных расходов ресурсов вычислительной системы, связанных с реализацией ГА средствами интегрированной инструментальной подсистемы.
  7. Разработан ГА двумерного размещения разногабаритных элементов схемы, использующий мультихромосомное негомоморфное представление размещения и модифицированные операторы, основанные на множестве Кантора. Проведенный вычислительный эксперимент подтвердил то, что качество решений, получаемых с помощью разработанного ГА в среднем на 6,38% превосходит результаты размещения, полученные известными алгоритмами Capo 8.6, Feng Shui 2.0, Dragon 2.23.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

  1. Бакало М.А., Курейчик В.В. Нахождение максимального паросочетания с использованием искусственных нейронных сетей. // Труды Международных научно-технических конференций «Интеллектуальные системы (IEEE AIS’04)» и «Интеллектуальные САПР (CAD-2004)». – М.: Физматлит, 2004, с.363-372.
  2. Backalo M.A. The finding of the maximum matching using neural network. // Еhe International Scientific Conferences “Intelligent Systems (IEEE AIS’04)” and “Intelligent CAD’s (CAD- 2004)”. – M., Physmathlit, 2004, vol. 3, pp. 121.
  3. Бакало М.А., Курейчик В.В. Генетические операторы на основе множества Кантора. // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS’05) и «Интеллектуальные САПР» (CAD-2005). Научное издание в 4-х томах. – М.: Физматлит, 2005, т.4, с.237-243.
  4. Бакало М.А., Курейчик В.В. К вопросу построения модифицированного алгоритма размещения. // Перспективные информационные технологии и интеллектуальные системы. – Таганрог: ТРТУ, 2006, № 4(28), с.44-55.
  5. Бакало М.А. Варианты представления различных типов данных, их кодирование и декодирование в виде хромосом. // Известия ТРТУ. – Таганрог: ТРТУ, 2007, № 1, с.70-75.
  6. Бакало М.А., Курейчик В.В. Модифицированный алгоритм размещения методом парных перестановок. // Известия ТРТУ. – Таганрог: ТРТУ, 2007, № 1, с.77-84.
  7. Бакало М.А., Курейчик В.В. Концепция построения системы поддержки генетических алгоритмов. // Перспективные информационные технологии и интеллектуальные системы. – Таганрог: ТТИ ЮФУ, 2007, №1(29), с.4-10.
  8. Свидетельство об официальной регистрации программы для ЭВМ № 2006612763, 2006г.

В работах 1 и 2, выполненных в соавторстве, автору принадлежит структура искусственной нейронной сети. В работах 4 и 6 автору принадлежит идея выделения подобластей расположения элементов относительно анализируемых и вывод математических формул расчета. В работе 7 автору принадлежит идея использования интерфейсных объектов, инспектора хромосом и буфера особей.

Соискатель М.А. Бакало



Pages:     | 1 ||
 

Похожие работы:










 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.