الگوریتم ژنتیک که روش بهینه‌سازی الهام گرفته از طبیعت جاندار(موجودات زنده) است که می‌توان در طبقه‌بندی‌ها، از آن به عنوان یک روش عددی، جستجوی مستقیم و تصادفی یاد کرد. این الگوریتم، الگوریتمی مبتنی بر تکرار است و اصول اولیۀ آن همانطور که پیشتر اشاره شد از علم ژنتیک اقتباس گردیده است و با تقلید از تعدادی از فرآیندهای مشاهده شده در تکامل طبیعی اختراع شده است و به طور موثّری از معرفت قدیمی موجود در یک جمعیت استفاده می‌کند، تا حل‌های جدید و بهبود یافته را ایجاد کند. این الگوریتم در مسائل متنوعی نظیر بهینه‌سازی، شناسایی و کنترل سیستم، پردازش تصویر و مسایل ترکیبی، تعین توپولوژی و آموزش شبکه‌های عصبی مصنوعی و سیستم‌های مبتنی بر تصمیم و قاعده به کار می‌رود.

در اینجا لازم می‌بینم که برای ورود به موضوع اصلی این نوشتار (الگوریتم ژنتیک) مروری بر مطالبی که پیشتر در مورد مباحث «ژنتیک» و «الگوریتم» ارائه شد داشته باشیم.

چنانکه قبل‌تر اشاره شد، علم ژنتیک، علمی است که دربارۀ چگونگی توارث و انتقال صفحات بیولوژیکی از نسلی به نسل بعد صحبت می‌کند. عامل اصلی انتقال صفحات بیولوژیکی در موجودات زنده کروموزوم‌ها[1] و ژن‌ها[2] می‌باشد و نحوه عملکرد آنها به گونه‌ای است که در نهایت ژن‌ها و کروموزوم‌های برتر و قوی مانده و ژن‌هاي ضعيف‌تر از بين مي‌روند. به عبارت ديگر نتيجۀ عمليات متقابل ژن‌ها و كروموزوم‌‌ها باقي ماندن موجودات اَصلح و برتر مي‌باشد.

همچنین مجدداً یادآور می‌شویم که اين الگوريتم براي بهينه سازي، جستجو و يادگيري ماشين مورد استفاده قرار مي‌گيرد. اساس اين الگوريتم قانونِ تكاملِ داروين (بقا بهترين) است كه مي‌گويد: موجودات ضعيف‌تر از بين مي‌روند و موجودات قوي‌تر باقي مي‌مانند. در واقع تكامل فرآيندي است كه روي رشته‌ها صورت مي‌گيرد، نه روي موجودات زنده‌اي كه معرف موجودات رشته است. در واقع، قانون انتخاب طبيعي براي بقا مي‌گويد كه هر چه امكان تطبيق موجود بيشتر باشد بقاي موجود امكان‌پذيرتر است و احتمال توليد مثل بيشتري، برايش وجود دارد. اين قانون بر اساس پيوند بين رشته‌ها و عملكرد ساختمان‌هاي رمزگشايي شده آنها مي‌باشد.

الگوريتم ژنتيك به دليل تقليد نمودن از طبيعت داراي چند اختلاف اساسي با روش‌هاي جستجوي مرسوم مي‌باشد كه در زير به تعدادي از آنها اشاره مي‌كنيم.

  • الگوريتم ژنتيك با رشته‌هاي بيتي كار مي‌كند كه هر كدام از اين رشته‌ها كلّ مجموعه متغيرها را نشان مي‌دهد حال آنكه بيشتر روش‌ها به طور مستقل با متغيرهاي ويژه برخورد مي‌كنند.
  • الگوريتم ژنتيك براي راهنمايي جهت جستجو، انتخاب تصادفي انجام مي‌دهد كه به اين ترتيب به اطلاعات مشتق نياز ندارد.
  • در الگوريتم ژنتيك روش‌هاي جستجو بر اساس مكانيزم انتخاب و ژنتيك طبيعي عمل مي‌نمايند.

اين الگوريتم‌ها مناسب‌ترين رشته‌ها را از ميان اطلاعات تصادفي سازماندهي شده انتخاب مي‌كنند. در هر نسل يك گروه جديد رشته‌ها با استفاده از بهترين قسمت‌هاي دنباله‌هاي قبلي و بخش جديد اتفاقي براي رسيدن به يك جواب مناسب به وجود مي‌آيند. با وجود اينكه الگوريتم‌ها تصادفي هستند ولي در زمره الگوريتم‌هاي تصادفي ساده نيستند. آنها به طور كارآمدي به اكتشاف اطلاعات گذشته در فضاي جستجو مي‌پردازند تا در يك نقطه جستجوي جديدي با پاسخ‌هاي بهتر به سمت بهترين جواب پيش روند. هنگام پيش‌‌آمدسازي[3] الگوريتم‌هاي ژنتيك عمل پيش‌آمدسازي ساده را نمي‌پيمايند بلكه آنها داده‌هاي پيشين را با تفكّرِ انتخابِ جستجويِ جديد براي رسيدن پيشرفتِ مورد نظر توأم مي‌كنند.

  • الگوريتم ژنتيك در هر تكرار چند نقطه از فضاي جستجو را در نظر مي‌گيرد بنابراين شانس اينكه به يك ماكزيمم محلي همگرا شود كاهش مي‌يابد.

در بيشتر روش‌هاي جستجوي مرسوم (روش گراديان) قاعده تصميم حاكم به اين صورت عمل مي‌كند كه از اين يك نقطه به نقطۀ ديگر حركت مي‌كند. اين روش‌ها مي‌توانند در فضاهاي جستجو داراي چند بيشينۀ خطرناك باشند. زيرا ممكن است آنها به يك ماکزيمم محلي همگرا شوند. ليكن الگوريتم ژنتيك جمعيت‌هاي كاملي از رشته‌ها (نقاط) را توليد مي‌كند سپس هر نقطه را به صورت انفرادي امتحان مي‌كند و با تركيب محتويات آنها يك جمعيت جديد را كه شامل نقاط بهبود يافته است تشكيل مي‌دهد. صرف نظر از انجام يك جستجو ملاحظۀ هم‌زمانِ تعدادي نقطه در الگوريتم ژنتيك آنها را با ماشين‌هاي موازي تطبيق مي‌سازد زيرا در اينجا تكامل هر نقطه يك فرآيند مستقل است. لذا الگوريتم ژنتيك فقط نياز به اطلاعاتي در مورد كيفيت حل‌هاي ايجاد شده به وسيلۀ هر مجموعه از متغيرها دارد، در صورتي كه بعضي از روش‌هاي بهينه‌سازي نياز به اطلاعات يا حتي نياز به شناخت كامل از ساختمان مسأله و متغيرها دارند. چون الگوريتم ژنتيك نياز به چنين اطلاعات مشخصي از مسأله ندارد بنابراين قابل انعطاف‌تر از بيشتر روش‌هاي جستجو است. همچنين الگوريتم ژنتيك از روش‌هاي جستجوي نوعي كه براي راهنمايي جهت روش‌هاي جستجويشان از انتخاب تصادفي استفاده مي‌كنند متفاوت است زيرا اگر چه براي تعريف روش‌هاي تصميم‌گيري از تصادف و شانس استفاده مي‌كند ولي در فضاي جستجو به صورت تصادفي قدم نمي‌زند.[13]

  • الگوریتم ژنتیک از قوانین احتمالی پیروی می‌کند و نه از قوانین قطعی.[5]

 

[1] Chromosome

[2] Gene

[3] Randomization