В» і В«цільова функціяВ» полягає в наступному:
1. Цільова функція може включати в себе більше одного критерію.
2. Для цільової функції завжди і обов'язково вказується вид екстремуму:
Розрізняють два виду завдань оптимізації:
o Задачу мінімізації.
o Задачу максимізації.
Щоб вирішити завдання мінімізації функції на безлічі, необхідно знайти такий вектор (а також відповідне значення цільової функції), щоб нерівність: виконувалося для всіх. При цьому називають оптимальним рішенням (точніше тут - мінімальним рішенням), а - оптимумом (мінімумом).
Щоб вирішити задачу максимізації функції на безлічі, необхідно знайти такий вектор (а також відповідне значення цільової функції), щоб нерівність: виконувалося для всіх. При цьому називають оптимальним (максимальним) рішенням, а-оптимумом (Максимумом). p> У загальному вигляді знаходиться саме вектор, тому що, наприклад, при вирішенні двопараметричної завдання, він буде включати в себе два параметри, трипараметричної - три параметра і т.д.
2.3 Рішення діофантових рівняння
Розглянемо диофантова (Тільки цілі рішення) рівняння: a +2 b +3 c +4 d = 30, де a, b, c і d - деякі позитивні цілі. Застосування ГА за дуже короткий час знаходить шукане рішення (a, b, c, d).
Звичайно, Ви можете запитати: чому б не використати метод грубої сили: просто не підставити всі можливі значення a, b, c, d (очевидно, 1 <= a, b, c, d <= 30)? p> Архітектура ГА-систем дозволяє знайти рішення швидше за рахунок більш 'осмисленого' перебору. Ми не перебираємо все підряд, але наближаємося від випадково вибраних рішень до кращих.
Для початку виберемо 5 випадкових рішень: 1 =
Хромосома
(a, b, c, d)
1
(1,28,15,3)
2
(14,9,2,4)
3
(13,5,7,3)
4
(23,8,16,19)
5
(9,13,5,2)
Таблиця 1: 1-е покоління хромосом і їх вміст
Щоб обчислити коефіцієнти виживаності (fitness), підставимо кожне рішення у вираз a +2 b +3 c +4 d. Відстань від отриманого значення до 30 і буде потрібним значенням. span align=center>
Хромосома
Коефіцієнт виживаності
1
| 114-30 | = 84
2
| 54-30 | = 24
3
| 56-30 | = 26
4
| 163-30 | = 133
5
| 58-30 | = 28
Таблиця 2: Коефіцієнти виживаності першого покоління хромосом (набору рішень)
Так як менші значення ближче до 30, то вони більш бажані. У нашому випадку великі чисельні значення коефіцієнтів виживаності підходять, на жаль, менше. Щоб створити систему, де хромосоми з більш придатними значеннями мають великі шанси виявитися батьками, ми повинні обчислити, з якою ймовірністю (у%) може бути обрана кожна. Одне рішення полягає в тому, щоб взяти суму зворотних значень коефіцієнтів, і виходячи з цього обчислювати відсотки. (Зауважимо, що всі рішення були згенеровані Генератором Випадкових Чисел - ГВЧ)
Хромосома
Подходімость
1
(1/84)/0.135266 = 8.80%
2
(1/24)/0.135266 = 30.8%
3
(1/26)/0.135266 = 28.4%
4
(1/133)/0.135266 = 5.56%
5
(1/28)/0.135266 = 26.4%
Таблиця 3: Імовірність виявитися батьком
Для вибору 5-й пар батьків (кожна з яких матиме 1 нащадка, все - 5 нових рішень), уявімо, що у нас є 10000-стогони гральна кістка, на 880 сторонах відзначена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома +4 і на 2640 сторонах відзначена хромосома 5. Щоб вибрати першу пару, кидаємо кістка два рази і вибираємо випали хромосоми. Таким же чином вибираючи інших, отримуємо:
Хромосома батька
Хромосома матері
3
1
5
2
