Генетичният алгоритъм е адаптивен евристичен алгоритъм за търсене, вдъхновен от теорията на Дарвин за еволюцията в природата .' Използва се за решаване на проблеми с оптимизацията в машинното обучение. Това е един от важните алгоритми, тъй като помага за решаването на сложни проблеми, чието разрешаване би отнело много време.

Генетичните алгоритми се използват широко в различни приложения от реалния свят, напр. Проектиране на електронни схеми, разбиване на кодове, обработка на изображения и изкуствено творчество.

В тази тема ще обясним подробно генетичния алгоритъм, включително основните терминологии, използвани в генетичния алгоритъм, как работи, предимствата и ограниченията на генетичния алгоритъм и т.н.

Какво е генетичен алгоритъм?

Преди да разберем генетичния алгоритъм, нека първо разберем основните терминологии, за да разберем по-добре този алгоритъм:

Население:Популацията е подмножество от всички възможни или вероятни решения, които могат да решат даден проблем.Хромозоми:Хромозомата е едно от решенията в популацията за даден проблем, а колекцията от гени генерира хромозома.ген:Хромозомата е разделена на различен ген или е елемент от хромозомата.Алели:Алелът е стойността, предоставена на гена в определена хромозома.Фитнес функция:Фитнес функцията се използва за определяне на индивидуалното ниво на годност в популацията. Това означава способността на индивида да се конкурира с други индивиди. Във всяка итерация индивидите се оценяват въз основа на тяхната фитнес функция.Генетични оператори:В генетичен алгоритъм най-добрият индивидуален партньор за регенериране на потомство по-добре от родителите. Тук генетичните оператори играят роля в промяната на генетичния състав на следващото поколение.Избор

След изчисляване на пригодността на всеки съществуващ в популацията се използва процес на подбор, за да се определи коя от индивидуалностите в популацията ще може да се размножи и да произведе семето, което ще формира следващото поколение.

Налични типове стилове за избор

Избор на колело на рулетка Избор на събитие Подбор, основан на ранг

И така, сега можем да дефинираме генетичен алгоритъм като евристичен алгоритъм за търсене за решаване на проблеми с оптимизацията. Това е подгрупа от еволюционни алгоритми, които се използват в изчисленията. Генетичният алгоритъм използва концепции за генетичен и естествен подбор за решаване на проблеми с оптимизацията.

двоично дърво в java

Как работи генетичният алгоритъм?

Генетичният алгоритъм работи върху еволюционния генерационен цикъл, за да генерира висококачествени решения. Тези алгоритми използват различни операции, които или подобряват, или заместват популацията, за да осигурят подобрено подходящо решение.

Основно включва пет фази за решаване на сложни оптимизационни проблеми, които са дадени по-долу:

Инициализация Фитнес задача Избор Възпроизвеждане Прекратяване на договора

1. Инициализация

Процесът на генетичен алгоритъм започва с генериране на набор от индивиди, който се нарича популация. Тук всеки индивид е решението на даден проблем. Индивидът съдържа или се характеризира с набор от параметри, наречени гени. Гените се комбинират в низ и генерират хромозоми, което е решението на проблема. Една от най-популярните техники за инициализация е използването на произволни двоични низове.

2. Фитнес задача

Фитнес функцията се използва, за да се определи в каква форма е индивидът? Това означава способността на индивида да се конкурира с други индивиди. Във всяка итерация индивидите се оценяват въз основа на тяхната фитнес функция. Фитнес функцията осигурява фитнес резултат за всеки индивид. Този резултат допълнително определя вероятността да бъде избран за възпроизвеждане. Колкото по-висок е фитнес резултатът, толкова по-големи са шансовете да бъдете избрани за възпроизвеждане.

3. Избор

Фазата на подбор включва подбор на индивиди за възпроизвеждане на потомство. След това всички избрани индивиди се подреждат по двойки, за да се увеличи възпроизводството. След това тези индивиди прехвърлят своите гени на следващото поколение.

Има три вида налични методи за избор, които са:

• Избор на колело на рулетка
• Избор на турнир
• Подбор въз основа на ранг

4. Размножаване

След процеса на подбор, създаването на дете става в етапа на възпроизвеждане. В тази стъпка генетичният алгоритъм използва два оператора за вариация, които се прилагат към родителската популация. Двата оператора, участващи във фазата на възпроизвеждане, са дадени по-долу:

кросоувър:Кроссоувърът играе най-важна роля във фазата на възпроизвеждане на генетичния алгоритъм. В този процес точката на кръстосване се избира на случаен принцип в рамките на гените. След това кръстосаният оператор разменя генетичната информация на двама родители от текущото поколение, за да произведе нов индивид, представляващ потомството.

Гените на родителите се обменят помежду си, докато се достигне точката на кръстосване. Тези новосъздадени потомци се добавят към популацията. Този процес се нарича също или кросоувър. Налични видове кросоувър стилове:
• Кросоувър с една точка
• Двуточков кросоувър
• Ливрея кросоувър
• Кросоувър на наследими алгоритми
Мутация
Операторът на мутация вмъква произволни гени в потомството (ново дете), за да поддържа разнообразието в популацията. Може да се направи чрез обръщане на някои части в хромозомите.
Мутацията помага при решаването на проблема с преждевременната конвергенция и подобрява диверсификацията. Изображението по-долу показва процеса на мутация:
Налични видове стилове на мутация,
Флип битова мутация Гаусова мутация Размяна/Размяна на мутация

5. Прекратяване

След фазата на възпроизвеждане се прилага критерий за спиране като основа за прекратяване. Алгоритъмът прекратява след достигане на праговото решение за годност. Той ще идентифицира окончателното решение като най-доброто решение в популацията.

arraylist сортиран java

Общ работен процес на прост генетичен алгоритъм

Предимства на генетичния алгоритъм

• Паралелните възможности на генетичните алгоритми са най-добри.
• Помага при оптимизирането на различни проблеми като дискретни функции, проблеми с множество цели и непрекъснати функции.
• Предоставя решение за проблем, което се подобрява с времето.
• Генетичният алгоритъм не се нуждае от производна информация.

Ограничения на генетичните алгоритми

• Генетичните алгоритми не са ефективни алгоритми за решаване на прости проблеми.
• Не гарантира качеството на крайното решение на проблем.
• Повтарящото се изчисляване на стойностите за годност може да доведе до някои изчислителни предизвикателства.

Разлика между генетичните алгоритми и традиционните алгоритми

• Пространството за търсене е набор от всички възможни решения на проблема. В традиционния алгоритъм се поддържа само един набор от решения, докато в генетичния алгоритъм могат да се използват няколко набора от решения в пространството за търсене.
• Традиционните алгоритми се нуждаят от повече информация, за да извършат търсене, докато генетичните алгоритми се нуждаят само от една обективна функция, за да изчислят пригодността на индивида.
• Традиционните алгоритми не могат да работят паралелно, докато генетичните алгоритми могат да работят паралелно (изчисляването на годността на индивидуалностите е независимо).
• Една голяма разлика в генетичните алгоритми е, че вместо да работят директно върху резултатите от търсенето, наследствените алгоритми работят върху техните представяния (или изобразяване), често приписвани като хромозоми.
• Една от големите разлики между традиционния алгоритъм и генетичния алгоритъм е, че той не работи директно върху кандидат-решения.
• Традиционните алгоритми могат да генерират само един резултат в крайна сметка, докато генетичните алгоритми могат да генерират множество оптимални резултати от различни поколения.
• Традиционният алгоритъм не е по-вероятно да генерира оптимални резултати, докато генетичните алгоритми не гарантират генериране на оптимални глобални резултати, но също така има голяма възможност за получаване на оптимален резултат за даден проблем, тъй като използва генетични оператори като Crossover и Mutation.
• Традиционните алгоритми са детерминистични по природа, докато генетичните алгоритми са вероятностни и стохастични по природа.