На головну

Методи пошуку рішення

  1.  Cтатіческіе методи обгрунтування інвестицій
  2.  I. Методи перехоплення.
  3.  IE1, регістр 1 дозволу переривань
  4.  II. Методи несанкціонованого доступу.
  5.  II. Методи патогенетичної і етіологічної (особистісно орієнтованої) психотерапії
  6.  II. Структурні і персональні методи управління організаційними конфліктами.
  7.  III. Методи агрегатування і уніфікації.

Якщо рішення задачі невідомо чи неоднозначно, наприклад, відсутні аналоги або його важко визначити в явному вигляді, то застосовуються методи пошуку (виведення) рішення. Більшість цих методів засновано на стратегіях повного перебору, імпліцитно (неявного, неповного) перебору або скороченого (спрямованого) перебору на основі евристик (евристичний пошук). стратегія повного перебору використовується при відсутності достатньої апріорної інформації про завдання і порівняно невеликої потужності безлічі альтернатив (до 103 елементів при ручному рахунку і до 109 - На ЕОМ). імпліцитний перебір включає велику групу градієнтних методів, наприклад симплекс-метод, метод мінімальної вартості ( "жадібний" алгоритм), динамічне програмування,  -метод, метод гілок і меж і т.п. Всі вони засновані на розгляді на кожному кроці пошуку не тільки простору завдання, а деякого його фрагмента, що визначається симетрією завдання. евристичні методи засновані на моделюванні евристик - якісно-ситуаційних способів вирішення завдань. Евристики - це покрокові процедури, які за кінцеве число кроків забезпечують задовільне рішення задачі шляхом скорочення можливих варіантів при пошуку рішення і використання спрямованого перебору. Евристичні методи застосовуються для вирішення слабо структурованих, погано формалізованих задач, які не можуть бути описані числовий моделлю і характеризуються неточністю, неповнотою, неоднозначністю, неясністю інформації. Їх застосування також доцільно при жорстких ресурсних обмежень (дії в екстремальних або невідомих ситуаціях). Евристичний пошук включає системний аналіз завдання; виявлення обмежень, що впливають на результат (як зовнішніх, так і внутрішніх); аналіз можливості отримання результату простими засобами; визначення особливостей, обмежень і "вузьких місць", що вимагають використання додаткових коштів, і шляхів їх зменшення; моделювання задачі і можливих ситуацій для отримання найкращого рішення. Евристичний пошук базується на використанні ряду загальних підходів, застосовуваних людиною в процесі вирішення завдань при генеруванні варіантів рішень, їх порівнянні та виборі оптимального рішення. метод аналогії (Прецеденту) є найбільш загальним і може передбачати аналогію в цілях і критеріях, структуру та функції, умови функціонування, в результатах і їх оцінці, способах опису і моделях. метод спрощення застосовується, коли пряма аналогія утруднена через складність проблеми і полягає в знятті низки умов і обмежень, підвищення "симетрії" завдання. метод агрегування (Асоціації, занурення) доповнює попередній і передбачає застосування концептуального апарату вищого рівня, що дозволяє розглядати решаемую завдання як частина більш загальної (такий підхід характерний для вирішення так званих некоректних задач).

Основні методи пошуку рішення можна розділити на три групи. Першу групу складають стратегії пошуку по станам. Вихідна інформація може надаватися у вигляді простору ситуацій, що описується як стан системи та навколишнього середовища. Алгоритм пошуку полягає в пошуку шляху  , Що веде з початкового стану в одне з кінцевих (цільових станів)  . До цієї групи належать методи пошуку "в ширину", пошуку "в глибину",  -метод, метод гілок і меж, метод найкоротшого шляху, методи прямого і зворотного пошуку, а також градієнтні методи, наприклад, метод мінімальної вартості, метод динамічного програмування, метод векторної оптимізації, інтерактивні ЧС-методи.

Другу групу складають стратегії пошуку за завданнями. Вихідна інформація може надаватися як завдання s і безліч елементів рішення (підзадач)  , де j - Число рівнів рішення; i - Число елементів на j-му рівні. Алгоритм пошуку полягає в зведенні вихідної задачі до більш простим завданням, поки не будуть отримані елементарні завдання  . До цієї групи належать метод ключових операторів, метод загального решателя завдань і інші.

