Определение искусственного интеллекта - файл n1.doc

Определение искусственного интеллекта
Скачать все файлы (373.5 kb.)

Доступные файлы (1):
n1.doc631kb.18.05.2010 11:25скачать

n1.doc

  1   2   3



СОДЕРЖАНИЕ
1.Определение искусственного интеллекта

2. История развития ИИ и основные авторы, которые занимались его разработкой.

3. Представление знаний.

4. Прикладные интеллектуальные системы.

4. 1. Алгоритм отжига, его применение в задачах оптимизации

4.2. Алгоритм муравья, естественная мотивация.

4.3. Применение генетического алгоритма в задачах оптимизации, теории игр.

5. Искусственная жизнь

6. Планирование решения задач.

6.1. Обзор технологий ЭС

6.2. ЭС основанные на правилах

6.3. Выбор задачи и процесса инженерии знаний

6.4. Концептуальные модели и их роль в приобретении знаний

6.5. Понятие – «планирование»

Определение искусственного интеллекта
Согласно толковому словарю, интеллект - способность к познанию, постижению чего-либо.

Психологи: интеллект - это то, что оценивается в интеллектуальных тестах.

Термин "Искусственный интеллект" появился в конце 60-х годов. В 1969 году I между народная объединенная конференция по ИИ узаконила эту метафору. У англоязычных ученых термин computer science не порождает побочных эмоций. У нас термин ИИ ассоциируется с протезом мозга. С первых шагов ИИ выделяют две основные цели исследований:

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

решения, важно лишь совпадение решений по результатам.

- бионическая. создание программ для ЭВМ, имитирующих процесс получения решения

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

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

умели делать. Новая технология использования ЭВМ просто необходима. С усложнением ЭВМ увеличился объем знаний, необходимых для общения с ней. Увеличился рост числа посредников между пользователем и машиной: аналитики, программисты (прикладные и системные), администраторы систем. Если так дальше будет продолжаться, то в будущем общество будет делиться на 2 части - программисты и непрограммисты.

Схема интеллектуального интерфейса:
┌──────────┐ ┌──────┐

│ДИАЛОГОВЫЙ├────────┤ БАЗА │

│ПРОЦЕССОР │ │ЗНАНИЙ│

└────┬─────┘ └──┬───┘

│ │

│ ┌───────────┐ │

└───┤ПЛАНИРОВЩИК├─┘

└───────────┘
Основные проблемы ИИ:

- представление знаний (модели);

- приобретение знаний (общение и восприятие);

- обработка знаний (планирование действий).

Является ли ИИ наукой?

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

смежные науки.

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

собой, специфичны. Это позволяет сделать вывод, что ИИ является самостоятельной наукой.

История развития ИИ и основные авторы,

которые занимались его разработкой
Рождение компьютера, 1940-е

Эра разумных машин наступила вскоре после появления первых компьютеров. Большинство компьютеров были созданы для того, чтобы взломать немецкие шифры во время Второй мировой войны. В 1940 г. был построен первый рабочий компьютер на электромагнитных реле - Робинсон (Robinson). Он предназначался для расшифровки военных переговоров немцев, которые были зашифрованы с помощью машины Энигма (Enigma). Робинсон назван в честь создателя мультипликационных трюков, Хита Робинсона (Heath Robinson). Три года спустя вакуумные трубки заменили электромагнитные реле, что позволило построить Колосс (Colossus). Этот более быстрый компьютер был создан для взлома новых усовершенствованных кодов. В 1945 г. в Университете Пенсильвании доктор Джон В. Мохли (Dr. John W. Mauchly) и Д. П. Экерт Q. P. Eckert, Jr.) разработали более известный компьютер, ENIAC. Его задачей было рассчитать баллистические таблицы времен Второй мировой войны. Нейронные сети с обратной связью построены Вальтером Питтсом (Walter Pitts) и Уорреном МакКуллочем (Warren McCulloch) в 1945 г., чтобы показать возможности их применения при расчетах. Эти ранние сети были электронными и весьма поспособствовали росту энтузиазма у создателей технологии. Примерно в то же время Норберт Винер (Norbert Wiener) создал область кибернетики, которая включала математическую теорию обратной связи для биологических и инженерных систем. Важным аспектом данного открытия стала концепция о том, что разум - это процесс получения и обработки информации для достижения определенной цели.

