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

 

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СППР- Системы поддержки принятия решений

АСУ- Автоматизированные системы управления

ЛПР- Лицо, принимающее решение

ГА- Генетические алгоритмы

ПО- Программное обеспечение

ПС- Программное средство

ЗВМ- Электронная вычислительная машина

ВВЕДЕНИЕ

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

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

В условиях широкого развития вычислительной техники и внедрения автоматизированных систем управления (АСУ) актуальным вопросом является формализация процедуры принятия решения, которая во многом определяет степень «интеллектуальности» СППР и АСУ.

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

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

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

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

ОБЗОР ЛИТЕРАТУРЫ

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

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

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

В области исследования методов решения задач многокритериальной оптимизации в настоящее время сложилось два подхода:

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

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

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

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Теоретические основы и проблемы принятия решений

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

- формирование цели, ее анализ и формализация;

определение множества возможных путей ее достижения (множества решений);

формирование оценки (меры*) позволяющей сравнивать (ранжировать) возможные решения между собой по качеству;

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

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

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

Таким образом, абстрактная система представляется в виде:

С = (N, R, P)

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

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

Проблема синтеза системы, рассмотренная выше, включает в себя следующие задачи:

• определение цели;
• анализ цели и выделение свойств, которыми должна обладать система, для ее достижения;

-определение множества возможных структур, обладающих требуемыми свойствами и выделение из него допустимого множества решений;

-выбор наилучшего варианта структуры.

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

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

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

P = {p1, p2,…, pn}

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

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

Определение множества возможных структур. Как вытекает из общего определения системы, свойства могут быть реализованы только на упорядоченном множестве элементов и отношений, т. е. структур [1]. Задание конкретного подмножества свойств P, которыми должна обладать система, путем их отображения на универсуме элементов N и отношений R, определяет подмножества N и R, на которых в принципе реализуема система с заданными свойствами. В свою очередь упорядоченное множество

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

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

Следует иметь в виду, что отображение свойств Р на множества N и R, а также выделение подмножества структур Хв, на которых они достижимы, может иметь различную степень определенности, что обуславливает сложность задачи синтеза системы.

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

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

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

Цель системы характеризуется частными свойствами p1, p2,…, pn; а уровень ее достижения - их количественными значениями. Таким образом, сравнение решений можно осуществлять по достигнутому уровню частных свойств. Поэтому частные свойства системы, приведенные к виду, допускающему измерение в количественных или качественных шкалах, будем называть частными критериями. Эта группа критериев оценивает полезные функциональные свойства, ради которых создавалась система:

Кф(х) = {к1ф(х),к2ф(х),...,ктф(х))

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

Kз(x) = {k1зx).k2з(x),...,krзx)}

Отметим, что в частном случае множества Кф(х) и К3(х) могут содержать по одному элементу, но в общем случае эти множества имеют различную мощность, их элементы разнородны по смыслу, измерены в различных шкалах и интервалах. Таким образом, каждое решение хєХ характеризуется набором разнородных частных критериев

К(х) = {Кф(х) Кз(х)}= {kl(x),k2(x)....,km+rx)}

Выбор системы частных критериев - это неформализованная, эвристическая задача. Ее решение затрудняется необходимостью удовлетворения следующих отчасти противоречивых условий [1]:

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

6)измеримость - каждый критерий должен допускать возможность оценки (количественной или качественной) интенсивности характеризуемого качества. Это означает, что для любого решения хХ задано отображение f:X?K и соответственно функциональная зависимость [1].

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

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

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

В общем случае множество допустимых решений X является композицией двух подмножеств:

• согласованных решений (области согласия) Xs;
• компромиссных решений (области компромиссов) Xс.
• Областью согласия Xs называется подмножество множества допустимых решений X на котором один или несколько частных критериев можно улучшить без ухудшения качества других частных критериев.
• Областью компромиссов Xс называется подмножество X, на котором ни один частный критерий ki(x) невозможно улучшить без ухудшения значения хотя бы одного, другого частного критерия, либо ни один частный критерий нельзя улучшить вообще. Возможность существования такого подмножества доказал итальянский экономист Парето, поэтому его часто называют областью Парето или множеством Парето-оптимальных решений.
• Для подмножеств Xs и Xе выполняются условия:

X = Xs Xс, Xs Xc =

которые означают, что объединение подмножеств образует допустимое множество и любое решение хХ принадлежит только одному из подмножеств.

По определению область согласия Xs в принципе не может содержать экстремальных решений, так как каждое xXs можно улучшить хотя бы по одному критерию. Поэтому множество допустимых экстремальных решений задачи (1.2) совпадает с областью компромиссов Xcи если она не пустая, т. е. Xc ?, то все хХс являются решением задачи. Таким образом, задача многокритериальной оптимизации (1.2) имеет единственное решение только в том случае, когда X = XS {x0}. Иначе решение не будет единственным, а это означает, что задача является некорректно поставленной по Адамару.

Корректными по Адамару называются задачи, для которых решение: существует, единственно и устойчиво, т.е. в заданной метрике малым изменениям входных переменных соответствуют малые изменения выходных переменных.

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

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

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

- неконструктивный, когда в качестве регуляризующего элемента выступает непосредственно ЛПР, которое на основе эвристических соображений (опыта) выбирает единственное решение из Xс;

• - конструктивный, основанный на обосновании и реализации некоторого формального правила выбора единственного "компромиссного" решения.

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

• В первом случае определяется строгое, например,

х1 х2 ... хп,

или нестрогое, например

х1 х1 ~ х1 … х1

отношения порядка, где и ~ - знаки отношений предпочтительности и эквивалентности соответственно. Во втором случае непосредственно находится экстремальное решение х° х, х°X.

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

• 1.2 Синтез модели многофакторного оценивания

Теоретической основой формирования многокритериальных скалярных оценок является теория полезности, которая предполагает существование некоторой количественной оценки предпочтительности решений. Это означает, что если решения х1, , и х1х2 (х1 предпочтительнее х2), то Р(х1) > Р(х2), где Р(х1), Р(х2) - функции полезности. В общем случае справедливо и обратное утверждение. Таким образом, полезность является количественной мерой "качества" решений. В связи с этим возникает задача обоснования правила (метрики), по которому формируется функция полезности каждого хj в пространстве частных критериев ki(хj)

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

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

Проблема синтеза любой математической модели заключается в определении характера связи между некоторым входным воздействием X и реакцией системы (выходом) Y

Y = F(X),

где X и Y - в общем случае многомерные величины.

• Для этого необходимо решить две взаимосвязанных задачи: структурной и параметрической идентификации.
• Общий подход к решению проблемы заключается в получении путем наблюдения за моделируемым объектом информации о значениях входного воздействия X и соответствующей его реакции У.
• Под наблюдением понимается проведение серии активных или пассивных экспериментов с моделируемым объектом. В первом случае на вход объекта подаются специально выбранные воздействия, а во втором наблюдается естественное функционирование системы без вмешательства в ее работу. В результате получаем некоторую последовательность значений входных воздействий X и соответствующие им его реакции Y. На основе этой информации решается задача структурно-параметрической идентификации оператора F. Схема решения приведена на рисунке 1.1.

• Рисунок 1.1 - Схема идентификации математической модели
• Здесь ?1, ?2 - погрешности измерения, соответственно, входных и выходных воздействий.
• В процессе идентификации математической модели необходимо решить задачу

,

• где F.A - структура и параметры модели, соответственно, подлежащие идентификации.
• В общем случае идентификация предусматривает решение следующих задач: выбор класса математической модели, языка ее описания, класса и типов входных сигналов, критериев соответствия ("близости") объекта и модели, метода идентификации и разработку соответствующих алгоритмов.
• Трудоемкость и качество решения перечисленных выше задач определяется полнотой и точностью измерения X и У, особенностями системы и объемом априорной информации о структурно-параметрических характеристиках оператора F.
• При этом различают две полярные ситуации:

-априорная информация о структуре F полностью отсутствует (задача о "черном ящике");

• -вид (структура) оператора F априорно известен и решается только задача его параметрической идентификации.

Между этими крайностями лежит спектр задач о "сером ящике", прозрачность которого определяется степенью априорной информированности исследователя о характере взаимосвязи X и У, т. е. виде F.

