ساعدنیوز
ساعدنیوز

الگوریتم ژنتیک و کاربردهای آن

  یکشنبه، 21 آذر 1400   زمان مطالعه 8 دقیقه
الگوریتم ژنتیک و کاربردهای آن
الگوریتم ژنتیک-(Genetic Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی مانند وراثت و جهش استفاده می‌کند.

الگوریتم های ژنتیک (به انگلیسی: Genetic algorithm) تکنیک جستجو در علم رایانه برای یافتن راه حل تقریبی برای بهینه سازی مدل، ریاضی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم های تکاملی است که از تکنیک های زیست شناسی فرگشتی مانند وراثت، جهش زیست شناسی و اصول انتخابی داروین برای یافتن فرمول بهینه جهت پیش بینی یا تطبیق الگو استفاده می شود. الگوریتم های ژنتیک اغلب گزینه خوبی برای تکنیک های پیش بینی بر مبنای رگرسیون هستند. در مدل سازی الگوریتم ژنتیک یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می کند. مسئله ای که باید حل شود دارای ورودی هایی می باشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راه حل ها تبدیل می شود سپس راه حل ها به عنوان کاندیداها توسط تابع برازش یا تابع برازندگی (Fitness Function) مورد ارزیابی قرار می گیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه می یابد. به طور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخش های آن به صورت فرایندهای تصادفی انتخاب می شوند که این الگوریتم ها از بخش های تابع برازش، نمایش، انتخاب و تغییر تشکیل می شوند.

الگوریتم‌های ژنتیک

مفهوم الگوریتم ژنتیک

الگوریتم ژنتیک (GA)، یک الگوریتم جستجوی ابتکاری انطباق پذیر است که بر مبنای ایده های تکاملی انتخاب طبیعی و ژنتیک طراحی شده است. به این ترتیب این الگوریتم نمایانگر استفاده ی هوشمند از یک الگوریتم جستجوی تصادفی برای حل مسائل بهینه سازی می باشد. اگرچه الگوریتم های ژنتیک از پدیده هایی تصادفی استفاده می کنند اما خودشان به هیچ وجه تصادفی نیستند بلکه، آن ها از اطلاعات تاریخی موجود برای هدایت عملیات جستجو به منطقه ای با عملکرد بهتر در فضای جستجو استفاده می کنند. روش های اصلی الگوریتم ژنتیک به گونه ای طراحی شده اند تا بتوانند فرآیند های ضروری برای تکامل در سیستم های طبیعی را شبیه سازی کنند. از جمله مهمترین این فرآیند ها، آن هایی هستند که از قوانینی که اولین بار توسط چارلز داروین و با نام “بقای اصلح”(Survival Of The Fittest) مطرح شد، پیروی می کنند. علت این امر آن است که در طبیعت، رقابت میان موجودات زنده برای دستیابی به منابع کمیاب منجر به غلبه اصلح ترین موجودات بر موجودات ضعیف تر می شود.

چرا الگوریتم ژنتیک؟

الگوریتم ژنتیک به دلیل قدرت و دوام بیشتر نسبت به سایر روش های مبتنی بر هوش مصنوعی، بهتر است. بر خلاف سیستم های هوش مصنوعی قدیمی تر، الگوریتم ژنتیک با تغییر اندک مقادیر ورودی و یا با وجود مقادیر قابل توجهی از نویز در سیستم به راحتی قطع نمی شود. علاوه بر این، در جستجوی یک فضای حالت بزرگ، فضای حالت Multimodal و یا یک رویه چند بعدی، استفاده از الگوریتم ژنتیک مزیت های بسیار بیشتری نسبت به روش های جستجوی متداول در سایر تکنیک های بهینه سازی مانند برنامه ریزی خطی، جستجوی تصادفی و یا روش های جستجوی اول عمق، اول سطح و یا praxis دارد.

روش های نمایش

قبل از این که یک الگوریتم ژنتیک برای یک مسئله اجرا شود، یک روش برای کد کردن ژنوم ها به زبان کامپیوتر باید به کار رود. یکی از روش های معمول کد کردن به صورت رشته های باینری است: رشته های ۰ و ۱. یک راه حل مشابه دیگر کد کردن راه حل ها در آرایه ای از اعداد صحیح یا اعداد اعشاری است. سومین روش برای نمایش صفات در یک GA یک رشته از حروف است، که هر حرف دوباره نمایش دهنده یک خصوصیت از راه حل است. خاصیت هر سه روش این است که آن ها تعریف سازنده ای را که تغییرات تصادفی در آن ها ایجاد می کنند را آسان می کنند: ۰ را به ۱ و برعکس، اضافه یا کم کردن ارزش یک عدد یا تبدیل یک به صفر یا برعکس. یک روش دیگر که توسط John Koza توسعه یافت، برنامه نویسی ژنتیک است؛ که برنامه ها را به عنوان شاخه های داده در ساختار درخت نشان می دهد. در این روش تغییرات تصادفی می توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت، یا عوض کردن یک زیر درخت با دیگری به وجود آیند.

عملگرهای یک الگوریتم ژنتیک

در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است:در ابتدا روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. در دومین جزء اساسی الگوریتم ژنتیک روشی است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید.

ایده اصلی الگوریتم ژنتیک

در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه سازی های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن هاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم های او به نسل بعدی منتقل می شوند. هر ژن در این کروموزوم ها نماینده یک خصوصیت است. به عنوان مثال ژن ۱ می تواند رنگ چشم باشد، ژن ۲ طول قد، ژن ۳ رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهیست که در عمل چنین اتفاقی رخ نمی دهد. در واقع به صورت هم زمان دو اتفاق برای کروموزوم ها می افتد. اتفاق اول جهش (Mutation) است. «جهش» به این صورت است که بعضی ژن ها به صورت کاملاً تصادفی تغییر می کنند. البته تعداد این گونه ژن ها بسیار کم می باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است؛ مثلاً ژن رنگ چشم می تواند به صورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوه ای بوده اند. علاوه بر «جهش» اتفاق دیگری که می افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به «جهش» رخ می دهد چسبیدن دو کروموزوم از طول به یکدیگر و تبادل برخی قطعات بین دو کروموزوم است. این مسئله با نام Crossover شناخته می شود. این همان چیزیست که باعث می شود تا فرزندان ترکیب ژن های متفاوتی را (نسبت به والدین خود) به فرزندان خود انتقال دهند.

روش های انتخاب الگوریتم ژنتیک

روش های مختلفی برای الگوریتم های ژنتیک وجود دارند که می توان برای انتخاب ژنوم ها از آن ها استفاده کرد. اما روش های لیست شده در پایین از معمول ترین روش ها هستند.

  • انتخاب Elitist

مناسب ترین عضو هر اجتماع انتخاب می شود.

  • انتخاب Roulette

یک روش انتخاب است که در آن عنصری که عدد برازش (تناسب) بیشتری داشته باشد، انتخاب می شود. در واقع به نسبت عدد برازش برای هر عنصر یک احتمال تجمعی نسبت می دهیم و با این احتمال است که شانس انتخاب هر عنصر تعیین می شود.

  • انتخاب Scaling

به موازات افزایش متوسط عدد برازش جامعه، سنگینی انتخاب هم بیشتر می شود و جزئی تر. این روش وقتی کاربرد دارد که مجموعه دارای عناصری باشد که عدد برازش بزرگی دارند و فقط تفاوت های کوچکی آن ها را از هم تفکیک می کند.

  • انتخاب Tournament

یک زیر مجموعه از صفات یک جامعه انتخاب می شوند و اعضای آن مجموعه با هم رقابت می کنند و سرانجام فقط یک صفت از هر زیرگروه برای تولید انتخاب می شوند.

بعضی از روش های دیگر عبارتند از:

  1. Hierarchical Selection
  2. Steady-State Selection
  3. Rank Selection

عملگرهای یک الگوریتم ژنتیک

در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است: اول روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. به شکل سنتی یک جواب به صورت یک رشته از بیتها، اعداد یا نویسه ها.نمایش داده می شود.دوم روشی لازم است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. مثلاً اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند بدون اینکه کوله پشتی پاره شود، (مسئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ می تواند به شکل رشته ای از بیتهای ۰ و۱ در نظر گرفته شود, که ۱ یا ۰ بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است.تناسب پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه گیری می شود. روال بهینه یابی در الگوریتم ژنتیک براساس یک روند تصادفی- هدایت شده استوار می باشد. این روش,بر مبنای نظریه تکامل تدریجی و ایده های بنیادین داروین پایه گذاری شده است.در این روش , ابتدا برای تعدادی ثابت که جمعیت نامیده می شود مجموعه ای از پارامترهای هدف بصورت اتفاقی تولید می شود , پس از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعیت مذکور نسبت می دهیم. این عمل را برای تک تک اعضای ایجاد شده تکرار می کنیم , سپس با فراخوانی عملگرهای الگوریتم ژنتیک از جمله لقاح , جهش و انتخاب نسل بعد را شکل می دهیم و این روال تا ارضای معیار همگرایی ادامه داده خواهد شد. بصورت متداول سه معیار به عنوان معیار توقف شمرده می شود: ۱. زمان اجرای الگوریتم ۲. تعداد نسلهایی که ایجاد می شوند ۳. همگرایی معیار خطا

کاربردهای الگوریتم ژنتیک

  • روندیابی هیدرولوژیکی رواناب جاری در شبکه رودخانه خشک
  • کمک در حل مسایل تصمیم گیری چند معیاره
  • بهینه سازی چند هدفه در مدیریت منابع آبی
  • بهینه سازی و بارآرایی شبکه های توزیع نیروی برق
پایگاه خبری ساعدنیوز را در شبکه‌های اجتماعی دنبال کنید.

دیدگاه ها
  دیدگاه ها
پربحث های هفته   
مراسم سلام عید نوروز و اهداء سکه توسط فرح پهلوی به همسران مقامات دولتی +عکس/ ولخرجی زن تازه به دوران رسیده زمانی که مردم غرق در فقر و بدبختی بودند! (369 نظر) میزبانی حسن روحانی از سیاستمداران و اقوام در مراسم عید دیدنی در منزل زیبا و ایرانی پسندش+ عکس/ چه مبلمانی، چه فرش هایی، از همه مهمتر چه خونه دلبازی😍 (290 نظر) خلاقیت خنده دار یک ایرانی برای گرم کردن آب حماسه ساز شد/ خسته نباشی هم وطن+ عکس (239 نظر) تلاوت زیبا و دلنشین سوره شمس توسط رهبر معظم انقلاب+ویدئو (235 نظر) صبحانه مفصل و رنگارنگ دو نفره رضا گلزار و آیسان خانوم+عکس/از خاویار گرفته تا آواکادو و انار وحشی... (182 نظر) روایتی از هواپیمایی که برای آوردن یک روبان عروسی برای فرح پهلوی از تهران به پاریس رفت! (147 نظر) رونمایی منوچهر هادی از خواهر و شوهر خواهر پزشکش+ عکس/ به قولی مخ خانواده ایشون هستن که پسرش هم دکتره (145 نظر) خلاقیت منحصر به فرد پسر مشهدی با ساخت تریلی حماسه آفرید/ هیلتر هم مغز اینو نداشت!+عکس (140 نظر) تصویری از عیادت نجم الدین شریعتی، مجری برنامه سمت خدا از رهبر معظم انقلاب و استقبال گرم ایشان (133 نظر) دو پادشاه یکی از ایران (ناصرالدین شاه) و دیگری از ژاپن (میجی) در یک زمان به اروپا رفتند/ تفاوت ها را بنگرید (127 نظر) مراسم تولد جگرسوز آزاده نامداری در خانه ابدی اش و گریه های دلخراش همسر و پدرش/ روحت شاد+ عکس (123 نظر) خواهر یکتا ناصر سکوتش را شکست (120 نظر) استوری معنادار شاهین صمدپور برای یکتا ناصر و منوچهر هادی (101 نظر) اتاق خواب اروپایی و امروزی سانیا سالاری، ارغوانِ سریال دلدادگان با طراحی مدرن+عکس/ انصافا سلیقه خاصی داره! (98 نظر) خنده های رهبر معظم انقلاب به اشعار شاعر طنزپرداز با موضوع آقازاده+ویدئو/ ای صورت و سیرت تو مطلوب، به‌به به‌به به این ژن خوب (97 نظر)
دیگران می‌خوانند   
روایت خنده دار گاوی که از روی ملیکا شریفی نیا رد شد و عمرش را داد به مهران مدیری/ بیژ بیژ را بیشتر بشناسید+فیلم میز ناهار رنگارنگ مصطفی زمانی و مهتاب کرامتی در یک رستوران شیک چینی+عکس (عکس) کشف شگفت انگیز حلقه طلایی و زیبای کوروش هخامنشی در روسیه/ انگشتری متعلق به 500 سال قبل از میلاد مسیح عکس های دکوراسیون شیک و لاکچری خانه شیلا خداداد و همسر جراحش/ هفت سین جذابش را هم ببینید (تصاویر) حیوانات خانگی عجیب و غریب ملکه الیزابت دوم / باورتون میشه واقعا؟ (عکس) تلاشهای بی وقفه ی زن بریتانیایی برای جلب رضایت همسرش جواب داد و رکوردش در کتاب گینس ثبت شد فال قهوه با نشان روز جمعه 10 فروردین ماه 1403 فال ابجد روزانه جمعه 10 فروردین 1403 فال حافظ با تفسیر جمعه 10 فروردین 1403 + فیلم فال شمع روزانه امروز جمعه 10 فروردین 1403 فال روزانه امروز جمعه 10 فروردین ماه 1402 (عکس) جواد عزتی و علی مردانه در پشت صحنه فصل 3 سریال زخم کاری در رامسر / فصل 3 زخم کاری در راه است رونمایی از سفره افطار مفصل و رنگین 6 کیلومتری در مشهد +عکس 12 دروغ شاخداری که پدر و مادرها در بچگی به ما گفتند / خیلی از باورهای کودکیمان حقیقت ندارد و باید با واقعیت رو به رو شد اگر این 10 رفتار را در اولین قرارتان دیدید پا به فرار بگذارید / اگر طرف مقابل این رفتارها را داشت بدون فرد مناسبی برای ازدواج نیست (عکس) خوابیدن محمدرضا گلزار وسط تمرین ورزش / مثل اینکه فشار زندگی متاهلی با آیسان خانم زیاده🤣 جزئیات مسمومیت شدید یک جوان در پی بلعیدن مواد مخدر چهرۀ «خون‌آشام ایتالیایی» بعد از 400 سال بازسازی شد+ عکس مخالفت با بازیگر شدن فریبرز به سبک ژاله صامتی، پریِ سریال زیرخاکی+ویدئو/ اون تیکه معنی کردن چپر چلاغ برا کاوه خیلی خوب بود رونمایی از برادر جوان و قدبلند داریوش فرضیایی، عموپورنگ پرانرژی بچه ها/ جفتشون چقدرم مهربون و خوش استایلن+عکس امروز آخرین مهلت ثبت‌نام دیدار رمضانی دانشجویان با رهبر معظم انقلاب جایی که ابر‌ها زیر پای‌تان شناورند/ پیشنهادی رویایی برای سفر یک روزه در اطراف تهران (ویدئو) مظنون فراری از دست پلیس به خودروی در حال حرکت آویزان شد حرکات با مزه گربه وقتی خودش رو توی آینه میبینه/ چه دیوونه بازی هایی درمیاره+ فیلم واکنش معین به انتشار خبر حضور پنهانی‌اش در ایران/ معین چند بار به ایران آمده؟ هم میز شدن امیر قلعه نویی و علی دایی در ضیافت افطاری در آجودانیه+عکس/ چهره بشاش و شاد هر دو سرمربی سابق و فعلی تیم ملی مبتلا شدن ستاره سادات قطبی به بیماری ناشناخته و دست و پنجه نرم کردن با مرگ+ویدئو عروسی مجلل دختر شاه اینجا برگزار شد!+عکس سلفی عجیب و غریب بهرام رادان با سفره هفت سین ساده در دفتر کارش در دوران مجردی+ عکس/ برا همیناست که میگن ازدوج کنی سر و سامون میگیری غوغای خوانندگی و نوازندگی شهاب حسینی با آهنگ ناصر عبداللهی +ویدئو/عجب صدای قشنگی داره! تصاویری از دوقلوهای ریزه میزه و بانمک یاسمین مقبلی در کنار مادر فضانوردشان (ویدیو) رقصی این چنین در میانه میدانم آرزوست!/ واکنش ماده شیمیایی با اشعه‌ی فرابنفش (عکس) ماجرای ازدواج جنجالی ژیلا صادقی با بازیگر سریال "رستگاری" و "بچه مهندس3"، کاوه سماک باشی، چه بود و به کجا رسید مدیتیشن بهاری الناز شاکردوست با ظاهر عجیب و شال پیچی شده در کرمانشاه/ بیستون کعبه عشاق جهان است هنوز+عکس کتک کاری و بزن بزن در مراسم عروسی دختر قلعه نویی/شوخی بی جا کار دست مهمان داد (فیلم) همخوانی هلیا امامی در کنسرت مسعود صادقلو / تعطیلات عید خانم بازیگر از مشهد تا کنسرت صادقلو (عکس) وقتی شاهرخ استخری دختراشو سر صبحی میبره مدرسه / نبات چه غری میزنه 🤣 خلاقیت منحصر به فرد باغبان خوش ذوق با پرورش میوه های قلبی شکل حماسه ساز شد +ویدئو/مغز تو رو باید طلا گرفت! (عکس) گشت و گذار بهاری دمت اوزدمیر با ظاهری متفاوت در یک جای بهشتی تصویری از عبادت خالصانه رهبر انقلاب، آیت الله خامنه ای در حیاط با صفا و سرسبز/ قبول حق باشه
تیتر امروز   
12 دروغ شاخداری که پدر و مادرها در بچگی به ما گفتند / خیلی از باورهای کودکیمان حقیقت ندارد و باید با واقعیت رو به رو شد اگر این 10 رفتار را در اولین قرارتان دیدید پا به فرار بگذارید / اگر طرف مقابل این رفتارها را داشت بدون فرد مناسبی برای ازدواج نیست جزئیات مسمومیت شدید یک جوان در پی بلعیدن مواد مخدر چهرۀ «خون‌آشام ایتالیایی» بعد از 400 سال بازسازی شد+ عکس امروز آخرین مهلت ثبت‌نام دیدار رمضانی دانشجویان با رهبر معظم انقلاب جایی که ابر‌ها زیر پای‌تان شناورند/ پیشنهادی رویایی برای سفر یک روزه در اطراف تهران فال قهوه با نشان روز جمعه 10 فروردین ماه 1403 فال ابجد روزانه جمعه 10 فروردین 1403 فال حافظ با تفسیر جمعه 10 فروردین 1403 + فیلم فال شمع روزانه امروز جمعه 10 فروردین 1403 واکنش معین به انتشار خبر حضور پنهانی‌اش در ایران/ معین چند بار به ایران آمده؟ فال روزانه امروز جمعه 10 فروردین ماه 1402 عروسی مجلل دختر شاه اینجا برگزار شد!+عکس کتک کاری و بزن بزن در مراسم عروسی دختر قلعه نویی/شوخی بی جا کار دست مهمان داد پادشاهی که فقط 20 دقیقه سلطنت کرد+عکس