Реализация алгоритма отбора в элитную группу

Реализация алгоритма отбора в элитную группу

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

.        ПОСТАНОВКА ЗАДАЧИ

.1 Характеристика задачи

.2 Входная информация

.3 Выходная информация

.4 Математическая постановка задачи

.5 Специальные требования к техническому обеспечению

.        ОПИСАНИЕ МЕТОДА МОДЕЛИРОВАНИЯ

.        ОПИСАНИЕ АЛГОРИТМА

.1 Назначение и характеристика

.2 Используемая информация

.3 Результаты решения

.4 Математическое описание

.5 Алгоритм решения

.        ОПИСАНИЕ ПРОГРАММЫ

4.1     Описание функции заполнения исходного множества

4.1.1  Вводная часть

4.1.2  Функциональное назначение

4.1.3  Описание информации

.1.4    Описание логики

.1.5    Настройка программных средств

4.2     Описание функции формирования элитной группы

4.2.1  Вводная часть

4.2.2  Функциональное назначение

.2.3    Описание информации

.2.4    Описание логики

.2.5    Настройка программных средств

4.3     Описание функции эволюции элитной группы

4.3.1  Вводная часть

4.3.2  Функциональное назначение

.3.3    Описание информации

.3.4    Описание логики

.3.5    Настройка программных средств

4.4     Описание функции "прополки"

4.4.1  Вводная часть

4.4.2  Функциональное назначение

.4.3    Описание информации

.4.4    Описание логики

.4.5    Настройка программных средств

4.5     Описание функции "сбора урожая"

4.5.1  Вводная часть

4.5.2  Функциональное назначение

.5.3    Описание информации

.5.4    Описание логики

.5.5    Настройка программных средств

.        ОПИСАНИЕ КОНТРОЛЬНОГО ПРИМЕРА

5.1     Назначение

.2  Исходные данные

5.3     Результаты работы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 1. ТЕКСТ ПРОГРАММЫ

ПРИЛОЖЕНИЕ 2. КОНТРОЛЬНЫЙ ПРИМЕР

ПРИЛОЖЕНИЕ 3. РУКОВОДСТВО ПРОГРАММИСТА

ПРИЛОЖЕНИЕ 4. РУКОВОДСТВО ОПЕРАТОРА

ВВЕДЕНИЕ

Целью данной курсовой работы является разработка программы для принятия решения с повторением - реализация алгоритма отбора в элитную группу. В качестве элитной группы используется различные виды меха. Претенденты в коллекцию будут отбираться согласно критериям: вид меха, высота мехового покрытия (в мм), блеск. Эволюция группы предусматривает набор элементов в элитную группу заново согласно выбранному рекомендателю. Развитие группы пойдет либо в положительном направлении, либо в отрицательном (деградация). Так же возможно проведение процедур «прополки», то есть исключения из группы «сорных» элементов или отбора лучших - уход из группы лучших элементов.

Задача программы показать, какие элементы попадут в группу, предусматривая элемент случайности, также показать дальнейшее развитие группы.

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

.       
ПОСТАНОВКА ЗАДАЧИ

1.1     Характеристика задачи

Задача предназначена для принятия решения с повторением - для отбора мехов по трём критериям: вид меха, высота мехового покрытия (в мм), блеск. Задача предусматривает эволюцию элитной группы, процедуры «прополки» и отборки лучших.

1.2     Входная информация

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

Входные данные включают:

·        Имя меха

·        Вид меха

·        Высота мехового покрытия (в мм)

·        Блеск

1.3     Выходная информация

Выходной информацией является сформированная согласно эталону элитная группа, а именно коллекция видов меха. При формировании группы предусматривается включение «сорных» элементов.

При эволюции подсчитывается сумма элитной группы по критериям до и после, и в результате сравнения выводим результат, развивается группа или деградирует.

При «прополке» выводятся n заменяемых элементов с худшей суммой, а при отборе лучших - с лучшей.

1.4     Математическая постановка задачи

В данной работе реализована модель - «Претендент - Рекомендатель». Она заключается в том что, на первом этапе из генеральной совокупности объектов выбираются объекты с улучшенными свойствами. В качестве таких свойств выбраны: вид меха, высота мехового покрова (в мм), блеск.

Запишем их в следующем виде:

< surface,depth,glitter> - множество критериев, где

surface - вид меха