• В ходе структурной идентификации оператора F выдвигается гипотеза о его виде и затем эта гипотеза проверяется на основе информации о X и Y. При этом возможны два подхода. Если исследователь располагает достаточной априорной информацией о моделируемом объекте, то целесообразно стремиться как можно более точно и полно математически описать весь процесс его функционирования. Это направление известно в теории моделирования как принцип прямой аналогии. В противном случае используется принцип непрямой аналогии, основанный на стремлении описать реальный процесс некоторым полиномом (рядом), обладающим хорошими аппроксимирующими свойствами с учетом конкретного характера последовательностей X и Y. В этом случае модель обеспечивает совпадения только конечных результатов реакции системы без описания промежуточных процессов. При этом в ходе более глубокого исследования объекта происходит постепенный эволюционный переход от второго подхода к первому.
• В настоящее время в области поддержки принятия решений распространена характерная ситуация, которая состоит в том, что полная формализация нахождения наилучшего (в определенном смысле) решения возможна только для хорошо изученных, относительно простых задач. На практике же чаще встречаются слабоструктурированные или неструктурированные задачи, для которых полностью формализованные процедуры отсутствуют и их необходимо идентифицировать. В этих случаях, наряду с традиционными трудностями решения задач идентификации моделей сложных систем, связанных с качеством исходной экспериментальной информации о входных и выходных сигналах, которое обусловлено ошибками измерений, ограниченностью ее объема и т. п., количественное измерение выхода Y часто вообще невозможно. Можно только зарегистрировать принятое индивидуумом решение, т. е. конечный результат выбора решения из множества альтернатив. Это делает принципиально невозможным использование хорошо зарекомендовавших себя методов идентификации моделей сложных систем. В связи с чем возникла проблема разработки новых, проблемно-ориентированных методов идентификации.
• В настоящее время сложилось несколько подходов к преодолению указанных затруднений.
• Учитывая, что опытные, компетентные специалисты в большинстве случаев принимают решения, которые оказываются достаточно эффективными, в настоящее время одной из основных тенденций практики принятия решений является реализация систем, сочетающих способности человека решать неформализованные задачи с использованием разработанных формальных методов и компьютерного моделирования. К таким системам можно отнести:
• диалоговые системы поддержки принятия решений;
• адаптивные человеко-машинные автоматизированные системы управления;
• экспертные системы.

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

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

. Отсутствие априорной информации, позволяющей выдвинуть аргументированную гипотезу о структуре модели, т. е. о виде оператора F.

В настоящее время отсутствуют инструментальные средства непосредственного количественного измерения значения полезности для ЛПР конкретной альтернативы хХ. Можно зарегистрировать только конечный результат выбора.

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

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

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

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

Для этого можно воспользоваться идеями компараторной идентификации.

1.3 Описание метода компараторной идентификации

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

Выход из этой тупиковой ситуации впервые указал И. Ньютон. Он воспользовался тем обстоятельством, что сам испытуемый способен установить, равны или нет цвета любых предъявленных ему световых излучений. Делает он это субъективным способом, анализируя цвета собственным сознанием. В результате такого анализа человек может выработать физический сигнал, принимающий одно из двух значений: 1, если цвета совпадают, и 0, если не совпадают. Эта двоичная реакция испытуемого вполне объективна, ее можно зарегистрировать физическими приборами [6].

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

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

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

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

К достоинствам метода компараторной идентификации можно отнести следующее.

1. Повышается точность исходной, получаемой от эксперта информации. Это связано с тем, что как показали многочисленные исследования [9, 10], человек более точно выполняет операцию сравнения, чем измерения. Объяснение этого факта заключается в том, что при сравнении, измерительная шкала содержит только два значения и ошибка возможна только в пороговой зоне различимости двух ощущений.
2. Появляется возможность отказаться от структуризации задачи и выполнения последовательности промежуточных оценок, дающих накопление погрешностей, заменив их анализом (сравнением) ситуации, как целого [11].
3. В свою очередь, это открывает возможность получения исходной информации не только с помощью активных экспериментов (путем проведения экспертиз), но в ходе пассивных экспериментов, путем регистрации конечных результатов естественной деятельности ЛПР, т. е. наблюдения поведения и принятых решений.

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

