розділ 2.1) множина
змінних xij формує структуру хромосоми. Отже, хромосома є бінарною матрицею
розміром IЧJ. Змінна xijh зберігає значення іj-ого гена хромосоми h. Значення
гена може дорівнювати або „0”, або „1”. Відповідно до обмеження задачі,
зазначеного у формулі (2.9), значення гена xijh може дорівнювати „1” тільки
один раз для кожної і для j. Це потрібно врахувати під час програмування
алгоритму, щоб будувати допустимі рішення.
…
…
…
…
...
...
...
...
...
...
0
...
...
...
...
...
0
Рис. 2.8. Загальний вигляд хромосоми h
На рис. 2.8 наведено загальний вигляд хромосоми популяції за індексом h.
Кількість хромосом популяції с є змінною величиною, визначається
проектувальником відповідно до потрібної ймовірності пошуку глобального
оптимуму. Під час формування початкової популяції значення генів хромосоми
визначається випадково.
2.3.2. Розрахунок цільової функції
Пристосованість або ЦФ хромосоми h розраховується на базі функції оптимізації
математичної моделі задачі добору і розподілу робітників підприємства,
зазначеної у формулі (2.8), і з урахуванням обмеження задачі, наведеного у
формулі (2.10). Значення пристосованості хромосоми h визначає корисність
хромосоми для подальшого розмноження популяції у напрямку оптимального рішення.
Тому значення ЦФ хромосоми h розраховується за формулою (2.14), яка побудована
відповідно до неокласичної функції корисності з урахуванням штрафної функції.
(2.14)
Коефіцієнт г визначається відповідно до потреб задачі. Кількість хромосом у
популяції дорівнює с. За формулою (2.14) розраховується показник корисності для
кожної хромосоми h. Значення корисності хромосоми Fh залежить від qh – якості
виконання робіт робітниками (формула (2.15)), і від ph – розміру витрат на
оплату праці робітників для даного розв’язання (формула (2.16)), з урахуванням
g(Xh) – величини відхилення від обмеження задачі (формули (2.17) – (2.19)):
(2.15)
(2.16)
(2.17)
(2.18)
(2.19)
Значення штрафної функції поточного розподілення g(Xh) дорівнює сумі розмірів
штрафів усіх робітників. Розмір штрафу Иjh робітника залежить від двох
показників: сумарного часу роботи j-го робітника иjh поточного розподілу і
нормативного значення часу роботи j-го робітника зj. Коефіцієнт у у формулі
(2.18) визначає розмір штрафу. Значення коефіцієнта у повинно відповідати
порядку одиниць, якими визначено вагомість (прибутковість) роботи і витрати на
виконання робіт.
Отже, вище було визначено функцію (2.14), відповідно до якої буде визначаться
пристосованість кожної хромосоми популяції при виконанні МГА. Значення функції
(2.14) є критерієм для визначення розв’язання задачі пошуку оптимального
розподілення завантаження робітників підприємства.
2.3.3. Опис генетичних операторів
У процесі формування нової популяції вибирається один із ГО (селекція,
кросинговер, мутація) залежно від заданої імовірності. Значення імовірностей ГО
взято такі: Рселекція=0,399; Ркросинговер=0,6; Рмутація=0,001 [53]. Сума
імовірностей ГО повинна дорівнювати „1”. У МГА застосовуються такі оператори,
як селекція, кросинговер, мутація. Але можливе використання і інверсії,
транслокації, транспозиції та інших, а також і можливі модифікації ГО. Вибір
додаткових ГО залежить від умов задачі, напрямків пошуку і потреб
проектування.
На рис. 2.9 – 2.10 наведено приклад виконання ГО кросинговер і мутація
відповідно до заданої структури хромосоми і відповідно до обмеження задачі
зазначеного у формулі (2.9).
Кросинговер виконується за наступним алгоритмом:
випадково вибирається рядок i, за яким буде відбуватися розрив хромосом предків
(наприклад, рядок 3);
будується перша нова хромосома: отримує гени предка_1 з 1 по і та гени предка_2
з і+1 по I;
будуються друга нова хромосома: отримує гени предка_2 з 1 по і та гени предка_1
з і+1 по I.
…
0
0
0
...
i
…
I
1
2
3
...
i
…
I
…
0
0
0
...
I
…
I
1
2
3
...
i
…
I
Рис. 2.9. Реалізація кросинговеру
Мутація виконується за наступним алгоритмом:
випадково вибирається рядок i, який буде мутовано;
обнуління рядка i: всім значенням j рядка i ставиться у відповідність 0;
вибирається колонка j рядка i, за якою значення гена хij змінюється з 0 на 1.
…
0
0
0
...
i
…
I
J
0
1
0
...
I
…
I
Рис. 2.10. Реалізація мутації
Результатом роботи алгоритму є хромосома, яка визначає значення змінної хij.
Отже, результатом роботи методу пошуку оптимального розподілу завантаження
робітників підприємства на базі МГА є перелік робіт для виконання кожному з
робітників.