понедельник, 2 августа 2010 г.

Мягкие вычисления – Часть 1

Мягкие вычисления


Лотфи Аскер Заде родился 4 февраля 1921 года. Математик, основатель теории нечётких множеств и нечёткой логики, профессор Калифорнийского университета (Беркли), чьи работы легли в основу мягких вычислений в их сегодняшнем представлении[SC Wiki]. Это работы в области нечетких множеств (1965), нечеткой логики (1973), статьи по анализу сложных систем и процессам принятия решений (1973), работы по нечетким алгоритмам (1976), статьи по теории возможностей и мягкому анализу данных (1981)[BISC].
Термин "мягкие вычисления" введен Лотфи Заде в 1994 году.

Мягкие вычисления не являются отдельной методологией. Это понятие объединяет такие области как нечеткая логика, нейровычисления, эволюционные вычисления и вероятностные вычисления с более поздним включением хаотических систем, сетей доверия и разделов теории обучения.
clip_image002
Каждая из составляющих областей имеет много возможностей для ее использования в рамках мягких вычислений. Нечеткая логика лежит в основе методов работы с неточностью, зернистой структурой (гранулированной информацией), приближенных рассуждений и вычислений со словами (computing with words). Нейровычисления отражают способность к обучению, адаптации и идентификации. В случае эволюционных вычислений, речь идет о возможности систематизировать случайный поиск и достигать оптимального значения характеристик. Вероятностные вычисления обеспечивают базу для управления неопределенностью и проведения рассуждений, исходящих из свидетельств[Zadeh].
Системы, в которых нечеткая логика, нейровычисления, генетические алгоритмы и вероятностные вычисления используются в некоторой комбинации, называются гибридными системами. Наиболее известными системами этого типа являются так называемые нейро-нечеткие системы. В настоящее время появляются нечетко-генетические системы, нейро-генетические системы и нейро-нечетко-генетические системы.

Нечеткая логика

Математическая теория нечетких множеств (fuzzy sets) и нечеткая логика (fuzzy logic) являются обобщениями классической теории множеств и классической формальной логики. Нечеткая логика опирается на теорию нечетких множеств. Теория нечетких множеств - раздел прикладной математики, посвященный методам анализа неопределенных данных, в которых описание неопределенностей реальных явлений и процессов проводится с помощью понятия о множествах, не имеющих четких границ. Основной причиной появления новой теории стало наличие нечетких и приближенных рассуждений при описании человеком процессов, систем, объектов.
Лотфи Заде опубликовал основополагающую работу по теории нечётких множеств в 1965, в которой изложил математический аппарат теории нечётких множеств.
Как пишет в своей статье «Роль мягких вычислений и нечеткой логики в понимании, конструировании и развитии информационных интеллектуальных систем» Л.Заде [Zadeh], в основе методов работы с нечеткими понятиями лежит одна важнейшая особенность. Речь идет о гранулировании информации (information granulation) и его роли в человеческих рассуждениях, взаимодействиях и формировании концепций. Гранулирование информации играет существенную роль в оперировании нечеткими понятиями и, в частности, в рассуждениях и вычислениях со словами, а не с числами.
Понятие гранулирования информации послужило мотивировкой для написания большинства ранних работ Лотфи Заде по нечетким множествам и нечеткой логике. По существу, все человеческие понятия являются нечеткими, так как они получаются в результате группировки (clumping) точек или объектов, объединяемых по сходству. Тогда нечеткость подобных групп (clumps) есть прямое следствие нечеткости понятия сходства.
В естественном языке слова играют роль меток гранул. В этой ипостаси они служат для сжатия данных. Сжатие данных с помощью слов является ключевым аспектом человеческих рассуждений и формирования понятий.
Вычисления со словами есть раздел нечеткой логики. В ближайшие годы вычисления со словами должны превратиться в важнейшее научное направление, обеспечивающее эффективную работу с всеобъемлющей неточностью и неопределенностью реального мира. В этой перспективе исходной моделью для вычислений со словами, нечеткой логики и мягких вычислений является человеческий разум.
В нечеткой логике гранулирование информации лежит в основе понятий лингвистической переменной и нечетких правил типа «если, …, то». Эти понятия были формально введены в 1973 году в статье “Основы нового подхода к анализу сложных систем и процессов принятия решений” Лотфи Заде [Zadeh 1973]. В 1973 он предложил теорию нечёткой логики, а также теорию вербальных вычислений и представлений (computing with words and perceptions).Сегодня почти все приложения нечеткой логики используют эти понятия. Однако изначально введение этих понятий было встречено со скептицизмом и враждебностью.
Важность нечетких правил связана с тем, что такие правила близки человеческой интуиции. Гранулирование информации лежит в центре человеческих рассуждений, взаимодействий и формирования понятий. В рамках нечеткой логики оно играет ключевую роль в вычислениях со словами. Вычисления со словами можно рассматривать как один из наиболее важных результатов нечеткой логики.
Вычисления со словами должны обеспечить возможность вывода из множества исходных данных, в котором информация выражается в виде предложений на естественном языке. Это откроет пути для формулировки и решения многих важных проблем, в которых имеющаяся информация не является достаточно точной для использования традиционных методов. В настоящее время проблема состоит в разработке систем вычислений со словами, способных справиться с предложениями очень большой сложности, которые выражают знания о реальном мире.

Этапы развития нечеткой логики

Прежде чем нечеткий подход к моделированию сложных систем получил признание во всем мире, прошло не одно десятилетие с момента зарождения теории нечетких множеств. И на этом пути развития нечетких систем, по материалам статьи Н. Паклина [Fuzzu math], принято выделять три периода.
clip_image004
Первый период (конец 60-х–начало 70 гг.) характеризуется развитием теоретического аппарата нечетких множеств (Л. Заде, Э. Мамдани, Беллман).
Во втором периоде (70–80-е годы) появляются первые практические результаты в области нечеткого управления сложными техническими системами. Начиная с конца 70-х годов, методы теории нечетких множеств начинают применяться в экономике. В работе [Kofman] представлен широкий спектр возможных применений этой теории - от оценки эффективности инвестиций до кадровых решений и замен оборудования, приводятся соответствующие математические модели. Одновременно стало уделяться внимание вопросам построения экспертных систем, построенных на нечеткой логике, разработке нечетких контроллеров. Нечеткие экспертные системы для поддержки принятия решений находят широкое применение в медицине и экономике.
Наконец, в третьем периоде, который длится с конца 80-х годов и продолжается в настоящее время, появляются пакеты программ для построения нечетких экспертных систем, а области применения нечеткой логики заметно расширяются. Она применяется в автомобильной, аэрокосмической и транспортной промышленности, в области изделий бытовой техники, в сфере финансов, анализа и принятия управленческих решений и многих других.
Триумфальное шествие нечеткой логики по миру началось после доказательства в конце 80-ых Бартоломеем Коско знаменитой теоремы FAT (Fuzzy Approximation Theorem). В бизнесе и финансах нечеткая логика получила признание после того как в 1988 году экспертная система на основе нечетких правил для прогнозирования финансовых индикаторов единственная предсказала биржевой крах. И количество успешных фаззи-применений в настоящее время исчисляется тысячами.
Нечеткая логика с каждым годом привлекает все большее число исследователей из разных научных областей. В настоящее время нечеткой логикой во всем мире занимаются тысячи ученых и инженеров, по этой тематике опубликованы сотни книг, десятки тысяч статей, издается более десяти научных журналов по нечеткой логике и мягким вычислениям, механизмы нечеткой логики реализованы в сотнях прикладных систем: в стиральных машинах, видеокамерах, двигателях, системах управления метро и летательными аппаратами.
Прикладные результаты теории нечетких множеств не заставили себя ждать. Сегодня зарубежный рынок так называемых нечетких контроллеров (разновидность которых установлена даже в стиральных машинах широко рекламируемой марки LG) обладает емкостью в миллиарды долларов. Нечеткая логика, как модель человеческих мыслительных процессов, встроена в системы искусственного интеллекта и в автоматизированные средства поддержки принятия решений, в частности, в системы управления технологическими процессами.

Эволюционные вычисления