F[A,X(s)] = F[A,X(t)], s,t = 1,k, s?t

де X(s) и Х(t) - некоторые кортежи входного воздействия X.

Анализ такой системы позволяет определить вид оператора F (структуру) и параметры А модели.

Классическая теория компараторной идентификации заключается в формализации и использовании информации, содержащейся не только в ситуации эквивалентности ощущений, порождающей равенства вида (1.3), но и ситуаций неэквивалентности, порождающих неравенства вида

F[A,X(s) ]<(<)F[A,X(t)],s,t = 1,k, s?t.

Такая расширенная модель компараторной идентификации рассмотрена ниже.

Пусть имеется ограниченное множество альтернативных вариантов поведения (решений) X={хх,х2,:..,хп}. Каждая альтернатива xiX, описывается набором частных характеристик K(xi) = <k](xi),k2(xi),…, km(xi)>, которые допускают их объективное количественное измерение.

На основе анализа значений частных характеристик конкретной альтернативы xiX, ЛПР формирует внутреннюю оценку этой альтернативы viV, , которая отражает ее полезность (ценность) для ЛПР. Таким образом, существует отображение множества альтернативе во множество индивидуальных оценок V [12]:

Р : X ? V

где р - оператор модели оценивания.

Тогда V = P(X) - модель формирования многофакторных оценок альтернатив (vi = Р(хi), ).

Значения элементов множества V (субъективные оценки ЛПР) недоступны для количественного измерения, но поддаются качественному анализу.

Пусть для множества V выполняется два условия [12]:

все оценки vi =Р(хi), сравнимы между собой (обеспечивается корректным заданием множества альтернатив X);

на множестве V существует отношение предпорядка, т. е. для элементов viU, выполняются аксиомы рефлексивности и транзитивности.

Анализ множества V позволяет сформировать на нем фактор-множество V1 путем объединения в один класс всех равных оценок. Далее, фактор-множество V1 можно упорядочить, указав порядок предшествования элементов и крайние элементы в цепи.

• В соответствии с (1.4), процесс оценивания ЛПР пары альтернатив xq,xreX, q?r формально может быть описан в виде системы компараторов, первый из которых реализует предикат вида:

• с областью определения V2, что означает сравнимость любой пары элементов множества V, где vq=P(xq), vr = P(xr) - субъективные оценки ЛПР соответствующих альтернатив. Суперпозиция предикатов (1.5) образует предикат

с областью определения X2 и множеством значений {0, 1}. Предикаты D1 и Е1 обладают свойствами рефлексивности, транзитивности и симметричности и в силу этого являются соответственно предикатами равенства оценок и эквивалентности альтернатив. Реализация предиката Dx(vq,vr) позволяет преобразовать множество V в фактор-множество V', элементами которого являются классы одинаковых оценок, а предикат El(xq,xt.) - множество X в фактор-множество X', содержащее классы эквивалентных альтернатив. При этом в обоих случаях часть или все классы могут содержать по одному элементу.

Следующий этап анализа заключается в реализации на фактор-множествах V' и X' отношения линейного порядка. Для этого пара оценок vq,vrV, для которых значение D1=0 подается на компаратор, реализующий предикат либо вида

• либо вида

• Суперпозиции предикатов (1.6), (1.7) образуют соответственно предикаты

и

Предикаты D2(vq,vr) и E2(xq,xr) обладают свойствами транзитивности и антирефлексивности и в силу этого являются предикатами строгого порядка. Соответственно D2(vq,vr) устанавливает на V' отношение предшествования, а предикат E2(xq,xr) устанавливает на X' отношение строгого предпочтения.

Предикаты нестрогого порядка D3(vq,vr) и E3(xq,xr), обладающие свойствами рефлексивности, транзитивности и антисимметричности, устанавливают соответственно на V отношение предшествования, а на X' - отношение нестрогого предпочтения.

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

Полученная информация является исходной для решения задачи идентификации оператора Р. Для каждой пары эквивалентных альтернатив xq~xr, xq,xr е X, q ?r из (1.6) следует

