Содержание к диссертации
Введение
1. Анализ современного состояния и проблемы многокритериальной оптимизации поиска наилучшего распределения ресурсов 12
1.1. Обзор существующих методов оптимизации производственных ресурсов 12
1.2. ERP-системы 18
1.3. Моделирование на основе генетических алгоритмов 20
1.4. Многокритериальный поиск наилучшего распределения ресурсов для производственного предприятия 24
1.5. Проблематика эволюционных вычислений и новейшие достижения 28
1.6. Выводы по главе 33
2. Исследование применимости генетических алгоритмов при создании программного комплекса решения задач многокритериальной оптимизации
2.1. Обзор существующих методов многокритериальной оптимизации на основе генетических алгоритмов 34
2.2. Сущность эволюционных вычислений и исследование применимости генетических алгоритмов при создании программного комплекса решения задач многокритериальной оптимизации 35
2.3. Основные понятия генетических алгоритмов 38
2.4. Кодирование в генетических алгоритмах, генетические операторы 46
2.5. Формализация задачи распределения ресурсов при условии неоднородности затрат 61
2.6. Разработка алгоритма, использующего предварительное разбиение на подмножества области определения 65
2.7. Программная реализация алгоритма, использующего предварительное разбиение на подмножества области определения 66
2.8. Разработка алгоритма, использующего предварительное разбиение на подмножества области определения для симметричной целевой функции 73
2.9. Разработка гибридных адаптивных алгоритмов решения задач многокритериальной оптимизации 75
2.10. Выводы по главе 91
3. Программная реализация алгоритмов распределения ресурсов 93
3.1. Разработка программного комплекса для решения задач распределения ресурсов 93
3.2. Структурно - архитектурное решение программного комплекса... 95
3.3. Верификация эффективности разработанного комплекса 95
3.4. Выводы по главе 109
4. Экспрериментальная проверка гипотезы по более быстрой работе модификации генетического алгоритма 111
4.1. Проверка эффективности работы при целевой функции с большой конечной производной 111
4.2. Выводы по главе 117
Заключение 119
Список литературы 120
Приложение 1 129
Приложение 2
- Обзор существующих методов оптимизации производственных ресурсов
- Обзор существующих методов многокритериальной оптимизации на основе генетических алгоритмов
- Разработка программного комплекса для решения задач распределения ресурсов
- Проверка эффективности работы при целевой функции с большой конечной производной
Введение к работе
Актуальность проблемы. В настоящее время успешная деятельность предприятия по производству приборов возможна только при наличии автоматизированной системы, обеспечивающей эффективное управление и распределение производственными ресурсами. Иначе, уже на этапе переговоров о заключении - контрактов, руководство не сможет показать преимущество своего предложения по сравнению с предложениями конкурентов. Отсутствие одного критерия оценки качества решения о распределении производственных ресурсов, высокие требования к качеству продукции и необходимость» принимать оптимальные решения в сжатые сроки усложняют задачу.
В последнее время наиболее распространенными универсальными методами поиска оптимального решения при управлении производственными ресурсами являются эволюционные вычисления (ЭВ).
Среди методов ЭВ можно выделить следующие [81-93]:
эволюционное программирование (1963г., Л». Фогель, А. Оуэне, М. Уолш)- представляет решение задачи в виде1 универсальных конечных автоматов, которые реагируют на стимулы из внешней среды;
эволюционные стратегии (1973г., И. Реченберг) - каждое решение находится в виде массива числовых параметров, определяющих аргумент целевой функции;
генетические алгоритмы (1975г., Д. Холланд) - каждое решение является битовой строкой (хромосомой) определенной длины в массиве объектов фиксированного размера;
генетическое программирование (1992г., Д. Коза) - здесь применяются идеи генетических алгоритмов для эволюции компьютерных программ.
В России до начала 80-х годов прошлого века получили развитие два направления, близкие к методам ЭВ, но мало известные на Западе, к которым относятся методы стохастической оптимизации (1968г., Л.А. Расстригин) и
группового учета аргументов (1969г., А.Г. Ивахненко).
Каждая из этих школ взяла за основу ряд принципов, существующих в природе, и упростила до такой степени, чтобы их можно было реализовать на вычислительной технике того времени.
Необходимо отметить, что указанные выше методы не обеспечивают в полной мере задачу многокритериальной оптимизации производственных ресурсов, что делает их применение в современных системах управления технологическими процессами и производствами недостаточно эффективным. Таким образом, актуальными являются исследования, направленные на разработку формальных моделей и алгоритмов многокритериальной оптимизации для автоматизации процессов управления производственными ресурсами.
Целью диссертации является повышение скорости и,обоснованности принятия решения за счёт разработанных формальных моделей, алгоритмов многокритериальной оптимизации параметров для управления производственными ресурсами в предметной области.
В соответствии с указанной целью в работе решаются следующие задачи:
анализ современного состояния проблемы повышения скорости принятия решения для автоматизированного управления ресурсами производственного предприятия;
исследование способов анализа ситуаций и управления ресурсами в производственных объектах и определение перечня и особенностей используемых алгоритмов;
создание формализованного представления задачи распределения и управления ресурсами при многокритериальной оптимизации;
разработка алгоритмов распределения ресурсов при многокритериальной оптимизации в предметной области;
программная реализация и использование разработанных алгоритмов в системах автоматизированного управления
производственными ресурсами в предметной области.
Методы исследования. Теоретическую и методологическую базу исследования составили теория математического программирования, теория эволюционных вычислений и генетических алгоритмов. При- решении конкретных задач использовались труды отечественных и зарубежных ученых в области многокритериальной оптимизации и поиске глобального экстремума функции многих переменных на компактном множестве.
Научная новизна. Диссертационная работа представляет собой совокупность научно обоснованных технических разработок, направленных на создание моделей, алгоритмов и реализацию на их основе комплекса программных средств, осуществляющих многокритериальную оптимизацию и поиск глобального экстремума функции многих переменных в системах автоматизированного управления производственными ресурсами.
В процессе исследований» и разработок получены, следующие новые научные результаты.
1. На основе исследования способа! анализа ситуаций и распределения,
ресурсов в производственных объектах определен^ перечень и особенности
используемых для этих целей алгоритмов.
Формализована задача многокритериальной* оптимизации для автоматизации процессов управления производственными ресурсами.
Предложен алгоритм, позволяющий эффективно находить оптимальное распределение ресурсов в случае неоднородности затрат для определенной целевой функции.
Разработан модифицированный алгоритм многокритериальной, оптимизации, имеющий большее быстродействие по сравнению- с известными алгоритмами.
5. Разработан алгоритм поиска экстремума непрерывной функции для
частных случаев управления производственными ресурсами.
6. Создан программный комплекс для автоматизированного
управления производственными ресурсами в предметной области на основе
разработанных алгоритмов. Применение алгоритмов позволило повысить быстродействие при поиске глобального оптимума от 20% до 80%, в-зависимости от целевой функции; и, соответственно, повысить скорость принятия решения при управлении производственными ресурсами.
7. Результаты диссертации вошли в курсы учебной дисциплины
«Объектно-ориентированное программирование» Московского
государственного института электронной техники (Технического университета).
Практическая ценность работы заключается в том, что основные положения, выводы и рекомендации диссертации ориентированы на широкое применение алгоритмов для автоматизированного управления распределением ресурсов в» предметной области. Наибольшие применения-они могут найти в приборостроении, микроэлектронике,, в научных исследованиях и т.д.
Самостоятельное'практическое значение имеют:
Формализованное представление задачи распределения, ресурсов
при'многокритериальной оптимизации-.
i Верификация * гипотезы о повышении скорости принятия решения-на основе разработанных алгоритмов.
Программная реализация разработанных алгоритмов в предметной
области.
Реализация полученных результатов. Диссертационная работа выполнялась в соответствии с планом научно-технических исследований кафедры "Информатика и программное обеспечение вычислительных систем» Московского государственного института электронной техники (технического университета) и являлась составной частью исследовательских мероприятий в рамках НИОКР «Разработка методологии практической подготовки студентов в рамках инновационных образовательных программ» Федеральной целевой программы развития образования на 2006-2010 годы. Результаты диссертационной работы внедрены в учебный процесс и вошли в
курсы учебных дисциплин (лабораторные практикумы): «Объектно-ориентированное программирование» по специальности 230105.65 «Программное^ обеспечение вычислительной техники* и автоматизированных систем» направлений 654600, 552800 «Информатика и вычислительная техника».
Все работы по программной реализации алгоритмов поиска наиболее подходящего решения проводились при непосредственном участии автора.
В результате проведенных исследований получены и выносятся на защиту следующие основные научные результаты:
Математическая модель распределения ресурсов при условии неоднородности затрат.
Алгоритм распределения производственных ресурсов в случае неоднородности затрат.
Модифицированный алгоритм многокритериальной оптимизации.
Алгоритм^ поиска экстремума непрерывной функции для' частного случая.
Результаты верификации гипотезы о» повышении скорости принятия решения на основе разработанных алгоритмов.-.
Программная реализация разработанных алгоритмов, внедрение^ которых позволило повысить быстродействие поиска оптимума целевой функции от 20% до 80%. В результате, при использовании в системе поддержки управления данных алгоритмов, повышается скорость принятия решения.
Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях:
12я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Микроэлектроника и информатика — 2005., М.: МИЭТ.
13 я Всероссийская межвузовская научно-техническая конференция
студентов и аспирантов: Микроэлектроника и информатика —
2006., М.: МИЭТ.
14 я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Микроэлектроника и информатика — 2007., М.: МИЭТ.
15 я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Микроэлектроника и информатика — 2008., М.: МИЭТ.
Всероссийская межвузовская научно-практическая конференция Проблемы информатизации - 2007., М.: МИЭТ.
По результатам исследований опубликовано 9 работ, из них 3 статьи.
Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка литературы.
В первой главе проводится анализ современного состояния проблемы многокритериальной оптимизации распределения ресурсов.
Во второй главе проводится исследование применимости генетических алгоритмов при создании программного комплекса решения задач многокритериальной оптимизации. Для этого проводится обзор существующих методов многокритериальной оптимизации на основе генетических алгоритмов и формализация задачи распределения ресурсов при условии неоднородности затрат.
Также во второй главе приводится описание модификацированного алгоритма многокритериальной оптимизации.
Обзор существующих методов оптимизации производственных ресурсов
Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По этому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.
Необходимость принятия наилучших решений так же стара, как само человечество. Испокон веку люди, приступая к осуществлению своих мероприятий, раздумывали над их возможными последствиями и принимали решения, выбирая тем или другим образом зависящие от них параметры -способы организации мероприятий. Но до поры, до времени решения могли приниматься без специального математического анализа, просто на основе опыта и здравого смысла.
Возьмем пример: человек вышел утром из дому, чтобы ехать на работу. По ходу дела ему приходится принять целый ряд решений: брать ли с собой зонтик? В каком месте перейти улицу? Каким видом транспорта воспользоваться? И так далее. Разумеется, все эти решения человек принимает без специальных расчетов, просто опираясь на имеющийся у него опыт и на здравый смысл. Для обоснования таких решений никакая наука не нужна, да вряд ли понадобится и в дальнейшем.
Однако возьмем другой пример. Допусти, организуется работа городского транспорта. В нашем распоряжении имеется какое-то количество транспортных средств. Необходимо принять ряд решений, например: какое количество и каких транспортных средств направить по тому или другому маршруту? Как изменять частоту следования машин в зависимости от времени суток? Где разместить остановки? И так далее.
Эти решения являются гораздо более ответственными, чем решения предыдущего примера. В силу сложности явления последствия каждого из них не столь ясны; для того, чтобы представить себе эти последствия, нужно провести расчеты. А главное, от этих решений гораздо больше зависит. В первом примере неправильный выбор решения затронет интересы одного человека; во втором - может отразиться на деловой жизни целого города.
Конечно, и во втором примере при выборе решения можно действовать интуитивно, опираясь на опыт и здравый смысл. Но решения окажутся гораздо более разумными, если они будут подкреплены количественными, математическими расчетами. Эти предварительные расчеты помогут избежать длительного и дорогостоящего поиска правильного решения "на ощупь".
Наиболее сложно обстоит дело с принятием решений, когда речь идет о мероприятиях, опыта в проведении которых еще не существует и, следовательно, здравому смыслу не на что опереться, а интуиция может обмануть. Пусть, например, составляется перспективный план развития вооружения на несколько лет вперед. Образцы вооружения, о которых может идти речь, еще не существуют, никакого опыта их применения нет. При планировании приходится опираться на большое количество данных, относящихся не столько к прошлому опыту, сколько к предвидимому будущему. Выбранное решение должно по возможности гарантировать нас от ошибок, связанных с неточным прогнозированием, и быть достаточно эффективным для широкого круга условий. Для обоснования такого решения приводится в действие сложная система математических расчетов.
Вообще, чем сложнее организуемое мероприятие, чем больше вкладывается в него материальных средств, чем шире спектр его возможных последствий, тем менее допустимы так называемые "волевые" решения, не опирающиеся на научный расчет, и тем большее значение получает совокупность научных методов, позволяющих заранее оценить последствия каждого решения, заранее отбросить недопустимые варианты и рекомендовать те, которые представляются наиболее удачными.
Практика порождает все новые и новые задачи оптимизации причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.
Реальные прикладные задачи оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека. Нет, пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи.
Формулировка математической задачи оптимизации В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом: Минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.
Под минимизацией (максимизацией) функции п переменных f(x)=f(xl, ... ,хп) на заданном множестве U /7-мерного векторного пространства Еп понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на U значения f(x).
Обзор существующих методов многокритериальной оптимизации на основе генетических алгоритмов
Многокритериальная оптимизация, также известная как векторная оптимизация, может быть определена как задача нахождения вектора переменных-решений, которые удовлетворяют ограничениям и доставляют оптимум вектор-функции, чьи элементы представляют собой целевые функции. В многокритериальных задачах, когда из первоначальной постановки не удается выделить критерий, преобладающий по важности над другими - главный критерий, довольно часто критерии искусственно комбинируют посредством агрегирующей функции с параметрами -весовыми коэффициентами, назначаемыми каждому критерию согласно его относительной важности. Этот подход часто называют скаляризацией или сверткой векторного критерия. А получающуюся при этом параметризованную функцию, сводящую исходную многокритериальную задачу к однокритериальной, - обобщенным, агрегированным, глобальным критерием или суперкритерием. Наиболее широко распространенным видом обобщенного критерия является линейная свертка, когда глобальный критерий представляется в виде суммы (иногда произведения) частных критериев, умноженных на соответствующие весовые коэффициенты.
Как показывает практика применения различных оптимизационных процедур, довольно сложно найти универсальный подход, даже при решении задач одного класса. Эволюционные алгоритмы многокритериальной оптимизации, не достаточно точно аппроксимирующие множество Парето, не являются исключением. Выходом в таком случае может послужить модернизация уже разработанных алгоритмов, которая бы привела к сглаживанию недостатков существующих подходов. Наиболее часто используются различные варианты сочетания (гибридизации) нескольких отличных подходов, что в большинстве случаев позволяет значительно улучшить результаты, относительно применения методов по отдельности. Каждый из включаемых в гибрид алгоритмов ориентирован на решение определенной подзадачи. А сами гибридные схемы состоят из последовательности этапов включения того или иного отдельного подхода, позволяя аккумулировать на определенном этапе решения задачи положительные свойства каждого из алгоритмов. При этом важную роль играет сама организация взаимодействия нескольких алгоритмов, составляющих гибрид, в частности, порядок их включения друг относительно друга.
Очевидно, что многие эволюционные программы (синоним эволюционных вычислений) могут быть сформулированы для решения конкретной проблемы. Такие программы могут иметь различную структуру данных для построения отдельного индивидуума, генетические операторы для трансформации индивидуумов, методы для создания начальной популяции, параметры вычислений (размер популяции, вероятности применения различных операторов и т.д.). Однако несмотря на различия такие программы имеют общий принцип: массив объектов индивидуумов подвергается некоторым преобразованиям, и в течение эволюционного процесса индивидуумы сражаются за выживание.
Следует отметить, что методы ЭВ не гарантируют обнаружения глобального оптимума за приемлемое время. Практический интерес к ним объясняется тем, что эти методы позволяют найти «хорошие» решения очень трудных задач за меньшее время, чем другими методами.
Необходимо уяснить разницу между эволюционным программированием и ГА: при первом подходе используется любая структура данных (хромосомное представление), подходящая для решения задачи, и любое множество генетических операторов; во второй ситуации применяются бинарные строки фиксированной длины (хромосомы) и два оператора (бинарные мутация и скрещивание).
Естественно, что близкое к эволюционным процессам представление потенциального решения для данной проблемы вместе с совокупностью подходящих генетических операторов может быть полезным для решения многих задач, и такой подход является весьма перспективным направлением. За последние 10-15 лет опубликовано достаточное количество работ, в которых для решения конкретных задач рассмотрены различные модификации классического представления ГА (ниже будет показано, что ГА, впервые предложенный Д. Холландом в 1975 г., является классическим), например, строки переменной длины; более богатая, чем бинарные строки, структура; модифицированные генетические операторы. Среди последних можно указать описание ГА, который использует в качестве оператора метод обратного распространения ошибки (в гибридных нейронных сетях). Многие исследователи в этой области применяют модифицированные реализации ГА или путем использования нестроковой хромосомы при представлении задачи, или посредством разработки специальных генетических операторов для возможности решения конкретной проблемы. Различные нестандартные подходы были предложены для частных задач, так как классические ГА было трудно непосредственно применить для решения подобных задач.
В связи с указанными выше соображениями о модификации ГА возникает вопрос о том, являются ли эволюционные стратегии генетическими алгоритмами? Для того, чтобы избежать подобных вопросов, связанных, прежде всего, с классификаций ЭВ, назовем такие системы эволюционными программами (ЭП) [81] и рассмотрим различие между ГА и
ЭП. Несмотря на то, что ГА имеют достаточно серьезную теоретическую базу, они не могут обеспечить успешное применение во многих областях. Очевидно, что главный фактор неудачи ГА является тем же фактором успеха в решении задач: то область независимости. Одним из следствий четкости ГА в смысле области независимости является их неспособность к учету нетривиальных ограничений. В большинстве работ по ГА хромосомы представляют собой битовые строки (строки, состоящие из 1 и 0), поэтому реализация ограничений в такой ситуации является достаточно сложной задачей.
Разработка программного комплекса для решения задач распределения ресурсов
Для проведения многокритериальной оптимизации генетическими алгоритмами и осуществления проверки эффективности работы разработанных подходов был создан программный комплекс, о которой и пойдет речь далее. Программный комплекс представляет собой программную реализацию предложенных в диссертации подходов и исследуемых в ней методов многокритериальной оптимизации генетическими алгоритмами.
Разработанный программный продукт предназначен для решения сложных задач многокритериальной оптимизации и является интегрированной программной системой, включающей все этапы решения многокритериальных оптимизационных задач генетическими алгоритмами, начиная от выбора самой задачи и алгоритма ее решения с заданием соответствующих параметров, до получения ее конечного решения с выводом результатов в графической и текстовой форме (на экран и в текстовый файл).
Языком реализации программного продукта является язык программирования C++. Благодаря заложенным в него возможностям при разработке системы использовался объектно-ориентированный подход, при котором вся система представляется как совокупность находящихся во взаимосвязи элементов.
Программная система для решения оптимизации генетическими алгоритмами является 32-рязрядным приложением для Windows и для ее установки не требуется выполнение операций объектов. Чтобы установить программный комплекс, необходимо скопировать все его файлы в один каталог. Желательно создать отдельный каталог, для того чтобы в последствии осуществлять более быстрый поиск файлов с результатами, которые в процессе работы системы создаются в том же каталоге, что и сама программа.
Для установки и эксплуатации системы необходим IBM совместимый персональный компьютер в следующей конфигурации: 1. процессор Intel Pentium с тактовой частотой не ниже Pentium II 300, рекомендуется Pentium IV с частотой 2,2 ГГц; 2. операционная система Microsoft Windows 98/МЕ/2000/ХР; 3. оперативная память не менее 64 Мбайт, рекомендуется 512 Мбайт; 4. не менее 8 Мбайт свободного пространства на жестком диске; 5. мышь и клавиатура для осуществления ввода и изменения данных и параметров алгоритмов в интерактивном режиме; 6. флоппи-дисковод/дисковод для компакт-дисков CD-ROM, чтобы иметь возможность установки программы с дискеты или компакт-диска; 7. монитор, поддерживающий разрешение экрана не менее 640x480 8. пикселей, рекомендуется 1024x768; 9. видеокарта с памятью не менее 128 Кбайт.
После подсчета вероятностей стать родителем для массива объектов необходимо породить новую популяцию. Обычно в процедуру порождения входят две стадии: скрещивание (обмен частями цепочек генов родителей) и мутация (случайное изменение одного или нескольких генов). Поскольку в данной задаче на объект накладываются строгое ограничение не повторяемости чисел, отдельное использование мутации, вероятно, не целесообразно и можно ограничиться только скрещиванием. Начиная порождение новой популяции, первым делом необходимо выбрать родителей. Выбор родителей осуществляется на основе генерации случайного числа и, исходя из посчитанной вероятности стать родителем объектов популяции. Таким образом, наиболее часто выбираются наиболее приспособленные объекты, что в свою очередь увеличивает вероятность того, что в новом массиве объекты будут еще более приспособленные. То, что в качестве родителя объект выбирается с некоторой вероятностью (а не точный выбор самого приспособленного объекта), помогает избежать попадания в область локального оптимума. После выбора родителей производится скрещивание. Т.е. выбирается точка разрыва цепочек генов родителей и заменяется часть цепочки генов одного родителя на часть цепочки генов другого. (Кроме этого возможны и другие методы -двухточечный кроссовер и равномерный кроссовер - вполне достойные альтернативы одноточечному оператору. В двухточечном кроссовере выбираются две точки разрыва, и родительские хромосомы обмениваются сегментом цепочки генов, который находится между двумя этими точками. В равномерном кроссовере, каждый бит первого родителя наследуется первым потомком с заданной вероятностью; в противном случае этот бит передается второму потомку). После этого необходимо убедиться, что новый объект соответствует накладываемым ограничениям, для этого, просматриваются все десять чисел нового объекта, дублирующие числа заменяются теми, которые еще не были задействованы. Эта операция не является классическим скрещиванием и представляет собой некую ее адаптацию к данной задаче, которую можно рассматривать как скрещивание с мутацией. После порождения нового массива объектов она замещает старую. (Конечно, это не единственный вариант изменения массива объектов, кроме полного замещения родителей, например, возможно наращивание массива).
Полученные в работе результаты позволяют сделать вывод о перспективности разработки и применения генетических алгоритмов и их комбинаций с другими походами для решения задач поиска наиболее подходящего значения.
Современные тенденции развития области применения ГА обуславливают расширение методик проектирования и разработку новых методов повышения эффективности генетических алгоритмов. Эти методики будут востребованы как при исследовании новых областей применения ГА так и практическом применении для решения конечных задач. Предложенный подход к решению задачи повышения эффективности генетических алгоритмов является одним из наиболее перспективных методов по повышению эффективности и расширению областей применения не только для рассмотренных задач генетического поиска, но задач, для решения которых требуется значительные временные затраты. При этом, основной целью выступает разработка методик построения объекта, максимально оптимизированного под конкретный класс задач, универсального внутри этого класса, и использующего современные методы аппаратной реализации (конвейеризация, распараллеливание вычислений, микропрограммный принцип управления, предоставление пользователю возможности реконфигурирования параметров функционирования и организации алгоритма и т.п.).
Проверка эффективности работы при целевой функции с большой конечной производной
Иногда оказывается, что одна из сравниваемых альтернатив уступает другим вариантам по всем показателям. В этом случае ее исключают из рассмотрения также на основе принципа доминирования. Ситуация из примера 1 встречается не часто. Поэтому принцип доминирования в «чистом виде» используется редко. Для устранения обнаруженного недостатка метода SPEA при решении безусловных многокритериальных задач — наличие в итоговом деноминируемом множестве непаретовских точек, предлагается производить «лечение» (уточнение) тех недоминируемых точек, полученных после остановки генетического алгоритма, которые не принадлежат множеству Парето. Благодаря тому, что решения в генетических алгоритмах представляются в виде бинарной строки, для «лечения» недоминируемых точек очень удобным представляется использование алгоритма паретовского локального поиска, действующего в пространстве булевых переменных. Паретовский локальный поиск
Главная идея локального поиска — существование окрестности, которая представляет собой некоторое множество решений, близких к текущему решению в некотором смысле [19,49,52]. Решения задач оптимизации должны принадлежать допустимой области, то есть X є D . Если на множестве D заданы целевые функции F(X), то имеем задачу (D,F(X)). В этом случае системой окрестностей N называется отображение множества D в множество 2D (множество всех подмножеств множества D), определенное для каждой задачи. При этом две точки, принадлежащие допустимой области, будем называть к-соседними, если они отличаются друг от друга значениями своих к координат.
Таким образом, отыскание оптимального решения в алгоритме локального поиска осуществляется посредством просмотра точек окрестности, меняя компоненты булева вектора решений. А решение о переносе поиска в новую точку принимается после просмотра ближайших точек окрестности. При этом различают 2 способа просмотра окрестности: первый - наискорейший спуск, когда просматривается вся окрестность и осуществляется переход в точку с наилучшим значением функции, и второй переход по первому улучшению - очевидная альтернатива наискорейшему спуску, который следует применять в условиях, когда отсутствует специфическая информация, дающая повод надеяться, что «наискорейший» спуск будет действительно наискорейшим [49].
В случае многокритериальных задач мы имеем дело с так называемым паретовским локальным поиском (ПЛП). Паретовский локальный поиск представляет собой оригинальный метод локального спуска в пространстве бинарных переменных с переходом по первому улучшению. Его отличительной особенностью является способ определения лучшего решения - сравнение соседних точек. В данном случае определение является ли точка, полученная на данном этапе, лучше предыдущей, полученной до этого, основывается на принципе Парето, т.е. переход в соседнюю точку осуществляется, если она доминирует текущую по совокупности критериев.
Схема гибридного алгоритма для решения безусловных многокритериальных задач оптимизации
Таким образом, для решения безусловных задач многокритериальной оптимизации предлагается использовать гибридный адаптивный поисковый алгоритм, сочетающий эволюционный алгоритм SPEA и паретовский локальный поиск.
Были рассмотрены и проанализированы различные схемы гибридизации, включающие введение паретовского локального поиска на начальных этапах работы генетического алгоритма (мультистарт), в процессе и после остановки SPEA, В результате была выбрана наилучшая схема, когда локальный поиск включается в конце работы алгоритма SPEA, осуществляя «лечение» псевдо недоминируемых точек. Т.е. паретовские точки не могут быть улучшены, а остальные переводятся локальным поиском в область Парето. Если в процессе уточнения псевдо-недоминируемых точек улучшение (доминирование) не наблюдается, то возникает ситуация, эквивалентная множествам постоянства [52]. Для преодоления компактных множеств псевдо недоминируемых точек в алгоритме предусмотрена процедура выхода из множества постоянства, включающая просмотр 1 соседних, 2-соседних и 3-соседних точек окрестности — точек, отличающихся одной, двумя и тремя координатами соответственно. После этого проводится кластерный анализ и лишние точки, образующие сгустки, удаляются, оставляя одного репрезентативного индивида в каждом кластере. Итак, схему гибридного эволюционного алгоритма многокритериальной оптимизации можно представить в виде последовательности следующих шагов.
