Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем

Размещено на http://www.allbest.ru/

125

Размещено на http://www.allbest.ru/

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ВЕРОЯТНОСТНЫХ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ ДЛЯ МОДЕЛИРОВАНИЯ И ОПТИМИЗАЦИИ СЛОЖНЫХ СИСТЕМ

• Содержание:
• Введение
• Глава I. Разработка и исследование вероятностного генетического алгоритма для оптимизации сложных систем
• 1.1 Основные свойства задач оптимизации сложных систем и возможные подходы к их решению
• 1.1.1 Метод бинаризации
• 1.1.2 Коды Грея
• 1.1.3 Тестовые задачи
• 1.2 Стандартный генетический алгоритм и исследование его работоспособности на тестовых задачах
• 1.2.1 Представление решений в ГА
• 1.2.2 Общая схема ГА
• 1.2.3 Инициализация
• 1.2.4 Селекция
• 1.2.5 Скрещивание
• 1.2.6 Мутация
• 1.2.7 Пригодность индивидов (fitness-функция)
• 1.2.8 Исследование работоспособности на тестовых задачах
• 1.3 Метод изменяющихся вероятностей (МИВЕР) и исследование его работоспособности на тестовых задачах
• 1.3.1 Общая схема МИВЕР
• 1.3.2 Исследование работоспособности на тестовых задачах
• 1.4 Основные идеи вероятностного генетического алгоритма и исследование его работоспособности на тестовых функциях
• 1.4.1 Общая схема вероятностного генетического алгоритма
• 1.4.2 Исследование работоспособности на тестовых задачах
• 1.5 Алгоритм прогноза сходимости вероятностного генетического алгоритма
• 1.6 Выводы
• Глава II. Разработка и исследование метода вероятностного генетического программирования для моделирования сложных систем
• 2.1 Методы решения задач аппроксимации в моделировании сложных систем
• 2.2 Обычный метод генетического программирования для решения задачи символьной регрессии и его исследование
• 2.2.1 Представление решений в методе генетического программирования
• 2.2.2 Общая схема метода генетического программирования, применение основных генетических операторов
• 2.2.3 Решение задачи символьной регрессии с помощью метода генетического программирования
• 2.2.4 Исследование работоспособности на тестовых задачах
• 2.3 Основные идеи вероятностного генетического программирования и его исследование
• 2.3.1 Общая схема метода вероятностного генетического программирования
• 2.3.2 Исследование работоспособности на тестовых задачах
• 2.4 Выводы
• Глава III. Практическая реализация разработанных алгоритмов
• 3.1 Программная реализация обыкновенного и вероятностного генетического алгоритмов
• 3.1.1 Программная система «GA lab»
• 3.1.2 Программная система «ProbGA lab»
• 3.2 Программная реализация методов обыкновенного и вероятностного генетического программирования
• 3.2.1 Программная система «GP: Symbolic Regression»
• 3.2.2 Программная система «ProbGP: Symbolic Regression»
• 3.3 Постановка задачи оптимизации работы электростанции на топливных элементах в стационарном режиме
• 3.3.1 Водородные топливные элементы - основные принципы
• 3.3.2 Теплоэлектростанции на топливных элементах
• 3.3.3 Математическая модель электростанции на топливных элементах
• 3.3.4 Постановка задачи оптимизации
• 3.4 Решение задачи оптимизации работы электростанции на топливных элементах в стационарном режиме с помощью вероятностного генетического алгоритма
• 3.4.1 Исследование устойчивости решения
• 3.5 Выводы
• Заключение
• Список использованных источников
• Приложение 1. Общая схема конструирования многоэкстремальных функций непрерывных переменных
• Приложение 2. Набор тестовых задач
• Введение
• Идея оптимальности является центральной идеей кибернетики. Понятие оптимальности получило строгое и точное представление в математических теориях, прочно вошло в практику проектирования и эксплуатирования технических систем, сыграло важную роль в формировании современных системных представлений. Оптимизация - один из способов выражения рационального поведения. Математически задача оптимизации формулируется как задача поиска экстремума некоторого функционала, выражающего зависимость выходных параметров исследуемого объекта (системы, процесса) от входных [11, 34].
• При решении задач оптимизации сложных систем часто встречаются ситуации, которые затрудняют или делают невозможным применение классических методов. Поэтому задача разработки адаптивных стохастических методов прямого поиска является весьма актуальной.
• За прошедшие годы было предложено много различных схем применения эволюционных алгоритмов для решения сложных задач оптимизации [35, 36, 58, 61, 62]. Генетические алгоритмы с бинарным представлением решений занимают особое место среди стохастических методов адаптивного поиска. Особая сложность разработки и исследования алгоритмов связана с тем, что большинство методов прямого поиска основано на различных эвристических идеях. Перспективным направлением является разработка методов комбинирующих эвристические идеи интеллектуальных информационных технологий и строгий формальный аппарат современной математики.
• В ситуациях, когда с объектом нельзя активно экспериментировать, оптимизация производится по модели объекта. Если экспертные знания об объекте в явном виде отсутствуют, то обычно по имеющимся статистическим данным строится некоторая вычислительная модель (например, статистические методы, нейронные сети, непараметрический подход). Однако недостаток численной модели заключается в том, что она, по сути, является «черным ящиком». В результате никакой дополнительной информации для оптимизации мы извлечь из «черного ящика» не можем.
• Символьная регрессия дает нам не только вычислительную процедуру, но и формулу (символьное математическое выражение), которую можно было бы подвергнуть содержательному анализу, упростить, а затем и уточнить. Однако на современном этапе методы символьной регрессии не разработаны достаточно хорошо, поэтому направление разработки и следования подобных методов является актуальным. Метод генетического программирования является наиболее перспективным направлением.
• Цель работы: разработка и исследование комплексной системы моделирования и оптимизации сложных систем на основе алгоритма вероятностного генетического программирования (моделирование сложных систем путем решения задач символьной регрессии) и вероятностного генетического алгоритма (оптимизация сложных систем с применением построенной модели).
• Для достижения поставленной цели необходимо решить следующие задачи:
• 1. Провести анализ основных свойств задач оптимизации сложных систем и возможных подходов к их решению.
• 2. Программно реализовать и провести анализ сравнительной эффективности метода изменяющихся вероятностей и генетического алгоритма с бинарным представлением решений.
• 3. Разработать и программно реализовать алгоритм поиска, комбинирующий эвристические идеи генетического алгоритм и формальный аппарат современной математики. Показать работоспособность предложенного вероятностного генетического алгоритма на тестовых и практических задачах, сравнить с известными алгоритмами.
• 4. Провести анализ методов решения задачи символьной регрессии.
• 5. Разработать и программно реализовать алгоритм решения задачи символьной регрессии с помощью метода генетического программирования. Показать его работоспособность на тестовых задачах.
• 6. Разработать метод генетического программирования, использующий механизм вероятностного генетического алгоритма. Программно реализовать и показать работоспособность предложенного подхода на тестовых задачах.
• Методы исследования. Для решения поставленных задач использовались методы системного анализа, теории вероятности, математической статистики, псевдобулевой оптимизации и эволюционных алгоритмов.
• Научная новизна результатов диссертации:
• 1. Разработан новый метод решения сложных задач оптимизации - вероятностный генетический алгоритм, и показана его работоспособность на тестовых и практических задачах.
• 2. Проведен сравнительный анализ эффективности вероятностного генетического алгоритма и классического генетического алгоритма, и показано, что вероятностный генетический алгоритм превосходит классический как по надежности, так и по быстродействию.
• 3. Разработан новый метод решения задачи символьной регрессии - вероятностный алгоритм генетического программирования, и доказана его работоспособность на тестовых задачах.
• Практическая значимость. Предложенный вероятностный генетический алгоритм использован при решении актуальной практической задачи - оптимизаций работы электростанции на топливных элементах в установившемся режиме. Полученные с помощью вероятностного генетического алгоритма параметры позволяют повысить эффективность работы станции на 6.5%, что подтверждено официальным сертификатом от Института прикладных исследований при Высшей технической школе г. Ульм (Германия).
• На основе предложенных алгоритмов разработаны современные программные системы, которые позволяют в рамках одного подхода решать задачи моделирования и параметрической оптимизации сложных систем.
• Предложенные в диссертации алгоритмы и программные системы используются в учебном процессе при проведении занятий по специальным курсам «Системы искусственного интеллекта» и «Адаптивные и эволюционные методы принятия решений» в Сибирском государственном аэрокосмическом университете, а также по общему курсу «Методы оптимизации» и специальным курсам «Системный анализ и управление» и «Эволюционные алгоритмы оптимизации» в Красноярском государственном университете.
• Основные защищаемые положения:
• 1. Предложенный вероятностный генетический алгоритм позволяет эффективно решать задачи оптимизации сложных систем, содержит меньше настраиваемых параметров и превосходит стандартный генетический алгоритм по надежности и по трудоемкости.
• 2. Предложенный метод вероятностного генетического программирования позволяет эффективно решать задачу символьной регрессии и строить адекватные математические модели сложных систем по результатам наблюдений.
• 3. Полученные с помощью вероятностного генетического алгоритма значения параметров для задачи оптимизации работы электростанции на топливных элементах в стационарном режиме позволяют повысить КПД электростанции в 2 раза.
• Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих научно-практических конференциях:
• - Межвузовская научно-практическая конференция «Молодежь Сибири - науке России», СИБУП, 2002.
• - 40-я научно-практическая конференция студентов, аспирантов и молодых ученых посвященная дню космонавтики. САА. Красноярск, 2002.
• - Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Совершенствование методов поиска и разведки, технологий добычи и переработки полезных ископаемых», КрасГАЦиЗ, 2003.
• - Межвузовская научная конференция «Информатика и информационные технологии», КГТУ, 2003.
• - 41-й студенческая конференция СибГАУ посвященная дню космонавтики. Красноярск, 2003.
• - XXVI Научная студенческая конференция по математике. КГУ, 2003.
• - Краевая выставка технических идей и разработок «Первый сибирский техносалон». Красноярск, 2003.
• - Х Юбилейная Международная научно-практическая конференция студентов, аспирантов и молодых ученых «Современные техника и технологии», Томск, 2004.
• А также на научно-техническом семинаре института прикладных исследований при Высшей технической школе г. Ульм (Германия), научных семинарах экспериментальной лаборатории интеллектуальных технологий и адаптации СибГАУ и научном семинаре кафедры механики и процессов управления Красноярского государственного университета.
• Программные системы, реализующие гибридный метод генетического программирования и вероятностный генетический алгоритм прошли экспертизу и зарегистрированы в отраслевом фонде алгоритмов и программ (ОФАП) Государственного координационного центра информационных технологий Министерства образования и науки (коды программ по ЕСПД: .03524577.00637-01 и .03524577.00638-01, номера государственной регистрации 50200400500 и 50200400501, номера свидетельств об отраслевой регистрации разработок 3507 и 3508).
• Публикации. По результатам диссертационной работы опубликовано 12 печатных научных работ, список которых приведен в конце диссертации [19-29, 56].
• Структура
• Диссертационная работа состоит из введения, трех глав, заключения, списка литературы из 62 наименований и 2 приложений. Содержание работы изложено на 106 страницах основного текста, включая 4 таблицы и 54 рисунка.
• Глава I. Разработка и исследование вероятностного генетического алгоритма для оптимизации сложных систем
• 1.1 Основные свойства задач оптимизации сложных систем и возможные подходы к их решению
• Оптимизация (от лат. Optimum - наилучшее) - «процесс нахождения экстремума (глобального максимума или минимума) определенной функции или выбора наилучшего (оптимального) варианта из множества возможных» [13].
• Оптимизация - «минимизация или максимизация определенным образом заданного критерия, который характеризует качество или эффективность принимаемого решения» [10].
• Оптимизация - «итеративный процесс улучшения решения задачи, сформулированный в постановке поиска экстремума целевой функции» [8].
• Данные определения отражают наиболее широко распространенные представления об этом понятии. Иногда после слов «функции» добавляют «или функционала» (переменной величины, заданной на множестве функций), что несколько расширяет определение, не меняя по существу его смысла. Анализ приведенных выше и иных определений термина «оптимизация» позволяет выделить в этом термине две основные составляющие:
• 1) указание на наличие моделирующего некоторую реальность целевого критерия (целевой функции/целевого функционала, критерия оптимизации, экстремальной характеристики, показателя экстремума, критерия качества и др.), экстремальное (максимальное или минимальное) значение которого необходимо либо однократно определить (если его положение не зависит от времени), либо перманентно отслеживать (в противном случае);
• 2) указание на наличие соответствующих средств определения экстремума данного целевого критерия: при наличии достаточной информации о виде оптимизируемой функции вполне формальных, при ее отсутствии - поисковых [6].
• Идея оптимальности является центральной идеей кибернетики. Понятие оптимальности получило строгое и точное представление в математических теориях, прочно вошло в практику проектирования и эксплуатирования технических систем, сыграло важную роль в формировании современных системных представлений, широко используется в административной и общественной практике, стало понятием, известным почти каждому человеку. И это не удивительно: стремление к повышению эффективности любой целенаправленной деятельности нашло свое выражение, ясную и понятную форму в идее оптимальности [11].
• В ситуации, когда мы имеем дело с «достаточно простыми» системами, которые поддаются адекватной математической формализации, для решения задач оптимизации предложено множество формальных регулярных оптимизационных и поисковых методов. Исходя из характера и особенностей представления целевого критерия, выбирается соответствующий алгоритм решения задачи оптимизации. Для случаев, когда существует математическое выражение целевой функции, и ограничения отсутствуют - это методы спуска (градиентный метод, обобщенный метод Ньютона, методы сопряженных направлений и т.п.). Если имеются ограничения, возникает задача нахождения условного экстремума. Задача условной оптимизации решается как методами, непосредственно обобщающими методы нахождения безусловного экстремума, так и специальными методами (методы математического программирования). И т.д.
• В последние годы усилился интерес у построению оптимизационных моделей различных сложных процессов и систем, формализовать которые полностью не удается. При переходе от чисто технических или технологических проблем к проблемам, включающим организационные и социальные вопросы, задача существенно ухудшается.
• При решении задач оптимизации сложных систем часто встречаются следующие ситуации:
• - Вычислительная сложность - математическое выражение целевого функционала либо отсутствует вообще, либо целевой функционал вычисляется математически (точнее, на компьютере) как последовательность сложных нелинейных математических преобразований.
• - Неопределенность - априорные сведения о свойствах целевого функционала отсутствуют. Оптимизация производится только по измерениям функционала в фиксированных точках.
• - С объектом нельзя активно экспериментировать, оптимизация производится по модели объекта.
• - Объект нестационарный - положение экстремума может меняться во времени.
• - Размерность задачи высока.
• - Переменные задачи выражены в различных шкалах измерения.
• - Оптимизируемый функционал крайне нелинеен и многоэкстремален, в допустимой области существуют множества постоянства.
• - Допустимая область ограничена - наличие ограничений типа равенств и неравенств (ограничения также могут обладать выше перечисленными свойствами).
• - Оптимизация производится по многим экстремальным критериям одновременно - многокритериальная оптимизация.
• Очевидно, что применение классических методов оптимизации в подобных задачах невозможно или крайне затруднено.
• 1.1.1 Метод бинаризации
• В общем виде задачу безусловной оптимизации можно представить в виде (1), где переменные могут быть выражены в различных шкалах измерений.
• ,(1)
• где - область изменения метрических переменных, - область изменения порядковых переменных, - область изменения переменных наименований, - область изменения переменных перестановок.
• Предложенный Л.А. Растригиным метод бинаризации позволяет сводить задачи типа (1) к задачам псевдобулевой оптимизации (2). Следует отметить, что к задаче (2) сводятся любые задачи дискретного программирования, а также непрерывного, путем дискретизации пространства поиска [12, 15].

