Изучение и анализ рынка товаров, закупаемых и реализуемых торгово-закупочным предприятием (на примере Белгородского территориального фонда обязательного медицинского страхования)

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

Установить соответствие между генотипом и фенотипом закодированных особей можно, разделив соответствующее двоичное целое число на (). Например, 0000000000 соответствует 0/1023 или 0, тогда как 1111111111 соответствует 1023/1023 или 1. Оптимизируемая структура данных - N*10-битная строка, представляющая конкатенацию кодировок N переменных. Первая переменная размещается в крайних левых 10 разрядах, тогда как последняя – в правой части генотипа особи (N*10-битовой строке).

Генотип - точка в N*10-мерном хеммининговом пространстве, исследуемом генетическим алгоритмом. Фенотип - точка в N пространстве параметров.

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

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

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

Работа генетического алгоритма

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

Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величине Ps(i). Простейший пропорциональный отбор - рулетка Голдберга – отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью.

После отбора, n выбранных особей подвергаются кроссоверу (иногда называемому рекомбинацией) с заданной вероятностью Pc. n строк случайным образом разбиваются на n/2 пары. Для каждой пары с вероятность Pc может применяться кроссовер. Соответственно с вероятностью 1-Pc кроссовер не происходит и неизмененные особи переходят на стадию мутации. Если кроссовер происходит, полученные потомки заменяют собой родителей и переходят к мутации.

Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из n-1 точек разрыва (участок между соседними битами в строке). Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков. На рисунке 1.4 представлен одноточечный кроссовер с точкой разрыва, равной 2.

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

В настоящее время исследователи генетические алгоритмы предлагают много других операторов отбора, кроссовера и мутации. Назовем наиболее распространенные из них. Прежде всего, турнирный отбор, который реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.

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

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

Обоснование выбора инструментальных и аппаратных средств

В процессе обучения по специальности ПО ВТиАС в БелГТАСМ мною были изучены такие языки высокого уровня как Turbo Pascal (Турбо Паскаль) , Turbo C (самостоятельное изучение), Delphi Client/Server Suite, системы управления базами данных: FoxPro, dBase, Paradox, InterBase.

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

Язык Turbo Pascal

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

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

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

Язык содержит ряд изобразительных средств таких как case, repeat, if, while, помогающих организовать ветвление в программе без использования операторов перехода, что способствует простому пониманию алгоритма.

 Скачать реферат