Наконец в 1949 г. Дональд Хеббс (Donald Hebbs) открыл способ создания самообучающихся искусственных нейронных сетей. Этот процесс (получивший на-

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

Рождение ИИ, 1950-е

1950-е отмечены в истории как годы рождения ИИ. Алан Тьюринг (Alan Turing) предложил специальный тест в качестве способа распознать разумность машины. В этом тесте один или несколько людей должны задавать вопросы двум тайным собеседникам и на основании ответов определять, кто из них машина, а кто человек. Если не удавалось раскрыть машину, которая маскировалась под человека, предполагалось, что машина разумна. В 1950-е гг. ИИ по своей природе был в первую очередь символичным. Именно в то время сделано открытие, что компьютеры могут управлять символами так же, как и числовыми данными. Это привело к разработке таких программ, как предназначавшаяся для доказательства теорем авторы – Ньюэлл Симон и Шоу. Наверное, самым крупным открытием в программной области в 1950-е было создание Артуром Самуэлем программы для игры в шашки, которая постепенно научилась обыгрывать своего создателя.

В 1950-е гг. были также разработаны два языка ИИ. Первый, язык IPL, был создан Ньюэллом, Симоном и Шоу для программы Logic Theorist. IPL являлся языком обработки списка данных и привел к созданию более известного языка LISP. LISP появился в конце 1950-х и вскоре заменил IPL, став основным языком приложений ИИ. Язык LISP был разработан в лабораториях Массачусетсткого технологического института (MIT). Его автором был Джон МакКарти, один из первых разработчиков ИИ. - Джон МакКарти представил концепцию ИИ как часть своего предложения для Дормутской конференции по проблемам ИИ. В 1956 г. разработчики ИИ встретились в Дормутском колледже, чтобы обсудить дальнейшее развитие разумных машин. В своем предложении Джон МакКарти написал:Задача заключается в том, чтобы работать на основе предположения, что любой аспект обучения или другой функции разума может быть описан так точно, чтобы машина смоглаего симулировать. Мы попытаемся определить, как сделать так, чтобы машины

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

задачи, которыми сейчас занимаются только люди, а также заниматься самобучением.

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

Подъем ИИ, 1960-е

В 1960-е гг. произошел скачок в развитии ИИ, вызванный прогрессом в компьютерных технологиях, а также увеличением количества разработок в данной области. Наверное, самым важным показателем того, что ИИ достиг приемлемого уровня, стало появление критиков. В 1960-е наиболее важным было представление знаний, так как сильный ИИ продолжал оставаться главной темой в разработках ИИ. В начале 1960-х Джон МакКарти основал лабораторию ИИ в Стэндфордском" университете. Сотрудники лаборатории, помимо прочего, создали робота Шейки, который мог перемещаться по искусственному миру и выполнять простые приказания. Разработки нейронных сетей процветали до конца 1960-х, ровно до тех пор, пока не была издана книга Мински и Паперта в которой авторы описали ограничения по использованию простых одноуровневых перцептронов, что привело к серьезному снижению инвестиций в исследования нейронных сетей более чем на декаду.

Спад исследований ИИ, 1970-е

1970-е гг. показали резкий спад интереса к ИИ после того, как исследователям не удалось выполнить нереальные обещания его успеха. Практическое применение ИИ было по-прежнему минимальным. Ситуация осложнялась тем, что в MIT, Стэнфорде и Карнеги Меллон возникли проблемы с финансированием исследований в области ИИ. Такое же препятствие ожидало и разработчиков в Великобритании. К счастью, исследования продолжались и не без успеха. Дуг Ленет в Стэндфордском университете создал программу «Автоматический математик» (AM) и позднее - EURISKQ что позволило открыть новые теории в математике. AM успешно повторил открытие теории чисел, но по причине

ограниченного количества кодировок в эвристике быстро достиг потолка своих возможностей. EURISKO, следующая разработка Ленета, был построен с учетом ограничений AM и мог определять свою эвристику, а также решать, что в ней является полезным, а что нет. Впервые нечеткая логика была применена на практике в начале 1970-х гг. Следует отметить, что Лотфи Заде (Lotfi Zadeh) создал саму концепцию еще в 1960-х. Нечеткая логика была использована в работе над паровым двигателем в колледже Королевы Марии (Queen Mary), что стало первым из многочисленных примеров применения нечеткой логики для управления процессами.

В 1970-х продолжалось создание языков для ИИ. Был разработан язык ПРОЛОГ (Prolog - Программирование логики). Язык ПРОЛОГ предназначался для разработки программ, которые управляли символами (а не выполняли числовые расчеты) и работал с правилами и фактами. Развитие ИИ для игр продолжилось в 1970-х. В Карнеги Меллон была создана программа для игры в триктрак. Она играла настолько хорошо, что смогла победить чемпиона мира по триктраку, Луиджи Вилла (Luigi Villa) из Италии. Это был первый случай победы компьютера над человеком в сложной игре.

Подъем и спад ИИ, 1980-е

1980-е гг. казались многообещающими для ИИ после того, как продажи аппаратных средств и программного обеспечения, связанного с ИИ, превысили 400 млн. долларов в 1986 г. Большую часть этого дохода принесли продажи экспертных систем на LISP и, соответственно, LISP-машин, которые развивались, становясь лучше и дешевле задач, например, диагностики электровоза. Также были идентифицированы ограничения в работе экспертных систем, поскольку их знания становились все больше и сложнее. Например, системный конфигуратор XCON компании Digital Equipment Corporation достиг предела в 10000 правил, и поддерживать его работу стало очень сложно. Нейронные сети в 1980-е гг. также переживали возрождение. Они нашли применение при решении ряда различных задач, таких как распознавание речи и возможность самообучения машин. К сожалению, 1980-е продемонстрировали как рост, так и спад интереса к ИИ. Основной причиной этого были сбои экспертных систем. Однако многие другие приложения ИИ были серьезно улучшены именно в 1980-е гг. Например, системы распознавания речи смогли наконец работать независимо от говорящего (то есть распознавать речь любого человека, а не только специально обученного диктора), а также выполнять распознавание в режиме реального, времени (позволяя человеку говорить обычно, а не делать остановки и паузы). Кроме того, значительно увеличился их словарный запас.

Постепенный прогресс ИИ, 1990-е и настоящее время

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

Важным событием в развитии компьютерных игр с использованием ИИ стало создание в 1997 г. суперкомпьютера для игры в шахматы Deep Blue (он был разработан в Карнеги Меллон). Эта машина смогла победить Гарри Каспарова, чемпиона мира по шахматам.

Другое интересное событие для развития ИИ в 1990-е гг. произошло в 60 млн. миль от Земли. Была создана система Deep Space I (DS1), которая могла тестировать технологии 12-ой степени риска, включая полет кометы и тестирование для будущих космических полетов. DS1 включала систему искусственного интеллекта под названием Remote Agent, которой на небольшое время предоставлялось управление космическим кораблем. Обычно такая работа исполнялась командой ученых посредством терминалов. Remote Agent продемонстрировала, что искусственная система способна управлять сложным космическим кораблем, позволяя ученым и экипажам кораблей сконцентрироваться на решении

других задач.
Представление знаний

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

Данные и знания. Основные определения.

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

Одинаковое число разрядов в машинных словах для команд и данных позволяет рассматривать их в ЭВМ в качестве одинаковых информационных единиц и выполнять операции над командами, как над данными. Содержимое памяти образует информационную базу.

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

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

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

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

Особенности знаний:

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

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

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

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

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

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

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

Модели представления знаний.

Существуют два типа методов представления знаний (ПЗ):

  1. Формальные модели ПЗ;

  2. Неформальные (семантические, реляционные) модели ПЗ.


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

Каждому из методов ПЗ соответствует свой способ описания знаний.

1Логические модели. В основе моделей такого типа лежит формальная система, задаваемая четверкой вида: M = . Множество T есть множество базовых элементов различной природы, например слов из некоторого ограниченного словаря, деталей детского конструктора, входящих в состав некоторого набора и т.п. Важно, что для множества T существует некоторый способ определения принадлежности или непринадлежности произвольного элемента к этому множеству.

2. Сетевые модели. В основе моделей этого типа лежит конструкция, названная ранее семантической сетью. Сетевые модели формально можно задать в виде H = . Здесь I есть множество информационных единиц; C1, C2, ..., Cn - множество типов связей между информационными единицами. Отображение Г задает между информационными единицами, входящими в I, связи из заданного набора типов связей.

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

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

4. Фреймовые модели. В отличие от моделей других типов во фреймовых моделях фиксируется жесткая структура информационных единиц, которая называется протофреймом.

Система ИИ в определенном смысле моделирует интеллектуальную деятельность человека и, в частности, - логику его рассуждений.


Прикладные интеллектуальные системы
Алгоритм отжига, его применение в задачах оптимизации.

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

Естественная мотивация

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

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

Алгоритм отжига очень прост и может быть разделен на пять этапов



Начальное решение

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

Оценка решения

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

Случайный поиск решения

Поиск решения начинается с копирования текущего решения в рабочее решение. Затем

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

Критерий допуска

На этом этапе алгоритма у нас имеется два решения. Первое - это наше оригинальное решение, которое называется текущим решением, а второе - найденное решение, которое именуется рабочим решением. С каждым решением связана определенная энергия, представляющая собой его эффективность (допустим, что чем ниже Энергия, тем более эффективно решение). Затем рабочее решение сравнивается с текущим решением. Если рабочее решение имеет меньшую энергию, чем текущее решение (то есть является более предпочтительным), то мы копируем рабочее решение в текущее решение и переходим к этапу снижения температуры. Однако если рабочее решение хуже, чем текущее решение, мы определяем критерий допуска, чтобы выяснить, что следует сделать с текущим рабочим решением. При высокой температуре (свыше 60 *С) плохие решения принимаются чаще, чем отбрасываются. Если энергия меньше, вероятность принятия решения выше. При снижении температуры вероятность принятия худшего решения также снижается. При этом более высокий уровень энергии также способствует уменьшению вероятности принятия худшего решения. При высоких температурах симулированное восстановление позволяет принимать худшие решения для того, чтобы произвести более полный поиск решений. При снижении температуры диапазон поиска также уменьшается, пока не достигается равенство при температуре 0°.

Снижение температуры

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

Повтор

При одной температуре выполняется несколько итераций. После завершения итераций температура будет понижена. Процесс продолжится, пока температура не достигнет нуля.
  1   2   3
Учебный текст
© perviydoc.ru
При копировании укажите ссылку.
обратиться к администрации