გენეტიკური ალგორითმები

ეს ნოუთბუქი AI დამწყებთათვის სასწავლო პროგრამა-ის ნაწილია.

ზოგიერთი თეორია

გენეტიკური ალგორითმები (GA) ეფუძნება ევოლუციური მიდგომას AI-ს მიმართ, რომელშიც გამოყენებულია მოსახლეობის ევოლუციის მეთოდები მოცემული პრობლემის ოპტიმალური გადაწყვეტის მისაღებად. ისინი შემოგვთავაზეს 1975 წელს ჯონ ჰენრი ჰოლანდი-ის მიერ.

გენეტიკური ალგორითმები ეფუძნება შემდეგ იდეებს:

• პრობლემის სწორი გადაწყვეტილებები შეიძლება წარმოდგენილი იყოს როგორც გენები
• Crossover საშუალებას გვაძლევს გავაერთიანოთ ორი გამოსავალი, რათა მივიღოთ ახალი მოქმედი გადაწყვეტა
• Selection გამოიყენება უფრო ოპტიმალური გადაწყვეტილებების შესარჩევად ზოგიერთი ფიტნეს ფუნქციის გამოყენებით
• მუტაციები დანერგილია ოპტიმიზაციის დესტაბილიზაციისა და ლოკალური მინიმალურიდან გამოსაყვანად

თუ გსურთ გენეტიკური ალგორითმის დანერგვა, დაგჭირდებათ შემდეგი:

• ვიპოვოთ ჩვენი პრობლემის გადაწყვეტის კოდირების მეთოდი გენების $g\in\Gamma$-ის გამოყენებით
• $\Gamma$ გენების ნაკრებზე უნდა განვსაზღვროთ fitness ფუნქცია $\mathrm{fit}: \Gamma\to\mathbb{R}$. ფუნქციის უფრო მცირე მნიშვნელობები შეესაბამება უკეთეს გადაწყვეტილებებს.
• განვსაზღვროთ ჯვარედინი მექანიზმი, რომ დააკავშიროთ ორი გენი ერთად ახალი მოქმედი გადაწყვეტის მისაღებად $\mathrm{crossover}: \Gamma^2\to\Gamma$.
• მუტაციის მექანიზმის განსაზღვრა $\mathrm{mutate}: \Gamma\to\Gamma$. ხშირ შემთხვევაში, კროსოვერი და მუტაცია საკმაოდ მარტივი ალგორითმებია გენების მანიპულირებისთვის, როგორც რიცხვითი თანმიმდევრობების ან ბიტების ვექტორების სახით.

გენეტიკური ალგორითმის სპეციფიკური განხორციელება შეიძლება განსხვავდებოდეს შემთხვევიდან კონკრეტულ შემთხვევაში, მაგრამ საერთო სტრუქტურა შემდეგია:

1. აირჩიეთ საწყისი პოპულაცია $G\subset\Gamma$
2. შემთხვევით აირჩიეთ ერთ-ერთი ოპერაცია, რომელიც შესრულდება ამ ეტაპზე: კროსოვერი ან მუტაცია
3. კროსოვერი:

• შემთხვევით აირჩიეთ ორი გენი $g_1, g_2 \G$-ში
• გამოთვალეთ კროსოვერი $g=\mathrm{კროსოვერი}(g_1,g_2)$
• თუ $\mathrm{fit}(g)<\mathrm{fit}(g_1)$ ან $\mathrm{fit}(g)<\mathrm{fit}(g_2)$ - შეცვალეთ შესაბამისი გენი პოპულაციაში $g$-ით.

1. მუტაცია - აირჩიეთ შემთხვევითი გენი $g\G$-ში და შეცვალეთ იგი $\mathrm{mutate}(g)$-ით
2. გაიმეორეთ მე-2 საფეხურიდან, სანამ არ მივიღებთ საკმარისად მცირე მნიშვნელობას $\mathrm{fit}$, ან სანამ არ მიიღწევა ნაბიჯების რაოდენობის ლიმიტი.

ამოცანები, როგორც წესი, წყვეტს GA:

1. განრიგის ოპტიმიზაცია
2. ოპტიმალური შეფუთვა
3. ოპტიმალური ჭრა
4. ამომწურავი ძიების დაჩქარება

პრობლემა 1: სამართლიანი განძის გაყოფა

