Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы


управления является порождение управляющих конечных



Download 9,87 Mb.
Pdf ko'rish
bet33/228
Sana20.06.2022
Hajmi9,87 Mb.
#683557
TuriКнига
1   ...   29   30   31   32   33   34   35   36   ...   228
Bog'liq
Algorithms3

управления является порождение управляющих конечных 
автоматов (как классических, так и на основе теории нечетких 
множеств), где также достигнуты определенные успехи. 
Итак, 
эволюционные вычисления неплохо себя зарекомендовали в 
качестве методов поиска как при решении задач классического ИИ 
(т. е. при решении корректно поставленных NP-полных задач), так 
и при решении задач машинного обучения, хотя и не дали их 
полного решения. 
Почему же методы эволюционных вычислений оказываются достаточно 
успешными для решения проблем поиска? Эволюционные стратегии в 
применении к поиску экстремума функции от вещественных 
переменных очень похожи на стохастический градиентный спуск за 
исключением того, что в них происходит «скрещивание» решений. С 
генетическими алгоритмами ситуация чуть сложнее, так как в них 
небольшие мутации генов могут привести к значительному изменению 
«фенотипа» (примером может служить изменение старшего бита в 
двоичной записи числа). Но и в ГА основной особенностью является 
скрещивание, благодаря которому новые решения строятся как 
фрагменты имеющихся решений. Если задача разбивается на подзадачи 
и решению каждой подзадачи соответствует отдельный участок генома
то за счет скрещивания подзадачи могут решаться независимо. 
Действительно, если решение какой-то подзадачи улучшает общее 
решение независимо от других подзадач, то в генофонде популяции 
соответствующий участок генома быстро стабилизируется (его 
вариативность сильно уменьшится). Еще в большей степени этому 
будет способствовать использование не равномерного скрещивания, а 
кроссинговера, при котором потомкам передаются длинные фрагменты 
генотипов родителей. Кроссинговер будет работать хорошо, только 
если решения отдельных подзадач локализованы в геноме. 
Итак, мы видим, что ГА дополнены одним, но очень мощным приемом, 


А.Е. Кононюк Дискретно-непрерывная математика 
55 
благодаря которому решаемая задача «мягко» (но не адаптивно) 
разбивается на подзадачи. Следует, однако, иметь в виду, что этот 
прием не вполне универсален. Если участки генома не соответствуют 
фрагментам решений почти независимых подзадач (в силу 
особенностей решаемой NP-полной задачи или в силу неудачного 
выбора способа кодирования решения в геноме), то ГА будут смесью 
полного перебора и градиентного спуска, причем реализованного не 
самым эффективным образом. Отдельные участки генома не будут 
стабилизироваться независимо друг от друга, и найти решение удастся, 
только если все гены одновременно рекомбинируют нужным образом, 
вероятность чего будет очень низка. 
Прием, который позволяет эффективно сокращать перебор для многих 
задач, но в общем случае не гарантирует нахождения оптимального 
решения, принято называть метаэвристикой. В отличие от простой 
эвристики метаэвристика не является предметно-специфичной, что 
делает ее широко применимой, но во многих случаях недостаточной. К 
примеру, сами по себе ГА не могут использоваться при выборе хода в 
шахматах, для которых классическое эвристическое программирование 
пока остается хоть и весьма трудоемким, но практически единственным 
подходящим средством. Если же в какой-то NP-полной задаче части 
решения являются почти независимыми (как, например, в задаче 
коммивояжера), то единственная метаэвристика, заложенная в ГА, 
может оказаться достаточной для получения приемлемого решения, 
благодаря чему не нужно будет разрабатывать индивидуальный (под 
данную задачу) алгоритм обхода дерева варианта со сложными 
предметно-специфичными эвристиками. 
Часто говорят, что эволюционные вычисления весьма эффективны, 
поскольку они заимствуют основные идеи из естественной эволюции. 
Но зададимся наивным вопросом: почему генетическое 
программирование не позволяет создать ИИ? Выше мы не напрасно 
останавливались на вопросах устройства генов: теперь мы видим, что 
ГА и аналогичные им методы столь же проще реальных генетических 
механизмов, сколь и ИНС проще биологических нейронов. Вместе с тем 
ГА, как и методы обучения ИНС, недостаточны для работы в 
алгоритмически полном пространстве. 
Несмотря на некоторые положительные свойства, методы 


А.Е. Кононюк Дискретно-непрерывная математика 
56 
эволюционных вычислений оказываются вовсе не универсальными. В 
связи с этим, если мы рассмотрим эволюционные вычисления как 
методы поиска в пространстве решений, то становится понятным, 
почему с их помощью не так просто автоматически получить ИИ. По 
сути, эти методы сами будут составлять интеллектуальную систему, 
перед которой ставится задача поиска программы ИИ. Нет ли здесь 
противоречия? Не получается ли так, что нам уже нужно иметь ИИ, 
чтобы компьютер смог сам его придумать? Принципиального 
противоречия здесь нет: более «глупая» программа может вывести 
более «умную» посредством «грубой силы», т. е. используя очень 
интенсивный перебор. Конечно, чем глупее эволюционная программа, 
тем больше грубой силы ей придется приложить. Полным перебором 
задачу построения ИИ или даже игры в шахматы на практике не 
решить. Естественно, недостаточно и нескольких простых 
метаэвристик. Такой взгляд показывает наивность попыток с помощью 
простой искусственной эволюции вывести интеллектуальные 
программы. Но как это удалось сделать естественной эволюции? 

Download 9,87 Mb.

Do'stlaringiz bilan baham:
1   ...   29   30   31   32   33   34   35   36   ...   228




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish