Книги по разным темам Pages:     | 1 |   ...   | 7 | 8 | 9 | 10 | 11 |   ...   | 65 |

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

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

енной генетическим алгоритмом статистики.

- накопление и использование генетическим алгоНа каждом поколении генетического алгоритма выритмом статистических данных о пространстве поиска;

числяется средняя пригодность fitnessср. Далее подсчи - управление ресурсом генетического алгоритма, тывается количество единиц в j-м гене k-й хромосомы, выделяемого для решения задачи оптимизации.

удовлетворяющей неравенству fitnessk fitnessср.

Рассмотрим предложенные модификации более На основе статистических данных определяются веподробно.

роятности появления единицы в j-м гене: pi = Mi /k, Математика, механика, информатика где Мi - количество единиц в j-м гене; k - количество Управление ресурсом генетического алгоритма, хромосом в популяции с fitnessk fitnessср. выделяемого для решения задачи оптимизации.

Полученные вероятности используютя при фор- В процессе работы алгоритма генетического промировании хромосомы, значения генов которой ини- граммирования целью применения генетического алциализируются по следующиму правилу (рис. 6): горитма с предложенными выше модификациями явkmax ляется увеличение скорости генерирования структуры - р = 1, если pi pmax = pi max, где дерева решения с заданной ошибкой аппроксимации kmax i=за счет повышения вероятности отбора нелинейных структур путем настройки численных коэффициенpi max 0,5;

тов. Но нельзя заранее предугадать, на каком именно kmin поколении будет сгенерирована данная структура, из - р = 0, если pi pmin = pi min, kmin i=за чего применение генетического алгоритма с ресурсом, сопоставимым с ресурсом алгоритма генетичегде pi min < 0,5 ;

ского программирования, даже с учетом интервала - значение гена инициализируется случайным обадаптации является необоснованным. Поэтому было разом, если pmin < pi < pmax.

предложено ограничить ресурс генетического алгоПусть например, вероятности имеют следующие ритма 20 % от ресурса алгоритма генетического прозначения: граммирования. Однако если генетический алгоритм находит решение с пригодностью, большей чем ис№ ходная пригодность этого же решения, найденного 1 2 3 4 5 6 7 8 гена с помощью метода генетического программирования P 0,54 0,25 0,19 0,8 0,9 0,32 0,65 0,12 0,до настройки численных коэффициентов, то ресурс генетического алгоритма однократно увеличивается Тогда вдвое.

Эффективность модифицированного алгоритма pmax = pimax = в рамках интегрированной процедуры автоматизироi=ванного построения и оптимизации математических моделей сложных систем и процессов проверена = 0,54 + 0,8 + 0,9 + 0,65 + 0,93 = 0,764, () на тестовых функциях с усреднением по многим запускам.

pmin = pimin = Работа гибридного алгоритма с применением i= предложенных модификаций исследовалась на задаче построения модели функции sin(x) на интервале = 0, 25 + 0,19 + 0,32 + 0,12 = 0, 22.

() [Ц3,14; 3,14] со случайным шагом и объемом тестовой выборки, равном 100 точкам. В качестве функциоВ результате будет получена хромосома:

нального множества использовались арифметические операции сложения, вычитания, умножения и деле№ 1 2 3 4 5 6 7 8 ния, терминальное множество содержало переменную гена x и набор констант на интервале [Ц1;1] со случайным P Rand Rand 0 1 1 Rand Rand 0 шагом.

Полученные результаты представлены в табл. 2, Эта хромосома, созданная на основе статистичеи на рис. 7.

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

аппроксимации больше 5 % до нуля.

Random 0 p = p = pmin pmax Рис. 6. Правила формирования хромосомы на основе статистических данных Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Таблица Обобщенные результаты исследований Модификации N1, % N2, % N3, % G Cn Использование статистических данных ГА 5 50 45 751 Управление ресурсом ГА 5 50 45 783 Использование статистических данных ГА + управление ресурсом 0 45 55 632 ГА + переход коэффициентов лучших решений АГП Таблица Сравнительный анализ эффективности алгоритмов № Алгоритм N1, % N2, % N3, % п/п 1 АГП 20 40 2 АГП + ГА 5 45 3 АГП + ГА + использование статистических данных ГА 5 50 4 АГП + ГА + использование статистических данных ГА + Управление ресурсом ГА 5 50 АГП+ГА + использование статистических данных ГА + управление ресурсом ГА + 5 0 45 + переход коэффициентов лучших решений АГП Синтез модифицированных эволюционных алго- Предложенный алгоритм развивает эволюционритмов позволил создать гибридный алгоритм реше- ную теорию моделирования и оптимизации сложных ния задачи символьной регрессии и оптимизации систем, а также теорию и практику поддержки приняв рамках интегрированной процедуры автоматизиро- тия решений при управлении этими системами.

ванного построения и оптимизации математических Библиографические ссылки моделей сложных систем и процессов на основе экспериментальных данных, превосходящий стандарт- 1. Koza J. R. Genetic Programming: On Programming ный алгоритм генетического программирования по Computer by Means of Natural Selection and Genetics.

