Генетичните алгоритми (GA) се базират на еволюционен подход към изкуствения интелект, при който методите на еволюцията на популация се използват за намиране на оптимално решение за даден проблем. Те са предложени през 1975 г. от Джон Хенри Холанд.
Генетичните алгоритми се основават на следните идеи:
- Валидните решения на проблема могат да бъдат представени като гени
- Кросоувър позволява комбинирането на две решения, за да се получи ново валидно решение
- Селекция се използва за избор на по-оптимални решения чрез някаква функция за пригодност
- Мутации се въвеждат, за да дестабилизират оптимизацията и да ни изведат от локалния минимум
Ако искате да реализирате генетичен алгоритъм, ще ви трябват следните елементи:
- Да намерите метод за кодиране на решенията на проблема чрез гени g∈Γ
- В множеството от гени Γ трябва да дефинирате функция за пригодност fit: Γ→R. По-малките стойности на функцията съответстват на по-добри решения.
- Да дефинирате механизъм за кросоувър, който комбинира два гена, за да се получи ново валидно решение crossover: Γ2→Γ.
- Да дефинирате механизъм за мутация mutate: Γ→Γ.
В много случаи кросоувърът и мутацията са доста прости алгоритми за манипулиране на гени като числови последователности или битови вектори.
Специфичната реализация на генетичен алгоритъм може да варира в зависимост от случая, но общата структура е следната:
- Изберете начална популация G⊂Γ
- Случайно изберете една от операциите, които ще се изпълнят на тази стъпка: кросоувър или мутация
- Кросоувър:
- Случайно изберете два гена g1, g2 ∈ G
- Изчислете кросоувър g=crossover(g1,g2)
- Ако fit(g)<fit(g1) или fit(g)<fit(g2) - заменете съответния ген в популацията с g.
- Мутация - изберете случаен ген g∈G и го заменете с mutate(g)
- Повтаряйте от стъпка 2, докато получите достатъчно малка стойност на fit или докато достигнете лимита на броя стъпки.
Задачи, които обикновено се решават с генетични алгоритми, включват:
- Оптимизация на графици
- Оптимално опаковане
- Оптимално рязане
- Ускоряване на изчерпателното търсене
Продължете обучението си в следните тетрадки:
Отидете на тази тетрадка, за да видите два примера за използване на генетични алгоритми:
- Справедливо разделяне на съкровище
- Проблемът с 8 царици
Генетичните алгоритми се използват за решаване на много проблеми, включително логистични и задачи за търсене. Областта е вдъхновена от изследвания, които обединяват теми от психологията и компютърните науки.
"Генетичните алгоритми са лесни за реализиране, но тяхното поведение е трудно за разбиране." източник Направете проучване, за да намерите реализация на генетичен алгоритъм, например за решаване на Судоку, и обяснете как работи чрез скица или блок-схема.
Гледайте това страхотно видео, което разказва как компютър може да се научи да играе Super Mario, използвайки невронни мрежи, обучени чрез генетични алгоритми. Ще научим повече за обучението на компютри да играят игри като тази в следващия раздел.
Вашата цел е да решите така нареченото Диофантово уравнение - уравнение с цели корени. Например, разгледайте уравнението a+2b+3c+4d=30. Трябва да намерите целите корени, които удовлетворяват това уравнение.
Тази задача е вдъхновена от тази публикация.
Подсказки:
- Можете да разгледате корените в интервала [0;30]
- Като ген, помислете за използване на списък с стойности на корените
Използвайте Diophantine.ipynb като начална точка.