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

ისტორია

გენეტიკური ალგორითმების გამოგონების მიზანი იყო, რომ მოეხდინათ გარკვეული ბუნებრივი ევოლუციის პროცესების იმიტირება. ბევრი მეცნიერი, მათ შორის ბიოლოგები, არიან გაოცებულნი, რადგან ცხოვრების დონის სირთულე რომლის წინაშეც ვდგევართ, შეიძლება განვითარდეს შემოთავაზებული ნამარხი ნაშთების ჩანაწერებით. გენეტიკური ალგორითმების იდეაა, რომ გამოიყენოს ევოლუციის ეს ძალა ოპტიმიზაციის ამოცანების ამოსახსნელად. გენეტიკური ალგორითმების შემქმნელად, მამად, ითვლება ჯონ ოლანდი (John Holland), რომელმაც გამოიგონა ის 1970-იანი წლების დასაწყისში.

რა არის გენეტიკური ალგორითმები (GA) ?

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

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

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

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

გენეტიკური ალგორთმების მიმოხილვა.

გენეტიკური ალგორითმი აკეთებს ბუნებრივი გადარჩევის სიმულაციას ინდივიდების პრობლების გადასაჭრელად შემდეგი თაობისთვის, რომელიც ალგორითმში წარმოადგენს ცვლადს. თითოეული თაობა (ცვლადი) შედგება character string-ის პოპულაციისაგან, რომელიც არის ქრომოსომის ანალოგი, რასაც ჩვენ ვხედავთ დნმ-ში. თითოეული ინდივიდი წარმოადგენს წერტილს ძებნის სივრცეში და მის შესაძლო ამოხსნას.

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

ესენია:

  1. ინდივიდები პოპულაციაში კონკურენციას უწევენ ერთმანეთს რესურსისა და თანამოაზრეებისათვის.
  2. ის ინდივიდები, რომლებიც ყველაზე წარმატებული იქნებიან თითოეულ „შეჯიბრში“ აწარმოებენ უფრო მეტ პირმშოს, იმათთან შედარებით ვინც „დამარცხდნენ“.
  3. „კარგი“ ინდივიდებისაგან წარმოქმნილი გენი გავრცელდება მთელ პოპულაციაში. ასე რომ, ორი „კარგი“ მშობელი ზოგჯერ წარმოქმნის პირმშოს, რომელიც იქნება უკეთესი ვიდრე მისი მშობლები სათითაოდ.
  4. ამგვარად თითოეული მომდევნო თაობა იქნება უფრო შეთვისებული გარემოსთან, ვიდრე წინა.

ძებნის სივრცე

ინდივიდების პოპულაცია შენარჩუნებულია ძებნის სივრცეში გენეტიკური ალგორითმებისთვის, რომელთაგან თითოეული წარმოადგენს მოცემული ამოცანის შესაძლო ამოხსნას. თითოეული ინდივიდი კოდირებულია როგორც სასრული სიგრძის კომპონენტების ვექტორი, რაღაც ალფავიტის ფარგლებში, მაგრამ როგორც წესი გამოიყენება ბინარული (ორობითი) ალფავიტი, რომლის ასონიშნებია 0 და 1. რომ გავაკეთოთ ანალოგია, ინდივიდები მიმსგავსებულია ქრომოსომებთან და ცვლადები არის გენის ანალოგი. თავსებადობის (fitness) კოეფიციენტი/ქულა გვიჩვენებს ამოხსნას, ანუ ინდივიდის შესაძლებლობებს შეჯიბრში. ამგვარად, საძიებელია ინდივიდი ოპტიმალური (ან ოპტიმალურთან მიახლოებული) თავსებადობის კოეფიციენტით. გენეტიკური ალგორითმების მიზანია გამოიყენოს გადარჩევით „გამრავლება“ ამონახსნისა და ქრომოსომიდან მიღებულ ინფორმაციასთან კომბინაციით აწარმოოს უკეთესი „შთამომავლობა“ ვიდრე მშობელია. ანუ ყველა მშობლის მიზანია, რომ მისი შთამომავალი იყოს უკეთესი, ვიდრე თვითონ („ის ურჩევნია მამულსა, რომ შვილი სჯობდეს მამასა“).