depth - высота мехового покрова (в мм.),- блеск.

Данные эталона вводятся пользователем, обозначим их следующим образом:

<s,d,g> - множество критериев эталона, где

s - вид меха,

d - высота мехового покрова (в мм.),

g - блеск.

Элементы из генеральной совокупности попадают в элитную группу при выполнении следующего условия:

(surface >= s) & (depth >=d) & (glitter >=g)

Данная схема идеализирована, поэтому следует добавить ошибку, так что в результате в элитную группу могут попасть и не элитные элементы, так называемые «сорняки»:

(surface <= s) & (depth <=d) & (glitter <=g). Вероятность попадания «сорняка» p=0,02.

С долей сорных элементов или без нее, формируется элитная группа и с ней можно начать работать.

Введём ещё одно условие: при необходимости пополнить группу из-за того, что какие-то элементы выбыли из неё. При этом к эталону обратиться уже нельзя, так как он нужен только на этапе формирования группы. Для этого поступаем следующим образом:

Выбираем наугад элитный элемент, назвав его «рекомендателем» и так же наугад элемент из исходной совокупности «претендента» и сравниваем их. Если «претендент» окажется не хуже «рекомендателя», он включается в элиту.

Пусть рекомендатель rec принадлежит множеству элементов элитной группы Э, тогда rec выбирается следующим образом:

Rec = СЛЧИСЛ(Э)

Пусть претендент can принадлежит множеству генеральной совокупности Г, тогда can выбирается следующим образом:

Can = СЛЧИСЛ(Г)

Элемент добавляется при выполнении следующего условия:

Can >= Rec

При этом для элиты возможно два пути развития: положительный, когда элита состоит из элементов с высокими показателями критериев, либо отрицательный (деградация), когда число сорных элементов стало велико в группе. Для этого считается сумма до шага эволюции (S1) и сумма после эволюции (S2):

Все элементы элитной группы Э принадлежат следующему множеству:

<s,d,g> - множество критериев элемента, где

s - вид меха,

d - высота мехового покрова (в мм.),

g - блеск.

Сумма до шага эволюции вычисляется следующим образом:

где КОЛ - количество элементов в элитной группе.

Сумма после шага эволюции вычисляется следующим образом:

Элита развивается, если S1>S2, иначе элита деградирует

1.5     Специальные требования к техническому обеспечению

Программа может работать на персональном компьютере с операционной системой Windows XP\Vista\7. Дополнительное наличие программ или библиотек не требуется.

2. ОПИСАНИЕ МЕТОДА МОДЕЛИРОВАНИЯ

Эталон - объект внешний по отношению, как к исходной совокупности, так и к формируемой группе. Он привносится извне и вообще может иметь иную природу, чем сортируемые объекты.

Оперируя эталоном и найдя в исходной совокупности нужное число элементов, не худших, чем эталон, мы закончим формирование элитной группы. Введем еще одно условие: при необходимости пополнить группу из-за того, что какие-то элементы выбыли из нее (израсходовав ресурс, погибнув и т. д.), к помощи эталона прибегнуть уже нельзя. Эталон был доступен только на этапе формирования группы.

Выберем наугад элитный элемент, назвав его "рекомендатель", и так же наугад элемент из исходной совокупности "претендента" и сравним их. Если претендент окажется не хуже «рекомендателя», он включается в элиту.

Рис. 2.1

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

Нужно исследовать два режима: когда первыми выбывают худшие и когда первыми выбывают лучшие элементы.

Жизнь математической модели - это последовательность шагов, на каждом из которых из элитной группы удаляются и заменяются претендентами элементы с недопустимо изменившимся параметром. Если лучший существует дольше (положительная обратная связь), то на первых же шагах "вымирает" часть "сорных", попавших в элиту, миновав эталон, и возрастает доля элитных. Дальнейшие шаги делают группу все более элитной (см. рис. 2.2).

Рис 2.2

Если же лучшие выбывают первыми (отрицательная обратная связь), то уже начальный шаг уносит "сверхэлиту" (см. рис 2.3) и процесс пополнения идет без нее - они рекомендателями быть не смогли, а остальные, в том числе "сорные", померялись доблестью с претендентами.

Рис 2.3

Свойства элитной группы с отрицательной обратной связью (лучшие выбывают первыми) и механизмом пополнения "претендент - рекомендатель" неизбежно ухудшаются, если при первоначальном формировании в элиту попала, хотя бы малая доля неэлитных ("сорных") элементов.

