Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений
Разработан генетический алгоритм решения задачи выбора оптимального порядка соединения отношений. Описаны процедуры кодирования и декодирования решений, операторы мутации, приведена структурная схема генетического алгоритма. Розроблено генетичний алгоритм розв’язку задачі вибору оптимального порядку...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/61831 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений / Ю.О. Чернышев, Н.Н. Венцов // Электронное моделирование. — 2012 — Т. 34, № 3. — С. 115-122. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859587233869201408 |
|---|---|
| author | Чернышев, Ю.О. Венцов, Н.Н. |
| author_facet | Чернышев, Ю.О. Венцов, Н.Н. |
| citation_txt | Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений / Ю.О. Чернышев, Н.Н. Венцов // Электронное моделирование. — 2012 — Т. 34, № 3. — С. 115-122. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Разработан генетический алгоритм решения задачи выбора оптимального порядка соединения отношений. Описаны процедуры кодирования и декодирования решений, операторы мутации, приведена структурная схема генетического алгоритма.
Розроблено генетичний алгоритм розв’язку задачі вибору оптимального порядку з’єднання відносин. Описано процедури кодування та декодування рішень, операторів мутації та наведено структурну схему генетичного алгоритму.
Genetic algorithm for solving the problem of optimal choice of the order of relations combination has been designed. The procedures of coding and decoding of solutions, mutation operators have been described, the structural algorithm scheme is presented.
|
| first_indexed | 2025-11-27T11:11:58Z |
| format | Article |
| fulltext |
ÓÄÊ 004.023
Þ. Î. ×åðíûøåâ, ä-ð òåõí. íàóê, Í. Í. Âåíöîâ, êàíä. òåõí. íàóê
Ãîñóäàðñòâåííîå îáðàçîâàòåëüíîå ó÷ðåæäåíèå
âûñøåãî ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ
Äîíñêîé ãîñóäàðñòâåííûé òåõíè÷åñêèé óíèâåðñèòåò
(Ðîññèÿ, 344000, Ðîñòîâ-íà-Äîíó, ïë. Ãàãàðèíà, 1,
òåë. 79185991645, e-mail: chernyshevyo@list.ru, myvnn@list.ru)
Ãåíåòè÷åñêèé àëãîðèòì ðåøåíèÿ
çàäà÷è âûáîðà îïòèìàëüíîãî ïîðÿäêà
ñîåäèíåíèÿ ðàñïðåäåëåííûõ îòíîøåíèé
Ðàçðàáîòàí ãåíåòè÷åñêèé àëãîðèòì ðåøåíèÿ çàäà÷è âûáîðà îïòèìàëüíîãî ïîðÿäêà ñîåäè-
íåíèÿ îòíîøåíèé. Îïèñàíû ïðîöåäóðû êîäèðîâàíèÿ è äåêîäèðîâàíèÿ ðåøåíèé, îïåðàòî-
ðû ìóòàöèè, ïðèâåäåíà ñòðóêòóðíàÿ ñõåìà ãåíåòè÷åñêîãî àëãîðèòìà.
Ðîçðîáëåíî ãåíåòè÷íèé àëãîðèòì ðîçâ’ÿçêó çàäà÷³ âèáîðó îïòèìàëüíîãî ïîðÿäêó ç’ºäíàí-
íÿ â³äíîñèí. Îïèñàíî ïðîöåäóðè êîäóâàííÿ òà äåêîäóâàííÿ ð³øåíü, îïåðàòîð³â ìóòàö³¿ òà
íàâåäåíî ñòðóêòóðíó ñõåìó ãåíåòè÷íîãî àëãîðèòìó.
Ê ë þ ÷ å â û å ñ ë î â à: ãåíåòè÷åñêèé àëãîðèòì, îïòèìèçàöèÿ, ñîåäèíåíèå îòíîøåíèé.
Îïèñàíèå ïðîáëåìû. Èìååòñÿ ìíîæåñòâî îòíîøåíèé R r r rn� �{ , ,..., },0 1 1
ðàñïîëîæåííûõ íà ðàçëè÷íûõ óçëàõ ñåòè è ïîäëåæàùèõ ñîåäèíåíèþ.
Êàæäîå îòíîøåíèå èç R íàõîäèòñÿ íà óíèêàëüíîì óçëå ñåòè, ò.å. íå ñó-
ùåñòâóåò äâóõ îòíîøåíèé, ðàñïîëîæåííûõ íà îäíîì è òîì æå ñåðâåðå
êîìïüþòåðíîé ñåòè. Â ñâÿçè ñ ýòèì ñîåäèíåíèþ äâóõ îòíîøåíèé ïðåä-
øåñòâóåò ïåðåñûëêà îäíîãî èç íèõ íà óçåë, ãäå õðàíèòñÿ âòîðîå ñîåäè-
íÿåìîå îòíîøåíèå.  ðàññìàòðèâàåìîì ñëó÷àå âðåìÿ ïåðåäà÷è äàííûõ ïî
ñåòè ñóùåñòâåííî áîëüøå âðåìåíè èõ îáðàáîòêè â îïåðàòèâíîé ïàìÿòè.
Ïîýòîìó çàòðàòû íà îïåðàöèþ ñîåäèíåíèÿ îòíîøåíèé öåëåñîîáðàçíî îöå-
íèâàòü, èñõîäÿ èç îáúåìîâ ïåðåäàâàåìûõ ïî ñåòè äàííûõ.
Äëÿ ìèíèìèçàöèè ñåòåâîãî òðàôèêà ïðè ñîåäèíåíèè äâóõ îòíîøåíèé,
ri è r j , ïåðåñûëêå ïîäëåæèò íàèìåíüøåå èç íèõ. Çàòðàòû íà ñîåäèíåíèå
îòíîøåíèé ri è r j îïðåäåëèì â âèäå
min ( ( ), ( ))T r T ri i , (1)
ãäåT ri( ) — ÷èñëî êîðòåæåé â îòíîøåíèè ri (ìîùíîñòü îòíîøåíèÿ ri ); min —
ôóíêöèÿ, âîçâðàùàþùàÿ çíà÷åíèå íàèìåíüøåãî èç ñâîèõ àðãóìåíòîâ.
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 3 115
 ñëó÷àå ñîåäèíåíèÿ íåñêîëüêèõ îòíîøåíèé ïîðÿäîê ñîåäèíåíèÿ
