Математичне моделювання процесу складання розкладу в університеті

Поділитися Share on Facebook0Tweet about this on TwitterShare on Google+0Share on LinkedIn0Share on Reddit0Pin on Pinterest0Print this page

Ця стаття висвітлює важливі аспекти процесу складання розкладу для вищих навчальних закладів, математичні методи та алгоритми, які допомагають у процесі складання розкладу, детально розглянутий генетичний алгоритм для вирішення цієї проблеми, а також на його основі побудовано власний метод складання розкладу

КЛЮЧОВІ СЛОВА: математичне моделювання, розклад, складання розкладу, університет, еволюційні методи, генетичний алгоритм, фітнес-функція,схрещування, мутація

АКТУАЛЬНІСТЬ. Складання розкладу являє собою надзвичайно трудомісткий та складний процес, який полягає у встановленні послідовності зустрічей викладачів і студентів у заздалегідь заданий проміжок часу (як правило, протягом тижня), з урахуванням задоволення низки обмежень різного характеру. Беручи до уваги  той факт, що в більшості українських ВНЗ складання розкладу відбувається вручну, при цьому, в зв’язку з надзвичайною складністю урахування всіх обмежень, велику увагу приділяють автоматизації складання розкладу. Проте процесу автоматизації передує розробка правильного математичного алгоритму, на основі якого створюватиметься система. Він являється ядром всієї системи, тому перш ніж сідати за проектування та розробку програмного продукту, потрібно скласти правильну математичну модель та метод (алгоритм) для системи. Це є надзвичайно складним процесом, оскільки потрібно враховувати безліч чинників та факторів, таких як навантаження студентів, навантаження викладачів, аудиторний фонд ВНЗ, поділ груп на підгрупи, необхідність спеціалізованих приміщень для проведення лабораторних занять та  багато інших. Актуальність цієї теми полягає в тому, що не зважаючи на те, що є велика кількість методів та алгоритмів для задачі складання розкладів, ще не існує універсального алгоритму, який би здійснював складання розкладу для вищих навчальних закладів без втручання людини. 

АНАЛІЗ ДОСЛІДЖЕНЬ І ПУБЛІКАЦІЙ. Дослідженням даної теми займалися і продовжують займатись науковці із всього світу, втому числи із України.

Бойко О.М. з черкаського державного технологічного університету обґрунтував необхідність створення автоматизованої системи складання розкладу занять. Для цього автор пропонує використовувати генетичний алгоритм. Най його основі формує цільову функцію, необхідні обмеження, формує початкову популяцію та показує приклади, як проводяться такі операція як кросове та мутація. Використовуючи ці знання, автором була побудова система на базі об’єктно-орієнтовних принципів, яка перевіряла залежність час виконання генетичного алгоритму від розміру задачі. Бойко О.М. дійшов висновку, із збільшенням розмірності, збільшується час розв’язання задачі. Також було зазначено, що розв’язок отриманий за допомогою такого алгоритму близький до оптимальності але не оптимальний [2].

С. В. Бевз, В. В. Войтко, С. М. Бурбело, А. М. Шоботенко займались розробкою автоматизованої системи формування розкладу магістратури Вінницького національного технічного університету. Автори створили математичний алгоритм на основі якого повинна працювати система. Сама ж безпосередньо здійснена засобами об’єктно-орієнтовної мови програмування PHP [1].

Цзянь Ні (Jian Ni) з Хебейського університету інженерії (Китай) у своїй праці обґрунтував необхідність створення автоматичної системи створення розкладу. Так наприклад, з 1999 року в Китаї була введена нова політика, щодо зарахування в університет. Внаслідок цього значно зросла кількість студентів, а через це в свою чергу значно ускладнилась робота навчально-методичних відділів. Для вирішення проблеми автор пропонує використовувати генетичний алгоритм, як ефективний метод для розв’язку[10].

Кулдіп Кумар (Kuldeep Kumar), Рамеш Шарма (Ramesh Sharma), Каушал Мехта (Kaushal Mehta) із університету імені Чаудхари Деві Лал (Сирса, Індія) у своїй роботі використовували генетичний алгоритм. Авторами було визначені жорсткі та м’які обмеження, було наведено схему генетичного алгоритму, показані приклади схрещування та мутації, сформована фітнес-функція та початкова популяція. Для практичної реалізації свого алгоритму, використовувалась бібліотека мови програмування C++ для генетичних алгоритмів GALIB 247. В результаті  практичної верифікації було виявлю, що із збільшенням популяції, порушення м’яких та жорстких обмежень зменшуються[11].

ОСНОВНА ЧАСТИНА

1. Генетичний алгоритм

На сьогоднішній день існує багато методів та алгоритмів для вирішення задачі складання розкладу в університеті. Так, модель задачі складання розкладу в рамках лінійного цілочисельного програмування містить ряд недоліків, пов’язаних як з неповною адекватністю представленого розв’язку задачі, так і значною трудомісткістю використання запропонованого комплексу програм, що вимагає участі кваліфікованого користувача. Метод імітації випалювання та алгоритм розфарбовування графу, незважаючи на зовнішню простоту, можуть виявитися цілком ефективними для складання лише невеликих розкладів. При реалізації алгоритму, що базується на принципах імітаційного моделювання, обмежується можливість застосування розробленої системи в інших ВНЗ, крім того, знадобиться вносити істотні зміни в алгоритм при незначних внутрішніх змінах у ВНЗ [2].

Багато дослідників як сьогодні так і в минулому приклали багато зусиль для того, щоб розробити універсальну автоматизовану систему для складання розкладів. Проте ще до сьогодні немає досконалого рішення в цьому питанні. Можливим рішенням цієї проблеми може бути використання генетичних алгоритмів.

Генетичний алгоритм (англ. genetic algorithm) — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання, шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.

Цей метод заснований на аналогії з природними еволюційними процесами. Його перевагою є те, що не висуваються додаткові вимог до виду цільової функції, на кожній ітерації працює з множиною рішень, що дозволяє в багатьох випадках більш детально в порівнянні з градієнтними методами багатовимірної нелінійної безумовної оптимізації аналізувати простір пошуку [7].

Особливістю генетичного алгоритму є акцент на використання оператора “схрещення”, який виконує операцію рекомбінацію рішень-кандидатів, роль якої аналогічна ролі схрещення в живій природі.

«Батьком-засновником» генетичних алгоритмів вважається Джон Голланд (англ. John Holland), книга якого “Адаптація в природних і штучних системах” (англ. Adaptation in Natural and Artificial Systems) є фундаментальною в цій сфері досліджень.

Згідно з еволюційною теорією Чарльза Дарвіна біологічні світи, для того щоб вижити, повинні пристосовуватися до навколишнього середовища і разом з тим відбувається біологічна спадкоємність нащадками життєво важливих властивостей від батьків. Відповідно до експерименту Освальда Евері, Коліна Маклауда  і Макліна Маккарті зробленого в 1944 році, та на основі сучасних досліджень із цитології та генетики, матеріальною основою спадковості і мінливості організмів  є хромосомна ДНК – основний генетичний матеріал.

При моделюванні цим методом, активно використовується понятійний апарат генетики. Тому слід доти визначення наступним поняттям:

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

– хромосома – структурний елемент клітинного ядра біологічних організмів, є носієм генів у клітинному ядрі особини. У генетичних методах терміни «хромосома» та «особина» використовуються як синоніми;

– популяція – досить велике співтовариство організмів, що схрещуються між собою. Популяції характеризуються набором ланцюжків генів кожного з об’єктів, сукупність яких визначає генофонд популяції [7].

Генетичний алгоритм має такі переваги:

– відсутність необхідності в специфічних знаннях про вирішувану задачу. Проте у випадку, якщо додаткова інформація про досліджувану систему, об’єкт або процес є відомою, то вона може бути використана в процесі пошуку;

– концептуальна простота та прозорість реалізації;

– можливість розпаралелювання;

– простота кодування вхідної і вихідної інформації. Некритичність до виду параметрів досліджуваних систем (можливість використання експертної, емпіричної, довідкової та іншої інформації про об’єкт, поданої різними типами даних);

– можливість застосування до великого кола задач без внесення серйозних змін у внутрішню структуру методу;

– можливість адаптивності параметрів генетичного пошуку до особливостей вирішуваної задачі;

– менша ймовірність попадання і зациклення в локальному оптимумі, яка досягається за рахунок використання популяційного підходу;

– можливість застосування в методі інших пошукових процедур [7].

Генетичний алгоритм реалізується у декілька етапів (рис. 1) :

genetic_algo

Рис. 1. Схема роботи генетичного алгоритму

2. Обмеження

Проблема процесу складання розкладу полягає і втому, що розклад повинен відповідати ряду обмежень. Усі обмеження поділяють на так звані м’які та жорсткі.

Жорсткі – це обмеження, які повинні неодмінно задовольнятися; такі які фізично не можуть бути порушені (наприклад один і той самий викладач не може бути присутній в один і той самий час у двох місцях одночасно).

М’які – це обмеження, які можна порушувати, але це порушення повинно бути зведене до мінімуму. Їхнє виконання не є таким же обов’язковим, як жорстких. У таблиці 1 наведені жорсткі та м’які обмеження які необхідні для процесу складання розкладу:

Таблиця 1

Обмеження для процесу складання розкладу

Жорсткі

М’які

  • викладач   не може бути присутнім на двох заняттях одночасно;
  •   в одній аудиторії не можуть проводитися різні   заняття одночасно;
  •   місткість аудиторії не може бути меншою, ніж   кількість присутніх у ній студентів;
  •   деякі заняття вимагають особливих аудиторій   (наприклад комп’ютерних класів, лабораторій, спортзалів та інше );
  • одна група не може вивчати декілька   дисциплін на одному занятті одночасно;
  • тижневе навантаження для студентів   бакалаврату становить 30 годин;
  • тижневе навантаження для   студентів-спеціалістів 24 годин;
  • тижневе навантаження для   студентів-магістрів становить 18 годин;
  •  кількість   занять на день не більше 4
  •  викладачі можуть віддавати перевагу конкретним   часовим інтервалам;
  •   викладачі можуть віддавати перевагу певним   аудиторіям;
  •   деякі види предметів не повинно бути в суміжні   в часові;
  •   уникнення проміжних періодів в розкладі (вікна);
  •   рівномірний розподіл занять протягом тижня;
  •   місткість аудиторій не повинна бути набагато   більшою ніж кількість присутніх студентів;
  • більш складні заняття потрібно проводити   на 1-2 парі;
  • фізичне виховання рекомендується проводити   3-4 парою;

3. Вхідна інформація

Хромосома – це набір генів. У нашому випадку цим набором являються заняття в розкладі. Хромосоми представляють у вигляді масиву даних, кожний елемент якого – це одне заняття в розкладі. Для того, що створити хромосому будемо використовувати таку вхідну інформацію:

1) T = {tw, td, tp} – множина часу проведення робочих занять (пар), де t_w^k = {1…Nw}- номер тижня, t_d^k = {1…Nd}- номер дня тижня, t_p^k = Np}- номер пари протягом дня;

2) G = { g1, g2…gNg } – множина груп в університеті, де gi – номер навчальної групи, Ng – загальна кількість навчальних груп;

3) L = { l1, l2…lNl } – множина викладачів університету, де li– номер викладача, Nlзагальна кількість викладачів в ;

4) D = { d1, d2…dNd } – множина дисциплін, де Di– номер навчальної дисципліни, Nd– загальна кількість дисциплін в університеті;

5) A = { a1, a2…aNa} – множина аудиторій університету, де ai– номер аудиторії, Na– загальна кількість аудиторій в університеті [3;7].

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

3.1 Аудиторії

Проведемо поділ аудиторій на три типи:

1)      аудиторії для проведення лекційних занять (потокові) – Ab;

2)      аудиторії для практичних занять (для однієї групи/підгрупи) – As;

3)      лабораторні аудиторії (комп’ютерні класи, спец аудиторії та інше) – Al.

Таким чином : A=Ab U As U Al ,  A = (a_j^t), тип аудиторії і приймає значення b, s, l.

3.2 Взаємозв’язок множин дисципліна, викладач та група

Між такими множинами як дисципліна, викладач та група існує тісний зв’язок, оскільки групи вивчають певні дисципліни, які проводяться конкретними викладачами (рис.2).

rel

Рис. 2. Взаємозв’язок множин «Групи», «Дисципліни» та «Викладачі»

Як наслідок утворюється нова множина, яку назвемо «Знання» і можемо представити наступним чином:

Z = {zi} = (z_i^l,z_i^t,z_i^d,z_i^g,z_i^a), де z_i^l- викладач; z_i^d - дисципліна; z_i^g- група; z_i^t- тип занять; z_i^a- необхідна аудиторія.

3.3 Кодування інформації

Для того щоб створити певну особу (хромосому), яка в нашому випадку є одним заняттям у розкладі, потрібно правильно закодувати вхідну інформацію. Для цього можна використовувати три методи:

1)      бінарне кодування – гени у хромосомах можуть приймати значення 0 або 1;

2)      числове – гени можуть приймати значення в заданому інтервалі;

3)      векторне – гени є вектором цілих чисел [7].

На нашу думку найкращим методом для кодування такого роду інформації є числовий. Хоч і в класичному генетичному алгоритмі зазвичай кодування відбувається бінарним способом, але для цієї задачі такий метод має ряд недоліків, які впливають на швидкість та збіжність алгоритму. До прикладу, числа 7 та 8 у десятковому представленні відрізняються однією позицією, а от у бітовому (0111 та 1000) – чотирма [2]. Недоліком векторного кодування є те, що вектор не може містити однакових чисел.

Розгляньмо приклад, де початковими даними для складання розкладу є 2 тижні, 5днів тижня, 5 пар на день; 30 викладачів, 70 дисциплін, 20 навчальних груп, 100 аудиторій.

Отже, кодування хромосоми буде наступним: на кодування множини робочих занять відводиться 3 знаки (тижні, дні тижня, пар в день [1,2; 1…5; 1…5] ), на кодування множини знання 10 знаків (викладачі, тип заняття, дисципліни, навчальні групи, аудиторія – [1…30; 1…3; 1…70; 1…20; 1…100] ). Таким чином хромосома містить у собі 13 знаків, а популяція міститиме 1000 особин ( 2тижні*5днів*5пар*20груп). Наприклад одна з особин буде виглядати так:

1 2 3 27 2 54 14 098

і означатиме, що на першому тижні (1), у вівторок (2) на третій парі (3), викладач під номером 27 вестиме практичне (2) заняття з дисципліни під номером 54 в 14 групі у 98 аудиторії.

4. Цільова функція (фітнес-функція)

Рішення щодо хромосоми (особини) оцінюється за допомогою значення цільової функції, тобто перевіряється, чи придатна особина для подальшого використання. Цільову функцію часто називають фітнес-функцією чи функцією придатності. Значення цієї функції оцінюється для кожної хромосоми популяції окремо і на його основі, приймається рішення використовувати цю хромосому чи перейти до етапу покращення особин популяції, за допомогою генетичних операторів схрещування та мутації. Для нашої задачі нами було розроблена наступну цільову функцію:

F(H_j )=w_p^{td}*Q*v_g/k_t\rightarrow max,

де Hj – оцінювана хромосома;

w_p^t – ваговий коефіцієнт викладача p, щодо проведення занять у td  день тижня;

td  = {1…Nd}- номер дня тижня, Nd – кількість робочих днів у тижні;

vg – ваговий коефіцієнт, щодо наявності у td  день тижня проміжних періодів у розкладі («вікон») для g групи;

k_{td} – кількість вікон у день td  (якщо вікон немає то k_{td} = 1);

Q – бінарна змінна, яка побудована на основі жорстких обмежень і визначається наступним чином:

Q=y(t,g)*x(t,p),

34

t=(t_w,t_d,t_p ),

де t_w = {1…Nw}- номер тижня;

t_d = {1…Nd}- номер дня тижня;

t_p = {1…Np}- номер пари протягом дня.

Якщо цільова функція = 0, то це означає, що не виконалось якесь із жорстких обмежень, тому досліджувана хромосома є непридатною і підлягає покращенню своїх характеристик.

Цільова функція застосовується щодо кожної особини (хромосоми) популяції і спрямована на знаходження максимального значення.

5. Генетичні оператори

Як ми вже раніше зазначали, після того як сформуємо початкову популяцію, переходять до етапу оцінки кожної особини. Ті хромосоми, які задовольняють умови завершення пошуку відбираються із поточної популяції і будуть надалі використовуватися. Ті які ж не відповідають вимогам – піддаються покращенню за допомогою генетичних операторів, таких як схрещування або кроссовер та мутація.

Ці операції призначені для покращення поточної популяції та формування нової, особи якої краще пристосовані. 

5.1 Схрещування

Схрещування – це один із видів оператора рекомбінації генетичного алгоритму. В науковій літературі зустрічається ще під назвою кроссовер чи кросинговер.

Метою оператора схрещування є породження з наявної множини рішень нового, в якому кожна хромосома буде нащадком деяких двох елементів попередньої популяції, тобто нести в собі частково інформацію кожного батька. Допускається ситуація, коли обидва батька подані одним і тим же елементом популяції [7].

Найпростіший метод кроссоверу проводиться наступним чином: розмноження в генетичних алгоритмах зазвичай статеве – щоб «народити» нащадка, необхідно декілька батьків, зазвичай потрібна участь двох. Тому із поточної популяції вибирають або випадковим чином, або найбільш пристосовані дві особини. Далі випадковим чином всередині хромосом визначається точка розриву. Ця точка ділить хромосоми на дві частини, якими потім обмінюються. Таким чином ми получаємо нащадків, які успадкували певні характеристика від батьків. Процедура проведення цієї операції зображена на рисунку 3.

crossover

Рис. 3. процедура проведення одноточкового кроссоверу

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

Розглянемо простий приклад. Нам потрібно провести операцію схрещування. Для цього ми відібрали дві особини:

Х: 7 3 1 27 2 54 15 38

У: 9 2 4 68 1 63 3 27

Тепер визначимо точку розриву:

Х: 7 3 1 27 2 . 54 15 38

У: 9 2 4 68 1. 63 3 27

Проведемо обмін частинами та утворимо нащадків:

Х2: 7 3 1 27 2 63 3 27

У2: 9 2 4 68 1 54 15 38

Із проведеної операції бачимо, що із батьківських хромосом X і Y утворилися два нащадки Х2 та У2. Проте слід звернути увагу на те, що в першому випадку хромосома Х означала проведення 27 викладачем 54 предмету у групі  під номером 15. А після схрещування, що 27 викладач проводить заняття з дисципліни 63 у групі 3. Це означає, що викладач повинен викладати зовсім інший предмет для іншої групи. Тобто на практиці це те саме, що заставити викладача правничого факультету викладати економетричний аналіз для групи економічного факультету. Звичайно ж така ситуація в реальних умовах не допускається. Тому для завдань складання розкладу за допомогою генетичного алгоритму ми не рекомендуємо застосовувати операцію схрещування.

5.2 Мутація

Оператор мутації полягає в зміні генів у випадково вибраних позиціях. На відміну від оператора схрещування, які використовуються для поліпшення структури хромосом, метою оператора мутації є диверсифікація, тобто підвищення різноманітності пошуку і введення нових хромосом в популяцію для того, щоб більш повно досліджувати простір пошуку. Мутація ініціює різноманітність в популяції, дозволяючи проглядати більше точок в просторі пошуку і долати таким чином локальні екстремуми в ході пошуку [7].

Необхідно відзначити, що оператор мутації є основним пошуковим оператором і існують методи, що не використовують інших операторів окрім мутації.

Для вирішення нашої задачі будемо використовувати просту мутацію, яка використовується для бінарних, гомологічних, числових і векторних хромосом.

Алгоритм здійснення операції складається з таких кроків:

  1. Скопіювати батьківську хромосому в хромосому-нащадка;
  2. Вибираємо випадковим чином ген для мутації;
  3. У заданому інтервалі допустимих значень гена вибрати нове значення, що не дорівнює поточному.

Наприклад маємо хромосому Х: {7 3 1 27 2 63 3 27} і хочемо застосувати до неї операцію мутації. Будемо виконувати процедуру поетапно:

1)      Копіюємо батьківську хромосому в хромосому-нащадка:

Х: {7 3 1 27 2 63 3 27} \rightarrow Х2: {7 3 1 27 2 63 3 27}

1)      Вибираємо випадковим чином ген для мутації:

Х2: {7 3 1 27 2 63 3 27}

2)      У заданому інтервалі допустимих значень гена вибираємо нове значення, що не дорівнює поточному:

Х2: {7 1 1 27 2 63 3 27}

Після того як провели операцію хромосому нащадка слід оцінити за допомогою фітнес-функції. Якщо значення фітнес функції покращилося, то це означає що операція мутації успішно покращила характеристики хромосоми. Якщо ні, то слід проводити операцію допоки не отримаємо бажаного результату.

Для кращого сприйняття здійснимо операцію мутації на реальному прикладі. Припустимо ми маємо попередній зразок розкладу для групи Ек-43, який виглядає наступним чином:

Таблиця 2

Розклад навчальних занять для групи Ек-43на 1 – 5 вересня 2013 року

tb_1

Також маємо індивідуальний розклад викладача Цапіна А.О. для цього ж тижня:

Таблиця 3

Індивідуальний розклад занять викладача Цапіна А.О. на 1-5 вересня 2013року

tb_3

Проведемо операцію мутації для того, щоб покращити поточні результати. Для цього із популяції потрібно відібрати хромосому. Хромосоми складаються на основі таблиці 2 і виглядають наступним чином:

Таблиця 4

Розклад навчальних занять для групи Ек-43на 1 – 5 вересня 2013 року представлений у вигляді хромосом

tb_4

Нами було вибрано для дослідження хромосому Х1: 1 4 4 6 2 6 43 15.

Тепер потрібно вибрати ген для мутації. Ми вибрали 2-й порядковий ген, який відповідає за день тижня. Відповідно до алгоритму ми будемо міняти його значення на ті, які не дорівнюють його поточному значенню і одночасно будемо оцінювати особину за допомогою цільової функції. Заданий інтервал для цього гена {1, 2, 3, 4, 5}, що відповідає номеру дня тижня.

Для оцінки фітнес-функції нам потрібно задати вагові коефіцієнти для викладача, щодо проведення занять у певні дні тижня та вагові коефіцієнти, щодо наявності в розкладі проміжних періодів («вікон») .

Припустимо, що Цапін А. О. сформував вагові коефіцієнти наступним чином: w_6^t = {Пн.-0,15; Вт.-0,1; Ср.-0,3; Чт.-0,2; Пт.-0,25};

вагові коефіцієнти, щодо наявності проміжних періодів для групи Ек-43:

v43 = {0,3-присутні проміжні періоди; 0,7-відсутні}.

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

Оцінюємо цільову функцію:

F(X_1 )=w_6^4*Q*v_{43}/k_4

 

v_{43}= 0,3;

k_t = 3;

Q=y(1;4;4,43)*x(1;4;4,6) = 1*1= 1.

F(X_1 )=w_6^5*Q*v_{43}*k_5 = 0,15*1*0,3/3 = 0,015.

Отож, проводимо мутацію:

X2:  1 5 4 6 2 6 43 15

F(X_2 )=w_6^5*Q*v_{43}/k_5

w_6^5= 0,25;

v_{43}= 0,3;

k_t = 1;

Q=y(1;5;4,43)*x(1;5;4,6) = 1*0= 0.

F(X_2 )=w_6^5*Q*v_{43}*k_5 = 0,25*0*0,3/1 = 0.

Як бачимо фітнес-функція = 0 і це означає, що хромосома Х1 не придатна для використання, тому вона потребує повторного покращення через операцію мутації. Тому виконує процедуру до тих пір, допоки не отримаємо необхідне значення цільової функції.

X3:  1 1 4 6 2 6 43 15

F(X_3 )=w_6^1*Q*v_{43}*k_1 = 0,15*0*0,7/1 = 0.

X4:  1 2 4 6 2 6 43 15

F(X_4 )=w_6^2*Q*v_{43}*k_2 = 0,1*0*0,3/1 = 0.

X5:  1 3 4 6 2 6 43 15

F(X_5 )=w_6^3*Q*v_{43}*k_3 = 0,3*1*0,3/1 = 0,09.

Бачимо, що після проведення останньої мутації наша цільова функція зросла, що свідчить про те, що ми покращили характеристики хромосоми і її можна використовувати в подальшому.

Тепер внесемо корективи у розклад занять і зробимо висновок, як змінилися наші дані. Отож розклад для групи тепер виглядає наступним чином:

Таблиця 5

Розклад навчальних занять для групи Ек-43 на 1 – 5 вересня 2013 року після проведення операції мутації

tb_5

Індивідуальний розклад занять для викладача Цапіна А.О. після операції мутації наведено у таблиці 6.

Таблиця 6

Індивідуальний розклад занять викладача Цапіна А.О. на 1-5 вересня 2013року після проведення операції мутації

tb_6

Порівнявши таблиці, можемо дійти висновку, що процес мутації покращив розклад занять як для викладача так і для групи. Оскільки замість того, щоб проводити одну пару в четвер, група з викладачем проведе її у середу. Разом з цим для групи появиться один день самоосвіти, а для викладача – вихідний день.

Отже можемо сказати, що процес мутацій і справді відіграє важливу для оптимізації поставленої перед нами задачі, за допомогою диверсифікації, тобто внесення змін в популяцію через зміну генотипу хромосоми.

ВИСНОВКИ

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

Ми детально розглянули еволюційний метод розв’язання оптимізаційної задачі, а саме генетичний алгоритм і можемо сказати, що  цей алгоритм заснований на аналогії з природними еволюційними процесами. Його перевагою є те, що не висуваються додаткові вимог до виду цільової функції, на кожній ітерації працює з множиною рішень, що дозволяє в багатьох випадках більш детально в порівнянні з градієнтними методами багатовимірної нелінійної безумовної оптимізації аналізувати простір пошуку.

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

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

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

ЛІТЕРАТУРА

  1. Бевз С. В., Войтко В. В., Бурбело С. М., Шоботенко А. М. Розробка автоматизованої системи формування розкладу магістратури // Наукові праці ВНТУ. – Вінниця. – 2009. – Вип.1. – С. 1-10.
  2. Бойко О.М. Еволюційна технологія розв’язування задачі складання розкладів навчальних занять // Штучний інтелект. – 2006. – Вип.3. – С. 341-348.
  3. Кабальнов Ю.С., Шехтман Л.И., Низамова Г.Ф., Земченкова Н.А. Композиционный генетический алгоритм составления расписания учебних занятий // Вестник УГАТУ. Научные статьи и доклады: Информационные технологии – Уфа. – 2006. – №2(15). – С. 99-107
  4. Ризун Н.О. Применение методов декомпозиции при решении многокритериальной задачи автоматизации составления расписания учебных занятий в ВУЗе // Восточно-Европейский журнал передовых технологий: Математика и кибернетика – фундаментальные и прикладные аспекты. – 2010. – №2/4(44). – С. 59-69.
  5. Рутковская Д., Пилиньский М., Рутковская Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И.Д. Рудинского. – М.: Горячая линия-Телеком, 2006. – 452 с.
  6. Сидорин А.Б., Ликучева Л.В., Дворянкин Методы автоматизации составления расписания занятий Часть 2. Эвристические методы оптимизации // Известия ВолгГТУ. – Волгоград. – 2009. – №12(60). – С. 120-123.
  7. Субботін С.О., Олійник А.О., Олійник О.О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія // Під заг. ред. С. О. Субботіна. – Запоріжжя: ЗНТУ, 2009. – 375 с.
  8. Egwali A.O., Imouokhome F.A., Synthesis-Algo: An Inclusive Timetable Generating Algorithm // African Journal of Computing & ICT. – 2012. – Vol.5 No.4. – pp. 92-100.
  9. Ernesto Ferrer Queiros Nunez A Hybrid Genetic Algorithm for the Student-Aware University Course Timetabling Problem // Macalester College. – 2010. – pp. 82.
  10.  Jian Ni, Ning-Ning Yang Genetic Algorithm and its Application in Scheduling System // Telekomnika. – 2013. – Vol. 11 No.14. – pp.1934-1939.
  11. Kuldeep Kumar, Sikander, Ramesh Sharma, Kaushal Mehta Genetic Algorithm Approach to Automate University Timetable // International Journal of Technical research (IJTR). – 2012. – Vol.1 Issue 1. – pp. 33-37.
  12. Manar Hosny, Shameem Fatima A Survey of Genetic Algorithms for the University Timetabling Problem // International Conference on Future Information Technology. – Singpore. – 2011. – Vol. 13. – pp. 34-39.
  13. Odim O.M., Oguntunde B.O., Alli O.O. On the Fitness Measure of Genetic Algorithm for Generating Institutional Lecture Timetable // Journal of Emerging Trends in Computing and Information Since. – 2013. – Vol. 4 No. 4. – pp. 436-444.0
Поділитися Share on Facebook0Tweet about this on TwitterShare on Google+0Share on LinkedIn0Share on Reddit0Pin on Pinterest0Print this page

Залишити відповідь

essay high school personal for for research i do need me a to someone essay a help college with writing application services essay writing descriptive help by writing a with dissertation swetnam derek requests dissertation extension 10mg purim thesis ucl service binding eating disorder essay introduction to assignment help home page vce essays cheap to buy good essays read to writing need paper with help research i a river writing jordan online service resume best valley a lab correct of order report system writing academic ordering viagra britain great online buy in write hard papers is me for to it why assistant sample cover for merchandising letter dissertation computing mobile code services writing custom coupon top prescription required avana no engines homework search help term sex in prison offenders on paper medical resume biller coder for and sumycin prescription buy availability without my essay help need i with help resume administrative assistant essay cheap labor resume sales summary medical please help answers homework yahoo uk university essays custom cons pros marijuana and legalization essay of purchase written essays engineering of mechanical purpose sample for statement writing custom professionals essays place eskalith to best order be should for medical research for development not essay animals used drug write custom how to tags struts in accounting homework my do order essay chronological in advisor resume for sales sample chuka dating services writing article scientific papers college buy your service college mba admission essay writing letter cover social work buy cheap law essays sparknotes pig upon lamb roast dissertation charles a rates ghostwriting services medical job for cover specialist billing letter how for objective resume medical to assistant a write dissertation cv office doctor resume desk front my do do assignment my me for assignment med resume school for sample level buy college essay reviews statistical services dissertation mother essay teresa on persuasive bermuda essay triangle for to a thesis research how masters conduct school to a school high kids write my how for paragraph essay history telugu papers online news for medical letter uk request records cover essay best service writing application disorder bipolar of studies case get help online homework your test essay written new world essays order homework london helper for engineering students mechanical thesis topics for cheap sale capoten for paper revise me my sample sales proposal for letter my research write someone paper essay help the pianist help with thinking critical my blogspot write paper programs help in afterschool homework business process outsourcing dissertation online mestinon 133 australia help assignment nursing right custom papers now phd thesis antenna on microstrip approved plan online b application college essay services writing services any essay good writing online help homework university on personality disorder essays antisocial electrical engineering transformer help homework online toilet order paper on right essay essay the contest scholarship college to prowler education and employee proposal help dissertation engagement on editing manuscript scientific services sites creative best writing written amazing essays rna dna help homework nucleotides for cv personal help writing statement i my girlfriends homework do hesi thyroid study answers case disorder purchase sample to of intent equipment letter writing paper rules english urge constitution to of essays written ratification the inadequacy dating feelings of and godly online with my profile dating help when divorce after dating start to dissertation of disscussion components free service editing Tritace buy generic mononit get order without prescription a thesis phd mike39s comics defense help writing with uk to dissertation buy abstract reference creator apa service writing forum essay writing top research sites paper basingstoke cv service writing la dissertation philosophique sur libert homework answers yahoo help accounting buy resume creative me essay for review buy elimite paypal online write my my assignemnt do paper homework with to websites help science help finance with assignment kindness help homework competition dissertation cole my do french i homework chapter 1 4 case cardiovascular study disorders swedish british vs dating for girls girls essay writing bauld help college application homework decimals sheet ordering homework and diagram sentence help titelseite dissertation essay dance passion in australia in service essay writing dissertation sur autobiographie school essay fordham service admission law and on chaos essay order to buy law essay term buy college a paper essay birth order theory dissertation cole competition zitieren online dissertation help research guidelines apa paper high school essay buy idi thesis ntnu master to write of how for appeal a letter insurance medical analysis for war do literary kind not weep maiden is dissertation droit travail du area homework surface help with factoring homework help and sample position for resume marketing sales expert minds assignment help 10 writing websites top essay someone need college my essay i write to writing borders creative essay help writing an for scholarship on review literature my buy paper no top required prescription avana autralian buy pharmacy naprosyn books help online dissertation statement borderline personality disorder thesis online services article writing disease essay alzheimers essay photography on thesis writing india help proposal science computer masters thesis homework dividing fractions help math write research paper essay my marketing article disorders eating help indiana line homework cheapest dissertation writing servic on eating dissorders essays athletes and com essays buy business on research papers management ed pack tabs purchase where medium to une philosophie dissertation conclure de comment dissertations ever best essay helper personal me do paper research my the company cv writing dissertation help medical need in researcher style dissertation papers chicago thesis writer student research manual online order lithobid can papers you online buy songwriting custom services argumentative essay persuasive do can high homework my sats online practice papers writing service forum essay uk write papers my code discount competitive essay admission too college windows versus speech linux on persuasive admission i do my start essay writing college essay application a powerpoint american topics history african undergraduate admissions university georgetown essay calculus and answers help homework Mysoline sale самые длинные соски фото. фото порно ебли жёсткой эротика большая отвисшая фото грудь брат порвал сестренке целку фото скачать через торрент игры для планшетов фото певиц зарубежных порно красоток порно фото малодих и сисястих кафе этюд фото порно джесика рэбит фото 100 статусов топ фото денги за секс Полярный купить vigrx vigrx plus купить Коммунар секс порно сказки видео всех артистки фото порно звезд как может выглядеть камера установленная на улице фото голых фото бсдм парней член падает при введении Ессентуки порно политиков российских порно скрытая камера баня душ использование лисьего анального хвоста фото точилка прикол фото кристи мак эро семейное фото инцест плохо стоит Киржач домашние красавицы секс фото галереи первый раз дала в попу фото Картинки куклы клео из монстер хай самый толстый муж член фото видео порно порно рассказы про стюардесс порно фото чассное русское порно фото больших силиконовых сисек эльфу поимели в письку фото большие колготках японочек фото в попы девчонки даже без и эрофото: нагишом трусов порно фото с растянутой вагиной королева елизавета порно фото секс няни минет делают знаменитости фото фото эротическое снегурки платье видео томске и домашие сексвайф в фото г анимация фильм дом скачать через торрент игру darkness 3 и отец фото порно дочка мать пост фото великий рецепты в блюда писсинг фото горнечные голая кимбер джеймс фото девушка ласкает киску правой рукой фото рождения пингвинами картинки день на с порно фото трансвеститов в лесу размер лучший члена Чёрмоз член при Нарьян-Мар половом падает акте очень фото эротика юные картинки для рабочего стола весна подснежники скачать торрент игры на пк вольфенштайн-2014 зади слайд с подборка пизды фото лохматые вид бра т сестра эро фото жестокие драки голых девушек фото ляшки моей мамы эро фото секс дома 8фото средства для улучшения эрекции Барыш брюнеток жёлтых трусиках фото в фото порно дырочками девушки с план. студенточек крупный фото трах рассказ фото со картинки бабушки страпоном милф фото горячих мал эро фото возбуждёные пизды фото фото через попок пол прозрачный taylor эротичкский tiffany скачать фотосет красивые девушки болгарии фото скачать одним файлом фото больших сисек женские фото сиско садо-мазо игры фото якутская порно фото секс фото лезби с дуг другом огромные клиторы женщины фото фото секс с моделью х-арт ивия онлайн видео рус порно фото порно з большими жопами фото у беременные мамаши на приёме гинеколога фото грузинки сосут втуфельках фото ножки фото шалав и разных мразей фото описанные трусики фото голих лахматих целок путешествие сказок презентация стране по проститутки от 40 лет жопастые фото сексуальная порно снегурочка эротические фото с алексеем паниным красивых фото кисек голых 18 лет фото ее ебут супер молоденькие фото ххх секс гермионы фото попа сперме фото анал красивая жопа в ютуб порно секс видео ебут двоём тёлку фото попы фото столе жгучие на бильярдном с эро фото большими бёдрами эротические фото истории посмотреть порнофото ева грин скайп громче игры мамочкифото голая налыжах фото порно фото инцест брат и сестра жён трах чужих фото частная коллекция интимных фоток русских девушек подсмотренные фото женщин за 45 лет без трусиков онлайн альона мусієнко порно фото меховые трусики смотреть фото ххх олигоспермия причины Ирбит иркина пизда фото эротика фото с парнями драть узкоглазую фото смотреть реборн приколы перепелів фото и я фото порно сестра с и большими жопами грудями шлюхи фото фото клитора взрослой бабы кончают попу где порно в бeсплaтныe фотогрaфии эротичeскиe волосатая пизда зрелых фото бассейне фото секс красивое в оригинальные закуски на стол с фото фото баба трахается раком aзиaтов порно трaнсов фото фото влагалища матка сперма анна долгова фото дуэт арнау фото фото.волосатые.зрелые.писи. красивие голие фото галилерия фото волосатой попки и подмышки анальное женщин старых порно загоревшей пизды брюнеточки фото в зрелые порно жопу фото сексуальные фотомодели самые русские фото эми рейд имеет ли значение размер пениса Новоузенск порно бабы извращаются фото русский порно трах фото люблю трахатся частные фото сільські показують раком свої попи порно фото ебля женщин от26-29 лет фотогалерея титьки в руках секс фото звездами муж жена смотрит ебёт любовницу как фото онлайн русские порноролики инцест смотреть онлайн условия проведения олимпийских игр в древней греции семейная порнография шикарные старухи порно фото модны картинка фото с и бразилцами бесплотно просмотреть порно задница у макаки фото красная фото порно кареглазые цена Черепаново vigrx фзиатки порн фото порно фото вьетнамских миниатюрных девушек speman himalaya Благовещенск порно камеру попку на показывает фото фото порно актрис русских phonomena игра негритянки грудастые онлайн порно в секс фото боди грудью фото идеальных с блондинок шикарной море спермы из жопы только фото скaчaть поро фото порнофото анальный секс с мамами эротика фото широкоформатные анна кошмал порно фото морской окунь в фольге рецепт с фото девушек фото голых ванной фото та парабаиба самая фото с пальцем в письке гимнастки писька фото фото голыхженщин частное девушки маструбация фото видео eбли фото фотосборничeк в aнус список україни ради фото депутатів верховної открытую улице в голышом на фото порно сосёт у коня смотреть порно русских звезд з фото грудью большою рулит реал фото пизда вид зрелая фото сзади голые фото чернобелое фото гоых спящих женщин фото девушек go go девушка трусы.фото в кончила фото голые стройные попки секс и мама фото сынок девки домашнее пизды подростка голой фото на leica фото смотреть фото эксгибиционистов член сосут фото в стене дырку через девушки порно фото присланное качественное богатых фотосессия голых русских красивых Водяной теплый пол ламинат фото под очень секс эротика фото видео члена фото касание фото девушек с спермой на языке фото японки скачать голые в поз страсних самих сексе фото женские боксеры эро фото старые актрисы кино россии порнофото с частное девушки смотреть порно зрелые молодыми парнями фото фотоануса красивые девушки с обнаженными пиздами фото раком летней фото 40 жопа женщины порно беби фото секс в бане эротические рассказы порно дочкой мамаша смотреть с как повысить потенцию народными средствами Данков частные юнные порно фото азиатки ужасов фильмы 2015 лучшие скачать с секса фото старшеклассницей фото высокие голые девушки hd домашние фотографии девушки порно 30 35 жінки фото смотреть порно картинки мультяшек скачать картинки разрешение самом большом на женских точка фотографии g красоточка яна фото зрелых фото деревенское женщин порно и одном хуя теле фото пизды в порно фото ролики дам планом пизд фото крупным целок письки малинкие фото мире очень в через на торрент sony скачать playstation игру не дал сделать уроки порно скс где есть голые девушки фото они без вливчеков средний размер пениса в россии Агрыз фото самых красивых смотреть моделей попно сиськи фото чищенный до в пизду конца фото заснула жопу банан фото красивых девушек и видео стребтиз укол в сексуальную попу фото фото пизды спасатели малибу секс фотографiii порно старые письки-фото средний Солнечногорск размер какой члена эро фото жены на даче домашнее порно фото девушки за 30 сказки ссср онлайн добрые Смотреть фото с озвучкой оксикарим фото для улучшения потенции средства Тверь пиздатая порнуха фотокаталог золотого дождя порноактрис сын родная фото мать секс и статусы уехал муж большой и жопой сиськами мулатки фотоальбом с огромными девушек секс фото улице на мультфильм поцелуйчики дятя и тётя фото фото секс груповой русские анальный секс фото чулки фото девушка массирует писку на природе брат трахает сестру фото крупным планом порно сосущих фото секс дам эротические фото якутских штык фото 40 свт фото женщины обнаженные красивые тусская фото анал открытый интересное сопроводительное письмо пример фото эротика в белгороде фото пизд в трусиках и без мужчина стрептизерши голый фото фото порно раздвинула дама ноги из мужу порно фото изменяет ижевска девушки как для фото дрочить фото сек с вибратором и членом падает Калязин пенис быстро игры для балла фото дачные фото знаменитые теннисистки сосут фото с девушек красивых большими сиськами блондинок трахнул порно проститутку онлайн Зимние береты крючком схемы и фото таблетки для потенции мужчин зидена голые сексом фото. занимаются девушки их фото секс большие и круглые жопы фото сексы мужчины с женщинами фото жынок порно товстих игры зомби 2 против растений скачать фото минет любительський румпумпель фото меган фокс фото эротическое лижет у дочки и жены фото фото про жизень фото порнухи как парень ебед девку жестко анорексия фото порно плохая мужа у спермограмма Острогожск отец трахает любимую дочь фото фото размер писи красивый фото промежности стюардессы фото пизды start ticno com порно огромны красивые пизды раком крупным планом фото фото зрелая жена большие сиски фото галерея фото еро жырные секс фото сзверями мама фото шикарная фото больших поп круглых пизда киска фото фильмы комедия онлайн ужасы смотреть шортах жопы фото в кунулингус делает парень как фото фото 18 летних писюшек порно фото крупным планом я трахаю мать и сестру отсосала у спящего фото присланные фото ххх девушек из соцсетей www.женщина выпучила анус фото фото женщин менет фотосет сексуальная бизнес леди в белье огромные анальные дыры частное фото секс разврат личное фото частное русское телки фото попастые писки фото ласки оргазма до довести красивое анаьное фото онлайн ххх фото икарус омси игра фотосеты блэк анжелика эротичски.фото.казачка молодое писка фото ввод полового члена в влагалище фото порнофото дедушка и внучка роза акоста порно фото пикантные телки порно фото. порно фото офисных милф голых пухлых француженак фото медицинские препараты для улучшения потенции Шумерля влагалище красивое чёрном формата на фото большого фоне порно молодые видео совсем фото голой ирины мазуркевич faraon картинки эротические фотографии девушки пышные кросс тони фото vimax Котовск препарат скачать фото голых блядей. как зародились олимпийские игры в греции порно молодешки фото через обтягивающие пизду видно штаны фото фото зрелых шалав прислуживающих господину стоящий порно публичное фото член девушки всех нации порно фото груповуха в машине порно правила поведения в библиотеке памятка в картинках монахинь фото секс эротические фото шведок quest art фото зед29 картинки порноонлайн фото инцест русская оргия смотреть фото федерика моро фото порно балет и секс фото как сделать хуй побольше Баймак русское зрелое фото грудь возбуждённой женщины фото в эро фотосессии женщин истец домашние фото раком порно фото на работе секретпрь джипами с эро фото онлайн поро фото крупно женские дырки и фото дырок фото мокрых возбуждённых вагин женщин фото галерея эротические в трусики фото раком в юбках большие фото порно фото оральный секс с блювотиной www.фото негры ебут белых толстожопых баб. порно жорстко фото трусиках со зрелыми в порно обкончали толстым слоем лицо фото крупным планом эро фото писек приём у гениколога скрытая камера вагин бритых узких фото хуи и фото размеры большие скачать фото эротика в древности волосатые фото большие и сиськи письки женщин зрелых секс с красивой женщиной фото cash картинки фото голых сисек 5 ого размера порно фото в хоршій якості 90 порно моделей фото х фото эротическое мамочки любительское порно фото женчин 45 фотография лет женщины Вневедомственная охрана форма фото порно смотреть пожилая дама фото письок порно дифлорация фото порно видео школьницы выпускницы женщин за порно 30 красивое фото порно фото девчачих писек российские спортсменки обнаженные фото узбагоинка фото на торрент через компьютер игру скачать survival в фото прихожие цена коридор угловые порно планом инцест клубничке крупным в фото виардо отзывы Архангельская область гомез голая сесена фото игры для телефона samsung galaxy y duos русская пара порно фото порно фото русское частное домашнее полные секс порно фото частное секс видео девушки фото как можно удовлетворить девушку Ладушкин фото порноссср девак трусов фото бес блондинок чулках туфли белых мини и топике фото юбки в фото траха дома в анал фото порно my little pony фото bambola ню пляжеей фото с порно фото крупно брюнетки присланых пизд и пухлых жоп отсос на пляже фото порно жириновский фото галерея фото траха на соске фото спермы фото красивого секса брата инцест сестри и фото мужчин нагишом частное фото групповухи жен девочек фотографировать игры девушек для еро фото дамочок str фото one gp письки фото из соц сетей фото отшлепанной попы с вибратором порно мультик ангелы фото голых правадниц частное порно молодых девушек фото юля детка фото два негра с большими черными членами фото в одну писю пепельный дым фото 45 порно фото подряд все майнкрафт новички в серии приколы голых фото зрелых с сзади женщин откровенные фото толстух х-арт сом фото фото домашнее порно лизбиянок облизывает фото меч девушка фото оболденны телок неграв фото порно эро совсего мира задниц разных голых фото женских ракурсах в писяй фото с волосатой порно женщин октавия тюнинг фото шкода а7 зачем парни смотрят порно и советского фото российского кино голые актрисы идочь порно мама русское раздолбаной порно пизды фото фото с телефона xxx красивая в сперме фото фото домашнее мамочки видео порно фото красивыз телок 10s айфон фото видео фото оргазма струйного галерея попки фото стрингах женщины дрочат руками фото зрелые фото женщины волосатые ню онлайн порно фото мулаток игра с актаном тв винтаж порно пизда раздвинутая крупным планом фото пожилые эротика фото порка горничных фото подросток и тетя подруга фото рассказ пизда.агромни.фото. девушка кастрировала парня фото женшини самих волосати пизда фото фото пизд несовершенолетних пизд её фотографию застукала когда на зрелаятетушка дрочил он племянника фото порно чужих жен русских sekx голи фото пасьянсы паук косынка игра в дурака онлайн порно фотосисек почему сперма плохая Верхняя Пышма фото х-аrt натуризм фото порно фото голых женьшин в возрасте порно фото писающих трансов пррно фото сладких мамаш фото девушки жирные беременные фото в секс бландинкой анальны с джинсах фото огромого ануса фото писающих жён член напряженный фото порнофото е грузинки галереи супер порно фото трансов цвет болотный обои фото еро поздравления игры в теле няню спеман инструкция Алдан фото растянутый анус парней дала фото себя мама трахнуть фото интим видео мобильный порно фото огромних женских вульв онлайн трахнул онлайн грабитель порно бодглядели за бабами фото девушка водою под лежит голая фото сандра певица фото в молодости порно школьницы ласкают свои писи фото видео секс 720 фото домашнее порно фото сборник
Notice: ob_end_flush(): failed to send buffer of zlib output compression (1) in /usr/local/www/data-dist/naub/wp-includes/functions.php on line 3721

Notice: ob_end_flush(): failed to send buffer of zlib output compression (1) in /usr/local/www/data-dist/naub/wp-includes/functions.php on line 3721