Статья

Название статьи АДАПТИВНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ НА ОСНОВЕ НЕЧЕТКИХ ПРАВИЛ
Автор В. М. Курейчик, Т. Г. Каплунов
Рубрика РАЗДЕЛ I. МЕТОДЫ И АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ
Месяц, год 05, 2018
Индекс УДК 004.021
DOI
Аннотация Рассмотрен подход к увеличению поисковых способностей генетического алгоритма. Цель данной работы заключается в нахождении путей ускорения работы генетических алгоритмов используемых для оптимизации и поиска глобальных экстремумов функций. Актуальность работы состоит в том, что на сегодняшний день увеличение поисковых способностей генетических алгоритмов составляет основную проблему при использовании таких алгоритмов. Зачастую при манипуляциях с алгоритмом повышается вероятность попадания в локальный экстремум исследуемой функции. Постановка задачи в данной работе выглядит следующим образом: дан некоторый набор тестовых функций, необходимо найти глобальные экстремумы этих функций, сделав это за полиномиальное время, меньшее чем время, затрачиваемое классическим генетическим алгоритмом. Классический генетический алгоритм реализует действие естественного отбора (ЕО) на уровне индивидов. Однако в микробиологии естественный отбор представляется как отбор генов, эта точка зрения в теории генетических алгоритмов не получила широкого распространения. В данной работе представлен алгоритм реализующий естественный отбор на уровне генов. За меру оценки приспособленности гена в работе принимается его стабильность в процессе смены поколений, которая прослеживается на основе карт Шухарта. В алгоритме используется набор нечетких правил, с помощью которых происходит управление динамически изменяемыми параметрами алгоритма, в частности, вероятность попадания в следующее поколение. На основе заключения о том, что гены являются статистически управляемыми – в алгоритм внедрен блок прогнозирования. Для повышения скорости работы алгоритма можно ввести внутреннее прогнозирование генома. Решение о прогнозировании вносится на основе нечеткого правила: если временной ряд i-го представителя популяции управляем по Шухарту за последние L поколений, то добавить в популяцию особь, геном которой состоит из предсказанных значений генов на K поколений вперед. Таким образом в алгоритме происходит управление динамически изменяемыми параметрами (мутация, размер популяции), а также реализовано прогнозирование наиболее приспособленных генов на основе стороннего ГА. Результаты работы подтверждаются экспериментом, проведенном на тестовых функциях для алгоритмов оптимизации. На основе проведенных экспериментов можно сделать вывод о практической применимости данного алгоритма в поисковых и оптимизационных задачах.

Скачать в PDF

Ключевые слова Генетический алгоритм; оптимизация; прогнозирование; контрольные карты Шухарта; нечеткие правила.
Библиографический список 1. Гладков Л.А., Курейчик В.В, Курейчик В.М. и др. Биоинспирированные методы в оптимизации: монография. – М.: Физматлит, 2009. – 384 с.
2. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. – 2-е изд. – М.: Горячая линия-Телеком, 2008. – 452 с.
3. Уилер Дональд, Чамберс Дэвид. Статистическое управление процессами: Оптимизация бизнеса с использованием контрольных карт. – М.: Альпина Паблишер, 2009. – 410 с.
4. Синюк В. Г., Акопов В.Н. Управляемые статистические генетические алгоритмы // Программные продукты и системы. – 2008. – № 4.
5. Курейчик В.М., Синютин В.Г., Каплунов Т.Г. Прогнозирование состояний технических систем при помощи генетических алгоритмов // Вестник рязанского государственного радиотехнического университета. – 2018. – № 3. – С. 107-113.
6. Ярушкина Н.Г., Афанасьева Т.В., Перфильева И.Г. Интеллектуальный анализ временных рядов: учеб. пособие. – М.: Изд. дом «ФОРУМ»: ИНФРА-М, 2012. – 315 с.
7. Holland J.H. Hidden Order: how adaptation builds complexity. – Addison-Wesley, 1995.
– 204 p.
8. Baeck T., Fogel D., Michalewicz Z. Evolutionary computation. Basic algorithms and operators. – Bristol&Philadelphia: IOP publishing LTD, 2000. – 304 p.
9. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: учеб. пособие.
– 2-е изд.. – М.: Физматлит, 2006. – 320 с.
10. Uziel Sandler, Lev Tsitolovsky. Neural Cell Behavior and Fuzzy Logic. – Springer, 2008.
– 478 p.
11. Тэрано Т., Асаи К., Сугэно М. Прикладные нёчеткие системы. – М.: Мир, 1993. – 368 с.
12. Рутковский Лешек. Искусственные нейронные сети. Теория и практика. – М.: Горячая линия - Телеком, 2010. – 452 с.
13. Новак В., Перфильева И., Мочкрож И. Математические принципы нечёткой. – М.: Физматлит, 2006. – 352 с.
14. Лапидус В.А. Система Шухарта. – Н. Новгород: ООО СМЦ «Приоритет», 2004. – 65 с.
– ISBN 5-98366-010-1.
15. Барабанова О.А. Семь инструментов контроля качества. – М.: ИЦ «МАТИ» - РГТУ им. Циолковского, 2001. – 88 c.
16. Spears W.M. Adapting crossover in a genetic algorithm. – The University of Michigan Press, 1988.
17. Donald J. Wheeler. Advanced Topics in Statistical Process Control: The Power of Shewhart's Charts. – SPC Press, 1995.
18. Романов В.Н. Нечеткие модели принятия решений // Альманах современной науки и образования. – 2013. – № 5 (72). – C. 144-147.
19. Грант В. Эволюционный процесс: Критический обзор эволюционной теории: пер. с англ. – М.: Мир, 1991. – 488 c.
20. Шмальгаузен И.И. Избранные труды. Организм как целое в индивидуальном и историческом развитии. – М.: Наука, 1982. – С. 348-372.
21. Goldberg D.E., Sastry K. A Practical Schema Theorem for Genetic Algorithm Design and Tuning / Illinois Genetic Algorithms Laboratory, 2001.
22. Herrera F., Lozano M., Verdegay J.L. Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis, 1996. – Department of Computer Science and Artifcial Intelligence University of Granada, Spain.
23. Rosenbrock H.H. An automatic method for finding the greatest or least value of a function // The Computer Journal. – 1960. – No. 3. – P. 175-184.
24. Rastrigin L.A. Systems of extremal control. – Moscow: Mir, 1974.

Comments are closed.