Преглед генетског алгоритма
Технике оптимизације су технике које се користе како би се пронашло најбоље решење од свих могућих решења која су доступна под ограничењима која постоје. Дакле, Генетски алгоритам је један такав алгоритам оптимизације који је изграђен на основу природног еволутивног процеса наше природе. Овде се користи идеја природне селекције и генетског наследства. Користи вођену случајну претрагу, за разлику од других алгоритама, тј. Проналажење оптималног рјешења почевши с функцијом случајних почетних трошкова, а затим претражујући само у простору који има најмање трошкове (у вођеном смјеру). Погодно када радите са огромним и сложеним скуповима података.
Шта је генетски алгоритам?
Генетски алгоритам заснован је на генетској структури и понашању хромозома популације. Следеће ствари су темељ генетских алгоритама.
- Сваки хромозом указује на могуће решење. Тако је популација збир хромозома.
- Сваког појединца у популацији карактерише фитнес функција. Рјешење је боље кондиције.
- Од расположивих јединки у популацији, најбоље јединке се користе за репродукцију потомства нове генерације.
- Настало потомство имаће карактеристике оба родитеља и резултат је мутације. Мутација је мала промена у структури гена.
Фазе генетског алгоритма
Испод су различите фазе генетског алгоритма:
1. Иницијализација становништва (кодирање)
- Сваки ген представља параметар (променљиве) у раствору. Ова збирка параметара која формира раствор је хромозом. Популација је колекција хромозома.
- Редослед гена по питању хромозома.
- Већина временских хромозома је приказана у бинарним форматима као 0 и 1, али могући су и други кодирања.
2. Функција фитнеса
- Од расположивих хромозома морамо одабрати оне који су најбољи за репродукцију потомка, тако да сваки хромосом добија фитнес вредност.
- Фитнесс резултат помаже у одабиру појединаца који ће се користити за репродукцију.
3. Избор
- Главни циљ ове фазе је пронаћи регион у којем су шансе за најбоље решење веће.
- Инспирација за то је из опстанка најбољих.
- То би требао бити баланс између истраживања и искориштавања простора за претраживање.
- ГА покушава да премести генотип у вишу кондицију у простору за претрагу.
- Превелика пристраност одабира фитнеса може довести до оптималних решења.
- Премало одабира пристраности фитнеса резултира не фокусираном претрагом.
- Тако се користи пропорционална селекција фитнеса, која је позната и као селекција колута на рулету, генетски оператор који се користи у генетским алгоритмима за избор потенцијално корисних решења за рекомбинацију.
4. Репродукција
Генерација потомства се дешава на два начина:
- Цроссовер
- Мутација
а) Цроссовер
Цроссовер је најбитнија фаза у генетском алгоритму. Током цроссовер-а, одабире се случајна тачка док паре пар родитеља како би се створили потомци.
Постоје 3 главне врсте цроссовера.
- Цросс поинт цроссовер: Тачка на хромосомима оба родитеља бирана је насумично и означена као „цроссовер поинт“. Битови десно од те тачке размењују се између два матична хромозома.
- Цросс-цроссовер у две тачке : Две тачке укрштања изабране су насумично из матичних хромозома. Комадићи између две тачке се мењају између матичних организама.
- Униформни кросовер: У униформном кросоверу, типично се сваки бит бира из било којег родитеља са једнаком вероватноћом.
Ново потомство се додаје становништву.
б) Мутација
У неколико формираних нових потомака, неки од њихових гена могу се подвргнути мутацијама уз малу случајну вероватноћу. Ово указује да се неки делови у битном хромозому могу окренути. Мутација се дешава да би се побринула за различитост становништва и зауставила преурањена конвергенција.
5. Конвергенција (када престати)
Неколико правила која слиједе и која говоре када треба зауставити је сљедећа:
- Када не дође до побољшања квалитета раствора након завршетка одређеног броја генерација постављених пред руку.
- Када се достигне тежак и брз распон генерација и времена.
- Док се не добије прихватљиво решење.
Примена генетског алгоритма
У овом одељку ћемо говорити о неким областима у којима се генетски алгоритам често примењује.
1. Усмеравање путовања и отпреме
Проблем путничког продавца једна је од главних примена генетског алгоритма. На пример, када се од планера путовања тражи да планира путовање, он би узео помоћ генетичког алгоритма који не само да помаже у смањењу укупних трошкова путовања, већ и у смањењу времена.ГЕ се такође користи за планирање испоруке производа од места до места на најбољи ефикасан начин.
2. Роботика
Генетски алгоритам се широко користи у области роботике. Роботи се међусобно разликују по намену за који су изграђени. На пример, неколицина је направљена за задатак кувања, мало је који се гради за наставне задатке итд.
- Избор важних карактеристика у датом скупу података.
- У традиционалном методу, важне карактеристике у скупу података бирају се следећом методом. тј. Погледате важност тог модела, поставите вриједност прага за значајке, а ако значајка има значајност већу од прага, сматра се.
- Али овде користимо методу која се зове проблем са руксаком.
- Поново ћемо почети са популацијом хромозома, где ће сваки хромозом бити бинарни низ. 1 ће означавати „укључивање“ карактеристике у модел, а 0 ће означавати „искључење“ карактеристике у моделу.
- Фитнес функција овде ће бити наша тачност мерења такмичења. Што је прецизнији наш хромозом у предвиђању вредности, то ће он бити прикладнији.
- Постоје многе друге апликације генетских алгоритама као што су ДНК анализа, апликације за заказивање, Инжењерски дизајн.
Закључак
У тренутном сценарију, ГЕ се користи у великим производним компанијама попут авиона итд. Како би се оптимизирало коришћење времена и ресурса. Даље научници раде на проналажењу нових начина за комбиновање генетских алгоритама са другим техникама оптимизације.
Препоручени чланци
Ово је водич за шта је генетски алгоритам? Овдје разговарамо о увођењу, фазама и примјени генетског алгоритма. Можете и да прођете кроз друге наше предложене чланке -
- Алгоритми усмјеравања
- Врсте алгоритама
- Алгоритми неуронске мреже
- Алгоритми за рударјење података
- водич за примере алгоритма Ц ++