وفق پذيري شامل يک سري تغييرات در ساختار برنامه مي باشد به گونه اي که در محيط خود بهتر عمل

کند. يادگيري گونه اي از وفق پذيري مي باشد که در آن هدف حل يک مسئله است. در ادامه به بررسي موارد زير خواهيم پرداخت.

  • ساختارهايي که عمل وفق پذيري را انجام مي دهند.
  • ساختارهاي اوليه
  • مقدار تناسب که ساختارها را مورد ارزيابي قرار مي دهد.
  • عملياتي که جهت تغيير ساختارها استفاده مي شود.
  • انتخاب پاسخ
  • شرط خاتمه
  • پارامترهاي کنترل

4-1. ساختارهايي که عمل وفق پذيري را انجام مي دهند

در تمامي سيستم هاي يادگيري ساختارهايي وجود دارند که اين عمليات را انجام مي دهند.اين ساختارها در برنامه نويسي ژنتيک ،برنامه هاي کامپيوتري ساخت يافته سلسله مراتبي هستند. اندازه، شکل و پيچيدگي اين برنامه هاي کامپيوتري در طي عمل پردازش به طور پويا تغيير مي کنند.

مجموعه ساختارهاي ممکن در برنامه نويسي ژنتيک شامل مجموعه ترکيبات ممکن از توابع مي باشد که مي تواند به طور بازگشتي از مجموعه ممکن N  تابع از مجموعه توابع F={f1,f2,…,fN} و مجموعه ممکن از M پايانه از مجموعه پايانه ها T={a1,a2,…,aM} بدست آيد.

توابع موجود در مجموعه توابع مي توانند يکي از حالات زير باشند:

  • عملگرهاي رياضي ( + , – , *, etc )
  • توابع رياضي ( Sin , Cos , Exp , etc )
  • عملگرهاي بولي ( AND , OR , NOT , etc )
  • عملگرهاي منطقي( If-Then-Else )
  • عملگرهاي تکرار حلقه وبازگشتي

همانطور که قبلا گفته شد پايانه ها مي توانند اتمهاي ثابت و يا اتمهاي متغير باشند.مجموئه تابع زير را در نظر بگيريد:

F = { AND , OR , NOT }

و مجموعه پايانه ها:

T = { D0 , D1 }

که D0 و D1 اتمهاي متغير بولي هستند که بعنوان آرگومانهاي تابع عمل مي کنند.

حال تابع توازن زوج با دو آرگومان را در نظر مي گيريم. اين تابع بولي را بصورت زير نشان داد.

 

( OR ( AND ( NOT D0 ) ( NOT D1 ) ) ( AND D0 D1 ) )

 

فرم درختي اين درخت در شکل4-1 نشان داده شده است.

 

انتخاب مجموعه توابع و پايانه ها بايد به گونه اي باشد که دو شرط بسته بودن و کافي بودن را برآورده کند.

 

4-1-1 . شرط بسته بودن

هر تابعي که در مجموعه توابع مشخص مي شود بايد به گونه اي باشد که براي هر گونه ترکيبي از آرگومانها به خوبي تعريف شده باشد. فرضا اگر عملگر رياضي تقسيم را بعنوان يکي از توابع موجود تعريف کنيم بايد براي تقسيم بر صفر آن نيز چاره اي انديشيد. فرضا مي توان از تقسيم حفاظت شده ( % ) استفاده کرد. اگر شرط بسته بودن وجود نداشت يا بايد از عضوهايي که درون دامنه دلخواه نيستند صرف نظر کرد و يا جريمه اي براي مقدار تناسب اين عضو ها در نظر گرفت.

 

4-1-2 . شرط کافي بودن

اين شرط بيان ميکند که مجموعه توابع و پايانه هايي که براي مسئله اي خاص انتخاب مي شوند قادر به حل مسئله باشند. فرضا تابع NOT بايد براي توابع بولي تعريف شده باشد چرا که از روي توابع ديگر نمي توان آنرا بدست آورد.

 

4-2. ساختارهاي اوليه

