СОДЕРЖАНИЕ 2

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ 4

ВВЕДЕНИЕ 5

1. СПЕЦИАЛЬНЫЙ РАЗДЕЛ 8

1.1. Исследовательская часть 8

1.1.1. Обзор существующих программ для оптимизации 8

Генетические алгоритмы 9

1.1.3. Информационные потребности пользователя 17

1.2. Конструкторская часть 18

1.2.1. Требования, предъявляемые к системе 18

1.2.2. Структура входных и выходных данных 19

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

1.2.4. Модули комплекса 27

1.2.5. Общий алгоритм работы программы 29

1.2.6. Иерархия классов 32

1.2.7. Переменные в выражениях и их использование в программе 34

1.2.8. Основные алгоритмы и особенности программной реализации 35

1.2.9. Проверка отказоустойчивости программы 42

1.2.10. Проверка работы комплекса на контрольных примерах 49

1.3. Выводы 52

2. ТЕХНОЛОГИЧЕСКИЙ РАЗДЕЛ 53

2.1. Использование стандартных библиотек 53

2.1.1. Библиотека STL 53

2.1.2. Библиотека MFC 54

2.1.3. Применение библиотек STL и MFC в программе 56

2.1.4. Средство ClassWizard 57

2.2. Методы отладки и тестирования программ в среде Visual C++ 58

2.2.1. Инструментальные средства отладки среды Microsoft Visual Studio C++ 59

2.2.2. Встроенные средства языка для отладки программ 64

2.2.3. Отладка программного кода, содержащего STL и MFC 66

2.4. Приёмы объектно-ориентированного проектирования 68

2.4.1. Применение паттернов проектирования в программе 68

2.5. Выводы 69

3. ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКИЙ РАЗДЕЛ 71

3.1. Метод анализа иерархий 71

3.2. Метод парных сравнений. 72

3.2.1. Определение собственных векторов 75

3.3. Применение метода для выбора среды программировани 76

3.3.1. Характеристики сред программирования 76

3.3.2. Таблица сравнений важности критериев 82

3.3.3. Таблицы попарного сравнения сред разработки по каждому критерию 82

3.4. Результаты применения метода 84

3.5. Выводы 85

4. ПРОИЗВОДСТВЕННАЯ И ЭКОЛОГИЧЕСКАЯ БЕЗОПАСНОСТЬ 87

4.1. Опасные и вредные факторы, воздействующие на программиста 87

4.1.1. Микроклимат рабочей зоны программиста 88

4.1.2. Воздействие шума на программиста. Защита от шума 89

4.1.3. Уровень напряжённости электромагнитного поля 89

4.1.4. Электробезопасность. Статическое электричество 91

4.1.5. Освещенность рабочего места 93

4.2. Заключение 94

ЗАКЛЮЧЕНИЕ 95

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

ПРИЛОЖЕНИЯ 99

1. Исходный текст программы 99

2. Результаты испытаний 119

3. Руководство оператора 124

С оптимизацией человек сталкивается постоянно в своей жизни, порой даже не замечая этого. Мы выбираем, на каких станциях метро нам лучше пересесть в другой поезд, чтобы добраться до места назначения быстрее и с меньшим числом пересадок. Казалось бы, простая задача, с которой каждый из нас справляется с большим или меньшим успехом. Но даже это простой пример показывает, как неоднозначен выбор. Мы проводим оптимизацию по двум критериям – время и количество пересадок. А если таких критериев не 2, а, скажем, несколько десятков, причём один критерий зависит от определённого количества других? Тут уже не так просто справиться с задачей, найти лучшее сочетание значений этих критериев. Не помогает даже большой опыт человека в области, в которой решается задача оптимизации.

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

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

С задачей поиска такого решения хорошо справляются относительно недавно появившиеся эволюционные алгоритмы, в частности, генетические алгоритмы. В их основу положена теория эволюционного развития живых организмов [15] (если коротко – выживает особь, наиболее приспособленная к условиям окружающей среды). Один цикл работы генетических алгоритмов состоит в выборе продукционной группы родителей из текущей популяции и проведение с ней таких операций, как скрещивание и мутация, в результате чего формируется новое поколение особей. Процесс продолжается до тех пор, пока число поколений не достигнет заранее определённого или значение функции приспособленности системы для лучшей особи в двух соседних поколениях не будет отличаться на какую-то наперёд заданную малую величину. Эволюционные алгоритмы обладают одним замечательным свойством – с их помощью отыскивается именно глобальный максимум или минимум. Выход из точек, соответствующих локальным максимумам или минимумам, обеспечивается за счёт применения операции мутации. Генетические алгоритмы приспособлены к решению переборных непрерывных и дискретных задач и обладают хорошей скоростью сходимости, т.е. обеспечивают нахождение решения в приемлемые сроки.

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

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

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

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

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

1. Гагарина Л. Г., Зубов Н. Н., Стрижков А. В., Федотова Е. Л. Методические указания для подготовки дипломного проекта по специальности 220400 / Под ред. д.т.н. Нестерова. А. Э. –М.:МИЭТ, 2005. – 65 с.

2. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд. / Пер. с англ.– М.: «Издательство Бином», СПб: «Невский диалект», 1998. – 560 с., ил.

3. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. / Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 384 с.: ил.

4. Страуструп Б. Язык программирования СИ++ – М.: «Издательство Бином», СПб: «Невский диалект», 1999. – 991 с.

5. Паппас К. Х., Мюррей У. Х. Отладка в С++ – М.: «Издательство Бином», McGraw-Hill Companies, 2001. – 512 с.

6. Согомонян А. Статья STL - Standard Template Library – http://infocity.com.ua/

7. Nicolai M. Josuttis C++ Standard Library, The: A Tutorial and Reference – Addison Wesley, 1999 – 832 p.

8. Статья Уроки программирования на Visual C++ с помощью MFC – http://click.ipc.ru/~vc/html/Lessons

9. Гамма Э., Хелм Р. Джонсон Р., Влиссидес Дж. Приёмы объектно-ориентированного проектирования. Паттерны проектирования – Спб: Питер, 2004. – 366 с.: ил.

10. Валиков А. Технология XSLT – СПб: БХВ-Петербург, 2002. – 544 с.: ил.

11. Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 768 с.: ил.

12. Брилюк Д. Статья Обучение, самоорганизация и эволюция как методы в искусственном интеллекте – http://msk.nestor.minsk.by/kg/2000/kg0011/kg04712.html

13. Батищев Д. И., Исаев С. А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов –

http://bspu.secna.ru/Docs/~saisa/ga/summer97.html

14. Составитель Burger Y. Эволюционные вычисления – http://tz.ints.ru/?prog_ev

15. Конева К.К., Терехова Л.М. Появление эволюционных алгоритмов – Московский институт электроники и математики – http://nit.miem.edu.ru/cgi-bin/article?id=49

16. Статья Генетические алгоритмы: стратегии отбора – http://qai.narod.ru/GA/strategies.html

17. Саати Т. Принятие решений. Метод анализа иерархий. М.: Радио и связь, 1993.

18. Хостинг обзор Статья Метод анализа иерархий – http://www.hostobzor.ru/manual/mai.php

19. Статья Технологии принятия решений: метод анализа иерархий –

http://www.citforum.ru/consulting/BI/resolution/

20. Каракеян В.И. Безопасность жизнедеятельности – М. – 1999.

21. СанПиН 2.2.2.542-96. Гигиенические требования к видеодисплейным терминалам, персональным электронно-вычислительным машинам и организации работы.

Примечаний нет.