быстродействию и надежности.

Cambridge, Mass. : MIT Press, 1992.

2. Сопов Е. А. Эволюционные алгоритмы моделирования и оптимизации сложных систем : дис. Е канд. техн. наук. Красноярск, 2004.

3. Holland J. H. Adaptation in Natural and Artificial Systems. Ann Arbor : Univ. of Michigan Press, 1975.

4. Жуков В. Г. Моделирование сложных систем коэволюционным алгоритмом генетического программирования : дис. Е канд. техн. наук. Красноярск, 2006.

5. Жуков В. Г. О решении проблемы настройки численных коэффициентов при решении задачи символьной регрессии методом генетического программиРис. 7. Сравнительный анализ эффективности стандартных рования // Сб. тр. XII Нац. конф. по искусств. интеллекту и предложенных алгоритмов / Твер. гос. техн. ун-т. Тверь, 2010. С. 311Ц317.

V. G. Zhukov AUTOMATION OF CONSTRUCTION AND OPTIMIZATION OF MATHEMATICAL MODELS EVOLUTIONARY ALGORITHMS BASED ON EXPERIMENTAL DATA The author considers synthesis of evolutionary algorithms for solution of the problem of symbolic regression and optimization, and their proposed modifications, through the development of integrated procedures of automated construction and optimization of mathematical models of complex systems and processes.

Keywords: evolutionary algorithms, symbolic regression, optimization.

й Жуков В. Г., Математика, механика, информатика УДК 658.512.001.М. В. Карасева, А. А. Новожилов, Т. А. Рукавицына К ВОПРОСУ ОЦЕНКИ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ ОРГАНИЗАЦИОННО-ТЕХНИЧЕСКИХ СИСТЕМ* Рассмотрено применение метода DEA и его модификации для оценки эффективности функционирования организационно-технических систем предприятий.

Ключевые слова: метод DEA, многоатрибутивный, организационно-техническая система, критерии оценки.

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

понятием здесь является понятие эффективности - Следует отметить, что значение технической эфнаиболее общего, определяющего свойства любой фективности не может превышать единицы. Объекты, целенаправленной деятельности, которое с познава- для которых значение показателя эффективности тельной точки зрения раскрывается через категорию оказалось равным единице, находятся на границе эфцели и объективно выражается степенью достижения фективности. Для объектов, у которых показатель цели с учетом затрат, ресурсов и времени [1]. Поэто- эффективности оказался меньше единицы, могут быть му оценка эффективности функционирования пред- выданы рекомендации, заключающиеся в выведении приятий и организаций является очень важной для таких объектов на границу эффективности за счет принятия верных управленческих решений. пропорционального сокращения объемов затрачиваеОдним из методов оценки эффективности является мых ими ресурсов при сохранении значений выходметод DEA (Data Envelopment Analysis - анализ вло- ных переменных на прежнем уровне.

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

водственной функции для случая, когда выпуск явля- Можно провести модификацию метода DEA, построется не скалярным, а векторным, т. е. когда выпуска- ив такую же границу, но наоборот, и назвав ее граниется несколько видов продукции. Эта граница имеет цей отставания. Граница отставания показывает убыформу выпуклой оболочки или выпуклого конуса точные или отстающие от основной части выборки в пространстве входных и выходных переменных, объекты, т. е. она является эталоном для получения описывающих каждый объект в исследуемой сово- численного значения оценки отставания каждого купности, и как бы огибает (обертывает) точки, соот- из объектов [2].

ветствующие исследуемым объектам в многомерном После применения к исследуемой выборке объекпространстве. Граница эффективности используется в тов метода DEA и его модификации будут получены качестве эталона (точки отсчета) для получения чис- два показателя:

енного значения оценки эффективности каждого из - мера эффективности объектов;

объектов в исследуемой совокупности. Степень эф- - мера их отставания/убыточности.

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

*Работа выполнена при финансовой поддержке Федеральной целевой программы Научные и научно-педагогические кадры инновационной России на 2009Ц2013 годы и Федеральной целевой программы Исследования и разработки по приоритетным направлениям развития научно-технического комплекса России на 2007Ц2013 годы (проект № 2011-1.9-519-005).

Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Рассмотрим реализацию метода DEA и его моди- - анализируются наборы их входных и выходных фикации на примере организационно-технических параметров;

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

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

взаимодействующей с внешними средой и факторами, Критериями оценки предприятий по сортировке и заканчивая локальным технологическим процессом. твердых бытовых отходов как организационно-техниТакже выделим особенности ОТС предприятий по ческих систем будут энергоэффективность, оптисортировке твердых бытовых отходов [5]: мальность работы технологической линии, степень - в качестве сырья используется в основном сме- автоматизации производства и некоторые другие. На шанная многокомпонентная масса; основании этих критериев можно определить сле - входами служат трудовые и энергетические за- дующие направления по повышению эффективности траты; производства:

Pages:     | 1 |   ...   | 7 | 8 | 9 | 10 | 11 |   ...   | 65 |    Книги по разным темам