Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683



Download 5,19 Mb.
Pdf ko'rish
bet66/101
Sana16.10.2022
Hajmi5,19 Mb.
#853454
TuriУчебное пособие
1   ...   62   63   64   65   66   67   68   69   ...   101
Bog'liq
fel20E533

 
 
 


112 
Применение генетических алгоритмов 
Генетические алгоритмы носят эвристический характер. Можно 
предположить, что генетический алгоритм способен осуществлять 
эффективный поиск оптимального решения, при условии, что:
-
пространство поиска достаточно велико, и предполагается, что 
целевая функция не является гладкой и унимодальной в области поиска, т. е. 
не содержит один гладкий экстремум;
-
нет необходимости в поиске универсального оптимального 
решения, достаточно быстро найти подходящее решение. 
Если 
целевая 
функция 
обладает 
свойствами 
гладкости 
и 
унимодальности, то любой градиентный метод, такой как метод 
наискорейшего спуска, будет более эффективен. Генетический алгоритм 
является в определенном смысле универсальным методом, в связи с тем, что 
не учитывает специфику задачи. Если существует возможность получить 
сведения о целевой функции и сведения о пространстве поиска, то 
становится возможным использование эвристического поиска, который 
превосходит по эффективности универсальный алгоритм.
Сегодня генетические алгоритмы успешно применяются для решения 
классических NP-полных задач, задач оптимизации в пространствах с 
большим количеством измерений, ряда экономических задач оптимального 
характера, например, задач распределения инвестиций.
Использование эволюционных алгоритмов вместе с параллельными 
вычислениями позволяет эффективно решать задачи оптимизации, размер 
которых превышает 2
100
. Такие эволюционные алгоритмы называются 
распределенными генетическими алгоритмами. 
Можно выделить два способа применения параллельных технологий к 
генетическим алгоритмам [3]: 
1. 
Изменение структуру алгоритма (технология master-slave). При 
использовании этого способа параллельной обработке подвергаются такие 
независимые элементарные операции, как:


113 
-
построение особи, в операторе создания начальной популяции; 
-
построение потомка и его мутация, в операторе воспроизводства; 
-
оценка приспособленности особи. 
Технология master-slave предполагает, что работа над популяцией 
осуществляется на главном процессоре, а приспособленность особей 
вычисляется на подчиненных процессорах. Недостатком данного метода 
является возможное снижение эффективности вычислений при увеличении 
количества процессоров. Это происходит за счет потери времени на обмен 
данными между главным процессором и подчиненным
и потери времени на 
ожидание завершения работы всех подчиненных процессоров для 
продолжения вычислений. 
2. 
Изменение структуры алгоритма в результате применения 
ограничений 
возможности 
скрещивания 
(мелкоструктурированный 
параллельный 
генетический 
алгоритм 
и 
крупноструктурированный 
параллельный 
генетический 
алгоритм. 
Крупноструктурированный 
параллельный 
генетический 
алгоритм 
имеет 
отношение 
к 
мултипопуляционным моделям, таким как метод случайных иммигрантов в 
исследованиях Grefenstette, метод ниш и островным моделям. При таком 
способе вычислений популяция делится на локальные популяции, развитие 
которых происходит параллельно и независимо, но при этом сохраняется 
возможность обмена особями между популяциями. Особи разных локальных 
популяций не могут образовывать брачные пары. Естественный отбор 
действует только внутри локальной популяции. Каждая локальная популяция 
обрабатывается на отдельном процессоре. Основой алгоритма является 
определенный метод разбиения популяции. Для минимизации затрат на 
обмен данными, топология связи между локальными популяциями отражает
топологию связи между процессорами или компьютерами вычислительной 
системы. Большое количество связей между популяциями снижает 
эффективность вычислений. А уменьшение количества связей приводит к
преждевременной сходимости в ряде локальных популяций и потери 


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

Download 5,19 Mb.

Do'stlaringiz bilan baham:
1   ...   62   63   64   65   66   67   68   69   ...   101




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