Штучний інтелект у системах проектування та планування

9.1. Методи та засоби відображення розв’язків оптимізаційних задач

Метод повного перебирання варіантів. Для цього методу типовою є загальноінтелектуальна процедура: якщо інтелектуальна система потрапляє в нову ситуацію, вона намагається звести планування своїх цілеспрямованих дій до оптимізаційної задачі ― визначення множини припустимих розв’язків і цільової функції і якщо це вдається, повним перебиранням отримується оптимальний розв’язок.

Означення 9.1. Метод повного перебирання — це універсальний метод гарантованого розв’язання оптимізаційних задач за умови скінченності множини припустимих розв’язків (ситуація, характерна для дискретного програмування) і існування ефективного алгоритму породження будь-якого елементу з та обчислення на цьому елементі цільової функції

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

Означення 9.2. Евристичним пошуком називають процедуру систематизованого перебирання на основі послідовного аналізу можливих варіантів та оцінки їх наслідків [21] з такою схемою алгоритмічних кроків:

· вибрати певну дію з області можливих;

· здійснити дію; це приведе до зміни ситуації;

· оцінити нову ситуацію;

· якщо досягнуто успіху ― кінець; якщо ні ― почати з першого кроку.

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

Стратегії організації пошуку вершин дерева перебирання. Найпоширенішими стратегіями організації пошуку необхідної вершини на дереві перебирання і шляху до неї є пошук у ширину і пошук у глибину.

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

Ця стратегія для наведеного прикладу 9.1 для булевого виразу з ілюструється рис. 9.2.

Рис. 9.2. Стратегія з процедурою пошуку в ширину

Означення 9.4.Стратегією пошуку у глибину називається організація такої процедури, якою передбачається першочерговий аналіз породжень тих вершин, що були проаналізовані останніми, тобто послідовну перевірку всіх альтернатив одна за одною, причому аналіз деякої альтернативи завершується тільки тоді, коли точно встановлюється, що вона приводить до успіху. У разі невдачі відбувається повернення на крок і розглядаються інші альтернативи.

Ілюстрацією стратегії пошуку у глибину для умов того ж прикладу слугує аналогічне дерево перебирання з наведеною пунктирними стрілками послідовністю процедурного крокування (рис. 9.3).

Рис. 9.3. Стратегія з процедурою пошуку у глибину

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

Простори станів і задач. Методики реалізації цілеспрямованих дій при організації пошуків розв’язків поділяються на два класи: планування в просторі станів і планування в просторі задач [42].

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

Означення 9.5. Граф станів задачі ― це орієнтований граф, вершини якого відповідають можливим станам об’єкта дослідження, а дуги ― методам переходу від стану до стану.

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

Фактично задача зводиться до пошуку в графі, основними машинними способами завдання якого є матриця інцидентності, матриця суміжності та списки суміжності.

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

Для планування у просторі задач традиційно використовується формалізм І–АБО-графів.

Означення 9.6. І–АБО-графом називається орієнтований граф, вершини якого відповідають задачам, а дуги ― відношенням між задачами, причому між дугами вводяться відношення «І» та «АБО».

Будь-який І–АБО-граф можна звести до певної нормальної форми, в якій з будь-якої вершини виходять або тільки «І»-дуги, або тільки «АБО»-дуги.

Означення 9.7. «І»-вершиною називається вершина, з якої виходять лише «І»-дуги; «АБО»-вершиною є вершина із виключно «АБО»-дугами.

Означення 9.8.Початковою вершиною І–АБО-графа є вершина, з якої розпочинаються цілеспрямовані дії щодо розв’язання задачі.

Означення 9.9. Вершина є розв’язною, якщо задача, що відповідає цій вершині, має розв’язок.

З урахуванням означення 9.9 метою пошуку, що реалізується на І–АБО-графі, є встановлення факту розв’язуваності початкової вершини.

Оскільки процедурно розв’язання задачі на І–АБО-графах нагадує механізм виведення продукційної системи, можна стверджувати, що фактично такі графи є фрагментами послідовностей виведення з продукційних систем.

На завершення можна навести таке рекурсивне правило для встановлення того, є дана вершина розв’язною чи ні:

заключні вершини, які відповідають елементарним задачам, розв’язні;
«І»-вершина розв’язна, якщо всі її породження є розв’язними;

· «АБО»-вершина розв’язна, якщо хоча 6 одне її породження є розв’язним.

Метод динамічного програмування. Цей метод ґрунтується на схемі послідовного перебирання варіантів з використанням процедур, які на основі побічних оцінок відхиляють всі ті допустимі розв’язки, серед яких не може бути оптимального, тобто відбувається стиснення множини конкурентоспроможних варіантів до одного або декількох обмежених, які й порівнюються.

Означення 9.10. Динамічне програмування ― це такий алгоритмічний метод, який доцільно використовувати, коли розв’язання задачі можна звести до певної послідовності розв’язків.

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

Тоді під динамічним програмуванням щерозуміють такий спосіб побудови алгоритмів, який можна застосувати тоді, коли розв’язання загальної задачі можна розбити на розв’язок її підзадач і отримувати розв’язок наступної задачі як суперпозицію попередніх розв’язків.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
При їх підпорядкованому функціонуванні	\|	Методи пошуку розв’язання на прикладах задач планування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.029 сек.