,

.(2)

Основная идея бинарного кодирования заключается в следующем. Булев вектор компонент, может принимать - значений. Необходимо каким-либо образом установить соответствие между значениями переменных исходной задачи и значениями булевого вектора (задать алгоритм кодирования). В случае, если число значений переменных исходной задачи не равно , то либо переопределяют область изменения исходных переменных, либо одному значению исходной переменной ставят в соответствие несколько значений булевого вектора.

Перевод порядковых переменных в булевы

Пусть дана порядковая переменная . Бинарным представлением переменной будет вектор , где . Находим значение булевого вектора, переведя его в целое число . Тогда полагаем .

Перевод метрических переменных в булевы

Кодирование метрической шкалы начинается с перевода ее в порядковую. Для этого интервал разбивается на равных частей ( - точность решения задачи оптимизации). Теперь переменная измеряется в порядковой шкале, , где . Далее порядковая переменная преобразуется в булеву аналогично.

Перевод переменных наименований и перестановок в булевы

Эффективных алгоритмов перевода порядковых переменных и переменных наименований до сих пор не предложено. Непосредственный перевод их в булевы переменные дает результат аналогичный полному перебору.

Предложено по мере накопления информации о функционале в процессе оптимизации, определять отношения порядка на множестве перестановок и наименований. Далее работать так же как и с порядковыми шкалами.

