Формирование вспомагательных функций генетических алгоритмов
Saved in:
| Published in: | Моделювання та інформаційні технології |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2010
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/21849 |
| 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: | Формирование вспомагательных функций генетических алгоритмов / Я. Равецки // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 56. — С. 45-53. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860042771106103296 |
|---|---|
| author | Равецки, Я. |
| author_facet | Равецки, Я. |
| citation_txt | Формирование вспомагательных функций генетических алгоритмов / Я. Равецки // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 56. — С. 45-53. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Моделювання та інформаційні технології |
| first_indexed | 2025-12-07T16:56:52Z |
| format | Article |
| fulltext |
45 © Я.Равецки
1. Процеси життєвого циклу програмного забезпечення (ISO/IEC 12207: 1995) : ДСТУ
3918-1999 – [Чинний від 2000-07-01]. – К. : Держстандарт України, 2000. VI. 49 с.
(Державний стандарт України).
2. Цивільний процесуальний кодекс України [Електронний ресурс] Закон України від
18.03.2004 р. № 1618-IV. – Режим доступу: http.rada.gov.ua. – Заголовок з екрану.
3. Определение концепции открытого исходного кода – “http://www.free-
soft/org/mirrors/www.opensource.org/docs/osd-russian.php”.
4. Воробйова Н. І. Надійність комп’ютерних систем / Воробйова Н. І., Корнійчук В. І.,
Савчук О. В. – К.: Корнійчук, 2000. – 144 с.
Поступила 3.02.2010р.
УДК 683.06
Я.Равецки
ФОРМИРОВАНИЕ ВСПОМОГАТЕЛЬНЫХ ФУНКЦИЙ
ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
Принципы построения структуры SAR , которая обеспечивает
прогрессивное развитие объектов управления ( OU ), состоят не только в
последовательном использовании таких базовых компонент как
эволюционные модели процессов функционирования OU , процессов
функционирования окружения OU , которые будем называть QOU и
моделей определения риска MR , но и в использовании обратных связей
между отдельными функциональными компонентами, а также, в
использовании рекуррентных схем инициации текущих функциональных
блоков.
В связи сформирование структуры SAR , необходимо рассмотреть все
конструктивные элементы, которые обеспечивают определенную
последовательность функционирования компонент SAR и общую схему
реализации процесса анализа и преобразования PR в UR .
Сформированное PR инициирует активизацию SAR и
соответственноMGR . Система SAR , реализующая анализ PR , осуществляет
моделирование изменений параметров, которые характеризуют отдельные
OU , а результаты такого моделирования оцениваются моделью оценки
риска, который возникает в результате использования модифицированного
PR , являющегося управляющим решением.
В первую очередь, необходимо отметить, что отличие модели SAR от
модели MGR состоит в следующем. Модель MGR = ( , , )F MER MEF MR , а
модель системы SAR описывается соотношением:
46
[ , , ]SAR MGR LM IM= Φ ,
где LM - логическая модель процессов в OU , а IM - информационная
модель OU , которая является расширением для MGR и LM .
Любое UR или PR является действием упреждающим по отношению к
моменту их появления. Поэтому, задача SAR состоит в том, чтобы
спрогнозировать возможные последствия выполнения UR . Решение PR
изменяется таким образом, чтобы оно было ориентировано на
положительные изменения в OU . Причинами малоэффективного
воздействия PR на объект управления могут быть следующие факторы:
− ошибки в PR различной природы и, в первую очередь, ошибки
обусловленные объективным отсутствием тех или иных данных о OU в
момент 1it − , который соответствует времени формирования PR ,
− несовершенство методики, которой пользуется специалист, при
формировании PR , что приводит к внесению в PR субъективных
особенностей,
− в большинстве случаев, специалист, который формирует PR , не может
предвидеть и учесть редких событий, которые могут существенно
влиять на характер PR и известны как форс-мажорные обстоятельства,
− процесс формирования PR специалистом является существенно
зависимым от опосредствованного влияния данных и утверждений,
которые сформированы структурами или группами лиц,
специализирующихся на прогнозировании тех или иных состояний в
экономической, социальной или других сферах.
Параметры ошибок, обусловленных объективными причинами
отсутствия отдельных данных о OU , непосредственно зависят от сложности
OU и его размеров, которые определяются значениями параметров OU .
Типичным примером одного из таких параметров может служить величина
стоимости инвестиций, если предполагается управлять инвестиционным
процессом.
Несовершенство методики формирования PR специалистом
обуславливается следующими факторами:
− несоответствием объема и характера знаний, которыми обладает
специалист, реальным факторам, которые определят OU и его
особенности,
− использование инструментальных средств, для формирования PR ,
которые могут быть несовершенными и неадаптированными к
конкретному OU , например, информационные системы принятия
решений по управлению, экспертные системы и т.д.
Важной особенностью для большинства специалистов является
инертность процессов анализа, который ними осуществляется. Поэтому, если
отсутствуют специальные данные о возможности наступления форс-
мажорных событий, то в формируемом PR будут отсутствовать аспекты,
47
которые их могли бы учитывать.
Формирование тех или иных PR специалистом подвержено достаточно
активному влиянию внешних факторов, которые формируются экспертами
аналитиками, представляющих собой утверждения и предположения по
поводу различных событий, которые могут происходить в области, к которой
относится OU . Такое воздействие может негативно влиять на формирование
PR . Это обусловлено тем, что соответствующая информация может
преднамеренно или не преднамеренно искажать реальную действительность
в области деятельности, к которой относится соответствующий материал,
представляемый экспертами.
При построении генетических алгоритмов, достаточно широко
используются вспомогательные функции. В большинстве случаев такими
функциями являются вероятностные функции или схемы реализации выбора
случайных величин. Естественно предположить, что способ построения
таких функций основывается на данных о характере и природе случайных
процессов, которые существуют в соответствующей предметной области.
Приведенные выше факторы, которые влияют на процессы построения PR , в
первом приближении могут считаться факторами, природа возникновения
которых носит случайный характер. При проведении исследований
процессов и факторов, действие которых на формирование PR принято
считать случайным, приводит к тому, что степень случайности, в этом
случае, соответствующих факторов уменьшается. Такое уменьшение
осуществляется за счет выявления дедуктивных зависимостей в процессах
соответствующих факторов. Благодаря последнему, появляется возможность
строить те или иные схемы использования первичных случайных факторов,
которые могут использоваться при принятии решений, необходимых, для
реализации генетических преобразований.
Рассмотрим некоторую иерархию в рамках генетических
преобразований, которую будем рассматривать как некоторую
структуризацию в рамках преобразований соответствующим генетическим
алгоритмом. Такую иерархию будем рассматривать по отношению
структурной сложности всех компонент, которые участвуют в генетических
преобразованиях. Такие уровни можно определить следующим образом:
− наиболее низкий уровень соответствует преобразованиям, которые
касаются отдельных генов ige ,
− следующий уровень соответствует преобразованиям, которые касаются
хромосом ihr ,
− следующий уровень по возрастанию иерархии определяется
преобразованиями, которые проводятся с популяциями хромосом ipo .
Наиболее низкому уровню иерархии соответствую генетические
преобразования мутации [ ]iM hr . Известно, что это преобразование
обслуживают вспомогательные функции:
48
− Pf - функция преобразования гена ige ,
− Vf - функция выбора гена ige в хромосоме ihr .
В предметной области управления OU отдельный ген представляет
собой значение одного параметра. Поэтому, функция Pf представляется
достаточно сложной и может реализовываться в виде преобразований,
которые могут задаваться следующими способами:
− в виде аналитического преобразования от одной переменной ix ,
1 ( )i ix f x+ = ,
− в виде описания характера изменения значения ige , например, «
увеличить», «уменьшить» и « не изменять»,
− в виде условных преобразований, например, «увеличивать до порога
iα » и т.д.,
− в виде опосредствованного изменения, которое выполняется, при
выполнении дополнительного условия, которое может использовать
текущее значение других генов той же хромосомы и т.д.
Выбор перечисленных функций, которые составляют некоторое
множество, может осуществляться на основе использования определенной
случайной функции выбора [1]. Функция выбора может определяться на
различными способами:
− на основе использования функции распределения случайных величин,
− на основе использования механизмов моделирования различных
случайных процессов, например, модели рулетки, модели Монте-Карло
и т.д.,
− на основе использования псевдослучайных генераторов закономерности
изменения значений параметров в OU , которые, как правило, являются
наиболее изученными, что приводит к тому, что, чаще всего, Pf в
определенных диапазонах значений некоторых параметров являются
известными.
В последнем случае, функция Pf заменяется ограниченным
множеством известных преобразований, описывающих закономерности
изменения соответствующих параметров. Такие закономерности могут
задаваться не только аналитически, но и в виде графических зависимостей
или таблично [2].
Выбор определенного гена для модификации осуществляется на основе
использования функции Vf , которая может быть функцией случайного
выбора того или иного параметра. Такая ситуация имеет место в том случае,
если параметры, которые собраны в одной ihr не зависимы между собой.
Если одна хромосома описывает отдельный комплект параметров, то, чаще
всего, параметры этого комплекта относятся к одному экземпляру объекта.
49
Параметры в рамках одной хромосомы являются параметрами одного
изделия, но они могут иметь разные значения в зависимости от экземпляра
продукта, который они описывают. Это означает, что разные экземпляры
могут иметь разные значения одного и того же параметра. В этом случае,
операция скрещивания позволяет производить замену значений группы
параметров одного экземпляра продукции группой параметров другого
экземпляра продукции. Соответствующие группы выбираются таким
образом, чтобы типы заменяемых параметров одного экземпляра продукции
соответствовали тем же типам параметров второго экземпляра продукции. В
качестве дополнительных или вспомогательных функций: Wf - при помощи
которой выбирается пара скрещиваемых хромосом из популяции iPO и
функция Df , с использованием которой выбираются места деления
хромосом на группы параметров, как минимум одна пара, одна из которых
обменивается на соответствующую группу из другой хромосомы
соответствующей пары. Как правило, соответствующие группы параметров,
которые выбираются для скрещивания, должны отображать некоторую
отдельную функцию продукции и поэтому такие группы могут выбираться
по функциональным признакам. Следовательно, операции скрещивания
могут приводить к изменениям свойств отдельных функциональных
возможностей изделий. В достаточно сложном продукте функциональные
возможности могут, при определенных ситуациях, становиться зависимыми
от параметров, которые на предыдущих этапах относились к другим
функциональным возможностям. Это означает, что в рамках функции Df не
целесообразно реализовывать только детерминированные механизмы. Они
должны также допускать и случайный выбор параметров, которые
относились к другим группам. Таким образом, целью реализации операции
скрещивания является не улучшение некоторых, возможно интегральных
параметров, а улучшение функциональных возможностей соответствующего
изделия. В этом смысле, функция Wf , которая используется для выбора
пары ihr и jhr , для выполнения скрещивания, тоже должна формироваться
таким образом, чтобы выбранные пары для скрещивания привели к
увеличению эффективности операции скрещивания, которая должна
увеличить функциональные возможности отдельных изделий. В этом случае,
можно утверждать, что между Wf и Df должна существовать некоторая
зависимость, которую условно будем называть прогрессивной зависимостью.
Ее формально можно представить в виде следующего многоступенчатого
соотношения:
1 1[ ( ,..., ) ( ,..., )]W D
i i in j j jmf f f x x f x x→ ⇒ → ,
где 1( ,..., )i i inf x x - описание функциональных возможностей фрагмента
50
изделия до операции скрещивания, а 1( ,..., )j j jmf x x - описание
функциональных возможностей этого же фрагмента изделия после операции
скрещивания. Очевидно, что должна существовать некоторая проекция
такого изменения функциональных возможностей в некоторый интегральный
параметр. Это становится возможным в том случае, если такое изменение или
расширение функциональных возможностей приведет к необходимости
формирования нового его описания в предметной области интерпретации.
На наивысшем уровне иерархии преобразований реализуется функция
репродукции. В качестве вспомогательных функций используются функции
Sf и Cf , где Cf это функция оценки хромосом популяции, а Sf - функция
выбора отдельных хромосом, обладающих различными оценками, в состав
следующей популяции. Интуитивно, складывается впечатление, что оценки
должно быть достаточно для того, чтобы принять решение о возможности
включить в популяцию 1iPO + из iPO те или иные хромосомы. На самом деле
ситуация состоит в том, что на множестве оценок, полученных при
использовании функции Cf , функция выбора хромосом Sf не обязательно
должна быть линейной. Ситуация, когда эта функция принимается линейной,
она может описываться соотношением, которое может интерпретироваться
следующим текстовым расширением <чем выше оценка, тем более
пригодной для 1iPO + является хромосома>. Не оптимальность использования
линейных функций выбора Sf обосновывается тем, что сама функция Cf не
может обеспечить возможности получения идеальной оценки. По существу,
использование двух вспомогательных функций выбора ihr для 1iPO +
представляет собой двухуровневый выбор. Очевидно, что количество таких
уровней оценки и, соответственно, выбора можно было бы увеличивать
путем введения соответствующего количества вспомогательных функций.
При этом, возникает задача определения оптимального количества
выбираемых уровней оценки [3].
При реализации MER , возникает задача формирования
вспомогательных функций, которые участвуют в реализации генетических
преобразований. Очевидно, что вспомогательные функции должны
отображать исходные данные и описывать фрагменты предметной области
iW , к которой должны относиться данные. Рассмотрим вспомогательные
функции операции мутации Vf и Pf . Одна из причин необходимости
проведения анализа PR состоит в том, что у специалиста, который
формирует PR , нет достаточно полной информации о параметрах, которые
участвуют в формировании PR . Такая неполнота может обуславливаться
двумя факторами, касающимися параметров:
− может отсутствовать информация о значениях этих параметров, что
51
приводит к использованию в PR , что приводит к использованию тех
значений параметров, которые могут оказаться неадекватными реальной
действительности,
− неизвестно, какие из параметров представлены достаточно или
недостаточно точно.
В этом случае, функция Vf представляет собой функцию выбора
наименее адекватно представленного параметра. Если принять, что
отдельный ige соответствует отдельному параметру, то функция Vf выбор
ige будет соответствовать выбору наименее точных параметров. Если в
результате проведения экспериментов по формированию PR , в которых
проводится анализ с целью определения, какие параметры выбираются
наиболее точно, то на основании таких данных можно построить функцию
распределения, которая описывает вероятность, с которой выбираются
параметры, значения которых являются наименее точными. Очевидно, что
могут существовать более сложные механизмы построения функции Vf , в
которых могут учитываться факторы характерные для рассматриваемого
фрагмента iω предметной области iW .
Точность выбора значений каждого из параметров, которые
предполагается использовать, при формировании PR , может быть разной. В
наиболее простом случае мера неточности значения отдельного параметра
может определяться на основе вероятностных оценок случайных величин,
которой может быть текущее значение отдельного параметра. Значение
функции Pf , в этом случае, рассчитывается путем определения величины
соответствующей оценки, а сама Pf представляет собой соответствующую
функцию оценки возможного отклонения значения параметра или величины,
на которую изменяется ген ige в операции мутации.
На следующем уровне иерархии выполняется алгоритм скрещивания,
который обслуживается функцией выбора пары хромосом подлежащих
скрещиванию Wf и функцией выбора места разделения хромосом, для
выделения их частей, подлежащих замене Df . С точки зрения
интерпретации процессов управления производством, отдельная хромосома
может представлять собой отдельную реализацию финансового процесса или
отдельную реализацию партии продукции. В случае использования в
качестве примера некоторого финансового процесса, например, инвестиции,
в качестве популяции необходимо рассматривать ряд инвестиций, которые в
течении некоторого времени реализуются на производстве или ряд
однотипных производств, на которых реализуются инвестиции одного
характера, например, инвестиции в развитие производства. Для большего
удобства, в качестве примера объекта интерпретации будем рассматривать
52
различные партии одного и того же изделия, принимая во внимание, что
изделия одной партии являются в наибольшей мере одинаковыми, поскольку,
в одной партии используются одинаковые материалы, идентичные
технологические процессы или один и тот же технологический процесс и т.д.
Различные партии одного и того же изделия могут различаться в силу
следующих причин, например, изменения сырья, улучшения
функциональных параметров, изменения технологических процессов и т. д.
В рассматриваемом случае, одной из причин формирования такого PR ,
которое требует анализа, является несовершенство методики формирования
PR . Это обуславливается, в большинстве случаев, неполным
представлением о объекте управления и его возможностями, которыми в
данном случае являются различные фрагменты технологического процесса,
сырье используемое для производства и т. д. Соответствующая методика
определяет способ расчета параметров продукта в зависимости от параметров
и факторов описывающих процесс производства соответствующего продукта.
Поэтому, если процесс производства соответствующего продукта
недостаточно полно известен специалисту, то он не в состоянии с
необходимой адекватностью таким образом сформировать PR , чтобы
параметры изделия соответствовали сформированным требованиям.
Методика определения требуемого PR состоит в моделировании процесса
производства изделия с помощью технологического процесса. В рамках
такой модели реализуются алгоритмы изготовления продукта при заданных
параметрах сырья и заданных параметрах фрагментов технологических
процессов. В этом случае, необходимо выбрать те пары продукции, которые
изготавливались в различных партиях, которые обладали бы максимальными
различиями в значениях параметров. В этом случае, процедура замены
параметров или генов одной хромосомы группой генов другой хромосомы
будет наиболее эффективной.
Обслуживающими функциями в скрещивании являются функция
выбора хромосом Wf и функция точки деления хромосом Df [4]. Каждая
хромосома описывает экземпляр продукта из отдельной партии. Поскольку
таких партий может быть много и можно принять, что нет точной
информации, какие параметры, каких партий способствуют улучшению
качества продукции, то естественно принять, что функция Wf является
функцией случайных величин. В данном случае, под качеством продукта
подразумевается не увеличение значений отдельных параметров, а
прогрессивные изменения в продукте, которые могут сопровождаться
уменьшением значений некоторых параметров. Обоснованность, для
определения такой природы соответствующему продукту состоит в том, что
специалист, формирующий PR , может, в силу объективных причин, не
знать, какие качества или характеристики продуктов могут быть
интерпретированы как характеристики, которые определяют прогрессивные
изменения. Благодаря рыночной схеме функционирования производства,
53
можно принять, что критерий прогрессивности изменений продуктов,
определяется величиной их спроса на рынке. Следовательно, изменение
уровня спроса можно рассматривать как величину случайную а также можно
ее сопоставлять с изделиями из различных партий. Таким образом,
исходными данными для построения функции Wf могут быть данные о
изменении уровня спроса на изделия из различных партий.
Функция Df определяет точки разделения хромосомы, которые
вырезают группы параметров подлежащие обмену, представляет собой
сложную конструкцию. Прежде всего отметим, что отдельные параметры
одного изделия могут находиться между собой в более или менее сильной
связи. Под силой связи, в данном случае, называется величина описывающая
отношение величины изменения значений одного параметра, который
зависит от второго ( )i ix f y= , до величины изменения второго параметра.
Например, можно записать соотношение:
1 1{[( ( ) & ( )] ( )} ( / )S
i i i i i i i i i ix f y y y y x x x x yδ+ += = + Δ → = + Δ → = Δ Δ ,
где Sδ - сила связи между ix и iy . В зависимости от Sδ группируются ige в
ihr и Df может определять точки в ihr только между группами ige ,
которые определяются определенными значениями Sδ . Тогда, фрагмент
1, ,...,i i i kge ge ge+ + выделяется как подлежащий замене в ihr на фрагмент из
jhr . При этом, Df в ihr и jhr выделяет одни и те же группы генов. Таким
образом, осуществляется интерпретация обслуживающих функций в
операции скрещивания. Функция Df тоже является случайной, поскольку,
неизвестно, как фрагменты технологического процесса влияют на изменение
значений ige .
1. Billingsley P. Prawdopodobenstwo i miara. Warszawa, PWN, 1987.
2. Rao C.R. Liniowe modele statystyki matematycznej. Warszawa, PWN, 1985.
3. Costa L., Oliviera P. Adaptive Sharing Elitist Evolution Strategy for Multiobjektive
Optimization. Evolutionari Computation, Vol.11,N4, 1998.
4. Grefenstette J.J. Genetic algoritms and their applications/ Procedings of the Second
Internnational Conference on Genetic Algorithms. Hillsdale, NJ: Lawrence Erlbaum
Associates 1987.
Поступила 21.01.2010р.
|
| id | nasplib_isofts_kiev_ua-123456789-21849 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0068 |
| language | Russian |
| last_indexed | 2025-12-07T16:56:52Z |
| publishDate | 2010 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Равецки, Я. 2011-06-17T16:32:53Z 2011-06-17T16:32:53Z 2010 Формирование вспомагательных функций генетических алгоритмов / Я. Равецки // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 56. — С. 45-53. — Бібліогр.: 4 назв. — рос. XXXX-0068 https://nasplib.isofts.kiev.ua/handle/123456789/21849 683.06 ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Моделювання та інформаційні технології Формирование вспомагательных функций генетических алгоритмов Article published earlier |
| spellingShingle | Формирование вспомагательных функций генетических алгоритмов Равецки, Я. |
| title | Формирование вспомагательных функций генетических алгоритмов |
| title_full | Формирование вспомагательных функций генетических алгоритмов |
| title_fullStr | Формирование вспомагательных функций генетических алгоритмов |
| title_full_unstemmed | Формирование вспомагательных функций генетических алгоритмов |
| title_short | Формирование вспомагательных функций генетических алгоритмов |
| title_sort | формирование вспомагательных функций генетических алгоритмов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/21849 |
| work_keys_str_mv | AT raveckiâ formirovanievspomagatelʹnyhfunkciigenetičeskihalgoritmov |