<<
>>

ЛАБОРАТОРНАЯ РАБОТА. ПОИСК МАКСИМАЛЬНОГО ЗНАЧЕНИЯ НЕЛИНЕЙНОЙ ФУНКЦИИ ГЕНЕТИЧЕСКИМ АЛГОРИТМОМ

КРАТКАЯ СПРАВКА

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

ГА показал высокую эффективность в задачах минимизации (максимизации) многомерных функций типа

/(*) —» min (max), (4.4.1)

в которой вектор х = (х х2, ..., хт) имеет достаточно большую размерность.

Приведем некоторые понятия и определения из теории ГА. Все ГА работают на основе начальной информации, в качестве которой выступает популяция р = {р(0), р(1), ..., р(п)} — множество элементов p(i), i = 1, п, именуемых особями или хромосомами. В задаче минимизации (4.4.1) особь р(1) — это вектор х1 =(х[,х12,...,х1т), i = 1, ..., п, т. е. p(i) = х1.

Особи состоят из генов х. Обычно размер популяции п не превышает 5. Каждый ген характеризуется величиной и позицией в особи. Ген может быть подвергнут случайному изменению — мутированию в соответствии с формулой

дг = Ran(xmin, xmax) = *min + a(*max - jcmin), (4.4.2)

где ;cmin, xmax — верхний и нижний пределы числа х; а — случайное число, изменяющееся в пределах [0, 1].

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

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

Исходная популяция формируется из нулевой особи, содержащей т начальных значений переменных, именуемых генами:

р(0) = (х°ух

С помощью операции (4.4.1) определяется количество генов к = Кап(1, т), подлежащих мутации, т.

е. к раз вычисляется номер И = Кап(1, т) мутируемого гена:

хк = Кап(4™'г,л:£1ах).

Таким образом формируется первая особь исходной популяции. Например, для к = 3, к = 2, 10, 15:

_ / -у 1 у1 /у»1 \ / уО у у у у 0 \

V*'! , л,2 у • • • у •А'т ) — 9 •*'2 9 • • • 9 -МО ^ ? -^15 ? • • • 9**'т

Аналогичным путем определяется количество к номеров генов /г и проводится их мутация для получения второй р(2) и третьей />(3) особей исходной популяции

Р(]) (х^, Х'2,. •.,), /' 1, 2, 3.

Оператор отбора вычисляет соответствующие критерии /(/>(/)), у = 1, 2, 3, и выбирает два критерия (например, /(р(1)) и /(р(3)) с минимальными значениями и соответственно две особи р(1) и р(3), именуемые родителями.

Оператор скрещивания передает потомкам свойства родителей.

Вначале определяется целое число т = Кап(1, ц) — точка разбиения строки на две подстроки, а затем строки обмениваются элементами подстрок, находящимися после разбиения, т. е. начиная с (р 4- 1)-го и до р-го элемента. Таким образом образуются две новые особи (строки) или два потомка, наследующие свойства родителей:

л-1

1 ? и'т 1

■ > -*•«1 •

, • • •, Х^ , +1,.

у 3 у.З у 3

9 * * * 9 9 ■Л'|Д + 1 9

I у 1 у 1 у 3 уЗ

«4 ^ 9 • • • у 9 -*^ + 1 9 • • • 9 -*7Н 9

Потомки: ‘ з „з „1 „1

| 9 * * * 9 *Л'|Д 9 *^14 + 1 9 • • • 9 •¿'ГР *

Запишем выражения потомков в унифицированной форме особей:

Р{ 4) — (Л-1 » %2 »* * *» ) »•••» •^(.1 > >

^?(5) = (хх , х2»• • •»х^ ) = (х^ , .

• Хц , х^1+|,

Оператор мутации при выполнении условия

Кап(0, 100) < 3

определяет номер X = Кап(1, т) генов Ху и х?, которые переставляются в особях р(4) и />(5) с образованием новых мутированных потомков

р{ 4) — (х^»• • •»х^ »•••» ^/п)»

/?(5) — (х^ , • • • , Ху ,».», х~т).

Так происходит расширение исходной популяции

р = (р{1), р(2), ...,/>(5».

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

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

ЗАДАНИЕ 1

ТТ « V V « 1

Наити максимум нелинейной квадратической функции

f = 6хг+32х2-х*-4х% (4.4.3)

с помощью генетического алгоритма, начиная итерационный поисковый процесс в точке с координатами х® = 7,

х?1-4.

Технология работы

Откройте первое окно программы «Генетический алгоритм» (рис. 4.4.1), в поле Исследуемая функция введите нелинейную функцию (4.4.3) в форме

б*Х1+32*Х2—Х1Л2—4*Х2Л2

и, нажимая кнопку Вперед, перейдите во второе окно генетического алгоритма (рис. 4.4.2).

Рис. 4.4.1

Рис. 4.4.2

Рис. 4.4.3

В этом окне установите следующие параметры: поиск максимума и начальные значения переменных Х1=7, Х2=4. Остальные параметры задаются по умолчанию.

Нажмите кнопку Вперед и перейдите в третье окно генетического алгоритма (рис. 4.4.3).

Нажмите кнопку Старт и запустите генетический алгоритм для определения максимума нелинейной функции (4.4.3). Текущий процесс поиска отображается в нижней части окна «Процесс поиска оптимума». Результаты х1 = 2,9993, #2=4 приводятся в верхней части окна, а значение нелинейной функции / = 73 — в средней части окна. Точное решение: х[ = 3, х*2 - 4, /=73.

Решение получено за 200 полных расчетов, называемых эпохами.

Повторите расчет с другими начальными значениями переменных = 3, = 10. Определите минимум и корни

уравнения (4.4.3), т. е. х^х^ при которых / = 0 с двумя парами заданных начальных значений переменных.

<< | >>
Источник: Ю. И. КУДИНОВ, Ф.Ф. ПАЩЕНКО, А. Ю. КЕЛИНА. ПРАКТИКУМ ПО ОСНОВАМ СОВРЕМЕННОЙ ИНФОРМАТИКИ. 2011

Еще по теме ЛАБОРАТОРНАЯ РАБОТА. ПОИСК МАКСИМАЛЬНОГО ЗНАЧЕНИЯ НЕЛИНЕЙНОЙ ФУНКЦИИ ГЕНЕТИЧЕСКИМ АЛГОРИТМОМ:

  1. Какое метафизическое значение имеет наследственная или генетическая болезнь?
  2. 2. Специфика и алгоритмы работы с источниками.
  3. Поиск значения вашей болезни
  4. Функции и значение желчного пузыря
  5. Направление поиска работы
  6. Направление поиска работы
  7. Направление поиска работы
  8. Направление поиска работы
  9. Направление поиска работы
  10. Направление поиска работы