P(xq) = P(xr)

• для ситуации, когда установлено отношение строгого предпочтения

Р(хq)>(<)Р(хr)

соответственно для отношения нестрогого предпочтения (xq >(<)хг) (1.10) выполняется

P(xq)>(<)P(xr)

• В основу формализации предикатов (1.5) - (1.10) положены принципы теории полезности и рационального выбора.
• Общее количество соотношений вида (1.11) - (1.13) зависит от мощности множества X и его структуры, т. е. количества классов эквивалентности и числа элементов в каждом из них.
• В частном случае множество X может:
• не содержать подмножеств эквивалентных альтернатив более чем с одним элементом, т. е. представлять собой линейно упорядоченное множество;
• содержать одно подмножество эквивалентных альтернатив, в которое входят все сравниваемые элементы;
• содержать несколько линейно упорядоченных подмножеств эквивалентных альтернатив, некоторые из которых или все содержат более чем один элемент.

Первому случаю соответствуют только соотношения в виде неравенств вида (1.12), (1.13); второму - только равенств вида (1.11); последнему - композиция равенств и неравенств вида (1.11) - (1.13).

Рассмотрим эти случаи более подробно.

1. Пусть в ходе активного компараторного эксперимента ЛПР ранжирует по предпочтительности набор альтернатив X = {хi}, . Для этого ЛПР предъявляют множество альтернатив с предложением установить на нем отношение порядка. Решение этой задачи связано с парным сравнением всех возможных альтернатив. Это означает, что ЛПР раз предъявляют пары альтернатив (xi, xi), xi, xj eX, , i ? j и оно выбирает из них наиболее предпочтительную альтернативу, т. е. реализует компаратор (1.7) и соответствующий предикат (1.9). При этом фактор-множество V1 состоит только из строго упорядоченных оценок и не содержит элементов с равными оценками, а фактор-множество X1 состоит только из альтернатив находящихся в отношении строгого порядка и не содержит эквивалентных альтернатив. Это случай наибольшей уверенности ЛПР в своих предпочтениях, так как ЛПР абсолютно уверено в своем выборе на каждом шаге оценивания. В результате, на множестве X установлено отношение строгого порядка, например:

Тогда, в соответствии с (1.11), получаем систему строгих неравенств

Р(х1)>Р(х2)>...>Р(хn)

Данную систему неравенств можно детализировать следующим образом:

Рассмотрим аналогичную ситуацию, когда на множестве X ЛПР устанавливает отношение нестрогого порядка. Она может возникнуть, если ЛПР не абсолютно уверено в своем выборе, т. е. этот случай более слабой уверенности ЛПР в своих предпочтениях, чем в случае с установлением отношения строгой предпочтительности. Таким образом, теперь реализуется компаратор (1.8) и, следовательно, работает предикат (1.10), т.е. фактор-множество V1 содержит нестрого упорядоченные оценки альтернатив, а фактор-множество X1 состоит из элементов, находящихся в отношении нестрогого предпочтения. В результате, на множестве альтернатив X = {xi}> устанавливается отношение нестрогого порядка, например:

x1 > xi >...> xn.

Тогда, в соответствии с (1.13), получаем систему нестрогих неравенств

Р(х1)>Р(х2)>...>Р(хп),

и аналогичную (1.14) детализированную систему неравенств, где вместо знаков «<» будут стоять знаки «<».

1.При проведении активного компараторного эксперимента ЛПР раз оценило пары альтернатив и сделало вывод, что все альтернативы для него равноценны, т. Е. фактически реализовался компаратор (1.5) и, соответствующий ему предикат (1.6). При этом фактор-множество V1 будет содержать только равные оценки, а X1 состоять только с эквивалентных альтернатив. В результате, на множестве X установлено отношение эквивалентности альтернатив:

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

Установив на множестве X отношение эквивалентности в соответствии с (1.11), получаем систему уравнений:

Р(хх) = Р(х2) = ... = Р(хп).

Более детально систему уравнений (1.15) можно записать в виде:

P(x2) = P(x1);

………

P(xn) = P(x1);

………

P(xn) = P(xn-1).