a

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

ამონახსნების ახალი თაობები მიღებულია ისე, რომ ისინი შეიცავენ საშუალოდ უფრო მეტ კარგ გენს (კარგ თვისებებს), ვიდრე ტიპიური ამონახსნები წინა პოპულაციაში. თითოეული წარმატებული თაობა შეიცავს უფრო კარგ „ნაწილობრივ ამონახსნს“ ვიდრე წინა თაობა. საბოლოოდ შეიძლება ითქვას, რომ როცა მომდევნო თაობა საგრძნობლად/შესამჩნევად არ განსხვავდება წინა თაობისგან, ამ დროს უკვე ალგორითმმა უკვე დაასრულა მუშაობა და მიღებულია ის ოპტიმალური (ოპტიმალურთან მიღებული) ამონახსნი (თაობა), რომელიც წარმოადგენს ამოცანის ამონახსნს.

დანერგვის დეტალები

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

  1. selection – რომელიც ტოლფასია ბუნებრივი გადარჩევის ( ანუ გადარჩევის გზით უკეთესის გამარჯვების).
  2. crossover – რომელიც წარმოადგენს ინდივიდების შეჯვარებას.
  3. mutation – რომელიც წარმოადგენს შემთხვევით ცვლილებებს.

განვიხილოთ ოპერაციები:

Selection:

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

Crossover:

  • ძირითადი გამორჩეული ფაქტორი გენეტიკური ალგორითმებისა სხვა სხვა ოპტიმიზაციის ტექნიკებისგან.
  • ორი ინდივიდი აირჩევა პოპულაციიდან selection-ის მეთოდით.
  • ე.წ. გაწყვეტის წერტილი crossover-თვის უნდა აირჩეს შემთხვევითად.
  • ორი ინდივიდის მნიშვნელობები იცვლება გაწყვეტის წერტილის მიხედვით.
  • თუ S1 ინდივიდი არის 000000 და S2 ინდივიდი არის 11111111 და გაწყვეტის წერტილი არის 2 მაშინ S1’=11000000 და S2’=00111111
  • ორი ახალი ინდივიდი, რომელიც მივიღეთ წინა თაობის შეჯვარებით ჯდება უკვე ახალი თაობის პოპულაციაში
  • „კარგი“ ინდივიდების ნაწილების რეკომბინირებით, ეს პროცესი მიზნად ისახავს უკეთესი ინდივიდების შექმნას.

b

Mutation:

  • მცირე ალბათობით, ახალი ინდივიდების ნაწილი ბიტებისა უბრალოდ გადანაცვლდება.
  • მისი მიზანია შეინარჩუნოს მრავალფეროვნება პოპულაციის ფარგლებში და შეაჩეროს ნაადრევი დაახლოება.
  • მუტაცია მარტო იწვევს შემთხვევით გავლას ძებნის სივრცეში.
  • მუტაცია და სელექცია (crossover-ის გარეშე) ქმნის პარალელურ, ხმაურით-ტოლერანტულ (noise-tolerant), მთაზე ასვლის (hill-climbing) ალგორითმს.

c

ალგორითმის ფსევდოკოდი:

  1. შემთხვევითად მოვახდინოთ t პოპულაციის ინიციალიზაცია.
  2. განვსაზღვროთ პოპულაციის შეგუებადობის კოეფიციენტი.
  3. გავიმეოროთ:
    • შევარჩიოთ მშობლები t პოპულაციიდან
    • ჩავატაროთ crossover მშობელზე და მივიღოთ t+1 პოპულაცია
    • ჩავატაროთ t+1 პოპულაციის მუტაცია
    • განვსაზღვროთ t+1 პოპულაციისთვის შეგუებადობის კოეფიციენტი
  4. ეს ოპერაციები ჩავატაროთ მანამ, სანამ კარგი შთამომავლობები არიან შესამჩნევად უკეთესები წინაპრებზე.

Leave a Reply / უპასუხე

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / შეცვლა )

Twitter picture

You are commenting using your Twitter account. Log Out / შეცვლა )

Facebook photo

You are commenting using your Facebook account. Log Out / შეცვლა )

Google+ photo

You are commenting using your Google+ account. Log Out / შეცვლა )

Connecting to %s