ამოცანა: ორმა ადამიანმა იპოვა საგანძური, რომელიც შეიცავს სხვადასხვა ზომის (და, შესაბამისად, განსხვავებული ფასის) ბრილიანტებს. მათ უნდა გაანაწილონ საგანძური ორ ნაწილად ისე, რომ ფასში სხვაობა იყოს 0 (ან მინიმალური).

ფორმალური განმარტება: ჩვენ გვაქვს რიცხვების ნაკრები $S$. ჩვენ უნდა გავყოთ ის ორ ქვეჯგუფად $S_1$ და $S_2$, ისე, რომ $$\left|\sum_{i\in S_1}i - \sum_{j\in S_2}j\right|\to\min$$ და $S_1\cup S_2=S$, $S_1\cap S_2=\emptyset$.

პირველ რიგში, მოდით განვსაზღვროთ ნაკრები $S$:

მოდით დავაშიფროთ პრობლემის ყოველი შესაძლო გადაწყვეტა ორობითი ვექტორით $B\in{0,1}^N$, სადაც რიცხვი $i$-th პოზიციაზე გვიჩვენებს, რომელ კომპლექტს ($S_1$ ან $S_2$) ეკუთვნის $i$-th რიცხვი თავდაპირველ კომპლექტში $S$. generate ფუნქცია გამოიმუშავებს იმ შემთხვევით ორობით ვექტორებს.

მოდით განვსაზღვროთ fit ფუნქცია, რომელიც ითვლის გადაწყვეტის "ფასს". ეს იქნება სხვაობა ჯამს ან ორ კომპლექტს შორის, $S_1$ და $S_2$:

ახლა ჩვენ უნდა განვსაზღვროთ ფუნქციები მუტაციისა და გადაკვეთისთვის:

• მუტაციისთვის ჩვენ ავირჩევთ ერთ შემთხვევით ბიტს და უარვყოფთ მას (0-დან 1-მდე შეცვლა და პირიქით)
• კროსოვერისთვის, ჩვენ ავიღებთ რამდენიმე ბიტს ერთი ვექტორიდან, ხოლო ზოგ ბიტს მეორე ვექტორიდან. ჩვენ გამოვიყენებთ იგივე generate ფუნქციას, რათა შემთხვევით ავირჩიოთ, რომელი ბიტი ავიღოთ შეყვანის ნიღბებიდან.

მოდით შევქმნათ გადაწყვეტილებების საწყისი პოპულაცია $P$ ზომის pop_size:

ახლა მთავარი ფუნქციაა ევოლუციის შესრულება. n არის ევოლუციის საფეხურების რაოდენობა, რომელიც უნდა გაიარო. ყოველ ნაბიჯზე:

• 30%-იანი ალბათობით ვასრულებთ მუტაციას და ელემენტს ყველაზე ცუდი fit ფუნქციით ვანაცვლებთ მუტაციური ელემენტით
• 70%-იანი ალბათობით ვასრულებთ კროსოვერს

ფუნქცია აბრუნებს საუკეთესო გამოსავალს (გენი, რომელიც შეესაბამება საუკეთესო ხსნარს) და პოპულაციაში მინიმალური მორგების ფუნქციის ისტორიას თითოეულ გამეორებაზე.

თქვენ ხედავთ, რომ ჩვენ მოვახერხეთ fit ფუნქციის საკმაოდ მინიმიზაცია! აქ არის გრაფიკი, რომელიც გვიჩვენებს, თუ როგორ იქცევა fit ფუნქცია მთელი პოპულაციისთვის პროცესის განმავლობაში.

პრობლემა 2: N Queens პრობლემა

ამოცანა: თქვენ უნდა მოათავსოთ $N$-ის დედოფალები $N\ჯერ N$ ზომის ჭადრაკის დაფაზე ისე, რომ ისინი ერთმანეთს არ შეუტიონ.

უპირველეს ყოვლისა, მოვაგვაროთ პრობლემა გენეტიკური ალგორითმების გარეშე, სრული ძიების გამოყენებით. ჩვენ შეგვიძლია წარმოვადგინოთ დაფის მდგომარეობა $L$ სიით, სადაც $i$-th რიცხვი სიაში არის დედოფლის ჰორიზონტალური პოზიცია $i$-ე მწკრივში. სავსებით აშკარაა, რომ თითოეულ ხსნარს ექნება მხოლოდ ერთი დედოფალი რიგზე და თითოეულ მწკრივს ექნება დედოფალი.