3. В ходе проведения активного эксперимента ЛПР, оценив множество альтернатив, сделало вывод, что в нем имеются равноценные альтернативы. Из этих альтернатив ЛПР сформировало некоторое количество подмножеств эквивалентных альтернатив и затем на этих подмножествах установило отношение предпочтения (строгого или нестрогого). Эксперимент предполагает, что вначале ЛПР сравнивает раз пары альтернатив и для каждой из них делает заключение об их равноценности, т.е. реализует компаратор (1.5) и формирует фактор-множество V1, содержащее подмножества равных оценок. С помощью предиката (1.6) формируется фактор-множество X1, содержащее подмножества эквивалентных альтернатив. После этого, ЛПР попарно сравнивает полученные подмножества эквивалентных альтернатив между собой и устанавливает между ними отношение предпочтения (строгого или нестрогого). Таким образом, уже сформированные подмножества эквивалентных альтернатив подаются вновь на компаратор (1.6) и для подмножеств, у которых D1 = 0, реализуется либо компаратор (1.7) и предикат (1.9), либо компаратор (1.8) и предикат (1.10). В результате, на множестве альтернатив будет установлено отношение частичного линейного порядка, например

{х1 ~ х2} (>){х3~ х4 ~ х5} (>)...(>){хп-1 ~хn}

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

Таким образом, установив на множестве альтернатив X отношение частичного линейного порядка, в соответствии с (1.11) - (1.13), получаем систему уравнений и неравенств:

{Р(х1) = Р(х2)} > (>){Р(х3) = Р(х4) = Р(х5)} > (>)... > (>)

> (>){Р(хп-1) = Р(хп)}

Систему уравнений и неравенств (1.16) более детально можно записать в виде:

В общем случае такая система будет состоять из уравнений

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

Полную информацию о структурах множеств Х и V, как правило, можно получить только в условиях активного, т. е. специально спланированного эксперимента со специально подготовленным экспертом или группой. В том случае, если такой эксперимент невозможен или нежелателен, проводится пассивный эксперимент, который состоит в наблюдении за поведением неподготовленного специально ЛПР (эксперта) в естественных условиях. Как правило, в этом случае не удается получить полную информацию о структуре множеств X и V. Например, если изучается процесс выбора, то в процессе пассивного эксперимента, зафиксировав выбор ЛПР, можно получить информацию только о наиболее предпочтительной альтернативе (крайнем элементе множества X), но не о структуре предпочтений на всем множестве доступных альтернатив.

Данный случай предполагает проведение либо активного, либо пассивного компараторного эксперимента, в ходе которого ЛПР выбирает единственную наиболее предпочтительную альтернативу xseX, из множества X = {х1,х2,...,хп}. При этом в зависимости от того насколько ЛПР уверено в своем выборе, можно установить отношение или строгого, или нестрогого предпочтения выбранной альтернативы по отношению к остальным:

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

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

Если ЛПР полностью уверено в своем выборе, реализуется компаратор (1.7) с соответствующим предикатом (1.9), если не полностью - (1.8) и (1.10).

На основании вышеизложенного и в соответствии с (1.11) (или (1.12)), получаем систему строгих (или нестрогих) неравенств:

Например, если наиболее предпочтительной для ЛПР является альтернатива х3, то система неравенств (1.18) будет выглядеть следующим образом:

P(х1)<(<)P(х3);

Р(х2)<(<)Р(х3)

………

P(хn)<(<)P(х3),

т. е., в общем случае, может быть сформировано n-1 неравенств.

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

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 Описание генетического алгоритма

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. А кортеж показателей , составляют следующие элементы:

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

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

- понимание;

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

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

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

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

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

) ;

);

);

);

);

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

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

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

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

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

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

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

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

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

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

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

В качестве системного программного обеспечения используется Windows 7.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 легко портируются на другие платформы. Девиз компании 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 - Значения параметров модели

№ параметраЗначениеа10.145а20.057а30.177а40.09992а50.138а60.123а70.194а80.066

ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

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

.Исаев С. Генетические алгоритмы в задачах оптимизации #"justify">5.Mitchell M. An introduction to Genetic Algorithm. MIT Press, 1996.

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

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

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

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

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

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

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

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

