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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 075. 8
В. А. Иванюк, И. Е. Егорова
РАЗРАБОТКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ
Волгоградский государственный технический университет
Hedin99@mail. ru
Раскрывается сущность генетического алгоритма, рассматривается терминология, описываются достоинства и недостатки генетического алгоритма. Приводится пример использования генетического алгоритма на примере решения задачи многомерной оптимизации.
Ключевые слова: генетический алгоритм, оптимизация, система.
V. A. Ivanyuk, I. E. Egorova
DEVELOPMENT OF PROGRAM IMPLEMENTATION OF GENETIC ALGORITHM FOR SOLVING MULTIVARIATE OPTIMIZATION
Volgograd State Technical University
The essence of the genetic algorithm, we consider the terminology, describes the advantages and disadvantages of genetic algorithm. Is an example of using a genetic algorithm on the example of solving the problem of multivariate optimization.
Key words: genetic algorithm, optimization, system.
Генетический алгоритм чаще всего используют в физике при большом количестве экспериментов, он позволяет ответить на вопрос существует ли скрытая зависимость между показателями или нет. Генетический алгоритм даем нам наиболее точную функциональную зависимость между показателями при ограниченном количестве по времени. Например, физики открыли квантовую запутанную пару испускаемую рубином благодаря генетическому алгоритму. Квантовая запутанная пара позволяет повысить скорость передачи данных вдвое. Открыли частицу «бозон», проведя миллионы экспериментов на коллайдере, сделав миллиард фотографий и обработав их с помощью генетического алгоритма. Генетический алгоритм по-
зволяет за один проход (цикл) просчитать 1000 уравнений. Таким образом в классическом понимании генетический алгоритм отвечает на вопрос есть скрытая зависимость между показателями в эксперименте или ее нет.
Сущность генетического алгоритма заключается в имитации процесса эволюции особей одного вида животных в замкнутом пространстве, в результате выживают наиболее приспособленные. Достоинства генетического алгоритма:
1. Высокая скорость нахождения решения в сравнении с другими стохастическими методами.
2. Достаточно низкая вероятность нахождения неверного решения (западание в локальный оптимум).
3. Четкая ограниченность точности по времени в зависимости от необходимой точности вычислений.
Далее будем рассматривать генетический алгоритм как типовой метод многофакторной оптимизации функции с несколькими переменными. Создадим алгоритм решения задач методом генетического алгоритма. На первом этапе введем основную терминологию, используемую при реализации генетического алгоритма.
Рассмотрим простейшую многофакторную функцию вида F (x1, X2… Xn) = fl (xl)*flX2) … fxn), где:
а) ген — соответствует одному из аргументов функции — один аргумент (^) или ^2) или (гз) и т. д.
б) особь — это полный набор аргументов с помощью которой выражается функция, x2 … xn), причем значения аргументов выбираются случайно.
в) популяция — это набор особей
г) критерий оптимизации функции (П) — это величина обратная расстоянию до искомого оптимума.
_1_______ _1_
ЛF '
П =
— F
ИСКОМАЯ 1 особи
где AF расстояние до искомого оптимума.
В случае оптимизации функции неизвестному значению критерия F, F^^^ будет являться наилучшим случайно найденным min или max функции.
д) отсев или вымирание — это удаление из популяции с наименьшим критерием выживания (П).
е) мутация — это случайные изменения случайно выбранного гена у случайно выбранной особи.
ж) кроссовер — операция, при которой из генов двух случайно выбранных родителей создается особь — потомок, помещающийся на место, освободившейся после смерти особи.
Ограничение времени работы генетического алгоритма может быть реализована тремя различными способами: 1 способ — временное ограничение- 2 способ — количественное ограничение циклов эволюции- 3 способ — способ естественной убыли — смертность превышает рождаемость.
Приведем блок схему работы генетического алгоритма (рис. 1).
Рис. 1. Блок-схема работы генетического алгоритма
Пункт 1. Вводим в программу основные критерии работы алгоритма: N — начальное число особей в популяции- S — количество эволюционных циклов, через которое происходит отсев- C — количество эволюционных циклов, через которое происходит кроссовер- M — количество эволюционных циклов, через которое происходит мутация. Необходимо, чтобы S & lt- C, значения S, C, M варьируем. Пункт 2. Создаем в памяти массив из N-Г переменных, где N -количество особей, Г — количество генов. Заполняем их случайными вещественными числами AeR. Пункт 3. Создаем массив из Д, еличин
Приспособленности. Используя критерий оптимизации и значения аргументов особей, рассчитываем для каждой особи ее приспособленность. Пункт 4. Проверяем не наступило ли время отсева. Не кратен ли счетчик циклов значению отсева. Пункт 5. Если да, находим особь с min значением П (критерий оптимизации функции). Помечаем занимаемое ею место как свободное. Пункт 6. Проверяем не кратно ли значение С счетчику цикла. Пункт 7. Если да (кратно), случайным образом выбираем двух родителей на свободное место в таблице особей, помещаем их значения генов (аргументов).
Пункт 8. Проверяем не наступило ли время мутации. Не кратен ли счетчик циклов числу М (мутации). Пункт 9. Получаем три случайных числа особь, а = 1 — Ы, ген Ь = 1 — Г, сєЯ. Особи с номером а, ген с номером Ь изменяем на с. Пересчитываем ее П (приспособленность). Пункт 10. Проверяем не осталась ли в живых одна особь. Пункт 11. Выводим как результат ее гены (аргументы). Пункт 12. Увеличиваем счетчик циклов.
Основным недостатком генетического алгоритма является то, что при программирова-
нии задачи невозможно создать универсальным код, описывающий функцию и критерий оптимизации, поскольку начальные условия задач всегда различны.
Рассмотрим пример использования генетического алгоритма. Задача заключается в отыскании параметров регрессии а, Ypot и Ь из уравнения
Р = а ln (Ypot — Y) + Ь, (1)
где Y — динамический ряд реального ВВП, Р -динамический ряд дефлятора (общий уровень цен) (таблица).
Таблица
Исходные данные
1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010
ВВП реальный дефлято- ры 372,30 100,8% 373,7892 100,4% 373,0416 99,8% 373,7877 100,2% 376,0304 100,6% 379,0387 100,8% 381,3129 100,6% 387,4139 101,6% 392,0629 101,2% 394,4153 100,6% 394,0208 99,9% 399,5371 101,4%
с C: WI N DOWSsystem 3 2cmd. exe
ostalos и populac11 6
ostalos и populac11 6
ostalos и populacii e
?stalos V populac ii e
?stalos V populac ii 5
?stalos V populac ii 5
Dstalos V populac ii 5
Dstalos V populac ii 5
Dstalos V populac ii 5
Dstalos V populac ii 5
Dstalos V populac ii 5
Dstalos V populac ii 5
Dstalos V populac ii 5
Dstalos V populac ii 5
Dstalos V populac ii 4
Dstalos V populac ii 3
Dstalos V populac ii 2
Dstalos и populac ii 1
105. 785
-1. 27 368
439. 894
2. 77 113
C: tg>-_
Рис. 2. Программная реализация генетического алгоритма
По условию задачи задано, что: а должно быть отрицательно, Ypot (потенциальный ВВП) должен быть больше всех значений Y, b любым числом.
Данная задача реализована программно в среде разработки dev C++ на языке программирования C++ (рис. 2).
Таким образом имеем следующие результаты: коэффициент, а равен -1. 27 368, коэффициент b равен 105. 785, коэффициент Ypot равен 439. 894. При этом сумма квадратов отклонений в каждой точке равна 2. 77 113.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Тейво Кохонен, Гвидо Дебок. Анализ финансовых данных с помощью самоорганизующихся карт. Москва, издательский дом. Альпина., 2001.
2. Уоссерман. Нейрокомпьютерная техника., Москва, издательство Мир., 1992.
3. Шумский C. A. Нейрокомпьютинг и его применение в экономике и бизнесе., Москва, издательство МИФИ, 1998.

ПоказатьСвернуть
Заполнить форму текущей работой