Автоматизированная система тендерного отдела

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

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

 

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

 

Простой генетический алгоритм случайным образом генерирует начальную  популяцию структур. Работа генетического алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий остановки. На каждом поколении генетического алгоритма реализуется отбор пропорционально приспособленности, одноточечный кроссовер и мутация. Сначала, пропорциональный отбор назначает каждой структуре вероятность 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.

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

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

 

2  РАЗРАБОТКА  СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ  ДЛЯ ФОРМИРОВАНИЯ ЗАКАЗА НА  ТОРГОВО-ЗАКУПОЧНОМ ПРЕДПРИЯТИИ

 

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

 

 

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

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

 

 

2.1.1 Языки программирования

2.1.1.1 Язык Turbo Pascal

 

 

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

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

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

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

Некоторые из основных расширений Паскаль-стандарта и дополнительные возможности Турбо Паскаля:

• Введены типы данных word, byte, string.
• Введены понятия типизированного и нетипизированного файлов и разработаны соответствующие процедуры.
• В Турбо Паскале разработаны процедуры и функции ввода-вывода для работы с любыми файлами.
• Предусмотрены процедуры и функции для работы с переменными типа string.

В Турбо Паскале разработаны  программные средства для построения графических изображений на экране компьютера; создана интегрированная Среда разработчика (ИСР), то есть ряд специализированных средств и возможностей, позволяющих создавать на экране персональной ЭВМ так называемые “окна”. В рамках этих окон, рабочих областей, пользователь может задавать те или иные действия. ИСР является средством, используемым при создании, редактировании, компиляции, выполнении и отладке Паскаль-программ.

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

Начиная с версии 5.5 Турбо  Паскаль еще один современный  метод проектирования программ —  объектно-ориентированное программирование.

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

 

2.1.1.2 Язык Turbo С

 

 

Язык Си разрабатывался как язык системного программирования. Его развитие шло по пути повышения надежности программ.

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

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

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

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

Например:

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

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

В Турбо Си, также как и в  Турбо Паскале есть нововведения, такие как интегрированная среда разработчика, дополнительные операторы и типы, функции и т.д.

 

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

• язык Турбо Паскаль используется в учебных целях и мое знание его проверено преподавателями в процессе написания лабораторных работ и сдачи экзаменов;
• удобочитаемость программ Турбо Паскаль лучше, чем программ Турбо Си;
• синтаксис языка безопасен;
• больше примитивных типов данных, чем в Ту<span class="dash041e_0431_044b_0447_043d_044b_0439__Char" st