Преглед на генетичния алгоритъм
Техниките за оптимизация са техниките, които се използват за откриване на най-доброто решение от всички възможни решения, налични при наличните ограничения. Така че генетичният алгоритъм е един такъв алгоритъм за оптимизация, който е изграден въз основа на естествения еволюционен процес на нашата природа. Тук се използва идеята за естествен подбор и генетично наследство. Той използва ръководено произволно търсене, за разлика от други алгоритми, т.е. намиране на оптималното решение, като се започне с функция за произволна първоначална цена и след това се търси само в пространството, което има най-малко разходи (в насочената посока). Подходящ, когато работите с огромни и сложни набори от данни.
Какво е генетичен алгоритъм?
Генетичният алгоритъм се основава на генетичната структура и поведението на хромозомата на популацията. Следните неща са в основата на генетичните алгоритми.
- Всяка хромозома показва възможно решение. Така популацията е съвкупност от хромозоми.
- Всеки индивид в популацията се характеризира с фитнес функция. По-доброто фитнес е по-добро решение.
- От наличните индивиди в популацията, най-добрите индивиди се използват за възпроизвеждането на потомците от следващото поколение.
- Произведеното потомство ще има черти и на родителите и е резултат от мутация. Мутацията е малка промяна в генната структура.
Фази на генетичния алгоритъм
По-долу са различните фази на генетичния алгоритъм:
1. Инициализация на популацията (кодиране)
- Всеки ген представлява параметър (променливи) в разтвора. Тази колекция от параметри, която образува разтвора, е хромозомата. Популацията представлява съвкупност от хромозоми.
- Ред на гените по въпросите на хромозомата.
- По-голямата част от хромозомите във времето се изобразяват в двоични като 0 и 1, но има и други възможни кодировки.
2. Фитнес функция
- От наличните хромозоми трябва да подберем най-добрите за възпроизвеждането на потомството, така че всяка хромозома получава фитнес стойност.
- Фитнес резултатът помага да се изберат индивидите, които ще бъдат използвани за възпроизвеждане.
3. Избор
- Основната цел на тази фаза е да се намери регионът, в който шансовете за най-добро решение са повече.
- Вдъхновението за това е от оцеляването на най-силните.
- Той трябва да бъде баланс между проучването и използването на пространството за търсене.
- GA се опитва да премести генотипа към по-висока годност в пространството за търсене.
- Твърде силните пристрастия за избор на фитнес могат да доведат до неоптимални решения.
- Твърде малкото подбор на фитнес пристрастия води до безфокусирано търсене.
- По този начин се използва пропорционален избор на фитнес, който е известен още като избор на колело на рулетка, е генетичен оператор, използван в генетичните алгоритми за избор на потенциално полезни решения за рекомбинация.
4. Възпроизвеждане
Генерирането на потомството става по два начина:
- кросоувър
- мутация
а) Кросоувър
Кросоувърът е най-жизненоважният етап в генетичния алгоритъм. По време на кросоувър се избира случайна точка, докато чифтосват двойка родители за генериране на потомство.
Има 3 основни типа кросоувър.
- Кросовър с единична точка: Точка върху хромозомите на двамата родители се избира случайно и се обозначава като „кросоувър точка“. Битовете вдясно от тази точка се обменят между двете родителски хромозоми.
- Двуточков кросоувър: Две точки на кръстоса се избират произволно от родителските хромозоми. Битовете между двете точки се разменят между родителските организми.
- Унифициран кросоувър: В еднакъв кросоувър обикновено всеки бит се избира от всеки родител с еднаква вероятност.
Новото потомство се добавя към населението.
б) Мутация
При няколко новообразувани потомства някои от техните гени могат да бъдат подложени на мутация с ниска случайна вероятност. Това показва, че някои от битовете в битовата хромозома могат да бъдат обърнати. Мутацията се случва, за да се грижи за многообразието сред населението и да спре преждевременното сближаване.
5. Конвергенция (кога да спре)
Няколко правила, които се спазват, които казват кога да спрете, са както следва:
- Когато няма подобрение в качеството на разтвора след завършване на определен брой поколения, поставени пред ръка.
- Когато се достигне твърд и бърз обхват от поколения и време.
- До получаване на приемливо решение.
Приложение на генетичен алгоритъм
В този раздел ще обсъдим някои от областите, в които често се прилага генетичният алгоритъм.
1. Маршрути за пътуване и изпращане
Проблемът с пътуващия продавач е едно от основните приложения на генетичния алгоритъм. Например, когато един от планиращите пътувания бъде помолен да планира пътуване, той би използвал генетичен алгоритъм, който не само помага за намаляване на общите разходи за пътуването, но и за намаляване на времето.GE се използва и за планиране на доставката на продуктите от място на място по най-ефективния начин.
2. Роботика
Генетичният алгоритъм се използва широко в областта на роботиката. Роботите се различават един от друг по целта, за която са изградени. Например, малцина са изградени за готварска задача, малко са изградени за учебни задачи и т.н.
- Избор на важни характеристики в дадения набор от данни.
- В традиционния метод важните характеристики в набора от данни се избират по следния метод. т.е. Вие разглеждате важността на този модел, след това ще зададете прагова стойност за характеристиките и ако функцията има стойност на важността повече от праг, тя се счита.
- Но тук използваме метод, наречен проблем с раницата.
- Отново ще започнем с популацията на хромозома, където всяка хромозома ще бъде двоичен низ. 1 ще означава "включване" на характеристиката в модел, а 0 ще означава "изключване" на характеристиката в модела.
- Фитнес функцията тук ще бъде нашата метрика за точност на състезанието. Колкото по-точен е нашият набор от хромозоми в прогнозиращата стойност, толкова по-подходящ ще бъде той.
- Има много други приложения на генетични алгоритми като ДНК анализ, програмиране на програми, Инженерно проектиране.
заключение
В настоящия сценарий GE се използва в големи производствени компании като самолети и т.н., за да се оптимизира използването на време и ресурси. По-нататък учените работят върху намирането на нови начини за комбиниране на генетични алгоритми с други техники за оптимизация.
Препоръчителни статии
Това е ръководство за това какво е генетичен алгоритъм? Тук обсъждаме въвеждането, фазите и приложенията на генетичния алгоритъм. Можете да разгледате и другите ни предложени статии -
- Алгоритми за маршрутизиране
- Видове алгоритми
- Алгоритми на невронната мрежа
- Алгоритми за извличане на данни
- ръководство за примери на алгоритъм на C ++
