дНЙСЛЕМР БГЪР ХГ ЙЩЬЮ ОНХЯЙНБНИ ЛЮЬХМШ. юДПЕЯ НПХЦХМЮКЭМНЦН ДНЙСЛЕМРЮ : http://www.abitu.ru/en2002/closed/viewwork.html?work=24
дЮРЮ ХГЛЕМЕМХЪ: Fri May 5 15:25:32 2006
дЮРЮ ХМДЕЙЯХПНБЮМХЪ: Tue Oct 2 02:18:07 2012
йНДХПНБЙЮ: koi8-r
оНХЯЙНБШЕ ЯКНБЮ: О О О О О О О О

цЕМЕРХВЕЯЙХЕ ЮКЦНПХРЛШ

юБРНП: йНПЕМЧЬЙХМ юМРНМ бЮЯХКЭЕБХВ

11 ю ЙКЮЯЯ, яЛНКЕМЯЙХИ оЕДЮЦНЦХВЕЯЙХИ кХЖЕИ.

Ц. яЛНКЕМЯЙ, e-mail toshakor@yandex.ru

хЯРНПХЪ

рЕНПХЪ ЩБНКЧЖХХ дЮПБХМЮ МЕ ЛНЦКЮ МЕ ОНДБХЦМСРЭ ОПНЦПЮЛЛХЯРНБ МЮ
ЯНГДЮМХЕ ЯХЯРЕЛ, ДЕИЯРБСЧЫХУ ОН РЕЛ ФЕ ОПХМЖХОЮЛ, ВРН Х АХНКНЦХВЕЯЙХЕ.
яМЮВЮКЮ ЩРН ДЕКЮКНЯЭ КХЬЭ ДКЪ РНЦН, ВРНАШ ОНЯЛНРПЕРЭ, ВРН ОНКСВХРЯЪ ОПХ
ЛНДЕКХПНБЮМХХ ЕЯРЕЯРБЕММНИ ФХГМХ МЮ ЙНЛОЭЧРЕПЕ, ЩРНР ПЮГДЕК
ОПНЦПЮЛЛХПНБЮМХЪ ПЮГБХБЮКЯЪ Х ЯЕИВЮЯ ЛШ ЕЦН МЮГШБЮЕЛ Artificial Life
(хЯЙСЯЯРБЕММЮЪ фХГМЭ). йНМЙПЕРМНЦН ОПХЛЕМЕМХЪ Б ДЮММШИ ЛНЛЕМР ЕЛС МЕ
МЮИДЕМН, МН Б АСДСЫЕЛ БХДЪРЯЪ МЕБННАПЮГХЛШЕ БШЯНРШ.
мН ЙПНЛЕ хЯЙСЯЯРБЕММНИ ФХГМХ ЯСЫЕЯРБСЧР ДПСЦХЕ ЙНЛОЭЧРЕПМН-
АХНКНЦХВЕЯЙХЕ ЯХЯРЕЛШ, ЙНРНПШЕ СФЕ ЯЕИВЮЯ ОПХЛЕМЪЧРЯЪ ДКЪ ПЕЬЕМХЪ ПЮГКХВМШУ
ГЮДЮВ. й МХЛ ЛНФМН НРМЕЯРХ цЕМЕРХВЕЯЙНЕ оПНЦПЮЛЛХПНБЮМХЕ (Genetic
Programming), щБНКЧЖХНММШЕ яРПЮРЕЦХХ (Evolutionary Strategies), МС Х
цЕМЕРХВЕЯЙХЕ юКЦНПХРЛШ (Genetic Algorithms, ДЮКЕЕ цю), Н ЙНРНПШУ ОНИД╦Р
ПЕВЭ Б ДЮММНИ ЯРЮРЭЕ.
юБРНП ОНЯРЮБХК ЯЕАЕ ЖЕКЭ НАЗЪЯМХРЭ ВХРЮРЕКЧ, ВРН цю - ЩРН МЕ ЙЮЙХЕ-РН
ГЮНАКЮВМШЕ ДЮКХ, Н ЙНРНПШУ ХЛЕЧР ОПЮБН ЦНБНПХРЭ РНКЭЙН ОПНТЕЯЯНПЮ, ЩРН
БОНКМЕ ОПХЛЕМХЛШИ ЛЕРНД ПЕЬЕМХЪ ГЮДЮВ, ЙНРНПШЕ ЯРЮМНБЪРЯЪ МЮ РЕПМХЯРНЛ ОСРХ
МЮОХЯЮМХЪ ОПНЦПЮЛЛ! дКЪ ОНМЪРМНЯРХ Б УНДЕ ЯРЮРЭХ ЛШ ПЮЯЯЛНРПХЛ ПЕЬЕМХЕ
ХГБЕЯРМНИ ГЮДЮВХ Н ЙНЛЛХБНЪФЕПЕ Я ОНЛНЫЭЧ цю. дЮ, Е╦ ЛНФМН ПЕЬХРЭ КХЬЭ
ОНКМШЛ ОЕПЕАНПНЛ, МН цю Х МЕ ДЮЧР РНВМШУ ПЕЬЕМХИ (НАШВМН НЬХАЮЧРЯЪ МЮ 5-
10%), ГЮРН БОНКМЕ ЯМНЯМШИ НРБЕР ДКЪ ДБЮДЖЮРХ ЦНПНДНБ МЮЬЮ ОПНЦПЮЛЛЮ АСДЕР
БШДЮБЮРЭ ГЮ ОЮПС ЯЕЙСМД, Ю ЯРЮМДЮПРМНЛС ЮКЦНПХРЛС ОПХДЕРЯЪ ОНЛСВЮРЭЯЪ,
ОЕПЕАХПЮЪ 20! БЮПХЮМРНБ.

рЕНПХЪ

оПЕФДЕ ВЕЛ ОПХЯРСОХРЭ Й ПЕЬЕМХЧ МЮЬЕИ ГЮДЮВХ, МСФМН ХГСВХРЭ МЕЛМНЦН
РЕНПХХ, ОНЩРНЛС МЮЯРПНИРЕЯЭ МЮ ЯННРБЕРЯРБСЧЫХИ КЮД.
б НАЫХУ ВЕПРЮУ ПЮАНРС цю ЛНФМН НОХЯЮРЭ РЮЙ: НМ ЯНГДЮЕР ОНОСКЪЖХЧ
НЯНАЕИ, ЙЮФДЮЪ ХГ ЙНРНПШУ ЪБКЪЕРЯЪ ПЕЬЕМХЕЛ ГЮДЮВХ, Ю ГЮРЕЛ ЩРХ НЯНАХ
ЩБНКЧЖХНМХПСЧР ОН ОПХМЖХОС ╚БШФХБЮЕР ЯХКЭМЕИЬХИ╩, РН ЕЯРЭ НЯРЮЧРЯЪ КХЬЭ
ЯЮЛШЕ НОРХЛЮКЭМШЕ ПЕЬЕМХЪ.
рЕОЕПЭ ПЮГАЕПЕЛЯЪ ОНОНДПНАМЕЕ. йЮФДСЧ НЯНАЭ НОХЯШБЮЕР УПНЛНЯНЛЮ (Б
МЮЬЕЛ ЯКСВЮЕ ЩРН АСДЕР ЛЮЯЯХБ ХГ МНЛЕПНБ ЦНПНДНБ, ЙНРНПШЕ ОН НВЕПЕДХ
ОПНУНДХР ЙНЛЛХБНЪФЕП), УПНЛНЯНЛЮ ЯНЯРНХР ХГ ЦЕМНБ (МНЛЕПЮ ЦНПНДНБ), ЙНРНПШЕ
ПЮЯОНКЮЦЮЧРЯЪ Б НОПЕДЕКЕММШУ ОНГХЖХЪУ (КНЙСЯЮУ) УПНЛНЯНЛШ. бННАЫЕ, Б
АНКЭЬХМЯРБЕ ЯКСВЮЕБ УПНЛНЯНЛЮ ОПЕДЯРЮБКЪЕР ЯНАНИ АХРНБСЧ ЯРПНЙС, ЦДЕ ЙЮФДШИ
АХР - ЦЕМ, МН ОПНЦПЮЛЛХЯР БНКЕМ БШАХПЮРЭ РС ТНПЛС, ЙНРНПЮЪ СДНАМЕЕ ДКЪ
ПЕЬЕМХЪ ЕЦН ГЮДЮВХ. хРЮЙ, БЯЪ МЮЯКЕДЯРБЕММЮЪ ХМТНПЛЮЖХЪ, ХКХ ЦЕМНРХО,
УПЮМХРЯЪ Б УПНЛНЯНЛЮУ.
пЮАНРЮ цю ХЛХРХПСЕР ЕЯРЕЯРБЕММСЧ ФХГМЭ, РНКЭЙН ЯХКЭМН СОПНЫЕММСЧ. мЮ
ПХЯ1 ОПЕДЯРЮБКЕМЮ АКНЙ-ЯУЕЛЮ ЯРЮМДЮПРМНЦН цю. пЮЯЯЛНРПХЛ ЙЮФДШИ ХГ
НОЕПЮРНПНБ цю:

1)яНГДЮМХЕ ОНОСКЪЖХХ.
мЮ ЩРНЛ ЩРЮОЕ Я ОНЛНЫЭЧ ЯВЕРВХЙЮ ЯКСВЮИМШУ ВХЯЕК ЛШ ЯНГДЮЕЛ
МЮВЮКЭМСЧ ХКХ ЯРЮПРНБСЧ ОНОСКЪЖХЧ НЯНАЕИ.

2)яЕКЕЙЖХЪ.
гДЕЯЭ ЮКЦНПХРЛ БШАХПЮЕР НЯНАЕИ Б ЯКЕДСЧЫЕЕ ОНЙНКЕМХЕ. оПХ ЩРНЛ
АНКЭЬХЕ ЬЮМЯШ ХЛЕЧР АНКЕЕ ОПХЯОНЯНАКЕММШЕ (Б МЮЬЕЛ ЯКСВЮЕ ЩРН НЯНАХ Я
МЮХЛЕМЭЬЕИ ДКХММНИ ОСРХ ЙНЛЛХБНЪФЕПЮ).
яСЫЕЯРБСЕР МЕЯЙНКЭЙН ЛЕРНДНБ ЯЕКЕЙЖХХ, МН МЮХАНКЕЕ ПЮЯОПНЯРПЮМЕМ
ЛЕРНД ПСКЕРЙХ(roulette-wheel selection), ЙНРНПШЛ ЛШ Х АСДЕЛ ОНКЭГНБЮРЭЯЪ.
гЮЙКЧВЮЕРЯЪ НМ Б РНЛ, ВРН ДКЪ ЙЮФДНИ НЯНАХ БШВХЯКЪЕРЯЪ ТСМЙЖХЪ
ОПХЯОНЯНАКЕММНЯРХ Х ЬЮМЯШ БШФХРЭ НМЮ ОНКСВЮЕР ОПНОНПЖХНМЮКЭМШЕ ГМЮВЕМХЧ
ЩРНИ ТСМЙЖХХ. рН ЕЯРЭ ЙНКЕЯН ПСКЕРЙХ ДЕКХРЯЪ МЮ ЯЕЙРНПШ НЯНАЕИ,
ОПНОНПЖХНМЮКЭМШЕ ОПХЯОНЯНАКЕММНЯРХ, Х, ГЮОСЯРХБ ПСКЕРЙС ЯРНКЭЙН ПЮГ,
ЯЙНКЭЙН С МЮЯ НЯНАЕИ, ЛШ ОНКСВЮЕЛ МНБНЕ ОНЙНКЕМХЕ (Б МЕЦН ОЕПЕУНДЪР РЕ
НЯНАХ, МЮОПНРХБ ЯЕЙРНПЮ ЙНРНПШУ НЯРЮМНБХКЯЪ БНКВНЙ).
рЮЙФЕ МЕКЭГЪ МЕ СОНЛЪМСРЭ Н РЮЙНЛ ЛЕРНДЕ НРАНПЮ, ЙЮЙ ЩКХРХГЛ - ОПХ
МЕЛ ЯЮЛЮЪ ОПХЯОНЯНАКЕММЮЪ НЯНАЭ БЯЕЦДЮ ОЕПЕУНДХР Б ЯКЕДСЧЫЕЕ ОНЙНКЕМХЕ.
щКХРХГЛ НАШВМН БМЕДПЪЧР Б ДПСЦХЕ ЛЕРНДШ НРАНПЮ - ЯНУПЮМЪЧР ╚ЩКХРМСЧ╩
НЯНАЭ БМЕ ГЮБХЯХЛНЯРХ НР ДПСЦХУ СЯКНБХИ ЯЕКЕЙЖХХ.

3)яЙПЕЫХБЮМХЕ ХКХ ЙПНЯЯНБЕП (crossover)
б ЩРНИ ВЮЯРХ цю ЯКСВЮИМШЛ НАПЮГНЛ БШАХПЮЧРЯЪ ДБЕ НЯНАХ, ЙНРНПШЕ
ГЮРЕЛ ОН НОПЕДЕКЕММШЛ ОПЮБХКЮЛ НАЛЕМХБЮЧРЯЪ ЦЕМЮЛХ.
яЮЛШЛ ОПНЯРШЛ Х, Б РН ФЕ БПЕЛЪ , ОН ЛМЕМХЧ ЮБРНПЮ, ЯЮЛШЛ
ЩТТЕЙРХБМШЛ, ЛЕРНДНЛ ЯЙПЕЫХБЮМХЪ ЪБКЪЕРЯЪ НДМНРНВЕВМШИ ЙПНЯЯНБЕП. нМ
ПЮАНРЮЕР РЮЙ: ЦЕМЕПХПСЕРЯЪ ЯКСВЮИМНЕ МЮРСПЮКЭМНЕ ВХЯКН n, ЛЕМЭЬЕЕ ДКХМШ
УПНЛНЯНЛШ, Х ЙЮФДЮЪ ПНДХРЕКЭЯЙЮЪ УПНЛНЯНЛЮ ДЕКХРЯЪ МЮ ДБЕ ВЮЯРХ, ОЕПБЮЪ
ХГ ЙНРНПШУ ЯНДЕПФХР ОЕПБШЕ n ЦЕМНБ, Ю БРНПЮЪ - НЯРЮБЬХИЯЪ ЦЕМНРХО. йЮФДЮЪ
ДНВЕПМЪЪ НЯНАЭ ЯНЯРНХР ХГ ОЕПБНИ ВЮЯРХ НДМНИ ПНДХРЕКЭЯЙНИ НЯНАХ Х БРНПНИ
ВЮЯРХ ДПСЦНИ, РН ЕЯРЭ ПНДХРЕКХ ЙЮЙ АШ НАЛЕМХБЮЧРЯЪ ВЮЯРЪЛХ. пХЯ.2 -
ХККЧЯРПЮЖХЪ НДМНРНВЕВМНЦН ЙПНЯЯНБЕПЮ ДКЪ УПНЛНЯНЛ-АХРНБШУ ЯРПНЙ.

[pic]

рЮЙФЕ ДНБНКЭМН ПЮЯОПНЯРПЮМЕМ ДБСУРНВЕВМШИ ЙПНЯЯНБЕП. оПХ МЕЛ
БШАХПЮЧРЯЪ ДБЕ РНВЙХ ПЮГПШБЮ Х ПНДХРЕКХ НАЛЕМХБЮЧРЯЪ СВЮЯРЙНЛ УПНЛНЯНЛ
ЛЕФДС МХЛХ. пЮБМНЛЕПМШИ ЙПНЯЯНБЕП ПЕЮКХГСЕР МЮЯКЕДНБЮМХЕ ДЕРЭЛХ ЙЮФДНЦН
ХГ ЦЕМНБ ПНДХРЕКЕИ Я ГЮДЮММНИ БЕПНЪРМНЯРЭЧ.

4)лСРЮЖХЪ(mutation)
щРНР НОЕПЮРНП цю Я ГЮДЮММНИ (НАШВМН НВЕМЭ ЛЮКЕМЭЙНИ) БЕПНЪРМНЯРЭЧ
ЯКСВЮИМШЛ НАПЮГНЛ ХГЛЕМЪЕР ЯКСВЮИМШИ ЦЕМ НЯНАХ (ДКЪ АХРНБШУ ЯРПНЙ -
ХМБЕПРХПСЕР). щРН, ОНФЮКСИ, ОПНЯРЕИЬЮЪ ВЮЯРЭ цю, Х ДПСЦХЕ ЙНЛЛЕМРЮПХХ Й
МЕИ ХГКХЬМХ.

оПЮЙРХЙЮ

мС БНР, Я НЯМНБЮЛХ РЕНПХХ цю БПНДЕ АШ ПЮГНАПЮКХЯЭ - ОНПЮ ОЕПЕУНДХРЭ
Й ОПЮЙРХЙЕ. дКЪ МЮВЮКЮ ВЕРЙН ОНЯРЮБХЛ ГЮДЮВС: ЙНЛЛХБНЪФЕП ПЕЬХК НАЗЕУЮРЭ
20 ЦНПНДНБ ОН ЙПЮРВЮИЬЕЛС ОСРХ. нМ МЮВХМЮЕР ЯБНИ ОСРЭ Б КЧАНЛ ХГ МХУ Х
ГЮЙЮМВХБЮЕР Б ЙЮЙНЛ-РН ДПСЦНЛ, ОПХ ЩРНЛ МХ Б НДМНЛ ЦНПНДЕ НМ МЕ ДНКФЕМ
ОНАШБЮРЭ ДБЮФДШ. юАЯНКЧРМН БЯЕ ЦНПНДЮ ЯНЕДХМЕМШ ДНПНЦЮЛХ Х ХУ ДКХМШ
ЦЕМЕПХПСЧРЯЪ ЯВЕРВХЙНЛ ЯКСВЮИМШУ ВХЯЕК. мЮЛ МЕНАУНДХЛН ГЮ ЙНПНРЙНЕ БПЕЛЪ
МЮИРХ ОСРЭ, АКХГЙХИ Й ЙПЮРВЮИЬЕЛС.
б ЙЮВЕЯРБЕ ЙНЛОХКЪРНПЮ АСДЕЛ ХЯОНКЭГНБЮРЭ Borland Delphi. яНГДЮЕЛ
ЙНМЯНКЭМНЕ ОПХКНФЕМХЕ: File->New->Console Application. яМЮВЮКЮ НАЗЪБХЛ
МЕНАУНДХЛШЕ ЦКНАЮКЭМШЕ ЙНМЯРЮМРШ, РХОШ Х ОЕПЕЛЕММШЕ:

const n_t=20; //ЙНК-БН ЦНПНДНБ
n_os=50; //ЙНК-БН НЯНАЕИ
v_mut=1; //БЕПНЪРМНЯРЭ ЛСРЮЖХХ ДКЪ ЙЮФДНИ НЯНАХ(Б %)
v_cross=60;//БЕПНЪРМНЯРЭ ЯЙПЕЫХБЮМХЪ ДКЪ ЙЮФДНИ ОЮПШ
//НЯНАЕИ(Б %)
max=10; //ЛЮЙЯХЛЮКЭМНЕ ПЮЯЯРНЪМХЕ ЛЕФДС ЦНПНДЮЛХ
type TTowns=array[1..n_t,1..n_t]of byte;
//ЛЮЯЯХБ, НОХЯШБЮЧЫХИ ПЮЯЯРНЪМХЪ ЛЕФДС ЦНПНДЮЛХ
TOsobi=array[1..n_os+1,1..n_t]of byte;
//ЛЮЯЯХБ УПНЛНЯНЛ

var towns:TTowns;//ОЕПЕЛЕММЮЪ ЦНПНДНБ
i,j,k,p,n:word;//ОЕПЕЛЕММШЕ ДКЪ ЖХЙКНБ Х Р.Д. Х Р.О.
osobi,new_osobi,pr:TOsobi;//ОЕПЕЛЕММШЕ НЯНАЕИ
c:char;//ОПНЯРН ЯХЛБНКЭМЮЪ ОЕПЕЛЕММЮЪ

мЕЙНРНПШЕ ГЮЛЕВЮМХЪ ОН КХЯРХМЦС: towns[i,j] - ПЮЯЯРНЪМХЕ ЛЕФДС i-Л
Х j-Л ЦНПНДНЛ. еЯРЕЯРБЕММН, ДНКФМШ БШОНКМЪРЭЯЪ ПЮБЕМЯРБЮ:
towns[i,j]=towns[j,i] Х towns[i,i]=0 (ОНЯКЕДМЕЕ ЯЙНПЕЕ ДКЪ ОПХКХВХЪ - НМН
МЮЛ МЕ ОНМЮДНАХРЯЪ). дКЪ ЛЮЯЯХБЮ НЯНАЕИ osobi[i,j] - МНЛЕП j-ЦН ЦНПНДЮ Б
ОСРХ ЙНЛЛХБНЪФЕПЮ, НОХЯШБЮЕЛНЦН i-И УПНЛНЯНЛНИ. юБРНП БГЪК (n_os+1)НЯНАЕИ
ДКЪ СДНАЯРБЮ - ОНЯКЕДМЧЧ МЕ АСДСР ЙЮЯЮРЭЯЪ ЯЙПЕЫХБЮМХЕ Х ЛСРЮЖХЪ, НМЮ
БЯЕЦДЮ АСДЕР ОЕПЕУНДХРЭ Б ЯКЕДСЧЫЕЕ ОНЙНКЕМХЕ - ЩРН РЮ ЯЮЛЮЪ ЩКХРМЮЪ
НЯНАЭ. нАЗЪБКЕМН РПХ ОЕПЕЛЕММШУ НЯНАЕИ ДКЪ ОПНЖЕДСПШ ЯЕКЕЙЖХХ.
рЕОЕПЭ МЮОХЬЕЛ ОПНЖЕДСПС, ЙНРНПЮЪ, ЯНЦКЮЯМН СЯКНБХЧ, ЦЕМЕПХПСЕР
towns (ПЮЯЯРНЪМХЕ ЛЕФДС ЦНПНДЮЛХ НР 1 ДН max БЙКЧВХРЕКЭМН):

procedure gen_towns;
begin
for i:=1 to n_t do
begin
for k:=i+1 to n_t do
begin
towns[i,k]:=random(max)+1;
towns[k,i]:=towns[i,k];
end;
towns[i,i]:=0;
end;
end;

р.Й. ЙНЛЛЕМРЮПХХ Й ОПЕДШДСЫЕЛС КХЯРХМЦС ХГКХЬМХ, ОЕПЕИДЕЛ Й
ОПНЖЕДСПЕ ЯНГДЮМХЪ ОНОСКЪЖХХ, НМЮ МЕЛМНЦН ОНЯКНФМЕЕ, БЯЕ ОНЪЯМЕМХЪ
ОПХБЕДЕМШ ОПЪЛН Б КХЯРХМЦЕ:

procedure gen_pop;
begin
for i:=1 to n_os+1 do
begin
//ГЮОНКМЪЕЛ НЯНАЭ ЦНПНДЮЛХ 1,2,3...20
for k:=1 to n_t do osobi[i,k]:=k;
{ЛЕМЪЕЛ ЛЕЯРЮЛХ ОЕПБШИ ЦЕМ Х ЯКСВЮИМШИ,
ГЮРЕЛ БРНПНИ Х ДПСЦНИ ЯКСВЮИМШИ Х Р.Д.
б ПЕГСКЭРЮРЕ ЙЮФДШИ ЦНПНД БЯРПЕРХРЯЪ Б
УПНЛНЯНЛЕ КХЬЭ НДХМ ПЮГ}
for k:=1 to n_t do
begin
j:=osobi[i,k];
p:=random(n_t)+1;
osobi[i,k]:=osobi[i,p];
osobi[i,p]:=j;
end;
end;
end;

рЕОЕПЭ ДНЬКЮ НВЕПЕДЭ ДН НОЕПЮРНПЮ ЯЕКЕЙЖХХ, ЩРН ЯЮЛЮЪ ЯКНФМЮЪ
ОПНЖЕДСПЮ Б МЮЬЕИ ОПНЦПЮЛЛЕ, РЮЙ ВРН ЯЙНМЖЕМРПХПСИРЕЯЭ:

procedure selection;
var best:byte;//МНЛЕП КСВЬЕИ НЯНАХ
prisp:array[0..n_os+1]of word;
//ЛЮЯЯХБ ОПХЯОНЯНАКЕММНЯРЕИ НЯНАЕИ
begin
prisp[0]:=0;
p:=200;
best:=0;
//ЖХЙК ГЮОНКМЕМХЪ ЛЮЯЯХБЮ prisp
for i:=1 to n_os+1 do
begin
j:=0;
for k:=2 to n_t do
j:=j+towns[osobi[i,k-1],osobi[i,k]];
prisp[i]:=prisp[i-1]+10000 div j;
if p>j then begin
p:=j;
best:=i;
end;
end;
//ЙНОХПНБЮМХЕ КСВЬЕИ НЯНАХ МЮ (n_os+1)-Е ЩКХРМНЕ ЛЕЯРН
for i:=1 to n_t do new_osobi[n_os+1,i]:=osobi[best,i];
//ПЕЮКХГЮЖХЪ ПСКЕРЙХ
for i:=1 to n_os do
begin
j:=random(prisp[n_os]);
for k:=1 to n_os do
if prisp[k]>j then
begin
j:=k;
break;
end;
for k:=1 to n_t do new_osobi[i,k]:=osobi[j,k];
end;
//НАЛЕМ ОЕПЕЛЕММШУ osobi Х new_osobi ВЕПЕГ pr
pr:=osobi;
osobi:=new_osobi;
new_osobi:=pr;
//БШБНДХЛ МЮХЛЕМЭЬХИ ОСРЭ ДКЪ ЙЮФДНЦН 250-ЦН ОНЙНКЕМХЪ
//n-ЯВЕРВХЙ ОНЙНКЕМХИ (Б НЯМНБМНИ ТСМЙЖХХ)
if n mod 250=0 then writeln(p);
end;

пЮГАЕПЕЛ ЩРНР КХЯРХМЦ. яМЮВЮКЮ НАМСКЪЕЛ ОЕПЕЛЕММШЕ best Х prisp[0]
- ОНЯКЕДМЪЪ ЯКСФХР КХЬЭ ДКЪ ОПНЯРНИ НПЦЮМХГЮЖХХ ЖХЙКЮ. оЕПЕЛЕММНИ p, Б
ЙНРНПНИ АСДЕР УПЮМХРЭЯЪ ЙПЮРВЮИЬХИ ОСРЭ ОПХЯБЮХБЮЕЛ ГМЮВЕМХЕ 200,
ЙНРНПНЕ АНКЭЬЕ ЛЮЙЯХЛЮКЭМНЦН.
дЮКЕЕ Б ЖХЙКЕ ДКЪ ЙЮФДНИ НЯНАХ БШВХЯКЪЕЛ ДКХМС ОСРХ j, ЕЯКХ НМЮ
ЛЕМЭЬЮЪ ХГ БШВХЯКЕММШУ ДН ЩРНЦН, ОПХЯБЮХБЮЕЛ p ЕЕ ГМЮВЕМХЕ. лЮЯЯХБ prisp
ГЮОНКМЪЕЛ РЮЙ: prisp[n]=prisp[n-1]+f(n) ,ЦДЕ f(n) - ТСМЙЖХЪ
ОПХЯОНЯНАКЕММНЯРХ НЯНАХ (ВЕЛ АНКЭЬЕ ОПХЯОНЯНАКЕММНЯРЭ, РЕЛ АНКЭЬЕ f(n)).
р.Й. ЛШ ПЕЬЮЕЛ ГЮДЮВС ЛХМХЛХГЮЖХХ, РН ОПХУНДХРЯЪ АПЮРЭ f(n)=10000 div j.
гЮВЕЛ ЛЮЯЯХБ prisp ГЮОНКМЪЕРЯЪ ХЛЕММН РЮЙ, бШ СГМЮЕРЕ ВСРЭ ОНГФЕ, Ю ОНЙЮ
ГЮЛЕРЭРЕ, ВРН ╚ЩКХРМЮЪ╩ НЯНАЭ РНФЕ СВЮЯРБСЕР Б БШВХЯКЕМХХ
ОПХЯОНЯНАКЕММНЯРХ - Ю БДПСЦ МЮИДЕРЯЪ НЯНАЭ Я ЛЕМЭЬЕИ ДКХМНИ ОСРХ.
б ЯКЕДСЧЫЕЛ ЖХЙКЕ ЛШ ОПНЯРН ЙНОХПСЕЛ КСВЬСЧ НЯНАЭ МЮ (n_os+1)-Е
ЛЕЯРН Х АНКЭЬЕ МЕ РПНЦЮЕЛ ЕЕ ДН ЯКЕДСЧЫЕЦН БШВХЯКЕМХЪ ОПХЯОНЯНАКЕММНЯРЕИ.

[pic]
лЮЯЯХБ prisp ЙЮЙ АШ ПЮГАХБЮЕР ЛМНФЕЯРБН ЖЕКШУ МЕНРПХЖЮРЕКЭМШУ
ВХЯЕК, ЛЕМЭЬХУ prisp[n_os], МЮ ОПНЛЕФСРЙХ НЯНАЕИ, ДКХМЮ ЙЮФДНЦН ХГ
ЙНРНПШУ - ЩРН ОПХЯОНЯНАКЕММНЯРЭ НЯНАХ, РН ЕЯРЭ ЛШ ╚ПЮГЛЕВЮЕЛ╩ РС ЯЮЛСЧ
ПСКЕРЙС(ЯЛ. ПХЯ.3). я ОНЛНЫЭЧ ТСМЙЖХХ random ЦЕМЕПХПСЕЛ 0≤j ЛЕЯРН, МЮ ЙНРНПНЛ НЯРЮМНБХКНЯЭ ЙНКЕЯН ПСКЕРЙХ, Ю ГЮРЕЛ ХЫЕЛ, Б ЙЮЙНЛ
ОНКСХМРЕПБЮКЕ ЯНДЕПФХРЯЪ j, РН ЕЯРЭ МЮОПНРХБ ЙЮЙНЦН ЯЕЙРНПЮ НЯРЮМНБХКЮЯЭ
ПСКЕРЙЮ. нЯНАЭ, ЯННРБЕРЯРБСЧЫЮЪ ЩРНЛС ОНКСХМРЕПБЮКС-ЯЕЙРНПС, ОЕПЕУНДХР Б
ЯКЕДСЧЫЕЕ ОНЙНКЕМХЕ. рЮЙ ОПНБНДХЛ n_os ГЮОСЯЙНБ ПСКЕРЙХ.
б ОНЯКЕДМЕИ ВЮЯРХ ОПНЖЕДСПШ ЛШ ОПНЯРН ЛЕМЪЕЛ ЯРЮПНЕ(osobi) Х
МНБНЕ(new_osobi) ОНЙНКЕМХЪ ВЕПЕГ ОЕПЕЛЕММСЧ pr.
рЕОЕПЭ ОНПЮ ОНДСЛЮРЭ НА ЮКЦНПХРЛЕ ЯЙПЕЫХБЮМХЪ. яРЮМДЮПРМШИ
НДМНРНВЕВМШИ ЙПНЯЯНБЕП МЕ ОНДНИДЕР - Б УПНЛНЯНЛЮУ ОНРНЛЙНБ НДХМ ЦНПНД
ЛНФЕР БЯРПЕРХРЭЯЪ ДБЮ ПЮГЮ, Ю ДПСЦНИ - МХ ПЮГС, ОНЩРНЛС ОПХДЕРЯЪ
ОПХДСЛШБЮРЭ ВРН-РН ЯБНЕ. юБРНП ПЮГПЮАНРЮК ЮКЦНПХРЛ МЮ АЮГЕ НДМНРНВЕВМНЦН
ЙПНЯЯНБЕПЮ, МН ЯНУПЮМЪЧЫХИ ЯНЯРЮБ ЦНПНДНБ, ЕЦН ЛШ Х ОПХЛЕМХЛ.
[pic]
яМЮВЮКЮ ЛШ ДЕКХЛ ОЕПБСЧ ПНДХРЕКЭЯЙСЧ УПНЛНЯНЛС РНВЙНИ ПЮГПШБЮ МЮ
ДБЕ ВЮЯРХ, ДКХМЮ ЙЮФДНИ ХГ ЙНРНПШУ МЕ ЛЕМЭЬЕ ДБСУ. мЮГНБЕЛ МЮАНП ЦЕМНБ ХГ
ОЕПБНИ ВЮЯРХ ю. рЕОЕПЭ МЮВХМЮЕЛ ХЯЙЮРЭ БН БРНПНИ ПНДХРЕКЭЯЙНИ УПНЛНЯНЛЕ
ЦЕМШ (РН ЕЯРЭ МНЛЕПЮ ЦНПНДНБ) ХГ МЮАНПЮ ю. оЕПБШИ МЮИДЕММШИ ЛЕМЪЕЛ
ЛЕЯРЮЛХ Я ОЕПБШЛ ЦЕМНЛ ОЕПБНИ УПНЛНЯНЛШ, БРНПНИ - ЯН БРНПШЛ Х РЮЙ ДЮКЕЕ.
вРНАШ ЯРЮКН ОНМЪРМЕЕ, БГЦКЪМХРЕ МЮ ПХЯ.4, НМ МЕОКНУН ХККЧЯРПХПСЕР ДЮММШИ
ЮКЦНПХРЛ. йНМЕВМН, КСВЬЕ АШКН АШ НОХПЮРЭЯЪ МЮ ДБСУРНВЕВМШИ ЙПНЯЯНБЕП -
╚НРЫЕОКЪРЭ╩ ОПНХГБНКЭМСЧ ВЮЯРЭ УПНЛНЯНЛШ, Ю МЕ НАЪГЮРЕКЭМН КЕФЮЫСЧ С
КЕБНЦН ЙПЮЪ, МН, ЖЕКЭ ОПХЛЕПЮ Й ЯРЮРЭЕ - ОНМЪРМНЯРЭ, Ю МЕ ЩТТЕЙРХБМНЯРЭ.
хРЮЙ, ОХЬЕЛ ОПНЖЕДСПС:

procedure crossover;
var prom:array[1..n_t]of byte;
//ОПНЛЕФСРНВМШИ ЛЮЯЯХБ ДКЪ ГЮОХЯХ ЦЕМНБ
u:integer;//ЯВЕРВХЙ ДКЪ prom
begin
for i:=1 to n_os div 2 do
//ПЕЬЮЕЛ, ОПХГБНДХРЭ КХ ЯЙПЕЫХБЮМХЕ
if random(100) begin
//СЯРЮМЮБКХБЮЕЛ РНВЙС ПЮГПШБЮ
p:=random(n_t-2)+2;
//СЯРЮМЮБКХБЮЕЛ ЯВЕРВХЙ ДКЪ prom
u:=1;
//ЯЙЮМХПНБЮМХЕ ╚БРНПНИ╩ УПНЛНЯНЛШ
for k:=1 to n_t do
//ОПНБЕПЪЕЛ, ЯНДЕПФХРЯЪ КХ k-И ЦЕМ Б ю
for j:=1 to p do
//ЕЯКХ ЦЕМ ЯНДЕПФХРЯЪ Б МЮАНПЕ ю
if osobi[i*2-1,k]=osobi[i*2,j] then
begin
//ЙНОХПСЕЛ ЕЦН Б prom
prom[u]:=osobi[i*2-1,k];
//МЮ ЕЦН ЛЕЯРН - ЦЕМ ХГ МЮАНПЮ ю
osobi[i*2-1,k]:=osobi[i*2,u];
//СБЕКХВХБЮЕЛ ЯВЕРВХЙ ДКЪ prom МЮ 1
inc(u);
//БШУНДХЛ ХГ ЖХЙКЮ ОН j
break;
end;
//ГЮЛЕМЪЕЛ ЦЕМШ МЮАНПЮ ю МЮ ЦЕМШ ХГ prom
for j:=1 to p do osobi[i*2,j]:=prom[j];
end;
end;

щРЮ ОПНЖЕДСПЮ ОНКМНЯРЭЧ ПЕЮКХГСЕР НОХЯЮММШИ БШЬЕ ЮКЦНПХРЛ. р.Й.
НЯНАХ Б ЯКЕДСЧЫЕЕ ОНЙНКЕМХЕ ОЕПЕУНДЪР Б ОПНХГБНКЭМНЛ ОНПЪДЙЕ, МЕ
ГЮБХЯЪЫЕЛ НР ХУ ОНПЪДЙЮ Б ОПЕДШДСЫЕЛ ОНЙНКЕМХХ, РН ЮБРНП ОНГБНКХК ЯЕАЕ
ЯЙПЕЫХБЮРЭ МЕ НЯНАХ Я ОПНХГБНКЭМШЛХ МНЛЕПЮЛХ, Ю ОЕПБСЧ ЯН БРНПНИ, РПЕРЭЧ
Я ВЕРБЕПРНИ Х РЮЙ ДЮКЕЕ.
дКЪ ЙЮФДНИ РЮЙНИ ОЮПШ БЕПНЪРМНЯРЭ ЯЙПЕЫХБЮМХЪ v_cross Х ЛШ ПЕЬЮЕЛ,
ОПНХГБНДХРЭ КХ ЯЙПЕЫХБЮМХЕ, Я ОНЛНЫЭЧ ТСМЙЖХХ random. еЯКХ АШ ЛШ ЛЕМЪКХ
ЦЕМШ ЯПЮГС ФЕ, ЙЮЙ ЩРН НОХЯЮМН БШЬЕ, МЮАНП ЦЕМНБ ю МЕ ЯНУПЮМХКЯЪ АШ Х
ОПНЖЕДСПЮ ПЮАНРЮКЮ АШ МЕЙНППЕЙРМН, ОНЩРНЛС ЦЕМШ, ОПЕДМЮГМЮВЕММШЕ ДКЪ
ГЮОХЯХ Б ╚ОЕПБСЧ╩ УПНЛНЯНЛС, ЛШ ОХЬЕЛ Б ОПНЛЕФСРНВМШИ ЛЮЯЯХБ prom, Ю
ОНЯКЕ ГЮБЕПЬЕМХЪ ЯЙЮМХПНБЮМХЪ ╚БРНПНИ╩ УПНЛНЯНЛШ ОЕПЕОХЯШБЮЕЛ ХГ prom Б
╚ОЕПБСЧ╩.
оЕПЕИДЕЛ Й ЯНГДЮМХЧ ОПНЖЕДСПШ ЛСРЮЖХХ. гДЕЯЭ, ЙЮЙ Х ОПХ
ЯЙПЕЫХБЮМХХ, БНГМХЙЮЧР ЯКНФМНЯРХ ХГ-ГЮ РНЦН, ВРН Б ЙЮФДНИ НЯНАХ ЙЮФДШИ
ЦНПНД ДНКФЕМ БЯРПЕВЮРЭЯЪ НДХМ, Х РНКЭЙН НДХМ ПЮГ, Ю ЕЯКХ ОПНХГБНКЭМН
ХГЛЕМХРЭ ЙЮЙНИ-РН ЦЕМ ЩРН СЯКНБХЕ МЮПСЬХРЯЪ. нДМЮЙН ОПЕНДНКЕРЭ ЩРС
ГЮЦБНГДЙС КЕЦЙН: АСДЕЛ ЛЕМЪРЭ ЛЕЯРЮЛХ ДБЮ ОПНХГБНКЭМШУ ЦЕМЮ Б УПНЛНЯНЛЕ!
щРНР НОЕПЮРНП ЯЮЛШИ ОПНЯРНИ Б МЮЬЕИ ОПНЦПЮЛЛЕ, ДСЛЮЧ, ВРН ПЮГНАПЮРЭЯЪ Я
КХЯРХМЦНЛ БЮЛ АСДЕР МЕ ЯКНФМН:

procedure mut;
var b:byte;//ОЕПЕЛЕММЮЪ, ВЕПЕГ ЙНРНПСЧ
//АСДЕЛ ОПНХГБНДХРЭ НАЛЕМ
begin
//ОЕПЕАХПЮЕЛ БЯЕУ НЯНАЕИ
for i:=1 to n_os do
//ПЕЬЮЕЛ, ОПНХГБНДХРЭ КХ ЛСРЮЖХЧ
if random(100) begin
//k-МНЛЕП ОЕПБНЦН ОПНХГБНКЭМНЦН ЦЕМЮ
k:=random(n_t)+1;
//j-МНЛЕП БРНПНЦН
j:=random(n_t)+1;
//НАЛЕМ
b:=osobi[i,k];
osobi[i,k]:=osobi[i,j];
osobi[i,j]:=b;
end;
end;

хРЮЙ, МЮЛ НЯРЮКНЯЭ МЮОХЯЮРЭ НЯМНБМСЧ ТСМЙЖХЧ ОПНЦПЮЛЛШ, Ю ОНЯКЕ
ОПНДЕКЮММНИ ПЮАНРШ ЩРН ОЮПЮ ОСЯРЪЙНБ:

begin
//ХМХЖХЮКХГХПСЕЛ ЯВЕРВХЙ ЯКСВЮИМШУ ВХЯЕК
randomize;
//ЦЕМЕПХПСЕЛ ЦНПНДЮ
gen_towns;
//ЦЕМЕПХПСЕЛ МЮВЮКЭМСЧ ОНОСКЪЖХЧ
gen_pop;
//ГЮОСЯЙЮЕЛ 5000 ОНЙНКЕМХИ
for n:=0 to 5000 do
begin
//ЯЕКЕЙЖХЪ
selection;
//ЙПНЯЯНБЕП
crossover;
//Х ЛСРЮЖХЪ
mut;
end;
read(c);
end.

мС ВРН Ф, бЮЬЮ ОЕПБЮЪ ОПНЦПЮЛЛЮ МЮ НЯМНБЕ цю ЯНГДЮМЮ, ОНГДПЮБКЪЧ!
рЕОЕПЭ ЛНФМН ЕЕ ОПНРЕЯРХПНБЮРЭ. гЮОСЯРХЛ ЕЕ МЕЯЙНКЭЙН ПЮГ Х ОПНЯКЕДХЛ ГЮ
БШДЮБЮЕЛШЛХ ПЕГСКЭРЮРЮЛХ.
бН-ОЕПБШУ, ГМЮВЕМХЕ МЮХЛЕМЭЬЕЦН ОСРХ Б ЯЮЛНЛ ОЕПБНЛ ОНЙНКЕМХХ
ЯХКЭМН НРКХВЮЕРЯЪ НР ЩРНЦН ФЕ ГМЮВЕМХЪ Б 250-Л. щРН ЕЫЕ ПЮГ ДНЙЮГШБЮЕР,
ЙЮЙ АШЯРПН ПЮАНРЮЧР цю.
бН- БРНПШУ, ЙНМЕВМШИ ПЕГСКЭРЮР БШДЮЕРЯЪ ВЕПЕГ ОЮПС ЯЕЙСМД.
оНОШРЮЕЛЯЪ НЖЕМХРЭ ЕЦН РНВМНЯРЭ. нАШВМН НМ КЕФХР Б ЦПЮМХЖЮУ НР 30 ДН 40,
ХМНЦДЮ БШУНДХР ХГ МХУ Б РС ХКХ ДПСЦСЧ ЯРНПНМС, Х ЩРН ОПХ РНЛ, ВРН
МЮХЛЕМЭЬЕЕ БНГЛНФМНЕ ГМЮВЕМХЕ ДКХМШ ОСРХ 19, Ю МЮХАНКЭЬЕЕ 190!!! дСЛЮЧ,
НВЕБХДМН, ВРН, ЕЯКХ НРБЕР МЕ РНВМШИ, РН СФ РНВМН АКХГНЙ Й МЕЛС. мЮ ЩРНЛ
ОПХЛЕПЕ ПЮАНРЮ цю ОПНЯРН ОНРПЪЯЮЕР!
мС Ю ВРНА НМЮ ОНРПЪЯЮКЮ ЕЫЕ АНКЭЬЕ, НЖЕМХЛ БПЕЛЪ, ГЮ ЙНРНПНЕ Я
ДЮММНИ ГЮДЮВЕИ ЯОПЮБХКЯЪ АШ РНВМШИ ЮКЦНПХРЛ ОЕПЕАНПЮ БЯЕУ БЮПХЮМРНБ.
оПЕДОНКНФХЛ, ВРН Б ЙНЛОЭЧРЕПЕ ЦХЦЮЦЕПЖНБШИ ОПНЖЕЯЯНП, ЙНРНПШИ ОПНБНДХР
МЕНАУНДХЛШЕ БШВХЯКЕМХЪ ДКЪ ЙЮФДНЦН БЮПХЮМРЮ ГЮ 1 РЮЙР (МЕ ЯКЮАЮЪ
ЮАЯРПЮЙЖХЪ). бЯЕЦН БЮПХЮМРНБ 20! БЮПХЮМРНБ, ГМЮВХР ЯСОЕПОПНЖЕЯЯНПС
ОНМЮДНАХРЯЪ 20!/1.000.000.000 ЯЕЙСМД, Ю ВРНАШ ОЕПЕБЕЯРХ БПЕЛЪ Б ЦНДЮ
МСФМН ВХЯКН ЯЕЙСМД ПЮГДЕКХРЭ МЮ (60*60*24*365). гЮОСЯЙЮЕЛ MS йЮКЭЙСКЪРНП
Х ОНКСВЮЕЛ ОПХЛЕПМН 77 КЕР. дСЛЮЧ, ЙНЛЛЕМРЮПХХ ХГКХЬМХ.

яМНБЮ РЕНПХЪ

б ЩРНИ ЦКЮБЕ ЮБРНП ОНОШРЮЕРЯЪ БЙПЮРЖЕ НРБЕРХРЭ МЮ БНОПНЯ ╚ю ОНВЕЛС
ЩРН ПЮАНРЮЕР?╩ рЕ, ЙРН МЕ НВЕМЭ КЧАХР ВХЯРСЧ ЛЮРЕЛЮРХЙС, ЛНЦСР ЯПЮГС
ОЕПЕУНДХРЭ Й ПЕЙНЛЕМДЮЖХЪЛ ОН ХЯОНКЭГНБЮМХЧ.
нДМХЛ ХГ АЮГНБШУ ОНМЪРХИ РЕНПХХ цю ЪБКЪЕРЯЪ ЬХЛЮ (schema). ьХЛЮ -
ЩРН ЬЮАКНМ ДКЪ УПНЛНЯНЛ, НР ЙНРНПШУ НМЮ НРКХВЮЕРЯЪ КХЬЭ РЕЛ, ВРН Б ЕЕ
КНЙСЯЮУ (ОНГХЖХЪУ, ЕЯКХ ЙРН МЕ ОНЛМХР) ЛНЦСР ЯРНЪРЭ МЕ РНКЭЙН ЦЕМШ, МН Х
*-ЙХ (МЕНОПЕДЕКЕММШЕ ЦЕМШ). еЯКХ Б ЙЮВЕЯРБЕ ОПХЛЕПЮ УПНЛНЯНЛ
ПЮЯЯЛЮРПХБЮРЭ АХРНБШЕ ЯРПНЙХ ДКХМШ 5, РН ЬХЛШ ЛНЦСР АШРЭ РЮЙХЛХ: **10*1,
**110, 1***0 Х РЮЙ ДЮКЕЕ.
с ЙЮФДНИ ЬХЛШ ЕЯРЭ ДБЮ БЮФМШУ ОЮПЮЛЕРПЮ: ОНПЪДНЙ Х НОПЕДЕКЕММЮЪ
ДКХМЮ. оНПЪДНЙ - ЩРН ЙНКХВЕЯРБН НОПЕДЕКЕММШУ ЦЕМНБ Б ЬХЛЕ, Ю НОПЕДЕКЕММЮЪ
ДКХМЮ - ПЮЯЯРНЪМХЕ ЛЕФДС ЙПЮИМХЛХ ГМЮВЮЫХЛХ ЦЕМЮЛХ. мЮОПХЛЕП, ЬХЛЮ *1*00
ХЛЕЕР ОНПЪДНЙ 3 Х НОПЕДЕКЕММСЧ ДКХМС 4.
╚мС Х ГЮВЕЛ МСФМШ ЩРХ ЬХЛШ?╩ - ЯОПНЯХРЕ бШ. ю ГЮРЕЛ, ВРН цю
НАПЮАЮРШБЮЧР БНБЯЕ МЕ УПНЛНЯНЛШ, Ю ЬХЛШ - МЕЪБМН, Х ХЛЕММН Б ЩРН ЙПНЕРЯЪ
ЯЕЙПЕР ПЮАНРШ цю. хГ ОНЙНКЕМХЪ Б ОНЙНКЕМХЕ ОЕПЕУНДЪР РНКЭЙН КСВЬХЕ ЬХЛШ,
ЙНРНПШЕ МЮГШБЮЧР ЯРПНЪЫХЛХ АКНЙЮЛХ.
яРПНЪЫХЕ АКНЙХ - ЩРН ЬХЛШ, НАКЮДЮЧЫХЕ РПЕЛЪ ОПХГМЮЙЮЛХ:
1. бШЯНЙЮЪ ОПХЯОНЯНАКЕММНЯРЭ (БШВХЯКЪЕРЯЪ ЙЮЙ ЯПЕДМЕЕ ОПХЯОНЯНАКЕММНЯРЕИ
ГЮДЮБЮЕЛШУ ЬХЛНИ УПНЛНЯНЛ)
2. мХГЙХИ ОНПЪДНЙ
3. йНПНРЙЮЪ НОПЕДЕКЕММЮЪ ДКХМЮ
оЕПБШИ ОПХГМЮЙ ОНГБНКЪЕР ОПНИРХ ЯЕКЕЙЖХЧ (ВЕЛ БШЬЕ
ОПХЯОНЯНАКЕММНЯРЭ, РЕЛ АНКЭЬЕ ЬЮМЯШ БШФХРЭ), БРНПНИ - ЛСРЮЖХЧ (ЛЕМЭЬЕ
ГМЮВЮЫХУ ЦЕМНБ - ЛЕМЭЬЕ БЕПНЪРМНЯРЭ ХУ ХГЛЕМЕМХЪ), РПЕРХИ - ЙПНЯЯНБЕП
(ЛЕМЭЬЕ НОПЕДЕКЕММЮЪ ДКХМЮ - ЛЕМЭЬЕ БЕПНЪРМНЯРЭ РНЦН, ВРН РНВЙЮ ПЮГПШБЮ
ОНОЮДЕР ЛЕФДС ГМЮВЮЫХЛХ ЦЕМЮЛХ Х СМХВРНФХР ЬХЛС).
пЮЯЯЛНРПХЛ ОПНЯРНИ цю, НМ БШОНКМЪЕР ЯЕКЕЙЖХЧ ОПНОНПЖХНМЮКЭМН
ОПХЯОНЯНАКЕММНЯРХ, ЯЙПЕЫХБЮМХЕ НДМНРНВЕВМШЛ ЙПНЯЯНБЕПНЛ Х ЛСРЮЖХЧ
ЯКСВЮИМШЛ ХГЛЕМЕМХЕЛ ЯКСВЮИМНЦН ЦЕМЮ. дКЪ РЮЙНЦН цю ЯОПЮБЕДКХБН
СРБЕПФДЕМХЕ: НМ ЩЙЯОНМЕМЖХЮКЭМН СБЕКХВХБЮЕР ВХЯКН ЯРПНЪЫХУ АКНЙНБ.
дНЙЮГЮРЕКЭЯРБНЛ ЩРНЦН ЪБКЪЕРЯЪ РЕНПЕЛЮ ЬХЛ.
оСЯРЭ ЬХЛЮ X ХЛЕЕР Б k-Л ОНЙНКЕМХХ n(X,k) ОПЕДЯРЮБХРЕКЕИ ХКХ
ОПХЛЕПНБ. мСФМН НЖЕМХРЭ ГМЮВЕМХЕ n(X,k+1). рЮЙ ЙЮЙ С ОПНЯРНЦН цю
БЕПНЪРМНЯРЭ БШФХБЮМХЪ НЯНАХ ОПНОНПЖХНМЮКЭМЮ ЕЕ ОПХЯОНЯНАКЕММНЯРХ, РН
НФХДЮЕЛНЕ ВХЯКН ОПЕДЯРЮБХРЕКЕИ X ОНЯКЕ ЯЕКЕЙЖХХ
n(X,k)*(prisp(X)/prispЯП), ЦДЕ prispЯП - ЯПЕДМЪЪ ОПХЯОНЯНАКЕММНЯРЭ БЯЕУ
ВКЕМНБ ОНОСКЪЖХХ, Ю prisp(X) - РЕУ, ВРН ЪБКЪЧРЯЪ ОПЕДЯРЮБХРЕКЪЛХ X.
бЕПНЪРМНЯРЭ СЯОЕЬМНЦН ОПНУНДЮ ВЕПЕГ ЙПНЯЯНБЕП МЕ ЛЕМЭЬЕ, ВЕЛ
БЕПНЪРМНЯРЭ РНЦН, ВРН РНВЙЮ ПЮГПШБЮ ОНОЮДЕР ЛЕФДС ГМЮВЮЫХЛХ ЦЕМЮЛХ, РН
ЕЯРЭ 1-v_cross*(d(X)/(l-1)), ЦДЕ d(X) - НОПЕДЕКЕММЮЪ ДКХМЮ ЬХЛШ, Ю l -
ДКХМЮ УПНЛНЯНЛШ. ╚мЕ ЛЕМЭЬЕ╩ ГДЕЯЭ ОНРНЛС, ВРН Б ЯЙПЕЫХБЮМХХ ЛНЦСР
СВЮЯРБНБЮРЭ ДБЮ ОПХЛЕПЮ НДМНИ ЬХЛШ, Х РНЦДЮ НМЮ ЯНУПЮМХРЯЪ. б ОНГДМХУ
ОНЙНКЕМХЪУ, ЙЯРЮРХ, РЮЙ ОПНХЯУНДХР ДНБНКЭМН ВЮЯРН.
бЕПНЪРМНЯРЭ РНЦН, ВРН ЛСРЮЖХЪ МЕ ХГЛЕМХР ГМЮВЮЫЕЦН ЦЕМЮ (1-
v_mut)p(X), p(X) - ОНПЪДНЙ ЬХЛШ. рНЦДЮ БЕПНЪРМНЯРЭ ЯНУПЮМЕМХЪ ЬХЛШ ОНЯКЕ
ОПНУНДЮ ЕЕ ОПЕДЯРЮБХРЕКЪ ВЕПЕГ ЯЙПЕЫХБЮМХЕ Х ЛСРЮЖХЧ МЕ ЛЕМЭЬЕ (1-
v_cross*(d(X)/(l-1)))* (1-v_mut)p(X),МН РЮЙ ЙЮЙ p(X) Х v_mut ЛЮКШ, РН ЩРН
ОПХАКХФЕММН 1-v_cross*(d(X)/(l-1))-v_mut*p(X), Х РНЦДЮ ДКЪ n(X,k+1)
ОНКСВХЛ:
n(X,k+1)≥n(X,k)*(prisp(X)/prispЯП)*(1-v_cross*(d(X)/(l-1))-
v_mut*p(X)))
щРН СРБЕПФДЕМХЕ Х МЮГШБЮЧР РЕНПЕЛНИ ЬХЛ.
щРН РЕНПЕЛЮ ДНБНКЭМН ОПНЯРЮ, НДМЮЙН, МЕ ЯЛНРПЪ МЮ ЩРН, НМЮ ДЮЕР
ОНМЪРХЕ Н РНЛ, ЙЮЙ ПЮАНРЮЕР ОПНЯРНИ цю, ДЮ Х ОПНЯРН цю. хГ ТНПЛСКШ БХДМН,
ВРН ВХЯКН ОПХЛЕПНБ ЯРПНЪЫХУ АКНЙНБ ПЮЯРЕР ХГ ОНЙНКЕМХЪ Б ОНЙНКЕМХЕ ОН
ЩЙЯОНМЕМРЕ, Б РН БПЕЛЪ ЙЮЙ ВХЯКН ОПЕДЯРЮБХРЕКЕИ ╚АЕЯОНКЕГМШУ╩ ЬХЛ САШБЮЕР
ОН ЩЙЯОНМЕМРЕ.
хГ ЯЙЮГЮММНЦН Б ЩРНИ ЦКЮБЕ ЛНФМН ЯДЕКЮРЭ БЮФМШИ ОПЮЙРХВЕЯЙХИ БШБНД:
ЕЯКХ СБЕКХВХРЭ v_cross Х v_ mut, РН ОНОСКЪЖХЪ АШЯРПЕЕ ЯНИДЕРЯЪ Й
ПЕГСКЭРЮРС, МН МЕ БЯЕ ЯРПНЪЫХЕ АКНЙХ АСДСР ХЯОНКЭГНБЮМШ, ОНЩРНЛС
ПЕГСКЭРЮР ЛНФЕР НЙЮГЮРЭЯЪ КХЬЭ КНЙЮКЭМШЛ ЩЙЯРПЕЛСЛНЛ. еЯКХ ФЕ СЛЕМЭЬХРЭ
v_cross Х v_ mut, РН ПЕГСКЭРЮР АСДЕР ХЯЙЮРЭЯЪ ЛЕДКЕММЕЕ, МН АСДЕР АНКЕЕ
АКХГНЙ Й РНВМНЛС.

пЕЙНЛЕМДЮЖХХ ОН ХЯОНКЭГНБЮМХЧ

