|
озглянемо ГА більш детально:1. Ініціалізація, або вибір початкової популяції хромосом. Полягає у випадковому виборі заданої кількості N хромосом (особин).2. Оцінювання пристосованості хромосом в популяції полягає у розрахунку функції пристосованості для кожної хромосоми pS (Xi). Приймається, що функція пристосованості завжди приймає невід'ємні значення. Звичайно знаходиться максимум цієї функції.Рис.2.1 Алгоритм класичного ГА.3. Перевірка умови закінчення алгоритму. Алгоритм може бути закінчений, якщо його виконання не приводить до покращення отриманого результату або через певний проміжок часу. .4. Селекція хромосом полягає у виборі на основі функції пристосованості тих хромосом, які будуть приймати участь у створення нащадків, тобто нового покоління. Такий вибір виконується згідно принципу природного відбору, за яким найбільші шанси на створення потомства мають хромосоми з найвищими значеннями функції пристосованості. Існують різні методи селекції. Найбільш популярним вважається метод рулетки. Кожній хромосомі ставиться у відповідність сектор колеса рулетки, величина якого пропорційна до функції пристосованості даної хромосоми. Ймовірність селекції хромосоми Xi, i=1. N (для випадку, що функція F максимізується):.Таким чином, ймовірність селекції найбільша для хромосом з великим значенням функції пристосованості. У результаті селекції формується батьківська популяція з чисельністю N у яку особини з великим значенням pS (Xi) можуть увійти кілька разів, а з малим значенням pS (Xi) - жодного.5. Використання генетичних операторів до відібраних у результаті селекції батьківських хромосом приводить до створення популяції нащадків. В класичному ГА використовують два основних генетичних оператора: оператор схрещування (crossover) і оператор мутації (mutation). Як і живих організмах, ймовірність мутації звичайно дуже мала (рм<0,1).В ГА мутація може виконуватися на популяції батьків перед схрещуванням або на популяції нащадків, утворених у результаті схрещування.Оператор схрещування. На першому етапі схрещування вибиваються пари хромосом з батьківської популяції. Операції схрещування полягають у обміні фрагментами ланцюжків між двома батьківськими хромосомами (рис.2.2). Далі для кожної пари вибирається позиція гена (локус) в хромосомі, який визначає точку схрещування. Якщо хромосома містить L двійкових чисел, то точка схрещування LK вибирається випадковим чином з інтервалу [1, L]. В результаті схрещування утворюються два нащадки:1) нащадок, хромосома якого на позиціях від 1 до LK складається з генів першого предка, а позиції від LK+1 до L - з генів другого предка.2) нащадок, хромосома якого на позиціях від 1 до LK складається з генів другого предка, а позиції від LK+1 до L - з генів першого предка.Рис.2.2 Умовна схема кросовера6. Формування нової популяції. Хромосоми, отримані у результаті генетичних операторів до популяції предків, утворюють нову популяцію. Така популяція стає поточної для даної ітерації k ГА. На кожній ітерації розраховується значення функції пристосованості для всіх хромосом. В результаті перевірки умови закінчення ітерацій відбувається або зупинка алгоритму, або перехід до нового кроку ГА - селекції. В результаті селекції вся попередня популяція замінюється популяцією нащадків з кількістю N. Етап схрещування і мутації також називається еволюцією, на якому відбувається рекомбінація генів у хромосомах.7. Вибір найкращої хромосоми. Найкращою вважається хромосома з максимальним значенням функції пристосованості.Головний фактор еволюції - природний відбір, тобто природна селекція, приводить до того, що виживають найбільш пристосовані особини.Генетичний алгоритм є комбінованим методом. Механізми схрещування і мутації в якомусь значенні реалізують переборну частину методу, а відбір кращих рішень - градієнтний спуск. Така комбінація дозволяє забезпечити стійко хорошу ефективність генетичного пошуку для будь-яких типів задач.2.2.4 Нечіткі системиЗа допомогою нечітких множин можна формально визначити неточні та багатозначні поняття, такі як "висока температура", "молодий чоловік", "середній зріст" або "велике місто" [3]. Перед формулюванням визначення нечіткої множини необхідно задати так звану область значень (universe of discourse). В випадку неоднозначного розуміння "багато грошей" великою буде визнана одна сума, якщо ми обмежимось діапазоном [0, 1000 грн.] та зовсім інша в діапазоні [0, 1000000 грн.]. Область значень, далі будемо називати простором або множиною, буде позначатись символом Х. Необхідно пам'ятати, що Х - чітка множина.Визначення. Нечітка множина А в деякому (не порожньому) просторі Х, що позначається як А Х, називається множиною парA = { (x,A (x)); xX} (2.1)деA: X [0,1] (2.2)функція приналежності нечіткої множини А. Ця функція приписує кожному елементу х Х степінь його приналежності до нечіткої множини А, при цьому можна виділити три випадки:1) A (x) = 1 означає повну приналежність елемента х до нечіткої множини А, тобто х А;2) A (x) = 0 означає відсутність приналежності елемента х до нечіткої множини А, тобто х А;3) 0 < A (x) < 1 означає часткову приналежність елемента х до нечіткої множини А.В літературі застосовується символьне описання нечітких множин. Якщо Х - це простір з кінцевою кількістю елементів, тобто Х = {x1, …, xN}, то нечітка множина А Х записується у вигляді (2.3)Приведений запис має символьний характер. Знак "-" не означає ділення, а означає приписування конкретним елементам х1, …, хn степенів приналежності A (x1),…, A (xn). Іншими словами, запис. (2.4)означає пару. (2.5)Так само знак "+" в виразі (2.3) не означає операцію додавання, а інтерпретується як множинне сумування елементів (2.5). Слід зазначити, що так само можна записувати і чіткі множини. Наприклад, множину шкільних оцінок можна символічно записати якD = 2 + 3 + 4 + 5, (2.6)що рівнозначно записуD = {2, 3, 4, 5}. (2.7)Якщо Х - це простір з нескінченною кількістю елементів, то нечітка множина А Х символічно записується у виглядіПриклад. Якщо X = R, де R - множина дійсних чисел, то множину дійсних чисел "близьких до числа 7", можна визначити функцією приналежності вигляду (рис.2.3). (2.8)Тому нечітка множина дійсних чисел, "близьких до числа 7", описується виразом. (2.9)На рисунку 2.3 представлені дві функції приналежності нечіткої множини А дійсних чисел, "близьких до числа 7". а) б)Рис.2.1 Функції приналежності нечіткої множини дійсних чисел, "близьких до числа 7"2.3 Опис організації вхідних та вихідних данихВ якості вхідних (початкових) даних використано: навчальне навантаження викладачів (кількість занять для навчальних груп із визначених дисциплін); вимоги до послідовності проведення занять; пристосованість приміщень для проведення занять; поділ груп на підгрупи, умови їх об'єднання у потоки; вимоги викладачів до вільних пар або днів та ін. За змістом вхідні дані поділені на таблиці бази даних.Вихідними даними програми є допустимий варіант розкладу. Розклад являє собою таблицю, в якій стовпці відповідають певній навчальній підгрупі, а рядки - певній парі з вказанням назви дисципліни, прізвища викладача та назва приміщення.Проміжними вихідними результатами є варіант розкладу для покоління з номером k.2.4 Опис організації вибору технічних і програмних засобівРозроблений програмний продукт орієнтований на роботу в ОС Windows 95/98/NT/XP, тому для коректної роботи програми необхідне стабільне функціонування ОС. Програма створена в середовищі Borland Delphi 6.0. Для збереження початкових даних використано базу даних, яка створена за допомогою системи керування базами даних Firebird. Під час виконання програма звертається до програми Microsoft Excel з пакету Microsoft Office для збереження результатів, а також до реєстру ОС.До технічних засобів відносимо ПК, на яких буде проводитися складання розкладу. Мінімальними вимогами до апаратної частини ПК, за яких програма працюватиме та буде видавати достовірні результати, можна вважати:* процесор 6-го покоління Intel Celeron 533 МГц;* об'єм оперативної пам'яті 64 Мб.;* графічний адаптер S3 Savage 4 Мб.;* жорсткий диск ємністю 10 Гб.;* привід гнучких дисків (дисковод).2.5 Охорона праціРобоче місце (РМ) - це обладнаний технічними засобами (засобами відображення інформації, органами управління, допоміжним обладнанням) простір, де здійснюється діяльність виконавця (або групи виконавців).Удосконалення організації РМ є однією з умов, що сприяють підвищенню продуктивності праці, тому питанню організації РМ тепер приділяється велика увага.Основним обладнанням робочого місця користувача ЕОМ є монітор, клавіатура, робочий стіл, стілець (крісло); допоміжним - пюпітр, підставка для ніг, шафи, полиці та ін. Вимоги до них відображені у нормативних документах: ВСПиПРВЦ; ГОСТ 12.2 032-78; ГОСТ 22269-76.Робочі місця з ЕОМ повинні розташовуватися на відстані не менше як 1,5 м від стіни з віконними прорізами, від інших стін - на відстані 1 м, між собою на відстані не менше 1,5 м. При розміщенні робочих місць необхідно виключити можливість прямого засвічування екрана джерелом природного освітлення. Джерело природного освітлення (вікно) не повинно також потрапляти в зону прямого спостереження користувача.При розміщенні робочих місць з відеотерміналами та персональними ЕОМ необхідно забезпечити виконання наступних вимог:робочі місця з відеотерміналами та персональними ЕОМ розміщуються на відстані не менше 1 м від стін зі світловими прорізами;відстань між бічними поверхнями відеотерміналів має бути не меншою за 1,2 м;відстань між тильною поверхнею одного відеотермінала та екраном іншого не повинна бути меншою 2,5 м;прохід між рядами робочих місць має бути не меншим 1 м.Вимоги цього пункту щодо відстані між бічними поверхнями відеотерміналів та відстані між тильною поверхнею одного відеотерміналу та екраном іншого враховуються також при розміщенні робочих місць з відеотерміналами та персональними ЕОМ в суміжних приміщеннях, з урахуванням конструктивних особливостей стін та перегородок.Конструкція робочого місця користувача відеотерміналу (при роботі сидячи) має забезпечувати підтримання оптимальної робочої пози з такими ергономічними характеристиками: ступні ніг - на підлозі або на підставці для ніг; стегна - в горизонтальній площині; передпліччя - вертикально; лікті - під кутом 70 - 90 град. до вертикальної площини; зап'ястя зігнуті під кутом не більше 20 град. відносно горизонтальної площини, нахил голови - 15 - 20 град. відносно вертикальної площини.Якщо використання відеотерміналу та персональної ЕОМ є періодичним, то устаткування, як правило, розміщується на приставному столі, переважно з лівого боку від основного робочого столу. Кут між поздовжніми осями основного та приставного столів має бути 90-140 град.Висота робочої поверхні столу для відеотерміналу має бути в межах 680-800 мм, а ширина - забезпечувати можливість виконання операцій в зоні досяжності моторного поля.Екран відеотермінала та клавіатура мають розташовуватися на оптимальній відстані від очей користувача, але не ближче 600 мм, з урахуванням розміру алфавітно-цифрових знаків та символів.Розташовувати відеотермінал на робочому столі необхідно так, щоб поверхня екрана знаходилася на відстані 400-700 мм від очей користувача. Розташування екрану відеотерміналу має забезпечувати зручність зорового спостереження у вертикальній площині під кутом ±30 град. від лінії зору працівника.Клавіатуру слід розміщувати на поверхні столу або на спеціальній, регульованій за висотою, робочій поверхні окремо від столу на відстані 100 - 300 мм від краю, ближчого до працівника. Кут нахилу клавіатури має бути в межах 5 - 15 град.Рекомендується розміщувати елементи робочого місця таким чином, щоб витримувалася однакова відстань очей користувача від екрана, клавіатури, тримача документів. 3. Очікувані техніко-економічні показники3.1 Визначення трудомісткості розробки програмного продуктуАналіз різноманітних підходів до нормування процесу програмування говорить, про те що в якості основного фактору, який визначає трудомісткість розробки, треба прийняти розмір вихідного тексту запису алгоритмів та даних (кількість рядків програми) [4].Теоретичний термін розробки програмного продукту в місяцях обчислюється за формулою:TТ = 2,5 · NТВК0,32, (3.1)де NТВК - кількість тисяч вихідних команд.В якості вихідної команди приймемо рядок програми. Загальний розмір програмної частини дипломної роботи складає приблизно 4500 рядків. В нашому випадку TТ дорівнює:TТ = 2,5 · 4,50,32 = 4,05 (міс).Дійсний термін розробки Т=2,5 міс. менший за теоретичний, що свідчить про ефективність та професійність розробки програмного продукту.Продуктивність праці програміста визначається за формулою:П = 1000 · NТВК / Т, (3.2)де П - продуктивність праці розробника програмного продукту, вих. команд/міс.В нашому випадку продуктивність становить:П = 1000·4,5/2,5= 1800 (вих. команд/міс).Весь час, необхідний для написання роботи, можна підрахувати за формулою:Тзаг = Т + Топ + Тал + Тнал + Трук + Тдр, (3.3)де Топ - час на вивчення опису задачі з врахуванням кваліфікації програміста, Тал - час на створення алгоритму, Тнал - час на налагодження програми, Трук - час на підготовку рукопису, Тдр - час на підготовку друкованого документу. Ці величини визначаються з врахуванням трьох параметрів: kС - ступеню готовності виконавця до роботи, B - якості формулювання задачі (в залежності від доробок В приймається від 1,2 до 1,5) та Nтвк. Значення kС визначається в залежності від стажу роботи: для працюючих до 2 років kС=0,8; від 3 до 5 - 1,1-1,2; більш ніж 7 років - 1,5-1,6.Розрахунок ведеться за наступними формулами (в місяцях):Tоп = NТВК · В / (0,72 · 80 · kС), (3.4)Тал = NТВК / (0,720 · 25 · kС), (3.5)Тнал = NТВК / (0,48 · 25 · kС), (3.6)Трук = NТВК / (0,72 · 20 · kС), (3.7)Тдр = 0,75 · Tрук. (3.8)Приймемо k = 1,1 та B = 1,2. Розрахунок за формулами (3.4 - 3.8) дає такі результати:Tоп = 4,5 · 1,2/ (0,72 · 80 · 1,1) = 0,09 (міс),Тал = 4,5/ (0,72 · 25 · 1,1) = 0,27 (міс),Тнал = 4,5/ (0,48 · 25 · 1,1) = 0,34 (міс),Трук = 4,5/ (0,72 · 20 · 1,1) = 0,28 (міс),Тдр = 0,75 · 0,28 = 0,21 (міс).Час, необхідний для створення програми, за формулою (3.3) дорівнює:Тзаг = 3,7 місяці.Таким чином, затрати часу на створення програм та документації оцінюються приблизно в 3,5 місяця. Реальна цифра також приблизно 3,5 місяця.3.2 Визначення собівартості години роботи на ПКДля визначення собівартості години роботи ПК розраховуються витрати на експлуатацію комп'ютера Век. В їх склад входять витрати на електроенергію та амортизаційні відрахування.Витрати на електроенергію визначаються множенням витрат електроенергії за годину на вартість 1кВт год. електроенергії та на час роботи комп'ютера за рік. Витрати електроенергії визначається з паспортних даних комп'ютера. Для ПК на базі процесора Intel Intel Celeron 533 МГц вони складають 0,8 кВт год. Вартість 1 кВт години складає 24 копійок. Час роботи комп'ютера визначається множенням кількості робочих днів року на час роботи ПК в день:Троб = (365 - 104 - 6) * 8 = 2040 (год).Тоді вартість витрат електроенергії за рік складає:Sел = 0,8 · 2040 · 0,24 = 391,7 (грн).Норма амортизації дорівнює 10%, вартість комп'ютеру відповідає приблизно 2500 грн. Тоді амортизаційні витрати дорівнюють:Sам = 0,1 · 2500 = 250 (грн).Річна зарплата персоналу з окладом 550 грн. складає:Зр = 12 * 550 = 6600 (грн).Відрахування на соціальне страхування складають 3% від заробітної плати (2% - у фонд зайнятості, 1% - у пенсійний фонд):Всоц = 0,03 * 6600 = 198 (грн).Вартість витратних матеріалів складає 2% від вартості обчислювальної техніки:SВМ = 2500 * 0,02 = 50 (грн).Утримання та ремонт приміщень складає 3% від вартості ПК:Sрм = 2500 * 0,03 = 75 (грн).Таким чином, загальні затрати на експлуатацію ПК за рік складають:Век = Sел + Sам + Зр + Всоц + SВМ + Sрм = 7564,7 (грн).Собівартість години роботи на ПК визначається діленням суми витрат на кількість годин роботи комп'ютера в рік:C = Век / Троб = 7564,7/2040 = 3,71 (грн. /год). 3.3 Розрахунок витрат на створення програмного продуктуДля визначення договірної ціни розраховуються поточні витрати на виконання програмного продукту. Ці витрати розраховуються як сума прямих та накладних витрат на виконання дипломної роботи за весь період її написання.Прямі витрати, пов'язані з використанням ПК для виконання дипломної роботи, розраховуються виходячи з кількості годин Тгод роботи даної персональної ЕОМ, необхідних для виконання дипломної роботи та собівартості години її експлуатації:Впр = С · Тгод. (3.9)Кількість годин роботи ПК:Тгод = Троб·Тзаг / 12 = 2040 · 3,7/12 = 630 (год).В такому випадку прямі витрати:Впр = 3,71 · 630 = 2337,60 (грн).Накладні витрати включають в себе витрати на утримання персоналу, освітлення, опалення та інші витрати. Вони складають 40-50% від суми прямих витрат.Внакл = 2337,6 · 0,4 = 935,04 (грн).Поточні витрати на створення програмного продукту складаютьВППП = Впр + Внакл = 2337,60 + 935,04 = 3272,64 (грн). 3.4 Визначення договірної вартості на програмний продуктДоговірна вартість на програмний продукт визначається наступним чином:Впп = ВППП · (1 + Р / 100%) · К, (3.10)де Впп - витрати на виконання дослідження, передбаченого дипломною роботою, в грн., P - рівень рентабельності дослідження, К - коефіцієнт, що враховує заохочувальну надбавку за якість розробки.Ступінь рентабельності програми приймається рівною Р=20%.Заохочувальна надбавка за якість визначається в залежності від величини науково-технічного ефекту. Науково-технічний ефект - це інтегральний показник. Він включає в себе:рівень новизни,науково-технічний рівень дослідження та інше.Величина науково-технічного ефекту приймається рівною 15, тобто К=1.Таким чином, договірна вартість на програмний продукт:Впп = 3272,64 · (1 + 20% / 100%) · 1 = 3927,16 (грн).3.5 Розрахунок ефективності впровадження програмного продуктуРічний економічний ефект визначається за формулою:Ер = Вор * T - Вприв, (3.11)де Вор - витрати на одноразове розв'язування задачі в традиційних умовах (ручна обробка інформації), Т - періодичність розв'язування задачі (емпіричні дані відділу - 4), Вприв - приведені витрати.Витрати (в гривнях) при ручній обробці інформації визначаються за формулою:Вор = Т1 * A1, (3.12)де Т1 - розрахункова трудомісткість (в люд. год) обробки інформації, А1 - середньогодинна зарплата виконавця.За даними факультету Т1 = 40 годин, А1 = 8 грн.Таким чином, витрати складають:Вор = 40 · 8 = 320 (грн).Приведені витрати розраховуються за формулою:Вприв = В1 + Ен * Впп, (3.13)де В1 - річні експлуатаційні витрати на розв'язок задачі, Ен = 0,15 - нормативний галузевий коефіцієнт (враховує можливість використання програмного продукту протягом кількох років), Впп - договірна вартість на програмний продукт (розраховується за формулою 3.10).Експлуатаційні витрати розраховуємо за формулою:В1 = Воп * T, (3.14)де Воп - експлуатаційні витрати при одноразовому розв'язуванні задачі з використанням програмного продукту.Воп = t * R, (3.15)де t - час розв'язування задачі на ПК, С - собівартість години роботи на ПК. За результатами переддипломної практики t = 0,3 години.Воп = 3,71 · 0,3 = 1,11 (грн).Експлуатаційні витрати за формулою (3.14):В1 = 1,11 · 4 = 4,44 (грн).Звідси приведені витрати за формулою (3.13):Вприв = 4,44 + 0,15 · 3927,16 = 539,50 (грн).Річний економічний ефект від впровадження програмного продукту розраховуємо за формулою (3.11)Eр = 320 · 4 - 539,50 = 686,50 (грн).Річний економічний ефект розрахований при використанні програмного продукту на одному факультеті. При використанні розробленої програми на багатьох факультетах економічний ефект значно збільшиться.Порівняння трудомісткості при ручній та машинній обробці дає:k = Т1/t = 40/0,3 = 133,тобто трудомісткість розв'язку зменшується в 133 рази.В результаті застосування розробленого програмного продукту час, який витрачається на складання розкладу, зменшиться в 133 рази. Список використаних джерел 1. Володин В., Володина Н. Расписание - это просто или не очень просто. - [Електронний ресурс]. - tech. stolica.ru. 2. Танаев.С.В., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. - М.: Наука, 1989. - 327 с. 3. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И.Д. Рудинского. - М.: Горячая линия - Телеком, 2004. - 452 с. 4. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. - М.: Мир. 1976. - 162 с. 5. Вороновский Т.К., Махотило К.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. - Харьков: Основа, 1997. - 112 с. 6. Ковальчук В.М. Основи економічної теорії. - Тернопіль: 2003. - 203 с. 7. Руснак І.С., Бабюк А.В., Федорова О. Є. Охорона праці при роботі з комп'ютером. - Чернівці: Рута, 2005. - 128 с.
Страницы: 1, 2
|
