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

ავტორი: სოფიკო გოგალაძე
საკვანძო სიტყვები: ზურგჩანთის ამოცანა, გენეტიკური ალგორითმები
ანოტაცია:

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