1.1.2 Коды Грея

Код Грея это бинарный код целого числа, такой, что для смежных целых чисел расстояние между их кодами в метрике Хемминга равно 1.

Стандартное рефлексивное Грей кодирование целого числа получается применением оператора исключающего ИЛИ к стандартному бинарному кодированию целого числа и к тому же бинарному коду, смещенному на одну позицию вправо, последний бит отсекается.

Кодирование и декодирование Грея можно выразить в виде операций с матрицами. Пусть x и y n-битовое бинарное и Грей кодирование целого числа соответственно, и G матрица трансформации, состоящая из 1 на главной диагонали и диагонали верхнего минора и 0 в других позициях. Грей кодирование и декодирование тогда можно представить как и соответственно. Можно показать, что любая перестановка столбца в матрице G приводит к другой матрице трансформации [54].

Можно использовать следующий алгоритм перевода бинарного кода в Грей-код и наоборот: начать со старшего (правого) бита для получения Грей кода и с левого для получения бинарного кода, последовательно заменять биты по правилу:

На каждом шаге заменяется два бита и производится смещение на один бит таким образом, что на последующем шаге заменяется один новый бит и один старый.

Для многих практических задач код Грея оказывается более эффективным, чем бинарное кодирование [39]. Код Грея сохраняет структуру окрестностей пространства поиска в бинаризованном пространстве. В результате, Грей код не может образовать оптимумов больше, чем у исходной целевой функции. Более того, т.к. у текущей точки в коде Грея соседних точек больше, чем в дискретной целевой функции, то в пространстве поиска Грей кода число оптимумов обычно меньше. В противоположность, бинарный код часто создает новые оптимумы, которых нет в целевой функции [59].