3. ОПИСАНИЕ АЛГОРИТМА

3.1     Назначение и характеристика

Данная задача предназначена для формирования элитной группы из исходного множества согласно введенным критериям (эталону), эволюции элитной группы, то есть новое формирование элитной группы за счет выбора «рекомендателя» из элитной группы и «претендента» из исходного множества. Данная задача предусматривает случайные факторы при отборе в элитную группу.

3.2     Используемая информация

Исходное множество, состоящее из добычи вид меха со случайными значениями критериев (вид меха, толщина перламутрового слоя, блеск).

Значение эталона: вид меха, толщина перламутрового слоя, блеск.

3.3     Результаты решения

В случае задания всех критериев для эталона (вид меха, толщина перламутрового слоя, блеск) формируется элитная группа, и результаты выдаются в форме таблицы. При дальнейшей эволюции элитная группа формируется заново, также может произойти случайное удаление элементов (не обязательно «сорных»).

3.4     Математическое описание

При задании эталона вводятся минимальные значения критериев: вид меха, толщина перламутрового слоя, блеск.

При этом жемчуг из исходного множества отбираются в группу, если выполняется следующее условие:

Обозначим входные данные: вид меха - П, высота мехового покрова - Т, блеск - Б.

(вид меха >=П) & (толщина слоя >= Т) & (блеск>=Б).

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

Если случайное число Х в промежутке от 1 до 100 меньше или равно 2 -«коэффициента сорности», то в элитную группу включается текущий элемент из исходного множества. Таким образом, существует возможность попадания в группу «сорного» элемента.

При эволюции из элитной группы выбирается случайным образом рекомендатель (Р), а из исходного множества претендент (П). Если значения претендента по критериям больше либо равны значениям критериев рекомендателя, претендент - включается в элитную группу.

3.5     Алгоритм решения

)        В начале программы исходное множество заполняется вид мехаами следующим образом:

Имя = Вид меха + номер в списке;

Вид меха = случайное число от 1 до 11;

Высота мехового покрова = случайное число от 1 до 35;

Блеск = случайное число от 1 до 5;

)       
Чтение значений критериев эталона (вид меха, высота мехового покрова (в мм), блеск).

)        Набор в элитную группу согласно условию, описанному в пункте 2.4.

)        Развитие элитной группы: выбор «рекомендателя» и «претендента».

)        Отбор в элитную группу.

)        Подсчет суммы по критериям.

)        Вывод о развитии или деградации группы.

)        Конец.

4. ОПИСАНИЕ ПРОГРАММЫ

4.1     Описание функции заполнения исходного множества

4.1.1  Вводная часть

Процедура для заполнения исходного множества в самом начале работы программы случайными значениями критериев.

4.1.2  Функциональное назначение

Процедура формирует исходное множество для дальнейшего формирования из него элитной группы.

4.1.3  Описание информации

Процедура не использует входную информацию: вид меха, высота мехового покрова (в мм), блеск.

В качестве выходной информации выводятся значения критериев в таблицу. Критерии вычисляются следующим образом:

Имя = Вид меха + номер в списке;

Вид меха = случайное число от 1 до 11;

Высота мехового покрова = случайное число от 0,1 до 20;

Блеск = случайное число от 1 до 5;

4.1.4  Описание логики

Описание логики процедуры представлено на рис.4.1.

Рис.4.1. Описание логики

4.2     Описание функции формирования элитной группы

4.2.1  Вводная часть

Процедура формирует элитную группу из исходного множества согласно эталону.

4.2.2  Функциональное назначение

Процедура предназначена для отбора элементов в исходное множество согласно значениям критерия эталона и случайного включения в группу «сорных» элементов.

4.2.3 
Описание информации

Входная информация: вид меха, высота мехового покрова (в мм), блеск.

Выходная информация: элитная группа, данные которой выводятся в таблицу.

4.2.4  Описание логики

Описание логики процедуры представлено на рис.4.2.

Рис.4.2. Описание логики процедуры.

4.3    
Описание функции эволюции элитной группы

4.3.1  Вводная часть

Процедура предназначена для дальнейшего развития элитной группы.

4.3.2  Функциональное назначение

