Разработка и исследование метода компараторной идентификации модели многофакторного оценивания

P(xi) = Qi,

где Qi - количественная оценка полезности i-ой альтернативы.

Полученные уравнения могут быть добавлены к рассмотренным выше системам уравнений и неравенств (1.14), (1.17), (1.19).

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

Количество уравнений и неравенств, необходимых для решения конкретной задачи идентификации, зависит от особенностей идентифицируемого процесса, структуры оператора Р, условий проведения эксперимента и т.п. Следует учесть, что соотношения вида (1.11) более информативны, чем (1.12) и (1.13), так как в принципе позволяют однозначно определить неизвестные параметры Р в то время, как соотношения (1.12) и (1.13) определяют только некоторую область допустимых значений этих параметров, выбор из которой единственного решения требует дополнительной информации.

Обобщенная модель оценивания может быть записана в виде

где VM(хi) - обобщенная оценка полезности альтернативы xi;

РM - оператор модели оценивания;

K(xi) - m-мерное количественно измеренное входное воздействие (частные характеристики, определяющие альтернативу);

АM - r-мерный вектор количественных характеристик (параметров) модели.

Индекс "М" указывает на принадлежность к модели, а не реальному процессу. В классической теории идентификации выходное воздействие допускает количественное измерение. Задача идентификации заключается в определении таких РM и АM, которые минимизируют некоторую функцию невязки между выходными воздействиями V(xi) и VM(xi)

полученными при одном и том же входном воздействии K(xi).

В случае применения теории компараторной идентификации для определения параметров моделей оценивания, как показано выше, экспериментальная информация позволяет выделить только классы эквивалентности и отношения предпочтения на множествах оценок (выходных воздействий V(Xi)) анализируемых ситуаций (входных воздействий К(хi)). В таких условиях задача идентификации заключается в том, чтобы найти такие Рм и Ам, которые не противоречат вытекающим из отношений эквивалентности и предпочтения зависимостям вида (1.11) и (1.12), (1.13). Эта задача по постановке полностью совпадает с задачей идентификации моделей описывающих отношения предпочтения в численном виде.

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

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

1.4 Описание генетического алгоритма

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

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

Реализацию базового генетического алгоритма можно представить как итерационный процесс, включающий несколько этапов:

1) генерация начальной популяции;

2) воспроизводство "потомков":

а) выбор родительской пары;

б) выбор и реализация одного из операторов кроссовера;

в) выбор и реализация одного из операторов мутации;

3) создание репродукционной группы;

4) процедура отбора и формирование на его основе нового поколения;

5) если не выполнено условие останова, то перейти к п. 2).

Операторы кроссовера и мутации

Одной из особенностей рассматриваемого ГА является отход от традиционной схемы "размножения", используемой в большинстве реализованных ГА [5] и повторяющих классическую схему. Классическая схема предполагает ограничение численности потомков путем использования так называемой вероятности кроссовера. Такая модель придает величине, соответствующей численности потомков недетерминированный характер. Предполагается вместо вероятности кроссовера использовать фиксированное число брачных пар на каждом поколении, при этом каждая брачная пара порождает двух потомков. Такой подход хорош тем, что делает процесс поиска более управляемым и предсказуемым в смысле вычислительных затрат [4].

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

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

Старая популяция частично или полностью уничтожается и далее рассматривается следующее поколение особей. Популяция следующего поколения в большинстве реализаций ГА содержит столько же особей, сколько начальная, но, вследствие отбора, приспособленность в ней в среднем выше.

Описанные выше процессы отбора, скрещивания и мутации повторяются уже для новой популяции и т.д.

В каждом следующем поколении наблюдается появление совершенно новых решений задачи. Среди них имеются как «плохие», так и «хорошие», но благодаря отбору количество «хороших» решений будет возрастать.

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

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

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

