Автор: Попов В.А., Бердочник А.В.
Источник:
Национальный аэрокосмический университет им. Н.Е. Жуковского «ХАИ», Харьков
Попов В.А., Бердочник А.В. Оптимизационные задачи на основе генетического поиска. Приводится характеристика основных принципов функционирования генетического алгоритма, его сравнение с традиционными методами оптимизации, его достоинства и недостатки. Рассматриваются различные модификации генетического алгоритма в зависимости от области применения. Приводится сравнение генетических алгоритмов и эволюционных стратегий в рамках эволюционного моделирования. Рассматриваются области применения эволюционного программирования, а также типовые области и задачи применения моделей и методов генетического поиска.
Генетический алгоритм (ГА) изначально возник в результате наблюдений и попыток копирования естественных процессов, происходящих в природе, в частности эволюции и связанной с ней — селекции (естественного отбора) живых организмов. ГА представляет собой метод, отражающий естественную эволюцию методов решения проблем, и, в первую очередь задач, оптимизации. ГА — это процедуры поиска, основанные на механизмах естественного отбора и наследования. В них используется эволюционный принцип — выживание наиболее приспособленной особи [1–5].
С точки зрения программных и информационных технологий генетические алгоритмы используются как стратегия решения задач оптимизации, основанная на имитировании биологической эволюции.
В статье будут рассмотрены основные виды генетических алгоритмов, их возможности для решения задач в различных предметных областях, будут выделены наиболее эффективные условия применения ГА, будут даны их сравнительные оценки, на основании чего будут сформулированы новые — нерешенные задачи оптимизации на основе генетического поиска.
1. ГА и традиционные методы оптимизации
Генетические алгоритмы относятся к классу обширную область решений, исследование которой эволюционных алгоритмов и представляют собой вероятностные методы оптимизации. Генетические алгоритмы отличаются от традиционных алгоритмов оптимизации несколькими базовыми принципами. В частности к ним можно отнести следующее:
Рассмотрим некоторые отличительные характеристики ГА, обуславливающие его эффективность.
Первое и наиболее важное качество ГА — наличие внутреннего параллелизма. Большинство других алгоритмов оптимизации исследуют область поиска в одном направлении, и в случае, если найденное ими решение окажется субоптимальным, поиск придется прекратить, и начать все заново. В то же время ГА оперируют популяциями с многочисленными потомками, исследуя таким образом пространство поиска в различных направлениях.
Исходя из параллелизма, который позволяет неявно оценивать множество решений за одну итерацию, ГА хорошо применим для задач с огромной областью поиска — слишком обширной для основательного поиска и при разумных затратах времени. В эту область попадает большинство задач, называемых нелинейными.
Еще одним преимуществом применения ГА является то, что они эффективны в случаях сложной области поиска, когда она бесконечна, изменяется во времени, либо имеет множество локальных оптимумов. Большинство практических задач имеют обширную область решений, исследование которой полностью является невозможным. Также проблемой для традиционных оптимизационных алгоритмов могут стать локальные оптимумы. Все эти задачи с легкостью решаются с помощью генетического алгоритма.
Еще одной областью, в которой ГА отличаются от других алгоритмов оптимизации, является их умение оперировать множеством параметров одновременно. Множество реальных задач не может просто обозначаться в понятиях единственного значения либо максимизации, либо минимизации. Часто в таких задачах преследуются множественные цели или присутствуют элементы компромисса, когда улучшение одного из параметров возможно только за счет другого и т.п. ГА прекрасно решают данную задачу. В частности, используя параллелизм, они находят возможные решения, одно из которых оптимизирует один из взаимоисключающих параметров, другое решение — другой параметр. Тогда лицо, принимающее решение, на основе полученных результатов может выбрать наиболее приемлемое решение.
Наконец, наиболее примечательной чертой ГА является то, что он формально «не знает» ничего о решаемой задаче, т.е. ему не требуется никакой специфической информации для управления каждымшагом изменений на пути улучшения получаемых решений. Он «вслепую» производит изменения в решениях-кандидатах и использует функцию приспособленности для определения динамики в популяции.
2. Модификации классического ГА
В классическом варианте ГА используется двоичное представление хромосом, селекция методом колеса рулетки и точечное скрещивание(с одной точкой скрещивания). Для повышения эффективности его работы создано множество модификаций основного алгоритма. Они связаны с применением иных методов селекции, с модификацией генетических операторов (в первую очередь оператора скрещивания), с преобразованием функции приспособленности (путем ее масштабирования), а также с иными способами кодирования параметров задачи в форме хромосом. Существуют также версии алгоритмов, позволяющие находить не только глобальные, но и локальные оптимумы. Эти алгоритмы используют так называемые ниши, введенные в генетические алгоритмы по аналогии с природными экологическими нишами. Другие версии ГА служат для многокритериальной оптимизации, т.е. для одновременного поиска оптимального решения для нескольких функций. Встречаются также специальные версии генетических алгоритмов, созданные для решения проблем малой размерности, не требующие ни больших популяций, ни длинных хромосом. Их называют г енетическими микроалгоритмами [23, 28].
3. Эволюционные алгоритмы
ГА совместно с эволюционной стратегией и эволюционным программированием представляют три главных направления развития так называемого эволюционного моделирования (ЭМ). Несмотря на то, что каждый из этих методов возник независимо от других, в общем случае они характеризуются рядом важных общих свойств. Для любого из них формируется исходная популяция особей, которая в последующем поддается селекции и воздействию различных генетических операторов, что позволяет находить более оптимальные решения.
Отметим важнейшие сходства и различия между эволюционными стратегиями (ЭС) и ГА [24–28]. Очевидно, что главное сходство заключается в том, что оба метода используют популяции потенциальных решений и реализуют принцип селекции и преобразования наиболее приспособленных особей. Однако обсуждаемые подходы сильно отличаются друг от друга. Первое различие заключается в способе представления особей. Эволюционные стратегии оперируют векторами действительных чисел, тогда как ГА — двоичными векторами.
Второе различие между ЭС и ГА кроется в организации процесса селекции. При реализации эволюционной стратегии формируется промежуточная популяция, состоящая из всех родителей и некоторого количества потомков, созданных в результате применения генетических операторов. С помощью селекции размер этой промежуточной популяции уменьшается до величины родительской популяции за счет исключения наименее приспособленных особей. Сформированная таким образом популяция образует следующее поколение. В ГА предполагается, что в результате селекции из популяции родителей выбирается количество особей, равное размерности исходной популяции, при этом некоторые (наиболее приспособленные) особи могут выбираться многократно. При реализации ЭС особи выбираются без повторений. В эволюционных стратегиях применяется детерминированная процедура селекции, тогда как в ГА она имеет случайный характер.
Третье различие между ЭС и ГА касается последовательности выполнения процедур селекции и рекомбинации (т.е. изменения генов в результате применения генетических операторов). При реализации ЭС вначале производится рекомбинация, а затем селекция. В случае выполнения ГА эта последовательность инвертируется. При осуществлении применения ЭС потомок образуется в результате скрещивания двух родителей и последующей мутации. Формируемая таким образом промежуточная популяция, состоящая из всех родителей и полученных от них потомков, в дальнейшем подвергается селекции, которая уменьшает размер этой популяции до размера исходной популяции. При выполнении ГА вначале производится селекция, приводящая к образованию переходной популяции, после чего генетические операторы скрещивания и мутации применяются к особям, выбираемым с вероятностью скрещивания, и к генам, выбираемым с вероятностью мутации.
Следующее различие заключается в том, что параметры ГА (такие как вероятности скрещивания и мутации) остаются постоянными на протяжении всего процесса эволюции, тогда как при реализации ЭС эти параметры подвергаются непрерывным изменениям — так называемая самоадаптация параметров.
Еще одно различие между ЭС и ГА касается трактовки ограничений на решаемые оптимизационные задачи. Если при реализации ЭС на некоторой итерации потомок не удовлетворяет всем ограничениям, то он отвергается и включается в новую популяцию. Если таких потомков оказывается много, то ЭС запускает процесс адаптации параметров. В ГА такие параметры не изменяются. В них может применяться штрафная функция для тех особей, которые не удовлетворяют наложенным ограничениям.
Эволюционное программирование (ЭП) применяется для оптимизации функционирования нейронных сетей (НС). Также как и другие эволюционные методы, ЭП не требует градиентной информации и поэтому может использоваться для решения задач, в которых эта информация недоступна либо для ее получения требуются значительные объемы вычислений. Одними из первых приложений ЭП считаются задачи теории искусственного интеллекта, а самые ранние работы касались теории конечных автоматов [10].
Все три представленных метода, т.е. генетические алгоритмы, эволюционные стратегии и эволюционное программирование объединяются под общим названием эволюционные алгоритмы. Также применяется термин эволюционные методы.
4. ГА и области его применения
Генетические алгоритмы в различных формах применяются ко многим научным и техническим проблемам. Генетические алгоритмы используются при создании различных вычислительных структур [6–8], например, автоматов или сетей сортировки. В машинном обучении они используются при проектировании нейронных сетей или управлении роботами. Они также применяются при моделировании развития в различных предметных областях: управление производством [9–12, 14], экономика [15], медицина [16], моделирование [17–19].
Тем не менее, возможно наиболее популярное приложение генетических алгоритмов — оптимизация многопараметрических функций [13].
Многие реальные задачи могут быть сформулированы как поиск оптимального значения, где значение представлено сложной функцией, зависящей
от некоторых входных параметров. В некоторых случаях необходимо найти те значения параметров, при которых достигается наилучшее точное
значение функции. В других случаях, точный оптимум не требуется, решением может считаться любое значение, которое лучше некоторой
заданное величины. В этом случае, генетические алгоритмы являются наиболее приемлемым методом для поиска хороших
значений.
Эффективность генетического алгоритма заключена в его способности манипулировать одновременно многими параметрами. Эта особенность ГА
использована во многих прикладных программах, включая проектирование самолетов, настройку параметров алгоритмов и поиск устойчивых
состояний систем нелинейных дифференциальных уравнений.
Также можно отметить ряд примеров применения генетического алгоритма в таких областях научного знания как геофизика, экономика и финансы, разработка игр, математика и алгоритмирование, биология, в том числе и молекулярная, проектирование роботов и т.д. [2–21]
Описанные выше примеры не исчерпывают многообразие областей и задач применения ГА в целях оптимизации, которая является одной из древнейших математических задач, вошедшей во все сферы жизни.
В некоторых случаях ГА оказываются незаменимыми и более эффективными, чем традиционные известные алгоритмы и методы. Эволюционные алгоритмы, включающие ГА, эволюционные стратегии и эволюционное программирование активно развиваются и приобретают все большую популярность в сложных комбинаторных оптимизационных задачах, задачах с множеством локальных оптимумов, задачах с обширных полем поиска и т.д. Развитие компьютерных технологий и вычислительной мощности компьютеров только укрепит позиции генетического алгоритма как нового и эффективного алгоритма поиска.
1. Введение в ГА и генетическое программирование. [Электронный ресурс]. — Режим доступа к источнику: http://algolist.manual.ru/ai/ga.
2. Назаров А.В. Нейросетевые алгоритмы прогнозирования и оптимизации систем / А.В. Назаров, А.И. Лоскутов. — СПб.: Наука и Техника, 2003. — 384 с.
3. Курейчик В.М. Эволюционные вычисления: генетическое и эволюционное программирование / В.М. Курейчик, С.И. Родзин // Новости искусственного интеллекта.— 2003. — № 5. — С. 13–19.
4. Костенко В.А. Принципы построения генетических алгоритмов и их использование для решения задач оптимизации. [Электронный ресурс] / В.А. Костенко // Вестник МГУ . — Режим доступа к журналу: http://lvk.cs.msu/index.php/articles/156.
5. Генетические алгоритмы. [Электронный ресурс]. — Режим доступа к источнику: http://math.nsc.ru/AP/ benchmarks/UFLP/uflp_ga.html.
6. Костенко В.А. Генетические алгоритмы решения смешанных задач целочисленной комбинаторной оптимизации при синтезе структур ВС[Электронный ресурс] / В.А. Костенко, А.Г. Трекин. — Режим доступа к статье: http://lvk.cs.msu.su /index.php/articles/158.
7. Костенко В.А. Возможности генетических алгоритмов для решения задач синтеза архитектур и планирования вычислений / В.А. Костенко // Труды Третьей Междунар. научн. конф. «Дискретные модели в теории управляющих систем» (Красновидово’98). — М.: ДиалогМГУ, 1998. — С. 53–58.
8. Пятаев О.В. Особенности формализации задачи оптимизации структуры кампусных сетей [Электронный ресурс] / О.В. Пятаев, А.В. Семашко. — Режим доступак статье: http://zhurnal.ape.relarn/ articles/2001/000.pdf.
9. Валиахметова Ю.И. Мультиметодный генетический алгоритм для решения ортогональной упаковки/ Ю.И. Валиахметова, А.С. Филишова // Информационные технологии. — 2007. — № 12. — С. 50–56.
10. Витковски Т. Исследование переменных и параметров генетического алгоритма для планирования производства / Т. Витковски, С. Эльзвай., А. Антчак // Проблемы управления и информатики. — 2004. — № 1. — С. 136–144.
11. Баранов Л.Т. Генетическое программирование в задачах планирования профилактических работ/ Л.Т. Баранов, А.И. Птушкин, Д.В. Скориков // Вестник вузов. Приборостроение. — 2006 — № 10. — С. 3–9.
12. Серов В.А. Генетические алгоритмы оптимизации управления многокритериальными системами в условиях неопределенности на основе конфликтных равновесий / В.А. Серов // Вестник МГТУ им. Н.Э. Баумана. Сер. «Приборостроение». — 2007. — №4. — С. 70–78.
13. Батищев Д.И. Оптимизация нестационарных задач комбинаторного типа с помощью генетических алгоритмов. [Электронный ресурс] / Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. — Режим доступа: http://lvk.cs.msu.su /index.php/articles/153.
14. Матвейкин В.Г. Использование генетического алгоритма при оперативном управлении поточным производством / В.Г. Матвейкин, Б.С. Дмитриевский, Н.В. Жданова // Приборы и системы. Управление, контроль, диагностика. — 2007.— №12. — С. 56–58.
15. Баркалов С.А. Оптимизационные модели распределения инвестиций на предприятии по видам деятельности / С.А. Баркалов, О.Н. Бакунец, И.В. Гуреева, В.Н. Колпачев, И.Б. Руссман. — М.: ИПУ РАН, 2002. — 68 с.
16. Ковшов Е.Е. Применение аппарата генетических алгоритмов для моделирования и формирования расписания операций в многопрофильной клинике/ Е.Е. Ковшов,А.В. Машковцев // Информационные технологии. — 2006. — С. 63–66.
17. Гагарин А.В. Интеллектуальный алгоритм оптимизации параметров ресурсоемких моделей / А.В. Гагарин // Информационные технологии. — 2008 — № 1. — С. 23–27.
18. Андрейчиков А.В. Интеллектуальная система эволюционного синтеза сложных объектов / А.В. Андрейчиков, О.Н. Андрейчикова // Теория и системы управления.— 2006 — № 4. — С. 94–107.
19. Каширина И.Л. Генетический алгоритм решения многокритериальной задачи о назначениях/ И.Л. Каширина, Б.А. Семенов // Информационные технологии. — 2007. — № 5. — С. 62–68.
20. Genetic Algorithms and Evolutionary Computation by Adam Marczyk. [Электронный ресурс]. — Режим доступа: http://www.talkorigins.org/faqs/ genalg/genalg.html.
21. Genetic Algorithms: Mathematics. [Электронный ресурс]. — Режим доступа: http://articles.mql4.com/134.
22. Genetic Algorithms in Plain English. [Электронный ресурс] — Режим доступа: http://www.ai-junkie.com/ga/intro/gat1.html
23. Multiobjective Genetic Algorithm for Product Design. [Электронный ресурс]. — Режим доступа: http://www.masters.donntu.ru/2007/fvti/pogorelaya/library/nanda.htm.
24. Nhe GA Playground (Genetic Algorithms Toolkit). [Электронный ресурс]. — Режим доступа: http://www.aridolan.com/ga/gaa/gaa.html#MultipleProblems.
25. Global Optimization Algorithms — Theory and Application by Thomas Weise [Электронный ресурс]. — Режим доступа: http://www.it-weise.de.
26. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975.
27. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine learning. Addison-Wesley, 1989.
28. Mitchell M. An introduction to Genetic Algorithm. MIT Press, 1996.