Эволюционные методы - это обобщенное название компьютерных алгоритмов, использующих математические модели механизмов естественной эволюции в качестве ключевых структурных элементов. Существуют множество разновидностей подобного рода алгоритмов, отличающихся использованием или не использованием конкретных механизмов, а также различиями трактовки этих механизмов и представлением индивидов.
Эволюционные методы работают не с отдельными особями (объектами), а с популяциями этих объектов. Каждый алгоритм вначале создает некоторым способом популяцию объектов. Дальнейший процесс представляет собой последовательность эпох или циклов. Внутри каждой эпохи все индивиды оцениваются, и в зависимости от оценки участвуют в размножении - создании новой популяции. Процесс эволюции останавливается когда построенная в данной эпохе новая популяция удовлетворяет критерию завершения.
clip_image006
Генетические алгоритмы предназначены для решения задач оптимизации. Примером подобной задачи может служить обучение нейросети, то есть подбора таких значений весов, при которых достигается минимальная ошибка. При этом в основе генетического алгоритма лежит метод случайного поиска. Основным недостатком случайного поиска является то, что нам неизвестно сколько понадобится времени для решения задачи. Для того, чтобы избежать таких расходов времени при решении задачи, применяются методы, проявившиеся в биологии. При этом используются методы открытые при изучении эволюции и происхождения видов. Как известно, в процессе эволюции выживают наиболее приспособленные особи. Это приводит к тому, что приспособленность популяции возрастает, позволяя ей лучше выживать в изменяющихся условиях.
Исходя из материалов статьи [GA Math] можно сказать, что в генетических алгоритмах каждый индивид кодируется сходным с ДНК методом - в виде строки из символов одного типа. Длина строки (ДНК) постоянна. Популяция из индивидов подвергается процессу эволюции с интенсивным использованием перекреста и мутаций.
Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом в Мичиганском университете [Holland]. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов.
Генетические алгоритмы нашли применение в оптимизации, искусственном интеллекте, инженерии и других областях. В основе ГА лежат принципы, заимствованные из биологии и генетики. Основная идея ГА состоит в создании популяции особей, каждая из которых представляется в виде хромосомы. Любая хромосома есть возможное решение рассматриваемой оптимизационной задачи. Для поиска лучших решений необходимо только значение целевой функции, или функции приспособленности. Значение функции приспособленности особи показывает, насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи. Хромосома состоит из конечного числа генов, представляя генотип объекта, т.е. совокупность его наследственных признаков. Процесс эволюционного поиска ведется только на уровне генотипа. К популяции применяются основные биологические операторы: скрещивания, мутации, инверсии и др. В процессе эволюции действует известный принцип "выживает сильнейший". Популяция постоянно обновляется при помощи генерации новых особей и уничтожения старых, и каждая новая популяция становится лучше и зависит только от предыдущей.
Фиксированная длина хромосомы и кодирование строк двоичным алфавитом преобладали в теории генетических алгоритмов с момента начала ее развития, когда были получены теоретические результаты о целесообразности использования именно двоичного алфавита. К тому же, реализация такого генетического алгоритма на ЭВМ была сравнительно легкой. Все же, небольшая группа исследователей шла по пути применения в генетических алгоритмов отличных от двоичных алфавитов для решения частных прикладных задач. Одной из таких задач является нахождение решений, представленных в форме вещественных чисел, что называется не иначе как "поисковая оптимизация в непрерывных пространствах". Возникла следующая идея: решение в хромосоме представлять напрямую в виде набора вещественных чисел. Естественно, что потребовались специальные реализации биологических операторов. Такой тип генетического алгоритма получил название непрерывного генетического алгоритма (real-coded GA), или генетического алгоритма с вещественным кодированием. В статье Николая Паклина [GA] рассматривается история и основные принципы непрерывных генетических алгоритмов.
Первоначально непрерывные гены стали использоваться в специфических приложениях (например, хемометрика, оптимальный подбор параметров операторов стандартных ГА и др.). Позднее они начинают применяться для решения других задач оптимизации в непрерывных пространствах (работы исследователей Wright, Davis, Michalewicz, Eshelman, Herrera в 1991-1995 гг). Поскольку до 1991 теоретических обоснований работы непрерывных генетических алгоритмов не существовало, использование этого нового подвида было спорным; ученые, знакомые с фундаментальной теорией эволюционных вычислений, в которой было доказано превосходство двоичного алфавита перед другими, критически воспринимали успехи real-coded алгоритмов. После того, как спустя некоторое время теоретическое обоснование появилось, непрерывные ГА полностью вытеснили двоичные хромосомы при поиске в непрерывных пространствах.

Комментариев нет:

Отправить комментарий