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

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Введение

2. Техническое задание

2.1 Наименование и область применения

2.2 Основание для разработки

2.3 Назначение разработки

2.4 Технические требования к программе

2.4.1 Требования к функциональным характеристикам

2.4.2 Требования к надёжности

2.5 Условия эксплуатации

2.6 Требования к составу и параметрам технических средств

2.7 Требования к информационной и программной совместимости

2.8 Требования к маркировке и упаковке

2.9 Требования к транспортированию и хранению

2.10 Специальные требования

2.11 Технико-экономические показатели

2.12 Стадии и этапы разработки

2.13 Порядок контроля и приёмки

3. Эскизный проект

3.1 Постановка задачи

3.2 Предварительные НИР

3.2.1 Обзор средств автоматизации туристского бизнеса.

3.3 Потребности пользователя

3.4 Требования к системе

3.4.1 Выполняемые функции

3.4.2 Требования к надёжности

3.4.3 Требования к аппаратной и программной совместимости

3.5 Структура входных данных

4. Технический проект

4.1 Общий алгоритм работы программы

4.2 Выбор платформы для проектирования и его обоснование.

4.3 Выбор метода решения задачи и обоснование

4.4 Уточнение общего алгоритма

4.5 Описание генетических алгоритмов

4.5.1 История появления эволюционных алгоритмов

4.5.2 Основы генетических алгоритмов

4.5.3 Возможности применения генетических алгоритмов

4.5.4 Математическая формулировка экстремальной задачи однокритериального выбора

4.5.5 Понятие “оптимальное решение”

4.5.6 Влияние параметров генетического алгоритма на эффективность поиска

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

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

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

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

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

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

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

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

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

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

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

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

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

6.1 Введение

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

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

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

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

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

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

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

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

6.6.4 Метод «силовой отладки»

6.6.5 Методы тестирования

6.6.6 Виды тестов

7. Организационно-экономическая часть

7.1. Введение

7.2 Анализ рынка туруслуг

7.3 Постановка задачи

7.4 Методы сегментирования

7.5 Расчёт сегментации

7.6 Выводы

8.Раздел по технике безопасности

8.1 Введение

8.2 Рабочее место турагента

8.3 Источники опасности и вредностей

8.4 Излучения экрана монитора

8.5 Микроклимат помещения

8.6 Шумы

8.7 Психофизиологические факторы

8.8 Нерациональное освещение.

8.9 Выводы

Заключение

Список литературы

Введение

Туризм является одной из ведущих и наиболее динамично развивающихся отраслей мировой экономики. За быстрые темпы роста он признан экономическим феноменом столетия минувшего и ему пророчат блестящее будущее в столетии грядущем. Согласно прогнозу Всемирной Туристической Организации (ВТО) рост туристической индустрии будет необратим в ХХI веке, и к 2020 году количество международных туристических посещений составит 1,6 биллиона единиц.

Как известно, данная отрасль хозяйства является фундаментальной основой многих развитых и развивающихся стран мира. И по данным все той же ВТО, вклад ее в мировую экономику (валовое производство услуг) оценивается в 3,5 трлн долл.(данные 1993 года), что эквивалентно 10,9% мирового валового внутреннего продукта. Путешествия и туризм обеспечивают свыше 11% международных инвестиций и приносят в казну государств в виде налоговых поступлений 302 млрд. долл.

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

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

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

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

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

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

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

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

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

1. Введение

В специальном разделе пояснительной записки я опишу исследование предметной области, постановку задачи, предварительные НИР. Также будут определены входные и выходные данные, разработаны алгоритмы работы системы. Будут проведены программометрические расчёты - конфигурация технических средств, время работы программы.

2. Техническое задание

2.1 Наименование и область применения

Наименование работы: «Информационная система выбора оптимальных туристских маршрутов».

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

2.2 Основание для разработки

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

