Разработка информационной системы для туристического агентства

Механизм отбора

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

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

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

4.6 Формат данных

В процессе использования программы данные пребывают в нескольких состояниях: исходные данные - в обычном виде, называемые биологическим термином «фенотип», в процессе оптимизации работа идёт с преобразованными данными, или «генотипом». На выход, пользователь снова получает расшифрованную информацию. Таким образом, в генотипе отражены все свойства объекта, и наоборот, можно из генотипа получить фенотип. Всё функционирование алгоритма происходит на уровне генотипа, то есть позволяет обойтись без сведений о структуре используемых объектов. Обычно (и в моём случае тоже) каждому атрибуту объекта соответствует один ген в генотипе. Ген представляет собой битовую строку длиной 32 бита. Для кодирования признаков используется способ кодирования, при котором соседние числа отличаются меньшим количеством позиций, чем при стандартном - код Грея (табл. 1).

Таблица 1 Соответствие десятичных кодов и кодов Грея

Двоичное кодирование	Кодирование по коду Грея
Десятичный код	Двоичное значение	Шестнадцатеричное значение	Десятичный код	Двоичное значение	Шестнадцатеричное значение
0	0000	0h	0	0000	0h
1	0001	1h	1	0001	1h
2	0010	2h	3	0011	3h
3	0011	3h	2	0010	2h
4	0100	4h	6	0110	6h
5	0101	5h	7	0111	7h
6	0110	6h	5	0101	5h
7	0111	7h	4	0100	4h
8	1000	8h	12	1100	Ch
9	1001	9h	13	1101	Dh
10	1010	Ah	15	1111	Fh
11	1011	Bh	14	1110	Eh
12	1100	Ch	10	1010	Ah
13	1101	Dh	11	1011	Bh
14	1110	Eh	9	1001	9h
15	1111	Fh	8	1000	8h

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

Выходные данные представляются пользователю в виде документа в формате MS Word. Это позволяет удобно просмотреть подробное описание с ценами и распечатать при необходимости. Путь к файлу описания берётся из базы после оптимизации.

4.7 Разработка алгоритма генерации критерия

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

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

вид отдыха - должен влиять на значимость различных параметров, например, то, что важно для пляжного отдыха, совершенно не нужно в активном;

наличие или отсутствие каких либо услуг - должно увеличивать рейтинг туров, где условие выполнено;

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

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

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

Для формирования окончательного критерия необходимо сложить следующие числа:

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

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

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

4.8 Разработка алгоритма оптимизации

Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.

Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B0 = {A1,A2,…,Ak)

