Kontent qismiga oʻtish

Genetik algoritm

ZiyoSfera, erkin ensiklopediya

Genetik algoritm (genetic algorithm, GA) - informatika va operatsiyalarni tadqiq qilish sohalarida tabiiy tanlanish jarayoniga asoslangan, evolyutsion algoritmlar (EA) sinfiga mansub bo'lgan metaevristik qidiruv algoritmidir.

2006-yilda uchirilgan NASA ST5 kosmik kemasining antennasi. Ushbu murakkab shakl evolyutsion kompyuter dizayni dasturi tomonidan eng yaxshi nurlanish modelini yaratish uchun topilgan. Bu evolyutsiyalangan antenna sifatida tanilgan.

Genetik algoritmlar odatda optimizatsiya va qidiruv muammolari uchun yuqori sifatli yechimlarni topishda tanlash, krossover (rekkombinatsiya) va mutatsiya kabi biologik ilhomlantirilgan operatorlar yordamida qo'llaniladi.

Ushbu algoritmlar qaror qabul qilish daraxtlarini optimallashtirish, Sudoku jumboqlarini echish, giperparametr optimallashtirish va kaufal xulosalar chiqarish kabi keng ko'lamli sohalarda muvaffaqiyatli qo'llaniladi. Genetik algoritmlarning asosiy kuchi ularning murakkab, ko'p o'lchovli va tushunarli matematik modeli bo'lmagan qidiruv maydonlarida samarali ishlay olishidadir.

Evolyutsion jarayon odatda tasodifiy hosil qilingan shaxslar (yechimlar) populyatsiyasidan boshlanadi va iterativ (takrorlanuvchi) jarayon hisoblanadi. Har bir iteratsiya avlod (generation) deb ataladi. Har bir avlodda populyatsiyadagi har bir shaxsning "yaroqliligi" (fitness) baholanadi; bu qiymat odatda hal qilinayotgan optimallashtirish muammosidagi maqsad funksiyasining qiymatiga teng bo'ladi.

Metodologiya

Optimizatsiya muammolari

Genetik algoritmda optimallashtirish muammosiga nomzod yechimlar populyatsiyasi (shaxslar, jonzotlar yoki fenotiplar deb ataladi) yaxshiroq yechimlar sari rivojlanadi. Har bir nomzod yechim o'z xususiyatlari to'plamiga (uning xromosomalari yoki genotipi) ega bo'lib, ular mutatsiyaga uchrashi va o'zgarishi mumkin. An'anaviy ravishda yechimlar 0 va 1 lardan iborat ikkilik (binary) qatorlar shaklida ifodalanadi, ammo boshqa kodlash usullari ham mavjud.

Standart genetik algoritm quyidagilarni talab qiladi:

  1. Yechimlar sohasining genetik ifodasi (genetic representation);
  2. Yechimlar sohasini baholash uchun fitness funksiyasi (fitness function).

Jarayon bosqichlari

1. Initsializatsiya (Ishga tushirish)

Populyatsiya hajmi muammoning tabiatiga bog'liq, ammo odatda yuzlab yoki minglab mumkin bo'lgan yechimlarni o'z ichiga oladi. Ko'pincha boshlang'ich populyatsiya butun qidiruv maydonini qamrab olishi uchun tasodifiy tarzda shakllantiriladi. Ba'zan yechimlar optimal natija topilishi ehtimoli yuqori bo'lgan sohalarga "ekilishi" (seeding) mumkin.

2. Tanlash (Selection)

Har bir keyingi avlod davomida mavjud populyatsiyaning bir qismi yangi avlodni yaratish uchun tanlab olinadi. Shaxsiy yechimlar fitnessga asoslangan jarayon orqali tanlanadi, bunda yaroqlilik darajasi yuqori bo'lgan yechimlar tanlanish ehtimoli ko'proq bo'ladi. Fitness funksiyasi genetik ifoda ustida aniqlanadi va taqdim etilgan yechimning "sifatini" o'lchaydi.

Masalan, Xalta muammosida (knapsack problem) ma'lum sig'imga ega xaltaga joylashtirilishi mumkin bo'lgan buyumlarning umumiy qiymatini maksimallashtirish kerak. Yechimning fitness qiymati xaltadagi barcha buyumlar qiymatining yig'indisiga teng bo'ladi (agar umumiy og'irlik limitdan oshmasa).

3. Genetik operatorlar

Keyingi qadam tanlangan yechimlardan genetik operatorlar: krossover (rekkombinatsiya) va mutatsiya yordamida ikkinchi avlod populyatsiyasini yaratishdir.

  • Krossover: Ikki "ota-ona" yechimning xususiyatlarini birlashtirib, yangi "farzand" yechim yaratish jarayoni. Bu yangi yechim o'z ota-onalarining ko'plab xususiyatlarini meros qilib oladi.
  • Mutatsiya: Genetik xilma-xillikni saqlab qolish va algoritmning lokal optimumga (mahalliy eng yaxshi nuqtaga) tushib qolishining oldini olish uchun yechimning ayrim qismlarini tasodifiy o'zgartirish jarayoni.

4. Yakunlash (Termination)

