Задачи искусственного интеллекта 7 Тест по теме «История развития искусственного интеллекта» 9 (стр. 14 из 24)
Рис. 17. Островная модель генетического алгоритма
Изредка (например, каждые 5 поколений) процессы (или острова) будут обмениваться несколькими хорошими особями. Это называется миграция. Она позволяет островам обмениваться генетическим материалом.
Так как населенность островов обычно бывает невелика, подпопуляции будут склонны к преждевременной сходимости. Поэтому важно правильно установить частоту миграции. Чересчур частая миграция (или миграция слишком большого числа особей) приведет к смешению всех подпопуляций, и тогда островная модель будет несильно отличаться от обычного генетического алгоритма. Если же миграция будет слишком редкой, то она не сможет предотвратить преждевременного схождения подпопуляций.
Генетические алгоритмы стохастичны, поэтому при разных его запусках популяция может сходиться к разным решениям (хотя все они в некоторой степени «хорошие»). Островная модель позволяет запустить алгоритм сразу несколько раз и пытаться совмещать «достижения» разных островов для получения в одной из подпопуляций наилучшего решения.
Ячеистые генетические алгоритмы
Ячеистые генетические алгоритмы (Cellular Genetic Algorithms) - модель параллельных генетических алгоритмов. Пусть дано 2500 процессов, расположенных на сетке размером 50×50 ячеек, замкнутой, как показано на рисунке 18 (левая сторона замыкается с правой, верхняя с нижней, получается тор).
Каждый процесс может взаимодействовать только с четырьмя своими соседями (сверху, снизу, слева, справа). В каждой ячейке находится ровно одна особь. Каждый процесс будет выбирать лучшую особь среди своих соседей, скрещивать с ней особь из своей ячейки и одного полученного ребенка помещать в свою ячейку вместо родителя.
Рис. 18. Ячеистый генетический алгоритм
По мере работы такого алгоритма возникают эффекты, похожие на островную модель. Сначала все особи имеют случайную приспособленность (на рисунке она определяется по цвету). Спустя несколько поколений образуются небольшие области похожих особей с близкой приспособленностью. По мере работы алгоритма эти области растут и конкурируют между собой.
Тест по теме «Эволюционное моделирование»
1. Кто считается «отцом» генетических алгоритмов?
a) Д. Голдберг
b) Д. Холланд
c) К. Де Йонг
d) Нет правильного ответа
2. Какие методы относятся к направлению «Эволюционное моделирование»?
a) Метод группового учета аргументов
b) Нейронные сети
c) Генетические алгоритмы
d) Эволюционное программирование
e) Эвристическое программирование
3. Какие понятия относятся к генетическим алгоритмам?
a) особь
b) фенотип
c) ген
d) ДНК
e) нейрон
f) функция активации
4. Какие виды отбора в генетических алгоритмах существуют?
a) Дискретный отбор
b) Ранговый отбор
c) Поэтапный отбор
d) Дуэльный отбор
e) Турнирный отбор
f) Рулетка
5. Какие бывают операторы генетического алгоритма?
a) кроссинговер
b) скрещивание
c) транслитерация
d) транслокация
e) мутация
f) конверсия
6. Какие виды генетического алгоритма подразумевают параллельную обработку?
a) genitor
b) CHC
c) гибридные алгоритмы
d) островная модель
e) нет правильного ответа
7. Из какого числа особей можно выбирать пару (второго родителя) для особи в островной модели?
a) m, где m – число особей в популяции
b) m-1, где m – число особей в популяции
c) 4
d) 8
e) t, выбирается случайным образом, чаще всего t = 2
f) Нет правильного ответа
8. Какой оператор применен к особи (0001000 -> 0000000)?
a) инверсии
b) кроссовер
c) скрещивания
d) нет правильного ответа
Литература по теме «Эволюционное моделирование»:
1) Вороновский Г.К. Махотило К.В. Петрашев С.Н. Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Х.:ОСНОВА, 1997. - с.112.
2) Исаев С.А. Популярно о генетических алгоритмах. http://algolist.manual.ru/ai/ga/ga1.php
3) Каширина И.Л. Введение в эволюционное моделирование. Учебное пособие. Воронеж. 2007. с. 40.
4) Стариков А. Лаборатория BaseGroup. Генетические алгоритмы – математический аппарат. http://www.basegroup.ru/genetic/
5) Фогель Л., Оуэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969. 230 с.
6) Яминов Б. Генетические алгоритмы. Санкт-Петербургский государственный университет. 2005. http://rain.ifmo.ru/cat/view.php/theory/unsorted/genetic-2005
§4. Нечеткие множества и нечеткая логика
В основе нечеткой логики лежит теория нечетких множеств, изложенная в серии работ Л. Заде в 1965-1973 годах. Математическая теория нечетких множеств (fuzzy sets) и нечеткая логика (fuzzy logic) являются обобщениями классической теории множеств и классической формальной логики. Основной причиной появления новой теории стало наличие нечетких и приближенных рассуждений при описании человеком процессов, систем, объектов.
Л. Заде, формулируя это главное свойство нечетких множеств базировался на трудах предшественников. В начале 1920-х годов польский математик Лукашевич трудился над принципами многозначной математической логики, в которой значениями предикатов могли быть не только «истина» или «ложь». В 1937 г. еще один американский ученый Макс Блэк впервые применил многозначную логику Лукашевича к спискам как множествам объектов и назвал такие множества неопределенными.
Прежде чем нечеткий подход к моделированию сложных систем получил признание во всем мире, прошло не одно десятилетие с момента зарождения теории нечетких множеств.
Нечеткая логика как научное направление развивалась сложно и непросто, не избежала она и обвинений в лженаучности. Даже в 1989 году, когда примеры успешного применения нечеткой логики в обороне, промышленности и бизнесе исчислялись десятками, Национальное научное общество США обсуждало вопрос об исключении материалов по нечетким множествам из институтских учебников.
Первый период развития нечетких систем (конец 60-х–начало 70 гг.) характеризуется развитием теоретического аппарата нечетких множеств. В 1970 г. Беллман совместно с Заде разработал теорию принятия решений в нечетких условиях.
Во втором периоде (70–80-е годы) появляются первые практические результаты в области нечеткого управления сложными техническими системами (парогенератор с нечетким управлением). И. Мамдани в 1975 г. спроектировал первый функционирующий на основе алгебры Заде контроллер, управляющий паровой турбиной. Одновременно стало уделяться внимание вопросам построения экспертных систем, построенных на нечеткой логике, разработке нечетких контроллеров. Нечеткие экспертные системы для поддержки принятия решений находят широкое применение в медицине и экономике.
Наконец, в третьем периоде, который длится с конца 80-х годов и продолжается в настоящее время, появляются пакеты программ для построения нечетких экспертных систем, а области применения нечеткой логики заметно расширяются. Она применяется в автомобильной, аэрокосмической и транспортной промышленности, в области изделий бытовой техники, в сфере финансов, анализа и принятия управленческих решений и многих других. Кроме того, немалую роль в развитии нечеткой логики сыграло доказательство знаменитой теоремы FAT (Fuzzy Approximation Theorem) Б. Коско, в которой утверждалось, что любую математическую систему можно аппроксимировать системой на основе нечеткой логике.
Одним из самых впечатляющих результатов стало создание управляющего микропроцессора на основе нечеткой логики, способного автоматически решать известную «задачу о собаке, догоняющей кота». В 1990 г. Комитет по контролю экспорта США внес нечеткую логику в список критически важных оборонных технологий, не подлежащих экспорту потенциальному противнику.
В бизнесе и финансах нечеткая логика получила признание после того, как в 1988 году экспертная система на основе нечетких правил для прогнозирования финансовых индикаторов единственная предсказала биржевой крах. И количество успешных фаззи-применений в настоящее время исчисляется тысячами.
В Японии это направление переживает настоящий бум. Здесь функционирует специально созданная организация – Laboratory for International Fuzzy Engineering Research. Программой этой организации является создание более близких человеку вычислительных устройств.
Информационные системы, базирующиеся на нечетких множествах и нечеткой логике, называют нечеткими системами.
Достоинства нечетких систем:
- функционирование в условиях неопределенности;
- оперирование качественными и количественными данными;
- использование экспертных знаний в управлении;
- построение моделей приближенных рассуждений человека;
- устойчивость при действии на систему всевозможных возмущений.
Недостатками нечетких систем являются:
- отсутствие стандартной методики конструирования нечетких систем;
- невозможность математического анализа нечетких систем существующими методами;
- применение нечеткого подхода по сравнению с вероятностным не приводит к повышению точности вычислений.
Теория нечетких множеств
Главное отличие теории нечетких множеств от классической теории четких множеств состоит в том, что для четких множеств результатом вычисления характеристической функции могут быть только два значения – 0 или 1, то для нечетких множеств это количество бесконечно, но ограничено диапазоном от нуля до единицы.
Нечеткое множество
Пусть U - так называемое универсальное множество, из элементов которого образованы все остальные множества, рассматриваемые в данном классе задач, например множество всех целых чисел, множество всех гладких функций и т.д. Характеристическая функция множества
- это функция 
, значения которой указывают, является ли 
элементом множества A: