ხელოვნური ინტელექტის სფეროში, ევოლუციური ალგორითმი (EA) არის მთლიანი მოსახლეობის გამოთვლების ქვეჯგუფი, რომელიც დაფუძნებულია მეტაევრისტულ ოპტიმიზაციაზე. EA იყენებს ბიოლოგიური განვითარებით შთაგონებულ მექანიზმებს, როგორიცაა რეპროდუქცია, მუტაცია, რეკომბინაცია და შერჩევა. ევოლუციური ოპტიმიზაციის ალგორითმების პრობლემის კანდიდატური გადაწყვეტა პოპულაციაში ინდივიდების როლს ასრულებს. და ასევე ფიტნეს ფუნქცია განსაზღვრავს პასუხების ხარისხს.
ევოლუციური ალგორითმები ხშირად კარგად ახდენენ ყველა სახის პრობლემის გადაწყვეტილებებს. იმიტომ, რომ იდეალურ შემთხვევაში ისინი არ აკეთებენ რაიმე ვარაუდს ფიტნეს ლანდშაფტის შესახებ. ევოლუციური მოდელირებისა და გენეტიკური ალგორითმებისთვის გამოყენებული მეთოდები ჩვეულებრივ შემოიფარგლება მიკროევოლუციური პროცესების შესწავლით და უჯრედულ ეტაპებზე დაფუძნებული მოდელების დაგეგმვით. უმეტეს რეალურ EA აპლიკაციებში, გამოთვლითი სირთულე არის ამკრძალავი ფაქტორი.
რეალურადეს საკითხი დაკავშირებულია ფიტნეს ფუნქციის შეფასებასთან. ფიტნეს დაახლოება არის ერთ-ერთი გამოსავალი ამ სირთულის დასაძლევად. თუმცა, ერთი შეხედვით მარტივ EA-ს შეუძლია გადაჭრას ხშირად რთული პრობლემები. შესაბამისად, არ შეიძლება იყოს პირდაპირი კავშირი მიმდევრობის სირთულესა და პრობლემას შორის. დამატებითი დეტალები შეგიძლიათ იხილოთ წიგნებში "ევოლუციური ალგორითმები".
განხორციელება
ნაბიჯი პირველი არის ინდივიდების საწყისი პოპულაციის შექმნა შემთხვევითად.
მეორე ნაბიჯი არის ამ ჯგუფის თითოეული ინდივიდის ვარგისიანობის შეფასება (დროის ლიმიტი, საკმარისი მზადყოფნა და ა.შ.).
ნაბიჯი მესამე - გაიმეორეთ შემდეგი რეგენერაციის ნაბიჯები ბოლომდე:
- აირჩიეთ გამრავლებისთვის ყველაზე შესაფერისი ადამიანები (მშობლები).
- მოიტანეთ ახალი ინდივიდები, რომლებმაც გაიარეს ევოლუციური ალგორითმი კროსოვერის და მუტაციის გამოყენებით შთამომავლობის მისაღებად.
- შეაფასეთ ახალი ადამიანების ინდივიდუალური ფიტნესი.
- შეცვალეთ ყველაზე ნაკლებად შესაფერისი პოპულაცია მათთან ერთად.
ტიპები
გენეტიკური ალგორითმი არის ევოლუციური თანმიმდევრობა, ექსპერტი მრჩევლის ყველაზე პოპულარული ტიპი. პრობლემის გადაწყვეტა მოძებნილია რიცხვების სტრიქონების სახით (ტრადიციულად ორობითი, თუმცა საუკეთესო წარმოდგენები, როგორც წესი, არის ის, რაც უფრო მეტს ასახავს პრობლემის გადაჭრას) ოპერატორების გამოყენებით, როგორიცაა რეკომბინაცია და მუტაცია (ზოგჯერ ერთი, ზოგიერთ შემთხვევაში ორივე.). ამ ტიპის ექსპერტი მრჩეველი ხშირად გამოიყენება ოპტიმიზაციის პრობლემებში. ამის კიდევ ერთი სახელია fetura (ლათინურიდან "დაბადება"):
- გენეტიკური პროგრამირება. იგი წარმოადგენს გადაწყვეტილებებს როგორც კომპიუტერული კოდების სახით და მათი ვარგისიანობა განისაზღვრება გამოთვლითი ამოცანების შესრულების უნარით.
- ევოლუციური პროგრამირება. ევოლუციური გენეტიკური ალგორითმის მსგავსი, მაგრამ სტრუქტურა ფიქსირდება და მისი რიცხვითი პარამეტრები შეიძლება შეიცვალოს.
- პროგრამირებადი გენის ექსპრესია. ავითარებს კომპიუტერულ აპლიკაციებს, მაგრამ იკვლევს გენოტიპ-ფენოტიპის სისტემას, სადაც სხვადასხვა ზომის პროექტები დაშიფრულია ფიქსირებული სიგრძის ხაზოვან ქრომოსომებზე.
- სტრატეგია. მუშაობს რეალური რიცხვების ვექტორებთან ამონახსნების სახით. ჩვეულებრივ იყენებს თვითადაპტაციურ ევოლუციური მუტაციის სიჩქარის ალგორითმებს.
- დიფერენციალური განვითარება. დაფუძნებულია ვექტორულ განსხვავებებზე და, შესაბამისად, პირველ რიგში შესაფერისია რიცხვითი ოპტიმიზაციის ამოცანებისთვის.
- ნეიროევოლუცია. ევოლუციური პროგრამირებისა და გენეტიკური ალგორითმების მსგავსი. მაგრამ ეს უკანასკნელი არის ხელოვნური ნერვული ქსელები, რომლებიც აღწერს კავშირების სტრუქტურას და წონას. გენომის კოდირება შეიძლება იყოს პირდაპირი ან არაპირდაპირი.
შედარება ბიოლოგიურ პროცესებთან
ბევრი ევოლუციური ალგორითმის შესაძლო შეზღუდვა არის გენოტიპსა და ფენოტიპს შორის მკაფიო განსხვავების არარსებობა. ბუნებაში, განაყოფიერებული კვერცხუჯრედი გადის რთულ პროცესს, რომელიც ცნობილია როგორც ემბრიოგენეზი, რათა მომწიფდეს. ითვლება, რომ ეს არაპირდაპირი კოდირება უფრო საიმედოს ხდის გენეტიკურ ძიებას (ანუ ნაკლებად სავარაუდოა, რომ გამოიწვიოს ფატალური მუტაციები) და ასევე შეიძლება გააუმჯობესოს ორგანიზმის განვითარების უნარი. ასეთი არაპირდაპირი (სხვა სიტყვებით,გენერაციული ან განვითარების) კოდირებები ევოლუციას საშუალებას აძლევს გამოიყენოს კანონზომიერება გარემოში.
ბოლო სამუშაოები ხელოვნურ ემბრიოგენეზსა და განვითარების სისტემებში ამ საკითხების გადაჭრას ცდილობს. გენის ექსპრესიის დაპროგრამებისას, გენოტიპ-ფენოტიპის რეგიონი წარმატებით არის შესწავლილი, სადაც პირველი შედგება ფიქსირებული სიგრძის წრფივი მრავალგენური ქრომოსომებისგან, ხოლო მეორე მრავალი გამოხატვის ხეებიდან ან სხვადასხვა ზომისა და ფორმის კომპიუტერული პროგრამებისგან.
დაკავშირებული ტექნიკა
ალგორითმები მოიცავს:
- ჭიანჭველების კოლონიის ოპტიმიზაცია. იგი ემყარება იმ აზრს, რომ მწერები ეძებენ საკვებს ფერომონებთან შეერთებით, რათა შექმნან ბილიკები. ძირითადად შესაფერისია კომბინატორული ოპტიმიზაციისა და გრაფიკის პრობლემებისთვის.
- Root სლაიდერის ალგორითმი. შემქმნელი შთაგონებული იყო მცენარეების ფესვების ფუნქციით ბუნებაში.
- ალგორითმი ხელოვნური ფუტკრის კოლონიებისთვის. თაფლის ფუტკრების ქცევაზე დაყრდნობით. ის ძირითადად შემოთავაზებულია რიცხვითი ოპტიმიზაციისთვის და გაფართოებულია კომბინატორიული, შემოსაზღვრული და მრავალობიექტური ამოცანების გადასაჭრელად. ფუტკრის ალგორითმი ეფუძნება მწერების კვების ქცევას. იგი გამოიყენება მრავალ აპლიკაციაში, როგორიცაა მარშრუტიზაცია და დაგეგმვა.
- ნაწილაკების ჯგუფის ოპტიმიზაცია - ცხოველთა ნახირის ქცევის იდეებზე დაყრდნობით. და ასევე, უპირველეს ყოვლისა, შესაფერისია რიცხვითი პროცესის ამოცანებისთვის.
სხვა პოპულარული მეტაევრისტული მეთოდები
- ნადირობის ძიება. მეთოდი, რომელიც ეფუძნება გარკვეული ცხოველების ჯგუფურ დაჭერას, როგორიცაა მგლები, მაგალითად, რომელიცანაწილებენ თავიანთ მოვალეობებს მტაცებლის გარშემო. ევოლუციური ალგორითმის თითოეული წევრი გარკვეულწილად უკავშირდება სხვებს. ეს განსაკუთრებით ეხება ლიდერს. ეს არის უწყვეტი ოპტიმიზაციის მეთოდი, რომელიც ადაპტირებულია როგორც კომბინაციური პროცესის მეთოდი.
- ძიება გაზომვების მიხედვით. ბუნებაზე დაფუძნებული მეტაევრისტული მეთოდებისგან განსხვავებით, ადაპტაციური პროცესის ალგორითმი არ იყენებს მეტაფორას მთავარ პრინციპად. პირიქით, ის იყენებს მარტივ შესრულებაზე ორიენტირებულ მეთოდს, რომელიც ეფუძნება საძიებო განზომილების თანაფარდობის პარამეტრის განახლებას ყოველი გამეორებისას. Firefly ალგორითმი შთაგონებულია იმით, თუ როგორ იზიდავენ ციცინათელები ერთმანეთს მოციმციმე შუქით. ეს განსაკუთრებით სასარგებლოა მულტიმოდალური ოპტიმიზაციისთვის.
- მოძებნეთ ჰარმონია. მუსიკოსების ქცევის იდეებზე დაყრდნობით. ამ შემთხვევაში, ევოლუციური ალგორითმები არის კომბინატორული ოპტიმიზაციის გზა.
- გაუსური ადაპტაცია. ინფორმაციის თეორიაზე დაყრდნობით. გამოიყენება მაქსიმალური შესრულებისა და საშუალო ხელმისაწვდომობისთვის. ევოლუციური ალგორითმების მაგალითი ამ სიტუაციაში: ენტროპია თერმოდინამიკაში და ინფორმაციის თეორიაში.
მემეტიკ
ჰიბრიდული მეთოდი, რომელიც დაფუძნებულია რიჩარდ დოკინსის იდეაზე მემის შესახებ. ის ჩვეულებრივ იღებს პოპულაციაზე დაფუძნებული ალგორითმის ფორმას, რომელიც შერწყმულია ინდივიდუალურ სასწავლო პროცედურებთან, რომელსაც შეუძლია ადგილობრივი დახვეწის განხორციელება. ხაზს უსვამს პრობლემის სპეციფიკური ცოდნის გამოყენებას და მცდელობებს მოაწყოს წვრილმარცვლოვანი და გლობალური ძიებები სინერგიული გზით.
ევოლუციურიალგორითმები არის ევრისტიკული მიდგომა ამოცანების მიმართ, რომლებიც ადვილად ვერ გადაიჭრება პოლინომიურ დროში, როგორიცაა კლასიკური NP-მყარი ამოცანები და ნებისმიერი სხვა, რომლის ამომწურავ დამუშავებას ძალიან დიდი დრო დასჭირდება. დამოუკიდებლად გამოყენებისას ისინი ჩვეულებრივ გამოიყენება კომბინატორული პრობლემებისთვის. თუმცა, გენეტიკური ალგორითმები ხშირად გამოიყენება სხვა მეთოდებთან ერთად, რაც სწრაფი გზაა სამუშაოს მრავალი ოპტიმალური საწყისი ადგილის მოსაძებნად.
ევოლუციური ალგორითმის (ცნობილი, როგორც მრჩეველი) წინაპირობა საკმაოდ მარტივია იმის გათვალისწინებით, რომ თქვენ იცნობთ ბუნებრივი გადარჩევის პროცესს. ის შეიცავს ოთხ ძირითად საფეხურს:
- ინიციალიზაცია;
- არჩევანი;
- გენეტიკური ოპერატორები;
- დასრულება.
თითოეული ეს ნაბიჯი უხეშად შეესაბამება ბუნებრივი გადარჩევის გარკვეულ ასპექტს და გთავაზობთ ამ კატეგორიის ალგორითმების მოდულარიზაციის მარტივ გზებს. მარტივად რომ ვთქვათ, EA-ში საუკეთესო წევრები გადარჩებიან და გამრავლდებიან, ხოლო უვარგისი წევრები იღუპებიან და არ შეუწყობენ ხელს მომავალი თაობის გენოფონდს.
ინიციალიზაცია
ალგორითმის დასაწყებად, ჯერ უნდა შექმნათ გადაწყვეტილებების ნაკრები. პოპულაცია შეიცავს შესაძლო პრობლემური განცხადებების თვითნებურ რაოდენობას, რომლებსაც ხშირად უწოდებენ წევრებს. ისინი ხშირად წარმოიქმნება შემთხვევით (დავალების შეზღუდვების ფარგლებში) ან, თუ წინასწარი ცოდნა ცნობილია, სავარაუდოთ ორიენტირებულია იმაზე, რაც იდეალად ითვლება. მნიშვნელოვანია, რომ მოსახლეობამ მოიცვას გადაწყვეტილებების ფართო სპექტრი,რადგან ეს არსებითად გენოფონდია. ამიტომ, თუ ადამიანს სურს გამოიკვლიოს მრავალი განსხვავებული შესაძლებლობა ალგორითმის ფარგლებში, უნდა შეეცადოს ჰქონდეს მრავალი განსხვავებული გენი.
არჩევანი
როდესაც პოპულაცია შეიქმნა, მისი წევრები ახლა უნდა შეფასდნენ ფიტნეს ფუნქციის მიხედვით. ფიტნესის ფუნქცია იღებს წევრის მახასიათებლებს და იძლევა რიცხვით წარმოდგენას, თუ რამდენად შეესაბამება წევრი. მათი შექმნა ხშირად შეიძლება ძალიან რთული იყოს. მნიშვნელოვანია იპოვოთ კარგი სისტემა, რომელიც ზუსტად ასახავს მონაცემებს. ეს ძალიან სპეციფიკურია პრობლემისთვის. ახლა აუცილებელია ყველა მონაწილის ვარგისიანობის გამოთვლა და რამდენიმე საუკეთესო წევრის შერჩევა.
მრავალი მიზნობრივი ფუნქცია
EAs ასევე შეიძლება გაფართოვდეს ამ სისტემების გამოსაყენებლად. ეს გარკვეულწილად ართულებს პროცესს, რადგან ერთი ოპტიმალური წერტილის იდენტიფიცირების ნაცვლად, მათი გამოყენებისას მიიღება ნაკრები. გადაწყვეტილებების ერთობლიობას ეწოდება პარეტოს საზღვარი და შეიცავს ელემენტებს, რომლებიც თანაბრად შესაფერისია იმ გაგებით, რომ არცერთი მათგანი არ დომინირებს სხვაზე.
გენეტიკური ოპერატორები
ეს ნაბიჯი მოიცავს ორ ქვესაფეხურს: კროსოვერი და მუტაცია. საუკეთესო ტერმინების შერჩევის შემდეგ (ჩვეულებრივ, ტოპ 2, მაგრამ ეს რიცხვი შეიძლება განსხვავდებოდეს), ისინი ახლა გამოიყენება ალგორითმში შემდეგი თაობის შესაქმნელად. არჩეული მშობლების მახასიათებლების გამოყენებით, იქმნება ახალი ბავშვები, რომლებიც თვისებების ნაზავია. ეს ხშირად შეიძლება რთული იყოს მონაცემთა ტიპებიდან გამომდინარე, მაგრამ ჩვეულებრივ კომბინატორულ პრობლემებშისავსებით შესაძლებელია სწორი კომბინაციების შერევა და გამოტანა.
ახლა აუცილებელია თაობაში ახალი გენეტიკური მასალის შემოტანა. თუ ეს მნიშვნელოვანი ნაბიჯი არ გადაიდგა, მეცნიერი ძალიან სწრაფად გაიჭედება ლოკალურ უკიდურესობებში და ვერ მიიღებს ოპტიმალურ შედეგებს. ეს ნაბიჯი არის მუტაცია და ის კეთდება საკმაოდ მარტივად, ცვლის ბავშვების მცირე ნაწილს ისე, რომ ისინი ძირითადად არ ასახავს მშობლების გენების ქვეჯგუფებს. მუტაცია, როგორც წესი, ხდება ალბათობით, ვინაიდან ალბათობა იმისა, რომ ბავშვი მიიღებს მას, ისევე როგორც მისი სიმძიმე, განისაზღვრება განაწილებით.
შეწყვეტა
საბოლოოდ, ალგორითმი უნდა დასრულდეს. ეს ჩვეულებრივ ხდება ორ შემთხვევაში: ან მიაღწია შესრულების მაქსიმალურ დროს, ან მიაღწია შესრულების ბარიერს. ამ ეტაპზე, საბოლოო გადაწყვეტა არჩეულია და ბრუნდება.
ევოლუციური ალგორითმების მაგალითი
ახლა, ამ პროცესის შედეგის საილუსტრაციოდ, თქვენ უნდა ნახოთ მრჩეველი მოქმედებაში. ამისათვის ჩვენ შეგვიძლია გავიხსენოთ, თუ როგორ ისწავლეს დინოზავრების რამდენიმე თაობამ სიარული (თანდათანობით მიწის დაუფლება), სხეულის სტრუქტურის ოპტიმიზაცია და კუნთების სიძლიერის გამოყენება. მიუხედავად იმისა, რომ ადრეული თაობის ქვეწარმავლებს არ შეეძლოთ სიარული, მრჩეველმა შეძლო მათი ევოლუცია დროთა განმავლობაში მუტაციისა და კროსვორდის მეშვეობით, რათა სიარული შეეძლო.
ეს ალგორითმები სულ უფრო აქტუალური ხდება თანამედროვე მსოფლიოში, რადგან მათზე დაფუძნებული გადაწყვეტილებები სულ უფრო ხშირად გამოიყენება ისეთ ინდუსტრიებში, როგორიცაა ციფრული მარკეტინგი, ფინანსები დაჯანდაცვა.
სად გამოიყენება EA?
უფრო ფართოდ, ევოლუციური ალგორითმები გამოიყენება მრავალფეროვან აპლიკაციებში, როგორიცაა გამოსახულების დამუშავება, მანქანის მარშრუტიზაცია, მობილური კომუნიკაციების ოპტიმიზაცია, პროგრამული უზრუნველყოფის შემუშავება და ხელოვნური ნერვული ქსელის ტრენინგიც კი. ეს ხელსაწყოები არის მრავალი აპლიკაციისა და ვებსაიტის გულში, რომელსაც ადამიანები ყოველდღიურად იყენებენ, მათ შორის Google Maps და თუნდაც თამაშები, როგორიცაა The Sims. გარდა ამისა, სამედიცინო სფერო იყენებს EA-ს, რათა დაეხმაროს კლინიკური გადაწყვეტილებების მიღებას კიბოს მკურნალობასთან დაკავშირებით. სინამდვილეში, ევოლუციური ალგორითმები იმდენად ძლიერია, რომ მათი გამოყენება შესაძლებელია თითქმის ნებისმიერი ოპტიმიზაციის პრობლემის გადასაჭრელად.
მურის კანონი
EO-ს მზარდი გავრცელება განპირობებულია ორი ძირითადი ფაქტორით: ხელმისაწვდომი გამოთვლითი სიმძლავრე და მონაცემთა დიდი ნაკრების დაგროვება. პირველი შეიძლება აღწერილი იყოს მურის კანონით, რომელიც არსებითად ამტკიცებს, რომ კომპიუტერში გამოთვლითი სიმძლავრის რაოდენობა ორმაგდება დაახლოებით ორ წელიწადში ერთხელ. ეს პროგნოზი ათწლეულების განმავლობაში არსებობდა. მეორე ფაქტორი დაკავშირებულია ტექნოლოგიებზე მზარდ დამოკიდებულებასთან, რაც საშუალებას აძლევს ინსტიტუტებს შეაგროვონ წარმოუდგენლად დიდი რაოდენობით მონაცემები, რაც მათ საშუალებას აძლევს გააანალიზონ ტენდენციები და გააუმჯობესონ პროდუქტები.
როგორ დაეხმარება ევოლუციური ალგორითმები მარკეტოლოგებს?
ბაზრის პირობები სწრაფად იცვლება და ძალიან კონკურენტუნარიანია. ამან აიძულა მარკეტინგის მენეჯერები გაეჯიბრებინათ უკეთესი გადაწყვეტილების მისაღებად. ხელმისაწვდომობის გაზრდაგამოთვლითი ძალამ აიძულა მუშები გამოიყენონ EA პრობლემის გადასაჭრელად.
კონვერტაციის ოპტიმიზაცია
ერთ-ერთი მთავარი მიზანი საიტის ვიზიტორების მაჩვენებლის გაზრდაა. ეს პრობლემა ემყარება მომხმარებელთა რაოდენობის ოპტიმიზაციას, რომლებიც აკეთებენ იმას, რაც მარკეტერს სურს. მაგალითად, თუ კომპანია ყიდის ლეპტოპებს, იდეალურია საიტის ვიზიტორების რაოდენობის გაზრდა, რომლებიც საბოლოოდ ყიდულობენ პროდუქტს. ეს არის კონვერტაციის კურსის ოპტიმიზაციის არსი.
ერთ-ერთი საოცრად მნიშვნელოვანი ასპექტია მომხმარებლის ინტერფეისის არჩევანი. თუ ვებ დიზაინი არ არის ძალიან მოსახერხებელი მომხმარებლისთვის, არიან ისეთებიც, რომლებიც საბოლოოდ არ ყიდულობენ პროდუქტს ამა თუ იმ მიზეზის გამო. მაშინ მიზანია შეამციროს მომხმარებელთა რიცხვი, რომლებიც საბოლოოდ არ ახდენენ კონვერტაციას, რაც ზრდის მთლიან მოგებას.