ìîæíî ïðåäñòàâèòü â âèäå äåðåâà. Èçîáðàæåííîå íà ðèñ. 1 äåðåâî îïè-
ñûâàåò ïðîöåññ ñîåäèíåíèÿ ÷åòûðåõ îòíîøåíèé: r r0 3,..., . Íà ïåðâîì ýòàïå
ñîåäèíÿþòñÿ äâå ïàðû îòíîøåíèé: r0 ñ r1 è r2 ñ r3. Ïîñêîëüêó ïåðåñûëêå
ïîäëåæèò íàèìåíüøåå îòíîøåíèå â êàæäîé ñîåäèíÿåìîé ïàðå, çàòðàòû íà
ñîåäèíåíèå r0 ñ r1 è r2 ñ r3 îïðåäåëÿþòñÿ ñîîòâåòñòâåííî êàê min( ( ), ( ))T r T r0 1
è min ( ( ), ( ))T r T r2 3 . Îòíîøåíèå, ïîëó÷åííîå â ðåçóëüòàòå ñîåäèíåíèÿ r0 ñ
r1, îáîçíà÷èì r0 � r1, à îòíîøåíèå, ïîëó÷åííîå â ðåçóëüòàòå ñîåäèíåíèÿ r2 ñ
r3, îáîçíà÷èì r2 � r3.
Ñëåäóþùèé øàã — ñîåäèíåíèå îòíîøåíèé r0 � r1 è r2 � r3. Çàòðàòû íà
îïåðàöèþ ñîåäèíåíèÿ îòíîøåíèé îïðåäåëÿåì ïî ôîðìóëå min ( ( ),T r r0 1�
T r r( ))2 3� . Ñëåäîâàòåëüíî, ñóììàðíûå çàòðàòû íà ñîåäèíåíèå îòíîøåíèé â
ñîîòâåòñòâèè ñ ïîðÿäêîì, èçîáðàæåííûì íà ðèñ. 1, îïðåäåëÿþòñÿ òàê:
min ( ( ), ( )) min ( ( ), ( )) min ( ( ), (T r T r T r T r T r r T r0 1 2 3 0 1� � � 2 3� r )).
Ñëåäóåò çàìåòèòü, ÷òî â îáùåì ñëó÷àå â çàâèñèìîñòè îò èñõîäíûõ äàí-
íûõ ìîãóò áûòü ðàçëè÷íûå ñîîòíîøåíèÿ ìîùíîñòåé èñõîäíûõ, ïðîìåæó-
òî÷íûõ è ðåçóëüòèðóþùèõ îòíîøåíèé, íàïðèìåð min ( ( ), ( ))T r T r0 1 �
� �min ( ( )T r r0 1 èëè T r T r r T r( ) ( ) ( )1 0 1 0� � � è ò.ä.
Ïðè ïîäîáíîì ïîäõîäå ê ñîåäèíåíèþ è ïåðåñûëêå îòíîøåíèé ðå-
çóëüòèðóþùåå îòíîøåíèå, ÿâëÿþùååñÿ ðåçóëüòàòîì ñîåäèíåíèÿ âñåõ îò-
íîøåíèé èç R, ìîæåò îêàçàòüñÿ íà ëþáîì óçëå ñåòè. Îòñóòñòâèå ïðèâÿçêè
ðåçóëüòèðóþùåãî îòíîøåíèÿ ê êîíêðåòíîìó óçëó ñåòè âïîëíå ïðèåìëåìî,
êîãäà íàä ðåçóëüòèðóþùèì îòíîøåíèåì íåîáõîäèìî ïðîâåñòè âû÷èñëè-
òåëüíûå îïåðàöèè, ìîùíîñòü ðåçóëüòàòà êîòîðûõ àïðèîðè ñóùåñòâåííî
ìåíüøå ìîùíîñòè ðåçóëüòèðóþùåãî îòíîøåíèÿ.
Þ. Î. ×åðíûøåâ, Í. Í. Âåíöîâ
116 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 3
r0 � r1
( )r0 � r1 � ( )r r2 3�
r2 3� r
r0 r1 r2 r3
Ðèñ. 1
r0 r1
wk
wl
wm
r2 r3 r4
wi
Ðèñ. 2
Ôîðìóëèðîâêà çàäà÷è. Îáîçíà÷èì w ïîäìíîæåñòâî âíóòðåííèõ âåð-
øèí äåðåâà ñîåäèíåíèÿ îòíîøåíèé (ðèñ. 2). Êàæäîé âíóòðåííåé âåðøèíå
ñîîòâåòñòâóåò îòíîøåíèå, ïîëó÷åííîå â ðåçóëüòàòå îáúåäèíåíèÿ îòíîøå-
íèé, ñîîòâåòñòâóþùèõ äâóì äî÷åðíèì âåðøèíàì, íàïðèìåð äëÿ wm äî÷åð-
íèìè ÿâëÿþòñÿ wi è r4. Âåðøèíå wi áóäåò ñîîòâåòñòâîâàòü îòíîøåíèå,
ïîëó÷åííîå â ðåçóëüòàòå ñîåäèíåíèÿ îòíîøåíèé r0 � r1 è r2 � r3, ñîîòâåòñò-
âóþùèõ âåðøèíàì wk è wl . Ïðè íàëè÷èè îäíîãî àòðèáóòà ñîåäèíåíèÿ
ìîùíîñòü îòíîøåíèÿ, ñîîòâåòñòâóþùåãî âåðøèíå wi , îïðåäåëÿåòñÿ èç
âûðàæåíèÿ [1]
T w T w w
T w T w
V w x V w y
i k l
k l
k l
( ) ( )
( ) ( )
max ( ( ), ( ))
� � � , (2)
ãäåT wi( )— ÷èñëî êîðòåæåé â îòíîøåíèè, ñîîòâåòñòâóþùåì âåðøèíå wi ;
T w wk l( )� — ÷èñëî êîðòåæåé â îòíîøåíèè, ÿâëÿþùåìñÿ ðåçóëüòàòîì íà-
òóðàëüíîãî ñîåäèíåíèÿ îòíîøåíèé, ñîîòâåòñòâóþùèõ âåðøèíàì wk è wl ;
V w xk( , )— ÷èñëî ðàçëè÷íûõ çíà÷åíèé àòðèáóòà x3 r3 îòíîøåíèÿ, ñîîòâåòñò-
âóþùåãî âåðøèíå wk ; x, y — àòðèáóòû îòíîøåíèé, ïî êîòîðûì âûïîë-
íÿåòñÿ ñîåäèíåíèå. Åñëè èìååòñÿ äâà îáùèõ àòðèáóòà ñîåäèíåíèÿ, òî
T v w
T w T w
V w x V w y V w x
k l
k l
k l k
( )
( ) ( )
max ( ( , ), ( , )) max ( (
� �
1 1 2 2), ( ))V w yl
, (3)
ãäå T wk( )— ÷èñëî êîðòåæåé â îòíîøåíèè, ñîîòâåòñòâóþùåì âåðøèíå wk ;
T w wk l( )� — ÷èñëî êîðòåæåé â îòíîøåíèè, ÿâëÿþùåìñÿ ðåçóëüòàòîì
íàòóðàëüíîãî ñîåäèíåíèÿ îòíîøåíèé, ñîîòâåòñòâóþùèõ âåðøèíàì wk è
wl ; V w xk( ) — ÷èñëî ðàçëè÷íûõ çíà÷åíèé àòðèáóòà x îòíîøåíèÿ, ñîîò-
âåòñòâóþùåãî âåðøèíå wk ; x1, x2, y1, y2 — àòðèáóòû îòíîøåíèé, ïî êî-
òîðûì âûïîëíÿåòñÿ ñîåäèíåíèå. Åñëè ñîåäèíÿåìûå îòíîøåíèÿ íå èìåþò
îáùåãî àòðèáóòà, ìîùíîñòü ðåçóëüòèðóþùåãî îòíîøåíèÿ îïðåäåëÿåòñÿ
êàê äåêàðòîâî ïðîèçâåäåíèå:
T v w T w T wk l k l( ) ( ) ( )� � . (4)
Çàòðàòû, ñâÿçàííûå ñ ñîåäèíåíèåì îòíîøåíèé, ñîîòâåòñòâóþùèõ äî-
÷åðíèì âåðøèíàì wi , îáîçíà÷èì
S w T w T wi k l( ) min ( ( ), ( ))� . (5)
Ïîñêîëüêó äëÿ ïîëó÷åíèÿ èòîãîâîãî îòíîøåíèÿ íåîáõîäèìî îñóùåñòâèòü
ñîåäèíåíèå âñåõ âåðøèí, îïðåäåëèì âåëè÷èíó S wi( ) äëÿ êàæäîé âíóò-
Ãåíåòè÷åñêèé àëãîðèòì ðåøåíèÿ çàäà÷è âûáîðà îïòèìàëüíîãî ïîðÿäêà ñîåäèíåíèÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 3 117
ðåííåé âåðøèíû äåðåâà ñîåäèíåíèÿ. Òîãäà êðèòåðèé îïòèìàëüíîñòè çàïè-
øåì â âèäå
S wi
w Wi
( ) min
�
. (6)
Ðàçðàáîòêà ãåíåòè÷åñêîãî àëãîðèòìà. Îïòèìàëüíîå ðåøåíèå çàäà÷è
âûáîðà ïîðÿäêà ñîåäèíåíèÿ îòíîøåíèé, ðàñïîëîæåííûõ íà íåñêîëüêèõ
óçëàõ, ìîæåò ñîîòâåòñòâîâàòü ïðîèçâîëüíîìó äåðåâó ñîåäèíåíèÿ [1]. Â
ñâÿçè ñ ýòèì îáëàñòü ïîèñêà ðåøåíèÿ çàäà÷è îïòèìèçàöèè îáðàçóåò äâà
ìíîæåñòâà: òîïîëîãè÷åñêèõ ôîðì äåðåâüåâ ñîåäèíåíèÿ è ïîðÿäêîâ ðàç-
ìåùåíèÿ ëèñòüåâ äåðåâà ñîåäèíåíèÿ (r0 — r4). ×èñëî òîïîëîãè÷åñêèõ ôîðì
äåðåâüåâ ñîåäèíåíèÿ ïîä÷èíÿåòñÿ ðåêóððåíòíîìó ïðàâèëó [1]:
FD ( )1 1� ,
FD n FD i FD n i
i
n
( ) ( ) ( )� �
�
�
1
1
,
(7)
ãäå n — ÷èñëî ñîåäèíÿåìûõ îòíîøåíèé. ×èñëî ðàçëè÷íûõ ïîðÿäêîâ ðàç-
ìåùåíèÿ ëèñòüåâ äëÿ çàäàííîé ôîðìû äåðåâà ñîåäèíåíèÿ îòíîøåíèé
îïðåäåëÿåòñÿ êàê ÷èñëî ïåðåñòàíîâîê è ðàâíî n!
Òàêèì îáðàçîì, ÷èñëî âîçìîæíûõ ïîðÿäêîâ ñîåäèíåíèÿ (NPS) n-îòíî-
øåíèé â ñèòóàöèÿõ, êîãäà íå íàêëàäûâàþòñÿ îãðàíè÷åíèÿ íà ñòðóêòóðó äå-
ðåâà ñîåäèíåíèÿ îòíîøåíèé, îïðåäåëÿåòñÿ ñîîòíîøåíèåì [1]
NPS n( ) � FD n n( ) !
 íàñòîÿùåå âðåìÿ äëÿ ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷, èìåþùèõ
áîëüøóþ îáëàñòü ïîèñêà, ýôôåêòèâíî èñïîëüçóþòñÿ ãåíåòè÷åñêèå àëãî-
ðèòìû, âàæíîé îñîáåííîñòüþ êîòîðûõ ÿâëÿåòñÿ îïåðèðîâàíèå íå ñ ðåøå-
íèÿìè çàäà÷è, à ñ êîäàìè ýòèõ ðåøåíèé. Ïîýòîìó íåîáõîäèìî ðàçðàáîòàòü
ïðîöåäóðû êîäèðîâàíèÿ è äåêîäèðîâàíèÿ ðåøåíèé. Êàæäîå ðåøåíèå ïðåä-
ëàãàåòñÿ êîäèðîâàòü îñîáüþ �R, ñîñòîÿùåé èç äâóõ õðîìîñîì: �R � ( , )H H1 2 .
Õðîìîñîìà H1 ñîäåðæèò èíôîðìàöèþ î ïîðÿäêå ñëåäîâàíèÿ ëèñòüåâ äåðå-
âà ñîåäèíåíèÿ, H2 — î ñòðóêòóðå äåðåâà (åãî òîïîëîãè÷åñêîé ôîðìå).
Õðîìîñîìà H1 ïðåäñòàâëÿåò ñîáîé êîðòåæ, ñîäåðæàùèé èäåíòèôè-
êàòîðû ñîåäèíÿåìûõ îòíîøåíèé. Ðàññìîòðèì ñòðóêòóðó õðîìîñîìû H2.
Ââåäåì àëôàâèò � �
{ , }X . Ïî àíàëîãèè ñ [2—5] ñòðóêòóðó äåðåâà ñîå-
äèíåíèÿ çàäàäèì íà áàçå àëôàâèòà � �
{ , }X , èñïîëüçóÿ ïîëüñêóþ çàïèñü,
ãäå X — ñîîòâåòñòâóåò ñîåäèíÿåìûì îòíîøåíèÿì (ëèñòüÿì äåðåâà ñîåäè-
íåíèÿ, âåðøèíàì ïîäíîæüÿ), à
— îïåðàöèè ñîåäèíåíèÿ (ñì. ðèñ. 2).
Þ. Î. ×åðíûøåâ, Í. Í. Âåíöîâ
118 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 3
 ðàññìàòðèâàåìîì ñëó÷àå ñèìâîë
ñîîòâåòñòâóåò ñèìâîëó �. Äëÿ
âîññòàíîâëåíèÿ äåðåâà ñîåäèíåíèÿ ñîãëàñíî ïîëüñêîé çàïèñè íåîáõîäèìî
ïðîñìàòðèâàòü âûðàæåíèå ñëåâà íàïðàâî, ñèìâîë
ñîîòâåòñòâóåò ñîåäè-
íåíèþ è îáúåäèíÿåò äâà áëèæàéøèõ ïîäãðàôà, ðàñïîëîæåííûõ ñëåâà îò
ñèìâîëà
â ïîëüñêîé çàïèñè è îáðàçîâàííûõ íà ïðåäûäóùèõ øàãàõ.
Êàæäàÿ âíóòðåííÿÿ âåðøèíà, ñîîòâåòñòâóþùàÿ îïåðàòîðó
, õàðàêòåðè-
çóåò îòíîøåíèå, ïîëó÷åííîå â ðåçóëüòàòå îáúåäèíåíèÿ äâóõ ïîäãðàôîâ.
Ïîëüñêîå âûðàæåíèå äëÿ äåðåâà ñîåäèíåíèÿ ïÿòè îòíîøåíèé, èçîáðà-
æåííîãî íà ðèñ. 3, èìååò âèä XX XX X
, äëÿ äåðåâà, èçîáðàæåííîãî íà
ðèñ. 2, — r r r r r0 1 2 3 4
, äëÿ äåðåâà, èçîáðàæåííîãî íà ðèñ. 1, —
r r r r0 1 2 3
. Îáîçíà÷èì n X ÷èñëî ýëåìåíòîâ â ïîëüñêîì âûðàæåíèè òèïà
X, ãäå n
— ÷èñëî ñèìâîëîâ
. Òîãäà ñïðàâåäëèâî ðàâåíñòâî n nx � �
1
[2—5]. Ïåðâûé ñèìâîë
ìîæåò ïîÿâèòüñÿ â ïîëüñêîì âûðàæåíèè òîëüêî
ïîñëå äâóõ ñèìâîëîâ X. Åñëè â ïîëüñêîì âûðàæåíèè ïðîâåñòè ñïðàâà îò
çíàêà
ñå÷åíèå, òî ñëåâà îò ñå÷åíèÿ ÷èñëî çíàêîâ X áîëüøå ÷èñëà çíàêîâ
,
ïî êðàéíåé ìåðå, íà åäèíèöó [2—5].
Åñëè ïðîíóìåðîâàòü ïîçèöèè ìåæäó çíàêàìè X â äåðåâå ñîåäèíåíèÿ
îòíîøåíèé X X X X X nx
� � � �
�1 2 3 1... , òî ìàêñèìàëüíîå ÷èñëî çíàêîâ â íåì
ìîæåò îêàçàòüñÿ ðàâíûì íîìåðó ïîçèöèè [2]. Åñëè ïîëüñêîå âûðàæåíèå
ñîîòâåòñòâóåò óêàçàííûì âûøå óñëîâèÿì, òî íà åãî îñíîâå ìîæíî ïîñò-
ðîèòü äåðåâî ñîåäèíåíèÿ îòíîøåíèé. ×èñëî ðàçëè÷íûõ ôîðì äåðåâüåâ
ñîåäèíåíèÿ îïðåäåëÿåòñÿ ïî ôîðìóëå (7).
Òàêèì îáðàçîì, êàæäîå ðåøåíèå êîäèðóåòñÿ ñòðóêòóðîé �R H H� ( , )1 2 ,
ñîñòîÿùåé èç äâóõ õðîìîñîì. Õðîìîñîìà H1 ñîäåðæèò èíôîðìàöèþ î
ðàçìåòêå ìíîæåñòâà âåðøèí, õðîìîñîìà H2 — î ñòðóêòóðå äåðåâà. Ïî-
ñêîëüêó îïòèìàëüíîå ðåøåíèå ìîæåò ñîîòâåòñòâîâàòü äåðåâó ñîåäèíåíèÿ
ïðîèçâîëüíîé ôîðìû, ïðè îðãàíèçàöèè ïðîöåññà ãåíåòè÷åñêîãî ïîèñêà
Ãåíåòè÷åñêèé àëãîðèòì ðåøåíèÿ çàäà÷è âûáîðà îïòèìàëüíîãî ïîðÿäêà ñîåäèíåíèÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 3 119
X X X X X
Ðèñ. 3
r0 r1 r2 r3
Ðèñ. 4
r0 r1 r2r3
Ðèñ. 5
íåîáõîäèìî ïðèìåíÿòü îïåðàòîðû, ìîäèôèöèðóþùèå íå òîëüêî ðàñïî-
ëîæåíèÿ ëèñòüåâ äåðåâà ñîåäèíåíèÿ îòíîøåíèé, íî è åãî ñòðóêòóðó.
 êà÷åñòâå ïðèìåðà îïåðàòîðà ìîäèôèêàöèè ðàññìîòðèì îäíîòî÷å÷-
íûé îïåðàòîð ìóòàöèè, ïðèìåíÿåìûé ê õðîìîñîìàì îñîáè �R H H� ( , )1 2 :
H1= (r0, r1, r2, r3), H XX X X2 �
( ) .
Ïîðÿäîê ñîåäèíåíèÿ îòíîøåíèé, êîäèðóåìûé îñîáüþ�R, ïðåäñòàâëåí
íà ðèñ. 4. Çàòðàòû íà ñîåäèíåíèå îòíîøåíèé â ñîîòâåòñòâèè ñ ïîðÿäêîì,
çàäàííûì îñîáüþ �R, îïðåäåëÿþòñÿ òàê:
min ( ( ), ( )) min ( ( ), ( )) min ( (T r T r T r r T r T r r r0 1 0 1 2 0 1� � � � � 2 3), ( ))T r .
Ïðèìåíåíèå îïåðàòîðà ìóòàöèè ê õðîìîñîìå H1 îñîáè �R èçìåíèò ïî-
ðÿäîê ñëåäîâàíèÿ ëèñòüåâ äåðåâà. Íàïðèìåð, âçàèìíûå ïåðåñòàíîâêè ýëå-
ìåíòîâ r2 è r3 ïðèâîäÿò ê ñîçäàíèþ íîâîé îñîáè:
� � � � �R H H( , )1 2 , H �1 = (r0, r1, r3, r2), H �2 = H2.
Þ. Î. ×åðíûøåâ, Í. Í. Âåíöîâ
120 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 3
Íà÷àëî
Ôîðìèðîâàíèå
ñòàðòîâîé ïîïóëÿöèè
Âûáîð èçìåíÿåìûõ
õðîìîñîì
Ïðîâåðêà êîððåêòíîñòè
Êðèòåðèé îñòàíîâêè
âûïîëíåí?
Íåò
Êîíåö
Äà
OM1 OM2
OS1 OK2
OS2
Ðèñ. 6
Ïîðÿäîê ñîåäèíåíèÿ îòíîøåíèé, îïèñûâàåìûé îñîáüþ �R, ïðåäñòàâ-
ëåí íà ðèñ. 5. Çàòðàòû íà ñîåäèíåíèå îòíîøåíèé â ñîîòâåòñòâèè ñ ïîðÿä-
êîì, çàäàííûì îñîáüþ �R, îïðåäåëÿþòñÿ ïî ôîðìóëàì (1)—(6):
min ( ( ), ( )) min ( ( ), ( )) min ( (T r T r T r r T r T r r r0 1 0 1 3 0 1� � � � � 3 2), ( ))T r .
Ìóòàöèÿ õðîìîñîìû H2 ïðèâåäåò ê èçìåíåíèþ òîïîëîãè÷åñêîé ôîð-
ìû äåðåâà ñîåäèíåíèÿ îòíîøåíèé. Íàïðèìåð, âçàèìíàÿ ïåðåñòàíîâêà äâóõ
ýëåìåíòîâ, íåïîñðåäñòâåííî ïðåäøåñòâóþùèõ êðàéíåìó ïðàâîìó ýëåìåí-
òó õðîìîñîìû H2, ïðèâåäåò ê ñîçäàíèþ íîâîé îñîáè:
� �� � �� ��R H H( , )1 2 , H H�� �1 1, H XX XX2 �
( ).
Ïîëó÷åííûé ïîðÿäîê ñîåäèíåíèÿ îòíîøåíèé èäåíòè÷åí ïðèâåäåííîìó íà
ðèñ. 1.
Íà îñíîâå ïðåäëîæåííûõ ïðîöåäóð êîäèðîâàíèÿ (äåêîäèðîâàíèÿ) ðå-
øåíèÿ, îïåðàòîðîâ êðîññèíãîâåðà, ñåëåêöèè è ìóòàöèè ðàçðàáîòàí ãåíåòè-
÷åñêèé àëãîðèòì (ðèñ. 6), îñîáåííîñòüþ ñòðóêòóðíîé ñõåìû êîòîðîãî
ÿâëÿåòñÿ íàëè÷èå äâóõ ãðóïï ãåíåòè÷åñêèõ îïåðàòîðîâ äëÿ H1 è H2. Ãå-
íåòè÷åñêèé àëãîðèòì îáëàäàåò ïîëèíîìèàëüíîé âû÷èñëèòåëüíîé ñëîæ-
íîñòüþ.  çàâèñèìîñòè îò íàñòðîåê (÷èñëà îñîáåé ñòàðòîâîé ïîïóëÿöèè,
ïðàâèë ôîðìèðîâàíèÿ íîâûõ ïîïóëÿöèé, êðèòåðèÿ îñòàíîâêè è äð.) åãî âû-
÷èñëèòåëüíàÿ ñëîæíîñòü ìîæåò èçìåíÿòñÿ â ïðåäåëàõ îò O n( )2 äî O n( )5 .
Âûâîäû
Ðàçðàáîòàííûé ãåíåòè÷åñêèé àëãîðèòì ïîçâîëÿåò ðåøàòü çàäà÷ó âûáîðà
îïòèìàëüíîãî ïîðÿäêà ñîåäèíåíèÿ ðàñïðåäåëåííûõ îòíîøåíèé çà ïîëèíî-
ìèàëüíîå âðåìÿ. Ïðèìåíÿåìûå îïåðàòîðû êîäèðîâàíèÿ (äåêîäèðîâàíèÿ)
ðåøåíèé äàþò âîçìîæíîñòü íå îãðàíè÷èâàòü îáëàñòü ïîèñêà ìîäåëüþ
ëåâîñòîðîííåãî äåðåâà.
Genetic algorithm for solving the problem of optimal choice of the order of relations combi-
nation has been designed. The procedures of coding and decoding of solutions, mutation oper-
ators have been described, the structural algorithm scheme is presented.
1. Ãàðñèà-Ìîëèíà Ã., Óëüìàí Ä., Óèäîì Ä. Ñèñòåìû áàç äàííûõ. Ïîëíûé êóðñ.: Ïåð. ñ
àíãë. — Ì. : Èçä. äîì «Âèëüÿìñ», 2003. — 1088 ñ.
2. Êóðåé÷èê Â. Ì., Ëåáåäåâ Á. Ê., Ëåáåäåâ Î.Á . Ïîèñêîâàÿ àäàïòàöèÿ: òåîðèÿ è ïðàêòèêà. —
Ì. : ÔÈÇÌÀÒËÈÒ, 2006. — 272 ñ.
3. Ëåáåäåâ Á. Ê. Àäàïòàöèÿ â ÑÀÏÐ. —Òàãàíðîã: èçä-âî ÒÐÒÓ, 1999. — 160 ñ.
Ãåíåòè÷åñêèé àëãîðèòì ðåøåíèÿ çàäà÷è âûáîðà îïòèìàëüíîãî ïîðÿäêà ñîåäèíåíèÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 3 121
4. Ëåáåäåâ Á. Ê. Ìåòîäû ïîèñêîâîé àäàïòàöèè â çàäà÷àõ àâòîìàòèçèðîâàííîãî ïðîåêòè-
ðîâàíèÿ ÑÁÈÑ: Òàãàíðîã: èçä-âî ÒÐÒÓ, 2000. — 192 ñ.
5. Êóðåé÷èê Â. Ì., Ëåáåäåâ Á. Ê., Ëåáåäåâ Î. Á., ×åðíûøåâ Þ. Î. Àäàïòàöèÿ íà îñíîâå
ñàìîîáó÷åíèÿ. — Ðîñòîâ í/Ä : èçä-âî ÐÃÀÑÕÌ ÃÎÓ, 2004. — 146 ñ.
Ïîñòóïèëà 04.05.11;
ïîñëå äîðàáîòêè 16.01.12
×ÅÐÍÛØÅ Þðèé Îëåãîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð êàôåäðû «Âû÷èñëèòåëüíûå ñèñòåìû
è èíôîðìàöèîííàÿ áåçîïàñíîñòü» Ãîñóäàðñòâåííîãî îáðàçîâàòåëüíîãî ó÷ðåæäåíèÿ âûñøåãî
ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ Äîíñêîãî ãîñóäàðñòâåííîãî òåõíè÷åñêîãî óíèâåðñèòåòà. Â
1959 ã. îêîí÷èë Òàãàíðîãñêèé ðàäèîòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé —
ýâîëþöèîííîå ìîäåëèðîâàíèå, àäàïòèâíûå àëãîðèòìû, ìåòîäû îïòèìèçàöèè.
ÂÅÍÖÎÂ Íèêîëàé Íèêîëàåâè÷, êàíä. òåõí. íàóê, äîöåíò êàôåäðû «Èíôîðìàöèîííûå òåõíî-
ëîãèè» Ãîñóäàðñòâåííîãî îáðàçîâàòåëüíîãî ó÷ðåæäåíèÿ âûñøåãî ïðîôåññèîíàëüíîãî îáðàçî-
âàíèÿ Äîíñêîãî ãîñóäàðñòâåííîãî òåõíè÷åñêîãî óíèâåðñèòåòà.  2003 ã. îêîí÷èë Ðîñòîâñêóþ-
íà-Äîíó ãîñóäàðñòâåííóþ àêàäåìèþ ñåëüñêîõîçÿéñòâåííîãî ìàøèíîñòðîåíèÿ. Îáëàñòü íàó÷-
íûõ èññëåäîâàíèé — àäàïòèâíàÿ îïòèìèçàöèÿ.
Þ. Î. ×åðíûøåâ, Í. Í. Âåíöîâ
122 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 3
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/Description <<
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-61831 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-11-27T11:11:58Z |
| publishDate | 2012 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Чернышев, Ю.О. Венцов, Н.Н. 2014-05-12T14:01:20Z 2014-05-12T14:01:20Z 2012 Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений / Ю.О. Чернышев, Н.Н. Венцов // Электронное моделирование. — 2012 — Т. 34, № 3. — С. 115-122. — Бібліогр.: 5 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/61831 004.023 Разработан генетический алгоритм решения задачи выбора оптимального порядка соединения отношений. Описаны процедуры кодирования и декодирования решений, операторы мутации, приведена структурная схема генетического алгоритма. Розроблено генетичний алгоритм розв’язку задачі вибору оптимального порядку з’єднання відносин. Описано процедури кодування та декодування рішень, операторів мутації та наведено структурну схему генетичного алгоритму. Genetic algorithm for solving the problem of optimal choice of the order of relations combination has been designed. The procedures of coding and decoding of solutions, mutation operators have been described, the structural algorithm scheme is presented. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Применение методов и средств моделирования Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений Article published earlier |
| spellingShingle | Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений Чернышев, Ю.О. Венцов, Н.Н. Применение методов и средств моделирования |
| title | Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений |
| title_full | Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений |
| title_fullStr | Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений |
| title_full_unstemmed | Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений |
| title_short | Генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений |
| title_sort | генетический алгоритм решения задачи выбора оптимального порядка соединения распределенных отношений |
| topic | Применение методов и средств моделирования |
| topic_facet | Применение методов и средств моделирования |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/61831 |
| work_keys_str_mv | AT černyševûo genetičeskiialgoritmrešeniâzadačivyboraoptimalʹnogoporâdkasoedineniâraspredelennyhotnošenii AT vencovnn genetičeskiialgoritmrešeniâzadačivyboraoptimalʹnogoporâdkasoedineniâraspredelennyhotnošenii |