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

სალექციო ვიქტორინა

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

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

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

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

• ვიპოვოთ ჩვენი პრობლემის გადაწყვეტის კოდირების მეთოდი გენების g∈Γ
• გენების ნაკრებზე &გამა; ჩვენ უნდა განვსაზღვროთ ფიტნესის ფუნქცია fit: Γ→R. ფუნქციის მცირე მნიშვნელობები შეესაბამება უკეთეს გადაწყვეტილებებს.
• განვსაზღვროთ ჯვარედინი მექანიზმი, რომ დააკავშიროთ ორი გენი ერთად ახალი მოქმედი გადაწყვეტის კროსოვერის მისაღებად: Γ2→Γ.
• მუტაციის მექანიზმის მუტაციის დასადგენად: &გამა;→&გამა;.

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

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

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

• შემთხვევით აირჩიეთ ორი გენი g1, g2 ∈ გ
• გამოთვალეთ კროსოვერი g=კროსოვერი(g1,g2)
• თუ fit(g)<fit(g1) ან fit(g)<fit(g2) - შეცვალეთ შესაბამისი გენი პოპულაციაში გ-ით.

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

ტიპიური ამოცანები

როგორც წესი, გენეტიკური ალგორითმებით გადაწყვეტილი ამოცანები მოიცავს:

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

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

განაგრძეთ სწავლა შემდეგ რვეულებში:

გადადით ეს ნოუთბუქი-ზე გენეტიკური ალგორითმების გამოყენების ორი მაგალითის სანახავად:

1. განძის სამართლიანი დაყოფა
2. 8 დედოფლის პრობლემა

დასკვნა

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

გამოწვევა

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

ლექციის შემდგომი ვიქტორინა

მიმოხილვა და თვითშესწავლა

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