Исполнитель: Кафедра “Информатика и программное обеспечение вычислительных систем” (ИПОВС) Московского государственного института электронной техники (МИЭТ).

2.3 Назначение разработки

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

2.4 Технические требования к программе

2.4.1 Требования к функциональным характеристикам

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

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

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

2.4.2 Требования к надёжности

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

2.5 Условия эксплуатации

Условия эксплуатации совпадают с условиями эксплуатации IBM/PC совместимых компьютеров. Требования к обслуживающему персоналу: знание принципов работы на компьютере на уровне пользователя

2.6 Требования к составу и параметрам технических средств

Необходимое аппаратное обеспечение:

IBM/PC совместимый компьютер

64 Мбайт ОЗУ

100 Мбайт свободного пространства на HDD

видеокарта и монитор, поддерживающие разрешение 800х600

мышь

2.7 Требования к информационной и программной совместимости

Программа работает под управлением ОС MS Windows 9x или 2000/XP. Требуется MS SQL Server для хранения БД о турах.

2.8 Требования к маркировке и упаковке

Не предъявляются.

2.9 Требования к транспортированию и хранению

Не предъявляются.

2.10 Специальные требования

Специальных требований не предъявляется.

2.11 Технико-экономические показатели

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

2.12 Стадии и этапы разработки

Основные этапы разработки - эскизный, технический и рабочий проект.

Эскизный проект.

Во время разработки эскизного проекта происходит:

Исследование документов в обороте турфирмы.

Структуризация информации.

Создание базы данных.

Исследование переборных методов.

Определение параметров выбранного метода.

Технический проект.

При разработке технического проекта происходит:

Подробно исследуется алгоритм выбранного метода

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

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

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

На этой стадии осуществляется:

Реализация методов классов.

Разработка интерфейса.

Отладка программы

Разработка документации

По окончании разработки рабочего проекта предоставляется:

Текст программы

Описание программы

Схемы и описания алгоритмов

Информация о пробном использовании

Описание применения

Руководство пользователя

2.13 Порядок контроля и приёмки

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

3. Эскизный проект

3.1 Постановка задачи

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

3.2 Предварительные НИР

3.2.1 Обзор средств автоматизации туристского бизнеса

В туристском бизнесе применяется довольно большой спектр программ для автоматизации. Небольшие компании могут ограничиваться программами MS Word, MS Excel и электронной почтой. Крупные компании, конечно, не могут существовать без использования систем учёта продаж, ведения бухгалтерии, CMS (content management system) сайтов. Для этих целей используются, например, следующие программные продукты.

Программный комплекс «Мастер-Тур»

Разработка компании «Мегатек» является абсолютным лидером среди программ, автоматизирующих деятельность как агентов, так и операторов.

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

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

1С.Предприятие

Программа 1С.Предприятие кроме стандартной бухгалтерской программы представляет среду создания приложений, в которой возможно создание целого ряда добавочных приложений, облегчающих общение продающих менеджеров с бухгалтерией. К примеру, в Бюро путешествий «Ориент» 1С.Предприятие используется для печати счетов, отслеживания предоставления документов агентствам. 1С.Бухгалтерия - крайне мощное средство автоматизации бухгалтерского учёта. Она предоставляет возможность отслеживания финансового состояния предприятия, печатать множество документов и отчётов. Программа оперативно обновляется при изменении в законодательстве РФ. Для конечного менеджера, имеющего дело с продажей программа практически бесполезна ввиду своей сложности и ориентированности на серьёзное знание бухгалтерии.

3.3 Потребности пользователя

Возможность задания требований, которым должен удовлетворять тур;

Возможность вывода полного описания выбранного тура с ценами;

Возможность повторить поиск, уточнив параметры;

Простой интерфейс;

Защита от несанкционированного копирования;

Возможность последующей интеграции с системами учёта продаж.

3.4 Требования к системе

3.4.1 Выполняемые функции

Система должны выполнять следующие функции:

Сбор пожеланий клиента относительно параметров тура;

Формирование критерия оптимальности;

Максимизация полученного критерия;

Вывод информации о полученном туре;

Ведение служебной базы данных, необходимой для работы.

3.4.2 Требования к надёжности

Для обеспечения надёжности, система должна:

Использовать хорошо выверенные параметры алгоритмов;

Использовать стандартные способы работы с базой данных;

Делать резервные копии базы данных (реализуется на уровне сервера);

Иметь защиту от несанкционированного копирования.

3.4.3 Требования к аппаратной и программной совместимости

Система должна работать на IBM/PC совместимых компьютерах под управлением систем Microsoft Windows. Должна быть возможность дальнейшего совершенствования системы и интегрирования её с существующими программными комплексами автоматизации туризма.

3.5 Структура входных данных

программный туристический прибыль продажа

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

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

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

Размещено на http://www.allbest.ru/

Рис.1. Виды отдыха

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

4. Технический проект

4.1 Общий алгоритм работы программы

Рис.2. Схема работы системы

4.2 Выбор платформы для проектирования и его обоснование

В качестве операционной системы для работы системы было выбрано семейство Microsoft Windows 9x/NT. Выбор был сделан по следующим причинам:

Эти операционные системы очень распространены, и большинство туристических компаний использует именно эти ОС.

Обширное API (Applications Programming Interface) для работы с GUI (Graphics User Interface) позволяет создавать удобные для пользователя интерфейсы без значительных затрат времени.

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

Высокая скорость работы с современными компьютерами.

Высокая надёжность (семейство NT).

В качестве среды разработки был выбран продукт фирмы Borland - Delphi7. Эта среда сочетает в себе множество преимуществ. Среди них:

RAD (Rapid Application Development) - система быстрого создания интерфейсов, позволяющая не тратить время на создание внешнего вида программы, а использовать API.

Наличие большого числа утилит, облегчающих написание программ - Database Desktop etc…

Поддержка всех операционных систем Windows семейств 9х и NT.

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

Возможность использования внешних компонентов, реализующих многие функции.

Встроенная справка содержит большое количество информации не только по работе со средой, но и по стандартным функциям Windows API.

4.3 Выбор метода решения задачи и обоснование

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

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

4.4 Уточнение общего алгоритма

Необходимо определить, каким образом применить этот алгоритм, чтобы он проявлял хорошую сходимость и обеспечивал быстрый и качественный поиск. Исходя из предположения, что клиенту нужен только один - самый лучший тур, будем рассматривать задачу поиска одного экстремума. Быстрый поиск одного экстремума может быть достигнут путём использования параметров, которые способствуют максимально быстрой сходимости за счёт манипулирования только особями, обладающими лучшей приспособленностью, при этом более «слабые» члены популяции не участвуют в формировании родительских пар и не выживают после процедуры отбора. Этого можно достичь путём применения селективного выбора пар и элитного метода отбора. Размер популяции в данном случае не имеет смысла увеличивать, поскольку он влияет на фактор «исследования», который в данной задаче не так важен, как фактор «использования». Правда, слишком маленький размер приводит к ситуации, когда алгоритм замыкается на локальном максимуме, далёком от глобального - слишком велика вероятность гибели полезных генов. При отказе от стратегии элитизма поиск превращается в обычный перебор, который сходится гораздо медленнее. Вероятность кроссинговера, как основного инструмента прогресса, достаточно велика. А вот излишняя вероятность мутации или инверсии только ухудшает сходимость. Опытным путём были установлены оптимальные вероятности: для кроссинговера - 0.8, для инверсии и мутации - по 0.1.

4.5 Описание генетических алгоритмов

4.5.1 История появления эволюционных алгоритмов

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

Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение видов", в 1859 году, стала началом этого изменения. Многие области научного знания в настоящее время наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась неправильной. Это было на пятьдесят лет до того, как теория наследственности начала распространяться по миру, и за тридцать лет до того, как "эволюционный синтез" укрепил связь между теорией эволюции и относительно молодой наукой генетикой. Однако Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, "спуск с модификацией". Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в Природе.

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

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

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

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

Конечно, на практике мы не можем разделять эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).

Конечно, эволюция биологических систем не единственный "источник вдохновения" создателей новых методов, моделирующих природные процессы. Нейронные сети (neural networks), например, основаны на моделировании поведения нейронов в мозге. Они могут использоваться для ряда задач классификации, например, задачи распознавания образов, машинного обучения, обработки изображений и др. Область их приложения частично перекрывается со сферой применения ГА. Моделируемый отжиг (simulated annealing) - другая методика поиска, которая основана скорее на физических, а не биологических процессах.

4.5.2 Основы генетических алгоритмов

Генетические Алгоритмы - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Например, ГА могут использоваться, чтобы проектировать структуры моста, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Они могут также использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере. Вполне реальный пример: израильская компания Schema разработала программный продукт Channeling для оптимизации работы сотовой связи путем выбора оптимальной частоты, на которой будет вестись разговор. В основе этого программного продукта и используются генетические алгоритмы.

Основные принципы ГА были сформулированы Голландом (Holland, 1975), и хорошо описаны во многих работах. В отличии от эволюции, происходящей в природе, ГА только моделируют те процессы в популяциях, которые являются существенными для развития. Точный ответ на вопрос: какие биологические процессы существенны для развития, и какие нет? - все еще открыт для исследователей.

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

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

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

Имеются много способов реализации идеи биологической эволюции в рамках ГА. Традиционным считается ГА, представленный на схеме.

НАЧАЛО /* генетический алгоритм */

Создать начальную популяцию

Оценить приспособленность каждой особи

останов := FALSE

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /* создать популяцию нового поколения */

ПОВТОРИТЬ (размер_популяции/2) РАЗ

НАЧАЛО /* цикл воспроизводства */

Выбрать две особи с высокой приспособленностью из предыдущего поколения для скрещивания

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

Оценить приспособленности потомков

Поместить потомков в новое поколение

КОНЕЦ

ЕСЛИ популяция сошлась ТО останов := TRUE

КОНЕЦ

КОНЕЦ

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

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

4.5.3 Возможности применения генетических алгоритмов

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

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

Однако нередки случаи, когда ГА работает не так эффективно, как ожидалось.

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

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

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

4.5.4 Математическая формулировка экстремальной задачи однокритериального выбора

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

Предположим, что конкретный объект (техническое устройство, физический или технологический процесс, экономическая система и т.д.) может быть охарактеризован конечной совокупностью существенных свойств, которые могут быть объективно измерены. Количественная оценка существенных свойств осуществляется с помощью величин, называемых параметрами. Можно выделить следующие типы параметров: c= (c₁..c_m) - внешние параметры, характеризующие внешнюю по отношению к объекту среду и оказывающие влияние на его функционирование; x=(x₁..x_m) - внутренние параметры, характеризующие свойства отдельных элементов объекта.

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

Объединенную совокупность внешних и внутренних параметров будем называть множеством входных параметров.

Величины, характеризующие свойства объекта в целом как системы, будем называть выходными параметрами (характеристиками), которые можно только измерять или вычислять, но непосредственно изменять нельзя. Обозначим их вектором ц=(ц₁..ц_m).

Управляемые переменные x и характеристики ц определяют существенные свойства исследуемого объекта, а внешние параметры c являются, как правило, константами и характеризуют внешнюю среду. При этом внутренние параметры x играют роль независимых переменных, а выходные параметры ц являются зависящими от них величинами. Будем считать, что соотношения, выражающие эти зависимости, заданы в виде “черного ящика”, который имеет n входов x_i, i=1..n и s выходов ц, i=1..s.

В процессе принятия решения значения управляемых переменных x могут варьироваться в некоторых пределах, определяемых системой неравенств:

,; , (2.1)

где -нижнее и верхнее предельно-допустимые значения, соответственно, для i-ой переменной и j-ой характеристики. Область управляемых переменных, в которой выполняется система ограничений (2.1), будем называть областью поиска D, а любой вектор x, принадлежащий множеству D - допустимым решением.

Для выбора из области поиска D одного или нескольких “лучших” допустимых решений часто приходится вводить критерий оптимальности Q - количественный показатель, посредством которого осуществляется объективное измерение в некоторой числовой шкале Y какого-либо одного наиболее важного для задачи принятия решения выходного параметра i. Здесь под измерением по шкале Y понимается отображение Q, которое каждому решению ставит в соответствие числовую оценку таким образом, чтобы отношения между числами сохраняли бинарные отношения предпочтения между решениями:

1) “предпочтительнее” тогда и только тогда,

когда Q() < Q();

2) “не менее предпочтительнее” тогда и только тогда,

когда Q() Q(); (2.2)

3) “эквивалентно” тогда и только тогда,

когда Q() = Q().

Из соотношений (2.2) следует, что механизм выбора “лучшего” решения сводится к отбору тех и только тех решений, которые доставляют наименьшее значение критерию оптимальности Q в области поиска D :

, (2.3)

где x- оптимальное решение; - наименьшее значение критерия оптимальности, получаемое при принятии оптимального решения.

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

4.5.5 Понятие “оптимальное решение”

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

 для всех (2.4)

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

для всех ,(2.5)

где - -окрестность точки локального минимума.

В случае многоэкстремальной функции (функции Q(x), имеющей несколько локальных минимумов в области поиска D) оптимальное решение задачи (2.3) является глобальным минимумом - наименьшим из всех локальных минимумов:

,(2.6)

где - к-ый локальный минимум функции Q(x);

l - число локальных минимумов в области поиска D.

В общем случае оптимальное решение задачи (2.3) может достигаться на некотором подмножестве допустимых решений D, удовлетворяющих условию:

=Q^* для всех . (2.7)

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

4.5.6 Влияние параметров генетического алгоритма на эффективность поиска

Операторы кроссовера и мутации

Одной из особенностей предлагаемого генетического алгоритма является отход от традиционной схемы "размножения", используемой в большинстве реализованных генетических алгоритмов и повторяющих классическую схему, предложенную Голландом. Классическая схема предполагает ограничение численности потомков путем использования так называемой вероятности кроссовера. Такая модель придает величине, соответствующей численности потомков, вообще говоря, недетерминированный характер. В качестве генетических операторов получения новых генотипов "потомков", используя генетическую информацию хромосомных наборов родителей я применял только один из двух типов кроссоверов - одноточечный. Вычислительные эксперименты показали, что даже для простых функций нельзя говорить о преимуществе одно- или двухточечного оператора. При решении более сложных задач, можно применять сразу оба варианта. Более того, было показано, что использование механизма случайного выбора одно- или двух точечного кроссовера для каждой конкретной брачной пары подчас оказывается более эффективным, чем детерминированный подход к выбору кроссоверов, поскольку достаточно трудно априорно определить который из двух операторов более подходит для каждого конкретного ландшафта приспособленности. Одноточечный более эффективен на тестовых функциях De Jong'а 2 и 5, на двумерной функции Griewank'а и на двумерной функции Растригина, однако для функции De Jong'а 3, функции Griewank'а и Растригина от 10 переменных можно говорить о преимуществе выбора двухточечного оператора. Для данной задачи было решено сначала реализовать одноточечный кроссовер, и как показала практика, его оказалось достаточно для хорошей сходимости, хотя в ряде случаев (функции Griewank'а, 10-мерная функция Растригина) применение случайного механизма в выборе кроссовера дало бы лучшие результаты по сравнению с детерминированными подходами.

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

Выбор родительской пары

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

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

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

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