Другие два способа формирования родительской пары - это инбридинг и аутбридинг. Оба эти метода построены на формировании пары на основе близкого и дальнего "родства" соответственно. Под "родством" здесь понимается расстояние между членами популяции как в смысле геометрического расстояния особей в пространстве параметров (для фенотипов), так и в смысле хэмминингого расстояния между хромосомными наборами особей (для генотипов). В связи с этим будем различать генотипный и фенотипный (или географический) инбридинг и аутбридинг. Под инбридингом понимается такой метод, когда первый член пары выбирается случайно, а вторым с большей вероятностью будет максимально близкая к нему особь. Аутбридинг же, наоборот, формирует брачные пары из максимально далеких особей. Использование генетических инбридинга и аутбридинга является более эффективным по сравнению с географическим для всех тестовых функций при различных параметрах алгоритма [4]. Применение обоих рассмотренных методов целесообразно для многоэкстремальных задач. Однако два этих способа по-разному влияют на поведение ГА. Так инбридинг можно охарактеризовать свойством концентрации поиска в локальных узлах, что фактически приводит к разбиению популяции на отдельные локальные группы вокруг подозрительных на экстремум участков ландшафта, а аутбридинг как раз направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя алгоритм просматривать новые, неисследованные области.

Обсуждение вопроса о влиянии метода создания родительских пар на поведение ГА невозможно вести в отрыве от реализуемого механизма отбора при формировании нового поколения. Следует отметить, что метод пропорционального отбора, как и другие методы, основанные на включение особи в новую популяцию по вероятностному принципу, дают плохие результаты [2, 4]. Наиболее перспективными являются два метода: элитный и отбор с вытеснением.

Идея элитного отбора основана на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей, их потомков и мутантов. В литературе, посвященной ГА, например в [5], элитному отбору отводят место как достаточно слабому с точки зрения эффективности поиска. В основном это объясняют потенциальной опасностью преждевременной сходимости, отдавая предпочтение пропорциональному отбору. Быстрая сходимость, обеспечиваемая элитным отбором, может быть, когда это необходимо, с успехом компенсирована подходящим методом выбора родительских пар, например аутбридингом. Поэтому комбинация "аутбридинг-элитный отбор" является одной из наиболее эффективных для многих задач [5].

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

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

1) задача быстрой локализации одного оптимального значения;

2) задача определения нескольких (или всех) глобальных экстремумов;

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

Задача, рассматриваемая в работе, относится к первому классу.

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

2. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАТЬ

2.1 Описание задачи

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

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

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

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

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

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

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

Суть задачи заключается в следующем. Задано множество объектов X={xі}, подлежащих классификации. Каждый объект хіХ, характеризуется кортежем показателей (частных критериев)

,

Существует множество критериев оценки знаний учащихся, одними из наиболее полных являются критерии, предложенные Симоновым В.П. Максимовой В.Н.:

- различение (узнавание);

- запоминание;

- понимание;

- воспроизведение;

- творческий поиск;

- применение системы понятий;

- время, затраченное на решение задачи.

Структура кортежа одинакова для всех объектов хіХ. Кроме перечисленного, полагается известным количество классов B={bl}, по которым должны быть распределены объекты классификации хіХ. При этом на классах установлено отношение порядка и доминирования.

Число классов, отношение порядка и направление доминирования определяется эвристически на основе системного анализа особенностей предметной области, целей классификации и.т.п.

2.2 Постановка задачи

Пусть задано некоторое множество объектов X={x1, x2,…,xn}, подлежащих классификации. Определено количество возможных классов B={bl}, .

Каждый объект хіХ, характеризуется кортежем показателей , . В результате применения некоторой эвристической процедуры классификации множества Х получено разбиение на классы

, ,…,

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

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

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

можно записать

,

Отношение порядка для элементов внутри любого класса неизвестно, но по постановке задачи известны граничные объекты каждого класса. На основании этого можно записать:

где , - соответственно нижний и верхний граничные элементы классов , .