1.1.3 Тестовые задачи

Вопрос об определении адекватного множества тестовых задач для конкретного типа алгоритмов совсем не прост, хотя некоторые необходимые принципы кажутся очевидными.

- Задачи в тестовом наборе должны быть непохожи друг на друга, чтобы у создателя алгоритма было меньше возможностей настроить его на специальных примерах.

- В тестовых задачах должны содержаться такие ситуации, которые обычно вызывают затруднения; процесс проверки алгоритма должен показать, что эти трудности преодолеваются. [4]

- Тестовые задачи должны вызывать затруднения у локальных методов.

- Тестовые задачи должны быть нелинейными и несепарабельными.

- Тестовые задачи должны быть масштабируемыми. [60]

Наиболее часто для проверки эффективности адаптивных алгоритмов глобального поиска используются функции Розенброка, Шекеля, Растригина, Катникова, Griewank, De Jong. Общая схема проектирования многоэкстремальных тестовых функций предложена в [14, 16]. Подробно схема проектирования тестовых функций непрерывных переменных представлена в Приложении 1. Набор тестовых функций, используемых в диссертации, представлен в Приложении 2. Используемые тестовые функции реализуют многие свойства, затрудняющие оптимизацию: многоэкстремальность, несепарабельность, овражность, множества постоянства, значения функции в глобальном оптимуме слабо отличается от значений в локальных и др.

1.2 Стандартный генетический алгоритм и исследование его работоспособности на тестовых задачах

Эволюционные алгоритмы (ЭА), предложенные впервые для решения задач адаптации, в дальнейшем интенсивно развивались как методы решения сложных задач оптимизации. Генетические алгоритмы (ГА) представляют собой семейство ЭА, имеющих общую схему. На сегодняшний день ГА доказали свою конкурентоспособность при решении многих NP-трудных задач поиска и оптимизации и особенно в практических приложениях, где математические модели имеют сложную структуру и применение классических методов невозможно.

В основе большинства концепций искусственного интеллекта лежит богатое разнообразие природных явлений. Один из примеров - искусственные нейронные сети, основная идея которых основывается на функционировании нейронов мозга. ГА являются направлением более общей теории ЭА, основанной на следующем принципе: «каждый биологический вид целенаправленно развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде».

ЭА базируются на коллективном обучающем процессе внутри популяции индивидуумов, каждый из которых представляет собой поисковую точку в пространстве допустимых решений данной задачи. Популяция случайно инициализируется, и затем охватывает лучшие регионы поискового пространства посредством случайных процессов селекции, мутации и рекомбинации. Окружающая среда представляет качественную информацию (степень пригодности) о поисковых точках (индивидуумах), а процесс селекции отбирает тех индивидуумов, у которых значение пригодности выше. Отобранные потомки являются, в свою очередь, родителями в следующем поколении. Механизм рекомбинации перемешивает генетическую информацию родителей (тем самым рождается один или несколько потомков), и наконец, механизм мутации способствует в некоторой степени обновлению генетической информации потомков. [18]

В 1975 г. вышла основополагающая книга Дж. Холланда “Адаптация в естественных и искусственных системах”, в которой был предложен первый генетический алгоритм. Термин "генетические алгоритмы" ввел в 1975 г. Д. Голдберг [43]. Его книга содержит детальное обсуждение, как теоретических аспектов ГА, так и возможных областей их применения:

- Искусственная жизнь,

- Автоматическое обучение,

- Извлечение данных (знаний),

- Инженерное проектирование,

- Планирование и управление,

- Моделирование, идентификация,

- Численная и комбинаторная оптимизация.

Итак, ГА базируются на теоретических достижениях синтетической теории эволюции, учитывающей микробиологические механизмы наследования признаков в природных и искусственных популяциях организмов, а также на накопленном человечеством опыте в селекции животных и растений.

Методологическая основа ГА зиждется на гипотезе селекции, которая в самом общем виде может быть сформулирована так: чем выше приспособленность особи, тем выше вероятность того, что в потомстве, полученном с ее участием, признаки, определяющие приспособленность, будут выражены еще сильнее [3].

Т.о. ГА заимствуют из биологии:

- понятийный аппарат;

- идею коллективного поиска экстремума при помощи популяции особей;

- способы представления генетической информации;

- способы передачи генетической информации в череде поколений (генетические операторы);

- идею о преимущественном размножении наиболее приспособленных особей.

1.2.1 Представление решений в ГА

Подобно тому, как природный хромосомный материал представляет собой линейную последовательность различных комбинаций четырех нуклеотидов, решения в ГА представляются в виде хромосом (генотипов). Генотип - строка конечной длины, состоящая из генов, представленных символами некоторого алфавита.

В ГА существует строгое различие между фенотипом (решением, выраженным в терминах поставленной задачи) и генотипом (хромосомой, представлением решения). ГА работает с генотипом, фенотип служит для определения пригодности индивида (оценки качества решения поставленной задачи), поэтому для работы алгоритма необходимо определить некоторую функцию кодирования (, где - пространство поиска, - пространство представлений решений) и функцию декодирования (). Т.о. на самом деле ГА решают не задачу , где , а задачу , где и .

На практике наибольшее распространение получили ГА с бинарным представлением решений. Формально они решают задачу псевдобулевой оптимизации (2), т.е.

, где .

Как отмечалось в п.1.1., к задаче (2) сводятся практически любые задачи с дискретными переменными (возможно выраженные в разных шкалах), а также задачи с непрерывными переменными (заменяя непрерывные переменные дискретными с заданной точностью). Наиболее часто используются стандартное бинарное кодирование и бинарные коды Грея.

