Автореферат
Автореферат |
|
| . | |
Это почти полная версия моего автореферата. Рассылка состоялась 12 апреля 2000 года. Защита - 18 мая 2000 года.
На правах рукописи
Разработка и исследование генетических алгоритмов
для принятия решений на основе
многокритериальных нелинейных моделей
Специальность: 05.13.17 - теоретические основы информатики
АВТОРЕФЕРАТ
диссертации на соискание
ученой степени кандидата технических наук
Н.Новгород
2000
Работа выполнена на кафедре "Информатики и автоматизации научных исследований" Нижегородского государственного университета им.Н.И.Лобачевского
Научный руководитель: Заслуженный деятель науки РФ, доктор технических наук, профессор, БАТИЩЕВ Д.И.
Официальные оппоненты:
доктор технических наук, профессор ГЕРГЕЛЬ В.П.
кандидат технических наук, старший научный сотрудник ВЛАСОВ С.Е.
Ведущая организация: Институт Автоматизации Проектирования РАН
Модель, рассматриваемая в диссертационной работе, включает в себя три класса оптимизационных задач:
К настоящему времени каждый из трех классов представлен множеством различных методов и алгоритмов. Большинство из которых основаны на использовании свойств рассматриваемого класса задач. Включение дополнительной информации о свойствах исследуемых моделей безусловно способствовало тому, что появлялись мощные и высокоэффективные алгоритмы, но сфера их применимости ограничивалась часто только узким классом задач.
Применительно к реальным задачам большинство из "классических" методов были неприменимы напрямую, поскольку требовалась четкая формализация конкретной решаемой задачи. Это приводило к тому, что фактически для решения каждого класса задач требовался свой подход. Кроме того, в задачах оптимизации часто возникало много "неприятных" моментов, связанных с многоэкстремальностью, невыпуклыми ограничениями, многосвязностью области допустимых решений и т.д. Одним из направлений, позволившим создать робастные и эффективные алгоритмы для широкого класса задач оптимизации было использование подкласса методов направленного случайного поиска - методов эволюционных вычислений (ЭВ).
Методы ЭВ не гарантируют обнаружения глобального решения за полиномиальное время. Однако от этого практический интерес к ним не ослабевает. Объяснить это можно тем, что методы ЭВ позволяют найти более хорошие или "рациональные" решения очень трудных практических задач поиска за меньшее время, чем другие, обычно применяемые в этих случаях методы. Конечно, термин "хорошие" или "рациональные" не строг в математическом смысле. Под "рациональными" решениями нами понимаются решения, которые удовлетворяют исследователя. Ведь в большинстве реальных задач нет особой необходимости находить именно глобальный оптимум. Чаще всего целью поисков являются решения, удовлетворяющих определенным ограничениям, например, запас прочности конструкции не должен быть менее какой-либо заданной величины. В этом смысле достаточно найти именно "рациональное", т.е. разумное решение. Вторая немаловажная причина роста популярности ЭВ заключается в стремительном росте производительности современных компьютеров.
Идея использования основных факторов популяционной генетики (кроссинговера, мутации, естественного отбора и др.) в задачах поиска оптимальных решений позволила создать широкий спектр генетических алгоритмов (ГА). Сначала идеи генетики при решении задач оптимизации использовались для самоадаптации алгоритма оптимизации. Например, в работах Ю.И.Неймарка и его учеников предлагался подход, связанный с адаптацией коллектива независимых автоматов. Начиная с работ Holland (1975) и De Jong (1985), генетическими алгоритмами стали называть алгоритмы, моделирующие природную эволюцию в пространстве оптимизируемых параметров, а не в пространстве параметров алгоритма поиска. Однако в нашей стране эти идеи не нашли пока должного внимания, хотя за рубежом проходят ежегодные конференций посвященных ЭВ и ГА, выпускаются монографии и учебники, издаются бюллетени и журналы.
Цель работы заключается в создании и исследовании эффективных генетических алгоритмов для принятия оптимально-компромиссных решений в различных областях науки и техники.
1. Для трех различных классов матмоделей принятия решений (безусловной, нелинейной, многокритериальной), которые в традиционных подходах решались своими собственными методами оптимизации, предложен и исследован эволюционно-генетический подход, робастный по отношению к этим классам задач, позволяющий эффективно находить оптимальные или квазиоптимальные и оптимально-компромиссные решения, сводя исходные задачи к единой модели поиска оптимальных вершин в многомерном гиперкубе.
2. Для представления решений в закодированном виде с использованием бинарного алфавита в отличие от других эволюционно-генетических подходов, построенных на дискретизации области допустимых решений с требуемой точностью, предлагаемая символьная модель имеет значительно больший размер "ячейки" сетки дискретизации, но позволяет задавать несколько значений фенотипа около каждого узла сетки, что сокращает вычислительные затраты на поиск оптимального решения.
3. Разработан в рамках эволюционно-генетического подхода и реализован в виде программного продукта ГА, которые в отличие от традиционных имеет следующие особенности:
- изменена стратегия формирования нового поколения из решений поколения предыдущего за счет создания репродукционного множества, аккумулирующего в себе все решения, включая как старые, так и вновь формируемые в процессе поиска, и применения оператора отбора к этому репродукционному множеству;
4. Для повышения эффективности ГА за счет выбора конкретного генетического оператора исследована возможность самоадаптации алгоритма с использованием стохастических автоматов, настраиваемых в процессе поиска.
5. За счет подбора параметров и генетических операторов ГА позволяет решать три класса задач: быстрый поиск оптимального или квазиоптимального решения, локализация наибольшего числа глобальных решений и построение 3-мерного ландшафта исследуемой модели, позволяющего отслеживать в процессе поиска пики, долины, овраги...
6. Проведен большой вычислительный эксперимент на типовых тестовых задачах в сравнении с другими методами, показавший эффективность предлагаемого ГА. Исследованы потенциальные возможности ГА в сравнении с приближенно-оптимальными методами, построенными на использовании свойств одного класса функций. Показана эффективность ГА в тех случаях, когда параметры приближенно-оптимального алгоритма подобраны неточно.
Предложенный ГА апробирован при решении двух практических задач (расчет цепной передачи и жесткости пружины), которые показали эффективность подхода и методов для принятия оптимальных решений. Разработанные модели, методы и программная реализация, предложенная в виде программного продукта, могут использоваться в качестве элемента существующих систем САПР и АСУ для оптимизации параметров проектируемых систем и систем управления. Особый интерес представляет его использование в случаях, когда принятие решений осуществляется в интерактивном режиме. Теоретические результаты, полученные при создании алгоритмов отбора в задачах многокритериальной оптимизации и при использовании стохастического автомата для управления процессом поиска, могут быть использованы при разработке ГА для задач k-разрезания графа, коммивояжера и других комбинаторных задач.
Результаты диссертации обсуждались на Всероссийском совещании-семинаре "Математическое обеспечение высоких технологий в технике, медицине и образовании" (Воронеж, 1995г.), на Всероссийском совещании-семинаре "Математическое обеспечение информационных технологий в технике, образовании и медицине". (Воронеж, 1996г.), на Всероссйской конференции "Математическое программирование и приложения" (Екатеринбург, 1997г.), на Международной конференции "Новые информационные технологии в науке, образовании и бизнесе" (Гурзуф, 1997г.), на Всероссийском совещании-семинаре "Математическое обеспечение информационных технологий в технике, образовании и медицине" (Воронеж, 1997г.), на Всероссийском совещании-семинаре "Высокие технологии в региональной информатике" (Воронеж, 1998г.), на Международной научной конференции "Оптимизация численных методов" (Уфа, 1998г.), на Всероссийской научно-практической конференции "Компьютерная геометрия и графика" (Н.Новгород, 1998г.), на XII Международной конференции "Проблемы теоретической кибернетики" (Н.Новгород, 1999г.), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.
Работа состоит из введения, шести глав, списка литературы и приложения. Общий объем работы составляет 131 страницу. Список литературы составляет 193 наименования. Основные результаты излагаются в главах 2, 3, 4 и 5.
Во введении обосновывается актуальность проблемы, указывается место генетических алгоритмов (ГА) в общем классе методов оптимизации. Обсуждаются преимущества и недостатки, а также основные сферы применимости ГА в сравнении с традиционными "классическими" методами оптимизации.
В главе 1 приводится обзор существующих математических моделей принятия решений.
В § 1.1 описаны некоторые наиболее известные методы поиска оптимальных решений для рассматриваемого класса задач. Приводятся ссылки на наиболее значительные работы в этой области как отечественных, так и зарубежных авторов.
Об истории появления и этапы развития эволюционных методов рассказано в § 1.2. Особое место уделено работам отечественных ученых, посвященных проблемам случайного поиска и автоматным моделям. Там же приводится описание простого генетического алгоритма Холланда и обсуждаются сферы применимости ГА, т.е. когда применение ГА может оказаться более выгодным по сравнению с традиционными подходами.
В § 1.3 приводится обзор различных эволюционно-генетических подходов для решения трех классов задач - безусловной многопараметрической многоэкстремальной оптимизации, нелинейного программирования и поиска компромиссных решений в многокритериальных моделях. Обсуждаются преимущества и недостатки этих подходов при решении задач определенного класса.
В главе 2 описана общая схема предлагаемого генетического алгоритма в сравнении с генетическим алгоритмом Холланда-Гольдберга. Сформулировано понятие задачи поиска в пространстве бинарных структур. Реализован базовый ГА и оценена его эффективность на классе тестовых задач.
В § 2.1 предложена новая символьная модель генетического алгоритма. Мы предлагаем использовать более короткие бинарные представления, т.е. работать с более грубой сеткой дискретизации, а не сеткой, шаг дискретизации которой равен заданной точности поиска, как это делается в традиционных ГА. Использование сетки разбивает пространство параметров на множестве равных гиперкубиков с центром в узлах сетки. При этом предлагается вычисления целевой функции будут производится не в узлах сетки дискретизации, а, например, с равной вероятность во всем гиперкубике. Соответственно, в символьную модель помимо "генотипа" (бинарной строки) мы включаем и "фенотип" (вектор из пространства параметров). Предлагаются несколько правил для генерации "фенотипов" в гиперкубиках. Использование такой модели часто позволяет значительно сократить время поиска за счет уменьшения размерности пространства бинарных строк, добиваясь практически такой же точность, что и у традиционных ГА. Рассматривается возможность использования в символьной модели вместо обычной двоичной кодировки Грея. Код Грея предпочтительнее обычного двоичного тем, что обла-дает свойством непрерывности бинарной комбинации: изменение кодируемого числа на единицу соответствует изменению кодовой комбинации только в одном разряде. Приводится геометрическая интерпретация задачи поиска. Пространство поиска - множество всех бинарных строк представлений. Это пространство можно представить в виде трехмерного куба, вершинам которого соответствуют кодовые комбинации, расставленные так, что хэмминингово расстояние между смежными вершинами равно 1. Задача алгоритма поиска заключается в том, чтобы, следуя некоторому правилу, перемещаться в новые вершины этого куба, что будет соответствовать исследованию новых областей в пространстве оптимизируемых параметров. Здесь же формулируется понятие шима (schema) - шаблон схожести бинарных структур, - позволяющее описать особенности поведение ГА и доказать некоторые свойства генетических операторов. В заключении параграфа приводится краткий обзор других недвоичных кодировок, используемых некоторыми ГА исследователями при построении символьных моделей алгоритмов.
В § 2.2 приводится схема нового ГА.
НАЧАЛО /* генетический алгоритм */
/* формирование начальной совокупности решений P0 ={aK0}*/
сгенерировать начальную совокупности строк S0
сформировать векторы начального множества решений X0=e-1(S0)
оценить начальные решения P0: m (S0)
t = 0 /* счетчик итераций */
/* процедура поиска */
ПОКА НЕ выполнено условия останова ПОВТОРИТЬ
НАЧАЛО
Rt=Pt/* репродукционное множество */
ДЛЯ p = 1 до p = Np ПОВТОРИТЬ
НАЧАЛО
выбрать ait и ajt из Pt:
ait, ajt = B(Pt)
s2p-1t+1/2, s2pt+1/2 = С(ait,ajt)
x2p-1t+1/2 = e-1(s2p-1t+1/2)
x2pt+1/2 = e-1(s2pt+1/2)
оценить новые решения a2p-1t+1/2 и a2pt+1/2:
m(s2p-1t+1/2) и m(s2pt+1/2)
Rt = Rt U {a2p-1t+1/2,a2pt+1/2}
КОНЕЦ
С вероятность Pm для каждого решения (k=1,2,…) ПОВТОРИТЬ
НАЧАЛО
s2Np+kt+1/2 = M(am), am из Rt
x2Np+kt+1/2 = e-1(s2Np+kt+1/2)
оценить новое решение a2Np+kt+1/2: m(s2Np+kt+1/2)
Rt = Rt U {a2Np+kt+1/2}
КОНЕЦ
Оператор отбора S: Rt -> Pt+1
t = t+1
КОНЕЦ
КОНЕЦ
Прежде всего отличие от классических ГА-мов состоит в сохранении вещественных векторов решений (что позволят использовать более короткие представления, практические не теряя точности). Вторым важным отличием является порядок реализации основных генетических операторов. Вначале проходит стадия "воспроизводства" новых решений, включающая в себя три элемента:
1. Выбор элементов ait и ajt (брачная пара), используя правило B /breeding/.
2. Генерация новых решений с помощью оператора "кроссовер" C /crossover/
3. Локальные изменения некоторых решений с помощью оператора "мутации" M /mutation/.
И лишь затем осуществляется процедура построения совокупности решений для следующей итерации ("поколения") из всего множества доступных к тому моменту решений - оператор S.
В-третьих, представленный алгоритм допускает появление k >> 1 новых решений, накапливаемых в репродукционном множестве, прежде, чем включится процесс отбора, отбрасывающий лишние k решений.
В этом же параграфе предлагается новая схема формирования начальной популяции P0. Эта схема строится на гарантировании максимального побитового разнообразия в начале поиска...
В § 2.3 представлена реализация основных генетических операторов для генерации новых решений: "кроссовера" и "мутации". Приводится описание одноточечного, двухточечного и равномерного кроссовера, точечной мутации. Используя ссылки на литературу по ГА, обсуждается вопрос о предпочтительности того или иного оператора. Далее в § 2.6 мы вернемся к этому вопросу, проводя вычислительный эксперимент с новым ГА.
Отдельно рассмотрен вопрос формирования "родительских" пар. Приводятся несколько правил: "панмиксия", "аутбридинг" и "инбридинг".
Первый подход самый простой и, возможно, самый распространенный - брачная пара формируется случайным образом ("панмексия"), т.е. обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции, причем любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Его универсальность основана на "непредсказуемости" включения особи в брачную пару.
Чтобы не допускать преждевременной сходимости алгоритма к "подоптимальным" решениям, т.е. постоянно поддерживать в популяции генетическое разнообразие потенциальных решений, предлагается другой способ выбора родительских особей. Его принцип основан на скрещивании родителей обладающих дальним родством. Под "родством" двух особей здесь будем понимать хэммининговое расстояние между их хромосомными наборами. Такой способ называют "аутбридингом".
При такой схеме выбора родителей брачную пару с большей вероятностью будут составлять особи с максимально различными хромосомными наборами.
Третий способ, который мы тоже исследовали в нашей работе - это "инбридинг". Реализация инбридинга напоминает аутбридинг с той лишь разницей, что предпочтение при формировании пар отдается "близкородственным" особям.
Инбридинг полезен при формировании локальных групп около нескольких глобальных решений в многоэкстремальных задачах на заключительных этапах поиска. В силу этих причин инбридинг рассматриваться нами не как основной, а как дополнительный способ формирования брачных пар на последней стадии поиска. В § 2.4 приводятся несколько наиболее распространенных схем естественного отбора. В их числе пропорциональный, турнирный, линейный ранговый, экспоненциальный ранговый отбор, отбор отсечением. Несмотря на популярность, эти схемы отбора оказываются бессильны для локализации нескольких глобальных решений. Поэтому исследователями предлагались различные "нишевые" подстройки для алгоритмов, группирующие популяцию решений около нескольких решений. В своей работе мы решили не использовать такие "подстройки", а попытались предложить свой метод, который бы одинаково эффективно работал и с унимодальными и с многоэкстремальными функциям, и был бы более адекватен новой символьной модели. В § 2.5 предлагаются две такие схемы естественного отбора.
Первая - это "элитный" отбор. Этот метод основан на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей, их потомков и мутантов. Быстрая сходимость, обеспечиваемая элитным отбором, может быть, когда это необходимо, с успехом компенсирована подходящим методом выбора родительских пар, например аутбридингом.
Здесь же приводятся некоторые вероятностные оценки появления и выживания в популяции субоптимальных, т.е. максимально похожих на оптимальные, решений при использовании элитного отбора и равномерного кроссовера. В нашем генетическом алгоритме мы применяем символьную модель, допускающую существование в популяции решений обладающих одинаковыми хромосомными наборами, но разными фенотипическими признаками, т.е. одинаковыми строками представлений, но разной мерой приспособленности. Учитывая эту особенность, нами предложен новый метод отбора, названный отбор вытеснением. Отбор вытеснением носит бикритериальный характер - то, будет ли особь из репродукционной группы заноситься в популяцию нового поколения, определяется не только величиной ее приспособленности, но и тем, есть ли уже в формируемой популяции следующего поколения особь с таким же хромосомным набором. Из всех особей с одинаковыми генотипами предпочтение сначала, конечно же, отдается тем, чья приспособленность выше. Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие. Вытеснение в данном случае формирует новую популяцию скорее из далеко расположенных особей, вместо особей, группирующихся около текущего найденного решения. Этот метод особенно хорошо себя показал при решении многоэкстремальных задач, при этом помимо определения глобальных экстремумов появляется возможность выделить и те локальные максимумы, значения которых близки к глобальным.
Тестовые задачи и вычислительный эксперимент с использованием новых подходов описан в § 2.6. Оценка качества предлагаемого алгоритма и частных генетических операторов проводилась по нескольким направлениям: во-первых, сравнение эффективности поиска в зависимости от выбранной символьной модели, в том числе от длины хромосомного набора, во-вторых, зависимость улучшения значения приспособленности особей популяции от параметров генетического алгоритма, прежде всего метода выбора родительских пар и реализации механизма отбора. Кроме того, помимо количественных оценок приводится качественное описание поведения популяции, управляемой генетическим алгоритмом при тех или иных параметрах.
Оценка алгоритма проводилась на ряде тестовых функций. Это прежде всего несколько тестовых функций De Jong'а, которые часто используются для проверки эффективности новых генетических алгоритмов, кроме того, были использованы сложные многоэкстремальные функции высокой размерности, практически нерешаемые классическими методами.
Представленный алгоритм обладает достаточно широкими возможностями, - настроив соответствующим образом параметры системы, можно управлять процессом поиска в зависимости от поставленной задачи. С помощью представленного алгоритма выработана методика для решения трех классов:
· задача быстрой локализации одного оптимального значения,
· задача определения нескольких (или всех) глобальных экстремумов,
· задача описания ландшафта исследуемой функции, которая может сопровождаться выделением не только глобальных, но и локальных максимумов.
Основное различие в методах решения этих трех задач лежит в реализации различных уровней соотношения, которое в теории генетических алгоритмов называется как соотношение "исследование - использование". Быстрый поиск одного экстремума, как правило, достигается использованием параметров, которые способствуют максимально быстрой сходимости за счет манипулирования только особями, обладающими лучшей приспособленностью, при этом более "слабые" члены популяции не участвуют в формировании родительских пар и не выживают после процедуры отбора. Для решения второй задачи, очевидно, вопросу "исследования" пространства поиска должно уделяться гораздо большее внимание. Оно достигается за счет другого сочетания параметров и достаточно большой численности популяции, при этом ГА сможет выделить несколько (или даже все) глобальные экстремумы. И наконец третья задача. Особенность ее решения состоит в том, что при достаточно большом размере популяции и небольшом заданном количестве брачных пар проявляется интересное свойство поведения генетического алгоритма: в процессе поиска проявляются черты рельефа ландшафта функции приспособленности (овраги, холмы, долины). Оставляя области, которым соответствуют меньшая приспособленность, ГА группирует особи ближе к вершинам холмов, в область притяжения которых они попали. Это эквивалентно определению локальных экстремумов, значения которых близки к оптимальным.
В главе 3 изложены несколько подходов, позволяющих применять ГА для решения задач невыпуклого нелинейного программирования с одним критерием.
В § 3.1 приводится постановка задачи многопараметрического нелинейного программирования. В общем случае исследуемая многопараметрическая функция может быть многоэкстремальной, недифференцируемой, нелипшицируемой, допускается также нефункциональное или алгоритмическое задание этой функции. Допустимая область, задаваемая нелинейными ограничениями, может быть невыпуклой и состоящей из нескольких компонент связности. Описаны основные параметры используемого генетического алгоритма и предложены три эвристических приемов.
1. Динамическое изменение длины кодировки, начиная с 8 бит на каждый ген и доводя длину гена к 100-му поколению до 12.
2. Использование макромутации. Макромутация заключается в отклонении всех членов популяции (кроме нескольких лучших особей), используя нормальное распределение после каждого 20-ого поколения, не принесшего улучшения приспособленности лучшей особи. Такой нехитрый прием позволяет иногда "выбивать", в случае необходимости, популяцию из локальных решений.
3. Поскольку генетический алгоритм в том виде, в котором он описан, направлен на поиск оптимального гиперкубика, соответствующего "оптимальной" хромосоме, поиск решения с приемлемой точностью в гиперкубике фактически превращается в случайный поиск. Поэтому окончание поиска, - последние 20 поколений - сопровождалось нами сужением пространства поиска до окрестности найденного решения. Безусловно, при таком сужении полностью исключается выход из области притяжения этого решения, поэтому этот прием применяется в конце поиска, когда предполагается, что глобальное решение локализовано.
В § 3.2 описано применение алгоритма для решения задач с ограничениями, используя методы штрафных сверток. Приводится обзор предлагавшихся ранее методов штрафа для использования с ГА. Обсуждаются преимущества и недостатки этих методов.
Предлагается новый способ, который достаточно легко модифицируется для нескольких систем ограничений, поскольку при решении реальных задач часто возникает ситуация, когда допустимая область S является объединением нескольких областей SP
...
В §3.3 рассмотрена возможность сведения ряда задач с ограничениями к задаче безусловной оптимизации путем замены переменных. Мы реализовали этот подход для задач, область допустимых решений которых, - сфера единичного радиуса.
Хотя замена переменных позволяет избавиться от ограничений на параметры, ее применение может привести к следующим трудностям при решении задачи безусловной оптимизации:
- новая целевая функция может оказаться неограниченной для некоторых значений новых переменных
- степень нелинейности новой целевой функции может возрасти
- новая целевая функция может стать периодической по новым переменным z и т.д.
На классе тестовых примеров в § 3.4 подтверждена эффективность предложенного метода. В качестве примеров были выбраны несколько задач невыпуклого программирования, в том числе задачи с многосвязной допустимой области. Эффективность предлагаемого алгоритма оценивалась на тестовых задачах высокой размерности, взятых из литературы по ГА. На нескольких примерах с допустимой областью "сферой" мы сравнили метод штрафов и замены переменных.
В главе 4 обсуждаются вопросы модификации алгоритма для решения многокритериальных задач. Исторически так сложилось, что несколько критериев объединялись в форму скалярной целевой функции, обычно используя линейную комбинацию (взвешенную сумму) нескольких критериев или превращая функции цели в ограничения. С другой стороны генетические алгоритмы хорошо зарекомендовали себя в качестве методик поиска в больших областях практически при полном отсутствии информации о свойствах целевой функций и ограничений, однако они в основном используются для решения задач с одним критерием. В простейшем варианте для создания многокритериального ГА логично совместить методы сверки векторных критериев с ГА, работающим с одной целевой функцией. Нами предлагается альтернативный, и как нам кажется более эффективный и более адекватный задаче и идеологии ГА, подход. Этот подход предполагает модификацию ГА для работы с вектором критериев, включив идею парето-доминирования в операторы естественного отбора и используя специальные методики для равномерного "размазывания" решений вдоль парето-границы.
В § 4.1 ставится задача построения области компромиссов и парето-границ для многокритериальных моделей.
В § 4.2 вводится модификация символьной модели алгоритма для векторной функции приспособленности. Теперь приспособленность особи оценивается не скалярной величиной, а вектором, число компонент которого совпадает с числом критериев исходной задачи.
Специфика нового класса задач привела к необходимости создания специальных операторов многокритериального отбора. Главное отличие новых операторов заключается в использовании принципа доминируемости решений. Такой оператор отбора предлагается в § 4.3. Здесь же формулируется понятие ранга доминируемых решений, соответствующее количеству особей из текущей популяции, доминирующих эту особь. Также вводится специальное множество, в котором до последнего поколения поиска накапливаются отбрасываемые недоминируемые решения. На случай, когда количество несравнимых (недоминируемых) решений больше или меньше текущего размера популяции, предложены дополнительные процедуры. Первая позволяют из всего множества несравнимых решений выбирать только те, которые равномерно распределены вдоль парето-границы. Вторая процедура описывает правила, по которым "добирается" популяция для следующего поколения, если в репродукционном множестве не хватает недоминируемых решений. Это могут быть как доминируемые решения с наименьшим рангом, так и решения из множества, в которое помещаются удаляемые первой процедурой недоминируемые решения. Естественно "недоминируемость" этих решений пересматривается на каждом поколении поиска.
В § 4.4 на классе бикритериальных тестовых примеров проиллюстрирована работоспособность предложенных подходов, в том числе и в задачах с невыпуклой и разрывной парето-областью. Основной целью вычислительных экспериментов была проверка работоспособности предлагаемого оператора многокритериального отбора. Получено практическое подтверждение идеи о равномерном распределении решений вдоль парето-границы.
В главе 5 приводится описание программного комплекса для решения всех трех классов задач. Общие возможности программы, класс решаемых задач, необходимые системные требования указаны в § 5.1.
В § 5.2 даются рекомендации по настройке параметров алгоритма для решения одного из классов задач. Описан порядок работы в различных режимах поиска решений: одиночный запуск или сбор статистической информации, с различными критериями остановки алгоритма.
В § 5.3 приводится описание реализованных средств визуализации хода поиска и найденных решений. Правила подключения внешних модулей для новых оптимизационных задач пользователя указаны в § 5.4.
В главе 6 приводятся результаты экспериментально-теоретического сравнения предложенного алгоритма с приближенно-оптимальным алгоритмом, построенном на минимаксном подходе. Приближенно-оптимальный алгоритм строился для одного класса задач с четко сформулированными свойствами. Целью исследований была проверка того, на сколько генетический алгоритм окажется более (или менее) эффективным инструментом поиска по сравнению с приближенно-оптимальным минимаксным алгоритмом в случае: а) если два параметра, определяющие свойства целевой функции, известны точно и б) если эти параметры заданы неверно
...
В § 6.1 формулируются задача поиска глобального экстремума функции из класса FK(p), задаваемого двумя условиями
...
Класс FK(p) содержит вогнутые, выпуклые, удовлетворяющие условию Липшица функции и замкнут относительно ряда естественных операций: суммирования с неотрицательными коэффициентами, взятия минимума, максимума по конечному набору функций и т.п., замкнут относительно основных операций свертывания векторного критерия и содержит вогнутые, выпуклые, удовлетворяющие условию Липшица функции.
В § 6.2 описан приближенно-оптимальный алгоритм для одномерной функции из класса ФK(p). Для поиска глобального решения строится огибающая кусочно-выпуклая (или кусочно-вогнутая в зависимости от значения параметра p) мажоранта. Поиск осуществляется путем вычисления и сравнения значений функции в произвольных точках отрезка - области определения. В качестве критерия оптимальности при построении алгоритма рассматривалась точность в определении экстремального значения функции.
В § 6.3 описаны результаты вычислительного эксперимента по применению построенного алгоритма для отыскания экстремального значения нескольких тестовых функций двух переменных из класса FK(p), где K=0, p=1.
Решение таких задач осуществлялось с помощью схемы повторной оптимизации.
На тестовых функциях экспериментально показано, что генетический алгоритм всегда превосходить метод, построенный на использовании свойств функции, если эти свойства определены априори неточно.
И, наконец, в приложение вынесены результаты решения двух реальных задач оптимального проектирования: расчета зубчатой передачи и расчета жесткости пружины.
Задача расчета зубчатой передачи, состоящей из четырех шестерен, заключается в определении числа зубцов на каждой из шестерен. При этом требуется минимизировать ошибку между получаемым и требуемым (1/6.931) коэффициентом зубчатой передачи. Четыре переменные в задаче (y1, y2, y3, y4) - количество зубцов на шестеренках - обязательно целые числа.
Это дискретная задача с многоэкстремальной нелинейной целевой функцией. Целочисленные переменные изменяются в диапазоне (12,60). Мощность пространства решений составляет 494. Чтобы иметь возможность применять ГА, работающий, вообще говоря, с непрерывными моделями, мы ввели новые вещественные переменные x1, x2, x3, x4, изменяющиеся на отрезке [12, 61], и использовали замену xi=int(yi) .
Вторая задача - задача расчета жесткости пружины. Задача имеет три варьируемых параметра - количество витков пружины N, диаметр проволоки d и диаметр витка D. Число витков N - целочисленная переменная, изменяемая от 1 до 32, диаметр пружины d - одно из 42 значений (заданы таблично) в диапазоне от 0.0090 до 0.5 (в дюймах), диаметр витка пружины D - непрерывная величина. Помимо нелинейной целевой функции задача имеет семь линейных и нелинейных ограничений. С математической точки зрения, это нелинейная, многоэкстремальная дискретно-непрерывная задача оптимизации.
Проведенные вычислительные эксперименты и решение реальных задач оптимального проектирования показали, что предлагаемый ГА является достаточно эффективным инструментом для принятия оптимальных решений в сложных нелинейных дикретно-непрерывных системах.
По теме диссертации опубликовано 17 работ, 3 работы направлены в печать.
Основные результаты диссертации опубликованы в следующих работах:
Исаев Сергей
e-mail: saisa@mail.ru
web: http://saisa.chat.ru