ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
РАДІОЕЛЕКТРОНІКИ
Булавін Дмитро Олексійович
УДК 519.81
КОМПАРАТОРНА СТРУКТУРНО-ПАРАМЕТРИЧНА ІДЕНТИФІКАЦІЯ МОДЕЛІ БАГАТОФАКТОРНОГО ОЦІНЮВАННЯ МЕТОДАМИ ГЕНЕТИЧНОЇ СЕЛЕКЦІЇ
01.05.02 – математичне моделювання та обчислювальні методи
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Харків 2005
Дисертацією є рукопис.
Робота виконана в Харківському національному університеті радіоелектроніки Міністерства освіти і науки України.
Науковий керівник – доктор технічних наук, професор Петров Едуард Георгійович, Харківський національний університет радіоелектроніки, завідувач кафедри системотехніки.
Офіційні опоненти: доктор технічних наук, професор Руденко Олег Григорович, Харківський національний університет радіоелектроніки, завідувач кафедри електронно-обчислювальних машин;
кандидат технічних наук, доцент Шеховцов Сергій Борисович, Національний університет внутрішних справ, м. Харків начальник кафедри прикладної математики;
Провідна установа – Донецький національний технічний університет Міністерства освіти і науки України.
Захист відбудеться “ 21 ” червня 2005р. о 1300 годині на засіданні спеціалізованої вченої ради Д 64.052.02 в Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.
З дисертацією можна ознайомитися у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.
Автореферат розісланий _19_.__травня__. 2005р.
Вчений секретар спеціалізованої вченої ради Безкоровайний В.В.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Однією з актуальних проблем моделювання інтелектуальної діяльності людини є формалізація процесів вибору рішень. Теоретична і практична значущість таких моделей обумовлена необхідністю підвищити ступінь автоматизації процедур вибору рішень у системах планування, управління, проектування соціально-економічних та технічних систем, розв’язання задач управління поведінкою. Найважливішим при формалізації процесу вибору рішень з множини багатокрітеріальних альтернатив є визначення метрики для їх ранжування. При цьому виникає необхідність структурної та параметричної ідентифікації моделі індивідуального багатофакторного оцінювання. Наразі ця задача вирішується на аксиоматичному рівні – здебільшого приймається адитивна функція корисності, а її параметри (вагові коефіціенти) визначаються методом експертного оцінювання. Разом з цим необхідність розвитку теорії і рішення практичних задач вимагають розвитку більш формалізованих методів синтезу моделей оцінювання.
Основою вирішення вказаних задач, є фундаментальні результати в області теорії прийняття рішень, серед яких слід зазначити теорію корисності Дж. Неймана й О.Моргенштерна, а також сучасні теоретичні розробки вітчизняних та закордонних учених: П.Фішберна, Р.Кіні, Г.Райфа, О.Г.Івахненко, Ю.П.Шабанова-Кушнаренка, Е.Г.Петрова, А.О.Овезгельдиєва, О.Г.Руденка, Є.В.Бодянського, та ін.
Разом з цим для розв’язання задачі ідентифікації моделей оцінювання неможливо використовувати класичні методи, тому що вони потребують кількісного виміру вхідних та вихідних сигналів системи, а результати оцінювання альтернатив особою, що приймає рішення (ОПР), не можуть бути вимірювані чисельно. Тому необхідні альтернативні методи. Одним з можливих підходів, що розглядається в даній дисертаційній роботі, є метод компараторної ідентифікації, який базується на порівнянні вибраного ОПР рішення з іншими рішеннями з допустимої множини.
Задача компараторної ідентифікації, у загальній постановці, не має єдиного рішення, тобто є некоректною за Адамаром. Для регуляризації і загального розв’язання задачі структурно-параметричної ідентифікації моделі багатофакторного оцінювання альтернатив, у роботі використані методи генетичної селекції, такі як метод групового урахування аргументів і генетичне програмування.
Зв’язок роботи з науковими програмами та планами. Дисертаційна робота виконана у 2001-2004 р. на кафедрі системотехніки Харківського національного університету радіоелектроніки в рамках держбюджетної теми НДР № 165-1 „Математичні моделі і методи прийняття рішень в умовах багатокритеріальності” (№ ДР 0103U001564), в розробці якої автор брав участь як виконавець.
Мета й задачі дослідження. Метою дисертаційної роботи є розробка математичних моделей, ефективних обчислювальних методів та інструментальних засобів для розв’язання задачі структурно-параметричної ідентифікації функції багатофакторного оцінювання корисності альтернативних рішень методом компараторної ідентифікації. Ця мета реалізується на новій концептуальній основі шляхом застосування методів генетичної селекції для визначення структури і параметрів функції корисності, представленої у виді полінома Колмогорова-Габора.
Досягнення зазначеної мети потребує рішення наступних задач:
- розвитку теоретичних основ синтезу математичних моделей багатофакторного оцінювання і процедур їх структурно-параметричної ідентифікації на основі методів генетичної селекції;
- розвитку методу компараторної ідентифікації моделей багатофакторного оцінювання, який базується на порівнянні вибраного ОПР рішення з альтернативами з допустимої множини;
- формулювання й обґрунтування тверджень, що аргументують використання методу компараторної ідентифікації і методів генетичної селекції для розв’язання задачі структурно-параметричної ідентифікації функції багатофакторного оцінювання;
- розробки моделей, обчислювальних процедур і інструментальних засобів розв’язання задачі структурно – параметричної ідентифікації функції багатофакторного оцінювання з використанням методів
- групового урахування аргументів (МГУА),
- генетичного програмування (генетичних алгоритмів);
- верифікації розроблених моделей і оцінки ефективності алгоритмів, що реалізують ці обчислювальні методи;
- програмної реалізації розроблених моделей і обчислювальних процедур;
- тестового моделювання з метою апробації й експериментального підтвердження працездатності та ефективності виконаних дисертаційних розробок.
Об'єктом дослідження є формалізація процесів прийняття багатокритеріальних рішеннь з метою їхньої автоматизації та реалізації на ЕОМ.
Предметом дослідження є математичні моделі та обчислювальні методи розв’язання задачі структурно-параметричної ідентифікації функцій багатофакторного оцінювання корисності альтернатив.
Методи досліджень базуються на ідеях та принципах системного аналіза, теорії прийняття рішень та обчислювальних методах генетичної селекції. Для розв’язання задач структурно-параметричної ідентифікації використовуються методи групового урахування аргументів та генетичного програмування.
Наукова новизна одержаних результатів
1. Вперше запропоновано використовувати в якості функції корисності поліном Колмогорова-Габора, який поєднує в собі адитивні та мультиплікативні члени.
2. Вперше розроблено математичну модель та обчислювальні засоби розв'язання задачі структурної ідентифікації за допомогою методів генетичної селекції, які дозволяють формалізувати процес отримання рішення при більш загальних припущеннях про структуру функції корисності.
3. Вперше синтезована математична модель параметричної ідентифікації за допомогою метода генетичного програмування та розроблені інструментальні засоби розв'язання цієї задачи.
4. Набув подальшого розвитку метод верифікації адекватності і точності синтезованих моделей структурно-параметричної ідентифікації функції багатофакторного оцінювання.
Практичне значення одержаних результатів полягає в доведенні автором теоретичних розробок до конкретних алгоритмів, а також у розробці інтерактивного програмного комплексу (ІПК) “Компаратор”. Ці засоби можна безпосередньо використовувати в проектних, маркетингових і промислових організаціях для створення автоматизованих систем підтримки прийняття рішень (СППР) різного призначення. Результати досліджень впроваджено на АТВТ „Харківський молочний комбінат”, на НВПП „Харківський інститут екології”, а також в учбовий процес ХНУРЕ.
Апробація результатів дослідження. Основні результати дисертаційної роботи доповідалися та обговорювалися на 5 – 8-му Міжнародних молодіжних форумах „Радіоелектроніка та молодь у ХХІ сторіччі” (Харків 2001-2004 рр.); на 8 – 10-й Міжнародних конференціях „Теорія та техніка передачі, прийому й обробки інформації” (Харків – Туапсе, 2002-2004 рр.); на 28 – 30-й Міжнародних молодіжних наукових конференціях „Гагаринские чтения” (Москва, 2002-2004 рр.).
Публікації. Основні результати дослідження опубліковані в 15 друкованих працях, з яких 4 є статтями в наукових фахових виданнях, що входять до переліку ВАК України, а також 11 публікацій у матеріалах і тезах наукових конференцій.
Особистий внесок здобувача. У роботі [1] авторові належить розробка моделей і методів генетичних алгоритмів для розв’язання задачі компараторної ідентифікації; [2] – експериментальне порівняння метода Чебишевської точки та генетичних алгоритмів; [3] – розробка моделей і методів генетичних алгоритмів для розв’язання задачі структурно-параметричної ідентифікації; [4] – реалізація методу групового урахування аргументів для розв’язання задачі структурно-параметричної ідентифікації; у [11] – розробка методів розв’язання задачі й аналіз застосованих методів, у [12] – автором запропоновано застосування метода генетичних алгоритмів без урахування вагових коефіціентів; [13] – розроблені принципи порівняння метода групового урахування аргументів та метода генетичного програмування; [14] – постановка задачі, а також методика й алгоритми її вирішення.
Структура та обсяг роботи. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаної літератури і трьох додатків на 18 сторінках. Загальний обсяг дисертації 160 стор., у тому числі 4 малюнка на 4 сторінках, 13 таблиць на 9 сторінках, список із 115 використаних джерел на 12 сторінках.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обгрунтовано актуальність теми дисертації, відображена її наукова та практична цінність, сформульовані мета та задачі дослідження, які треба вирішити для ії досягнення. Надана стисла характеристика результатів досліджень, наведені відомості про їх апробацію і публікацію.
У першому розділі дисертації здійснено системологічний аналіз сучасного стану проблеми прийняття рішень, розглянуто існуючі методи розв'язання задач структурної і параметричної ідентифікації, та дано стислу характеристику методів генетичної селекції.
Оцінки альтернативних рішень, що формуються людиною, суб'єктивні і їх неможливо безпосередньо виміряти у кількісних шкалах. У таких випадках класичні методи прямої ідентифікації для вивчення процесів оцінювання незастосовні. Альтернативними є методи непрямої ідентифікації. З них перспективним для вказаного класу задач є метод компараторної ідентифікації.
Теоретичною основою визначення підмножини оптимальних альтернатив є теорія корисності. Відповідно до неї з двох заданих альтернатив і при цьому (тобто альтернатива є більш привабливою, ніж ), випливає:
, (1)
де , - функції корисності відповідних альтернатив.
У загальному випадку справедливо і зворотнє твердження. Отже, корисність – це кількісна оцінка “якості” рішення, за допомогою якої можна ранжувати альтернативи або безпосередньо визначити екстремальну з них. Але для цього потрібно визначити цю функцію.
Синтез будь-якої математичної моделі, включаючи і синтез функції корисності, потребує рішення двох взаємозалежних задач: структурної і параметричної ідентифікації.
Структурна ідентифікація припускає:
- визначення значущих факторів, що впливають на вихідні дані моделі;
- визначення структури, тобто виду оператора, що встановлює зв'язок між вхідними і вихідними характеристиками моделі.
Задача параметричної ідентифікації передбачає визначення конкретних кількісних значень параметрів моделі.
У теорії корисності найбільш широко використовуються дві аксіоматичні структури функції корисності: адитивна
(2)
і мультиплікативна
, (3)
де – коефіцієнти, що приводять різнорідні часткові критерії до однакової розмірності, однакового інтервалу зміни і враховують їх різну „вагу”.
Вираз (3) показує, що мультиплікативна оцінка не дозволяє врахувати “ваги” часткових критеріїв, тому що добуток є постійним масштабним множником і не впливає на співвідношення корисностей різних рішень . Тому більш широко застосовується аддитивна функція корисності, яку для практичного використання трансформують у вигляд:
, (4)
де – відносні безрозмірні вагові коефіцієнти, для яких виконуються наступні обмеження:
,; (5)
– це нормалізовані, тобто приведені до безрозмірного виду і однакового інтервалу значень, часткові критерії.
В дисертації нормалізація часткових критеріїв проводиться за формулою:
, (6)
де – значення часткового критерію альтернативи ; , – відповідно найкраще і найгірше значення часткового критерію, що він приймає на області припустимих значень .
У такий спосіб на аксіоматичному рівні постулюється структура моделі оцінювання і задача синтезу функції корисності зводиться до параметричної ідентифікації вагових коефіцієнтів . Для цього використовуються методи експертного оцінювання або компараторної ідентифікації.
Недолік аддитивної функції корисності полягає в тому, що вона не враховує можливої нелінійності залежності корисності від абсолютних значень часткових критеріїв та їхного взаємовпливу.
Великий теоретичний і практичний інтерес має рішення загальної задачі структурно-параметричної ідентифікації моделі індивідуального оцінювання при більш широких обмежуючих допущеннях про структуру моделі.
Для цього обгрунтовано використання, як класу можливих структур, поліному Колмогорова-Габора
, (7)
Такий підхід дозволяє описати будь-яку нелінійну залежність і не накладає ніяких апріорних обмежень на адитивність або мультиплікативність, тому що поліном (7) містить у своєму складі як перші, так і більш високі ступені характеристик і всі можливі їхні комбінації.
Згідно з теоремою Вейєрштрасса, будь-яку послідовність експериментальних даних можливо точно апроксимувати поліномом із членом шляхом рішення системи нормальних алгебраїчних рівнянь. Однак така апроксимація не означає, що синтезовано адекватну модель високої точності з гарними прогностичними властивостями. Це обумовлено тим, що експериментальні дані містять вимірювальні та інші неконтрольовані випадкові погрішності. Тому поліном високої складності апроксимує не тільки корисний сигнал, але й випадкові погрішності експериментальних даних. Для подолання зазначеного недоліку в роботах Івахненко О.Г. запропоновано розділяти вибірку експериментальних даних на дві підмножини: навчальну і перевірочну. Перша підмножина використовується для синтезу моделі і визначення її характеристик, наприклад, методом найменших квадратів, а друга – для перевірки точності моделі. При цьому виявилося, що при збільшенні складності моделі точність апроксимації перевірочної послідовності експериментальних даних спочатку поліпшується, досягає деякого мінімуму і потім починає погіршуватися за рахунок обліку “шкідливих” випадкових складових. Модель мінімальної складності, що дає мінімум погрішності апроксимації перевірочної послідовності, одержала назву моделі оптимальної складності.
Також у першому розділі проаналізовано підходи до вибору структури моделі, засновані на методах прямої та непрямої аналогії та обгрунтоване використання останього.
Розглянуті класичні методи параметричної ідентифікаціі, такі як метод мінімізації помилок передбачення; метод найменьших квадратів; метод максимальної правдоподібності; байєсовський підхід і показано, що вони принципово непридатні, коли відсутня кількісна інформація про вихід об’єкта. В таких умовах потрібно розробити нові методи. На основі проведеного аналізу для рішення задачі структурної ідентифікації запропоновано використати метод групового урахування аргументів і метод генетичного програмування, а для задачі параметричної ідентифікації – метод генетичного програмування.
Другий розділ присвячено розробці загальної постановки задачі компараторної структурно-параметричної ідентифікації функції корисності та синтезу математичних моделей розв'язання задачі параметричної ідентифікаціїї моделі індивідуального багатофакторного оцінювання.
Нехай задана множина альтернатив (рішень) , , кожна з яких характеризується набором часткових критеріїв (характеристик) , . Значення часткових критеріїв однозначно визначені. На основі аналізу зазначеної інформації індивідуум здійснює:
- або вибір з тільки кращого рішення, наприклад ;
- або ранжування всіх рішень у порядку зменшення їхньої переваги, тобто встановлює строге
, (8)
або нестроге
(9)
відношення порядку на множині альтернатив .
Це означає, що відповідно до теорії корисності (1), для випадку, коли вказано тільки краще рішення, можна записати:
, (10)
а для випадків (8), (9) відповідно:
(11)
або
, (12)
де – невідома скалярна індивідуальна оцінка корисності альтернативи.
У зв’язку з тим, що відношення порядку з визначення є транзитивним, у загальному випадку на основі (10), (11) можна записати систему нерівностей виду:
, (13)
де – найкраща альтернатива.
На основі цієї інформації необхідно синтезувати математичну модель індивідуального вибору ОПР, тобто модель формування узагальненої корисності . Ідентифікація моделі багатофакторного оцінювання в цьому випадку полягає в ітераційному виконанні наступних процедур:
- визначення виду полінома, що описує модель , який буде деяким фрагментом полінома Колмогорова – Габора;
- формування системи нерівностей виду (13), що визначають множину можливих значень коефіцієнтів (параметрів) моделі ;
- вибір із припустимої області значення коефіцієнтів моделі.
Процедури циклічно повторюються доти, доки буде отримана модель оптимальної складності, яка задовольняє всім нерівностям (13). Таким чином, виникає потреба вирішення задачи параметричної ідентифікації.
Система нерівностей (13) разом з співвідношенням (5) формує у просторі параметрів випуклий поліедр, який визначає множину припустимих значень. Параметрична ідентифікація в цьому випадку заключається у визначенні конкретного точкового значення. Для цього можна скористатися відомими Чебишевським рішенням або методом інтервального оцінювання. Ці методи було проаналізовано, визначені їх недоліки і для рішення задачі була розроблена модифікація метода генетичного програмування.
Припустимо, що структура моделі відома і необхідно визначити параметри методом генетичного програмування.
Реалізація методу проводиться у наступний спосіб. Аналізуємо структуру моделі і визначаємо кількість коефіцієнтів , які треба визначити. По визначенню значення коефіцієнтів повинне задовольняти умовам (5). Задаємо точність визначення коефіцієнтів, наприклад 0,01, тобто 102 значень.
Звідси число біт , що має містити хромосома кожного коефіцієнта , дорівнює:
, (14)
де [ , ] – інтервал зміни , зазначений у (5), тобто , , а довжина сумарної хромосоми усіх коефіцієнтів , має вигляд:
(15)
де дорівнює верхній межі ступені з (14).
Формуємо популяцію хромосом коефіцієнтів і вирішуємо задачу генетичного вибору таких значень коефіцієнтів, що максимізують значення функції відповідності. За функцію відповідності приймаємо число задоволених нерівностей системи (10), яка при необхідності може бути розділена на навчальну і перевірочну множини.
На сформованих популяціях реалізується ітераційна процедура генетичного вибору на другій і першій популяціях до досягнення кращого значення функції відповідності.
Оцінка функції відповідності хромосоми виконується в три етапи.
1. Перетворення генотипу хромосоми у фенотип .
У даній задачі це означає перетворення двоїчного рядка у відповідне десятичне значення та масштабування його відповідно до умови (5).
2. Обчислення для всіх альтернатив.
1. Визначення кількості нерівностей системи (10), яким задовольняє дане рішення. Якщо задовольняються усі нерівності, то рішення знайдено, якщо ні – необхідно продовжити дію алгоритму.
У третьому розділі розглядаються методи розв’язання задачі структурної ідентифікації синтезу моделі оптимальної складності, що забезпечують мінімум критерію оцінки похибки апроксимації експериментальних даних виходу моделі. У якості таких методів розглянуто метод групового урахування аргументів (МГУА) та метод генетичного програмування.
Спочатку розглянемо МГУА. Для спрощення викладання матеріалу, але без втрати загальності, розглянемо ситуацію, коли задані чотири часткові критерії . Складемо всі неповторювані попарні комбінації (групи) часткових критеріїв : Будемо визначати модель оптимальної складності у класі полінома Колмогорова-Габора (7), з якого виключений вільний член. Це аргументується тим, що якщо усі часткові критерії приймають нульові значення, функція корисності завжди дорівнює нулю.
Як часткові поліноми приймемо рівняння виду:
(16)
Для кожного з 6 поліномів системи рівнянь (16) методом компараторної ідентифікації визначаються чисельні значення вагових коефіцієнтів . Для рішення цієї задачі скористаємося методом генетичного програмування, що описаний у другому розділі.
Для кожного полінома (16) визначається оцінка якості моделі. У силу специфіки об'єкта моделювання, докладно розглянутої в розділах 1 і 2, за таку оцінку приймається кількість задоволених нерівностей виду (10). Для цього по кожному частковому поліному розраховуються корисності всіх альтернатив і встановлюється на них відношення порядку. Воно порівнюється з заданим (10) і по числу збігів визначається якість часткових моделей.
Виключаємо з подальшого розгляду два гірших часткових поліноми і на чотирьох, що залишилися повторюємо операцію попарного групування:
Формуємо для кожної пари поліном другого рівня:
(17)
Проводимо параметричну компараторну ідентифікацію аналогічно першому рівню селекції. Процедуру циклічно повторюємо доти, доки на деякому рівні селекції буде отриманий поліном, оцінка якості якого задовольняє всім нерівностям (10). По цьому поліному шляхом послідовної підстановки проміжних перемінних відновлюється повний поліном, тобто модель багатофакторного оцінювання корисності, у термінах вихідних перемінних.
Основною перевагою МГУА є те, що після кожного етапу рішення з'являється можливість відокремити “корисні” рішення від “шкідливих”, і в подальшому використовувати тільки “корисні” рішення. Даний метод дозволяє отримати високу точність і дозволяє знизити трудомісткість за рахунок послідовного розгляду коротких поліномів, що враховують тільки пари аргументів, замість одного, який враховує одразу всі аргументи. Результати розрахунків цим методом наведені в розд.4 .
Як альтернативу МГУА для вирішення задачи структурно-параметричної ідентифікації функції корисності розглянуто метод генетичного програмування. Для цього задається набір альтернативних рішень , . Кожна альтернатива характеризується кортежем часткових критеріїв , , що задаються у виді точних числових значень. Крім того визначена найкраща альтернатива. Ця альтернатива розглядається як вибір ОПР. Для неї складається система нерівностей виду (10), яка доповнюється співідношеннями (5) і далі вирішується задача компараторної структурно-параметричної ідентифікації, у результаті якої визначається структура і параметри моделі оцінювання.
При рішенні задачі структурно-параметричної ідентифікації методом генетичного програмування можна виділити наступні етапи:
- формування початкової популяції;
- розв’язання задачі параметричної ідентифікації з використанням генетичних алгоритмів (розд.2);
- оцінка якості початкової популяції;
- проведення операцій кросоверу та мутації;
- оцінка якості нової популяції, отриманної в результаті селекції;
- реалізація другого та наступних циклів селекції.
Для формування початкової популяції необхідно виділити клас припустимих структур. Як такий приймемо поліном Колмогорова-Габора, виключивши з нього вільний член і обмеживши його тільки лінійними і квадратичними членами. Тоді поліном буде мати вигляд:
(18)
Це означає, що для часткових критеріїв повний поліном буде мати
(19)
членів. Отже, кожна хромосома популяції має містити біт.
Введене обмеження на складність полінома засноване на тому, що після нормалізації по формулі (6) усі часткові критерії мають значення . Зведення таких чисел у ступінь або добуток двох і більш таких чисел приведуть до швидкого зменшення значень. Крім того кожен член полінома збільшується на коефіцієнт (так як сума всіх коефіціентів дорівнює одиниці). Тому значення більш ніж квадратних членів малі і їх можна не враховувати. Втім, допущення (18) не є принциповим, тому що генетичний алгоритм не критичний до порядку поліному, але треба враховувати швидке зростанння розміру хромосоми.
Вирішення задачі визначення коефіцієнтів кожного поліному (хромосоми), що входять до начальної і подальших популяцій, проводиться з використанням генетичного алгоритму методом, що наведений у розд.2.
Оцінка якості поліномів проводиться по кількості нерівностей (10), які задовольняються.
Для формування нової популяції хромосом використовуються операції одноточкового кросоверу та мутації.
Згідно з Холландом оператор кросоверу в технічних системах виконується в три етапи.
1. Із початкової популяції випадковим чином обираємо дві хромосоми, наприклад
1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0
та
1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0
2. Випадковим чином обирається число , що є точкою кросовера, з , де – довжина хромосоми.
3. Дві нові хромосоми формуються з и . Нехай , в результаті отримаємо хромосоми и
1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0
0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0
Таким чином, формується нова популяція хромосом. Потім стара популяція частково або повністю знищується, і ми переходимо до розглядання наступного покоління. Популяція наступного покоління у більшості реализацій генетичних алгоритмів містить стільки же особей, скільки початкова, але в силу відбору пристосованість в ній в середньому вище.
Мутації, при необхідності, проводяться на популяціях наступних поколінь. За звичай мутація проводиться один раз на 100 кроках. Аналогічно кросоверу випадковим чином обираються номери генів в хромосомах популяції, які міняються місцями.
Робота алгоритма закінчується як тільки буде отримано поліном, для якого виконуються усі вихідні нерівності (10).
Опис алгоритму та програми, що його реалізує і результати тестових розрахунків за цим методом наведені у розд. 4.
У четвертому розділі проведено експериментальну перевірку адекватності і точності запропонованих математичних моделей, дана порівняльна характеристика застосування методів генетичного програмування і групового урахування аргументів для рішення задачі структурно-параметричної ідентифікації моделі індивідуального багатофакторного оцінювання.
Експериментальну перевірку працездатності й ефективності методу генетичного програмування і методу групового обліку аргументів ідентифікації моделі багатофакторного оцінювання реалізовано з використанням принципу зовнішнього доповнення.
У якості зовнішнього доповнення використовується незалежна тестова ситуація вибору рішення. Для цього визначається деяка множина альтернатив , . Для кожної з них формується кортеж часткових критеріїв , ;. Крім того, задається структура і параметри моделі багатофакторного оцінювання альтернатив , тобто вид полінома і значення його коефіцієнтів. Таким чином, ситуація вибору повністю визначена.
Для тестової ситуації розраховуються значення функції корисності для кожної альтернативи , і з урахуванням цього встановлюється відношення порядку на множині вида (8) або (9) та визначається краща альтернатива. Вона приймається за таку, яку вибрав ОПР, і в подальшому для моделювання використовується тільки ця інформація.
З урахуванням цієї інформації формуємо модель (10), доповнюємо її співвідношеннями (5) і послідовно методами МГУА і генетичного програмуванння вирішуємо задачу структурно-параметричної ідентифікації функції корисності . Отримані результати порівнюються з тестовими.
За критерії оцінки адекватності і точності синтезованої моделі приймається ступінь співпадання тестових і модельних значень корисності альтернатив і відношення порядку на множині :
- абсолютна сумарна відмінность корисностей альтернатив
; (20)
- квадратична оцінка виду
. (21)
Для тестового моделювання за допомогою датчика випадкових чисел, розподілених в інтервалі [0,1], було згенеровано по 30 кортежів , ; для кожної ситуації:
- < >, тобто ;
- < >, тобто ;
- < >, тобто ;
- < >, тобто .
З кожного масиву 30-ти кортежів були вибрані 12 суперечливих за значеннями , тобто недомінованих альтернатив.
Для кожного випадку вирішено задачу структурно-параметричної ідентифікації за допомогою методів генетичних алгоритмів і групового урахування аргументів. Результати розрахунків наведені в табл.1.
Таблиця 1
Результати структурно-параметричної ідентифікації
Тестова ситуаціяРезультати моделюванняМГУА | Генетичне програмуванняВид моделі оцінки | Відношення порядку | абсолютна сумарна відмінність корисностей альтернатив0,08 | 0,06 | квадратична оцінка виду0,009 | 0,007 | МГУА | Генетичне програмування | Вид моделі оцінки | Відношення порядку | абсолютна сумарна відмінність корисностей альтернатив0,11 | 0,14 | квадратична оцінка виду0,01 | 0,03 |
Продовж. табл. 1
Тестова ситуаціяРезультати моделюванняМГУА | Генетичне програмуванняВид моделі оцінки | Відношення порядку | абсолютна сумарна відмінність корисностей альтернатив0,09 | 0,1 | квадратична оцінка виду0,01 | 0,02 | МГУА | Генетичне програмуванняВид моделі оцінки
Відношення порядку | абсолютна сумарна відмінність корисностей альтернатив0,12 | 0,15 | квадратична оцінка виду0,02 | 0,03 |
ВИСНОВКИ
У дисертації проведено аналіз проблеми формалізації процесу прийняття багатофакторних рішень в умовах невизначенності в технічних та соціально-економічних системах. Визначені дві найважливіші задачі – структурної та параметричної ідентифікації моделі індивідуального багатофакторного оцінювання. Оскільки експертні методи ідентифікаціі мають багато недоліків, в дисертаціі було проведено узагальнення та подальший розвиток формального методу компараторної ідентифікаціі.
Метою даної дисертаційної роботи є розробка математичних моделей розв'язання задачі структурно-параметричної ідентификації функції багатофакторного оцінювання за допомогою методів генетичної селекції. В результаті дослідження були отримані наступні результати:
1. Проведено системологічний аналіз проблеми синтезу моделей індивідуального багатофакторного оцінювання та сформульовано задачу формальної структурної та параметричної ідентифікації цих моделей.
2. Обгрунтовано використання модифікованого методу компараторної ідентифікації для розв'язання поставленої проблеми.
3. Вперше запропоновано використовувати в якості функції корисності поліном Колмогорова-Габора, який поєднує в собі адитивну та мультиплікативну моделі оцінювання.
2. Вперше для розв'язання задачі параметричної ідентифікації використано метод генетичних алгоритмів і розроблена його модифікація, що враховує специфіку задач компараторної ідентифікації.
3. Вперше розроблено математичну модель та інструментальні засоби для розв'язання задачі структурної ідентифікації за допомогою методу генетичного програмування.
4. Вперше розроблено математичну модель та обчислювальні засоби для розв'язання задачі структурної ідентифікації за допомогою методу групового урахування аргументів.
5. Набув подальшого розвитку метод верифікації адекватності і точності моделей структурно-параметричної ідентифікації, який базується на принципах формування зовнішнього незалежного доповнення.
Результати тестового моделювання показали, що при використанні метода генетичного програмування для розв’язання задачі структурно-параметричної ідентифікації отримані поліноми, які відповідають сформульованим вимогам, та відношення порядку на множині альтернатив в цілому співпадає з тестовим. Таким чином, сформульовану задачу можна вирішувати як МГУА, так и за допомогою генетичних алгоритмів, але останні на 10-15 відсотків менш трудомісткі.
СПИСОК РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1. Петров Э.Г., Булавин Д.А. Использование метода генетических алгоритмов для решения задач компараторной идентификации модели многофакторного оценивания // Радиоэлектроника и информатика. – 2003. – №1. – С. 89 – 93.
2. Петров Э.Г., Булавин Д.А. Использование метода Чебышевской точки и генетических алгоритмов для определения структуры модели многофакторного оценивания // Проблемы бионики. – 2003. – №58. – С. 36 – 44.
3. Петров Э.Г., Булавин Д.А., Петров К.Э. Использование метода генетических алгоритмов для решения задачи структурно-параметрической идентификации модели индивидуального многофакторного оценивания // Проблемы бионики. – 2004. – № 60. – С. 17–26.
4. Петров Э.Г., Булавин Д.А. Применение метода группового учета аргументов для решения задачи структурно-параметрической идентификации модели индивидуального многофакторного оценивания // АСУ и приборы автоматики. – 2004. – № 4. – С. 4–13.
5. Булавин Д.А. Решение задач оптимизации с помощью нейронных сетей // Тр. 5-го Междунар. молод. форума “Радиоэлектроника и молодежь в ХХIв”. – Ч.1. – Харьков: Изд.-полигр. центр ХНУРЭ. – 2001. – С. 54 – 55.
6. Булавин Д.А. Постановка задачи идентификации модели принятия решений с помощью метода компараторной идентификации // Тр. Междунар. молод. науч. конф. “XXVIII Гагаринские чтения”. – Том 2. – М.: Изд. “МАТИ” - Рос. гос. технол. ун-та им. К.Э. Циолковского. – 2002. – С.54 – 55.
7. Булавин Д.А. Постановка задачи компараторной идентификации модели многофакторного оценивания // Тр. 6-го Междунар. молод. форума “Радиоэлектроника и молодежь в ХХIв”. – Ч.2. – Харьков: Изд.-полигр. центр ХНУРЭ. – 2002. – С. 4 – 5.
8. Булавин Д.А. О методе компараторной идентификации // Тр. 8-ой Междунар. конф. “Теория и техника передачи, приема и обработки информации”, Харьков: Изд.-полигр. центр ХНУРЭ. -2002. – С. 167 – 169.
9. Булавин Д.А. Идентификация структуры модели многофакторного оценивания с помощью метода генетических алгоритмов // Тр. Междунар. молод. науч. конф. “XXIХ Гагаринские чтения”. – Том 7. – М.: Изд. “МАТИ” - Рос. гос. технол. ун-та им. К.Э. Циолковского. – 2003. – С.94 – 95.
10. Булавин Д.А. Алгоритм решения задач компараторной идентификации с использованием генетических алгоритмов // Тр. 7-го Междунар. молод. форума “Радиоэлектроника и молодежь в ХХIв”. – Харьков: Изд.-полигр. центр ХНУРЭ. – 2003. – С. 534.
11. Петров Э.Г., Булавин Д.А. Применение методов Чебышевской точки и генетических алгоритмов для решения задач компараторной идентификации // Тр. 9-ой Междунар. конф. “Теория и техника передачи, приема и обработки информации”, Харьков: Изд.-полигр. центр ХНУРЭ. -2003. – С. 421 – 422.
12. Булавин Д.А., Варламов А.Е. Применение генетических алгоритмов в задачах многофакторного оценивания без учета весовых коэффициентов // Тр. Междунар. молод. науч. конф. “XXХ Гагаринские чтения”. – Том 7. – М.: Изд. “МАТИ” - Рос. гос. технол. ун-та им. К.Э. Циолковского. – 2004. – С.163 – 164.
13. Булавин Д.А., Варламов А.Е. Применение генетических алгоритмов и МГУА для решения задачи компараторной идентификации // Тр. Междунар. молод. науч. конф. “XXХ Гагаринские чтения”. – Том 7. – М.: Изд. “МАТИ” - Рос. гос. технол. ун-та им. К.Э. Циолковского. – 2004. – С.178 – 179.
14. Булавин Д.А., Варламов А.Е. Решение задач компараторной идентификации с использованием генетических алгоритмов и метода группового учета аргументов // Тр. 8-го Междунар. молод. форума “Радиоэлектроника и молодежь в ХХIв”. – Харьков: Изд.-полигр. центр ХНУРЭ. – 2004. – С. 230.
15. Булавин Д.А. Сравнение аксиоматических и нелинейных методов идентификации // Тр. 10-ой Междунар. конф. “Теория и техника передачи, приема и обработки информации”, Харьков: Изд.-полигр. центр ХНУРЭ. -2004. – С. 44 – 45.
АНОТАЦІЯ
Булавін Д.О. “Компараторна структурно-параметрична ідентифікація моделі багатофакторного оцінювання методами генетичної селекції”. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. – Харківський національний університет радіоелектроніки, Харків, 2004.
Синтезовано математичні моделі та розроблені інструментальні засоби для розв’язання задачі компараторної структурно-параметричної ідентифікації функції багатофакторного оцінювання альтернатив за допомогою методів генетичної селекції.
Запропоновано використовувати у якості функції корисності поліном Колмогорова-Габора, який поєднує у собі адитивні та мультиплікативні члени. Для розв’язання задачі параметричної ідентифікації використано метод генетичного програмування, а для структурної ідентифікації метод групового урахування аргументів і метод генетичного програмування.
Проведено експериментальну перевірку запропонованих методів з використанням зовнішнього незалежного доповнення і показано, що синтезовані моделі дозволяють ефективно вирішувати задачі структурно-параметричної ідентифікації функції багатофакторного оцінювання.
Ключові слова: особа, що приймає рішення, модель індивідуального багатофакторного оцінювання, вагові коефіцієнти, функція корисності, поліном Колмогорова-Габора, компараторна ідентифікація, структурно-параметрична ідентифікація, генетичні алгоритми, метод групового урахування аргументів.
АННОТАЦИЯ
Булавин Д.А. “Компараторная структурно-параметрическая идентификация модели многофакторного оценивания методами генетической селекции”. – Рукопись.
Диссертация на соискание ученой степени кандидата наук по специальности 01.05.02 – математическое моделирование и вычислительные методы. – Харьковский национальный университет радиоэлектроники, Харьков, 2005.
Диссертация посвящена разработке моделей и инструментальных средств для решения задачи формальной структурно-параметрической идентификации модели индивидуального многофакторного оценивания. Разработка методов идентификации моделей интеллектуальной деятельности человека одна из важнейших проблем общей теории принятия решений. Трудность ее решения заключается в отсутствии прямого доступа к выходному сигналу объекта и невозможности получения его численных значений. Многие задачи такого типа можно решать методом компараторной идентификации.
Пусть имеется множество альтернатив (решений), каждая из которых характеризуется набором частных критериев (характеристик). Значения частных критериев однозначно определены. На основе анализа указанной информации индивидуум осуществляет:
- или выбор из множества альтернатив наиболее предпочтительного решения;
- или ранжирование всех решений в порядке убывания их предпочтительности.
На основе этой информации необходимо идентифицировать математическую модель индивидуального выбора ЛПР, то есть модель формирования обобщенной полезности. В настоящее время наиболее широко используются две формы функции полезности: аддитивная и мультипликативная. Однако обе они имеют некоторые недостатки, поэтому для решения задачи структурной идентификации предлагается использовать в качестве функции полезности полином Колмогорова-Габора, а в качестве метода решения общей задачи структурно-параметрической идентификации – методы генетической селекции.
Такой подход позволяет описать любую нелинейную зависимость и не накладывает никаких априорных ограничений на аддитивность или мультипликативность, так как полином Колмогорова-Габора содержит в своем составе как первые, так и более высокие степени частных критериев и все возможные их комбинации.
В данной диссертационной работе для решения задачи параметрической идентификации используется метод генетических алгоритмов, а для решения задачи структурной идентификации метод группового учета аргументов и метод генетического программирования.
Проведена экспериментальная проверка предложенных методов с использованием внешнего независимого дополнения и показано, что синтезированные модели позволяют эффективно решать задачи структурно-параметрической идентификации функции многофакторного оценивания.
Оценка качества идентифицированной модели производится путем сравнения с эталонной моделью по следующим критериям:
- степени совпадения структуры (полиномов);
- различию значений весовых коэффициентов;
- абсолютному суммарному отличию полезностей альтернатив;
- квадратичной оценки.
Таким образом, сформулированную задачу можно решать как с помощью МГУА, так и используя метод генетических алгоритмов, но последние на 10-15 процентов менее трудоемкие.
Ключевые слова: лицо, принимающее решение, модель индивидуального многофакторного оценивания, весовые коэффициенты, функция полезности, полином Колмогорова-Габора, компараторная идентификация, структурно-параметрическая идентификация, генетические алгоритмы, метод группового учета аргументов.
ABSTRACT
Bulavin D.A. “Comparatory structure-parametric identification of the multifactor estimation model with the genetic selection methods”. – Manuscript.
The dissertation is the manuscript presented for the scientific degree of the Candidate of Technical Science on the speciality 01.05.02 – Matematical modeling and computing methods – Kharkov National University of Radio Electronics, Kharkov, 2005.
Mathematical model and instrumental means for solving the structural identification problem with the genetic programming method are formulated; this model makes it possible to accelerate derivation of the solution and increase the obtained solution quality.
It is offered to use Kolmogorov-Gabor polynomial as a function combining adaptive and multiplicative terms. The genetic algorithms method is used for the parametrtic identification problems solution for the first time.
The offered methods are checked experimentally and it is shown that the offered methods give better results than the Group Method Data Handling in the structural identification problem and Chebyshev point method in the parametric identification problem.
Key words: decision-making person, individual multifactor identification model estimation, weight coefficients, quality function, Kolmogorov-Gabor polynomial, comparator identification, stuctural-parametric identification, genetic algorithms, Group Method Data Handling.
Відповідальний випусковий В.В. Безкоровайний
Підп. до друку 17.05.2005. Формат 60х84/16. Спосіб друку – ризографія.
Умов.-друк. 1,2. Обл.-вид. арк. 1,1. Наклад 100 прим.
Зам. № ________.
ХНУРЕ, Україна, 61166, Харків, проспект Леніна, 14 | Віддруковано в навчально-науковому
видавничо-поліграфічному центрі ХНУРЕ
Україна, 61166, м. Харків, проспект Леніна, 14
