introduction genetic algorithms machine learning
c ++ списък за съседство на графика
Този урок за генетичен алгоритъм обяснява подробно какво представляват генетичните алгоритми и тяхната роля в машинното обучение :
В Предишен урок , научихме за изкуствените невронни мрежови модели - многослоен персептрон, обратно размножаване, радиално отклонение и самоорганизиращи се карти на Kohonen, включително тяхната архитектура.
Ще се съсредоточим върху генетичните алгоритми, които са се появили по-рано от невронните мрежи, но сега GA е поета от NN. Въпреки че GA все още има приложения в реалния живот като проблеми с оптимизацията като планиране, игра на игри, роботика, хардуерен дизайн, проблеми с пътуващи търговци и т.н.
Генетичните алгоритми са алгоритми, които се основават на еволюционната идея за естествения подбор и генетиката. GA са адаптивни евристични алгоритми за търсене, т.е.алгоритмите следват итеративен модел, който се променя с времето. Това е вид обучение за подсилване, при което е необходима обратна връзка, без да се казва правилният път, който трябва да се следва. Отзивите могат да бъдат положителни или отрицателни.
=> Прочетете пълната серия за обучение по машинно обучение
Какво ще научите:
- Защо да използваме генетични алгоритми
- Какво представляват генетичните алгоритми
- Предимства и недостатъци на генетичния алгоритъм
- Приложения на генетични алгоритми
- Заключение
Защо да използваме генетични алгоритми
GA са по-надеждни алгоритми, които могат да се използват за различни проблеми с оптимизацията. Тези алгоритми не се отклоняват лесно при наличие на шум, за разлика от другите алгоритми на AI. GA могат да се използват при търсене на голямо пространство или мултимодално пространство.
Биологичен фон на генетичните алгоритми
Генетиката произлиза от гръцката дума „генезис“, което означава да расте. Генетиката решава факторите за наследственост, приликите и разликите между потомството в процеса на еволюция. Генетичните алгоритми също са получени от естествената еволюция.
Някои терминологии в биологична хромозома
- Хромозоми: Цялата генетична информация на даден вид се съхранява хромозоми.
- Гени: Хромозомите са разделени на няколко части, наречени гени.
- Алели: Гените идентифицират характеристиката на индивида. Възможността комбинация от гени да образува свойство се нарича Алели. Генът може да има различни алели.
- Генофонд: Всички възможни комбинации от гени, които са всички алели в популационен пул, се наричат генофонд.
- Геном: Наборът от гени на даден вид се нарича геном.
- Локус: Всеки ген има позиция в генома, която се нарича локус.
- Генотип: Пълна комбинация от гени в индивида се нарича генотип.
- Фенотип: Набор от генотипове в декодирана форма се нарича фенотип.
Какво представляват генетичните алгоритми
Генетичните алгоритми стимулират процеса както в естествените системи за еволюция. Чарлз Дарвин заяви теорията за еволюцията, че в естествената еволюция биологичните същества се развиват според принципа на „оцеляването на най-силните“. Търсенето на GA има за цел да насърчи теорията за „оцеляването на най-силните“.
GA извършват произволно търсене за решаване на проблеми с оптимизацията. GA използва техники, които използват предишната историческа информация, за да насочат търсенето си към оптимизация в новото пространство за търсене.
Корелация на хромозома с GA
Човешкото тяло има хромозоми, които са изградени от гени. Набор от всички гени на определен вид се нарича геном. При живите същества геномите се съхраняват в различни хромозоми, докато в GA всички гени се съхраняват в една и съща хромозома.
Сравнение между естествената еволюция и терминологията на генетичния алгоритъм
Естествена еволюция | Генетичен алгоритъм |
---|---|
Хромозома | Струна |
Ген | Особеност |
Алел | Стойност на характеристиките |
Генотип | Кодиран низ |
Фенотип | Декодирана структура |
Важна терминология в GA
- Население: Това е група лица. Популацията включва броя на изследваните индивиди, информация за пространството за търсене и параметрите на фенотипа. По принцип популацията се инициализира на случаен принцип.
- Физически лица: Лицата са едно решение в населението. Индивидът има набор от параметри, наречени гени. Гени, комбинирани, за да образуват хромозоми.
- Гени: Гените са градивни елементи на генетичните алгоритми. Хромозомата е изградена от гени. Гените могат да определят решението на проблема. Те са представени от битов (0 или 1) низ с произволна дължина.
- Фитнес: Фитнесът показва стойността на фенотипа на проблема. Функцията за фитнес показва колко близо е решението до оптималното решение. Фитнес функцията се определя по много начини, като например сумата от всички параметри, свързани с проблема - евклидово разстояние и др. Няма правило за оценка на фитнес функцията.
Прост генетичен алгоритъм
Един прост GA има популация от отделни хромозоми. Тези хромозоми представляват възможни решения. Репродуктивните оператори се прилагат върху тези набори хромозоми за извършване на мутации и рекомбинация. Поради това е важно да се намерят подходящи оператори за възпроизвеждане, тъй като поведението на GA зависи от него.
Един прост генетичен алгоритъм е както следва:
# 1) Започнете с популацията, създадена на случаен принцип.
# две) Изчислете фитнес функцията на всяка хромозома.
# 3) Повтаряйте стъпките, докато не се създадат n потомци. Потомците се създават, както е показано по-долу.
- Изберете чифт хромозоми от популацията.
- Пресичане на двойката с вероятност p° Сза формиране на потомство.
- Мутирайте кросоувъра с вероятност pм.
# 4) Заменете първоначалната популация с новата популация и преминете към стъпка 2.
Нека да видим стъпките, следвани в този процес на итерация. Генерира се първоначалната популация от хромозоми. Първоначалната популация трябва да съдържа достатъчно гени, за да може да се генерира всяко решение. Първият пул от популация се генерира произволно.
- Избор: Най-добрият набор от гени се избира в зависимост от фитнес функцията. Избира се струната с най-добрата фитнес функция.
- Възпроизвеждане: Новите потомци се генерират чрез рекомбинация и мутация.
- Оценка: Генерираните нови хромозоми се оценяват за тяхната годност.
- Замяна: В тази стъпка старото население се заменя с новосъздаденото население.
Метод за избор на колело на рулетка
Изборът на рулетка е методът за избор, който се използва широко.
Процесът на подбор е кратък, както е показано по-долу:
При този метод се извършва линейно търсене през колелото на рулетката. Прорезите в колелото се претеглят според индивидуалната стойност на фитнес. Целевата стойност се определя на случаен принцип според пропорцията от сумата на пригодността в популацията.
След това популацията се търси, докато се достигне целевата стойност. Този метод не гарантира най-пригодния от хората, но има вероятност да бъде най-пригодният.
Нека да видим стъпките, включени в избора на рулетка.
Очакваната стойност на индивида = Индивидуална годност / годност на населението. Слотовете на колелата се възлагат на лица въз основа на тяхната годност. Колелото се завърта N пъти, където N е общият брой индивиди в популацията. Когато една ротация приключи, избраният индивид се поставя в група от родители.
- Нека общата очаквана стойност на определен брой индивиди в популацията е S.
- Повторете стъпките 3-5 n пъти.
- Изберете цяло число s между 0 и S.
- Прегледайте индивидите в популацията, сумирайте очакваните стойности, докато сумата не е по-голяма от s.
- Избира се лицето, чиято очаквана стойност поставя сумата над лимита s.
Недостатъци на избора на колела на рулетка:
- Ако фитнесът се различава много, тогава обиколката на колелото на рулетката ще бъде взета максимално от хромозомата с най-висока фитнес функция, така че останалите имат много малък шанс да бъдат избрани.
- Шумно е.
- Еволюцията зависи от разликата във фитнеса на населението.
Други методи за подбор
Има много други методи за подбор, използвани в „Избор“ стъпка на генетичния алгоритъм.
Ще обсъдим 2-те широко използвани метода:
# 1) Избор на ранг: При този метод на всяка хромозома се дава фитнес стойност от класирането. Най-лошата годност е 1, а най-добрата е N. Това е метод за бавна конвергенция. При този метод се запазва разнообразието, което води до успешно търсене.
Избират се потенциални родители и след това се провежда турнир, за да се реши кой от лицата ще бъде родител.
# 2) Избор на турнир: При този метод се прилага стратегия за селективен натиск върху популацията. Най-добрият човек е този с най-висока физическа форма. Този индивид е победител в турнирното състезание сред Nu индивиди от населението.
Популацията на турнира заедно с победителя отново се добавя в пула, за да генерира ново потомство. Разликата във фитнес стойностите на победителя и индивидите в чифтосвания басейн осигурява селективно налягане за оптимални резултати.
Кросоувър
Това е процес на вземане на 2 индивида и създаване на дете от тях. Процесът на възпроизвеждане след селекцията прави клонинги на добрите ужилвания. Операторът на кросоувър се прилага върху струните, за да се получи по-добро потомство.
Изпълнението на оператора за кросоувър е както следва:
- Два индивида са избрани на случаен принцип от популацията, за да дадат потомство.
- Напречно се избира кръстосано място по дължината на низа.
- Стойностите на сайта се разменят.
Изпълненият кросоувър може да бъде едноточков кросоувър, двуточков кросоувър, многоточков кросоувър и др. Едноточковият кросоувър има едно място за кросоувър, докато двуточково кросоувър има 2 сайта, където стойностите се разменят.
Можем да видим това в примера по-долу:
Едноточков кросоувър
Двуточков кросоувър
Вероятност за кросоувър
P° С, вероятност за кросоувър е терминът, който описва колко често ще се извършва кросоувърът. 0% вероятност означава, че новите хромозоми ще бъдат точно копие на старите хромозоми, докато 100% вероятност означава, че всички нови хромозоми са направени чрез кръстосване.
Мутация
Мутацията се извършва след кросоувър. Докато кросоувърът се фокусира само върху текущото решение, операцията за мутация търси цялото пространство за търсене. Този метод е да възстанови загубената генетична информация и да разпространи генетичната информация.
Този оператор помага да се поддържа генетичното разнообразие в популацията. Той помага за предотвратяване на локални минимуми и предотвратява генерирането на безполезни решения от всяка популация.
Мутацията се извършва по много начини, като например обръщане на стойността на всеки ген с малка вероятност или извършване на мутация само ако подобрява качеството на разтвора.
Някои от начините за мутация са:
- Обръщане: Промяна от 0 на 1 или 1 на 0.
- Обмен: Избират се две произволни позиции и стойностите се обменят.
- Заден ход: Избира се произволна позиция и битовете до нея се обръщат.
Нека да видим няколко примера за всеки:
Обръщане
Разменящи се
Назад
Вероятност за мутация
Pм, вероятността за мутация е термин, който решава колко често хромозомите ще бъдат мутирани. Ако вероятността за мутация е 100%, това означава, че цялата хромозома е променена. Ако не се извърши мутация, тогава ново поколение се генерира непосредствено след кръстосването.
Пример за общ генетичен алгоритъм Вероятност за мутация: Pм, вероятността за мутация е термин, който решава колко често хромозомите ще бъдат мутирани. Ако вероятността за мутация е 100%, това означава, че цялата хромозома е променена.
Ако не се извърши мутация, новото потомство се генерира непосредствено след кръстосването. Първоначалната популация на хромозомите е дадена като A, B, C, D. Размерът на популацията е 4.
Функцията за фитнес се приема като число 1 в струната.
Хромозома | Фитнес |
---|---|
До: 00000110 | две |
B: 11101110 | 6 |
C: 00100000 | 1 |
D: 00110100 | 3 |
Сумата на годността е 12, което означава, че средната функция за фитнес ще бъде ~ 12/4 = 3
Вероятност за кросоувър = 0,7
Вероятност за мутация = 0,001
# 1) Ако са избрани B и C, кросоувърът не се извършва, тъй като фитнес стойността на C е под средната годност.
# две) B е мутирал => B: 11101110 -> B': 01101110 за запазване на популационното разнообразие
# 3) Избрани са B и D, изпълнява се кросоувърът.
B: 11101110 E: 10110100 -> D: 00110100 F: 01101110
# 4) Ако Е е мутирал, тогава
E: 10110100 -> E': 10110000
Съответните хромозоми са показани в таблицата по-долу. Поръчката се поставя произволно.
Хромозома | Фитнес |
---|---|
A: 01101110 | 5 |
B: 00100000 | 1 |
С: 10110000 | 3 |
D: 01101110 | 5 |
Въпреки че най-пригодният индивид с фитнес стойност 6 е загубен, общата средна физическа форма на населението се увеличава и ще бъде: 14/4 = 3,5
Кога да спрем генетичния алгоритъм
Генетичният алгоритъм се спира, когато са изпълнени някои условия, изброени по-долу:
# 1) Най-добра индивидуална конвергенция: Когато минималното ниво на фитнес падне под стойността на конвергенция, алгоритъмът се спира. Това води до по-бързо сближаване.
# 2) Най-лошото индивидуално сближаване: Когато най-слабо годни индивиди в популацията достигнат минимална стойност на фитнес под конвергенцията, тогава алгоритъмът се спира. При този метод минималният стандарт за фитнес се поддържа в популацията. Това означава, че най-добрият индивид не е гарантиран, но хората с минимална физическа стойност ще присъстват.
# 3) Сума на фитнес: При този метод, ако сумата на годността е по-малка или равна на стойност на конвергенция, търсенето се спира. Той гарантира, че цялото население е в рамките на фитнес.
# 4) Среден фитнес: При този метод поне половината от индивидите в популацията ще бъдат по-добри или равни на стойността на конвергенция.
Някои критерии за конвергенция или условие за спиране могат да бъдат:
- Когато еволюира определен брой поколения.
- Когато определеното време за стартиране на алгоритъма е изпълнено.
- Когато стойността на пригодността на популацията не се променя допълнително с повторения.
Предимства и недостатъци на генетичния алгоритъм
Предимствата на генетичния алгоритъм са:
- Той има по-широко пространство за решения.
- По-лесно е да откриете глобалния оптимум.
- Паралелизъм: Множество GA могат да работят заедно, използвайки един и същ процесор, без да се намесват помежду си. Те вървят паралелно изолирано.
Ограничения на GA:
- Идентификацията на фитнес функцията е ограничение.
- Сближаването на алгоритмите може да бъде твърде бързо или твърде бавно.
- Има ограничение при избора на параметри като кросоувър, вероятност за мутация, размер на популацията и т.н.
Приложения на генетични алгоритми
GA е ефективен за решаване на проблеми с големи размери. GA се използва ефективно, когато пространството за търсене е много голямо, няма налични математически техники за решаване на проблеми и други традиционни алгоритми за търсене не работят.
Някои приложения, в които се използва GA:
- Проблем с оптимизацията: Един от най-добрите примери за проблеми с оптимизацията е проблемът с продавача на пътници, който използва GA. Широко се използват и други проблеми с оптимизацията, като планиране на задания, оптимизиране на качеството на звука.
- Модел на имунната система: GA се използват за моделиране на различни аспекти на имунната система за отделни генни и многогенни семейства по време на еволюцията.
- Машинно обучение: GA са използвани за решаване на проблеми, свързани с класификация, прогнозиране, създаване на правила за обучение и класификация .
Заключение
Генетичните алгоритми се основават на метода на естествената еволюция. Тези алгоритми се различават от другите класификационни алгоритми, тъй като те използват кодирани параметри (0 или 1), има множество хора в популация и те използват вероятностния метод за конвергенция.
С процеса на кросоувър и мутация GA се сближават при следващи поколения. Изпълнението на алгоритъм на GA не гарантира успешно решение винаги. Генетичните алгоритми са с висока ефективност при оптимизиране - проблеми с планирането на работа.
Надявам се този урок да е обогатил вашите познания за концепцията за генетичните алгоритми !!
=> Посетете тук за ексклузивната серия за машинно обучение
Препоръчително четене
- Моделно тестване с използване на генетичен алгоритъм
- Извличане на данни срещу машинно обучение срещу изкуствен интелект срещу дълбоко обучение
- Урок за машинно обучение: Въведение в ML и неговите приложения
- Видове машинно обучение: Контролирано срещу ненаблюдавано обучение
- Пълно ръководство за изкуствена невронна мрежа в машинното обучение
- 11 Най-популярни софтуерни инструменти за машинно обучение през 2021 г.
- Топ 13 НАЙ-ДОБРИ компании за машинно обучение [Списък на актуализираните 2021 г.]
- Какво е поддръжка на векторна машина (SVM) в машинно обучение