Оптимізація лінійного рівняння за допомогою генетичного алгоритму в Python - javascript.org.ua

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

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

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

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

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

Методологія

У коді використовуються бібліотеки numpy для чисельних обчислень і matplotlib.pyplot для візуалізації даних. Ці бібліотеки необхідні для роботи з масивами та побудови графіків результатів. Вони імпортуються на початку коду за допомогою таких операторів:

import numpy as np  
import matplotlib.pyplot

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

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

Імплементація генетичного алгоритму

Python код реалізує генетичний алгоритм з наступними ключовими компонентами:

Ініціалізація

Створюється випадкова початкова популяція рішень за допомогою np.random.uniform. Кожне рішення представляє собою набір ваг для лінійного рівняння. Під час ініціалізації генеруються випадкові значення для ваг (позначених як num_weights), які стануть "генами" кожного хромосоми в популяції. Діапазон для цих випадкових значень встановлений між -4.0 і 4.0. Параметр pop_size визначає кількість рішень (хромосом) у популяції. Розмір популяції визначається кількістю рішень у популяції (sol_per_pop) і кількістю ваг для кожного рішення (num_weights). Отриманий масив new_population містить всі випадково згенеровані рішення.

pop_size = (sol_per_pop, num_weights)  
new_population = np.random.uniform(low=-4.0, high=4.0, size=pop_size)  
print(new_population)

sol_per_pop вказує на кількість рішень (хромосом) у популяції.
num_weights вказує на кількість ваг для кожного рішення (хромосоми).

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

Оцінка придатності

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

def cal_pop_fitness(equation_inputs, pop):  
 fitness = np.sum(pop*equation_inputs, axis=1)  
 return fitness

equation_inputs: Це значення для вхідних даних лінійного рівняння (зазвичай фіксовані та відомі заздалегідь).
pop: Це матриця популяції, де кожен рядок представляє рішення, а кожен стовпець — це вага для даного вхідного значення.

Функція працює, множачи кожну вагу в рішенні (pop) на відповідне значення вхідного параметра з equation_inputs і підсумовуючи ці добутки. Результатом є оцінка придатності для кожного окремого рішення. Чим кращі ваги (тобто, чим точніше зважена сума відповідає бажаному результату), тим вища оцінка придатності. Ця оцінка придатності використовується для керування еволюційним процесом, де рішення з вищою оцінкою придатності мають більший шанс бути обраними для відтворення та подальшого вдосконалення.

Вибір

Функція select_mating_pool обирає найкращі рішення (батьків) з популяції на основі їх оцінок придатності. Ці батьки обираються для створення нащадків для наступного покоління. У цій функції значення придатності спочатку коригуються шляхом віднімання мінімальної оцінки придатності, що гарантує, що всі значення будуть невід'ємними. Це коригування допомагає уникнути проблем з нульовими або негативними оцінками придатності. Далі виконується процес вибору за допомогою np.random.choice, який вибирає підмножину рішень (батьків) з популяції. Ключова ідея полягає в тому, що рішення з вищими оцінками придатності мають більшу ймовірність бути обраними батьками. Це робиться шляхом нормалізації оцінок придатності для створення розподілу ймовірностей, де сума всіх ймовірностей дорівнює 1. Чим краща оцінка придатності рішення, тим вища ймовірність його вибору.

def select_mating_pool(pop, fitness, num_parents):  
 fitness = fitness - fitness.min()  
 parents_idx = np.random.choice(pop.shape[0], size=num_parents, replace=False, p=fitness / fitness.sum())  
 return pop[parents_idx]

fitness: Оцінки придатності популяції, що вказують на те, як добре кожне рішення працює.
pop: Матриця популяції, де кожен рядок — це рішення.
num_parents: Кількість батьків, яких потрібно вибрати.

Функція:

Коригує оцінки придатності, щоб вони були невід'ємними.
Вибирає num_parents індивідуумів з популяції, використовуючи кориговані оцінки придатності як ймовірності.
Обрані батьки повертаються як нова популяція, яка буде використана для кросоверу на наступному етапі алгоритму.

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

Кросовер

Функція crossover генерує нащадків, комбінуючи гени (ваги) вибраних батьків. Цей процес імітує обмін генетичним матеріалом під час природного відтворення, коли нащадки успадковують риси від обох батьків. У цьому випадку "гени" — це ваги рівняння, і функція обмінює частини цих ваг для створення нових рішень.

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

def crossover(parents, offspring_size):  
 offspring = np.empty(offspring_size)  
 crossover_point = np.uint8(offspring_size[1]/2)  

 for k in range(offspring_size[0]):  
 parent1_idx = k%parents.shape[0]  
 parent2_idx = (k+1)%parents.shape[0]  
 offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]  
 offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]  
 return offspring

parents: Вибрані батьки, які передадуть свої гени для створення нащадків.
offspring_size: Кортеж, що вказує розмір популяції нащадків, яку потрібно створити (кількість нащадків та кількість генів для кожного нащадка).
crossover_point: Точка, в якій будуть розділені гени батьків. У цьому випадку точка визначається як половина кількості генів у кожному рішенні (offspring_size[1] / 2).

Процес:

Функція створює порожню матрицю offspring, яка міститиме нових нащадків.
Обчислюється crossover_point, що визначає, де гени двох батьків будуть розділені та обміняні.
Для кожного нащадка: Вибираються два батьки за допомогою модульної арифметики (k % parents.shape[0] для parent1 і (k + 1) % parents.shape[0] для parent2), що забезпечує круговий вибір батьків. Потім перша частина генів береться від parent1 (до точки кросоверу), а друга частина — від parent2 (після точки кросоверу).
Новостворені нащадки зберігаються в масиві offspring і повертаються.

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

Мутація

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

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

def mutation(offspring_crossover, num_mutations=1):  
 mutations_counter = np.uint8(offspring_crossover.shape[1] / num_mutations)  
 for idx in range(offspring_crossover.shape[0]):  
 gene_idx = mutations_counter - 1  
 for mutation_num in range(num_mutations):  
 random_value = np.random.uniform(-1.0, 1.0, 1)  
 offspring_crossover[idx, gene_idx] = np.clip(offspring_crossover[idx, gene_idx] + random_value, -4.0, 4.0)  
 gene_idx = gene_idx + mutations_counter  
 return offspring_crossover

Процес:

mutation_counter: Це визначає, як часто будуть відбуватися мутації. Кількість мутацій розподіляється по генах кожного нащадка.
Для кожного нащадка генерується random_value, випадкове значення з рівномірного розподілу між -1.0 та 1.0. Це значення додається до конкретного гена нащадка, вводячи невелику випадкову зміну.
Нове значення гена обрізається, щоб залишатися в межах заданого діапазону (між -4.0 та 4.0), щоб запобігти значенням, що виходять за дозволений діапазон.
4.
Процес мутації повторюється для num_mutations разів для кожного нащадка, вводячи кілька змін, якщо це необхідно.

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

Основний цикл генетичного алгоритму

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

best_outputs = []  
num_generations = 100  
for generation in range(num_generations):  
 print("Generation : ", generation)  
 fitness = cal_pop_fitness(equation_inputs, new_population)  
 print("Fitness")  
 print(fitness)  

 best_outputs.append(np.max(np.sum(new_population*equation_inputs, axis=1)))  
 print("Best result : ", np.max(np.sum(new_population*equation_inputs, axis=1)))  

 parents = select_mating_pool(new_population, fitness,  
 num_parents_mating)  
 print("Parents")  
 print(parents)  

 offspring_crossover = crossover(parents,  
 offspring_size=(pop_size[0]-parents.shape[0], num_weights))  
 print("Crossover")  
 print(offspring_crossover)  

 offspring_mutation = mutation(offspring_crossover, num_mutations=3)  
 print("Mutation")  
 print(offspring_mutation)  

 new_population[0:parents.shape[0], :] = parents  
 new_population[parents.shape[0]:, :] = offspring_mutation

Кількість поколінь (num_generations) = 100

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

Рівень мутації (що визначається через num_mutations в функції mutation) = 3 мутації на кожного нащадка

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

Кроки в циклі:

Оцінка пристосованості: В кожному поколінні оцінюється пристосованість популяції за допомогою функції cal_pop_fitness, і кращий показник пристосованості зберігається в best_outputs.
Відбір: Кращі індивідууми (батьки) обираються з популяції на основі їх значень пристосованості за допомогою функції select_mating_pool.
Кросовер: Вибрані батьки зазнають кросоверу, щоб створити нащадків, які успадковують частину генів від обох батьків, за допомогою функції crossover.
Мутація: Нащадки піддаються мутаціям, які вводять невеликі випадкові зміни в їхні гени за допомогою функції mutation.
Оновлення популяції: Створюється нова популяція шляхом заміни старої популяції батьками та мутованими нащадками.

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

Рівняння та параметри

Оптимізоване рівняння:

y = w₁x₁ + w₂x₂ + w₃x₃ + w₄x₄ + w₅x₅ + w₆x₆

де:

(x₁, x₂, x₃, x₄, x₅, x₆) = (3, -1, 4.5, 6, -10, -5.7) — це вхідні значення.
(w₁, w₂, w₃, w₄, w₅, w₆) — це ваги, які потрібно оптимізувати.

Метою оптимізації є знаходження найкращих значень для ваг w₁, w₂, w₃, w₄, w₅, w₆, що мінімізують різницю між обчисленим результатом y та бажаним цільовим значенням (залежно від мети оптимізації, зазвичай це заздалегідь визначена ціль або мінімізація помилки).

Параметри генетичного алгоритму

Для оптимізації ваг визначено кілька параметрів генетичного алгоритму:

Розмір популяції (sol_per_pop) = 30

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

Кількість батьків для парування (num_parents_mating) = 4

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

equation_inputs = [3,-1,4.5,6,-10,-5.7]  

num_weights = len(equation_inputs)  

sol_per_pop = 30  
num_parents_mating = 4

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

Результати та обговорення

Збіжність

Графік, згенерований за допомогою matplotlib.pyplot.plot(best_outputs), показує пристосованість найкращого рішення в кожному поколінні. Зазвичай це демонструє покращення пристосованості з часом, вказуючи на те, що алгоритм наближається до оптимальних рішень.

matplotlib.pyplot.plot(best_outputs)  
matplotlib.pyplot.xlabel("Iteration")  
matplotlib.pyplot.ylabel("Fitness")  
matplotlib.pyplot.show()

Ось X: Відображає кількість поколінь (ітерацій), через які пройшов алгоритм.
Ось Y: Відображає пристосованість найкращого рішення в цьому поколінні.

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

Найкраще рішення

Найкраще рішення, знайдене алгоритмом, представлено значеннями w1, w2, w3, w4, w5 та w6, які дають найвищу пристосованість.
Цей оптимальний набір ваг відповідає найкращому рішенню в кінцевій популяції, і його можна вивести за допомогою наступного коду:

fitness = cal_pop_fitness(equation_inputs, new_population)  
best_match_idx = np.where(fitness == np.max(fitness))  
print("Best solution : ", new_population[best_match_idx, :])  
print("Best solution fitness : ", fitness[best_match_idx])

new_population[best_match_idx, :]: Це дає ваги w1, w2, w3, w4, w5, і w6, які відповідають найкращому рішенню.
fitness[best_match_idx]: Це дає значення пристосованості найкращого рішення, яке відображає, як добре воно виконує рівняння.

Інтерпретація

Найкраще рішення, знайдене алгоритмом, представляє оптимальний набір ваг для рівняння:

y = w₁x₁ + w₂x₂ + w₃x₃ + w₄x₄ + w₅x₅ + w₆x₆

Ці ваги максимізують результат рівняння для заданих вхідних значень (x₁, x₂, x₃, x₄, x₅, x₆). Це означає, що набір ваг, отриманий алгоритмом, ефективно відображає взаємозв'язок між вхідними даними і бажаним виходом.

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

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

Висновок

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

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

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

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

Перекладено з: Optimization of a Linear Equation using a Genetic Algorithm in Python