Для удобства представим (2.1) в виде системы неравенств:

Определим структуру скалярной многокритериальной оценки

В общем случае ее можно представить в виде некоторого фрагмента полинома Колмогорова-Габора вида

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

,

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

- это нормализованные, т.е. приведенные к изоморфному виду по формуле

частные критерии или их нелинейные комбинации.

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

Задача параметрической идентификации по модели (2.2) является некорректной по Адамару, так как не имеет единственного решения. Для ее регуляризации используется схема, основанная на определении чебышевской или средней точки. В силу линейности по параметрам ограничений (2.2) задача определения параметров является стандартной задачей линейного программирования.

2.3 Разработка математической модели метода компараторной идентификации модели многофакторного оценивания

Пусть количество объектов, подлежащих классификации X={x1, x2,…,xn} равно 20 (n=20), количество возможных классов B={bl}, ,L=5. А кортеж показателей , составляют следующие элементы:

- различение (узнавание);

- запоминание;

- понимание;

- воспроизведение;

- творческий поиск;

- применение системы понятий;

- время, затраченное на решение задачи.

В результате применения некоторой эвристической процедуры классификации множества Х получено разбиение на классы:

1) ;

2);

3);

4);

5);

На классах установлено следующее отношение порядка:

Согласно теории полезности запишем:

По постановке задачи порядок внутри классов не установлен, но известны граничные объекты каждого класса. На основании этого можно записать:

Сформируем систему неравенств



В результате анализа исходных данных в качестве структуры модели был выбран фрагмент полинома Колмогорова-Габора. Структура модели имеет следующей вид:

Необходимо решить задачу параметрической идентификации коэффициентов . Учитывая следующие ограничения:

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

2.3 Разработка программного средства

Системным программным обеспечением (ПО) является операционная система, под управлением которой разработано программное средство.

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

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

В качестве системного программного обеспечения используется Windows 7.

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

Базовое программное обеспечение - программное обеспечение, используемое в ходе разработки, корректировки или развития разрабатываемого программного средства: редакторы, компиляторы, отладчики, вспомогательные системные программы, графические пакеты и др.

Для функционирования разработанного программного средства необходимо располагать JDK (Java Development Kit) версии 6.0 или более поздней версии и интегрированной средой разработки Eclipse Gelios. Для эффективного функционирования программного обеспечения необходимо удовлетворить минимальные системные требования: Microsoft Windows® Windows XP (SP1, SP2, SP3) или более поздние версии Windows.

Разработанное прикладное программное обеспечение реализует алгоритм, представленный в приложении А (ГЮИК 503100.005). Данное ПС разработано на объектно-ориентированном языке Java.

2.4 Обоснование выбора языка программирования и среды разработки

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

Java является сравнительно простым языком программирования. Быстрому созданию надежного программного кода способствует автоматическое управление памятью, отсутствие многократного наследования и указателей.

Байтовый код Java в большой степени независим от операционной системы или процессора. Благодаря этому приложения на языке Java легко портируются на другие платформы. Девиз компании Sun Microsystems «Написанное однажды работает всегда» раскрывает идею кросс-платыорменности. Один и тот же код можно запускать под управлением операционных систем Windows, Linux, FreeBSD, Solaris, Apple Mac и др. Это становится очень важным, когда программы загружаются посредством глобальной сети Интернет и используются на различных платформах.

С помощью технологий JNI и CORBA может быть реализована связь с объектами, созданными на других языках программирования.

В сравнении с другими программными решениями (например, с Remote Scripting) веб-базированное приложение на языке Java, использующее для обмена данными сокеты, позволяет достичь меньшего времени реакции при оповещении клиента.

Другим, не менее важным преимуществом Java, является большая схожесть с языком программирования C++. Поэтому тем программистам, которые знакомы с синтаксисом С и С++ будет просто освоить Java.