Процедура выбирает «рекомендателя» из элитной группы, претендента из исходного множества и происходит отбор элементов в элитную группу заново согласно значениям критериев «рекомендателя».

4.3.3  Описание информации

Входная информация: таблица со значениями критериев элитной группы.

Выходная информация: вновь сформированная элитная группа, вывод о результате развития группы.

4.3.4  Описание логики

Описание логики процедуры представлено на рис.4.3.

Рис.4.3. Описание логики процедуры

4.4     Описание функции "прополки".

4.4.1  Вводная часть

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

4.4.2     
Функциональное назначение

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

4.4.3  Описание информации

Входная информация: количество элементов, которое необходимо заменить; "элитная" группа.

Выходная информация: элитная группа, данные которой выводятся в таблицу (с замененными элементами);

4.4.4  Описание логики

Описание логики процедуры представлено на рис.4.4.

Рис.4.4. Описание логики процедуры

4.5    
Описание функции отбора лучших

4.5.1  Вводная часть

4.5.2      Функциональное назначение

Функция предназначена для удаления наиболее "качественных" элементов и замена их случайными элементами из генеральной группы. Таким образом, эмитируется переход "качественных" элементов в "в верхи".

4.5.3  Описание информации

Входная информация: количество элементов, которое необходимо заменить; "элитная" группа.

Выходная информация: элитная группа, данные которой выводятся в таблицу (с замененными элементами);

4.5.4  Описание логики

Описание логики процедуры представлено на рис.4.5.

Рис.4.5. Описание логики процедуры

ЗАКЛЮЧЕНИЕ

Данная курсовая работа была основана на теории элитных групп, выдвинутых А. Ефимовым. Разработанная программа формирует элитную группу и прогнозирует ее дальнейшее развитие в положительном или отрицательном направлении - деградация.

Применение данной программы отображает реальную модель формирования коллекции драгоценных камней.

программа элитный группа мех

СПИСОК ЛИТЕРАТУРЫ

1.       А.Н. Ефимов "Элитные группы, их возникновение и эволюция", Знание-сила. 1988. №1, С. 56-64.

2.       <#"577658.files/image010.gif">

Рис.2.1. Формирование исходного множества

Введем данные эталона и посмотрим на результаты формирования элитной группы (см.рис.2.2.).

Рис.2.2. Формирование элитной группы

Рис.2.3. Элитная группа развивается.

Рис.2.4. Элитная группа деградирует.

Программа работает согласно постановке задачи, см. пункт 1.

ПРИЛОЖЕНИЕ 3

РУКОВОДСТВО ПРОГРАММИСТА

П3.1. Назначение программы

Программа предназначена для формирования элитной группы из исходного множества согласно заданному пользователем эталону, а также для прогнозирования дальнейшего развития элитной группы.

П3.2. Условия применения программы

Программа может работать на персональном компьютере с операционной системой Windows XP\Vista\7. Дополнительное наличие программ или библиотек не требуется. Для реализации программы необходима программа Microsoft Visual Studio Team Suite 2008.

П3.3. Входные и выходные данные

В качестве входных данных используются исходное множество и значения критериев эталона.

Выходными данными являются таблица элитной группы и результаты эволюции.

П3.4. Сообщения

Выводиться сообщение о «прополотых» и отобранных элементах с полной информацией об их критериях.

ПРИЛОЖЕНИЕ 4

РУКОВОДСТВО ОПЕРАТОРА

П4.1. Назначение программы

Программа предназначена для формирования элитной группы из исходного множества согласно заданному пользователем эталону, а также для прогнозирования дальнейшего развития элитной группы.

П4.2. Условия применения программы

Программа может работать на персональном компьютере с операционной системой Windows XP\Vista\7. Дополнительное наличие программ или библиотек не требуется. Для реализации программы необходима программа Microsoft Visual Studio Team Suite 2008.

П4.3. Команда оператора

Оператор не управляет выполнением программы. Путем нажатия кнопок он может запускать различные процедуры.

Кнопки:

«Сформировать» - заполняет генеральную совокупность;

«Создать» - формирует элитную группу из исходной генеральной совокупности;

«Далее» - запускает эволюцию элитной группы;

«Прополоть» - запускает процедуру «прополки»;

«Отобрать лучшие» - запускает процедуру отбора лучших.

П4.4. Сообщения оператору

Выводиться сообщение о «прополотых» и отобранных элементах с полной информацией об их критериях.