Содержание к диссертации
Введение
1. Анализ и формализация задач синтеза систем управления космическими аппаратами 9
2. Анализ традиционных методов многокритериальной оптимизации 59
3. Эволюционные алгоритмы в многокритериальной оптимизации 78
4. Программная система GAST 111
Выводы 146
Заключение 146
Литература 148
Приложение
- Анализ и формализация задач синтеза систем управления космическими аппаратами
- Анализ традиционных методов многокритериальной оптимизации
- Эволюционные алгоритмы в многокритериальной оптимизации
- Программная система GAST
Введение к работе
Сложившаяся в настоящее время экономико-политическая ситуация в нашей стране существенно отразилась на процессах разработки и совершенствования космической техники, объемах космических исследований. Различные социально-экономические факторы оказывают негативное влияние на развитие российской космической индустрии. К ним можно отнести различного рода финансовые и политические кризисы, существенное снижение объема государственных заказов и жесткая конкуренция, как с российскими, так и с зарубежными фирмами. Все это, в конечном итоге, приводит к снижению темпов развития и совершенствования космической техники в нашей стране, потери приоритета среди космических держав, снижению обороноспособности государства.
В связи с этим, одними из главных задач, стоящих перед российскими специалистами сегодня, являются задачи создания, эффективного использования и расширения возможностей имеющегося технического парка, а также обеспечения наиболее эффективного управления как существующими, так и проектируемыми системами космических аппаратов (КА). Исходя из того, что КА является сложной технической системой, состоящей из множества подсистем, каждая из которых характеризуется собственным набором параметров эффективности, большинство задач оптимизации, возникающих при проектировании систем управления КА, обладают свойствами, делающими их исключительно сложными для решения. Этими свойствами являются, например, смешанные переменные, наличие многих критериев, заданных в алгоритмическом виде, многомодальность и др .
Преодолению проблем, связанных с многошкальностью, многомодальностью и алгоритмичным заданием целевых функций и ограничений задач оптимизации, посвящены многие работы, в частности диссертации [58,1,12]. Проблеме многокритериальное™ также уделялось достаточно внимания. В работах [2,21] практические задачи проектирования сложных систем сводились к задачам псевдобулевой оптимизации, для которых в дальнейшем предлагались автоматические и человеко-машинные процедуры порождения эффективных точек и сужения множества Парето, в частности в [2] предлагалось использовать обычные процедуры сведения многокритериальной задачи к однокритериальной, а в работе [21] главное внимание уделялось процедурам сужения множества Парето и получения дополнительной информации от ЛПР. В работе [30] был предложен метод, основанный на стандартных процедурах сведения многокритериальный постановки задачи к однокритериальной, которые в качестве основного оптимизационного алгоритма использовали генетический алгоритм.
Анализ этих и других научных работ позволил сделать вывод, что несмотря на разнообразие подходов к решению практических многокритериальных задач вопрос представительного порождения точек Парето подробно не рассматривался. Суть проблемы в том, что при потенциально бесконечном множестве эффективных решений, стандартные процедуры многокритериальной оптимизации имеют тенденцию сходимости только в несколько из них (в том числе и одну). Особенно сложным является случай с несвязными множествами Парето.
Таким образом, для эффективного решения поставленных практических задач необходимо разработать более тонкий метод (или совокупность методов), специально ориентированный на работу с множеством критериев и генерирование более представительного множества альтернатив. Одним из перспективных направлений является предложенный в данной диссертационной работе метод эволюционного поиска, который совместно с механизмом долевой пригодности способен быстро и качественно решать указанные оптимизационные задачи. Двумя словами можно охарактеризовать этот синтез следующим образом. В процессе оптимизации эволюционный поиск решает многокритериальную задачу оптимизации, в то время как механизм долевой пригодности, равномерно распределяет поисковые точки вдоль всего Парето-фронта. На заключительном этапе принятия решений механизм долевой пригодности применяется в качестве метода равномерного сужения полученного множества Парето.
Диссертация посвящена разработке эффективного математического и программного обеспечения, предназначенного для решения сложных задач многокритериальной оптимизации и способного создавать представительную выборку Парето-оптимальных решений.
Целью диссертационной работы является создание эффективного математического, алгоритмического и программного обеспечения решения многокритериальных задач выбора оптимального варианта систем управления КА.
Для достижения этой цели решались следующие задачи:
• изучение и анализ реальных систем управления КА, выявление особенностей и проблем, возникающих при выборе вариантов технологического, целевого и командно-программного контуров;
• построение математических моделей, формально описывающих задачи, к которым сводятся процедуры выбора эффективных вариантов технологического, целевого и командно-программного контуров;
• определение основных проблем (с точки зрения оптимизации), возникающих в процессе формализации, моделирования и решения задач выбора;
• разработка, обоснование и программная реализация алгоритмов многокритериальной оптимизации, решающих поставленные задачи;
• решение с помощью построенных моделей и разработанной программной системы задач выбора эффективных вариантов технологического, целевого и командно-программного контуров;
Методы исследования. Для решения поставленных задач использовались методы теории систем и системного анализа, теории вероятностей и математической статистики, теории многокритериальной оптимизации и дискретной математики.
Научная новизна результатов, полученных в диссертации, состоит в следующем:
1. Задачи выбора эффективных вариантов технологического, целевого и командно-программного контуров системы управления КА сформулированы и решены как задачи многокритериальной оптимизации алгоритмически заданных функций смешанных переменных.
2. Предложен новый подход к обеспечению представительной аппроксимации множества решений сложных задач многокритериальной оптимизации - механизм долевой пригодности в критериальном пространстве.
3. Обоснован, разработан и исследован новый метод эволюционного поиска, отличающийся тем, что в нем при реализации оператора селекции используется механизм долевой пригодности, что позволяет автоматически строить представительную аппроксимацию множества Парето и затем успешно решать задачу сужения этого множества на основе анализа предпочтений ЛПР.
4. С помощью программной системы, разработанной на базе созданных алгоритмов, впервые решены практические задачи выбора эффективных вариантов технологического, целевого и командно-программного контуров как задачи многокритериальной оптимизации.
Практическое значение. Данная работа выполнялась как составная часть госбюджетной комплексной программы «Прогресс-96», а также в рамках договора о содружестве НИИ СУВПТ и НПО ПМ (г. Железногорск) и заказ-нарядов НИИ СУВПТ 2.1.98Ф «Разработка методов высокоточного удержания геостационарных КА на долготе и широте», 2.2.98Ф «Разработка системы поддержки планирования функционального управления космическими аппаратами», 2.4.98Ф «Исследование теоретических предпосылок выбора вариантов сложных систем на основе адаптивных поисковых методов и интеллектуальных информационных технологий», финансируемых из средств федерального бюджета. Кроме того, работа поддерживалась Немецкой службой академического обмена (ДААД) и грантом фонда аэропорта г. Франкфурт-на-Майне (Германия). Разработанные алгоритмы, построенная на их основе программная система GAST, предназначенная для решения проблем многокритериальной оптимизации, а также результаты решения практических задач переданы в НПО прикладной механики, горно-химическому комбинату (г. Железногорск), Сибирскому отделению Инженерной Академии РФ, «Красэнерго» и Сибирской аэрокосмической академии. Результаты диссертационной работы используются в учебном процессе кафедры СА и ИО САА при обучении студентов по курсам «Теория оптимизации», "Системы искусственного интеллекта" и "Адаптивные эволюционные методы поддержки принятия решений", а также при выполнении лабораторных работ и курсовых проектов по данным курсам. Получены положительные отзывы пользователей программной системы.
Основные защищаемые положения.
1. Предложенный в работе метод эволюционного поиска в совокупности с механизмом долевой пригодности позволяет осуществлять многокритериальный выбор эффективных вариантов систем управления КА.
2. Предложенный метод эволюционного поиска позволяет успешно решать любые задачи многокритериальной оптимизации алгоритмически заданных функций смешанных переменных.
3. Разработанная на базе предложенных алгоритмов программная система GAST позволяет эффективно решать поставленные практические задачи, строить представительную аппроксимацию множества Парето, осуществлять его анализ и равномерное сужение.
4. При моделировании Марковских случайных процессов, протекающих в рассматриваемых технических системах, применение разработанного программного инструмента Соната позволяет быстро и качественно строить системы уравнений Колмогорова-Чепмэна, формировать наборы коэффициентов для подпрограмм решения соответствующих уравнений, визуализировать граф состояний рассматриваемой системы.
5. Возможность организации распределенных вычислений на базе разработанной программной системы позволяет решать особо сложные и ресурсоемкие практические задачи оптимизации.
Апробация работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на научных семинарах кафедры СА и ИО, секции информационных технологий Сибирского отделения Инженерной Академии РФ, международном симпозиуме по исследованию операций (Берлин, 1994), международной конференции "Адаптивные вычисления в инженерном проектировании и управлении" (Плимут, 1994), международной научно-технической конференции "Динамика систем, механизмов и машин" (Омск, 1995), научно-практической конференции "Информатизация региона" (Красноярск, 1996), Всероссийской научно-практической конференции "Решетневские чтения" (Красноярск, 1998), Всероссийской конференции "Перспективные материалы, технологии, конструкции" (Красноярск, 1998).
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений.
Анализ и формализация задач синтеза систем управления космическими аппаратами
Прежде чем формализовать задачи, возникающие при синтезе управления космическими аппаратами и выборе варианта системы управления, необходимо рассмотреть состав самого космического аппарата (КА) и его системы управления [3,22]. Космический аппарат связи и ретрансляции ( а именно этот тип рассматривается в настоящей работе) состоит из следующих основных подсистем: ? Бортовой ретрансляционный комплекс (БРК). Бортовой ретрансляционный комплекс выполняет целевые функции космического аппарата - передачу информации между наземными абонентами. Как правило, на базе БРК нескольких космических аппаратов организуются магистральные и международные линии связи, линии связи с удаленными и труднодоступными пунктами, сети деловой связи и передачи данных, системы спутникового телевизионного вещания. ? Система ориентации и стабилизации (СОС). Система ориентации и стабилизации обеспечивает необходимую ориентацию космического аппарата в пространстве в различные периоды его существования на орбите. ? Система электропитания (СП). Система электропитания обеспечивает бортовые системы энергией для их нормального функционирования. Основу системы составляют солнечные батареи, которые в процессе штатного функционирования космического аппарата постоянно ориентированы на солнце терморегулирования СГтерморегулирования поддержание температурно влажностного режима внутри термоконтейнера, а также поддержание требуемого температурного режима приборов, расположенных как внутри термоконтейнера, так и за его пределами. ? Система коррекции (СК). Система коррекции обеспечивает возможность изменения параметров орбиты космического аппарата как после его выведения на орбиту, так и в процессе его штатного функционирования. ? Механические системы (МС). Механические системы обеспечивают раскрытие всех элементов конструкции космического аппарата после его отделения от ракеты-носителя. ? Бортовой комплекс управления (БКУ). Бортовой комплекс управления является управляющим элементом космического аппарата и обеспечивает контроль и управление бортовыми системами космического аппарата в реальном масштабе времени, а также реализует программно-временное управление бортовыми системами. Кроме того, бортовой комплекс управления обеспечивает взаимодействие с наземными средствами управления.
Все бортовые системы космического корабля с точки зрения рассматриваемых задач оптимизации подразделяются на три основных типа: - целевые системы: БРК; - служебные системы: СОС, СП, СТ и МС; - управляющие системы: БКУ. В период штатного функционирования космического аппарата необходимо проводить следующие работы: - осуществлять контроль функционирования бортовых систем космического аппарата и контроль их технического состояния; - управлять режимами работы всех бортовых систем, включая режимы БРК; - закладывать в БКУ командно-программную информацию для обеспечения режима программно-временного управления бортовыми системами КА в период его автономного функционирования (без взаимодействия с наземными средствами управления через бортовой комплекс управления); - обеспечивать включение в работу резервных блоков и подсистем в случае выхода из строя основных элементов; - управлять восстановлением работоспособности бортовых систем в случае появления отказов и неисправностей; - управлять движением космического аппарата на орбите - удерживать его на рабочей орбите и при необходимости переводить на другую рабочую орбиту; - управлять движением корабля вокруг центра масс; - управлять проведением профилактических работ.
Решение перечисленных задач управления обеспечивает автоматизированная система управления космическими аппаратами, в состав которой входят наземный комплекс управления (НКУ) и космических аппаратов. Таким образом, понятие автоматизированной системы управления (АСУ) космическими аппаратами является понятием функциональным. Мы можем говорить об АСУ одним или несколькими космическими аппаратами в зависимости от того, взаимодействует или нет НКУ с этими аппаратами. Структурная схема АСУ несколькими космическими аппаратами представлена на рис. 1.1.1.
Наземный комплекс управления для решения задач управления взаимодействует с БКУ космических аппаратов, для чего на пунктах управления (ПУ) имеются соответствующие системы, состав и функции которых рассматриваются ниже.
Пункты управления расставлены по территории России определенным образом и связаны через систему коммуникации с Центром управления космическими аппаратами (ЦУ). В ЦУ производится обработка поступающей через средства ПУ информации, передаваемой БКУ, а также формируется и передается на борт КА через средства ПУ программно-командная информация для решения перечисленных задач управления космическими аппаратами.
В АСУ космическими аппаратами реализуется сеансовый принцип управления, который заключается в следующем: для каждого космического аппарата в течение суток выделяются один или несколько интервалов времени, так назьшаемые сеансы связи, в которых осуществляется взаимодействие одного из ПУ с данным космическим аппаратом.
Понятно, что в один и тот же момент времени различные ПУ могут производить сеансы с различными космическими аппаратами, но один и тот же ПУ не может работать одновременно с несколькими космическими аппаратами.
Анализ традиционных методов многокритериальной оптимизации
Большинство задач оптимизации, возникающих при проектировании или планировании систем управления сложными объектами, в том числе и космическими аппаратами, обладают свойствами, делающими эти задачи исключительно сложными для решения. Как уже упоминалось в первой главе, такими свойствами являются, например, смешанные переменные, наличие многих критериев, заданных в алгоритмическом виде, многомодальность и др. [50]. Преодолению проблем связанных с многошкальность многомодальностью и алгоритмическим заданием целевых функций и ограничений задач оптимизации посвящены многие работы, в частности диссертации [1,12,58]. Проблеме многокритериальности также уделялось достаточно внимания (см., например, [50,2,21,30]).
В работах [2,21] практические задачи проектирования сложных систем сводились к задачам псевдобулевой оптимизации, для которых в дальнейшем предлагались автоматические ([2]) и человеко-машинные ([21]) процедуры порождения эффективных точек и сужения множества Парето, в частности в [2] предлагалось использовать обычные процедуры сведения многокритериальной задачи к однокритериальной [47]. В каждом из предложенных [47] методов задача многокритериальной оптимизации заменяется к одной или нескольким задачам однокритериальной оптимизации. Чтобы сгенерировать множество Парето, методы должны работать многократно. Все указанные методы делятся на несколько групп согласно базовым принципам избавления от многокритериальности: свертка критериев, метод уступок, дискриминационный подход, целевое программирование, управление по идеалу, метод взвешенного критерия, минимаксный подход.
Такая модель получила название принципа равномерной оптимальности [9]. Она обычно используется в задачах, в которой критерии выражаются в одних и тех же единицах измерения. Легко видеть, что принцип равномерной оптимальности применим далеко не всегда. Его основным недостатком является возможность компенсации недопустимо малых значений некоторых критериев достаточно большими значениями других.
Этот принцип является едва ли не самым древним из всех принципов оптимальности [34]. Он весьма популярен и встречается во многих работах. Здесь задача многокритериальной оптимизации преобразуется в задачу однокритериальной оптимизации с обобщенным критерием, равным произведению исходных критериев : Недостатком данного подхода является невозможность оценить физический смысл глобального качества если критерии имеют различные единицы измерения. Пользователь должен указать весовые коэффициенты. Вместо суммы можно использовать произведение критериев, возведенных каждый в свою степень. В результате решения такой задачи по свертке обычно получают Парето оптимальную точку. Метод сверток, несмотря на его достаточно широкую популярность, имеет ряд недостатков: не всегда потеря качества по одному критерию компенсируется приращением по другому. «Оптимальное» по свертке решение может характеризоваться низким качеством некоторых частных критериев и, следовательно, будет неприемлемым, не всегда можно достаточно корректно задать веса критериев. Зачастую известна лишь сравнительная важность критериев, величина обобщенного критерия, полученная по свертке не имеет никакого физического смысла, многократный запуск алгоритма свертки может выдавать только несколько наиболее легко достижимых Парето точек, даже если в действительности существенно больше. Сначала решаются задачи оптимизации по каждому критерию в отдельности при исходной системе ограничений и отбрасывании остальных критериев. В результате получаем соответствующе оптимальное значение функции ft (х). Затем критерии упорядочиваются по важности и решается последовательность однокритериальных задач оптимизации по каждому критериев при дополнительных ограничениях на предыдущие по важности критерии, которые объявляют допустимые отклонения (уступки) от ранее найденных оптимальных значений.
Кроме главного критерия ЛПР должен также указать величины ограничений на остальные. В общем случае дискриминационный подход используется для сокращения количества частных критериев. В этом случае только несколько критериев остаются в роли целевых функций, а остальные уходят в ограничения. Проблемой здесь является выбор главного критерия и установки ограничений на остальные. При слишком жестких ограничениях может возникнуть опасность получения пустого допустимого множества, при слишком слабых -неудовлетворительного решения по некоторым исходным критериям.
Вариантом этого метода может являться подход, при котором главными назначаются все исходные критерии по очереди, а полученные результаты затем сравниваются. Минимизация расстояния до целевой точки в L2 метрике. Многокритериальная задача заменяется однокритериальной, где в качестве целевой функции выбрана сумма квадратов отклонений критериев от заданных целей у{. р F(x) = (/;( )-у{)2 - mm, і = І,...,/?. Пользователь должен указать цели, которыми могут быть и заранее вычисленные частные минимумы критериев. Выполняется минимизация суммарного относительного отклонения целевых функций от их частных минимумов в Lj и L2 -нормах. Предполагается, что все критерии равнозначны.
Эволюционные алгоритмы в многокритериальной оптимизации
Многочисленные исследования [80,61,66,98,96,92,68,69] ярко продемонстрировали, что моделирование поисковых процессов естественной эволюции могут создавать весьма стабильные вычислительные алгоритмы, несмотря на некоторые упрощения по сравнению с биологической реальностью. Полученные таким образом эволюционные алгоритмы базируются на коллективном процессе обучения внутри некоторой популяции индивидов, каждый из которых представляет собой поисковую точку в пространстве потенциальных решений конкретной проблемы. На первоначальном этапе популяция произвольным образом инициализируется, и затем, в процессе развития поиска, все лучшие и лучшие области поискового пространства вовлекаются в процесс оптимизации посредством операторов селекции, рекомбинации и мутации. Окружающая среда, т.е. само пространство поиска, предоставляет качественную информацию для каждого индивида (в простейшем случае - значение целевой функции), на основании которой определяется репродуктивная пригодность этого индивида в следующих поколениях. Оператор селекции, базируясь на значениях пригодности, отбирает более благоприятных индивидов, которые на следующем этапе эволюции (рекомбинации) путем смешивания генетической информации создают новую популяцию. Оператор мутации, в свою очередь, вводит некоторую случайность в генетическую информацию каждого индивида возродившейся популяции.
Процесс эволюции создает множество значений пригодности, которые в общем случае не являются идентичными значениям целевой функции. Однако, так как оператор селекции обрабатывает именно численные значения репродуктивных пригодностеи а не значения целевой функции, то результатом каждого этапа эволюции является именно множество значений пригодности индивидов. Процесс вычисления значений пригодностеи, как уже говорилось вьппе, использует значения целевой функции.
Что касается истории развития класса эволюционных алгоритмов, то здесь можно выделить три основных течения, возникших независимо друг от друга и имеющих место по сей день. - Эволюционное программирование (ЭП), первоначально созданное Фогелем в США [68,69]. - Эволюционные стратегии (ЭС), созданные в Германии Рехенбергом [89] и Швефелем [93]. - Генетические алгоритмы (ГА), [80,64,78,73,72].
Каждый из трех направлений ярко продемонстрировал свою способность создавать хорошие, устойчивые решения даже в случаях сложных многомодальных, несвязных, не дифференцируемых поверхностей отклика оптимизационных проблем. Внутри каждого исследовательского сообщества были представлены наиболее эффективные области своего применения. Однако, ЭП и, особенно, ГА имеют более широкий спектр применения, например, в таких областях как машинное обучение, планирование, управление т др. Приведенные в следующих главах описания алгоритмов всех трех направлений сделаны в попытке дать некоторые сравнительные характеристики общего плана, так как, к сожалению до сих пор не было проведено детальных исследований по сравнению этих трех направлений относительно конкретных областей применения.
Университете. Применения были, главным образом, экспериментальными и касались гидродинамических проблем. Различные версии ЭС были уже реализованы на первом компьютере Университета. Рехенберг [89] развил теорию скорости сходимости для так называемой (1+1)-ЭС, где простой механизм мутация-селекция создавал одного потомка на поколение используя только одного родителя. Кроме того, автор предложил теоретически обоснованное правило изменения стандартного отклонения мутации и впервые выдвинул идею многоиндивидуальной ЭС, т.е. (ц+1)-ЭС, где j. 1 индивидов использовались для воспроизводства одного потомка, который заменял наихудшего члена популяции. Хотя этот вариант так и не имел широкого применения, он послужил основой для последующих вариантов, таких как (\х+Х)-ЭС и (цД)-ЭС, предложенных в Швефель [93]. Тип (ц,А,)-ЭС является на данный момент наиболее перспективной формой реализации ЭС.
Поисковые точки в ЭС представляют собой и-мерные вектора х є R" и значение степени пригодности в точности эквивалентно значению целевой функции в этой точке, т.е. 0(a)=f(x), где х является компонентом объектных переменных индивида а. Таким образом, количество дополнительных параметров w = п(п+1)/2 могут быть скомбинированы с п объектными переменными для формирования индивида aeI=Rn+w. Для обеспечения положительной определенности ковариационной матрицы, алгоритм использует ротационные углы ау=(іап2ау=2су/(а2 - cjj2)). В качестве шага мутации вместо дисперсий Oj2 используется стандартное отклонение 0\. Таким образом, индивид формируется с помощью и-мерного нормального распределения с ожиданием 0, стандартного отклонения 0\ и ротационных углов а. Далее а=(х,а,а) є Rn+W используется для обозначения полностью сформированного индивида.
Различные механизмы рекомбинации используются либо в своей обычной форме, производя одного потомка от двух случайно выбранных родителей, либо используя глобальную форму, когда в создании потомка принимают участие все индивиды популяции родителей. Более того, рекомбинация осуществляется как на стратегических параметрах, так и на объектных переменных., используя различные механизмы.
Программная система GAST
Описанный выше метод эволюционного поиска, разработанный в данной работе, как основной метод многокритериальной оптимизации в полной мере реализуется в программной системе GAST. Программная система предназначена для решения оптимизационных задач, обладающих следующими свойствами: - наличие набора согласующих и\или противоречивых критериев; - целевые функции и ограничения, заданны как аналитически, так и алгоритмически; - наличие одно и\или разнотипных переменных;
Система создавалась с использованием элементов объектно-ориентированного программирования, что позволило осуществить четкую структуризацию и дальнейший анализ. Фактически система состоит из двух модулей: непосредственно оптимизационный алгоритм GAST v3.0 (Генетический Алгоритм с Подстраиваемой Структурой) и анализационный модуль ANALYZER (см. Рисунок 0.1). Оба модуля спроектированы и исполнены в качестве исполняемых файлов под управлением многозадачной операционной среды Windows95 .
В своей работе программы используют стандартные функции манипулирования базами данных BDE2. BDE предоставляет пользователю наиболее удобные и гибкие средства управления базами данных такие как построение таблиц и индексов, связывание нескольких таблиц через ключевые поля, использование. SQL -запросов и т.д. Одним из наиболее привлекательных свойств BDE является возможность нескольким виртуальным процессам работать с одной базой данных одновременно. Это позволяет значительно расширить область применения GAST, о чем будет сказано ниже. В этом варианте разработки использовался тип баз данных PARADOX, рекомендованный для совместного использования с BDE, хотя не исключалась возможность выбора формата dBASE или текстового. 1 Торговая марка корпорации Microsoft inc. 2 (Borland Database Engine) торговая марка фирмы Inprise Inc. 3 Язык структурированных запросов.
Модуль GAST представляет собой программную метода эволюционного поиска, предназначенного для решения многокритериальных задач оптимизации с использованием механизма долевой пригодности. Рисунок 4.1.1 поясняет каким образом модуль GAST взаимодействует с другими объектами, принимающими участие в процессе оптимизации. Здесь ядро модуля через понятный и интуитивный пользовательский интерфейс осуществляет диалог с экспертом, который в процессе работы настраивает рабочую структуру алгоритма т.е. выбирает задачу, настраивает ее параметры, параметры самого алгоритма и т.д. Кроме того, эксперт должен перед началом работы с GAST формализовать оптимизационную задачу и создать программный модуль, реализующий алгоритмы вычисления целевых функций и ограничений.
Модуль GAST и его связь с другими объектами. Задачи проектируются в виде динамически подключаемых библиотек (DLL-формат), имя которой просто указываются на подготовительном этапе определения рабочей структуры, что избавляет пользователя от перекомпиляции всего проекта в целом при подключении новой задачи или изменении существующей. Однако, при проектировании DLL-модуль должен удовлетворять нескольким правилам, но практика использования такого подхода показала, что эти правила достаточно легки в освоении. Использование программных реализаций тестовых и практических задач оптимизации в виде отдельных DLL-модулей имеет ряд дополнительных преимуществ: - универсальность данного подхода. Имеется в виду тот факт, что DLL-модуль может быть «читаем» практически любой Windows программой, независимо от того на каком языке был написан сам модуль или вызывающая его программа. Это достигается соблюдением стандартных правил написания DLL-модулей. Указанная универсальность может быть использована экспертами, которые для одной оптимизационной задачи реализуют различные алгоритмы в виде отдельных программ; - экономия оперативной памяти. Будучи загруженным в память по требованию программы А, DLL-модуль только один раз занимает область оперативной памяти. Далее, в случае, когда программа Б формирует открытие DLL-модуля, то операционная система не выделяет оперативную память под вторую копию. Вместо этого создается ссылка #2 на уже загруженную копию DLL-модуля и передается программе Б. Это позволяет сэкономить оперативную память ЭВМ при загрузке нескольких программ, использующих одну DLL.
Благодаря использованию механизма управления базами данных (БД), одна физическая БД может хранить информацию сразу о нескольких рабочих структурах алгоритма. Это является достаточно удобным при исследовательских работах, где необходимы частые переходы от одной задачи к другой. Таблица «Задача. Параметры» содержит поля соответствующие параметрам подключаемой задачи. Здесь содержится набор таких полей как наименование задачи, количество переменных (размерность задачи), количество функций-критериев, количество функций-ограничений, имя файла подключаемой библиотеки, реализующей модель оптимизационной проблемы;
Вычисление эффективной длины генотипа. Здесь прежде всего необходимо напомнить, что традиционный генетический алгоритм приводит все типы объектных переменных к одному типу - целочисленному, так как. происходит внутреннее декодирование переменных (фенотип) в битовую строку (генотип). Поэтому все вещественные величины исчисляются с заранее определенной точностью. Но, так как в стандартном варианте алгоритм может оперировать только определенным количеством бит (8,16,32,64,128...), то при кодировании возникает избыточность информации, содержащейся в генотипе. Обычно, количество бит применяемых для кодирования переменных выбирается на этапе проектирования ПО и остается постоянным в дальнейшем. Поэтому в каноническом ГА нет возможности настроить генотип в процессе подготовки рабочей структуры алгоритма. Наличие указанной избыточности оказывает негативное влияние как на производительность процесса оптимизации, так и на качество решений. Основные причитал в следующем:
