Увод у генетске алгоритме у машинском учењу

introduction genetic algorithms machine learning

Питања и одговори са ХП-овим центром за квалитет

Овај водич за генетски алгоритам детаљно објашњава шта су генетски алгоритми и њихова улога у машинском учењу :

У Претходни водич , сазнали смо о моделима вештачке неуронске мреже - вишеслојном перцептрону, повратном ширењу, радијалном пристрасности и Кохоненовим самоорганизујућим мапама, укључујући њихову архитектуру.

Усредсредићемо се на генетске алгоритме који су се појавили пре него на неуронске мреже, али сада је НН преузео ГА. Иако ГА још увек има апликације у стварном животу као што су проблеми са оптимизацијом попут распореда, играња игара, роботике, дизајна хардвера, проблема трговаца, итд.

Генетички алгоритми су алгоритми који се заснивају на еволутивној идеји природне селекције и генетике. ГА су адаптивни хеуристички алгоритми претраживања, тј. Алгоритми следе итеративни образац који се мења с временом. То је врста учења појачања где су повратне информације неопходне, а да се не каже тачан пут који треба следити. Повратне информације могу бити позитивне или негативне.

=> Прочитајте комплетну серију обука за машинско учење

Шта ћете научити:

• Зашто користити генетске алгоритме
  • Биолошка позадина генетичких алгоритама
• Шта су генетски алгоритми
  • Корелација хромозома са ГА
  • Важна терминологија у ГА
  • Једноставан генетски алгоритам
  • Метода одабира точка рулета
  • Остале методе избора
  • Цроссовер
  • Мутација
  • Када зауставити генетски алгоритам
• Предности и недостаци генетског алгоритма
• Примене генетичких алгоритама
• Закључак
  • Препоручено читање

Зашто користити генетске алгоритме

ГА су робуснији алгоритми који се могу користити за различите проблеме оптимизације. Ови алгоритми не одступају лако у присуству шума, за разлику од других алгоритама АИ. ГА се могу користити у потрази за великим простором или мултимодалним простором.

Биолошка позадина генетичких алгоритама

Генетика је изведена из грчке речи, „генеза“, што значи расти. Генетика одлучује о факторима наследности, сличностима и разликама између потомака у процесу еволуције. Генетски алгоритми су такође изведени из природне еволуције.

Неке терминологије у биолошком хромозому

• Хромозоми: Све генетске информације о врсти су похрањени хромозоми.
• Гени: Хромозоми су подељени у неколико делова који се називају гени.
• Алели: Гени идентификују карактеристике појединца. Могућност комбинације гена да формирају својство назива се Алелес. Ген може имати различите алеле.
• Генски фонд: Све могуће комбинације гена који су сви алели у популацијском фонду називају се генетским фондом.
• Геном: Скуп гена неке врсте назива се геном.
• Лоцус: Сваки ген има положај у геному који се назива локус.
• Генотип: Пуна комбинација гена код појединца назива се генотип.
• Фенотип: Скуп генотипова у декодираном облику назива се фенотип.

Шта су генетски алгоритми

Генетски алгоритми стимулишу процес као у природним системима за еволуцију. Цхарлес Дарвин је изјавио теорију еволуције да се у природној еволуцији биолошка бића развијају према принципу „преживљавања најспособнијих“. Претрага ГА осмишљена је да подстакне теорију о „преживљавању најспособнијих“.

Генерални аналитичари врше насумичну претрагу како би решили проблеме оптимизације. Генерална аналитика користи технике које користе претходне историјске информације да би своју претрагу усмерила ка оптимизацији у новом простору за претрагу.

Корелација хромозома са ГА

Људско тело има хромозоме који су направљени од гена. Скуп свих гена одређене врсте назива се геном. У живим бићима, геноми су ускладиштени у различитим хромозомима, док су у ГА сви гени ускладиштени у истом хромозому.

Поређење између природне еволуције и терминологије генетског алгоритма

Важна терминологија у ГА

• Популација: То је група појединаца. Популација укључује број јединки које се тестирају, информације о простору за претрагу и параметре фенотипа. Генерално се популација насумично иницијализује.
• Физичка лица: Појединци су једно решење у популацији. Појединац има скуп параметара који се називају гени. Гени комбиновани да би формирали хромозоме.
• Гени: Гени су градивни блокови генетичких алгоритама. Хромозом се састоји од гена. Гени могу одредити решење проблема. Они су представљени битним (0 или 1) низом случајне дужине.
• Фитнесс: Фитнес говори вредност фенотипа проблема. Функција фитнеса говори колико је решење близу оптималном решењу. Фитнес функција се одређује на више начина, као што је збир свих параметара који се односе на проблем - еуклидска удаљеност итд. Не постоји правило за процену фитнес функције.

Једноставан генетски алгоритам

Једноставни ГА има популацију појединачних хромозома. Ови хромозоми представљају могућа решења. Оператори репродукције се примењују преко ових скупова хромозома да би се извршиле мутације и рекомбинација. Стога је важно пронаћи одговарајуће операторе репродукције, јер понашање ГА зависи од тога.

Једноставан генетски алгоритам је следећи:

# 1) Почните са популацијом створеном случајно.

#два) Израчунајте фитнес функцију сваког хромозома.

# 3) Понављајте кораке док се не створи н потомстава. Потомци се стварају како је приказано доле.

• Изаберите пар хромозома из популације.
• Укрштање пара са вероватноћом п_цда се формирају потомци.
• Мутирајте укрштање са вероватноћом п_м.

# 4) Замените првобитно становништво новим и пређите на корак 2.

Погледајмо кораке који су следећи у овом поступку понављања. Генерише се почетна популација хромозома. Почетна популација треба да садржи довољно гена како би било које решење могло да се створи. Први фонд становништва генерише се насумично.

• Избор: Најбољи скуп гена се бира у зависности од функције кондиције. Одабрана је жица са најбољом фитнес функцијом.
• Репродукција: Нова потомства настају рекомбинацијом и мутацијом.
• Процена: Нови генерисани хромозоми процењују се у складу са њиховом кондицијом.
• Замена: У овом кораку старо становништво се замењује новонасталим становништвом.

Метода одабира точка рулета

Избор точкића рулета је метода избора која се широко користи.

Процес одабира је кратак како је приказано у наставку:

У овој методи врши се линеарно претраживање кроз точак рулета. Прорези у точку се мере према индивидуалној вредности кондиције. Циљна вредност се поставља случајно према пропорцији збира кондиције у популацији.

Популација се затим претражује док се не достигне циљана вредност. Овај метод не гарантује најспособније особе, али има вероватноћу да ће бити најспособнији.

Погледајмо кораке који су укључени у избор рулета.

Очекивана вредност појединца = Индивидуална кондиција / кондиција становништва. Прорези за точкове додељују се појединцима на основу њихове кондиције. Точак се окреће Н пута, где је Н укупан број јединки у популацији. Када се заврши једна ротација, изабрани појединац се ставља у групу родитеља.

1. Нека укупна очекивана вредност броја јединки у популацији буде С.
2. Поновите кораке 3-5 н пута.
3. Изаберите цео број с између 0 и С.
4. Прелистајте појединце у популацији, сумирајте очекиване вредности док зброј не буде већи од с.
5. Одабран је појединац чија очекивана вредност ставља зброј преко ограничења с.

Недостаци избора рулет кола:

1. Ако се кондиција јако разликује, обим точкића рулета максимално ће бити прихваћен хромозомом са највишом фитнес функцијом, тако да остали имају врло мало шанси да буду изабрани.
2. Бучно је.
3. Еволуција зависи од разлике у кондицији популације.

Остале методе избора

Постоје многи други начини избора који се користе у „Избор“ корак генетског алгоритма.

Разговараћемо о 2 друге широко коришћене методе:

# 1) Избор ранга: У овој методи, сваком хромозому се даје оцена кондиције из рангирања. Најгора кондиција је 1, а најбоља је Н. То је метода споре конвергенције. Овом методом различитост је очувана што доводи до успешне претраге.

Бирају се потенцијални родитељи, а затим се одржава турнир на коме се одлучује ко ће од појединаца бити родитељ.

# 2) Избор турнира: У овој методи се на популацију примењује селективна стратегија притиска. Најбољи појединац је онај са највећом кондицијом. Овај појединац је победник турнирског такмичења међу Ну појединцима у популацији.

Турнирска популација заједно са победником поново се додаје у базен да би се створило ново потомство. Разлика у фитнес вредностима победника и појединаца у базену за парење пружа селективни притисак за оптималне резултате.

Цроссовер

То је процес узимања 2 особе и рађања детета од њих. Процес размножавања након селекције чини клонове добрих убода. Оператор укрштања се примењује преко жица да би се добио бољи потомак.

Имплементација цроссовер оператора је следећа:

1. Две јединке су случајно одабране из популације ради стварања потомства.
2. Унакрсно место се бира случајно дуж дужине низа.
3. Вредности на локацији се замењују.

Извршено укрштање може бити укрштање са једном тачком, укрштање са две тачке, укрштање са више тачака итд. Укрштање са једном тачком има једно место укрштања, док место укрштања са две тачке има 2 места у којима се вредности замењују.

То можемо видети у доњем примеру:

Цросспоинт једноточка

Двоструки кросовер

Цроссовер Пробабилити

П._ц, вероватноћа укрштања је термин који описује колико често ће се укрштање изводити. 0% вероватноће значи да ће нови хромозоми бити тачна копија старих хромозома, док 100% вероватноћа значи да су сви нови хромозоми направљени укрштањем.

Мутација

Мутација се врши након укрштања. Док се цроссовер фокусира само на тренутно решење, операција мутације претражује читав простор претраживања. Овом методом се обнављају изгубљене генетске информације и дистрибуирају генетске информације.

Овај оператер помаже у одржавању генетске разноликости у популацији. Помаже у спречавању локалних минимума и спречава генерисање бескорисних решења од било које популације.

Мутација се изводи на много начина, на пример, са малим вероватноћама инвертовање вредности сваког гена или извођење мутације само ако побољшава квалитет раствора.

Неки од начина мутације су:

• Преокретање: Промена од 0 до 1 или 1 до 0.
• Размјена: Изаберу се два случајна положаја, а вредности се замењују.
• Вожња уназад: Бира се случајни положај и битови поред њега се обрћу.

Погледајмо неколико примера сваког од њих:

Превртање

Размењивање

Вожња уназад

Вероватноћа мутације

П._м, вероватноћа мутације је појам који одређује колико ће често хромозоми бити мутирани. Ако је вероватноћа мутације 100%, то значи да је промењен цео хромозом. Ако се мутација не изврши, тада се ново потомство генерише непосредно након укрштања.

Пример општег генетског алгоритма Вероватноћа мутације: П._м, вероватноћа мутације је појам који одређује колико ће често хромозоми бити мутирани. Ако је вероватноћа мутације 100%, то значи да је промењен цео хромозом.

Ако се мутација не изврши, тада се ново потомство генерише непосредно након укрштања. Почетна популација хромозома дата је као А, Б, Ц, Д. Величина популације је 4.

Функција фитнеса узима се као број 1 у низу.

Збир кондиције је 12 што подразумева да би просечна функција кондиције била ~ 12/4 = 3

Вероватноћа укрштања = 0,7

Вероватноћа мутације = 0,001

# 1) Ако су изабрани Б и Ц, укрштање се не изводи јер је кондициона вредност Ц испод просечне кондиције.

#два) Б је мутиран => Б: 11101110 -> Б.^': 01101110 ради очувања разноликости становништва

# 3) Бирају се Б и Д, врши се укрштање.

Б: 11101110 Е: 10110100 -> Д: 00110100 Ф: 01101110

# 4) Ако је Е мутиран, онда

Е: 10110100 -> Е.^': 10110000

Одговарајући хромозоми приказани су у доњој табели. Наруџба се ставља насумично.

Иако је изгубљен најспособнији појединац са кондицијском вредношћу од 6, укупна просечна спремност популације се повећава и износила би: 14/4 = 3,5

Када зауставити генетски алгоритам

Генетски алгоритам се зауставља када су испуњени неки доле наведени услови:

# 1) Најбоља појединачна конвергенција: Када минимални ниво фитнеса падне испод вредности конвергенције, алгоритам се зауставља. То доводи до брже конвергенције.

# 2) Најгора појединачна конвергенција: Када најмање способни појединци у популацији достигну минималну вредност кондиције испод конвергенције, тада се алгоритам зауставља. Овом методом у популацији се одржава минимални стандард кондиције. То значи да најбољи појединац није загарантован, али појединци са минималном вредношћу фитнеса ће бити присутни.

# 3) Збир фитнеса: У овом методу, ако је збир фитнеса мањи или једнак вредности конвергенције, претрага се зауставља. Гарантује да је сва популација у распону кондиције.

# 4) Средњи фитнес: У овој методи, најмање половина појединаца у популацији биће боља или једнака вредности конвергенције.

Неки критеријум конвергенције или услов заустављања могу бити:

• Када је одређени број генерација еволуирао.
• Када се испуни одређено време за покретање алгоритма.
• Када се кондициона вредност популације не мења даље са понављањима.

Предности и недостаци генетског алгоритма

Предности генетског алгоритма су:

1. Има шири простор решења.
2. Лакше је открити глобални оптимум.
3. Паралелизам: Више ГА-ова може радити заједно користећи исти ЦПУ без међусобног ометања. Паралелно теку изоловано.

Ограничења ГА:

1. Идентификација фитнес функције је ограничење.
2. Конвергенција алгоритама може бити пребрза или преспора.
3. Постоји ограничење избора параметара као што су укрштање, вероватноћа мутације, величина популације итд.

Примене генетичких алгоритама

ГА је ефикасан за решавање проблема са високим димензијама. ГА се ефикасно користи када је простор за претрагу веома велик, не постоје математичке технике решавања проблема и други традиционални алгоритми претраживања не раде.

Неке апликације у којима се користи ГА:

• Проблем оптимизације: Један од најбољих примера проблема са оптимизацијом је проблем продавача путовања који користи ГА. Остали проблеми са оптимизацијом, као што су распоређивање послова, оптимизација квалитета звука, широко се користе.
• Модел имуног система: ГА се користе за моделирање различитих аспеката имуног система за поједине генетске и вишегенезне породице током еволутивног времена.
• Машинско учење: ГА се користе за решавање проблема у вези са класификацијом, предвиђањем, стварањем правила за учење и класификацију .

Закључак

Генетски алгоритми се заснивају на методи природне еволуције. Ови алгоритми се разликују од осталих алгоритама за класификацију јер користе кодиране параметре (0 или 1), у популацији постоји вишеструки број појединаца и за конвергенцију користе пробабилистички метод.

Процесом укрштања и мутације, ГА конвергирају у следећим генерацијама. Извршење ГА алгоритма не гарантује увек успешно решење. Генетички алгоритми су високо ефикасни у оптимизацији - проблеми заказивања послова.

Надам се да би вам овај водич обогатио знање о концепту генетичких алгоритама !!

=> Посетите овде за ексклузивну серију машинског учења

Препоручено читање

• Испитивање засновано на моделу користећи генетски алгоритам
• Дата Мининг вс Мацхине Леарнинг вс Артифициал Интеллигенце вс Дееп Леарнинг
• Водич за машинско учење: Увод у МЛ и његове примене
• Врсте машинског учења: Надгледано против ненадгледаног учења
• Комплетан водич за вештачку неуронску мрежу у машинском учењу
• 11 Најпопуларнијих софтверских алата за машинско учење 2021
• Топ 13 НАЈБОЉИХ компанија за машинско учење (Ажурирана листа 2021)
• Шта је подршка за векторску машину (СВМ) у машинском учењу