1.2.2 Общая схема ГА

В общем виде работу генетического алгоритма можно представить следующим образом:

1. Инициализировать случайным образом популяцию решений.

2. С помощью оператора селекции выбрать часть популяции (родителей) для порождения потомков.

3. Применить оператор скрещивания.

4. Новые решения (потомки) подвергаются мутации.

5. Формируется новая популяция: выбрать решения из родителей и потомков.

6. Повторять 2 - 5 пока не выполнится условие остановки.

1.2.3 Инициализация

На шаге инициализации задаются параметры алгоритма: длина хромосомы, размер популяции и др., а также типы и вероятности применения основных генетических операторов (скрещивания, мутации и селекции). Если априорные сведения о пространстве поиска отсутствуют, начальная популяция генерируется случайным образом.

1.2.4 Селекция

Оператор селекции - оператор, посредством которого индивиды выбираются для порождения потомков или для перехода в следующее поколение. Наиболее приспособленные особи должны выбираться с большей вероятностью для сохранения своих генов в следующем поколении. Т.о., оператор селекции позволяет сконцентрировать поиск на наиболее многообещающих регионах пространства.

Предложено множество различных схем отбора в ГА. Конкретный тип оператора селекции (а также и др. генетических операторов) проектируется исходя из решаемой задачи (например, когда требуется контроль допустимости решений, учет ограничений, многокритериальности и т.д.), однако наиболее распространены следующие базовые типы селекции.

В пропорциональной селекции вероятность индивида быть отобранным пропорциональна его пригодности. Вероятность вычисляется следующим образом (для задачи минимизации):

,

где - размер популяции, , .

Пропорциональная селекция обладает следующими недостатками: преждевременная сходимость и стагнация.

Стагнация возникает, когда на определенном этапе поиска все индивиды получают относительно высокую и примерно равную пригодность, что приводит к очень низкому селективному давлению (наилучшее решение лишь немного предпочитается худшему).

Преждевременная сходимость (проблема супериндивида) возникает, когда на ранних этапах появляется индивид с пригодностью намного большей, чем у других индивидов в популяции, но очень плохой с точки зрения решаемой задачи. Вероятность супериндивида быть отобранным стремится к единице, в то время как вероятности других членов популяции - к нулю. В итоге он копирует себя в следующее поколение и вскоре «широкий» поиск прекращается.

При применении ранговой селекции индивиды популяции ранжируются в соответствии с их пригодностью: если . Тогда

, где .

Ранговая селекция устраняет недостатки пропорциональной: нет стагнации, т.к. даже к концу работы алгоритма , нет преждевременной сходимости, т.к. нет индивидов с вероятностью отбора близкой к единице.

В турнирной селекции для отбора индивида создается группа из t (t 2) индивидов, выбранных случайным образом. Индивид с наибольшей пригодностью в группе отбирается, остальные - отбрасываются. Параметр t называется размером турнира. Наиболее популярным является бинарный турнир. Этот тип селекции не требует сортировки популяции и вычисления пригодности для всех индивидов. Недостатки: худший индивид никогда не выбирается.

Селекция с усечением. В процессе селекции с усечением с порогом , только доля из всех лучших индивидов может быть отобрана, причем в этой доле каждый имеет одинаковую вероятность отбора.

Элитарная селекция. Как минимум одна копия лучшего индивида всегда переходит в следующее поколение. Преимущества: гарантия сходимости. Недостатки: большой риск захвата локальным оптимумом.

1.2.5 Скрещивание

Оператор скрещивания (рекомбинация) - генетический оператор поиска. При скрещивании отобранные индивиды (родители) по заданному правилу передают части своих хромосом. Потомок может унаследовать только те гены, которые есть у его родителей. Существуют различные схемы скрещивания: точечное, равномерное, скрещивание более чем двух родителей и другие. При точечном скрещивании для выбранных родителей выбираются точки разрыва хромосомы, родители определенным образом обмениваются соответствующими участками хромосом. При равномерном - соответствующий ген потомка может быть унаследован от любого родителя с равной вероятностью. Скрещивание осуществляется с вероятностью , иначе с вероятностью родители клонируются в следующее поколение.

Наиболее популярным типом скрещивания является одноточечное скрещивание - случайно выбирается точка разрыва, родительские хромосомы разрываются в этой точке и обмениваются правыми частями (рис. 1).

Рис. 1. Одноточечное скрещивание.

При двухточечном скрещивании хромосома как бы замыкается в кольцо, выбираются 2 точки разрыва, родитель обмениваются частями (рис. 2).

Рис. 2. Двухточечное скрещивание.

При равномерном скрещивании потомок может унаследовать с равной вероятностью гены любого из родителей (рис. 3).



Рис. 3. Равномерное скрещивание.

Равномерное скрещивание по всей популяции (uniform gene pool recombination) получается применением равномерного скрещивание к всем членам популяции, т.е. потомок может унаследовать любой ген, имеющийся в популяции в заданной позиции хромосомы [53].

1.2.6 Мутация

Оператор мутации - одноместный оператор поиска, случайное изменение в одном или нескольких генах индивида. В ГА мутация рассматривается как метод восстановления потерянного генетического материала, а не как поиск лучшего решения. Мутация применяется к генам с очень низкой вероятностью . Хорошим эмпирическим правилом считается выбор вероятности мутации равным , где - число генов в хромосоме (в среднем хотя бы один ген будет подвержен мутации). В случае бинарного алфавита мутация состоит в инвертировании случайно выбранных битов (рис. 4).

Рис. 4. Пример мутации в ГА.

1.2.7 Пригодность индивидов (fitness - функция)

Пригодность индивида - это некоторая количественная оценка качества решения поставленной задачи. Функция пригодности может быть спроектирована с учетом особенностей решаемой задачи (что делает ГА довольно гибким, универсальным). Обычно функция пригодности принимает положительные значения, и значение пригодности максимизируют.

В общем случае при решении задач безусловной оптимизации в качестве значения функции пригодности может выступать значение оптимизируемого функционала ().

1.2.8 Исследование работоспособности на тестовых задачах

Для исследования работоспособности ГА была разработана программная система «GA lab», реализующая практически все основные параметры алгоритма. Эффективность алгоритма проверялась на тестовых функциях 1, 3, 4, 6-8, 15. Исследования проводились для ГА с одноточечным скрещиванием и ГА с равномерным скрещиванием по всей популяции. Реализованы пропорциональная, ранговая и турнирная (размер турнира - 2) селекции, низкая и высокая мутации. Использовалось стандартное бинарное и кодирование Грея. Размер популяции - 50. Количество прогонов алгоритма - 50.

Для оценки эффективности алгоритмов использованы два показателя: надежность и среднее число итераций. Надежность - процент успешных запусков (решение найдено) к общему числу запусков алгоритма. Среднее число итераций - номер итерации, когда найдено решение, усредненный по успешным прогонам. Алгоритм с наибольшей надежностью всегда считается лучшим. Среди алгоритмов с одинаковой надежностью - лучший тот, у которого наименьшее среднее число итераций.

Результаты тестирования представлены в таблице 1 (серым выделен алгоритм «победивший» на данной тестовой задаче). Из таблицы видно, что наиболее эффективным оказывается использование высокой мутации, которая помогает избежать локальной сходимости даже при использовании пропорциональной селекции (победители на Ф4, Ф6, Ф8). Код Грея в сочетании с представленными алгоритмами оказался не достаточно эффективным на Ф6 и Ф8, т.к. на этих функциях было бы лучше если соседние в бинаризованном пространстве точки оказались далекими в исходном - для Ф6 структура локальных оптимумов могла бы нарушиться, и оптимумов могло бы стать меньше; для Ф8 в новой системе окрестностей могли нарушиться множества постоянства.

Таблица 1. Сравнительный анализ эффективности генетических алгоритмов.

Тестовая задача	Тип селекции	ГА с одноточечным скрещиванием (низкая мутация)	ГА с одноточечным скрещиванием (высокая мутация)	ГА с равномерным скрещиванием по всей популяции (низкая мутация)	ГА с равномерным скрещиванием по всей популяции (высокая мутация)
		Код Грея	Бинарный код	Код Грея	Бинарный код	Код Грея	Бинарный код	Код Грея	Бинарный код
		Надеж-ность	Ср. число итер.	Надеж-ность	Ср. число итер.	Надеж-ность	Ср. число итер.	Надеж-ность	Ср. число итер.	Надеж-ность	Ср. число итер.	Надеж-ность	Ср. число итер.	Надеж-ность	Ср. число итер.	Надеж-ность	Ср. число итер.
Ф1	пропорц.	24	19	54	15	82	31	76	18	52	28	64	18	87	34	84	18
	ранг.	26	32	56	20	84	32	100	18
	турнир.	16	15	46	9	34	15	46	12
Ф3	пропорц.	74	25	20	9	82	31	26	9	84	20	25	16	81	32	20	16
	ранг.	34	29	28	12	83	28	85	28
	турнир.	24	15	10	10	44	17	24	10
Ф4	пропорц.	2	48	6	13	44	30	8	15	10	27	5	14	27	25	16	20
	ранг.	4	25	10	10	0	0	24	20
	турнир.	6	14	4	14	2	6	8	12
Ф6	пропорц.	4	14	18	9	28	30	20	19	7	12	14	16	11	32	24	20
	ранг.	0	0	12	9	2	36	14	18
	турнир.	2	10	10	7	0	0	4	12
Ф7	пропорц.	10	28	20	5	48	26	58	14	25	17	36	11	60	23	63	20
	ранг.	10	18	30	7	14	28	18	30
	турнир.	16	16	14	6	10	20	22	7
Ф8	пропорц.	0	0	0	0	0	0	7	17	0	0	2	7	0	0	5	25
	ранг.	0	0	0	0	0	0	6	30
	турнир.	0	0	2	8	0	0	0	0
Ф15	пропорц.	52	29	52	18	50	32	36	22	70	27	22	20	87	32	34	20
	ранг.	26	33	46	16	98	36	48	23
	турнир.	12	11	12	11	50	23	28	18

1.3 Метод изменяющихся вероятностей (МИВЕР) и исследование его работоспособности на тестовых задачах

1.3.1 Общая схема МИВЕР

Метод изменяющихся вероятностей представляет собой семейство стохастических алгоритмов псевдобулевой оптимизации, имеющих общую схему, в основе которой лежит алгоритм случайного поиска с адаптацией [1]. В самом общем виде эта схема (обозначим МИВЕР1) применительно к задаче (2) выглядит следующим образом:

1. Задаются начальные значения компонент вектора вероятностей , .

2. Случайным образом (в соответствии с распределением вероятностей ), независимо выбираются векторов .

3. Вычисляются соответствующие значения функционала .

4. Определяются и . Значения и и соответствующие векторы и запоминаются.

5. По результатам п. 4 изменяются (в соответствии с правилом конкретного алгоритма) компоненты вектора вероятностей .

6. Пункты 2-5 повторяются раз.

7. За решение задачи принимается вектор , определяемый из условия ( при повторении п. 4).

Начальное распределение вероятностей единичных значений компонент вектора - определяется на основе априорной информации о решаемой задаче. Если такая информация отсутствует, используется равновероятностное распределение, т.е. .

Пункт 5 соответствует получению апостериорного распределения вероятностей по результатам испытаний п. 2 и п. 3.

В [1] предложены следующие алгоритмы пересчета вектора вероятностей единичных компонент: СПА, МСПА1, МСПА2:

СПА :

.

МСПА1 :

,

.

МСПА2 :

,

.

Первоначально метод был реализован для задачи условной псевдобулевой оптимизации, поэтому для безусловной оптимизации метод модифицирован так, что решение ищется во множестве . Множество . Общая схема (обозначим МИВЕР2) имеет вид:

1. Задаются начальные значения компонент вектора вероятностей , .

2. Случайным образом (в соответствии с распределением вероятностей ), независимо выбираются векторов и соответствующие значения по правилу .

3. Вычисляются соответствующие значения функционала .