Разработчиками языка Java из компании Sun Microsystems был проведен фундаментальный анализ программ на языке С++. Анализировались "узкие места" исходного кода, которые приводят к появлению трудновыявимых ошибок. Было принято решение проектировать язык Java с учетом возможности создавать программы, в которых были бы скрыты наиболее распространенные ошибки.

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

Интерфейс дает программисту практически все, что тот может получить от множественного наследования, избегая при этом сложностей, которые возникают при управлении иерархиями классов [15].

2.5 Руководство пользователя

Для запуска программы необходимо скопировать файлы папки Classification в локальную директорию. Открыть папку и запустить файл Classification.exe. После этого появится главное окно программы, представленное на рисунке 2.1.

Рисунок 2.1 - Кадр главного окна программы

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

Рисунок 2.2 - Кадр программы, уведомляющий о том, что сгенерирована новая популяция

Для того, чтобы решить задачу параметрической идентификации (произвести расчет весовых коэффициентов модели) необходимо нажать кнопку «Рассчитать». Кадр окна представлен на рисунке 2.3.



Рисунок 2.3 - Кадр программы с рассчитанными коэффициентами

2.6 Результаты исследования модели с помощью разработанного ПС

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

Полученные результаты представлены в таблице 2.1.

Таблица 2.1 - Значения параметров модели

№ параметра	Значение
а1	0.145
а2	0.057
а3	0.177
а4	0.09992
а5	0.138
а6	0.123
а7	0.194
а8	0.066

ВЫВОДЫ

В данной магистерской аттестационной работе решалась задача одна из подзадач многокритериальной оптимизации - задача компараторной идентификации.

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

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

Для исследования полученной модели разработано программное средство, реализующее построенный алгоритм расчета значения параметров модели с учетом ограничений.

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

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

алгоритм компараторный идентификация многофакторный оценивание

ПЕРЕЧЕНЬ ССЫЛОК

1. Петров Э.Г. Методы и средства принятия решений в социально-экономических системах / Э.Г. Петров, М.В. Новожилова, И.В. Гребенник, Н.А. Соколова. - Херсон: ОЛДИ-плюс, 2003. - 380с.

2. Петров К.Э. Крючковский В.В. Компараторная структурно-параметрическая идентификация моделей скалярного многофакторного оценивания: Монография. - Херсон: Олди-плюс, 2009. - 294с.

3. Тихонов А.Н. Методы решения некорректных задач / А.Н. Тихонов, В.Я. Арсенин. - М.: Наука, 1986. - 288с.

4. Исаев С. Генетические алгоритмы в задачах оптимизации http://www.masters.donntu.edu.ua/2005/kita/shestopalov/library/gaoptim.htm

5. Mitchell M. An introduction to Genetic Algorithm. MIT Press, 1996.

6. Компараторная идентификация цветового зрения человека М.Ф Бондаренко, С.Ю. Шабанов-Кушнаренко, Ю.П. Шабанов-Кушнаренко. Бионика интеллекта. 2008. №2(69). С. 3-12.

7. Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995.

8. Батищев Д.И., Скидкина Л.Н., Трапезникова Н.В. Глобальная оптимизация с помощью эволюционно-генетических алгоритмов / Мужвуз. сборник, ВГТУ, Воронеж, 1994.

9. Ларичев О. И. Теория и методы принятия решений, а также хроника событий в волшебной стране / О. И. Ларичев. - М.: Логос, 2000. - 294 с.

10. Ильин В. Н. Поведение потребителей / В. Н. Ильин. - С.-Пб.: Питер, 2000. - 224 с.

11. Крючковский В. В. Анализ методов идентификации модели многокритериального оценивания / В. В. Крючковский, В. П. Пономаренко, Д.И. Филипская // Вестник Херсонского национального технического университета. - 2008. - №1 (30). - с. 85-90.

12. Овезгельдыев А. О. Синтез и идентификация моделей многофакторного оценивания и оптимизации / А.О. Овезгельдыев, Э. Г. Петров, К. Э. Петров. - К.: Наук. Думка, 2002. - 164 с.