ساختارهاي اوليه در برنامه نويسي ژنتيک شامل عضوهايي در نسل اوليه برنامه مي باشند که از ساخت درختي بطور تصادفي از روي مجموعه توابع و پايانه ها بدست مي آ يد. اين کار با انتخاب يک تابع از مجموعه توابع بعنوان ريشه درخت شروع مي شود. انتخاب يک تابع بعنوان ريشه درخت بدين دليل است که ما خواهان ايجاد يک ساختار سلسله مراتبي مي باشيم و نه ساختاري که صرفا از يک نود ريشه تشکيل شده باشد. عمل ايجاد درخت ها شامل ايجاد يک تعداد درخت مشخص درهر نسل با عمقي بين دو تا يک مقدار مشخص ميباشد. عمق يک درخت برابر طول طولاني ترين مسيراز ريشه تا يک پايانه مي باشد. سپس براي هر مقدار عمق 50 % درختها تا آن عمق به يکي از دو روش زير ايجاد مي شوند.

  • 50 % درختها با عمق مشخص ، درخت پر هستند به اين معنا که طول مسير بين هر پايانه تا ريشه ماکزيمم مي باشد. در واقع با محدود کردن انتخاب نودها تا عمقي کمتر از مقدار ماکزيمم از مجموعه F و انتخاب نودها با عمق ماکزيمم از مجموعه T بدست مي آيد.
  • 50 %   درختها با عمق مشخص ، درخت با عمق متغير هستند به اين معنا که طول مسير بين هر پايانه تا ريشه بيشتر از مقدار ماکزيمم نباشد. در واقع با انتخاب نودها تا عمقي کمتر از مقدار ماکزيمم از مجموعه F و T و انتخاب نودها با عمق ماکزيمم از مجموعه T بدست مي آيد.

 

در واقع از توزيع تصادفي يکنواخت براي ايجاد انتخابهاي بالا از مجموعه هاي تعريف شده استفاده مي شود. ضمنا براي جلوگيري از ايجاد درختي مشابه ، پس از ايجاد هر درخت جديد آنرا با مجموعه درختهاي ايجاد شده از قبل مقايسه و در صورت يکسان بودن از آن صرفنظر مي شود.گوناگوني يک نسل درصدي از اعضا است که در آن نسل هيچ عضو تکراري موجود نباشد. گوناگوني اولين نسل 100% مي باشد.

 

4-3 . تناسب

به هر عضو در يک نسل مقداري عددي که نشان دهنده تراکنش آن با محيطش مي باشد نسبت داده مي شود. تناسب الهام گرفته شده از انتخاب دارويني از طبيعت است. در اين بخش به معرفي چهار نوع به نامهاي تناسب خام ، استاندارد ، تنظيم شده و نرمال شده خواهيم پرداخت.

تناسب خام اندازه گيري از تناسب است که در ذات خود مسئله نهفته است و اين بستگي به مسئله دارد. براي خيلي از مسائل مي تواند مجموع فواصل ( فرضا خطا ) انتخاب شود که از رابطه زير بدست مي آيد.

 

که در آن   مقدار بازگشتي از عضو ام براي مورد تناسب j ام و C ( j ) مقدار صحيح مورد تناسب j ام مي باشد و t نشاندهنده زمان مي باشد.

براي ساير مسائل تناسب خام مي تواند زمان اندازه گيري شده ، سود و… باشد. بنابراين تناسب خام براي مسائلي که تناسب خطا است هر چه کمتر باشد بهتر است و براي مسائلي که تناسب سود باشد هر چه بيشتر باشد بهتر مي باشد.

تناسب استاندارد ، تناسب خام را به گونه اي مطرح مي کند که مقادير کمتر بهتر باشند. اگر کمتربودن مقدار تناسب خام نشاندهنده بهتر بودن باشد اين دو مقدار با يکديگر برابرند در غير اين صورت از رابطه زير بدست مي آيد.

 

که    نشاندهنده مقدار تناسب خام ماکزيمم مي باشد.

تناسب تنظيم شده از رابطه زير بدست مي آيد:

 

