د جنتیک الګورېتم
په کمپیوټر ساینس او د ریاضیکي عملیو په څېړنه کې، د جنتیک الګورېتم (GA) د طبیعي ټاکنې له بهیر څخه الهام شوی خورا نوښتګر الګورېتم دی چې د تکاملي الګورېتمونو (EA) لویو ډولونو پورې تړاو لري. د جنتیک الګورېتم، د اوښتون، تقاطع او ټاکنې په څېر د بیولوجیکي الهام اخېستل شویو الګورېتمونو پر بنسټ، په ټولیزه توګه، د غورهګرځونې او د مسایلو لټولو لپاره د خورا کیفیت لرونکو حللارو د موندلو لپاره کارول کېږي. د جنتیک الګورېتم د کارَونو ځینې بېلګې عبارت دي له: د لا ښې کارکړنې لپاره د تصمیمنیونې ونې غورهګرځونه، د سودوکو معماګانو حلول، هایپرپارامتري غورهګرځونه.[۱][۲]
مېتودولوجي[سمول]
د غورهګرځونې مسایل[سمول]
د جنتیک په یوه الګورېتم کې، د غورهګرځونې یوې مسألې لپاره د کاندیدو مناسبو حللارو یوه ټولنه (چې د وګړو، موجوداتو، اورګانیزمونو یا فېنوټایپونو په نامه یادېږي) د غورو حللارو په لور تکامل مومي. هره وړاندې شوې حل لاره یو لړ ځانګړنې لري (د نوموړې ټولنې کروموزومونه یا جېنوټایپونه) چې کېدای شي واوړي او بدلې شي؛ په دودیز ډول، حللارې د 0 او 1 لړیو په بڼه د باینري (عدد په قاعدې د 2) سیسټم په ډول وړاندې کېږي، خو کېدای شي د کوډ کولو له نورو طریقو څخه هم کار واخېستل شي. [۳]
تکامل له داسې یوې ټولنې څخه، چې اړوند غړي یې په تصادفي توګه رامنځته شوي وي، پیلېږي او دا یو له ریاضیکي پلوه یو تکراري بهیر دی، چې د هر تکرار د وګړو اړوندې ټولګې ته «نسل» ویل کېږي. په هر نسل کې، د ټولنې د هر غړي وړوالی ارزول کېږي؛ «وړوالی» د غورهګرځونې د حل کېدو په حال مسأله کې، په ټولیزه توګه، د عینیت (یا د لګښت) تابع قیمت دی. لا «وړ» وګړي په تصادفي توګه له شته ټولنې څخه ټاکل کېږي، او د یوه نوي نسل د رامنځته کولو په موخه، د هر وګړي جېنوم اصلاح کېږي (یا بیاترکیب او په احتمال سره، په تصادفي توګه اوړي). وروسته، د کاندیدو حللارو نوی نسل د الګورېتم په راتلونکي تکرار کې کارول کېږي. په ټولیزه توګه، الګورېتم هغه مهال پای ته رسېږي چې یا تر ټولو لوی شمېر نسلونه تولید شوي وي او یا د وګړو لپاره «وړوالی» د قناعت وړ کچې ته رسېدلې وي.
د جنتیک یوه معمولي الګورېتم لپاره اړینې برخې په لاندې ډول دي:
- د حللارې د ډومېن (برخې) یو جنتیکي انځور (ښودنه)؛
- د حللارې ډومېن د ارزولو په موخه، د «وړوالي» یوه تابع.
د هرې کاندید حل لارې یوه معیاري ښودنه د بیټونو یو لړوند دی (چې بیټي ټولګه یا بیټي لړۍ هم ورته ویل کېږي). د نورو ډولونو او جوړښتونو لړوندونه کېدای شي، په بنسټیزه توګه، په همدې توګه وکارول شي. په دغو جنتیکي ښودنو کې اسانتیا رامنځته کوونکې اصلي ځانګړنه دا ده چې، د هغو برخې، د ثابتو اندازو لهامله، په اسانۍ سره په یوې لیکې کې واقع کېدلای شي، او دا د ساده تقاطع په عملیو کې اسانتیا راولي. د متحول اوږدوالي ښودنې هم کارېدلای شي، خو د تقاطع الګورېتم پلي کېدنه په دغه حالت کې لا پېچلې ده. ونه-ډوله ښودنې د جنتیک په پروګراملیکنه او ګراف-ډوله ښودنې د تکامل په پروګراملیکنه کې څېړل کېږي؛ د دواړو خطي کروموزومونو او ونو یو ترکیب د جېن بیان په پروګراملیکنه کې راسپړل کېږي.[۳]
کله چې جنتیکي ښودنه (انځور) او د وړوالي تابع تعریف شوه، د جنتیک یو الګورېتم په لومړي سر کې د حللارې اړوند غړو ته لومړني قیمتونه ورکوي او وروسته د اوښتون، تقاطع، معکوس کوونکي او د ټاکنې عملکوونکو د تکراري کارونې لهلارې د هغو په غوره ګرځولو کې هڅه کوي.
د لومړنیو قیمتونو ورکولو پړاو[سمول]
د ټولنې اندازه د مسألې په ماهیت پورې تړاو لري، خو په معمول ډول، په سلګونو یا زرګونو بېلابېلې ممکنه حللارې لري. ډېري وخت، لومړنۍ ټولنه په تصادفي توګه رامنځته کېږي، د ممکنه حللارو د یوې بشپړې لړۍ رامنځته کېدنې امکان برابروي (د لټون فضا). کله ناکله، کېدای شي په هغو برخو کې، چې په ترڅ کې یې تر ټولو غوره حلونه په لوی احتمال سره د موندلو وړ دي، حللارې «وکرل شي».
د ټاکنې پړاو[سمول]
د هر وروستي نسل په اوږدو کې، د شته ټولنې یوه برخه د راتلونکي نسل د زېږولو لپاره ټاکل کېږي. ځانګړې حللارې د «وړوالي پر بنسټ» یوه بهیر لهلارې ټاکل کېږي، چېرې چې په ټولیزه توګه، د لا مناسبو حللارو (څرنګه چې د وړوالي تابع په واسطه اندازه کېږي) د ټاکنې احتمال لوړ دی. د ټاکنې ځیني ځانګړي مېتودونه هره حللاره ارزوي او په غوره توګه، تر ټولو ښې حللارې ټاکي. نور مېتودونه د ټولنې یوازې یوه تصادفي نمونه ارزوي، ځکه چې مخکېنی بهیر کېدای شي زیات وخت ونیسي.
د وړوالي تابع د جنتیکي ښودنې پر مخ تعریفېږي او د وړاندې شوې حللارې «کیفیت» اندازه کوي. د بېلګې په توګه: د «چانټې» په مسأله کې غواړو چې په ثابت ظرفیت لرونکې چانټه کې د ځای په ځای کېدونکو څیزونو مجموعي ارزښت تر ټولو لوړې کچې ته ورسوو. د یوې حللارې ښودنه کېدای شي د بیټونو یو لړوند وي، چېرې چې هر بیټ یو جلا څیز ښیي او د بیټ قیمت (0 یا 1) ښیي چې ایا څیز په چانټه کې دی او که نه. څرنګه چې د څیزونو اندازې کېدای شي د چانټې له ظرفیت څخه زیاتې شي، هر ډول ښودنه معتبره نهده. که چېرې ښودنه معتبره وي، د حللارې «وړوالی» د چانټې دننه د ټولو څیزونو د ارزښتونو مجموعه ده؛ او که نه، د وړوالي قیمت 0 دی.
په ځینو مسایلو کې، د وړوالي د بیان تعریف ګران یا ان ناشونی دی؛ په دغه حالتونو کې، د فېنوټایپ د وړوالي تابع د قیمت معلومولو لپاره کېدای شي یوه ورته انځورونه (سیمولېشن) وکارول شي (د بېلګې په توګه: د محاسباتي سیالونو ډینامیک د هغې نقلیه وسیلې د هوا مقاومت معلومولو لپاره کارول کېږي چې بڼه یې د یوه فېنوټایپ په توګه کوډ شوې ده)، یا ان کېدای شي د جنتیک له تعاملي الګورېتمونو څخه ګټه واخېستل شي.
جنتیکي عملکوونکي[سمول]
راتلونکی پړاو، د جنتیکي عملکوونکي: تقاطع (چې د بیاترکیب په نامه هم یادېږي) او اوښتون لهلارې، له ټاکل شویو حللارو څخه د ټولنې د دوهیم نسل تولیدول دي.
د هرې نوې رامنځته شوې حللارې لپاره، له مخکېنۍ ټاکل شوې ټولګې څخه، د نسلاخېستنې لپاره د «والدینو» د جوړې یوه حللاره غوره کېږي. د پورتنیو تقاطع او اوښتون مېتودونو په کارولو سره، د یوې «اولاد» حللارې د تولیدولو په واسطه، یوه نوې حللاره رامنځته شوې ده چې په ټولیزه توګه، چې ګڼشمېر ځانګړنې یې له «والدینو» (پخوانیو حللارو) سره یوشان دي. نوي والدین د هر نوي اولاد لپاره ټاکل کېږي او دا بهیر تر هغو دوام مومي چې د حللارو نوې رامنځته شوې ټولنه له مناسبې اندازې سره تولید شوې وي. که څه هم له دوو والدینو څخه د ګټېاخېستنې پر بنسټ د تکثر مېتودونه «له بیولوجي څخه الهام اخلي»، ځینې څېړنې ښیي چې له دوو زیات «والدین» لا کیفیت لرونکي کروموزومونه تولیدولای شي.[۴][۵]
په پای کې، د دغو بهیرونو په پایله کې د کروموزومونو راتلونکی نسل منځته راځي چې له لومړني سره توپیر لري. په ټولیزه توګه، د دغه بهیر لهلارې به د ټولنې لپاره د وړوالي منځنۍ کچه لوړه شي، ځکه چې د نسلاخېستنې لپاره له لومړي نسل څخه، د لږو مناسبو حل لارو له کوچني تناسب سره، یوازې تر ټولو غوره اورګانیزمونه ټاکل کېږي. د مناسبو حللارو دغه لږ شمېر د والدینو په جنتیکي ټولګه کې جنتیکي تنوع باوري کوي او لهدې امله د اولاد په راتلونکي نسل کې هم جنتیکي تنوع باوري کېږي.
دا چې د تقاطع الګورېتم ډېر اهمیت لري که د اوښتون، بېلابېلې نظریې شتون لري. په فوګل (۲۰۰۶ز) کې ګڼشمېر سرچینې ذکر شوې دي چې د اوښتون پر بنسټ لټون د اهمیت وړ ګڼي.
که څه هم تقاطع او اوښتون د جنتیک اصلي عملکوونکو په توګه پېژندل کېږي، خو امکان لري چې د جنتیک په الګورېتمونو کې د بیا ګروپ کولو، استعمار-انقراض یا د کډوالۍ په څېر عملکوونکي هم وکارول شي.
سرچينې[سمول]
- ↑ Gerges, Firas; Zouein, Germain; Azar, Danielle (2018-03-12). "Genetic Algorithms with Local Optima Handling to Solve Sudoku Puzzles". Proceedings of the 2018 International Conference on Computing and Artificial Intelligence. New York, NY, USA: Association for Computing Machinery: 19–22. doi:10.1145/3194452.3194463. S2CID 44152535. د کتاب نړيواله کره شمېره 978-1-4503-6419-5. الوسيط
|CitationClass=تم تجاهله (مساعدة) - ↑ Mitchell 1996، ص. 2.
- ↑ ۳٫۰ ۳٫۱ Whitley 1994، ص. 66.
- ↑ Eiben, A. E. et al (1994). "Genetic algorithms with multi-parent recombination". PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: 78–87. کينډۍ:ISBN.
- ↑ Ting, Chuan-Kang (2005). "On the Mean Convergence Time of Multi-parent Genetic Algorithms Without Selection". Advances in Artificial Life: 403–412. کينډۍ:ISBN.