13. Теоретический анализ проблемы количественной оценки качества обучения [Электронный ресурс] / Режим доступа : www/ URL: http://www.gmcit.murmansk.ru/text/information_science/workshop/seminars/science_method/theoretical_analysis.htm - 02.05.2011 г. - Загл. С экрана.

14. Приемущества языка программирования Java [Электронный ресурс] - Режим доступа : www/ URL: http://www.codeguru.com.ua/article/a-204.html - 10.05.2011 г. - Загл. С экрана

16. Методичні вказівки до магістерської підготовки, з розробки й оформлення магістерської атестаційної роботи для студентів спеціальностей: 8.080402 - Інформаційні технології проектування, 8.091401 - Системи управління та автоматики. Освітньо-кваліфікаційний рівень - магістр [Текст] Упоряд.: Е.Г. Петров, В.В. Безкоровайний, Л.М. Ребезюк. - Харків: ХНУРЕ, 2009. - 72 с.

ПРИЛОЖЕНИЕ

Графические материалы к дипломному проекту

Размещено на http://www.allbest.ru/

Диаграмма взаимосвязи процессов управления командой проекта

Текст програми

title = About: ${Application.title} ${Application.version}

closeAboutBox.Action.text = &Close

appDescLabel.text=<html>${Application.description}

versionLabel.text=Product Version\:

vendorLabel.text=Vendor\:

homepageLabel.text=Homepage\:

#NOI18N

imageLabel.icon=about.png

# Application global resources

Application.name = Classification

Application.title = Basic Application Example

Application.version = 1.0

Application.vendor = Sun Microsystems Inc.

Application.homepage = http\://appframework.dev.java.net/

Application.description = A simple Java desktop application based on Swing Application Framework.

Application.vendorId = Sun

Application.id = ${Application.name}

Application.lookAndFeel = system

