Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы



Download 9,87 Mb.
Pdf ko'rish
bet58/228
Sana20.06.2022
Hajmi9,87 Mb.
#683557
TuriКнига
1   ...   54   55   56   57   58   59   60   61   ...   228
Bog'liq
Algorithms3

Пример 2.3
Рассмотрим задачу, аналогичную задаче из примера 2.2, т.е. 
будем искать максимум функции, заданной формулой (2.1), но для
переменной 
х
, принимающей действительные значения из интервала [
а, 
b
], где 
а
= 0, 
b
= 3,1. Допустим, что нас интересует решение с точностью 
до одного знака после запятой. 


А.Е. Кононюк Дискретно-непрерывная математика 
103 
Поиск решения сводится к просмотру пространства, состоящего из 32 
точек 0,0 0,1 ... 2,9 3,0 3,1. Эти точки (фенотипы) можно представить в 
виде хромосом (генотипов), если использовать бинарные пятизвенные 
цепочки, поскольку с помощью 5 битов можно получить 2
5
=32 
различных кодовых комбинации. Следовательно, можно использовать 
такое же множество кодовых последовательностей, как и в примере 2.2, 
причем хромосома [00000] будет соответствовать числу 0,0, хромосома 
[00001] - числу 0,1 и т.д., вплоть до хромосомы [11111], 
соответствующей числу 3,1. 
Таким образом, мы можем воспроизвести последовательность этапов 
генетического алгоритма (так же, как в примере 2.2), не забывая, что 
конкретным хромосомам (генотипам) в данном примере соответствуют 
другие фенотипы. Те кодовые последовательности, которые в примере 
2.2 представляли фенотипы 0, 1, ..., 29, 30, 31, в рассматриваемой 
ситуации обозначают значения 
х
, равные 0,0 0,1 ... 2,9 3,0 3,1. В связи с 
тем, что генетический алгоритм основан на случайном выборе исходной 
популяции и хромосом для последующего преобразования методом 
колеса рулетки, а также родительских пар для скрещивания и точки 
скрещивания, то генетический алгоритм в текущем примере будет 
выполняться аналогично, но не идентично предыдущему примеру. 
В результате выполнения этого алгоритма будет выбрано наилучшее 
решение, которое представляется хромосомой [11111] со значением 
фенотипа 3,1. Функция приспособленности этой хромосомы равна 
20,22; это максимально возможное значение. 
Заметим, что если бы в примере 2.3 нас интересовало решение с 
точностью, превышающей один знак после запятой, то интервал [0, 3,1] 
необходимо было бы разбить на большее количество подинтервалов, и 
для кодирования соответственно большего количества чисел 
потребовались более длинные хромосомы (с длиной, превышающей 5 
битов). Аналогично, расширение области определения переменной 
х
также потребует применения более длинных хромосом. Из этих 
наблюдений можно сделать вывод, что длина хромосом зависит от 
ширины области определения 
х
и от требуемой точности решения. 
Представим теперь задачу из примера 2.3 в более общем виде. 
Допустим, что ищется максимум функции 
f
(
х
1
, х
2
.....х
п
 
) > 0 для 
х
i

[
а
i
, b
i
]

R; i 
= 1, 2, ..., 

и требуется найти решение с точностью до 

знаков после запятой для каждой переменной х
i
. В такой ситуации 
необходимо разбить интервал [
а
i
, b
i
] на
(
b
i
-
а
i
)•10
q
одинаковых подинтервалов. Это означает применение 
дискретизации с шагом 
r= 
10
-q
. Наименьшее натуральное число 
m
i, 


А.Е. Кононюк Дискретно-непрерывная математика 
104 
удовлетворяющее неравенству 
(
b
i
-
а
i
)•10
q
≤2
i
m
-1 , (2.4)
определяет необходимую и достаточную длину двоичной последова-
тельности, требуемой для кодирования числа из интервала [
а
i
, b
i
] с 
шагом 
r. 
Каждой такой двоичной последовательности соответствует 
десятичное значение числа, представляемого данным кодом (с учетом 
правил перевода десятичных чисел в двоичную форму). Пусть 
у
i
-
обозначает десятичное значение двоичной последовательности, 
кодирующей число 
х
i
. Значение 
х
i
можно представить выражением 
1
2




i
m
i
i
i
i
i
a
b
y
a
x
. (2.5)
Таким способом задаются фенотипы, соответствующие кодовым 
последовательностям с длиной 
т
i

Пример 2.3 - это частный случай 
задачи в данной постановке при условии, что 
i
= 1 и 
q= 
1. Выражение 
(2.5) - это следствие из простого линейного отображения интервала [
а
i

b
i
] на интервал [0, 2
i
m
-1], где 2
i
m
- десятичное число, закодированное 
двоичной 
последовательностью 
длиной 
т
i

и 
составленной 
исключительно из единиц, а 0 - это, очевидно, десятичное значение 
двоичной последовательности длиной 
т
i

составленной только из нулей. 
Обратим внимание, что если 
а
i
= - 25, 
b
i
= 25 и применяется шаг 
r=
0,05, то согласно формуле (2.4) получаем 
т
i
=10, а с помощью 
формулы 2.5) можно проверить значения фенотипов для генотипов, 
представленных в табл. 2.1. 

Download 9,87 Mb.

Do'stlaringiz bilan baham:
1   ...   54   55   56   57   58   59   60   61   ...   228




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish