Читать реферат по информатике, вычислительной технике, телекоммуникациям: "Генетические алгоритмы" Страница 3

(Назад) (Cкачать работу)

Если ОК выполняется посредством случайного выбора, например, с вероятностью P(ОК), то вероятность выживания схемы определится

P(s)?1-P(ОК)L(H)/(L-1).(8) Допуская независимость репродукции (ОР) и ОК, получим [1]: m(H,t+1) ? m(H,t)  f(H)/f* [1-P(ОК) 

L(H)/(l-L)].(9) Из выражения (9) следует, что схемы с выше средней ЦФ и короткой L(H) имеют возможность экспоненциального роста в новой популяции.

Рассмотрим влияние мутации на возможности выживания. ОМ есть случайная альтернативная перестановка элементов в стринге с вероятностью Р(ОМ). Для того, чтобы схема H выжила, все специфические позиции должны выжить. Следовательно, единственная хромосома выживает с вероятностью (1-P(ОМ)) и частная схема выживает, когда каждая из l(H) закрепленных позиций схемы выживает. 1-L(H)Р(ОМ).(10) Тогда мы ожидаем, что частная схема H получает ожидаемое число копий в следующей генерации после ОР,ОК ОМ m(H,t+1)>m(H,t)f(H)/f*[1-Р(ОК)l(H)/(l-1)-

l(H)P(ОМ)].(11) Это выражение называется "схема теорем" или фундаментальная теорема ГА [1].

Ответа на вопрос, почему необходимо давать выживание схемам с лучшей ЦФ, нет или он расплывчатый, или каждый раз зависит от конкретной задачи.

Основная теорема ГА, приведенная Холландом, показывает ассимптотическое число схем "выживающих” при реализации ПГА на каждой итерации. Очевидно,что это число, конечно приблизительное и меняется в зависимости от вероятности применения ГА. Особенно сильное влияние на число "выживающих" и "умирающих" схем при реализации ПГА оказывает значение целевой функции отдельной хромосомы и всей популяции.

Во многих проблемах имеются специальные знания, позволяющие построить аппроксимационную модель. При использовании ГА это может уменьшить объем и время вычислений и упростить моделирование функций, сократить число ошибок моделирования.

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

Список литературы

Holland John H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan , 1975.

Goldberd David E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Inc. 1989, 412p.

Handbook of Genetic Algorithms, Edited by Lawrence Davis, Van Nostrand Reinhold, New York, 1991, 385p.

Курейчик В.М., Лях А.В. Задачи моделирования эволюции в САПР. Труды международной конференции (CAD-93), РФ - США, Москва, 1993.

Chambers L.D., Practical Handbook of Genetic Algorithms. CRS Press, BocaRation FL, 1995, v. 1, 560 p., v. 2, 448 p.

Растригин Л.А. статистические методы поиска. М: Наука, 1968.

Эволюционные вычисления и генетические алгоритмы. Составители Гудман Э.Д., Коваленко А.П. Обозрение прикладной и промышленной математики, том 3, вып. 5, Москва, ТВП, 1996, 760с.

Похожие работы