ПРИЛОЖЕНИЕ

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

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

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

title = About: ${Application.title} ${Application.version}.Action.text = &Close.text=<html>${Application.description}.text=Product Version\:.text=Vendor\:.text=Homepage\:

#NOI18N.icon=about.png

# Application global resources

.name = Classification.title = Basic Application Example.version = 1.0.vendor = Sun Microsystems Inc..homepage = http\://appframework.dev.java.net/.description = A simple Java desktop application based on Swing Application Framework..vendorId = Sun.id = ${Application.name}.lookAndFeel = system

class GA {Random r = new Random();counter;int[][] population = new int[50][64];int[][] popul10 = new int[50][8];double[][] populNorm = new double[50][8];[] c = new int[50];double[] a = new double[8];

/**

* The method randomly initializes first generation

*/void firstGeneration() {(int i = 0; i < 50; i++) {(int j = 0; j < 64; j++) {[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

*/int[][] mutation(int[][] popul) {z;x;(int i = 0; i < r.nextInt(97); i++) {= r.nextInt(49);= r.nextInt(63);(popul[z][x] == 0) {[z][x] = 1;

} else {[z][x] = 0;

}

}popul;

}

double[][] norm(int[][] array) {sum;(int i = 0; i < 50; i++) {= 0;(int j = 0; j < 8; j++) {+= array[i][j];(j == 7) {(int t = 0; t < 8; t++) {[i][t] = ((double)array[i][t] / (double)sum);

}

}

}

}populNorm;

}

void from2to10() {r = 256;m = 0;q = 0;(int j = 0; j < 50; j++) {= 0;(int i = 0; i < 64; i++) {= r / 2;+= population[j][i] * r;(i != 0 && i % 8 == 0) {[j][m] = q;= 256;++;= 0;

}(i == 63) {[j][m] = q;= 256;= 0;++;

}

}

}(popul10);.out.println(Arrays.deepToString(populNorm));

}

void qualityAnalysis() {

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

(int j = 0; j < 8; j++) {[j] = populNorm[i][j];

}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];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];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];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];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];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];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];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];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];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];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];b12 = 0.13*a[0]-0.09*a[1]-0.13*a[2]+0.05*a[6]-0.11*a[7];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];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];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];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];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];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];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];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];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];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];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];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];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];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];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];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];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];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];(b1 <= 0) {counter++;}(b2 <= 0) {counter++;}(b3 <= 0) {counter++;}(b4 <= 0) {counter++;}(b5 <= 0) {counter++;}(b6 <= 0) {counter++;}(b7 <= 0) {counter++;}(b8 <= 0) {counter++;}(b9 <= 0) {counter++;}(b10 <= 0) {counter++;}(b11 <= 0) {counter++;}(b12 <= 0) {counter++;}(b13 <= 0) {counter++;}(b14 <= 0) {counter++;}(b15 <= 0) {counter++;}(b16 <= 0) {counter++;}(b17 <= 0) {counter++;}(b18 <= 0) {counter++;}(b19 <= 0) {counter++;}(b20 <= 0) {counter++;}(b21 <= 0) {counter++;}(b22 <= 0) {counter++;}(b23 <= 0) {counter++;}(b24 <= 0) {counter++;}(b25 <= 0) {counter++;}(b26 <= 0) {counter++;}(b27 <= 0) {counter++;}(b28 <= 0) {counter++;}(b29 <= 0) {counter++;}(b30 <= 0) {counter++;}(counter >= 30) {.out.println("Оптимальное решение найдено");.out.println(Arrays.toString(a));;

}[count] = counter;++;

}

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

}

void krossengover() {= 0;[] s = new int[64];(int i =0; i<50;i++){(c[i]>=27){[counter]=i;++;

}

}arr1;arr2;(int i=0;i<50;i++){z = r.nextInt(63);(int j=0;j<z;j++){(counter!=0){= population[s[counter]][j];= population[s[counter-1]][j];[s[counter-1]][j]=arr1;[s[counter]][j]=arr2;

counter --;}}

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ СППР- Системы поддержки принятия решений АСУ- Автоматизированные системы управления ЛПР- Лицо, принимающее решение

Больше работ по теме: