Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов

Рассмотрена задача выбора наилучшего элемента для случая, когда элементы разбиты на группы и за один шаг осуществляется одновременный просмотр элементов всей группы. Вначале доказывается две леммы относительно вида оптимального порядка просмотра групп, позволяющие понять структуру оптимального решен...

Full description

Saved in:

Bibliographic Details
Date:	2014
Main Authors:	Доценко, С.И., Негадайлов, П.А.
Format:	Article
Language:	Russian
Published:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України 2014
Series:	Кибернетика и вычислительная техника
Subjects:	Сложные системы управления
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/84503
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:	Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов / С.И. Доценко, П.А. Негадайлов // Кибернетика и вычислительная техника. — 2014. — Вип. 175. — С. 31-39. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-84503
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-845032025-02-23T18:58:45Z Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов Про оптимальний порядок проглядання груп в задачі выбору найкращого елементу з груповим прогляданням кандидатів On optimal search order in the group secretary problem Доценко, С.И. Негадайлов, П.А. Сложные системы управления Рассмотрена задача выбора наилучшего элемента для случая, когда элементы разбиты на группы и за один шаг осуществляется одновременный просмотр элементов всей группы. Вначале доказывается две леммы относительно вида оптимального порядка просмотра групп, позволяющие понять структуру оптимального решения. Затем, в рамках найденной структуры, строится генетический алгоритм, приближенно находящий оптимальное решение. Розглянуто задачу оптимального вибору у випадку, коли елементи розбито на групи та за один крок здійснюється одночасний перегляд елементів групи. Спочатку доведено дві леми, щодо оптимального порядку перегляду груп, які дозволяють зрозуміти структуру оптимального розв’язку. Потім, з урахуванням знайденої структури, знайдено генетичний алгоритм, що знаходить оптимальний розв’язок. Purpose: We try to find the best order of viewing groups which maximize the probability of selecting the best candidate, provided that optimal stopping rule, based on the “Bruce’s theorem” is applied and we compare this probability for the best and the worst cases. As may be expected, the lower bound for the worst case is the probability to find the best element at the classical secretary problem, i.e. 1/e. 2014 Article Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов / С.И. Доценко, П.А. Негадайлов // Кибернетика и вычислительная техника. — 2014. — Вип. 175. — С. 31-39. — Бібліогр.: 4 назв. — рос. 0452-9910 https://nasplib.isofts.kiev.ua/handle/123456789/84503 519.83 ru Кибернетика и вычислительная техника application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Сложные системы управления Сложные системы управления
spellingShingle	Сложные системы управления Сложные системы управления Доценко, С.И. Негадайлов, П.А. Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов Кибернетика и вычислительная техника
description	Рассмотрена задача выбора наилучшего элемента для случая, когда элементы разбиты на группы и за один шаг осуществляется одновременный просмотр элементов всей группы. Вначале доказывается две леммы относительно вида оптимального порядка просмотра групп, позволяющие понять структуру оптимального решения. Затем, в рамках найденной структуры, строится генетический алгоритм, приближенно находящий оптимальное решение.
format	Article
author	Доценко, С.И. Негадайлов, П.А.
author_facet	Доценко, С.И. Негадайлов, П.А.
author_sort	Доценко, С.И.
title	Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов
title_short	Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов
title_full	Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов
title_fullStr	Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов
title_full_unstemmed	Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов
title_sort	об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України
publishDate	2014
topic_facet	Сложные системы управления
url	https://nasplib.isofts.kiev.ua/handle/123456789/84503
citation_txt	Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов / С.И. Доценко, П.А. Негадайлов // Кибернетика и вычислительная техника. — 2014. — Вип. 175. — С. 31-39. — Бібліогр.: 4 назв. — рос.
series	Кибернетика и вычислительная техника
work_keys_str_mv	AT docenkosi oboptimalʹnomporâdkeprosmotragruppvzadačevyboranailučšegoélementasgruppovymprosmotromkandidatov AT negadajlovpa oboptimalʹnomporâdkeprosmotragruppvzadačevyboranailučšegoélementasgruppovymprosmotromkandidatov AT docenkosi prooptimalʹnijporâdokproglâdannâgrupvzadačívyborunajkraŝogoelementuzgrupovimproglâdannâmkandidatív AT negadajlovpa prooptimalʹnijporâdokproglâdannâgrupvzadačívyborunajkraŝogoelementuzgrupovimproglâdannâmkandidatív AT docenkosi onoptimalsearchorderinthegroupsecretaryproblem AT negadajlovpa onoptimalsearchorderinthegroupsecretaryproblem
first_indexed	2025-11-24T14:21:11Z
last_indexed	2025-11-24T14:21:11Z
_version_	1849681847266574336
fulltext	31 Сложные системы управления УДК 519.83 ОБ ОПТИМАЛЬНОМ ПОРЯДКЕ ПРОСМОТРА ГРУПП В ЗАДАЧЕ ВЫБОРА НАИЛУЧШЕГО ЭЛЕМЕНТА С ГРУППОВЫМ ПРОСМОТРОМ КАНДИДАТОВ С.И. Доценко, П.А. Негадайлов Киевский Национальный Университет имени Тараса Шевченко Рассмотрена задача выбора наилучшего элемента для случая, когда элементы разбиты на группы и за один шаг осуществляется одновременный просмотр элементов всей группы. Вначале доказывается две леммы относительно вида оптимального порядка просмотра групп, позволяющие понять структуру оптимального решения. Затем, в рамках найденной структуры, строится генетический алгоритм, приближенно находящий оптимальное решение. Розглянуто задачу оптимального вибору у випадку, коли елементи розбито на групи та за один крок здійснюється одночасний перегляд елементів групи. Спочатку доведено дві леми, щодо оптимального порядку перегляду груп, які дозволяють зрозуміти структуру оптимального розв’язку. Потім, з урахуванням знайденої структури, знайдено генетичний алгоритм, що знаходить оптимальний розв’язок. ВВЕДЕНИЕ Задача оптимального выбора (известная также как задача секретаря) является одной из классических задач теории вероятностей и служит иллюстративным примером таких разделов математики, как оптимальная остановка марковских процессов, динамическое программирование, принятие решения в условиях риска или неопределенности. Наиболее известный и простой случай задачи (называемый классическим) состоит в следующем. Пусть есть n объектов, упорядоченных по качеству. Пусть некто знакомится с данными объектами в случайном порядке (т.е. это означает, что все n! перестановок объектов, задающих порядок, в котором они могут встретиться просматривающему, равновероятны). При просмотре каждого из объектов нужно принять решение: остановить просмотр на данном объекте в надежде, что он окажется наилучшим среди всех, либо отвергнуть его и продолжить просмотр. Возвращаться к ранее просмотренным (и отвергнутым) объектам нельзя. Целью данной статьи является обобщение процедуры просмотра в случае, когда объекты разбиты на группы различной численности и осуществляется одновременный просмотр всех объектов группы. В [1] было рассмотрено обобщение задачи оптимального выбора на случай, когда объекты разбиты на группы и осуществляется одновременный  С.И. Доценко, П.А. Негадайлов, 2014 ISSN 0452-9910. Кибернетика и вычисл. техника. 2014. Вып. 175 32 просмотр кандидатов в каждой группе. После просмотра кандидатов группы аналогично классической задаче в случае, если в группе присутствует наилучший кандидат среди всех ранее просмотренных элементов (такой элемент принято называть максимальным) нужно принять решение: выбрать этого кандидата и закончить просмотр либо же отвергнуть его и продолжить просмотр; возвращаться к ранее отвергнутым кандидатам нельзя. В этом случае оптимальное правило выбора наилучшего кандидата базируется на так называемой теореме шансов (или теореме Брюса), рассмотренной в [2]. Возникает естественный вопрос: в каком порядке следует осуществлять просмотр групп, чтобы максимизировать вероятность выбора наилучшего кандидата. ПОСТАНОВКА ЗАДАЧИ ГРУППОВОГО ПРОСМОТРА Пусть выбираемые объекты разбиты на группы численностью mxxx ...,,, 21 и пусть порядок просмотра групп фиксирован. Оказывается, что просмотр нужно остановить в случае, если в очередной просматриваемой группе, начиная с некоторого номера k, будет выявлен максимальный элемент. При этом индекс k, согласно [1], определяется следующим образом. Пусть i i i xx xp ++ = ...1 , ii pq −= 1 , i i i q pr = , тогда 2, ... 11 ≥ ++ = − i xx xr i i i , +∞=1r , ( )1...\|max ≥++= ni rrik . (1) Принципиальным моментом, позволяющим применить теорему Брюса к задаче выбора наилучшего элемента с групповым просмотром кандидатов является то, что независимо от появления максимальных элементов при просмотре предыдущих групп, вероятность того, что максимальный элемент будет обнаружен в очередной просматриваемой i-й группе равна ip . При этом вероятность нахождения наилучшего элемента выражается следующим образом: m m kj j m kj j xx xpVkrqkV ++ ==≥= ∑∏ == ... )1(;2,)( 1 1 1 . (2) Однако в данной постановке задачи предполагается, что порядок просмотра групп фиксирован. Целью данной статьи является нахождение оптимального порядка просмотра групп в случае, когда можно варьировать данный порядок. Забегая вперед, отметим, что в точности найти оптимальный порядок просмотра не удается. Однако применение теорем, доказанных ниже, позволяет существенно сузить количество перестановок, задающих порядок просмотра групп, среди которых может быть оптимальный (а именно с множества m! всех перестановок до 12 −m «перспективных»).  С.И. Доценко, П.А. Негадайлов, 2014 ISSN 0452-9910. Кибернетика и вычисл. техника. 2014. Вып. 175 33 ОСНОВНЫЕ РЕЗУЛЬТАТЫ Рассмотрим некоторые частные случаи: 1) 2=m . Пусть 21 xx ≤ . Тогда порядок просмотра групп не имеет значения и оптимальным алгоритмом является остановка на максимальном элементе из большей группы, при этом 21 2 xx xV + = . 2) 3=m . Пусть 321 xxx ≤≤ . Зафиксируем некоторый порядок просмотра и обозначим {1}, {2}, {3} номера работ в исходной нумерации, которые просматриваются 1-й, 2-й и 3-й соответственно при данном порядке просмотра. Обозначим через 321 ,, VVV вероятности нахождения наилучшего элемента при условии, что при просмотре соблюдается пороговая стратегия, начиная с 1-й, 2-й либо 3-й группы соответственно. Тогда }3{}2{}1{ }1{ 1 xxx x V ++ = ; ( ) ( )( ); }3{}2{}1{}2{}1{ }3{}1{ }3{}2{}1{ }2{ }2{}3{}2{}3{2 xxxxx xx xxx x rrqqV +++ + ++ =+= }3{}2{}1{ }3{ }3{}3{3 xxx x rqV ++ == . Тогда         + + ++ == }3{ }2{}1{ }3{}1{ }2{}1{ }3{}2{}1{ 321 ,,max1),,max( x xx xx xx xxx VVVV . Предположим, что }3{}1{ xx ≤ . При данном предположении первый и третий члены, стоящие под знаком максимума, могут поменяться местами, а второй член не уменьшится. Таким образом, весь максимум не уменьшится и его можно будет представить в виде         + +=′ }3{ }2{}1{ }3{}1{ }2{ ,max x xx xx xV . Рассмотрим альтернативный порядок просмотра групп. Поменяем местами вторую и третью группы, тогда выражение для максимума приобретает вид         + +=′′ }2{ }3{}1{ }2{}1{ }3{ ,max x xx xx xV . Сравнение }3{}1{ }2{}1{ }3{ }2{}1{ }3{}1{ }2{ xx xx x xx xx x + +∨ + + после элементарных преобразований сводится к сравнению }3{}2{ xx ∨ .  С.И. Доценко, П.А. Негадайлов, 2014 ISSN 0452-9910. Кибернетика и вычисл. техника. 2014. Вып. 175 34 Таким образом, если ,}3{}2{ xx ≥ то VV ′′≥′ , что свидетельствует о том, что порядок просмотра групп, при котором }1{}3{}2{ xxx ≥≥ (т.е. маленькая, большая, средняя) не хуже всех остальных. Рассуждая аналогичным образом, легко показать, что наихудшим порядком просмотра групп является большая, маленькая, средняя. Далее, докажем две леммы, позволяющие понять структуру оптимального порядка просмотра групп для произвольного m. Лемма 1. Пусть задан некоторый порядок просмотра групп }{...,},2{},1{ m и согласно оптимальному алгоритму, нужно придерживаться пороговой стратегии, начиная с номера k, и пусть, начиная с этого номера группы расположены, в любом порядке, отличном от порядка убывания численности. Тогда такой порядок не является оптимальным. Доказательство. Пусть реализуется пороговая стратегия, начиная с k-й группы. Тогда, согласно формуле полной вероятности, вероятность того, что в группах k, …, j – 1 не было максимальных элементов, а в группе j он появился (и согласно пороговой стратегии на нем была сделана остановка) и этот элемент к тому же оказался наилучшим, равна 111 11 1 1 111 11 ...... ... ... ... ...... ... − − − − ++ ⋅ ++ ++ = ++ ++ ⋅ ++ ⋅ ++ ++ j j m k m j j j j k xx x xx xx xx xx xx x xx xx . Суммируя по j от k до m, получим оптимальное значение вероятности нахождения наилучшего элемента при данном порядке просмотра: ∑ = − − ++++ ++ =′ m kj j j m k xx x xx xxkV 111 11 ...... ...)( . Поскольку, согласно предположению леммы, порядок численностей групп отличен от убывающего, среди групп k, …, m найдутся две соседние группы, такие, что 1+< ii xx . Поменяем эти две группы местами, остальные группы оставим на месте и выпишем значение )(kV ′′ для альтернативного порядка просмотра. Очевидно, в выражениях )(kV ′ и )(kV ′′ одинаковые множители перед знаком суммы, а под знаком суммы меняется вид только слагаемых с индексами i и (i + 1). Обозначим сумму этих двух слагаемых в первом и во втором случаях через S ′ и S ′′ соответственно. Обозначим 11 ... −++=σ ixx , тогда i ii x xxS +σ + σ =′ +1 , 1 1 + + +σ + σ =′′ i ii x xxS . После элементарных преобразований имеем 0 ))(( )( 1 11 < +σ+σσ − =′′−′ + ++ ii iiii xx xxxxSS . Значит это свидетельствует о том, что порядок просмотра групп не является оптимальным.  С.И. Доценко, П.А. Негадайлов, 2014 ISSN 0452-9910. Кибернетика и вычисл. техника. 2014. Вып. 175 35 Таким образом, группы, на которых следует делать остановку в случае появления в них максимального элемента, должны следовать в убывающем (точнее, невозрастающем) порядке численности элементов. Лемма 2. Последовательность групп, на которых следует делать остановку в случае появления в них максимального элемента, должна начинаться с группы, численность которой наибольшая среди всех групп (а если таких групп несколько, то с одной из них). Доказательство. Пусть установлен оптимальный алгоритм просмотра групп mkk xxxx ...,,,...,, 11 − и пусть алгоритм Брюса предписывает останавливаться на максимальном элементе, начиная с k-й группы. Если установлен оптимальный порядок просмотра групп, то, согласно лемме 1 должно выполняться условие mkk xxx ≥≥≥ + ...1 . Обозначим через V(k) вероятность нахождения наилучшего элемента при условии, что просмотр начат с k-й группы. Пусть ),...,max( 1 mk xxx ≠ , тогда среди групп 1...,,1 −k найдется группа i такая, что ki xx > . Переупорядочим группы 1...,,1 −k так, чтобы эта группа оказалась на )1( −k -м месте. Это не повлияет на вычисление V(k) и прочих V(j) при j > k, поскольку не имеет значения порядок следования пропускаемых групп, имеет значение только их общая численность 11 ... −++ kxx . После переупорядочения kk xx >−1 . Поскольку алгоритм Брюса предписывает начать просмотр именно с k-й группы, то 1≥∑ = m kj jr , но 1 1 <∑ += m kj jr . Покажем, что условие )1()( +> kVkV равносильно условию 1 1 <∑ += n kj jr . Действительно, пусть )1()( +> kVkV . Тогда, согласно (1) ∑∏∑∏ +=+=== > m kj j m kj j m kj j m kj j rqrq 11 ⇔ ∑∑ +== > m kj j m kj j rrq 1 k ⇔ ∑∑ +=+= >+ m kj j m kj jkk rrqrq 11 k . Но kkk prq = , тогда, перенося второе слагаемое левой части вправо и принимая во внимание, что kk pq =−1 , переходим к равносильному неравенству ∑ += > m kj jkk rpp 1 ⇔ 1 1 <∑ += m kj jr , что и требовалось доказать. Докажем еще одно вспомогательное утверждение. Пусть )1()( +> kVkV . Заменим kp на некоторую другую вероятность kp′ , такую, что kk pp >′ , остальные вероятности оставим без изменения. Соответствующую новой ситуации вероятность нахождения наилучшего элемента при той же самой пороговой стратегии выбора обозначим через )(kV ′ . Тогда )()( kVkV >′ .  С.И. Доценко, П.А. Негадайлов, 2014 ISSN 0452-9910. Кибернетика и вычисл. техника. 2014. Вып. 175 36 Действительно, согласно формуле полной вероятности имеет место рекуррентная формула )1()1()( 1 +−+= ∏ += kVpqpkV k m kj jk , (3) где первое слагаемое описывает вероятность ситуации, когда k-е испытание Бернулли привело к успеху, а последующие испытания окончились неудачей, а второе слагаемое — ситуацию, когда в k-м испытании произошла неудача. Принимая во внимание исходное предположение ),1()( +> kVkV имеем: )1( 1 +>∏ += kVq n kj j . (4) С другой стороны, )1()'1(')(' 1 +−+= ∏ += kVpqpkV k m kj jk . (5) Вычитая из (5) выражение (3), имеем:         +−−=− ∏ += )1()'()()(' 1 kVqppkVkV m kj jkk . (6) Заметим, что выражение, стоящее в правой части (4) строго положительно, поскольку первый сомножитель положителен в силу предположения )()( kVkV >′ , а второй — в силу (4). Таким образом, )()( kVkV >′ , что противоречит предположению об оптимальности исходного порядка просмотра групп. Оказывается, что в оптимальном порядке просмотра в роли отбрасываемых групп не всегда выступают группы наименьшей численности. Рассмотрим численный пример. Пусть n = 6, )10,10,10,10,8,5(=xr . Согласно леммам 1 и 2 оптимальными могут быть только три порядка просмотра, а именно: )10,10,10,10,8,5(1 =x r , )8,10,10,10,10,5(2 =x r , )5,10,10,10,10,8(2 =x r . Оказывается, что во всех трех порядках просмотра k = 3, при этом 1x r является наихудшим из трех приведенных ( 427,0)( 1 ≈xV r ) и 435,0)(433,0)( 32 ≈<≈ xVxV rr . Аналогично задаче о ранце, «жадный» алгоритм не всегда срабатывает. Численный поиск оптимального расположения для n групп, в общем случае, требует перебора всех возможных перестановок в последовательности чисел 1 … m (индексов групп), т.е. m! итераций. Леммы 1 и 2 дают возможность существенно сократить количество вариантов, тем не менее, количество итераций алгоритма полного перебора имеет факториальную зависимость от начального количества групп, что не позволяет его использовать даже при сравнительно небольших n. Поэтому было принято решение использовать так называемые «генетические  С.И. Доценко, П.А. Негадайлов, 2014 ISSN 0452-9910. Кибернетика и вычисл. техника. 2014. Вып. 175 37 алгоритмы», которые находят приблизительное решение задачи. Эффективность такого подхода подтверждается его многочисленными использованиями при решении задач дискретной оптимизации [3, 4]. Как известно (см., например, [2]), для описания генетического алгоритма достаточно указать функцию приспособленности и операторы мутации и скрещивания. В качестве функции приспособленности естественно использовать вероятность выбора оптимального индивидуума (кандидата). Согласно лемме 2 выбор должен начинаться с группы наибольшей размерности. Пусть imi xx ,1 max == . Рассмотрим последовательность 11 ~...,,~ −mxx , которая получена из последовательности nxx ...,,1 путем исключения из нее группы x (если групп такого типа размера несколько, то исключаем ту, что имеет наименьший индекс). Тогда для любой перестановки 11 ~...,,~ −mii xx оптимальное расположение x определяется однозначно, как ∑ = = m ki i k krk )(max* , где        > + = = ki x ki s x kr ki при, s x~ при, )( * 1-i i * , а ∑ = = k i ik xS 1 ~ . Согласно Лемме 1 группы в последовательности 11* ~...,,~ −+ mk ii xx должны быть расположены в порядке убывания. Таким образом, для выбора оптимального расположения групп mxx ...,,1 достаточно рассматривать последовательности 11 ~...,,~ −mii xx , вставляя группу x на позицию k и отсортировать хвост 11* ~...,,~ −+ mk ii xx в порядке убывания. При этом вероятность выбора оптимального индивидуума (она же функция приспособленности) ∏ ∑ = = − = m kj n kj jjm krkqiiF * )()(),...,( ** 11 , где        > + + = + = − − ki xs x ki xs s kq i k k i при,s при, )( * * 1-i * 1 1 . В качестве оператора скрещивания используется одноточечный кроссовер ([2]). Пусть есть две перестановки I11 ...,,:1...1 −− miim и 11 ...,, −mjj . Они порождают двоих потомков по следующему принципу: выбираем случайным образом точку (индекс) скрещивания k в пределах n...,,1 и формируем перестановки  С.И. Доценко, П.А. Негадайлов, 2014 ISSN 0452-9910. Кибернетика и вычисл. техника. 2014. Вып. 175 38 mkki jjii ~...,,~,...,, 1+ и ,~...,,~,...,, 1 mkki iijj + где mk jj ~...,,~ 1+ образуются из последовательности mk jj ...,,1+ путем замены повторяющихся индексов в ki ii ...,, на уникальные. Аналогично формируется последовательность mk ii ~...,,~ 1+ . Полученные последовательности индексов образуют потомков mk jjiki xxxx ...,,~,~...,,~ 11 + и mk iijkj xxxx ...,,~,~...,,~ 11 + , которые принимают участие на этапе отбора генетического алгоритма. Оператор мутации меняет местами два произвольных (выбранных случайным образом) индекса в перестановке. В следующей таблице приведены результаты работы описанного выше генетического алгоритма. Тут maxP — вероятность выбора наилучшего индивидуума при оптимальной последовательности групп, а minP — вероятность выбора наилучшего индивидуума при наихудшей перестановке последовательности групп. Кол-во групп maxP minP Среднее число итераций 100 0,373064 0,370633 580 200 0,370539 0,369356 1418 500 0,368929 0,368515 3217 Так как генетический алгоритм не гарантирует точного оптимального решения и относится к классу так называемых эвристических алгоритмов, то для получения лучшего результата алгоритм применяется несколько раз подряд для одной и той же задачи, но с различными начальными выборками. Для оценки результата для каждой задачи находится наихудший вариант перестановок, т.е. такая последовательность групп, для которой, применяя алгоритм оптимального поиска, вероятность выбора наилучшего индивидуума наименьшая ( minP ). Для этого используется генетический алгоритм с теми же операторами скрещивания и мутации. Хромосомами (индивидуумами алгоритма) служат перестановки начальной последовательности mxx ...,,1 , а функцией приспособленности является вероятность выбора наилучшего индивидуума в этой последовательности. ВЫВОДЫ Последовательность групп, позволяющая максимизировать вероятность выбора наилучшего индивидуума в обобщенной задаче оптимального выбора, должна удовлетворять ряду правил, приведенных в леммах 1 и 2. Тем не менее, количество вариантов расстановок групп, удовлетворяющих данным правилам, остается достаточно большим (при большом количестве исходных групп) и перебрать их все не представляется возможным. Предлагаемый генетический алгоритм численного поиска приблизительного решения задачи обеспечивает нахождение решения, близкого к оптимальному, с высокой точностью.  С.И. Доценко, П.А. Негадайлов, 2014 ISSN 0452-9910. Кибернетика и вычисл. техника. 2014. Вып. 175 39 1. Shou-Ren Hsiau, Jiing-Ru Yang. A natural variation of the standard secretary problem. Statistica Sinica, vol. 10 (2000), pp. 639–646. 2. Thomas Bruss. Sum the odds to one and stop. The annals of probability, 2000, vol. 28, no. 3, pp. 1384–1391. 3. Fonseca C.M., Fleming P.J. Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. Proc. of the 5th Int. Conf. on Genetic Algorithms, 1993, pp. 416–423. 4. Potvin J. Genetic algorithms for the travelling salesman problem. Annals of Operation Research, vol. 63 (1996), pp. 339–370. Получено 12.01.2014  С.И. Доценко, П.А. Негадайлов, 2014 ISSN 0452-9910. Кибернетика и вычисл. техника. 2014. Вып. 175

Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов

Institution

Similar Items