цю ОНЙЮГШБЮЧР ЯЕАЪ Я КСВЬЕИ ЯРНПНМШ ОПХ ПЕЬЕМХХ ДЮКЕЙН МЕ БЯЕУ
ГЮДЮВ, Х Б ЩРНИ ЦКЮБЕ ОНИДЕР ПЕВЭ Н РНЛ, ЙНЦДЮ ФЕ ЯКЕДСЕР ОПХЛЕМЪРЭ цю.
вЕРЙХИ НРБЕР МЮ ЩРНР БНОПНЯ МЕ МЮИДЕМ, ДЮ Х БПЪД КХ ЛНФЕР АШРЭ МЮИДЕМ,
БЕДЭ ГЮДЮВХ ЯРНКЭ ПЮГМННАПЮГМШ, ОНЩРНЛС ГДЕЯЭ АСДСР ОПХБЕДЕМШ КХЬЭ НАЫХЕ
ПЕЙНЛЕМДЮЖХХ.
мЮХАНКЭЬЕЕ ОПХЛЕМЕМХЕ цю МЮЬКХ Б ГЮДЮВЮУ НОРХЛХГЮЖХХ
ЛМНЦНОЮПЮЛЕРПХВЕЯЙХУ ТСМЙЖХИ, ЛМНФЕЯРБН ПЕЬЕМХИ ЙНРНПШУ ЯРНКЭ БЕКХЙН, ВРН
ЕЦН МЕКЭГЪ ОЕПЕАПЮРЭ. дКЪ ЩРНЦН ЯКСВЮЪ ЛНФМН ЯДЕКЮРЭ ПЕЬЕМХЕ
СМХБЕПЯЮКЭМШЛ Х ОНКСВЕММШИ ЮКЦНПХРЛ ЯЛНФЕР Я НДХМЮЙНБШЛ СЯОЕУНЛ ПЕЬЮРЭ
ВХЯРН ЛЮРЕЛЮРХВЕЯЙХЕ ГЮДЮВХ Х ОПНЕЙРХПНБЮРЭ ФЕКЕГМНДНПНФМШИ ЛНЯР! рЮЙФЕ
ГДЕЯЭ ХЯОНКЭГСЕРЯЪ РН, ВРН цю НОРХЛХГХПСЕР ЯПЮГС БЯЕ ОЮПЮЛЕРПШ, Ю МЕ ОН
НРДЕКЭМНЯРХ.
рЮЙ ЙЮЙ цю ПЮАНРЮЧР Я ОНОСКЪЖХЕИ ПЕЬЕМХИ, Ю МЕ Я НДМХЛ Б ЙЮФДШИ
ЛНЛЕМР, РН НМХ ХЛЕЧР ЛЕМЭЬЕ ЬЮМЯНБ ЯНИРХЯЭ МЮ КНЙЮКЭМНЛ ЩЙЯРПЕЛСЛЕ Х
БШДЮРЭ ЕЦН Б ЙЮВЕЯРБЕ НРБЕРЮ. оНЩРНЛС ЕЯКХ ТСМЙЖХЪ ОПХЯОНЯНАКЕММНЯРХ Я
ЬСЛЮЛХ, РН цю - НДХМ ХГ ЯЮЛШУ НОРХЛЮКЭМШУ ЛЕРНДНБ ПЕЬЕМХЪ ГЮДЮВХ.
мС Ю РЕОЕПЭ Н ЦПСЯРМНЛ - Н РНЛ, ЙНЦДЮ цю ПЮАНРЮЧР МЕ НВЕМЭ
ЩТТЕЙРХБМН. еЯКХ ОПНЯРПЮМЯРБН ОНХЯЙЮ МЕ НВЕМЭ АНКЭЬНЕ, ЕЦН КСВЬЕ
ОЕПЕАПЮРЭ, ДЮФЕ ЕЯКХ МЮ ЩРН ОНРПЕАСЕРЯЪ МЕЯЙНКЭЙН АНКЭЬЕЕ БПЕЛЪ, ВЕЛ МЮ
БШОНКМЕМХЕ цю, ГЮРН БШ АСДЕРЕ МЮ ЯРН ОПНЖЕМРНБ ГМЮРЭ, ВРН МЮИДЕММНЕ
ПЕЬЕМХЕ ЮАЯНКЧРМН РНВМНЕ.
еЯКХ ЯСЫЕЯРБСЕР ЙЮЙНИ-РН ЯОЕЖХЮКЭМШИ ДКЪ ДЮММНИ ГЮДЮВХ ЛЕРНД,
СВХРШБЮЧЫХИ ЯОЕЖХТХВЕЯЙХЕ ЯБНИЯРБЮ ОПНЯРПЮМЯРБЮ ОНХЯЙЮ, РН НМ ОНВРХ
МЮБЕПМЪЙЮ АСДЕР ПЮАНРЮРЭ КСВЬЕ, ВЕЛ цю. оНЩРНЛС ОПХДЕРЯЪ КХАН ЯНБЯЕЛ
НРЙЮГЮРЭЯЪ НР ОПХЛЕМЕМХЪ цю, КХАН ╚ЯЙПЕЯРХРЭ╩ ЕЦН ЯН ЯОЕЖХЮКЭМШЛ ЛЕРНДНЛ,
ВРН ЛШ, ЙЯРЮРХ, Х ЯДЕКЮКХ ОПХ ПЕЬЕМХХ ГЮДЮВХ-ОПХЛЕПЮ Й ЯРЮРЭЕ. бПЪД КХ
МЮЬЮ ОПНЦПЮЛЛЮ ОНЙЮГШБЮКЮ АШ РЮЙХЕ ПЕГСКЭРЮРШ, ЕЯКХ АШ МЕ СВХРШБЮКЮ РНР
ТЮЙР, ВРН ЙЮФДШИ ЦНПНД Б ОСРХ ЙНЛЛХБНЪФЕПЮ ДНКФЕМ БЯРПЕВЮРЭЯЪ ПНБМН НДХМ
ПЮГ.
йНМЕВМН, ЯЙЮГЮММНЕ БШЬЕ МЕ ЪБКЪЕРЯЪ ЯРПНЦХЛ ОПЮБХКНЛ, МН, БНГЛНФМН,
ЩРН НДМЮФДШ ОНДЯЙЮФЕР бЮЛ: ╚гДЕЯЭ МСФМН ОПХЛЕМХРЭ цю!╩, Х, НДМНБПЕЛЕММН,
МЕ ОНГБНКХР ╚ЯНБЮРЭ ХУ БН БЯЕ ДШПЙХ╩. еЯКХ бШ ГЮХМРЕПЕЯНБЮКХЯЭ ЩРНИ
РЕЛНИ, ОНЯЕРХРЕ ЯКЕДСЧЫХЕ ЯЯШКЙХ:

1. http://www.chat.ru/~saisa - НДХМ ХГ КСВЬХУ ПСЯЯЙХУ ПЕЯСПЯНБ Н цю.
еЯРЭ ЯЕПЭЕГМШЕ МЮСВМШЕ ЯРЮРЭХ. лМНФЕЯРБН ЯЯШКНЙ, ОПЮБДЮ, МЮ
ЮМЦКНЪГШВМШЕ ЯЮИРШ.
2. http://www.genetic-programming.org - ОНФЮКСИ, ЯЮЛШИ ХГБЕЯРМШИ Б
ЛХПЕ ПЕЯСПЯ ОН цю Х ХЛ ОНДНАМШЛ. лНПЕ ХМТНПЛЮЖХХ, МН, ЙНМЕВМН, БЯЕ
МЮ ЮМЦКХИЯЙНЛ.

-----------------------
пХЯ.1

лСРЮЖХЪ

яЙПЕЫХБЮМХЕ

яЕКЕЙЖХЪ

сЯКНБХЕ ЙНМЖЮ НРАНПЮ

яНГДЮМХЕ ОНОСКЪЖХХ

дЮ

мЕР

йНМЕЖ цю

мЮВЮКН цю

1 1 0 0 0 0 1 1

1 0 0 0 1 0 0 1

1 1 0 0 1 0 0 1

дЕРХ

пНДХРЕКХ

1 0 0 0 0 0 1 1

йПНЯЯНБЕП

рНВЙЮ ПЮГПШБЮ

пХЯ.2

оПХЯО. 1-И НЯНАХ

2-И НЯНАХ

3-И НЯНАХ

(n+1)-И НЯНАХ

.

пЮГАХБЙЮ prisp

Prisp[0]

Prisp[1]

Prisp[1]

Prisp[n]

Prisp[n+1]

еЯКХ j ОНОЮКН ЯЧДЮ, БШАПЮМЮ 3-Ъ НЯНАЭ

пХЯ.3

1 2 3 4 5 6 7

6 3 5 1 4 7 2

рНВЙЮ ПЮГПШБЮ

мЮАНП ю

яОЕЖйПНЯЯНБЕП

3 1 2 4 5 6 7

6 1 5 2 4 7 3

пХЯ.3