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

• Автор: Петров, Юрий Юрьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Ставрополь
• Количество страниц: 284 с. : ил.

ОГЛАВЛЕНИЕ

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МОДИФИКАЦИЙ ГЕНЕТИЧЕСКОГО АЛГОРИТМА И ИХ ПРИМЕНЕНИЕ В ТЕХНИЧЕСКИХ СИСТЕМАХ.

1.1 Обзор и анализ генетических алгоритмов

1.2. Анализ основных направлений повышения эффективности генетических алгоритмов.

1.3 Анализ применимости генетических алгоритмов и их модификаций в технических системах.

1.4 Обзор существующих программных комплексов, реализующих

оптимизацию с помощью генетических алгоритмов.

ВЫВОДЫ К ПЕРВОЙ ГЛАВЕ.

ГЛАВА 2. РАЗРАБОТКА СПОСОБА УВЕЛИЧЕНИЯ ВЕРОЯТНОСТИ НАХОЖДЕНИЯ ГЛОБАЛЬНОГО ЭКСТРЕМУМА ГЕНЕТИЧЕСКИМ АЛГОРИТМОМ.

2.1 Построение и анализ математической модели генетического алгоритма

2.2 Разработка способа регуляции генетических операторов
ВЫВОДЫ КО ВТОРОЙ ГЛАВЕ
ГЛАВА 3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА С ПОВЫШЕНОЙ ВЕРОЯТНОСТЬЮ НАХОЖДЕНИЯ ГЛОБАЛЬНОГО ЭКСТРЕМУМА БЕЗ УВЕЛИЧЕНИЯ ВРЕМЕНИ СХОДИМОС ТИ
3.1 Разработка новых методов обновления генетического материала.
3.2 Генетический алгоритм с регуляцией вероятностей генетических операторов и с равномерным распределением потомков.
3.3 Применение разработанного алгоритма в технических системах
ВЫВОДЫ К ТРЕТЬЕЙ ГЛАВЕ
ГЛАВА 4.ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ С РЕГУЛЯЦИЕЙ ВЕРОЯТНОСТЕЙ ГЕНЕТИЧЕСКИХ ОПЕРАТОРОВ И МУТАЦИЕЙ С РАВНОМЕРНЫМ
РАСПРЕДЕЛЕНИЕМ ПОТОМКОВ.
4Л Методика тестирования генетических алгоритмов
4.2 Описание программного комплекса тестирования генетических
алгоритмов
ВЫВОДЫ К ЧЕТВЕРТНОЙ ГЛАВЕ.
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ


Принципиальные отличия ГА и ЭА [, , , , , , , , 2, ИЗ] состоят в выборе объекта, возможности которого исследуются с точки зрения эволюционной адаптации. ГА ориентированы на исследования возможностей генетического материала, а в ЭА задача сводится к изучению поведения фенотипа [, ]. ГА ориентированы на применение операторов, которые изменяют генотип. В зависимости от результатов работы операторов на втором этапе соответственно изменяется и фенотип. Стандартный вариант ГА - ПГА был предложен в работах [, , , , 1, 2, 9]. Данный метод оказался эффективным не только при решении реальных инженерных проблем, но и при исследовании биологических, экономических, химических процессов. Эволюционный процесс представляется как способность более адаптированных особей оказывать большее влияние на состав новой популяции на основе длительного выживания и многочисленного потомства [, ]. Дх), X е Д (1. Дх) - целевая функция (приспособленность особи х). Примерами служат задачи размещения, стандартизации, выполнимости и другие [9, , 5]. В технических задачах оптимизации часто вместо понятия «приспособленность» используется целевая функция []. Генотип X кодируются бинарной строкой s с помощью функции кодирования s = g(x). Для обратного отображения s в х используется функция декодирования л: = g~s). Наиболее часто используется бинарная кодировка для представления элемента популяции, выбор которой определяется тем, что двоичный алфавит позволяет обрабатывать максимальное количество информации по сравнению с другими схемами кодирования []. В зависимости от свойств конкретной решаемой задачи обе схемы кодирования имеют свои достоинства и недостатки. Инициализация начальной популяции: инициализировать N случайных генотипов особей и сформировать из них начальную популяцию Р = {. Кроссинговер: выбрать из популяции вторую особь 5* с помощью оператора отбора и с вероятностью Рк особи и в'/' скрещиваются оператором кроссинговера; полученный потомок обозначить 5*. Переход к следующей особи: присвоить к = к + 1; если к = И, тогда перейти к шагу 8, иначе перейти к шагу 3. Р особь . Формирование нового поколения: Сформировать из полученных особей новую популяцию Я'= {. Р2у. Условие окончания работы алгоритма: если условие окончания работы алгори тма не выполняется, то перейти к шагу 3, иначе в качестве ответа взять особь с наилучшей приспособленностью. Блок-схема ПГА изображена на рис . Рисунок 1. Шаблоны определяются с помощью элементов множества {0, 1,*} и для данного шаблона Не {0, 1, *}/ строка А является одним из представителей данного шаблона тогда и только тогда, когда биты в специфицированных позициях шаблона (то есть, биты, содержащие 0 или 1) идентичны соответствующим битам строки А. Символ «*» означает, что в данной позиции строки бит может принимать значение 1 или 0 []. Очевидно, что для алфавита мощности к существует (к + 1); шаблонов (схем), определенных на хромосоме длиной /. Более того, существует 2! М схем, содержащихся в популяции размера Н, поскольку каждая строка может быть представлена минимум двумя схемами [, ,2]. Выбор двоичного алфавита приводит к оценке 0( п ) структур в течение одного поколения популяции, хотя в реальности популяция содержит только / индивидуумов. Этот эффект носит название неявного параллелизма [, , , 1]. ГА обладают следующими преимуществами: они не требуют никакой дополнительной информации о поверхности целевой функции; разрывы, существующие на ней, незначительно влияют на эффективность оптимизации; генетические алгоритмы устойчивы к попаданию в локальные оптимумы; хорошо работают при решении задач многоцелевой оптимизации; могут быть использованы для широкого класса задач; просты и прозрачны в реализации; они могут быть использованы в задачах с изменяющейся средой. ГА легко и удобно распараллеливать. Можно разбить поколение на несколько групп и работать с каждой из них независимо, обеспечивая время от времени межгрупповой обмен несколькими хромосомами. Существуют также и другие методы распараллеливания ГА. ГА обладают и существенными недостатками.