4. Из условий и находятся векторы и . Значения и запоминаются. По правилу: , для ;

;

,

где и - число единичных компонент векторов и соответственно, определяются векторы и , которые тоже запоминаются.

5. По результатам п. 4 изменяются (в соответствии с правилом конкретного алгоритма (СПА, МСПА1, МСПА2)) компоненты вектора вероятностей .

6. Пункты 2-5 повторяются раз.

7. За решение задачи принимается вектор , определяемый из условия ( при повторении п. 4).

СПА :

, где .

МСПА1 и МСПА2меняются аналогично.

1.3.2 Исследование работоспособности на тестовых задачах

Методы МИВЕР1 и МИВЕР2 был программно реализованы. Исследование алгоритмов СПА, МСПА1 и МСПА2 проводилось на тестовых функциях: функция Растригина (первоначально бинаризуется) и многоэкстремальная псевдобулевая функция.

Задача 1. Дискретная функция Растригина:

, .

.

Задача 2. Задача псевдобулевой оптимизации:

, . .

Для исследования эффективности использовались показатели надежности и среднее число итераций. Показатели вычислялись по статистике набранной из 100 запусков алгоритмов. Для всех алгоритмов . Работа МИВЕР1 и МИВЕР2 сравнена с ГА. Результаты исследования эффективности представлены ниже. Результаты работы алгоритмов с наилучшими настройками представлены в таблице 2.

Задача 1.

ГА.

Надежность алгоритма (%):Среднее число итераций до определения минимума:

МИВЕР1.

Надежность алгоритма (%):Среднее число итераций до определения минимума:

МИВЕР2.

Алгоритм не находит глобальный оптимум задачи.

Задача 2.

ГА.

Надежность алгоритма (%):Среднее число итераций до определения минимума:

МИВЕР1.

Надежность алгоритма (%):Среднее число итераций до определения минимума:



МИВЕР2.

Надежность алгоритма (%):Среднее число итераций до определения минимума:

Таблица 2. Сравнительный анализ эффективности МИВЕР и ГА.

	ГА	МИВЕР1	МИВЕР2
	Надеж-ность	Ср. число итер.	Надеж-ность	Ср. число итер.	Надеж-ность	Ср. число итер.
Задача 1	92	32	61	42	-	-
Задача 2	98	28	68	34	74	60

Из таблицы 2 видно, что ГА превосходит МИВЕР и по трудоемкости, и по надежности (МИВЕР2 не решил задачу 2).

1.4 Основные идеи вероятностного генетического алгоритма и исследование его работоспособности на тестовых функциях

Нетрудно понять, что ГА накапливают и обрабатывают некоторую статистическую информацию о пространстве поиска, однако эта статистика в явном виде отсутствует. Можно предложить следующий способ представления накопленной генетическими алгоритмами статистики - на текущей итерации в соответствие популяции решений ставить вектор вероятностей

,(3)

где - вероятность присвоения i-ой компоненте вектора решения значения 1, k - номер итерации.

Для изучения работы алгоритмов изменения компонент вектора вероятностей будем представлять в виде графиков. Ниже представлены примеры типичного поведения компонент для алгоритмов МИВЕР (рис. 5) и ГА (рис. 6).



Рис. 5. Пример изменения вероятностей в МИВЕР.

Рис. 6. Пример изменения вероятностей в ГА.

Из графиков видно, что в МИВЕР вероятности меняются линейно (в СПА, МСПА1 и МСПА2 «поощряющие» добавки прибавляются либо вычитаются), в ГА - нелинейно, т.к. новая популяция может значительно отличаться от предыдущей. Однако, в предельном случае (мутация отсутствует, пропорциональная селекция) изменение вероятностей близко линейному.

Когда какая-либо компонента вектора вероятностей сходится к 0 или 1, поиск по этой компоненте прекращается, что может привести к «захвату» локальным минимумом. В ГА поиск не прекращается, т.к. оператор мутации «выкидывает» решения в новые регионы поискового пространства. Мутация вызывает скачкообразные изменения (скачки тем больше, чем выше мутация) компонент вектора вероятности даже после того, как компонента сходится к 0 или 1, что придает ГА глобальные свойства. Очевидно, вероятности в МИВЕРе тоже не должны обращаться в 0 или 1, иначе алгоритм станет локальным. Нелинейное изменение вероятностей в ГА позволяет алгоритму находить решение быстрее, чем МИВЕР (показано в численных экспериментах).

Попробуем проанализировать работу ГА с точки зрения теории псевдобулевой оптимизации, рассмотрим основные шаги ГА.

Инициализация. Если априорная информация о пространстве поиска отсутствует, то начальная популяция решений формируется случайно - точки распределяются равномерно в бинаризованном пространстве поиска, т.е. .

Оператор скрещивания - генетический оператор поиска, посредством которого из выбранных индивидов (родительские особи) получаются новые (потомки). Решение, представленное бинарным вектором является вершиной n-мерного гиперкуба в булевом пространстве. Оператор скрещивания будет генерировать точки из некоторого подмножества, размерность которого определяется числом совпадающих бит в соответствующих позициях родительских особей. Легко показать, что одноточечное или двухточечное скрещивание не может получить все точки полученного подпространства, равномерное - может.

Для примера рассмотрим действие оператора скрещивание при и родителях и . Потомок может унаследовать любые гены родителей, т.е. решение, полученное при скрещивании может содержать 0 или 1 в любой позиции. Однако, при применении одноточечного скрещивания будут получены решения: , , .

В общем случае, если даны и , где и , то с помощью равномерного скрещивания можно получить различных точек. При одноточечном скрещивании мы имеем «эффективных» точек разрыва, разрыв в остальных точках не даст новых точек. При каждом «эффективном» скрещивании мы получим 2 потомка, т.е. при одноточечном скрещивании можно получить всего новых точек.

Очевидно, что равномерное скрещивание является наиболее полным оператором, который в частном случае может получить и одноточечное, и многоточечное скрещивание. Т.о., с точки зрения широты охвата пространства поиска (разнообразия популяции) равномерное скрещивание предпочтительней. Исключением могут быть те случаи, когда известны свойства оптимизируемого функционала, и точечное скрещивание использует эти свойства.