مقدار تناسب تنظيم شده بين صفر و يک مي باشد.بر خلاف تناسب استاندارد براي مقادير بيشتر بهتر مي باشد. اگر مقدار  مشخص نباشد اين بخش مي تواند حذف شده و مقدار تناسب تنظيم شده مستقيما از تناسب خام بدست آيد.

تناسب نرمال شده از رابطه زير بدست مي آيد:

 

تناسب نرمال شده داراي خواص زير است:

  • بين صفر و يک قرار دارد.
  • براي عضوهاي بهتر اين مقدار بهتر است.
  • مجموع مقادير تناسبهاي نرمال شده يک مي باشد.

 

4-4. عملياتي جهت تغيير ساختارها

عمليات اوليه اي که جهت تغيير ساختارها استفاده مي شوند به شرح زير مي باشند:

  • عمل خود توليد بر اساس نسبت تناسب دارويني
  • عمل توليد مثل

 

4-4-1. عمل خود توليد

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

 

 

توجه شود در هنگامي که عمل انتخاب در نسل جاري انجام مي شود والد در جمعيت باقي مي ماند. اين بدان معناست والدين بيش از بار براي عمل خود توليد انتخاب مي شوند.

 

4-4-2. عمل توليد مثل

اين عمل با انتخاب دو والد از نسل جاري شروع شده و منجر به توليد دو فرزند مي شود. معمولا حداقل يکي از والدين با احتمالي برابر با تناسب نرمال شده از جمعيت انتخاب مي شود.عمل با انتخاب يک نقطه بطور تصادفي از هر يک از والدين شروع مي شود و سپس زير درختهاي انتخاب شده با يکديگر جابجا مي شوند. شکل 4-2 اين عمل را نشان مي دهد و فرض کنيد اعداد 2 و 6 جهت جابجا شدن انتخاب شده باشند.

 

عبارت ليسپ دو درخت والد بصورت زير مي باشد:

( OR ( NOT D1 ) ( AND D0 D1 ) )

 