public class GA {

private Random r = new Random();

int counter;

private int[][] population = new int[50][64];

private int[][] popul10 = new int[50][8];

private double[][] populNorm = new double[50][8];

int[] c = new int[50];

private double[] a = new double[8];

/**

* The method randomly initializes first generation

*/

public void firstGeneration() {

for (int i = 0; i < 50; i++) {

for (int j = 0; j < 64; j++) {

population[i][j] = r.nextInt(2);

}

}

}

/**

* /** The method randomly change random chromosome. The maximum percentage

* of mutation equals to 3 percents.

*

* @param popul

* the initial population

*

* @return mutated population

*/

public int[][] mutation(int[][] popul) {

int z;

int x;

for (int i = 0; i < r.nextInt(97); i++) {

z = r.nextInt(49);

x = r.nextInt(63);

if (popul[z][x] == 0) {

popul[z][x] = 1;

} else {

popul[z][x] = 0;

}

}

return popul;

}

private double[][] norm(int[][] array) {

int sum;

for (int i = 0; i < 50; i++) {

sum = 0;

for (int j = 0; j < 8; j++) {

sum += array[i][j];

if (j == 7) {

for (int t = 0; t < 8; t++) {

populNorm[i][t] = ((double)array[i][t] / (double)sum);

}

}

}

}

return populNorm;

}

public void from2to10() {

int r = 256;

int m = 0;

int q = 0;

for (int j = 0; j < 50; j++) {

m = 0;

for (int i = 0; i < 64; i++) {

r = r / 2;

q += population[j][i] * r;

if (i != 0 && i % 8 == 0) {

popul10[j][m] = q;

r = 256;

m++;

q = 0;

}

if (i == 63) {

popul10[j][m] = q;

r = 256;

m = 0;

q++;

}

}

}

norm(popul10);

System.out.println(Arrays.deepToString(populNorm));

}

public void qualityAnalysis() {

int count = 0;

for (int i = 0; i < 50; i++) {

counter = 0;

for (int j = 0; j < 8; j++) {

a[j] = populNorm[i][j];

}

double b1 = 0.02*a[0]+0.37*a[1]-0.01*a[2]-0.18*a[3]+0.11*a[4]-0.18*a[5]-0.8*a[6]+0.09*a[7];

double b2 = -0.06*a[0]+0.59*a[1]-0.01*a[2]-0.26*a[3]+0.02*a[4]-0.26*a[5]-0.15*a[6]+0.15*a[7];

double b3 =-0.07*a[0]-0.23*a[1]+0.8*a[3]+0.1*a[4]+0.08*a[5]-0.65*a[6]-0.06*a[7];

double b4 = -0.3*a[0]-0.03*a[1]+0.26*a[2]-0.2*a[3]-0.4*a[4]-0.28*a[5]+0.45*a[6]+0.06*a[7];

double b5 = 0.23*a[0]-0.34*a[1]-0.53*a[2]-0.2*a[3]+0.13*a[4]+0.05*a[5]-0.1*a[6]-0.31*a[7];

double b6 = 0.12*a[0]-0.23*a[1]-0.38*a[2]-0.18*a[3]+0.16*a[4]+0.07*a[5]+0.3*a[6]-0.18*a[7];

double b7 = 0.12*a[0]-0.23*a[1]-0.38*a[2]-0.18*a[3]+0.16*a[4]+0.07*a[5]+0.3*a[6]-0.18*a[7];

double b8 = 0.23*a[0]-0.53*a[2]-0.06*a[3]+0.3*a[4]+0.2*a[5]-0.3*a[6]-0.13*a[7];

double b9 = 0.1*a[0]-0.25*a[1]-0.4*a[2]-0.2*a[3]+0.15*a[4]+0.06*a[5]-0.15*a[6]-0.2*a[7];

double b10 = 0.12*a[0]-0.12*a[1]-0.15*a[2]-0.02*a[3]-0.02*a[4]-0.02*a[5]-0.4*a[6]-0.13*a[7];

double b11 = 0.01*a[0]-0.34*a[1]-0.14*a[3]-0.17*a[4]-0.15*a[5]+0.2*a[6]-0.18*a[7];

double b12 = 0.13*a[0]-0.09*a[1]-0.13*a[2]+0.05*a[6]-0.11*a[7];

double b13 = -0.15*a[0]+0.07*a[1]-0.02*a[3]-0.02*a[4]-0.02*a[5]+0.04*a[7];

double b14 = -0.14*a[0]-0.2*a[1]-0.47*a[2]-0.16*a[3]-0.2*a[4]-0.16*a[5]+0.3*a[6]-0.45*a[7];

double b15 = -0.02*a[0]-0.03*a[1]-0.02*a[3]-0.02*a[4]-0.07*a[5]-0.2*a[6]-0.01*a[7];

double b16 = -0.12*a[0]-0.18*a[1]-0.47*a[2]-0.14*a[3]-0.17*a[4]-0.09*a[5]+0.5*a[6]-0.43*a[7];

double b17 = -0.02*a[0]-0.03*a[1]+0.4*a[2]-0.02*a[3]-0.02*a[4]-0.02*a[5]-0.4*a[6]+0.27*a[7];

double b18 = 0.05*a[0]-0.13*a[1]-0.1*a[2]-0.1*a[3]-0.12*a[4]-0.1*a[5]-0.25*a[6]-0.17*a[7];

double b19 = -0.02*a[0]-0.03*a[1]-0.02*a[2]+0.06*a[3]-0.02*a[4]-0.02*a[5]-0.03*a[7];

double b20 = -0.05*a[0]-0.08*a[1]-0.19*a[2]-0.06*a[3]-0.07*a[4]+0.06*a[5]-0.05*a[6]-0.2*a[7];

double b21 = 0.07*a[0]-0.1*a[1]-0.8*a[2]-0.16*a[3]-0.1*a[4]-0.09*a[5]-0.25*a[6]-0.14*a[7];

double b22 = 0.11*a[0]-0.05*a[1]+0.09*a[2]-0.04*a[3]-0.05*a[4]-0.17*a[5]-0.2*a[6]+0.04*a[7];

double b23 = 0.02*a[0]-0.04*a[1]-0.09*a[2]-0.1*a[3]+0.05*a[4]+0.17*a[5]-0.05*a[6]-0.11*a[7];

double b24 = -0.7*a[0]+0.25*a[1]-0.06*a[2]-0.2*a[3]+0.03*a[4]-0.46*a[5]-0.15*a[6]+0.16*a[7];

double b25 = -0.22*a[0]-0.04*a[1]+0.03*a[2]+0.04*a[3]-0.38*a[4]-0.22*a[5]+0.1*a[6];

double b26 = -0.26*a[0]-0.09*a[1]-0.01*a[2]-0.03*a[3]-0.13*a[4]-0.26*a[5]-0.08*a[7];

double b27 = -0.47*a[0]-0.09*a[1]-0.02*a[2]-0.03*a[3]-0.06*a[4]-0.27*a[5]+0.15*a[6]-0.09*a[7];

double b28 = -0.48*a[0]+0.28*a[1]-0.09*a[2]-0.24*a[3]+0.4*a[4]-0.24*a[5]-0.25*a[6]+0.16*a[7];

double b29 = -0.45*a[0]+0.33*a[1]-0.05*a[2]-0.17*a[3]-0.16*a[4]-0.2*a[5]-0.15*a[6]+0.23*a[7];

double b30 = -0.23*a[0]+0.33*a[1]-0.04*a[2]-0.17*a[3]+0.09*a[4]-0.19*a[5]-0.3*a[6]+0.24*a[7];

if (b1 <= 0) {counter++;}

if (b2 <= 0) {counter++;}

if (b3 <= 0) {counter++;}

if (b4 <= 0) {counter++;}

if (b5 <= 0) {counter++;}

if (b6 <= 0) {counter++;}

if (b7 <= 0) {counter++;}

if (b8 <= 0) {counter++;}

if (b9 <= 0) {counter++;}

if (b10 <= 0) {counter++;}

if (b11 <= 0) {counter++;}

if (b12 <= 0) {counter++;}

if (b13 <= 0) {counter++;}

if (b14 <= 0) {counter++;}

if (b15 <= 0) {counter++;}

if (b16 <= 0) {counter++;}

if (b17 <= 0) {counter++;}

if (b18 <= 0) {counter++;}

if (b19 <= 0) {counter++;}

if (b20 <= 0) {counter++;}

if (b21 <= 0) {counter++;}

if (b22 <= 0) {counter++;}

if (b23 <= 0) {counter++;}

if (b24 <= 0) {counter++;}

if (b25 <= 0) {counter++;}

if (b26 <= 0) {counter++;}

if (b27 <= 0) {counter++;}

if (b28 <= 0) {counter++;}

if (b29 <= 0) {counter++;}

if (b30 <= 0) {counter++;}

if (counter >= 30) {

System.out.println("Оптимальное решение найдено");

System.out.println(Arrays.toString(a));

break;

}

c[count] = counter;

count++;

}

krossengover();

System.out.println(Arrays.toString(c));

}

private void krossengover() {

counter = 0;

int[] s = new int[64];

for(int i =0; i<50;i++){

if(c[i]>=27){

s[counter]=i;

counter++;

}

}

int arr1;

int arr2;

for(int i=0;i<50;i++){

int z = r.nextInt(63);

for(int j=0;j<z;j++){

if (counter!=0){

arr1 = population[s[counter]][j];

arr2 = population[s[counter-1]][j];

population[s[counter-1]][j]=arr1;

population[s[counter]][j]=arr2;

counter --; } }

Размещено на Allbest.ru