Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем
Диссертация - Менеджмент
Другие диссертации по предмету Менеджмент
?о времени приемлемое решение не найдено, и весь код деревьев эффективный, то увеличить глубину деревьев на 1. Исходные деревья становятся левыми поддеревьями корня.
4.Если приемлемое решение найдено, то СТОП, иначе повторить
шаги 2 - 4.
Рис. 18. Пример наращивания деревьев.
При увеличении глубины дерева на 1 старое дерево должно становится поддеревом слева, так как при появлении в корне функции одной переменной, правое поддерево игнорируется. Т.е. если бы исходное дерево стало поддеревом справа, мы бы игнорировали результаты поиска на предыдущих поколениях.
2.3.1Общая схема метода вероятностного генетического программирования
На основе предложенного выше способа кодирования и интерпретации полных деревьев построена схема метода ГП, основанная на механизме ВГП. Такая схема получила название вероятностное генетическое программирование (ВГП):
1.Случайным образом формируются векторов . Вычисляется распределение , .
.На k-м шаге в соответствии с распределением формируются векторов .
.Случайным образом формируются новые решения: с вероятностью компоненты векторов меняются на противоположные.
.На основе векторов формируются полные деревья решений, интерпретируются решения, решения оцениваются.
.Выбираются векторов из в соответствии с конкретным правилом отбора.
.Пересчитывается распределение единичных компонент .
.Если не выполняется условие остановки, то , , повторить
шаги 2 - 6.
Оценивание деревьев в п. 4 происходит по критерию (7), аналогично обычному ГП.
2.3.2Исследование работоспособности на тестовых задачах
1. Функция: . Выборка: случайная, объем - 1000 точек.
Терминальное множество: , где .
Функциональное множество: .
Размер популяции: 100. Глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.
Найдено точное решение: .
Поколение: 89.
. Функция Растригина: . Выборка: случайная, объем - 1000 точек.
Терминальное множество: , где .
Функциональное множество: .
Размер популяции: 100. Глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.
Найдено решение: .
Ошибка (квадратичный критерий): 2.28.
Поколение: 1000.
. Функция: . Выборка: случайная, объем - 100 точек.
Терминальное множество: , где .
Функциональное множество: .
Размер популяции: 100. Глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.
Найдено решение: .
Ошибка (квадратичный критерий): 1.15.
Поколение: 180.
2.4 Выводы
Во второй главе рассмотрены методы аппроксимации статистических данных в задаче моделирования сложных систем. Поставлена задача символьной регрессии.
Рассмотрены способ представления решений в методе генетического программирования, основные генетические операторы и общая схема метода. Разработан алгоритм решения задачи символьной регрессии с использованием метода генетического программирования. Показана работоспособность предложенного алгоритма на тестовых функциях.
Предложен способ бинарного кодирования и интерпретации полных деревьев заданной глубины. Предложен алгоритм наращивания деревьев, позволяющий в случае необходимости постепенно усложнять получаемые выражения, повышая тем самым возможности аппроксимации.
Впервые предложен метод вероятностного генетического программирования, использующий механизм вероятностного генетического алгоритма, позволяющий более активно использовать информацию о пространстве поиска. Экспериментально показано, что метод вероятностного генетического программирования позволяет эффективно решать задачу аппроксимации статистических данных, и в отличие от известных методов позволяет получать аппроксимации в виде символьных выражений (математических формул).
Глава III. Практическая реализация разработанных алгоритмов
.1Программная реализация обыкновенного и вероятностного генетического алгоритмов
На основе рассмотренного в п. 1.2. стандартного ГА и предложенного ВГА разработаны программные системы: GA lab и ProbGA lab.
В качестве рабочей операционной системы (ОС) был выбрана Microsoft Windows, поскольку она является наиболее распространенной ОС, 32 битные приложения одинаково эффективно работают в различных версиях Windows: 9x, ME, 2000, NT, XP, ОС Windows обладает удобным и очень гибким интерфейсом [32].
В качестве среды программирования был выбран Borland C++ Builder, т.к. он обладает следующими свойствами:
-Язык C++ объектно-ориентированный, обеспечивает наследование, полиморфизм, абстракцию данных.
-Оптимизирующий 32-разрядный компилятор обеспечивает исключительно падежную и быструю оптимизацию, как длины выходного исполняемого кода, так и расходуемой памяти.
-Инкрементальный линкер осуществляет быструю и надежную сборку приложений в формате ЕХЕ файлов сравнительно меньшего размера [2, 31].
-Чистый и доступный код приложений, которые C++ Builder строит на основе предоставляемых разработчику компонентных свойств, событий и методов, исключает скрытые и трудные в отладке макросы.
-Создание DLL, LIB, и ЕХЕ файлов предоставляет свободу выбора формата целевого приложения в соответствии с требованиями конкретного проекта.
-Прямое обращение к системным функциям Windows 9x и NT дает возможность программистам, работающим в среде C++ Builder при необходимости воспользоваться всеми возможностями современных операционных систем [33].
3.1.1Программная с