Ushbu avlodlar almashinuvi jarayoni yakunlash sharti bajarilgunga qadar takrorlanadi. Umumiy yakunlash shartlari:

  • Minimal mezonlarga javob beradigan yechim topilishi;
  • Belgilangan avlodlar soniga yetib borilishi;
  • Ajratilgan vaqt yoki hisoblash resurslarining tugashi;
  • Eng yaxshi yechimning fitness darajasi platoga (turg'unlikka) yetishi, ya'ni keyingi iteratsiyalar yaxshiroq natija bermay qo'yishi.

Qurilish bloklari gipotezasi

Genetik algoritmlarni amalga oshirish oson, ammo ularning xatti-harakatlarini tushunish murakkab. Qurilish bloklari gipotezasi (building block hypothesis, BBH) algoritmlarning nima uchun muvaffaqiyatli ekanligini tushuntirishga harakat qiladi. David E. Goldbergning fikricha, algoritm "qurilish bloklari" deb ataluvchi qisqa, past tartibli va yuqori fitnessli sxemalarni aniqlash va ularni qayta birlashtirish orqali moslashishni amalga oshiradi.

Huddi bola oddiy yog'och bloklardan muhtasham qal'alar qurgani kabi, genetik algoritm ham qisqa va samarali qismlarni birlashtirish orqali optimal yechimga yaqinlashadi.

Cheklovlar

Genetik algoritmlarning amaliy qo'llanilishida bir qator cheklovlar mavjud:

  • Hisoblash resurslari: Murakkab muammolar uchun fitness funksiyasini qayta-qayta baholash juda ko'p vaqt talab qilishi mumkin. Ba'zan bitta simulyatsiya soatlab yoki kunlab davom etadi.
  • Masshtablashuv: Elementlar soni ko'paygan sari qidiruv maydoni eksponentsial ravishda kengayib boradi (murakkablik muammosi).
  • Lokal optimum: Algoritmlar ko'pincha global yechim o'rniga lokal optimumga (yaqin atrofdagi yaxshi nuqtaga) yaqinlashib, o'sha yerda "tiqilib" qolishga moyil bo'ladi.
  • Dinamik ma'lumotlar: Ma'lumotlar to'plami o'zgaruvchan bo'lsa, algoritm eski ma'lumotlarga moslashib qolishi mumkin.

Variantlar va turlari

Xromosoma ifodalanishi

Eng oddiy algoritm har bir xromosomani bitlar qatori (0 va 1) sifatida ifodalaydi. Ammo zamonaviy variantlarda xromosomalar quyidagicha bo'lishi mumkin:

  • Haqiqiy sonlar massivlari (real-valued representation);
  • Buyruqlar jadvaliga indekslar ro'yxati;
  • Bog'langan ro'yxatlar (linked lists) yoki ob'ektlar.

Ikkilik kodlashda ko'pincha Grey kodi (Gray coding) qo'llaniladi. Bu sonning kichik o'zgarishi xromosomada ham kichik o'zgarishga olib kelishini ta'minlaydi.

Elitizm (Elitism)

Yangi avlodni yaratishda joriy avlodning eng yaxshi vakillarini (yoki vakilini) o'zgartirishsiz keyingi avlodga o'tkazish strategiyasi. Bu yechim sifatining avloddan-avlodga yomonlashmasligini kafolatlaydi.

Adaptiv genetik algoritmlar (AGA)

Ushbu variantda krossover (pc) va mutatsiya (pm) ehtimollari o'zgarmas emas, balki populyatsiyaning holatiga qarab avtomatik ravishda moslashtiriladi. Agar populyatsiya xilma-xilligi kamaysa, mutatsiya darajasi oshiriladi.

Qo'llanilish sohalari

Genetik algoritmlar ayniqsa quyidagi sohalarda samarali:

  • Jadvallarni tuzish: Dars jadvallari, navbatchilik grafiklari va ishlab chiqarish rejalari.
  • Muhandislik dizayni: Aerodinamik shakllarni optimallashtirish, ko'priklar dizayni.
  • Kosmik texnologiyalar: NASA antennalari va kosmik apparatlar trayektoriyasini hisoblash.
  • Iqtisodiyot: Portfelni optimallashtirish va savdo strategiyalarini ishlab chiqish.
  • O'yinlar va robototexnika: Kompyuter personajlarining yurish usullarini va harakat logikasini o'rgatish.

Tarix

Genetik algoritmlarning rivojlanish tarixi bir necha muhim bosqichlarni bosib o'tgan:

  • 1950-yil: Alan Turing evolyutsiya tamoyillariga asoslangan "o'rganuvchi mashina" g'oyasini taklif qildi.
  • 1954-yil: Nils Aall Barricelli Prinstonda birinchi evolyutsion simulyatsiyalarni o'tkazdi.
  • 1960-yillar: Ingo Rechenberg va Hans-Paul Schwefel evolyutsion strategiyalar yordamida murakkab muhandislik muammolarini hal qilishdi.
  • 1975-yil: John Henry Holland o'zining "Adaptation in Natural and Artificial Systems" kitobini nashr etdi va genetik algoritmlarning nazariy asoslarini shakllantirdi.
  • 1980-yillar oxiri: General Electric dunyodagi birinchi sanoat genetik algoritm mahsulotini sotuvga chiqardi.

O'xshash texnikalar

Genetik algoritmlar quyidagi kengroq sohalarning bir qismidir:

Yana qarang

Manbalar

Qo'shimcha adabiyotlar

  • Goldberg, David (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Professional. ISBN 978-0201157673.
  • Mitchell, Melanie (1996). An Introduction to Genetic Algorithms. MIT Press. ISBN 9780585030944.
  • Holland, John (1992). Adaptation in Natural and Artificial Systems. MIT Press. ISBN 978-0262581110.

Tashqi havolalar

"https://ziyosfera.uz/index.php?title=Genetik_algoritm&oldid=448146" dan olindi