Третю групу складають методи, які використовують логічний висновок. Вихідна інформація може надаватися у вигляді опису станів в рамках деякої формальної системи, що включає алфавіт, аксіоми і правила виводу. Шляхом логічного висновку перевіряється, чи можна отримати кінцевий стан  з початкового стану  . До цієї групи належать дедуктивний метод, метод продукцій і ряд інших.

Розроблено різні модифікації методів пошуку з метою підвищення їх ефективності, а також комплексні цільові стратегії пошуку загального характеру, що моделюють процес міркування людини. Розглянуті схеми допускають узагальнення на нечіткий випадок шляхом об'єднання стратегій пошуку по станам і за завданнями, що підвищує гнучкість стратегії пошуку в різній інформаційному середовищі. Огляд цих методів можна знайти, наприклад, в [12].

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

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

Розглянемо приклад. Є схема автотранспортних перевезень між пунктами, представлена ??у вигляді графа, де пункти пронумеровані цифрами від 1 до 10 (рис.4). Потрібно знайти дерево, яке має мінімальну суму відстаней. Як оціночної функції використана вартість перевезення, пропорційна відстані (на графі вказані відстані в кілометрах).


 Рис.4. Граф системи автотранспортних перевезень

Для вирішення завдання розташуємо ребра-шляху в порядку зростання вартості. Маємо 1-3, 6-7, 5-6, 5-8, 9-10, 3-4, 7-10, 1-4, 4-7, 2-3, 3-6, 6-9, 8 -9, 1-2, 2-5, 2-6, 3-8. Алгоритм працює наступним чином. Починаючи з найменшого шляху, включаємо послідовно ребра, що мають меншу вартість з решти і не утворюють циклу з вже включеними ребрами. Отримуємо рішення 1-3, 6-7, 5-6, 5-8, 9-10, 3-4 і 7-10. Наступне за вартістю ребро 1-4 виключається, так як воно утворює цикл з уже включеними ребрами 1-3 і 3-4. Далі додаються ребра 4-7 і 2-3. Видно, що всі вершини досягнуті і дерево мінімальної вартості побудовано. Цей же метод можна застосовувати і при іншій інтерпретації величин і відносин між ними, наприклад аналогічно можна розглянути схему телефонних з'єднань, каналів зв'язку і т.п.

З евристичних методів розглянемо генетичний алгоритм, який моделюють закони розвитку живих систем: відбір найбільш пристосованого, успадкування корисних ознак і мінливість. Цей алгоритм був запропонований Дж. Холландом в його теорії адаптації і складається з наступних кроків:

- Випадковим чином створити початкову популяцію з N об'єктів (структур, варіантів вирішення і т.п.);

- Обчислити для кожного об'єкта показник його роботи. Якщо їх середнє значення досить високе, то перервати обчислення і вважати ці об'єкти підсумковим результатом;

- Для кожного об'єкта підрахувати ймовірність його вибору

;

- Застосовуючи генетичні оператори, створити таку популяцію об'єктів відповідно до обчисленої ймовірністю вибору;

- Повторити процедуру, починаючи з другого кроку.

Як генетичних операторів використовуються кроссинговер (перехрещення, перехід), зміна (мутація) і перестановка (інверсія). Оператор кросинговеру (перехрещення) є основним для створення нових структур. Він бере дві структури, випадковим чином вибирає точку розриву (місце поділу компонент) на цих структурах і змінює місцями послідовності компонент, що знаходяться праворуч від точки розриву. Наприклад, якщо дві структури и  перехрещуються між другою і третьою позиціями, то новими структурами будуть и  . Оператор кроссинговера працює з наявними в поточній момент структурними популяціями. Для обліку та внесення нової інформації в наявну популяцію використовується оператор мутації, який довільним чином змінює одну або кілька компонент обраної структури. Вірогідність його застосування дуже мала, і його наявність забезпечує досяжність всіх точок в просторі пошуку. Оператор інверсії змінює характер зв'язку між компонентами структури. Він бере одну структуру, випадковим чином вибирає на ній дві точки розриву і має в своєму розпорядженні в зворотному порядку елементи, що знаходяться між цими точками. Наприклад, інверсія структури з точками розриву між першим і другим і між третім і четвертим елементами дає нову структуру  . Оператор мутації не впливає на вибір структур і застосовується, коли не вдається побудувати хорошу популяцію. Оператор кроссинговера ефективно впливає на структури, що містять велику кількість елементів, оператор мутації навпаки більш ефективний для малих структур.

