Евристичне програмування

Міністерство  освіти та науки України

Національний  університет “Львівська політехніка”

Інститут  комп’ютерних наук та інформаційних  технологій

Кафедра інформаційних систем і мереж 
 

КУРСОВА РОБОТА

З КУРСУ:

“СИСТЕМИ  ШТУЧНОГО ІНТЕЛЕКТУ”

НА ТЕМУ:

“ЕВРИСТИЧНЕ ПРОГРАМУВАННЯ”

Львів-2008

Зміст

Вступ......................................................................................................................3

Теоретична  частина..............................................................................................5

     І. Строгі та евристичні методи.......................................................................5

       Недостатність строгих методів  при рішенні широкого кола  задач,                         які висуває практика.............................................................................................5

       Евристичні методи, евристичне програмування.........................................6

       Деякі проблеми теорії евристичних  рішень................................................7

       Основні підходи до теорії  евристичних рішень..........................................9

       Пряма та оборотна задачі евристичного  програмування..........................11

    ІІ. Деякі психологічні, логічно-математичні та технічні аспекти теорії евристичних рішень.............................................................................................13

       Операційні визначення як основа  опису інформаційних процесів, що  проходять в головному мозку.............................................................................14

       Інформаційний підхід, його сутність  та особливості................................14

       Метод строгих виводів і дві  експериментальні методики........................15

       Мова мозку не є мовою математики...........................................................16

       Строгі та евристичні методи, подібність та відмінність...........................16

       Роль логіки і математики в  теорії евристичних рішень та  евристичному програмуванні......................................................................................................18

       Множина представлення інформаційних  моделей як технічна основа  евристичного програмування.............................................................................19

       Евристичні програми як моделі  поведінки складних систем...................20

Висновки...............................................................................................................23

Список  літератури................................................................................................24 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                                           Вступ

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

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

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

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

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

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

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

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

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

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

Теоретична  частина 

Строгі  та евристичні методи 

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

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

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

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

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

Евристичні  методи, евристичне програмування 

Необхідно розробити якісно нові методи рішення  задач за допомогою ЕОМ шляхом моделювання окремих сторін процесу  творчого мислення людини, методів, що забезпечують ефективне рішення  особливо складних задач, особливо, в  умовах неповної, недостатньої поточної інформації. Такі задачі виникають в економіці, медицині, в дослідженнях космосу та інших галузях людських знань – всюди, де ми маємо справу з функціонуванням систем, що залежать від багатьох змінних. Методи рішення таких задач в умовах, коли через складність або недостатності інформації неможливо точно окреслити границі їх застосування та оцінити допущені помилки, називається евристичними (від грецької heurisko – знаходжу).

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

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

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

Найвища точність досягається саме евристичними методами. Це пояснюється тим, що точність залежить не тільки від досконалості математичного апарату, але й від вибору критеріїв якості, а також від “засипки”, для якої він застосовується. Евристики, які застосовуються до вибору критеріїв та покращення багатьох вихідних та проміжних даних, виявляються ціннішими у покращенні точності, ніж евристики, що застосовуються  до подальшого покращення математичного апарату, де нема само відборів корисної інформації. Точність евристичних методів виявляється набагато вищою за точність найдосконаліших та загальних математичних методів, що використовують специфічні (детерміністичні) підходи, оскільки вони засновані на само відборах корисної інформації за евристичними критеріями.

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

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

Розглянемо  загальну структуру процесу рішення, яке робить людина. Як і Л. Дж. Фогель, розглянемо три типи рішення: дедуктивні, абдуктивні та індуктивні. 
 

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

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

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

Деякі проблеми теорії евристичних рішень 

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

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

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

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