( OR ( OR D1 ( NOT D0 ) ) ( AND ( NOT D0 ) ( NOT D1 ) )

 

4-5. انتخاب پاسخ

بهترين عضو جمعيت در هنگام خاتمه برنامه بعنوان جواب انتخاب مي شود و دليلي ندارد که اين انتخاب بهترين جواب ممکن باشد.

 

4-6 . شرط خاتمه

يک برنامه ژنتيک هنگامي خاتمه مي يابد که يا تا يک تعداد نسل مشخص برنامه اجرا شده باشد و يا تناسب استاندارد مسئله به صفر ويا همسايگي صفر رسيده باشد.

4-7. پارامترهاي کنترل

دو پارامتر مهم عبارتند از اندازه جمعيت وتعداد نسلي که برنامه بايد اجرا شود.پارامتر بعدي انتخاب درصدي از جمعيت براي عمل توليد مثل مي باشد. فرضا 90 % از جمعيت از عمل توليد مثل و 10 % باقيمانده از عمل خود توليد دارويني انتخاب مي شود.پارامتر بعدي مي تواند انتخاب فرضا 90 % از نودهاي داخلي جهت عمل توليد مثل و 10 % از نودهاي برگ انتخاب شود. با اين عمل ساختارهاي بزرگتري با يکديگر ترکيب مي شوند. ساير پارامترها مي تواند انتخاب محدوده عمق براي نسل اوليه ونسلهاي بعدي باشد.

 

5. مالتي پلکسر-11 بولي                        

اين مسئله يکي از مسائل کلا سيک در زمينه برنامه نويسي ژنتيک مي باشد. مالتي پلکسر-N                                           شامل k  خط آدرس  و 2 خط داده  مي باشد که 2 N = k + . مقدار تابع مالتي پلکسربولي مقدار بولي صفر يا يک خط دادهاي مي باشد که توسط k خط آدرس انتخاب و به خروجي منتقل مي شود. شکل 5-1 يک مالتي پلکسر-11 را با ورودي 11001000000 وخروجي 1 نشان مي دهد.

 

براي حل يک مسئله با برنامه نويسي ژنتيک پنج گام اصلي بايد طي شود که بشرح زير مي باشد.

  1. مجموعه پايانه ها
  2. مجموعه توابع
  3. تابع تناسب
  4. پارامترهاي راه انداز برنامه
  5. شرط خاتمه برنامه

اولين گام مهم در حل برنامه نويسي ژنتيک انتخاب پايانه ها مي باشد. در اين مسئله اين مجموعه برابر با خطوط آدرس و داده خواهد بود. البته در ابتداي مسئله تفاوتي بين خطوط آدرس وداده قائل نمي شويم.

T = { A0 , A1 , A2 , D0 , D1 , … , D7 }

دومين گام مهم انتخاب مجموعه توابع مناسب جهت حل مسئله مي باشد. براي اين مسئله اين مجموعه بصورت زير مي با شد:

F = { AND , OR , NOT , IF }

که به ترتيب داراي 1،2،2 و3 آرگومان مي باشد. تابع IF بکار رفته قبلا مورد بررسي قرار گرفته بود. اين مجموعه توابع هر دو شرط بسته بودن وکافي بودن را در بر مي گيرد.

فضاي جستجوي مسئله تمام عباراتي است که مي تواند از ترکيب مجموعه توابع وپايانه ها بدست آيد .                 سومين گام مهم انتخاب تابع تناسب مي باشد. همانطور که   ترکيب مختلف از آرگومانها ي مسئله بدست مي آيد. بنابراين اين عدد مي تواند تخميني مناسب جهت تناسب خام باشد يعني هر تعداد جواب صحيحي که توسط يک عبارت پيدا شود بعنوان تناسب خام ارزيابي شده که اين مقدار مي تواند بين 0 و 2048 باشد. عبارتي که تمامي 2048 مورد را صحيح ارزيابي کند جواب مسئله است. تناسب استاندارد اين مسئله برابر با تفاضل تعداد صحيح بدست آمده از تعداد ماکزيمم حالات مي باشد.

چهارمين گام مهم انتخاب پارامترهاي برنامه مي باشد. فرضا مي توان تعداد اعضاء نسل اول را 4000 در نظر گرفت.

پنجمين گام مهم برنامه انتخاب شرط خاتمه مي باشد که در اين مسئله رسيدن به تناسب خام 2048 و يا اجراي برنامه تا يک تعداد نسل مي با شد.عمل پردازش با ايجاد تصادفي نسل صفر آغاز شد. اکثر عضو هاي ايجاد شده در اين نسل داراي مقدار تناسب پاييني بودند. بعضي از آنها مقادير ثابتي بودند مانند ( AND A0 ( NOT A0 ) )         در      برخي   ديگر   مقدار    ورودي    با خروجي يکسان بود مانند    ( NOT ( NOT A1 ) ) برخي از اعضاء ناکارا بودند مانند ( OR D7 D7 )   و در برخي ديگر جاي آرگومانهاي داده وآدرس با هم جابجا شده بود مانند ( IF D0 A0 A2 ) . هر چند که حتي در چنين جمعيتي برخي از اعضاء نسبت به مابقي داراي تناسب بالاتري بودند. در واقع 23 عضو از 4000 عضو نسل اوليه داراي تناسب خام 1280 بودند. ( IF A0 D1 D2 ) يکي از اين موارد مي باشد. تناسب استاندارد متوسط نسل اول 985 بود .

هيستوگرام برخورد يکي از روشهاي سودمند جهت نشان دادن اندازه برخورد مي باشد. ( منظور از اندازه برخورد تعداد موارد صحيح تشخيص داده مي باشد.) محور افقي اين نمودار تعداد برخوردها را نشان مي دهد ومحور عمودي نشان دهنده تعداد اعضايي مي باشد که اين ميزان برخورد را داشته اند. در روي محور افقي بسته هاي 64 تائي از مقدار تناسب در نظر گرفته شده است. شکل 5-2 نمودار برخورد در نسل صفر را نشان مي دهد.