Попробуем сформулировать равномерное скрещивание в «негенетических» терминах. Пусть для формирования потомка используется родителей (), где - размер популяции. Им соответствует статистика , где .

При статистика совпадает с . Потомок формируется в соответствии со статистикой . Такой оператор поиска соответствует теории генетических алгоритмов, содержит в себе свойства оператора скрещивания и имеет математически ясную формулировку.

Оператор мутации - оператор широкого поиска, т.к. в результате его применения возможно появление решений вне данной статистики. Если компонента вектора вероятностей обращается в 0 или 1, то поиск по компоненте вектора решения прекращается. Мутация предотвращает появление предельных значений компонент вектора вероятностей.

Оператор селекции - оператор, который каждому решению (в зависимости от качества решения) ставит вероятность быть отобранным. Наиболее приспособленные индивиды с большей вероятностью переходят в следующее поколение. На этом шаге происходит получение апостериорной информации о поисковом пространстве. В результате статистика меняется, компоненты вектора вероятностей смещаются в сторону распределения единичных компонент наиболее приспособленных решений.

1.4.1 Общая схема вероятностного генетического алгоритма

Попробуем сформулировать в «негенетических» терминах алгоритм, имеющий общую с генетическим алгоритмом схему, сохраняющий свойства генетических операторов. Такой вероятностный генетический алгоритм (ВГА) применимо к задаче (2) имеет следующую схему:

1. Случайным образом формируются векторов . Вычисляется распределение , . Вычисляются соответствующие значения оптимизируемого функционала .

2. На k-м шаге в соответствии с распределением формируются векторов .

3. Случайным образом формируются новые решения: с вероятностью компоненты векторов меняются на противоположные.

4. Вычисляются соответствующие значения функционала .

5. Выбираются векторов из в соответствии с конкретным правилом отбора.

6. Пересчитывается распределениеединичных компонент .

7. Если не выполняется условие остановки, то , , повторить шаги 2 - 6.

Если априорная информация о пространстве поиска отсутствует, . На шаге 2 выполняется поиск в соответствии с имеющейся статистикой, аналогичный скрещиванию в ГА. На шаге 3 происходит поиск вне имеющейся статистики - оператор мутации. На шаге 5 происходит получение апостериорной информации, и происходит пересчет распределения вероятностей единичных компонент.

1.4.2 Исследование работоспособности на тестовых задачах

Предложенный ВГА был реализован в программной системе «ProbGA» и апробирован на функциях 1-15. Результаты работы ВГА были сравнены с результатами работы стандартного ГА (таблица 3). Использовались следующие настройки: размер популяции - 50, максимальное число итераций - 50, число прогонов алгоритма - 50, мутация - высокая, селекция - ранговая.

Из таблицы видно, что ВГА превосходит обычный ГА: ВГА победил в 11 из 15 случаев (Ф3, Ф4, Ф6-Ф11,Ф13-Ф15), на Ф12 одинаково эффективен с ГА. В тех случаях, когда ВГА оказывается эффективней, разница в надежности существенная, когда побеждает обыкновенный ГА - ВГА проигрывает не значительно.

Обычный ГА выигрывает на функциях Ф1, Ф2 (многоэкстремальные функции одной переменной) и Ф5 (унимодальная, овражного типа), Ф12 имеет большую зону притяжения глобального минимума, в Ф13 и Ф14 значение в глобальном оптимуме значительно отличается от значений в ближайших локальных.

Таким образом, численные эксперименты показывают, что ВГА превосходит обычный ГА на наиболее сложных для оптимизации функциях, и не менее эффективен на более простых.

Таблица 3. Сравнительный анализ эффективности ВГА и стандартного ГА.

	Вероятностный ГА	ГА
	Код Грея	Бинарный код	Оптимальные параметры
	Надежность	Ср. число итер.	Надежность	Ср. число итер.	Надежность	Ср. число итер.
Ф1	88%	16	96%	15	100%	18
Ф2	96%	6	96%	6	100%	19
Ф3	100%	15	64%	24	85%	28
Ф4	78%	25	52%	27	44%	30
Ф5	84%	6	98%	10	100%	18
Ф6	56%	21	60%	29	28%	30
Ф7	82%	28	20%	31	7%	17
Ф8	100%	16	92%	16	86%	12
Ф9	100%	11	50%	20	76%	12
Ф10	100%	20	32%	25	36%	10
Ф11	100%	13	32%	24	28%	10
Ф12	100%	14	100%	8	100%	8
Ф13	100%	4	100%	6	100%	8
Ф14	100%	5	100%	8	100%	6
Ф15	100%	10	100%	19	98%	36

1.5 Алгоритм прогноза сходимости вероятностного генетического алгоритма

В результате анализа графиков изменения компонент вектора вероятностей (3) в ВГА было замечено следующее свойство: изменения компонент вектора вероятностей в ВГА происходят целенаправленно, в среднем компоненты вектора вероятностей сходятся к истинным значениям, т.е.

. (4)

Если предположить, что свойство (4) справедливо для ВГА при решении задачи (2), то это свойство можно использовать для прогноза сходимости генетических алгоритмов.

Построен следующий алгоритм прогноза:

1. Для данной задачи выбрать определенную схему ГА, определить число итераций и число прогонов алгоритма .

2. Набрать статистику . Усреднить по . Выявить тенденцию изменения компонент .

3. Считать .(5)

Однако, в результате частного прогона при малых решение может быть не найдено, и может принимать значения отличные от . Тогда среднее значение компонент может сместиться в противоположную сторону, либо слабо отличаться от . Поэтому для обеспечения сходимости к оптимуму, было предложено придавать веса компонентам вектора вероятностей в соответствии с результатом прогона. Т.е. наилучшие прогоны вносят больший вклад в среднее значение, наихудшие - меньший. Для прогноза вместо (5) можно использовался следующий интегральный критерий:

.(6)

Т.о. решение о том, что принимается, когда чаще оказывается больше 0.5 (а также дальше от 0.5). Пример усреднения компонент вектора вероятностей в алгоритме прогноза показан на рисунке 7. Сплошная линия - с использованием критерия (5) и пунктирная - интегральный критерий (6).