Розглянемо як приклад, що ілюструє дію генетичного алгоритму, завдання синтезу. Нехай потрібно розробити нову перспективну модель, наприклад автомобіль підвищеної прохідності. Модель конструюється з, приблизно, N = 1000 елементів, тобто безліч різнотипних елементів конструктора складається з 1000 одиниць. Кожен варіант оцінюється по n критеріям, наприклад, n @ 100. Загальна база знань про предметну область нараховує близько 10000 варіантів, які можуть відрізнятися числом і складом елементів. Будемо вважати, що критерії попередньо ранжовані за важливістю, причому найважливішими є функціональні критерії (група 1), потім йдуть техніко-економічні критерії (група 2), ергономічні (група 3) і спеціальні (група 4). Усередині груп попереднє ранжирування не проводиться. Ці ж групи критеріїв застосовуються і для оцінки окремих елементів конструктора. Таким чином, кожен варіант (і елемент) представлений впорядкованим набором критеріїв (показників) < K1, K2, ..., Kn >, Де n @ 100. У цьому наборі можуть бути пропуски (нульові позиції), тобто не обов'язково все критерії використовуються для оцінки всіх варіантів (елементів). Приймемо, що вага кожного варіанта (елемента) визначається відношенням числа критеріїв з максимальним значенням до загальної кількості критеріїв. Елементи конструктора можуть варіюватися (додаватися і віддалятися). Потрібно визначити найкраще рішення. Звичайно, таке завдання може бути вирішена методом перебору, проте це потребує великих витрат часу. Крім того, якщо врахувати, що безліч елементів конструктора може поповнюватися, то трудомісткість завдання ще більш зростає. Вибір рішення залежить також від відповідності (адекватності) умов завдання застосовується методом вибору. Впливає на результат співвідношення ваг критеріїв і поповнення безлічі альтернатив (елементів).

Застосуємо для пошуку рішення генетичний алгоритм. Необхідно визначити конкретний механізм відбору найкращого, а також способи накопичення корисних ознак стосовно до розв'язуваної задачі. Правила гри тут задає ЛПР, встановлюючи пріоритети, що визначають необхідність застосування генетичних операцій кросинговеру, зміни і перестановки. Зробимо пояснення щодо цих операцій.

Операція кросинговеру в основному буде застосовуватися при відборі варіантів. Поряд з традиційним перехрещуванням доповнимо її операціями перетину і об'єднання множин-популяцій, як граничними випадками операції кросинговеру.

Операція перетину застосовується до двох варіантів неоднаковою розмірності, коли у одного з них відсутня частина елементів (неповна розмірність), причому заповнені позиції збігаються. Операція об'єднання застосовується, коли обидва варіанти мають неповну розмірність (частина позицій - нульові позиції), причому заповнені позиції доповнюють один одного.

Операція зміни в основному буде застосовуватися для відбору методів отримання рішення. Її використання пов'язане з непридатністю розглянутого методу і необхідністю його модифікації. Операція перестановки (інверсії) буде застосовуватися при зміні переваг ОПР в оцінці варіантів (елементів), наприклад, якщо критерій (елемент), що стоїть на першій позиції, перестав відігравати домінуючу роль і його потрібно замінити.

У цьому завданню, кажучи мовою біології, популяція складається з 10000 варіантів рішень, кожен з яких оцінюється по n критеріям, наприклад, n = 100. Насправді на елементному рівні доводиться вирішувати декілька завдань різної розмірності: на рівні підсистем N @ 10, на рівні складових підсистем - модулів N @ 100 і на рівні елементів N @ 1000, але в нашому випадку це не має значення.

