Об асимптотическом вероятностном генетическом алгоритме

Видны падающие продольные и поперечные волны, конические поперечные волны и поверхностные волны Релея.

Библиографический список

1. Пальмов, В. А. Основные уравнения теории несимметричной упругости / В. А. Пальмов // Прикладная математика и механика. 1964. Т. 28, вып. 3. С. 401-408.

2. Садовская, О. В. Математическое моделирование в задачах механики сыпучих сред / О. В. Садовская, В. М. Садовский. М. : Физмат-лит, 2008.

M. P. Varygina, O. V. Sadovskaya

Institute of Computational Modeling, Russian Academy of Sciences, Siberian Branch, Russia, Krasnoyarsk

PARALLEL COMPUTATIONS IN DYNAMIC PROBLEMS OF COUPLE-STRESSED ELASTIC CONTINUUM

Parallel computational algorithm and program system for the solution ofplane and spatial dynamic problems of couple-stressed elastic theory on multiprocessor computing systems are worked out. The results of computations of three-dimensional Lamb problem about the action of concentrated load on the surface of homogeneous elastic half-space, and also the problem about the action of concentrated periodic impulsive load on the surface of space are represented.

© Варыгина М. П., Садовская О. В., 2009

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

УДК 519.688

П. В. Галушин

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Россия, Красноярск

ОБ АСИМПТОТИЧЕСКОМ ВЕРОЯТНОСТНОМ ГЕНЕТИЧЕСКОМ АЛГОРИТМЕ*

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

Вероятностный генетический алгоритм (ВГА) является попыткой создания алгоритма, имеющего схему, похожую на схему традиционного генетического алгоритма (ГА), и сохраняющего основные свойства генетических операторов, но сформулированного в терминах теории псевдо-булевой оптимизации [1]. В ВГА явным образом (в отличие от традиционного ГА) вычисляются компоненты вектора вероят-

ностей и отсутствует оператор скрещивания, но сохранены генетические операторы мутации и селекции.

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

Работа выполнена при финансовой поддержке АВЦП «Развитие научного потенциала высшей школы» (НИР 2.1.1/2710) и ФЦП «Научные и научно-педагогические кадры инновационной России» (НИР НК-136П/3).

Решетневские чтения

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

?' = Рт +Р (1 - 2Рт ),

где р — вероятность того, что ген был равен единице до мутации; р' — вероятность после мутации; рт - вероятность мутации. Название «асимптотическая мутация» связано с тем, что данная процедура является пределом традиционного оператора мутации при размере популяции, стремящемся к бесконечности.

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

Оператор селекции в ВГА также может быть заменен асимптотическим аналогом. Пусть популяция состоит из особей х\, ..., х„, каждой особи назначена вероятность быть отобранной в одном испытании: g\, ..., gn. Подсчитаем математическое ожидание вероятности того, что '-й ген окажется равным единице в одном испытании:

Р') = ±4) &. к=1

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

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

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

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

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

Библиографический список

1. Семенкин, Е. С. Вероятностные эволюционные алгоритмы оптимизации сложных систем / Е. С. Семенкин, Е. А. Сопов // Интеллектуальные системы (Л1Б'05), Интеллектуальные САПР (СЛБ-2005): тр. Междунар. науч.-техн. конф. в 3 т. М. : ФИЗМАТЛИТ, 2005. Т. 1.

2. Ахо, А. В. Компиляторы: принципы, технологии и инструментарий : пер. с англ. / А. В. Ахо, М. С. Лам, Р. Сети, Д. Д. Ульман. 2-е изд. М. : ООО «И. Д. Вильямс», 2008.

P. V. Galushin

Siberian State Aerospace University named after academician M. F. Reshetnev, Russia, Krasnoyarsk ON ASYMPTOTIC PROBABILISTIC GENETIC ALGORITHM

This paper proposes the modification of probabilistic genetic algorithm, which uses genetic operators, effecting on the probabilities distribution of solution vector's components. This paper also compares reliability and efficiency of base algorithm and proposed modification using the set of test optimization problems and bank loan portfolio problem

© TanyrnHH n. B., 2009

УДК 658.512; 004.82

А. С. Говорков, Р. Х. Ахатов Иркутский государственный технический университет, Россия, Иркутск

ПРЕДСТАВЛЕНИЕ ДАННЫХ ОБ ОБЪЕКТАХ ПРОИЗВОДСТВЕННОЙ СРЕДЫ ПРИ РАЗРАБОТКЕ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ СБОРКИ

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

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

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

1) опыт проектирования подобных (аналогичных) объектов;

2) использование различных классификаторов, справочников;

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

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

Для компьютерного представления и обработки знаний и данных о предметной области они должны быть представлены в определенном формализованном виде [1].

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

Особенности представления знаний с помощью фреймов создает новые возможности по отношению к системам продукции и логическим моделям. Фреймовая модель позволяет хранить родовидовую иерархию в явной форме [2].

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