Важливе значення у створенні теорії евристичних  рішень представляє дослідження елементарних інформаційних процесів на різних рівнях. Під дослідженням елементарних інформаційних процесів зазвичай розуміють “факторизацію, подрібнення, програмування процесу мислення”, а головним завданням дослідження є виявлення правил об’єднання цих елементарних інформаційних процесів у складні програми. Ці дослідження походять із припущення про можливість вивчення роботи мозку із різним ступенем детальності, що відповідає опису інформаційних процесів на різних рівнях. Розглядаючи мозок як самоорганізаційну систему і вважаючи, що в його основі лежить ієрархія підлеглих алгоритмів, виділяють три рівні: нижній – рівень систем умовних і безумовних рефлексів; Середній – рівень системи правил процесу навчання; вищий – рівень, який формує та корегує попередній рівень. Така ієрархія алгоритмів дозволяє виділяти правила переробки інформації, які забезпечують формування цілісної поведінки живого організму при зміні оточення. При більш детальному розгляді зовнішнього середовища та його зв’язків з живим організмом можна побудувати формальну модель евристичної діяльності – теорію пошуку в абстрактному лабіринті, постановка проблеми відбору достовірної та несуперечливої інформації, що безпосередньо пов’язана із ціллю. При цьому розглядаються не тільки в процесі, що відбуваються в мозку, але й ті зміни, які проходять у зовнішньому середовищі в результаті активних дій живого організму (прямий та оборотній зв’язок). Такий підхід дозволяє моделювати окремі аспекти мислення при рішенні конкретних задач, виявляти нові закономірності вищої нервової діяльності, знаходити методи формування систем підцілей при досягненні основної цілі, здійснювати ефективний відбір необхідної інформації в процесі рішення тої чи іншої задачі.

Частково, в результаті спеціальних експериментів (А. Ньюелл, Дж. Шоу, Г. Саймон) зроблена спроба виявити ряд правил переробки інформації, які здійснюються мозком. На основі цих правил створена евристична програма GPS (General Problem Solver – універсальний вирішувач проблем). Дослідження цієї програми на прикладах рішення деяких конкретних задач (наприклад, задач математичної логіки) показує, що вона виробляє рішення, які є досить близькими до тих, які в аналогічній ситуації приймає людина.

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

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

Неодноразово  вказувалося, що “область евристики  не зовсім чітко окреслена та не зовсім чітко класифікується як область, яка належить тій чи іншій дисципліні – філософії, логіці, психології, а в наші дні – кібернетиці”. Створення теорії евристичних рішень як робочого апарату для широкого кола особливо складних задач немислимо без рішення комплексу проблем, пов’язаних із вивченням людського мислення. 
 

Основні підходи до теорії евристичних рішень 
 

Теорія  евристичних рішень ставить завдання застосування ЕОМ для моделювання  психічних функцій людини; при  цьому головним є завдання моделювання  таких компонентів сприйняття, мислення та поведінки, як минулий досвід, інтуїція, аналіз ситуації та інше, іншими словами, тих факторів, які пов’язані з процесами цілеспрямованого продуктивного мислення і які на даний час не піддаються строгій формалізації.

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

Є й  інший підхід до моделювання психічних  функцій мозку. Він пов’язаний з  виявленням механізмів переробки інформації, що формується у дитини до періоду завершення її зрілості (перехідний вік у 7 – 8 років), і їх переклад на мову програм ЕОМ, що само організовуються та самонавчаються.

Таким чином, є два підходи до виявлення  механізмів переробки інформації, на основі яких здійснюється розробка теорії евристичних рішень та створення евристичних програм:

• виявлення початкових механізмів, що формуються у дитини в період завершення її розвитку;
• виявлення сформованих механізмів функціонування дорослої людини в процесі її конкретної продуктивної діяльності.

Основна ідея першого підходу будується  на базі наступних широко розповсюджених положень. Поведінка людини визначається:

А) спадковістю, від якої залежить побудова організму  та особливості нервової системи;

Б) подіями  її життя, які відбиваються в її організмі різними способами;

В) навколишнім  світом, з якою вона взаємодіє.

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

Такими  початковими механізмами є виявлення подібності та відмінності, цілеспрямований пошук.

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

Другий  підхід пов’язаний з вивченням діяльності сформованої людини в тій чи іншій  ситуації.

Обидва  підходи не виключають, а навпаки, збагачують один одного. 
 
 
 
 
 
 

Пряма та оборотна задачі евристичного програмування 

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

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

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

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

Обернена  задача в повному смислі протилежна: надати результатам переробки інформації визначеної форми (наприклад, форми координованих фізичних дій), конкретизуючи та інтерпретуючи отримані результати.

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

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