Вычислить приспособленность каждой особи FAi = fit(Ai) , i=1…k и популяции в целом Ft = fit(Bt) (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.

Выбрать особь Ac из популяции. Ac = Get(Bt)

С определенной вероятностью (вероятностью кроссовера Pc) выбрать вторую особь из популяции Аc1 = Get(Bt) и произвести оператор кроссовера Ac = Crossing(Ac,Ac1).

С определенной вероятностью (вероятностью мутации Pm) выполнить оператор мутации. Ac = mutation(Ac).

С определенной вероятностью (вероятностью инверсии Pi) выполнить оператор инверсии Ac = inversion(Ac).

Поместить полученную хромосому в новую популяцию insert(Bt+1,Ac).

Выполнить операции, начиная с пункта 3, k раз.

Увеличить номер текущей эпохи t=t+1.

Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Теперь рассмотрим подробнее отдельные этапы алгоритма.

Наибольшую роль в успешном функционировании алгоритма играет этап отбора родительских хромосом на шагах 3 и 4. При этом возможны различные варианты. Наиболее часто используется метод отбора, называемый рулеткой. При использовании такого метода вероятность выбора хромосомы определяется ее приспособленностью, то есть PGet(Ai) ~ Fit(Ai)/Fit(Bt). Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод - турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

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

4.9 Разработка структуры классов

Для реализации модели были разработаны следующие классы, представленные на диаграмме классов.

Рис.3 Диаграмма классов

Класс TGene представляет собой описатель гена, в котором свойство BegPos означает положение гена в хромосоме, а свойство Degree - длину гена. Как я уже упоминал, в этой конкретной системе длина гена постоянна и равна 32 битам.

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

Класс TGeneticAlgorithm описывает непосредственно алгоритм оптимизации и содержит в разделе private множество параметров, которые определяют работу алгоритма. Функциями этого класса реализуются генетические операторы, а также механизмы функционирования алгоритма в целом. В этом классе агрегированы объекты класса TChromosome в количестве, определяемом параметром ChromosomeCount класса.

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

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

Действие класса TChromosome покажу на диаграмме состояний.



Рис. 4 Диаграмма состояний - TChromosome.

Класс предназначен исключительно для хранения информации и не представляет особой сложности. На следующей диаграмме - класс TGeneticAlgorithm.

Рис.5 Диаграмма состояний - TGeneticAlgorithm

4.10 Разработка базы данных системы

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

не требуется преобразование данных после чтения из базы;

структура системы упрощается;

возрастает скорость оптимизации;

файлы в формате Word играют важную роль в бизнес-процессе, и отказаться от них всё равно не возможно;

расчёт на последующую интеграцию с системой учёта туров

Таблица 2. Поля в БД - таблица tblMain

Название поля	Значение
ID	Идентификатор
HotelName	Название отеля
RoomQ	Качество проживания
SeaDistance	Расстояние до моря (или другой цели тура)
FoodQ	Качество питания
RoomPrice	Стоимость проживания
Heal	Количество болезней, которые лечат
HealQ	Качество лечения
PreHeal	Количество болезней, от которых профилактика
Climat	Насколько климат способствует лечению
HealPrice	Стоимость лечения
TransferDist	Расстояние трансфера
TransferQ	Качество трансфера
TransferLong	Продолжительность трансфера
TransferMan	Количество человек в транспорте во время трансфера
TransferPrice	Стоимость трансфера
ExcursionNumber	Количество экскурсий
ExcursionDist	Расстояние до мест жкскурсий
ExcursionPrice	Стоимость экскурсий
Additional	Дополнительные услуги
AdditionalQ	Качество дополнительных услуг
DescriptionPath	Путь к полному описанию

В единственной таблице tblMain содержится информация о турах в следующем виде: все численные данные нормализованы, все качественные данные преобразованы в численные и также нормализованы. Дополнительные услуги хранятся в поле Additional в виде битовой строки, каждой услуге выделено по 1 биту. Таким образом, данные подготовлены к работе алгоритма. Приведение данных в нужный вид производится в модуле заполнения базы данных. Преобразование из понятного пользователю набора параметров в абстрактные числа производится автоматически.

Формат битовой строки Additional:

Таблица 3. Структура поля Additional

Номер бита	Значение бита
1	Спортзал
2	Корт
3	Столы для настольного тенниса
4	Тренажёрный зал
5	Бильярд
6	Прокат спортинвентаря
7	Библиотека
8	Парикмахерская
9	Косметический кабинет
10	Кафе
11	Бар
12	Продажа сувениров
13	Фотоуслуги
14	Автостоянка
15	Камера хранения
16	Гид
17	Дискотека
18	Казино
19	Детская комната
20	Детские аттракционы
21	Бассейн
22	Собственный пляж
23	Лодочная станция
24	Медпункт
25	Кинозал
26	Сауна
27	Солярий
28	Фитнесс-центр
29	Русская баня
30	Место для шашлыков
31	Конюшня
32	Аптека
33	Фитобар
34	Тир
35	Джакузи

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

База данных выполнена в СУБД Microsoft Access. Эта СУБД предоставляет удобное средство для проектирования баз данных, позволяет легко подключиться к полученной базе благодаря драйверам ODBC, включённым во все средства разработки. Использование драйверов ODBC позволяет в дальнейшем сменить базу данных без особых затрат времени.

Ограничения целостности реализованы только на уровне модуля заполнения базы ввиду абстрактности данных, хранящихся в БД. Более серьёзные ограничения потребовали бы значительного усложнения базы данных, что в данном случае не оправдано.

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

4.11 Конфигурация технических средств

Программа занимает в оперативной памяти компьютера 8 MB. Поскольку база данных выполнена в виде MS Access, память на сервер базы данных не требуется. Программа работает в семействе Windows, причем одновременно с множеством других программ. Исходя из этого, можно определить минимальные требования, предъявляемые программой:

Процессор - Intel Celeron 500 (AMD K6-2 500)

Память - 64 MB

HDD - 30 MB свободных

Screen - 800x600 SVGA

Принтер - любой (опционально)

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

Процессор - AMD Atlon (Duron) 1000 или Intel Pentium 3 (Celeron) 1000

Память - 256 MB DDR

HDD - 30 MB свободных

Screen - 800x600 SVGA

Принтер

Даже эти рекомендуемые требования не являются ничем запредельным в настоящее время, когда ведущие производители процессоров преодолели частоту 3ГГц, а память дешевеет на глазах, в SD-RAM и вовсе не выпускается. Таким образом, любой современный компьютер позволяет комфортно работать с программой. Поскольку остальные программы, применяемые в туризме уже требуют определённых ресурсов, применение моей системы не потребует от фирмы модернизации парка компьютеров.

5. Рабочий проект

5.1 Разработка программы

Разработка программы проводилась модульным способом. Все модули были созданы в среде Borland Delphi. Ниже приведу описание одного из самых сложных модулей, который реализует работу генетического алгоритма.

В модуле объявлены классы TChromosome и TGeneticAlgorithm. Это основные классы алгоритма, рассмотрим их подробнее.

Класс TChromosome порождён от TBits и представляет собой хранилище информации, включающее методы обработки информации. В нём объявлены следующие переменные:

Private //Раздел частных объявлений класса

fDegree : integer; //Разрядность генов

fGeneCount : integer; //Количество генов

fGene : array of TGene; //Собственно, гены

Работа с объектами этого класса происходит при помощи следующих методов.

procedure SetGeneCount(Value : integer); // Установка количества генов

function GetGeneSize:integer; //Установка размеров генов

procedure SetGeneSize(Value:integer); //Установка размера конкретного гена

function GetGene(Index:integer):LongWord; //Получение значения гена

procedure SetGene(Index:integer;Value:LongWord); //Установка значения гена

function GetGeneAsInteger(Index:integer):LongInt; //Получение значения гена

procedure SetGeneAsInteger(Index:integer;Value:LongInt); //Получение значения гена

function GetGeneAsFloat(Index:integer):double; //Получение значения гена

procedure SetGeneAsFloat(Index:integer;Value:double); //Получение значения гена

В разделе открытых объявлений содержатся поле Suitability, которое хранит текущую приспособленность хромосомы, конструктор, деструктор и следующие методы и свойства.

procedure Assign(Source: TChromosome); //Копирование информации из одной хромосомы в другую

property GeneCount : integer read fGeneCount write SetGeneCount; //Количество генов

property GeneSize : Integer read GetGeneSize write SetGeneSize; //Размер генов

property GeneValue[Index:integer] : Longword read GetGene write SetGene; //Значение гена

property GeneAsInteger[Index:integer] : LongInt read GetGeneAsInteger write SetGeneAsInteger; //Значение гена

property GeneAsFloat[Index:integer] : double read GetGeneAsFloat write SetGeneAsFloat; //Значение гена

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

Переменная fPopulation хранит набор хромосом, то есть рабочий материал для работы алгоритма.

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

Свойство Sutability хранит текущую приспособленность популяции, но его значение доступно только через свойство fSutability, описание которого находится в разделе public.

Функция fGetSutability - это указатель на внешнюю функцию, которая определяет фитнесс-функцию текущей хромосомы.

fBestChromosome - лучшая особь данной популяции.

fInversion, fCrossover, fMutation - вероятности инверсии, кроссовера и мутации - важных параметров алгоритма.

Процедура OneEpoch производит один шаг эволюции.

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

5.2 Алгоритмы работы программы

Общая схема работы представлена на рисунке 6.

Рис.6 Схема общего алгоритма работы программы

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

Рис.7 Схема алгоритма инициализации

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



Рис.8 Схема алгоритма оптимизации

Генные операторы кроссовера, мутации, инверсии реализованы функциями класса TGeneticAlgorithm. Проверка приспособленности производится фитнесс-функцией, сформированной программой.

Рис.9 Схема алгоритма преобразования данных

Преобразование в код Грея и обратно производится с помощью таблиц преобразования.

GrayToDec : array[0..15] of byte = (0,1,3,2,7,6,4,5,15,14,12,13,8,9,11,10);

DecToGray : array[0..15] of byte = (0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8);

5.3 Методика испытаний

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

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

Тестирование окончательной версии программы показало, что все ошибки были найдены и исправлены, и релиз избавлен от недоработок.

5.4 Разработка программной документации

В рамках работы над дипломным проектом были созданы следующие документы: схемы алгоритмов, текст программы и руководство оператора.

Текст всех модулей приведён в приложении 1. Руководство оператора - в приложении 2.

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

5.5 Установка информационной системы

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

По умолчанию, программа устанавливается в каталог C:\Program Files\TourAdviser\, однако при установке пользователь имеет возможность выбрать другой каталог.

Окно установщика выглядит следующим образом.



Рис. 10 Окно установщика TourAdviser

6. Технологический раздел

6.1 Введение

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

6.2 Объектно-ориентированное программирование

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

объектная модель позволяет в полной мере использовать выразительные возможности объектных и объектно-ориентированных языков программирования;

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

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

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

Основой объектно-ориентированного программирования является объектная модель. Она имеет 4 главных элемента:

абстрагирование;

инкапсуляция;

модульность;

иерархия.

Кроме главных, имеются ещё 3 дополнительных элемента:

типизация;

параллелизм;

сохраняемость.

Рассмотрю эти составляющие подробнее.

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

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

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

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

Иерархия - это упорядочивание абстракций по уровням. Примером иерархии является наследование - важнейший инструмент объектно-ориентированного программирования. Второй важной разновидностью иерархии является агрегация, определяющая отношение “part of”.

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

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

Ну и наконец, последний из элементов объектно-ориентированной модели - сохраняемость. Она представляет из себя способность объекта существовать во времени, переживая породивший его процесс, и(или) в пространстве, перемещаясь из своего адресного пространства.

6.3 Объектно-ориентированное проектирование

Рассмотрю принципы объектно-ориентированного проектирования, которое основано на объектно-ориентированной модели. Обычно процессы программирования и проектирования, отделенный от процесса управления (или микропроцесс в определении Гради Буча [16]), состоит из следующих видов деятельности:

выявление классов и объектов на данном уровне абстракции;

выявление семантики этих классов и объектов;

выявление связей между этими классами и объектами;

спецификация интерфейса и реализация этих классов и объектов.

При этом в микропроцессе перемешаны фазы анализа и проектирования. Рассмотрю эти процессы более подробно.

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

После выполнения этого шага можно переходить к выявлению семантики классов и объектов, то есть определению поведения и атрибутов каждой абстракции. На стадии анализа этот шаг применяется для распределения обязанностей между различными видами поведения системы. На стадии проектирования эта процедура позволяет распределить обязанности между частями реализации. При реализации следует продвигаться от описаний ролей и обязанностей в свободной форме к спецификациям конкретных протоколов для каждой абстракции и, в конечном счёте, - к точным сигнатурам (совокупностям признаков) каждой операции. Результатом становится уточнение словаря данных. В ходе проектирования можно выработать спецификации к каждой абстракции, перечисляя имена операций в протоколе каждого класса. Следующим шагом станет создание интерфейсов этих классов на языке реализации. Примером могут служить заголовочные файлы .h в С++. Также составляются диаграммы объектов и диаграммы взаимодействий, передающие семантику сценариев, создаваемых в ходе микропроцесса.

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

Реализация классов и объектов доводит существующие абстракции до уровня, достаточного для обнаружения новых классов и объектов, необходимых на следующем уровне абстракции. При проектировании с целью реализации становится создание осязаемого представления абстракций путём выпуска последовательных исполнимых версий системы (макропроцесс). Этот шаг намеренно выполняется позже всех, так как макропроцесс концентрирует внимание на поведении и откладывает решения о представлении. На этом шаге принимается решение о представлении каждой абстракции и об отображении каждой абстракций в физическую модель. В начале процесса разработки формулируются тактические решения о представлении в форме уточненных спецификаций классов. Решения, имеющие общий интерес, или подходящие для повторного использования, документируются на диаграммах классов (показывающих их статическую семантику), состояний или взаимодействия (показывающих их динамическую семантику). Когда становится ясно, на каком языке реализовывать проект, начинается программирование в псевдокоде или исполнимом коде. Для раскрытия связей между логическим и физическим уровнем, вводятся диаграммы модулей, которые затем можно использовать, чтобы показать отображение архитектуры в программную реализацию. С реализацией связано одно главное действие - выбор структур и алгоритмов, которые представляют семантику определённых ранее микропроцессом абстракций. В отличие от первых трех стадий микропроцесса, сосредоточенных на внешних представлениях абстракций, этот этап акцентирует внимание на их внутреннем представлении. На стадии анализа результаты этого действия относительно абстрактны, поскольку разработчик не столько обеспокоен реализацией сколько заинтересован в отыскании новых абстракций, которым можно делегировать обязанности. На стадии проектирования, особенно на поздних стадиях проектирования классов, нужно переходить к практическим решениям.

6.4 Работа с базами данных в Delphi

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

Для хранения данных был выбран реляционный тип базы данных. Это связано с тем, что этот тип БД позволяет удобно работать с большими объёмами данных, его поддерживают многие современные СУБД. И опять же нельзя было забывать о интеграции с существующими системами, которые используют именно этот тип баз данных.

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

Для создания базы данных не была использована стандартная утилита, входящая в Delphi - Database Desktop. Это связано с неудобным способом хранения таблиц, принятом в этой программе. Кроме того, хотелось избежать установки BDE на компьютеры клиента. Поэтому разработка базы данных проводилась в среде Microsoft Access, а программа подключалась к ней через драйвер ODBC. Это доказало независимость системы от выбора базы данных, что гарантирует лёгкий переход к использованию других баз после интеграции с внешними программами.

При работе использовались компоненты ADOConnection и ADOQuery. Эти компоненты предоставляют доступ к базе данных и возможность производить любые действия, изменяя свойство SQL компонента ADOQuery и выполняя метод ExecSQL. В модуле наполнения базы данных были использованы компоненты визуальной работы с базой данных. Это DBGrid, DBNavigator, DBText и DBEdit.

6.5 Использование компонентов ADO

Расскажу поподробнее про технологию ADO, которая использовалась для подключения к базе данных. ADO (ActiveX Data Objects) является частью универсального механизма доступа к данным фирмы Microsoft (Microsoft Universal Data Access), который позволяет осуществить доступ как к реляционным, так и к нереляционным источникам данных, таким как файловая система, данные электронной почты, многомерные хранилища данных и др. Универсальный механизм доступа к данным (Universal Data Access) являет собой стратегию предоставления доступа к любому типу информации предприятия. Он обеспечивает высокопроизводительный доступ к различным источникам информации (включая реляционные и нереляционные данные), в том числе к данным, хранящимся на мэйнфреймах, данным электронной почты и файловой системы, текстовым, графическим и географическим данным и др.

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

Назначение универсального механизма доступа к данным фирмы Microsoft -- предоставить доступ к перечисленным источникам данных с помощью единой модели доступа к данным.

В настоящее время универсальный механизм доступа к данным фирмы Microsoft поддерживает все наиболее популярные настольные и серверные СУБД.

Microsoft ActiveX Data Objects (ADO) представляет собой программный интерфейс для доступа к данным из приложений. С точки зрения программирования ADO и его расширения являются упрощенным высокоуровневым объектно-ориентированным интерфейсом к OLE DB.

OLE DB -- это низкоуровневый интерфейс для доступа к данным. ADO использует OLE DB, но можно использовать OLE DB и напрямую, минуя ADO.

Open Database Connectivity (ODBC) - стандартный способ доступа к реляционным данным. Этот компонент универсального механизма доступа к данным оставлен с целью обеспечения совместимости с прежними версиями программного обеспечения. В современных приложениях применению ODBC-драйверов предпочитают использование OLE DB-провайдеров.

Рассмотрим вышеупомянутые технологии поподробнее.

OLE DB представляет собой программный интерфейс для доступа к различным источникам данных, таким как реляционные и нереляционные данные, текстовые, графические и географические данные, архивы электронных писем, файловая система, бизнес-объекты. В спецификации OLE DB определен набор COM-интерфейсов (COM, Component Object Model, компонентная модель объектов Microsoft, являющаяся составной частью 32-разрядных версий Windows), инкапсулирующих различные сервисы управления данными и предоставляющих однотипный доступ к перечисленным выше данным. Эти интерфейсы могут быть использованы в приложениях, предоставляющих доступ к данным.

На самом верхнем уровне можно отметить три главных компонента OLE DB: потребители (consumers), провайдеры данных (data providers) и сервисные компоненты (service components).

Любой компонент программного обеспечения, применяющий интерфейсы OLE DB, является потребителем. Это может быть какое-либо офисное приложение или иное бизнес-приложение, средство разработки типа Visual Basic или Delphi либо даже COM-объекты для доступа к данным, применяющие интерфейсы OLE DB. Потребители могут обращаться к данным посредством ActiveX Data Objects, представляющих собой высокоуровневый интерфейс к OLE DB, или применять OLE DB непосредственно, используя OLE DB-провайдер.

Провайдер -- это часть программного обеспечения, в которой реализованы интерфейсы OLE DB. С точки зрения OLE DB существуют два типа OLE DB-провайдеров -- провайдеры данных и сервисные компоненты.

Провайдер данных -- это компонент программного обеспечения, манипулирующий данными. Он располагается между потребителем данных и базой данных. В OLE DB все провайдеры представляют данные в табличном формате (аналогичном тому, в котором хранятся данные в реляционных СУБД и файлах электронных таблиц), в виде виртуальных таблиц. Провайдер данных выполняет следующие функции:

получение от потребителя запросов на получение или модификацию данных;

получение данных из базы данных или их модификацию в базе данных;

возвращение данных потребителю.

Примером провайдеров данных является провайдер Microsoft Jet 4.0 OLE DB Provider, который используется для доступа к данным Microsoft Access, а также к данным I-ISAM (Installable Indexed Sequential Access Method), файлам рабочих книг Excel, хранилищ данных Microsoft Outlook и Microsoft Exchange, таблиц dBase и Paradox, текстовым файлам, файлам в формате HTML и др. Еще один пример OLE DB-провайдера -- Microsoft OLE DB Provider for SQL Server, применяемый для доступа к базам данных Microsoft SQL Server 6.5 и 7.0.

Провайдер сервисов (или сервисный компонент) реализует расширенную функциональность, не поддерживаемую обычными провайдерами данных, например сортировку и фильтрацию данных, обработку транзакций и SQL-запросов, управление курсором и др. Сервисный компонент может обращаться к хранилищу данных непосредственно или с помощью соответствующего провайдера данных -- в этом случае провайдер сервисов является одновременно и провайдером, и потребителем. Например, сервисные компоненты, такие как Microsoft Cursor Service for OLE DB и Microsoft Data Shaping Service for OLE DB, могут использоваться совместно с провайдерами данных OLE DB для расширения их функциональности.

С рядом продуктов Microsoft поставляется набор MDAC (Microsoft Data Access Components), в который входит ряд провайдеров.

Таблица 4. Список провайдеров, доступных в MDAC

Провайдер	Описание
Microsoft OLE DB Provider for ODBC Drivers	Позволяет осуществить доступ к любому ODBC-источнику
Microsoft Jet 4.0 OLE DB Provider	Применяется для доступа к данным Microsoft Access и некоторых других СУБД
Microsoft OLE DB Provider for SQL Server	Используется для доступа к данным Microsoft SQL Server
Microsoft OLE DB Provider for Oracle	Используется для доступа к данным Oracle
Microsoft OLE DB Provider for Internet Publishing	Используется для доступа к Web-серверам и ресурсам, обслуживаемым Microsoft FrontPage или Microsoft Internet Information Server
OLE DB Provider for Microsoft Directory Services	Применяется для доступа к гетерогенным службам каталогов с помощью Microsoft Active Directory Service Interfaces (ADSI)
Microsoft OLE DB Provider for Microsoft Index Server	Предоставляет доступ «только для чтения» к файловой системе и данным Web, индексированным с помощью Microsoft Indexing Service
Microsoft OLE DB Simple Provider	Используется для доступа к текстовым файлам
Cursor Service for OLE DB	Расширяет функциональность курсора
Data Shaping Service for OLE DB	Применяется для создания связей между наборами данных и получения иерархических наборов данных
OLE DB Persistence Provider	Используется для сохранения наборов данных в форматах ADTG (Advanced Data Table Gram) или XML (eXtensible Markup Language)
OLE DB Remoting Provider	Позволяет обращаться к провайдерам данных на удаленных компьютерах
Microsoft OLE DB Provider for OLAP Services	Применяется с расширением ADO Multi-Dimensional (ADO MD) для доступа к многомерным данным, созданным с помощью Microsoft SQL Server 7.0 OLAP Services

ADO представляет собой высокоуровневый программный интерфейс для доступа к OLE DB-интерфейсам. Он позволяет манипулировать данными с помощью любых OLE DB-провайдеров, как входящих в состав Microsoft Data Access Components некоторых других продуктов Microsoft, так и произведенных сторонними производителями. ADO содержит набор объектов, используемых для соединения с источником данных, для чтения, добавления, удаления и модификации данных.

Объект ADO Connection применяется для установки связи с источником данных. Он представляет единственную сессию. Этот объект позволяет изменить параметры соединения с базой данных, а также начать или завершить транзакцию. Используя объект Connection, мы можем выполнять команды (например, SQL-запросы) с помощью метода Execute. Если команда возвращает набор данных, автоматически создается объект Recordset, который возвращается в результате выполнения этого метода.

Объект Error используется для получения сведений об ошибках, возникающих в процессе выполнения.

Объект Command представляет собой команду, которую можно выполнить в источнике данных. Команда может содержать SQL-предложение или вызов хранимой процедуры. В последнем случае для определения параметров процедуры может быть использована коллекция Parameters объекта Command.

Объект Recordset - это набор записей, полученных из источника данных, и может быть использован для добавления, удаления, изменения, просмотра записей. Данный объект может быть открыт непосредственно или создан с помощью объектов Connection или Command.

Объект Field - это колонка в наборе данных, представленных объектом Recordset. Он может быть использован для получения значений конкретного поля, его модификации, извлечения метаданных, таких как имя колонки и тип данных.

Библиотека ADO 2.5, являющаяся составной частью операционной системы Windows 2000, содержит два новых объекта - Record и Stream.

Объект Record представляет одну запись внутри объекта Recordset и может быть использован для работы с гетерогенными и иерархическими данными. Объект Stream представляет двоичные данные, связанные с объектом Record. Например, если объект Record представляет собой файл, то его объект Stream должен содержать данные внутри этого файла.

6.6 Методика отладки и тестирования программы

Важным этапом разработки программы является её тестирование. Только тестирование может дать ответ на вопрос, все ли ошибки исправлены, реализует ли программа требуемые функции, не содержит ли она «дыр» в безопасности.

6.6.1 Особенности тестирования программного обеспечения

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

Процесс тестирования обычно включает в себя:

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

статическое тестирование текстов разработанных программ и данных на выполнение всех заданных правил построения и описания без исполнения объектного кода;

тестирование программы с её исполнением в объектном коде и с разными уровнями детализации: детерминированное, стохастическое, и тестирование в реальном масштабе времени;

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

разработку изменения программы с целью исключения причин отклонения результатов от эталонных;

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

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

6.6.2 Встроенные средства отладки и тестирования среды разработки

Среда Borland Delphi характеризуется рядом особенностей, влияющих на отладку. Среди них наличие обширного API, который предоставляет большой набор функций, при этом будучи хорошо отлаженным. Библиотека VCL содержит компоненты для создания множества стандартных объектов, причём в их надёжности не приходится сомневаться. Принцип модульности позволяет локализовать ошибку с точностью до модуля и, создавая тестовые модули, отладить отдельно взятый фрагмент.

ИСР Delphi содержит синтаксический анализатор, который ещё в процессе создания отлавливает ошибки в написании конструкций языка. Программист во время написания кода имеет возможность быстро получать доступ к именам свойств и методов классов, что исключает возможность указания неверного идентификатора.

Встроенный отладчик позволяет пошагово выполнять программу, отслеживая состояние объектов, значения переменных и порядок условных переходов. Это позволяет находить ошибки при работе с граничными значениями, логические недочёты алгоритма и оперативно исправлять. Поскольку в момент написания программы программисту доступен весь код, он имеет возможность вносить изменения «на лету». Крайне большое количество ошибок исправляется на этом этапе.

6.6.3 Основные факторы надёжности системы

Система выбора оптимальных туристских маршрутов имеет следующие наиболее важные аспекты надёжности работы:

корректность работы базы данных;

сходимость алгоритма за конечное время;

устойчивость к неверному вводу информации.

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

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

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