ჩვენი მიზანი იქნება პრობლემის პირველი გამოსავლის პოვნა, რის შემდეგაც შევწყვეტთ ძიებას. თქვენ შეგიძლიათ მარტივად გააფართოვოთ ეს ფუნქცია დედოფლებისთვის ყველა შესაძლო პოზიციის შესაქმნელად.

ახლა მოდით გავზომოთ რამდენი ხანი სჭირდება 20 დედოფლის პრობლემის გადაწყვეტას:

ახლა მოდით გადავჭრათ იგივე პრობლემა გენეტიკური ალგორითმის გამოყენებით. ეს გამოსავალი შთაგონებულია ეს ბლოგის პოსტი-ით.

ჩვენ წარმოვადგენთ თითოეულ ამოხსნას $N$ სიგრძის ერთი და იგივე სიით და fit ფუნქციის სახით ავიღებთ დედოფლების რაოდენობას, რომლებიც თავს ესხმიან ერთმანეთს:

ვინაიდან ფიტნესის ფუნქციის გამოთვლა შრომატევადია, მოდით შევინახოთ თითოეული გამოსავალი პოპულაციაში ფიტნეს ფუნქციის მნიშვნელობასთან ერთად. მოდით შევქმნათ საწყისი პოპულაცია:

ახლა ჩვენ უნდა განვსაზღვროთ მუტაციის და გადაკვეთის ფუნქციები. კროსვორდი აერთიანებს ორ გენს, არღვევს მათ რაღაც შემთხვევით წერტილში და აერთიანებს სხვადასხვა გენის ორ ნაწილს.

ჩვენ გავაძლიერებთ გენის შერჩევის პროცესს მეტი გენის შერჩევით უკეთესი ფიტნეს ფუნქციით. გენის შერჩევის ალბათობა დამოკიდებული იქნება ფიტნეს ფუნქციაზე:

ახლა განვსაზღვროთ მთავარი ევოლუციური მარყუჟი. ჩვენ ლოგიკას ოდნავ განსხვავებულად გავაკეთებთ წინა მაგალითისგან, რათა დავანახოთ, რომ შეიძლება შემოქმედებითი იყოს. ჩვენ გავაციკლებთ მანამ, სანამ არ მივიღებთ სრულყოფილ გადაწყვეტას (ფიტნეს ფუნქცია=0) და ყოველ ნაბიჯზე ვიღებთ მიმდინარე თაობას და ვაწარმოებთ იმავე ზომის ახალ თაობას. ეს კეთდება nxgeneration ფუნქციის გამოყენებით, შემდეგი ნაბიჯების გამოყენებით:

1. გააუქმეთ ყველაზე უვარგისი გადაწყვეტილებები - არის discard_unfit ფუნქცია, რომელიც ამას აკეთებს
2. დაამატეთ კიდევ რამდენიმე შემთხვევითი გადაწყვეტა თაობას
3. შეავსეთ ახალი თაობის gen_size ზომის ახალი თაობა თითოეული ახალი გენისთვის შემდეგი ნაბიჯების გამოყენებით:
   • აირჩიეთ ორი შემთხვევითი გენი, ფიტნეს ფუნქციის პროპორციული ალბათობით
   • გამოთვალეთ კროსვორდი
   • გამოიყენეთ მუტაცია mutation_prob ალბათობით

საინტერესოა, რომ უმეტეს შემთხვევაში ჩვენ საკმაოდ სწრაფად ვახერხებთ გამოსავლის მიღებას, მაგრამ იშვიათ შემთხვევებში ოპტიმიზაცია აღწევს ადგილობრივ მინიმუმს და პროცესი დიდხანს ჩერდება. მნიშვნელოვანია ამის გათვალისწინება საშუალო დროის გაზომვისას: მიუხედავად იმისა, რომ უმეტეს შემთხვევაში გენეტიკური ალგორითმი უფრო სწრაფი იქნება, ვიდრე სრული ძებნა, ზოგიერთ შემთხვევაში ამას შეიძლება მეტი დრო დასჭირდეს. ამ პრობლემის დასაძლევად ხშირად აზრი აქვს განსახილველი თაობების რაოდენობის შეზღუდვას და თუ გამოსავალი ვერ ვიპოვეთ, შეგვიძლია დავიწყოთ ნულიდან.