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


 Задачи оптимизации и применение алгоритмов



Download 9,87 Mb.
Pdf ko'rish
bet15/228
Sana20.06.2022
Hajmi9,87 Mb.
#683557
TuriКнига
1   ...   11   12   13   14   15   16   17   18   ...   228
Bog'liq
Algorithms3

1.4. Задачи оптимизации и применение алгоритмов 
Генетические алгоритмы - это очень популярные способы решения 
задач оптимизации. В их основе лежит использование эволюционных 
принципов для поиска оптимального решения. Уже сама идея выглядит 
довольно интригующей и любопытной, чтобы претворить её в жизнь, а 
многочисленные положительные результаты только разжигают интерес 
со стороны исследователей. 
Здесь не будет рассматриваться история становления и признания 
эволюционных вычислений вообще и генетических алгоритмов в 
частности. Вместо этого мы сразу перейду к рассмотрению самих 
алгоритмов.
Генетические алгоритмы в основном применяются для решения задач 
оптимизации, т.е. задач, в которых есть некоторая функция нескольких 
переменных 
F(x
1
, x
2
, ... ,x
n
) и необходимо найти либо её максимум, либо 
её минимум. Функция 
F
называется 
целевой функцией
, а переменные - 
параметрами функции
. Генетические алгоритмы "пришиваются" к 
данной задаче следующим образом. 
Параметры задачи являются генетическим материалом - генами. 
Совокупность генов составляет хромосому. Каждая особь обладает 
своей хромосомой, а, следовательно, своим набором параметров. 
Подставив параметры в целевую функцию, можно получить какое-то 
значение. То, насколько это значение удовлетворяет поставленным 
условиям, определяет характеристику особи, которая называется 
приспособленностью 
(fitness)

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


А.Е. Кононюк Дискретно-непрерывная математика 
28 
особей для скрещивания проводится согласно 
селективной стратегии 
(selection 
strategy)
. Заново сформированная популяция снова 
оценивается, затем выбираются наиболее достойные для скрещивания 
особи, которые скрещиваются между собой, получаются «дети»и 
занимают место «престарелых» индивидуумов и т.д. 
Все эта продолжается до тех пор пока не найдется особь, гены которой 
представляют оптимальный набор параметров, при которых значение 
целевой функции близко к максимуму или минимуму, либо равно ему. 
Останов работы ГА может произойти также в случае, если популяция 
вырождается, т.е. если практически нет разнообразия в генах особей 
популяции, либо если просто вышел лимит времени. Вырождение 
популяции называют 
преждевременной сходимостью (premature 
convergence)

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

Экстремальные задачи (нахождение точек минимума и 
минимума);


А.Е. Кононюк Дискретно-непрерывная математика 
29 

Задачи о кратчайшем пути;

Задачи компоновки;

Составление расписаний;

Аппроксимация функций;

Отбор (фильтрация) входных данных;

Настройка искусственной нейронной сети;

Моделирование искусственной жизни (Artificial life systems) ;

Биоинформатика (свертывание белков и РНК);

Игровые стратегии;

Нелинейная фильтрация;

Развивающиеся агенты/машины (Evolvable agents/machines);

Оптимизация запросов в базах данных 

Разнообразные задачи на графах (задача коммивояжера, 
раскраска, нахождение паросочетаний) 

Обучение искусственной нейронной сети 

Искусственная жизнь 
Некоторые разделы могут содержать подпункты. Так, например, 
экстремальные задачи включают в мебя целый класс задач линейного и 
нелинейного программирования.

Download 9,87 Mb.

Do'stlaringiz bilan baham:
1   ...   11   12   13   14   15   16   17   18   ...   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