Для відбору варіантів використовуємо метод Парето. Визначаються варіанти, які мають максимальні оцінки хоча б за одним критерієм. Потім вони порівнюються між собою. Варіанти, які не можна порівняти один з одним, залишаються, інші відкидаються. Утворюється нова популяція з рештою варіантами (безліч 1). Це безліч поповнюється за рахунок операцій кросинговеру і зміни, що застосовуються до елементів структури варіантів. Доповнене безліч приймається за вихідне, і з його варіантів виділяється безліч Парето (безліч 2). Після цього порівнюються варіанти множин 1 і 2. Якщо можливо скорочення то воно виконується, і варіанти, що залишилися утворюють нове безліч 3. Воно знову поповнюється, і процедура повторюється до тих пір, поки не перестане поліпшуватися (розширюватися) безліч Парето. Для вибору найкращого рішення необхідно до отриманого безлічі Парето застосувати методи першої групи, наприклад метод згортки, метод головного критерію, метод граничних критеріїв, метод відстані і т.п.

Для відбору методів до популяції, елементами якої є різновиди методів, застосовується генетичний алгоритм. Метод вважається придатним, якщо його інформаційні запити IM соответствуютусловіям завдання I0, Тобто IM I I0. Виділяються елементи методу і елементи умов завдання. У кожного методу є особливі запити (умови застосовності), які повинні міститися в умовах завдання. Операція кросинговеру при відборі методів мало придатна, хоча і може використовуватися для отримання комбінацій методів. Так як «популяція» методів нечисленна (кілька десятків методів), то основний для їх трансформації і вибору є операція зміни (мутації), яка застосовується, якщо не виконані інформаційні запити методу. Тоді цей метод відкидається (трансформується) і замінюється іншим, поки умови застосовності якогось методу не співпадуть з умовами завдання. При цьому метод представляється у вигляді сукупності елементів, що становлять інформаційний запит методу (умови застосовності). Якщо є багато методів, для яких виконані умови застосовності, то досліджується структура методів, і вони трансформуються за допомогою операцій зміни і кросинговеру. Визначається перетин методів за елементами інформаційного запиту. Ті умови, які є загальними для методів, утворюють типові елементи (ядро) запиту. Ядро запиту перевіряється на відповідність умовам завдання. Якщо відповідність відсутня, то застосовується операція зміни і відбувається їх заміна іншими. Методи ранжуються за їх відповідності умовам завдання, точніше, по числу особливих умов їх застосування (за типовими елементами запиту). Наприклад, для методу адитивної згортки важливість критеріїв повинна плавно спадати, для застосування методу головного критерію один з критеріїв повинен бути значно важливіше інших, для методу граничних критеріїв повинні бути задані порогові значення критеріїв, для методу відстані повинно бути відомо «ідеальне» рішення і т. п. Попереднє ранжування методів здійснює ОПР по ряду критеріїв, які враховують переваги ОПР, ступінь відповідності умовам завдання (інформаційний запит), точність, складність, надійність, час і т.п. (Загальне число критеріїв n @ 10). Вага методу визначається відношенням числа критеріїв з максимальним (найкращим) значенням до загальної кількості критеріїв при інших рівних умовах, тобто при відповідності інформаційного запиту методу умов завдання (цей критерій є основним). Решта процедура вибору кращого методу здійснюється аналогічно відбору варіантів, викладеному вище. Для підвищення достовірності розрахунків часто доцільно застосовувати кілька методів з близькими оцінками, тому поряд з кросинговером, зміною та перестановкою слід використовувати операцію об'єднання, яка дозволяє отримувати комбіновані методи вибору варіантів. Про використання операції перетину було сказано вище.

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




 проектування систем |  Моральні (етичні, моральні) проблеми проектування |  Формування загального уявлення системи |  Формування детального представлення системи |  Класифікація видів моделювання систем |  Моделювання поведінки систем |  Принципи та підходи до побудови математичних моделей |  Етапи побудови математичної моделі |  Класифікація задач прийняття рішень. |  Моделі прийняття рішень |

© um.co.ua - учбові матеріали та реферати