Распараллеливание программы генерации расписания занятий

ID работы - 743954
программирование (курсовая работа)
количество страниц - 64
год сдачи - 2001

---

СОДЕРЖАНИЕ:

---

Содержание
1. ВВЕДЕНИЕ 4
2. ПОСТАНОВКА ЗАДАЧИ 6
3. СИСТЕМНЫЕ ТРЕБОВАНИЯ 7
3.1. ТРЕБОВАНИЯ К АППАРАТУРЕ И ПРОГРАММНОМУ ОБЕСПЕЧЕНИЮ 7
3.2. ТРЕБОВАНИЯ К ПОЛЬЗОВАТЕЛЮ 7
4. ОПИСАНИЕ СЕРВЕРНОЙ ЧАСТИ 8
5. ОПИСАНИЕ КЛИЕНТСКОЙ ЧАСТИ 13
6. ВЗАИМОДЕЙСТВИЕ КЛИЕНТОВ С СЕРВЕРОМ 16
7. ИНТЕРФЕЙС 17
7.1. ИНТЕРФЕЙС СЕРВЕРНОЙ ЧАСТИ 17
7.2. ИНТЕРФЕЙС КЛИЕНТСКОЙ ЧАСТИ 24
8. ОБМЕН ИНФОРМАЦИЕЙ МЕЖДУ КЛИЕНТАМИ И СЕРВЕРОМ 26
9. ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО ПОДХОДА К РЕШЕНИЮ ЗАДАЧИ ГЕНЕРАЦИИ РАСПИСАНИЯ 30
9.1. ИСХОДНЫЕ ДАННЫЕ 31
9.2. ВЫХОДНЫЕ ДАННЫЕ 31
9.3. ТИПЫ И СТРУКТУРЫ ДАННЫХ 32
9.4. ГЕНЕРАЦИЯ НАЧАЛЬНОГО ПОКОЛЕНИЯ 34
9.5. МЕТОДЫ ЭВОЛЮЦИИ 35
9.5.1. Проверка правильности хромосом 35
9.5.2. Кроссовер 36
9.5.3. Мутация 36
9.5.4. Схема эволюции 37
9.5.5. Весовая функция 38
9.6. СТРУКТУРА ВХОДНОГО ФАЙЛА 41
9.7. СТРУКТУРА ФАЙЛА СО СХЕМОЙ РАСПИСАНИЯ 41
10. ЗАКЛЮЧЕНИЕ 43
11. ПРИЛОЖЕНИЯ 44
11.1. ИНТЕРФЕЙС СЕРВЕРА 44
11.2. ИНТЕРФЕЙС КЛИЕНТА 49
11.3. ЧТО ТАКОЕ «ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ» 50
11.4. ИСПОЛЬЗОВАНИЕ DIRECTPLAY 55
11.4.1. Краткий обзор 55
11.4.2. Архитектура DirectPlay 55
11.4.3. Использование DirectPlay 56
11.4.4. Управление сеансом 57
11.4.5. Управление игроками 58
11.4.6. Управление группами 58
11.4.7. Описание класса TCustomDXPlay 59
11.5 ДИАГРАММА ИСПОЛЬЗОВАНИЯ КЛИЕНТА 61
11.6. ДИАГРАММА ВАРИАНТОВ ИСПОЛЬЗОВАНИЯ СЕРВЕРА 61
11.6. ДИАГРАММА ВАРИАНТОВ ИСПОЛЬЗОВАНИЯ СЕРВЕРА 62
12. ЛИТЕРАТУРА 63

---

ВВЕДЕНИЕ:

---

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

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

---

СПИСОК ЛИТЕРТУРЫ:

---

12. Литература 1. «Генетические алгоритмы: почему они работают?» Компьютерра, 11/1999 2. НейроПроект. «Генетические алгоритмы» http://www.neuroproject.rugenealg.htm 3. ИКИ РАН «Генетические алгоритмы», http://www.iki.rssi.ru/ehips/genetic.htm 4. http://www.idisys.iae.nsk.su/ 5. Исаев С.А. «Популярно о генетических алгоритмах», http://www.chat.ru/~saisa/ga/ga-pop.html 6. Исаев С.А. «Обоснованно о генетических алгоритмах», http://www.chat.ru/~saisa/ga/text/part1.html 7. Редько В.Г. «Прикладное эволюционное моделирование. Генетический алгоритм. Оценка эффективности генетического алгоритма», http://www.keldysh.ru/BioCyber/Lecture1.html 8. MSDN 2001. Platform SDK: DirectX 8.0 for C/C++. Introduction To DirectPlay. Microsoft Corporation, April 2001. 9. MSDN 2001. Platform SDK: DirectX 8.0 for C/C++. Understanding DirectPlay. Microsoft Corporation, April 2001. 10. MSDN 2001. Platform SDK: DirectX 8.0 for C/C++. Using DirectPlay. DirectPlay. Microsoft Corporation, April 2001.
Цена: 750.00руб.