МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра ЕОМ
Звіт
з лабораторної роботи №1
з дисципліни «Системи штучного інтелекту»
на тему:
«Застосування генетичних алгоритмів для вирішення задач оптимізації»
Виконав:
ст. гр. КІКC-11
Криса В.В.
Прийняв:
Куриляк Д.Б.
Львів – 2021
Тема роботи: Застосування генетичних алгоритмів для вирішення задач оптимізації.
Мета роботи: навчитися розв’язувати задачі оптимізації за допомогою генетичного алгоритму, навчитися програмно реалізовувати генетичний алгоритм.
TЕОРЕТИЧНІ ВІДОМОСТІ
Генети́чний алгори́тм (англ. geneticalgorithm) — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.
Особливістю генетичного алгоритму є акцент на використання оператора «схрещення», який виконує операцію рекомбінацію рішень-кандидатів, роль якої аналогічна ролі схрещення в живій природі. «Батьком-засновником» генетичних алгоритмів вважається Джон Голланд (англ. JohnHolland), книга якого «Адаптація в природних і штучних системах» (англ. Adaptation in Natural and Artificial Systems) є фундаментальною в цій сфері досліджень.
Задача кодується таким чином, щоб її вирішення могло бути представлено в вигляді масиву подібного до інформації складу хромосоми. Цей масив часто називають саме так «хромосома». Випадковим чином в масиві створюється деяка кількість початкових елементів «осіб», або початкова популяція. Особи оцінюються з використанням функції допасованості, в результаті якої кожній особі присвоюється певне значення допасованості, яке визначає можливість виживання особи. Після цього з використанням отриманих значень допасованості вибираються особи, допущені до схрещення (селекція). До осіб застосовується «генетичні оператори» (в більшості випадків це оператор схрещення (crossover) і оператор мутації (mutation)), створюючи таким чином наступне покоління осіб. Особи наступного покоління також оцінюються застосуванням генетичних операторів і виконується селекція і мутація. Так моделюється еволюційний процес, що продовжується декілька життєвих циклів (поколінь), поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути:
знаходження глобального, або надоптимального вирішення;
вичерпання числа поколінь, що відпущені на еволюцію;
вичерпання часу, відпущеного на еволюцію.
Генетичні алгоритми можуть використовувати для пошуку рішень в дуже великих і важких просторах пошуку.
Можна виділити такі етапи генетичного алгоритму:
Створення початкової популяції:
Обчислення функції допасованості для осіб популяції (оцінювання)
Повторювання до виконання критерію зупинки алгоритму:
Вибір індивідів із поточної популяції (селекція)
Схрещення або/та мутація
Обчислення функції допасованості для всіх осіб
Формування нового покоління
ЗАВДАННЯ
Максимізувати та мінімізувати функцію однієї змінної. Обчислення провести з точністю до
10-n , де n=0,1,2
де x є [0,10)
Написати програму для реалізації генетичного алгоритму для розв’язування задач. Інтерфейс програми повинен дозволяти вводити такі дані: точність обчислення, кількість хромосом, вибір умови зупинки роботи алгоритму – після досягнення заданої точності або після досягнення кількості ітерацій, ймовірність схрещування, ймовірність мутації. Результатом роботи програми повинне бути значення всіх індивідумів у популяції, фенотип,
значення функції відповідності для кожного індивідума, середнє значення функції відповідності. При захисті лабораторної роботи студент повинен знати генетичний алгоритм, вміти зробити необхідні зміни у тексті програми, пояснити зміст отриманих результатів.
ХІД РОБОТИ
Програма для розв’язання функції генетичним алгоритмом
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace GenAlgoConsoleApp
{
class Program
{
static void Main(string[] args)
{
Random rand = new Random();
Console.WriteLine("Hello World!");
int X_Min = 0, X_Max = 10;
int x = 1;
int Population_Count = 0, Chromo_Count = 10, Iteration_Count = 3;
double Precision = 200, Hybrid_Probability = 0.8, Mutation_Probability = 0.03;
double y = Math.Pow(x, 2) + (Math.Pow(x, 3) - 7) * (Math.Pow(x, 2) + 5);
List
List
for(int i = 0; i < Chromo_Count; i++)
{
Chromos.Add(new ChromoInfo() { Id = i }) ;
Chromos[i].Feno = Fenos[i];
Chromos[i].Population = Convert.ToInt64((Convert.ToString(Chromos[i].Feno, 2))).ToString("d4");
Chromos[i].FuncVal = Math.Round(ReturnFuncVal(Chromos[i].Feno), 2);
}
for(int p = 0; p < Iteration_Count; p++)
{
Console.WriteLine($"-----------START NEW GENERATION #{p+1}-----------");
Chromos = NextChromoGeneration(Chromos, Precision, Chromo_Count, Hybrid_Probability, Mutation_Probability, rand);
Console.WriteLine($"------------END NEW GENERATION #{p+1}------------");
}
}
static List
{
List
double RevertCoefSum = 0;
for (int i = 0; i < Chromo_Count; i++)
{
Distances.Add(Math.Abs(Precision - Chromos[i].FuncVal));
RevertCoefSum += 1 / Distances[i];
}
for (int i = 0; i < Chromo_Count; i++)
{
Chromos[i].Percent = Math.Round((1 / Distances[i]) / RevertCoefSum, 2);
Chromos[i].Expected = Math.Round(Chromos[i].Percent * Chromo_Count);
if (i == 0)
{
Chromos[i].StartPercent = 0;
Chromos[i].EndPercent = Math.Round(Chromos[i].Percent, 2);
}
else if (i == Chromo_Count - 1)
{
Chromos[i].StartPercent = Chromos[i - 1].EndPercent;
Chromos[i].EndPercent = 100;
}
else
{
Chromos[i].StartPercent = Chromos[i - 1].EndPercent;
Chromos[i].EndPercent = Math.Round(Chromos[i].StartPercent + Chromos[i].Percent, 2);
}
}
List
for (int i = 0; i < Chromo_Count; i++)
{
int Rand_Percent = rand.Next(0, 101);
double Rand_Percent_Db = Rand_Percent / 100.0;
if (Rand_Percent == 0)
{
ActualChromos.Add(Chromos[^1].Id);
}
else if (Rand_Percent == 100)
{
ActualChromos.Add(Chromos[0].Id);
}
else
{
int id = Chromos.FirstOrDefault(ch => ch.StartPercent <= Rand_Percent_Db && ch.EndPercent >= Rand_Percent_Db).Id;
ActualChromos.Add(id);
}
}
for (int i = 0; i < Chromo_Count; i++)
{
Chromos[i].Actual = ActualChromos.Count(ch => ch == Chromos[i].Id);
}
for (int i = 0; i < Chromo_Count; i++)
{
Console.WriteLine($"{Chromos[i].Id}\t{Chromos[i].Population}\t{Chromos[i].Feno}\t{Chromos[i].FuncVal}\t\t{Chromos[i].Percent}\t{Chromos[i].Expected}\t{Chromos[i].Actual}");
}
List
for (int i = 0; i < Chromo_Count; i++)
{
for (int j = 0; j < Chromos[i].Actual; j++)
{
NextGenChromos.Add(Chromos[i].CloneChromo());
}
}
for (int i = 0; i < Chromo_Count; i++)
{
NextGenChromos[i].Id = i;
NextGenChromos[i].Partner = -1;
NextGenChromos[i].IsHybrid = false;
NextGenChromos[i].IsMutated = false;
}
List
for (int i = 0; i < RandPairs.Count; i++)
{
int point = rand.Next(0, RandPairs.Count - 2);
NextGenChromos[RandPairs[i].Item1].Partner = RandPairs[i].Item2;
NextGenChromos[RandPairs[i].Item2].Partner = RandPairs[i].Item1;
NextGenChromos[RandPairs[i].Item1].DividePoint = point;
NextGenChromos[RandPairs[i].Item2].DividePoint = point;
}
Console.WriteLine("\n\n");
for (int i = 0; i < Chromo_Count; i++)
{
string Population = NextGenChromos[i].Population;
Population = Population.Insert(NextGenChromos[i].DividePoint + 1, "|");
Console.WriteLine($"{NextGenChromos[i].Id}\t{Population}\t{NextGenChromos[i].Partner}\t{NextGenChromos[i].DividePoint + 1}");
}
for (int i = 0; i < RandPairs.Count; i++)
{
//Need add random probability and mutation
int HybridRand = rand.Next(0, 101);
if (HybridRand <= (int)(Hybrid_Probability*100)) {
ChromoInfo firstItem = NextGenChromos[RandPairs[i].Item1];
ChromoInfo secondItem = NextGenChromos[RandPairs[i].Item2];
string SecondPop = firstItem.Population.Substring(0, firstItem.DividePoint + 1) +
secondItem.Population.Substring(secondItem.DividePoint + 1, 3 - secondItem.DividePoint);
string FirstPop = secondItem.Population.Substring(0, secondItem.DividePoint + 1) +
firstItem.Population.Substring(firstItem.DividePoint + 1, 3 - firstItem.DividePoint);
NextGenChromos[RandPairs[i].Item1].Population = FirstPop;
NextGenChromos[RandPairs[i].Item2].Population = SecondPop;
NextGenChromos[RandPairs[i].Item1].Feno = Convert.ToInt32(FirstPop, 2);
NextGenChromos[RandPairs[i].Item2].Feno = Convert.ToInt32(SecondPop, 2);
NextGenChromos[RandPairs[i].Item1].FuncVal = Math.Round(ReturnFuncVal(NextGenChromos[RandPairs[i].Item1].Feno), 2);
NextGenChromos[RandPairs[i].Item2].FuncVal = Math.Round(ReturnFuncVal(NextGenChromos[RandPairs[i].Item2].Feno), 2);
NextGenChromos[RandPairs[i].Item1].IsHybrid = true;
NextGenChromos[RandPairs[i].Item2].IsHybrid = true;
}
}
int MutationCount = (int)(Mutation_Probability * Chromo_Count * 4);
List
foreach(int mutation in mutations)
{
StringBuilder sb = new StringBuilder(NextGenChromos[mutation / 4].Population);
if(sb[mutation % 4] == '1')
{
sb[mutation % 4] = '0';
}
else
{
sb[mutation % 4] = '1';
}
NextGenChromos[mutation / 4].Population = sb.ToString();
NextGenChromos[mutation / 4].IsMutated = true;
}
Console.WriteLine("\n\n");
for (int i = 0; i < Chromo_Count; i++)
{
string Population = NextGenChromos[i].Population;
Population = Population.Insert(NextGenChromos[i].DividePoint + 1, "|");
Console.WriteLine($"{NextGenChromos[i].Id}\t{Population}\t{NextGenChromos[i].Partner}\t{NextGenChromos[i].DividePoint + 1}\t{NextGenChromos[i].IsHybrid}\t{NextGenChromos[i].IsMutated}");
}
return NextGenChromos;
}
static List
{
List
int number;
for (int i = 0; i < count; i++)
{
do
{
number = rand.Next(min, max + 1);
} while (listNumbers.Contains(number));
listNumbers.Add(number);
}
return listNumbers;
}
static double ReturnFuncVal(int x)
{
return Math.Pow(x, 2) + (Math.Pow(x, 3) - 7)*(Math.Pow(x, 2)+5);
}
static List
{
var items = new List
var pickedItems = new HashSet
int count = (max - min + 1);
Func
{
int? candidate = null;
while (candidate == null || pickedItems.Contains(candidate.Value))
candidate = r.Next(min, max + 1);
pickedItems.Add(candidate.Value);
return candidate.Value;
};
while (pickedItems.Count != count)
{
int firstItem = randAndCheck();
int secondItem = randAndCheck();
items.Add(Tuple.Create(firstItem, secondItem));
}
return items;
}
}
}
РЕЗУЛЬТАТИ
Рис. 1. Генерації згенеровані генетичним алгоритмом
ВИСНОВКИ
На даній лабораторній я був ознайомлений з генетичним алгоритмом, мною була проведена оптимізація значень аргументу для функції однієї змінної. Множиною значень аргументу було визначено [0,10]. Кількість хромосом була встановлена 10, кількість ітерацій (генерацій) було обмежено до 3. Точним значення функції було обрано 200. Імовірність гібридизації хромосом 80%. Імовірність мутації хромосом 3%. На останній генерації залишилися хромосоми із найбільш наближеним значенням функції до еталонного.