Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации

Розглянуто задачу побудови оптимальної регресійної моделі складної системи, що характеризується m вхідними (незалежними) змінними і однією вихідною (залежною) змінною, які мають стохастичний характер. Задача полягає у виборі з усієї множини незалежних змінних такої підмножини, що оптимізує заданий ф...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2008
Автор:	Мельник, И.М.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2008
Назва видання:	Проблемы управления и информатики
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/209131
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации / И.М. Мельник // Проблемы управления и информатики. — 2008. — № 3. — С. 30-42. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-209131
record_format	dspace
spelling	irk-123456789-2091312025-11-16T01:13:27Z Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации Генетичний алгоритм розв’язання задачі побудови оптимальної регресійної моделі як задачі дискретної оптимізації Genetic algorithm for solving the problem of an optimum regression model construction as a discrete optimization problem Мельник, И.М. Оптимальное управление и методы оптимизации Розглянуто задачу побудови оптимальної регресійної моделі складної системи, що характеризується m вхідними (незалежними) змінними і однією вихідною (залежною) змінною, які мають стохастичний характер. Задача полягає у виборі з усієї множини незалежних змінних такої підмножини, що оптимізує заданий функціонал якості моделі. Запропоновано методи розв’язання цієї задачі дискретної оптимізації як задачі пошуку найкоротшого шляху на спеціальному графі. Основну увагу приділено застосуванню ідей генетичного алгоритму евристичного пошуку оптимуму в цій задачі. A task of construction of optimum regressive model of a complex system being characterized by m input (independent) variables and one output (dependent) variable having stochastic character is considered. The task consists in the choice from the set of independent variables of such a subset which optimizes a given functional of model quality. Methods are suggested for solving this task of discrete optimization as a task of search of the shortest path on a special graph. Main attention is focused on application of ideas of genetic algorithm of heuristic search of optimum in this problem. Работа была подготовлена в специальный номер журнала, посвященный 95-летию со дня рождения академика НАН Украины А.Г. Ивахненко. 2008 Article Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации / И.М. Мельник // Проблемы управления и информатики. — 2008. — № 3. — С. 30-42. — Бібліогр.: 8 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/209131 519.8 10.1615/JAutomatInfScien.v40.i6.60 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Мельник, И.М. Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации Проблемы управления и информатики
description	Розглянуто задачу побудови оптимальної регресійної моделі складної системи, що характеризується m вхідними (незалежними) змінними і однією вихідною (залежною) змінною, які мають стохастичний характер. Задача полягає у виборі з усієї множини незалежних змінних такої підмножини, що оптимізує заданий функціонал якості моделі. Запропоновано методи розв’язання цієї задачі дискретної оптимізації як задачі пошуку найкоротшого шляху на спеціальному графі. Основну увагу приділено застосуванню ідей генетичного алгоритму евристичного пошуку оптимуму в цій задачі.
format	Article
author	Мельник, И.М.
author_facet	Мельник, И.М.
author_sort	Мельник, И.М.
title	Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации
title_short	Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации
title_full	Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации
title_fullStr	Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации
title_full_unstemmed	Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации
title_sort	генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2008
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/209131
citation_txt	Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации / И.М. Мельник // Проблемы управления и информатики. — 2008. — № 3. — С. 30-42. — Бібліогр.: 8 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT melʹnikim genetičeskijalgoritmrešeniâzadačipostroeniâoptimalʹnojregressionnojmodelikakzadačidiskretnojoptimizacii AT melʹnikim genetičnijalgoritmrozvâzannâzadačípobudovioptimalʹnoíregresíjnoímodelíâkzadačídiskretnoíoptimízacíí AT melʹnikim geneticalgorithmforsolvingtheproblemofanoptimumregressionmodelconstructionasadiscreteoptimizationproblem
first_indexed	2025-11-16T02:05:28Z
last_indexed	2025-11-17T02:08:25Z
_version_	1849001566751686656
fulltext	© И.М. МЕЛЬНИК, 2008 30 ISSN 0572-2691 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 519.8 И.М. Мельник ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ПОСТРОЕНИЯ ОПТИМАЛЬНОЙ РЕГРЕССИОННОЙ МОДЕЛИ КАК ЗАДАЧИ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ  Введение Задача построения оптимальной регрессионной модели заключается в выборе из общего множества независимых переменных (регрессоров) некоторого их под- множества для включения в конечную регрессионную модель. Эта, вообще гово- ря, многоэкстремальная задача дискретной оптимизации переборного типа в на- стоящее время не имеет достаточно эффективных алгоритмов ее решения в случае большого числа регрессоров, поскольку для получения точного решения требует- ся выполнить полный перебор всех возможных вариантов. В настоящей статье такая задача формулируется как задача дискретной оп- тимизации на графе. Предлагаются некоторые алгоритмы ее решения как специ- альной задачи поиска кратчайшего пути на графе. Особенное внимание уделяется применению идей классического генетического алгоритма [1, 2] для эвристиче- ского поиска оптимума в этой сложной задаче. 1. Постановка задачи построения оптимальной регрессионной модели Рассматривается система, которая характеризуется m входными (независимы- ми) переменными mi xxx ,,,,1  и одной выходной (зависимой) переменной y, имеющими стохастический характер и заданными выборкой n статистических на- блюдений входных и выходной переменных. В процессе идентификации генери- руются структуры линейных регрессионных моделей, параметры которых оцени- ваются методом наименьших квадратов (МНК). Задан некоторый функционал оценки модели F, т.е. функционал выбора оптимальной регрессионной модели. Этот функционал может зависеть от сложности модели (количества оцениваемых параметров) и/или невязок уравнений регрессии на некотором подмножестве ста- тистических выборок и других параметров модели. Следовательно, задачу построения оптимальной регрессионной модели можно сформулировать так: из всего множества входных переменных mi xxx ,,,,1  необходимо выбрать такое их подмножество, чтобы регрессионная модель, по- строенная на этом подмножестве, имела оптимум (минимум или максимум) за- данного функционала оценки качества модели F. Соответствующую регрессион-  Работа была подготовлена в специальный номер журнала, посвященный 95-летию со дня рождения академика НАН Украины А.Г. Ивахненко. Проблемы управления и информатики, 2008, № 3 31 ную модель, в которую включены только переменные (регрессоры) из выбранного подмножества, будем называть оптимальной моделью. Такого рода задачи решает комбинаторный алгоритм метода группового учета аргументов (МГУА) [3]. В данной статье такую задачу выбора оптимальной регрессионной модели предлагается формулировать и решать как задачу дискретной оптимизации на специальном графе ).,( UI Множество вершин I этого графа определяется сле- дующим образом. Каждой независимой переменной ,,,1, mixi  ставится в со- ответствие вершина графа i и дополнительно задаются еще две вершины: 0 и .1m Множество дуг U строится так: вершина 0 соединяется с каждой вершиной i, ,,,1 mi  дугой ),,0( i а каждая i-я вершина соединяется с каждой j-й, ,ij  дугой ).,( ji Считается, что вершина i, ,,,1 mi  отвечает ситуации, когда независимая переменная ix включается в регрессионную модель. Тогда каждому пути из вер- шины 0 в вершину 1m отвечает определенный вариант построения регрессион- ной модели, в которую включаются независимые переменные ,ix отвечающие вершинам графа ),,( UI через которые проходит этот путь. Каждому пути  из вершины 0 в вершину 1m ставится в соответствие его «длина», равная значе- нию функционала оценки F для регрессионной модели, соответствующей этому пути. Итак, исходная задача построения регрессионной модели (задача селекции набора регрессоров, на которых строится эта модель) сводится к определению кратчайшего пути из вершины 0 в вершину 1m на графе ).,( UI Граф ),( UI позволяет последовательно, экономным способом организовать конструирование и перебор вариантов решения задачи выбора оптимальной рег- рессионной модели и их сопоставление между собой. Определение кратчайшего пути на построенном графе ),( UI и дает решение исходной задачи выбора опти- мальной регрессионной модели. 2. Переборные алгоритмы построения оптимальной модели Предлагаются два варианта переборного алгоритма решения задачи построе- ния оптимальной регрессионной модели как задачи определения кратчайшего пу- ти на графе с помощью процедуры последовательного отмечания вершин этого графа специальными метками с возможным отсевом неперспективных вариантов на этапе конструирования решения. В первом варианте алгоритма функционал оценки качества регрессионной модели включает как оценку сложности модели, так и квадраты невязок уравнений регрессионной модели на всем множестве эле- ментов статистической выборки. Во втором варианте алгоритма при разбиении всего множества статистической выборки на два подмножества, что типично для МГУА [3], решается минимаксная задача дискретной оптимизации для квадратов невязок регрессионной модели на одном из подмножеств выборки. Оптимизация модели по квадратичному критерию. Первый вариант алго- ритма — это решение задачи построения оптимальной модели для функционала, зависящего от сложности модели (суммы соответствующих весов для множества регрессоров, которые включаются в модель) и квадратов невязок уравнений рег- рессии на всей выборке, т.е. необходимо выбрать такое подмножество J из мно- жества },,,1{ m что ,min))(( 1 2      n k Ji k ii k Ji i xJayC (1) 32 ISSN 0572-2691 где ,),( JiJai  — коэффициенты регрессионной модели, найденные по МНК для набора регрессоров J; }/{ 1XxiJ i  — подмножество множества номеров входных независимых переменных };,,1{ m 1X — соответствующее подмноже- ство входных переменных; iC — некоторый показатель сложности модели, или некоторые «расходы» на получение и обработку статистической информации о значении независимой переменной ., Jixi  Пусть существуют два подмножества 1J и 2J из множества },,1{ m номе- ров независимых переменных ,,,1, mixi  т.е. }.,,1{},,,1{ 21 mJmJ   Лемма 1. Если ,21 JJ  то для этих подмножеств выполняется соотношение .)()( 2 2 1 2 1 1 21                     k ii Ji k n k k ii Ji k n k xJayxJay (2) Как и в [3], сформируем вариант регрессионной модели (вариант совокупности переменных ix для модели (1)) в соответствии со значениями булевых перемен- ных ,,,1, mii  в векторе :),,( 1 m  если ,1i то независимая пере- менная ix включается в регрессионную модель (1), в противном случае, при ,0i она не включается. Итак, задача (1) выбора оптимальной регрессионной модели формулируется так же, как задача дискретной оптимизации или целочисленного булевого про- граммирования: необходимо найти минимум функционала 2 11 )(            i k i Ji i k n k i m i i xJayC (3) при условиях },1,0{i (4) где },1{  iiJ а коэффициенты ),(Jai ,Ji определяются по МНК. Это типичная задача отыскания соответствующего кратчайшего пути из вер- шины 0 в вершину .1m Для варианта функционала оценки модели (3) каждому пути из вершины 0 в 1m поставим в соответствие его длину, равную ,),,( 2 1 111               lp p i k n k p l i xiiayC (5) где р — количество вершин в пути, или оцениваемых параметров. Если опреде- лить, что кратчайшему пути из вершины 0 в вершину 1m соответствует мини- мальное значение функционала (5), то исходная задача сводится к минимизации (5). Процедура построения множества меток вершин графа. Задачу определе- ния кратчайшего пути из вершины 0 в вершину 1m на графе будем решать с помощью процедуры последовательного отмечания вершин этого графа специ- альными метками, т.е. построением меток этих вершин [4]. Для случая функционала оценки (1) (или (5)) каждая метка iP вершины i, ,Ii которой соответствует путь ],,,0[ 10 iiii   из вершины 0 в верши- ну i, состоит из четырех признаков (чисел): ),,,,( 4321 iiiii PPPPP  где 1 iP — по- рядковый номер этой метки для вершины i; 2 iP — вершины из множества },...,,1{ m через которые проходит путь ],,,,[ 10  iiii  т.е. },,,{ 1 2  iiPi  ес- Проблемы управления и информатики, 2008, № 3 33 ли ,1 mi и },,,1{ 1 2   iPi если ;1 mi     1 3 r ii r CP — признак равен сумме iC для всех вершин пути ; ,)},,({ 2 1 1 1 4            k i r i k n k i rr xiiayP   т.е. 4 iP равно значению квадратов суммы невязок уравнений регрессии в (5) на множест- ве вершин пути i (на множестве }).,,{ 1  ii Множество вариантов путей из вершины 0 в вершину 1m на графе ),( UI (т.е. множество вариантов решения задачи выбора оптимальной модели по функ- ционалу оценки (1)) определяется процедурой последовательного отмечания вер- шин этого графа специальными метками с отсевом на этапе конструирования пу- тей явно неперспективных вариантов с применением леммы 1 (формулы (2)). Процедура построения множества меток вершин графа ),( UI осуществляет- ся в несколько этапов. Первый (начальный) этап заключается в назначении на- чальных значений числовых признаков для меток вершин графа. Основной, второй этап, заключается в собственно построении всего множе- ства меток вершин графа. Каждая метка вершины i — это соответствующий путь через вершины этого графа из 0 в i, и он же служит начальным отрезком подмно- жества путей из 0 в 1m . По каждой метке вершины i продолжается отрезок это- го пути в вершины, соседние с вершиной i, с помощью присвоения новых меток этим соседним вершинам. Причем на этом этапе существенно используется лем- ма 1 для конструирования только перспективных продолжений пути из вершины i в соседние с ней. Процедура порождения новых меток продолжается, пока появ- ляются новые метки, т.е. пока строятся новые варианты перспективных путей в вершину .1m Вершина 1m отмечается метками соответственно выбранному правилу формирования конечного набора вариантов решения исходной задачи построения оптимальной регрессионной модели. На последнем, заключительном этапе, по метке (меткам) вершины 1m опре- деляются номера вершин графа, через которые проходит именно кратчайший путь из вершины 0 в .1m Эти номера вершин и дают подмножество номеров пере- менных, которые необходимо включить в оптимальную регрессионную модель. Оптимизация модели по минимаксному критерию. Второй вариант алго- ритма решения задачи построения оптимальной регрессионной модели — это ре- шение задачи для минимаксного функционала оценки модели. Рассматривается следующий критерий выбора регрессионной модели. Мно- жество точек выборки },,1{ nS  разбито на две части — 1S и ,2S что типично для МГУА [3]. На первой части выборки (подмножестве) 1S строится регресси- онная модель, а на второй 2S вычисляется значение функционала качества по- строенной модели ,))(max)( 2 2            k ii Ji k Sk xJayJF (6) где }/{ 1XxiJ i  — подмножество из множества номеров независимых пере- менных },,,1{ mI  1X — подмножество входных переменных, на которых строится регрессионная модель. Значение функционала (6) вычисляется как мак- симальное значение квадрата невязок между значением выходной переменной y и значением регрессионной модели по всем k-м, ,1Sk  наблюдениям значений входных независимых переменных из .1X 34 ISSN 0572-2691 Необходимо выбрать такую регрессионную модель (подмножество номеров независимых переменных J из множества }),,,1{ mI  для которой значение функционала (6) принимает минимальное значение, т.е. решить задачу 2 )(maxmin 2           k ii Ji k SkIJ xJay (7) по всем подмножествам J из }.,,1{ m Алгоритм решения задачи (7) выбора оптимальной регрессионной модели как задачи отыскания соответствующего кратчайшего пути, определенного значе- ниями функционала (6), аналогичен алгоритму для первого варианта, только с не- которыми вычислительными модификациями. Например, отсутствует признак ,3 iP а 4 iP вычисляется по формуле (6). Поскольку аналог леммы 1 для этого вари- анта функционала выбора модели можно использовать как гипотезу, то этот алго- ритм обеспечивает эффективное определение соответствующего приближения к оптимальному решению начальной задачи. Следует отметить, что функционал (6) имеет детерминированный (не стохас- тический) характер, хотя сам моделируемый процесс стохастический, поэтому может представлять интерес функционал оценки модели в стохастическом виде, например с использованием вероятностных ограничений bmin при условии ,)( 2 pbxJayP ii IJ                в котором b — оценка значения квадратов невязок уравнений регрессии на под- множестве статистических выборок, где вычисляется значение функционала оценки модели; p — соответствующий порог вероятности для этой оценки. Рас- смотрение и исследование этого варианта может быть предметом отдельной пуб- ликации, однако заметим, что алгоритмический подход к решению этой задачи указан в [7]. Алгоритмы переборного типа решения задачи построения оптимальной рег- рессионной модели эффективны для не слишком больших размерностей (коли- честв заданных входных переменных). Для достаточно большого количества входных переменных (регрессоров) m предлагается генетический алгоритм реше- ния задачи выбора оптимальной регрессионной модели, который хоть и не гаран- тирует большой точности, но может давать достаточно удовлетворительное ре- шение исходной задачи. 3. Генетический алгоритм решения задачи построения оптимальной модели 3.1. Основные положения алгоритма. Идея классического генетического ал- горитма (ГА) предложена в Мичиганском университете Дж. Холландом [1]. Этот алгоритм часто позволяет найти удовлетворительное решение аналитически не- разрешимых (или трудноразрешимых) проблем посредством подбора и конструи- рования соответствующих процедур вычислительного процесса на основе меха- низмов, аналогичных генетическим процессам эволюции в мире живых организ- мов. Главная особенность ГА состоит в том, что на каждом его шаге (итерации) анализируется не одно решение (хромосома), а некоторое их подмножество. Каж- дое решение представляется в виде булевого вектора, компоненты которого при- нимают значение 0 или 1 и называются генами. Это подмножество достаточно Проблемы управления и информатики, 2008, № 3 35 «хороших» хромосом называется популяцией. На каждом цикле ГА на базе теку- щей популяции посредством применения основных процедур алгоритма — крос- совера (скрещивания), мутации и селекции — осуществляется процесс дополни- тельной генерации новых хромосом, которые называются потомками. При этом итерационный процесс строится таким образом, что каждая последующая попу- ляция должна быть «лучше» предыдущей. Итак, для рассматриваемой задачи, в соответствии с терминологией и опре- делениями теории ГА [1, 2], каждый путь из вершины 0 в вершину 1m на графе ),( UI (т.е. соответствующий вариант выбора регрессионной модели), которому отвечает булевый вектор размерности m, представляет собой хромосому соответ- ствующей популяции, а каждый элемент этого булевого вектора — ген этой хро- мосомы. Для каждой хромосомы (пути)  на основе значений целевой функции F для всех хромосом популяции определим функцию приспособляемости ( )(P таким образом: ,)(/)()(         FFFP (8) F — оператор суммирования по всем хромосомам популяции. Лемма 2. Если некоторая хромосома дает локальный (глобальный) оптимум исходной задачи выбора оптимальной регрессионной модели (для целевой функ- ции )),(F то та же хромосома соответствует локальному (глобальному) оптиму- му функции приспособляемости P, и наоборот. Лемма 3. Если 1 и 2 — хромосомы соответствующей популяции и ),()( 21  FF то ).(/)()(/)( 2121  PPFF Определим, что популяция k-го типа — это множество хромосом (путей из вершины 0 в вершину ),1m которые обязательно содержат вершину с номером k, 0k (т.е. переменную ),kx а также, возможно, еще и вершины, номера кото- рых больше k. Таким образом, общее множество популяций разбивается на m подмножеств (m типов популяций), которые не пересекаются и в сумме дают множество общей популяции. Это означает, что в графе ),( UI выделяются m частичных подграфов ),,( kk UI ;,,1 mk  kI — подмножество вершин из множества вершин I основного графа ),,( UI }.,,0{ kikIk  При этом kU — подмножество дуг из множества дуг U основного графа ),,( UI ),,();,0{( jkkU k  ,kIj ;kj  ),,( ji }.,,, jikiIji k  Каждый путь в графе ),,( kk UI ,,,1 mk  из вершины 0 в вершину 1m (он обязательно про- ходит через вершину с номером k) — это некоторая популяция (хромосома) из всех популяций k-го типа, представляющая собой соответствующее решение (ко- торое обязательно включает переменную )kx исходной задачи по выбору опти- мальной регрессионной модели. Предложенный генетический метод представляет собой итерационный алго- ритмический процесс. На каждой текущей итерации t, ,,1,0 t к подмножеству популяций k-го типа ),1( tWk полученному на предыдущей итерации, применя- ются основные процедуры ГА: кроссовер — выработка новых популяций k-го ти- па путем скрещивания, мутация и селекция, а также, дополнительно, процедура обмена (миграции) между подмножествами популяций различных типов. В ре- зультате получается новое текущее подмножество популяций k-го типа ),(tWk ко- 36 ISSN 0572-2691 торое, как правило, «лучше» предыдущего )1( tWk и которое, в свою очередь, в дальнейшем подвергается действиям вычислительных процедур ГА на )1( t -й итерации. Этот итерационный процесс продолжается до тех пор, пока текущие подмножества популяций k-го типа улучшаются. В этой модели ГА важное значе- ние имеет процедура построения начальных подмножеств популяций k-го типа ),0(kW .,,1 mk  3.2. Процедура построения начальных подмножеств популяций всех ти- пов. Выбор начального подмножества k-го типа популяции осуществляется спе- циальным вариантом метода меток на графе ),( kk UI [4]. У каждой вершины i может быть одна или несколько меток. Каждая метка вершины i содержит четы- ре признака (числа): ),,,,( 21 iiii LPPN здесь iN — номер предыдущей вершины; 1 iP — номер метки для предыдущей вершины; 2 iP — текущий номер этой метки для вершины i; iL — значение функционала оценки соответствующей регресси- онной модели. Для каждой дуги kUji ),( графа ),( kk UI вводится вероятност- ный датчик }1,0{ij со значениями 0 или 1 и с дискретным распределением ве- роятностей ),1,( ijij pp  где .10  ijp Процедура определения начального подмножества популяций k-го ти- па (0).kW Опишем эту процедуру для второго случая задания функционала оценки модели, т.е. для минимаксного функционала оценки выбора оптимальной регрессионной модели. Начальный (нулевой) этап. Вводим счетчик iP меток вершины i, ,1 ki ,1,, mm который на каждой итерации определяет количество уже сделанных меток для этой вершины. Вначале полагаем значение этих счетчиков равным 0. Вводим для дуги ,),( kUji  ,,,1, mkki  вероятностный датчик }1,0{ij с дискретным распределением вероятностей ),1,( ijij pp  где вероятность 10  ijp задается. Первый этап. На этом этапе отмечаем метками вершины 0 и k (которые будут иметь только по одной метке). Вершину 0 отмечаем меткой ,0,0( 1 00 1 0  PNR ).0,1 0 2 0  LP По этой метке 1 0R отмечаем вершину k меткой ,0(1  kk NR ),,1,1 21 kkk LPP  где ,)(max 2 2 s kk s Ss k xayL   а ka определяется по МНК, когда набор регрессоров состоит из одной переменной kx на статистической выборке 1S значений переменной .kx Основной этап отмечания метками вершин графа ).,( kk UI Отмечание вер- шин ,1k ,,,2 mk  а также ,1m выделено в отдельный (основной) этап, по- тому что у них (кроме вершины )1k может быть более одной метки. Поскольку эти вершины отмечаются с учетом результатов розыгрыша значений вероятност- ных датчиков },1,0{ij ,),( kUji  то они могут и не иметь ни одной метки. Процедура отработки вершины k. По метке ),1,1,0( 211 kkkkk LPPNR  вершины k осуществляем процедуру отмечания вершины .1k Для этого разыг- рываем для дуги ),( 1kk ii значения вероятностного датчика .1,  kk Если при этом выпало значение датчика, равное 1, то вершину 1k отмечаем меткой Проблемы управления и информатики, 2008, № 3 37 ),,1,,( 11 2 1 21 11 1 1   kkkkkkk LPPPPkNR .)max 2 1 1 2              s ll k kl s Ss k xayL Коэффициенты ka и 1ka определяются по МНК для набора регрессоров kx и 1kx на статистической выборке 1S значений этих переменных (регрессоров). Увеличиваем значение счетчика 1kP количества меток вершины 1k на 1. По- лагаем для датчика 1,  kk новое распределение вероятностей )0,1( и переходим к рассмотрению процедуры отмечания для вершины .2k Если же при розы- грыше значений вероятностного датчика }1,0{1,  kk выпал 0, то переходим сразу к процедуре отмечания для вершины .2k По метке 1 kR вершины k осуществляем процедуру отмечания для вершины .2k Разыгрываем для дуги ),( 2kk ii значения вероятностного датчика  2,kk }1,0{ с дискретным распределением вероятностей ).1,( 2,2,   kkkk pp Если при этом выпало значение датчика, равное 1, то отмечаем вершину 2k меткой ),,1,,( 22 2 2 21 22 1 2   kkkkkkk LPPPPkNR .))((max 2 222 2 s kk s kk s Ss k xaxayL     Коэффициенты ka и 2ka определяются по МНК для набора регрессоров kx и 2kx на выборке .1S Увеличиваем значение счетчика 2kP меток вершины 2k на 1. Полагаем для датчика 2,  kk новое распределение вероятностей 2,kkp )0,1( и переходим к процедуре отмечания для вершины .3k Если же при ро- зыгрыше значений датчика }1,0{2,  kk выпал 0, то переходим сразу к проце- дуре отмечания для вершины .3k Осуществляем по метке 1 kR вершины k процедуру отмечания для вершин ,3k 4k и т. д., пока не дойдем до вершины m. Разыгрываем для дуги ),( mik значения вероятностного датчика }1,0{,  mk с дискретным распределением ве- роятностей ).1,( ,, mkmk pp  Если при этом выпало значение датчика, равное 1, то по метке 1 kR вершины k отмечаем вершину m меткой ),,1,,( 2211 mmmkmmm LPPPPkNR  .))((max 2 2 s mm s kk s Ss m xaxayL   Коэффициенты ka и ma определяются по МНК для набора регрессоров kx и mx на выборке 1S значений kx и .mx Увеличиваем значение счетчика mP меток вершины m на 1. Полагаем для датчика mk, новое распределение вероятностей )0,1( и переходим к процедуре отмечания вершины 1m по метке .1 kR Если же при розыгрыше значений веро- ятностного датчика mk, выпал 0, то переходим сразу, без отмечания вершины m, к отмечанию вершины .1m По метке ),1,1,0( 211 kkkkk LPPNR  вершины k отмечаем вершину 1m меткой ).,1,,( 11 2 1 21 11 1 1 kmmmkmmm LLPPPPkNR   Увеличиваем зна- 38 ISSN 0572-2691 чение счетчика 1mP меток вершины 1m на 1. Таким образом, на этом шаге ос- новного этапа полностью использованы метки вершины k для процедур отмеча- ния вершин ,1k mk ,,2  и .1m Процедура отработки вершины 1.k Если вершина 1k имеет метку ),,,( 1 2 1 1 11 1 1   kkkkk LPPNR (у нее может быть только одна метка), она ис- пользуется для отмечания вершин ,2k ,,,3 mk  а также ,1m следующим образом. Для дуги ),( 21  kk ii разыгрываем значения вероятностного датчика   2,1 kk }1,0{ с дискретным распределением вероятностей ).1,( 2,12,1   kkkk pp Если при этом выпало значение, равное 1, то отмечаем вершину 2k меткой ),,1,,1( 22 2 2 2 1 1 222   kkkkkk q k LPPPPkNR ,max 2 2 1 2 2              s ll k kl s Ss k xayL .12  kPq Коэффициенты 1ka и 2ka определяются по МНК для набора регрессоров 1kx и 2kx на выборке 1S значений 1kx и .2kx Увеличиваем значение счетчика 2kP меток вершины 2k на 1. Полагаем для датчика 2,1  kk новое распределение вероятностей )0,1( и переходим к рас- смотрению процедуры отмечания вершины .3k Если же при розыгрыше значе- ний датчика }1,0{2,1   kk выпал 0, то переходим сразу к процедуре отмечания вершины .3k Рассматриваем использование метки 1 1kR вершины 1k для от- мечания вершины 3k и т. д., пока не дойдем до вершины m. Далее для дуги ),( 1 mik разыгрываем значения ее датчика }1,0{,1   mk с распределением ).1,( ,1,1 mkmk pp   Если выпало значение ,,1mk равное 1, то по метке ),,,( 1 2 1 1 11  kkkk LPPN вершины 1k отмечаем вершину m меткой ),,1,,1( 22 1 1 mmmkmm q m LPPPPkNR   ,1 mPq .))((max 2 11 2 s mm s kk s Ss m xaxayL    Коэффициенты 1ka и ma определяются по МНК для набора регрессоров 1kx и mx на выборке .1S Процедура отработки последующих вершин. Увеличиваем значение счет- чика mP меток вершины m на 1. Полагаем для датчика mk ,1 новое распределе- ние )0,1( и переходим к отмечанию вершины 1m по метке 1 1kR вершины .1k Если же по датчику mk ,1 выпал 0, то переходим сразу, минуя m, к отме- чанию вершины .1m По метке ),,,( 1 2 1 1 11  kkkk LPPN вершины 1k отмечаем вершину 1m меткой ).,1,,1( 11 2 1 2 1 1 11   kmmmkmm LLPPPPkN Увеличиваем значение счетчика 1mP меток вершины 1m на 1. Далее работаем с метками вершины 2k (если они есть) для использования их в процедуре отмечания вершин ,3k ,,,4 mk  а также .1m У вершины 2k может быть не более двух меток (одна — метка ),,,( 21 kkkk LPPN по верши- Проблемы управления и информатики, 2008, № 3 39 не k, а другая — метка ),,,( 1 2 1 1 11  kkkk LPPN по вершине 1k (если она была отмечена ранее)). Берем первую метку ),,,( 2 2 2 1 22 1 2   kkkkk LPPNR вершины 2k . По ней отмечаем все вершины от 3k до .1m Затем аналогично посту- паем со второй меткой вершины 2k (если она есть). Переходим к меткам вер- шины 3k (их может быть не более трех) и так до тех пор, пока не дойдем до вершины .1m По меткам вершины 1m (их может быть не более чем )1 km поочеред- но, в соответствии с розыгрышами значений вероятностного датчика   mm ,1 },1,0{ отмечаем (или не отмечаем) вершину m. После этого по меткам вершины 1m отмечаем вершину .1m Далее переходим к рассмотрению меток вершины m (их может быть не более чем ).km  По ее меткам отмечаем поочередно соот- ветствующими метками вершину .1m Этап формирования начального подмножества популяций k-го ти- па (0).kW По меткам вершины 1m проверяем, содержит ли начальное подмно- жество популяций k-го типа соответствующее количество популяций (хромосом). Будем считать, что этот тип популяции должен содержать kN особей, число kN определяется заранее соответствующим образом. Если нет, то переходим к началу процедуры определения начального подмножества популяций k-го типа для полу- чения новых меток вершины 1m (а значит, и новых популяций k-го типа). Если же вершина 1m имеет соответствующее количество меток, то, по существу, на- чальное подмножество популяций k-го типа построено. Каждой метке вершины 1m соответствует путь на графе ),( kk UI из вершины 0 в вершину 1m , кото- рый отвечает одному из решений основной задачи выбора оптимальной регресси- онной модели. 3.3. Основные шаги процесса вычислений на одной итерации алгоритма. Опишем t-ю, ,,2,1 t итерацию вычислительного процесса предлагаемого ГА для решения задачи выбора оптимальной регрессионной модели. Для выполне- ния этой итерации после предыдущей )1( t -й имеются подмножества популя- ций m типов: ).1(,),1(,),1(),1( 21  tWtWtWtW mk  Подмножества ),0(1W )0(,),0(,),0(2 mk WWW  для первой итерации )1( t определяются описанной процедурой определения начального подмножества популяций k-го типа, .,,1 mk  Большой цикл. Выбор поочередно номера типа популяции k, .,,1 mk  Малый цикл. Шаг 1. Представление для вычислительного генетического процесса на t-й итерации подмножества популяций k-го типа ),1( tWk которое содержит kN особей. Шаг 2. Выбор «родителей» из популяции хромосом k-го типа на основе соче- тания двух принципов: инбридинга и аутбридинга. Эти принципы построены на формировании популяций хромосом-родителей соответственно на основе близко- го и далекого «родства». Под родством хромосом-родителей понимается расстояние между членами популяции в смысле меры Хемминга (Hamming distance) между наборами (векторами булевых переменных) хромосом-родителей. Сначала при- меняем, например, принцип аутбридинга (далекого родства хромосом-родителей) для выбора конкретной пары родителей, а через определенное количество итера- ций переходим на принцип инбридинга (близкого родства). Инбридинг характе- ризуется свойством концентрации поиска в локальных узлах, что фактически 40 ISSN 0572-2691 приводит к разбиению подмножества популяции k-го типа на отдельные локаль- ные группы вокруг решений, которые предполагаются оптимальными, а аутбри- динг направлен на предупреждение сходимости алгоритма к уже найденным ре- шениям с целью просмотра новых, неисследованных областей поиска решений. Шаг 3. Кроссовер (скрещивание) пары хромосом-родителей для генерации хромосом-детей (потомков). Процедура скрещивания осуществляется так. Берут- ся хромосомы родителей 1 и 2 и соответственно их функции приспособляе- мости )( 1F и ).( 2F Вычисляются значения ))()(/()( 2111  FFFp и 2p )).()(/()( 212  FFF Строится вероятностный датчик }0,1{ с распреде- лением вероятностей ).1,( 121 ppp  Для каждого гена хромосомы-родителя 1 и 2 разыгрываются значения вероятностного датчика . Если выпадает 1, то значение соответствующего гена хромосомы-потомка (соответствующей компо- ненты m-мерного булевого вектора) полагается равным значению гена хромосо- мы-родителя ,1 в противном случае — значению гена хромосомы-родителя .2 Соответственно определяются значения каждого гена хромосомы-потомка. Таким образом, на основе двух хромосом-родителей определяется одна хромосома-пото- мок. Если необходимо, то для этой пары родителей так же определяем еще не- сколько хромосом-потомков. Шаг 4. Вычисляются значения целевой функции F и функции приспособляе- мости P для хромосом-потомков. Шаг 5. Проведение процедуры мутации для хромосом-потомков с целью ге- нерации хромосом-мутантов. Для этого значение каждого гена хромосомы- потомка с вероятностью mp /1 меняется на противоположное, т.е. 1 на 0 и на- оборот — 0 на 1. Шаг 6. Вычисление значений целевой функции F и функции приспособляе- мости P для хромосом-мутантов. Шаг 7. Проверка окончания процесса вычислений для популяций типа k. Ес- ли да, то переходим к следующему шагу. Если нет, то переходим к шагу 2 малого цикла для определения новых пар хромосом-родителей и вычисления на их осно- ве новых хромосом-потомков. Шаг 8. Проведение процедуры миграции между подмножествами популяций k-го и других типов. На первой итерации, когда популяции )1( k -го и k-го типов уже определены, а )1( k -го — еще нет, осуществляется миграция между популя- циями )1( k -го и k-го типов, а на последующих итерациях — и между популя- циями )1( k -го и k-го типов. Для этого выбирается одна хромосома (или не- сколько) из подмножества популяций )1( k -го типа; из нее (из них) исключается переменная с номером 1k и полученная хромосома включается в популяцию k-го типа. Миграция между популяциями )1( k -го и k-го типа осуществляется так: выбирается одна хромосома (или несколько) из подмножества популяций )1( k -го типа, в нее включается переменная под номером k и полученная хромо- сома включается в популяцию k-го типа. Для новых хромосом вычисляются значения целевых функций F и функций приспособляемости P. Шаг 9. Проведение процедуры селекции для генерации итогового подмноже- ства )(tWk популяций k-го типа на этой итерации. Из всего подмножества попу- ляций k-го типа, которые, в дополнение к подмножеству ),1( tWk получены в ре- Проблемы управления и информатики, 2008, № 3 41 зультате процедур скрещивания, мутации и миграции, исключаем все те, у кото- рых значение функции приспособляемости наименьшее, при условии, что оста- нется kN популяций. В результате получаем подмножество )(tWk популяций k- го типа для последующих преобразований на )1( t -й итерации. Шаг 10. Переход к следующему шагу малого цикла для выбора следующего номера типа популяции (с проверкой условия ).mk  Если ,mk  то переходим на большой цикл для выполнения следующей )1( t -й итерации. Предложенная модель ГА относится к так называемым «островным» моде- лям [8], или моделям параллельного ГА, в которых основная популяция разбива- ется на несколько различных типов (видов) популяций. Каждая из них развивает- ся отдельно на основе некоторого ГА (возможно, что к разным типам популяций могут применяться различные варианты (схемы) этого алгоритма). Можно образно сказать, что особи (хромосомы) общей популяции расселены, если по определенному правилу она сегментирована на некоторое количество ти- пов частных популяций по нескольким изолированным островам. Изредка может происходить миграция между островами — типы популяций (острова) меняются определенными «хорошими» особями (хромосомами). Поскольку в вычислитель- ном аспекте ГА имеет стохастический характер, то при разных его запусках попу- ляции могут сходиться к разным «хорошим» решениям. Островная модель позво- ляет параллельно запустить ГА сразу несколько раз и сопоставить «достижения» на разных островах для получения наилучшего общего решения. Выводы 1. Представление задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации позволяет эффективно использовать инструмен- тарий технологии поиска кратчайшего пути на специальном графе. 2. Предложены два критерия оценки качества построения оптимальной регрес- сионной модели, из которых минимаксный критерий оценки построения регресси- онной модели является оригинальным и представляет значительный практический интерес. 3. Проанализированы алгоритм переборного типа и ГА для поиска кратчай- шего пути как решения исходной задачи построения регрессионной модели, из них особый интерес представляет ГА. 5. Предлагаемый ГА решения исходной задачи построения оптимальной рег- рессионной модели относится к так называемым островным моделям, которые по- зволяют эффективно решать общую глобальную задачу оптимизации путем рас- параллеливания общего вычислительного процесса на процессы решения отдель- ных локальных подзадач. І.М. Мельник ГЕНЕТИЧНИЙ АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ ПОБУДОВИ ОПТИМАЛЬНОЇ РЕГРЕСІЙНОЇ МОДЕЛІ ЯК ЗАДАЧІ ДИСКРЕТНОЇ ОПТИМІЗАЦІЇ Розглянуто задачу побудови оптимальної регресійної моделі складної системи, що характеризується m вхідними (незалежними) змінними і однією вихідною (залежною) змінною, які мають стохастичний характер. Задача полягає у виборі 42 ISSN 0572-2691 з усієї множини незалежних змінних такої підмножини, що оптимізує заданий функціонал якості моделі. Запропоновано методи розв’язання цієї задачі дис- кретної оптимізації як задачі пошуку найкоротшого шляху на спеціальному графі. Основну увагу приділено застосуванню ідей генетичного алгоритму ев- ристичного пошуку оптимуму в цій задачі. I.M. Melnik GENETIC ALGORITHM FOR SOLVING THE TASK OF AN OPTIMUM REGRESSION MODEL CONSTRUCTION AS A DISCRETE OPTIMIZATION PROBLEM A task of construction of optimum regressive model of a complex system being characterized by m input (independent) variables and one output (dependent) variable having stochastic character is considered. The task consists in the choice from the set of independent variables of such a subset which optimizes a given functional of model quality. Methods are suggested for solving this task of discrete optimization as a task of search of the shortest path on a special graph. Main attention is focused on application of ideas of genetic algorithm of heuristic search of optimum in this problem. 1. Holland J.H. Adaptation in natural and artificial systems. — Ann Arbor : Michigan University Press, 1975. — 435 р. 2. Goldberg D.S. Genetic algorithms in search, optimization, and machine learning. — Boston : Addsson-Wesley, 1989. — 416 р. 3. Ивахненко А.Г., Степашко В.С. Помехоустойчивость моделирования. — Киев : Наук. дум- ка, 1985. — 216 с. 4. Ермольев Ю.М., Мельник И.М. Экстремальные задачи на графах. — Киев : Наук. думка, 1967. — 169 с. 5. Мельник І.М., Степашко В.С. Про один підхід до вибору оптимальної регресійної моделі методом дискретної оптимізації // Зб. праць Міжнародного семінару з індуктивного моде- лювання. — Київ : МННЦ ІТС НАН та МОН України, 2005. — С. 223–229. 6. Мельник І.М. Генетичний метод структурно-параметричної ідентифікації регресивної мо- делі складної системи // Мат. XIV Міжнар. конф. з автоматичного управління (Автоматика- 2007). Севастополь, 10–14 вересня 2007 р. Ч. 1. — Севастополь : Cевастопольський націо- нальний ун-т ядерної енергії та промисловості, 2007. — С. 80–82. 7. Ермольев Ю.М., Мельник И.М. О методах стохастического программирования с конечным числом испытаний // Кибернетика. — 1974. — № 4. — С. 82–84. 8. Whitley W.D., Rana S.B., Heckendorn R.B. Island model genetic algorithms and linearly separable problems // Selected Papers from AISB Workshop on Evolutionary Computing. — London : Springer-Verlag, 1997. — P. 109–125. Получено 28.12.2007

Генетический алгоритм решения задачи построения оптимальной регрессионной модели как задачи дискретной оптимизации

Репозитарії

Схожі ресурси