انتخاب چرخ رولت

ساده ترين طرح انتخاب ، انتخاب چرخ رولت می باشد به اين روش، نمونه گيري تصادفي با جايگزيني نيز گفته مي گردد [[bak87 . اين الگوريتم تصادفي با تكنيك ذيل ، انجام مي گيرد .

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

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

جدول زير، احتمال انتخاب براي 11 فرد ، همراه با رتبه بندي خطي و فشار انتخابي 2 و مقدار برازندگي آنها را نشان مي دهد. فرد 1 برازنده ترين فرد و بزرگترين فاصله را اشغال كرده می باشد همانطور كه فرد 10 تقريباً كمترين برازندگي فرد را دارد و همچنين تقريباً كوچكترين فاصله روي خط را اشغال نموده می باشد .

فرد11 حداقل فاصله و مقدار برازندگي صفر را دارد و هيچ شانسي براي توليد مثل مجدد ، ندارد .

براي انتخاب جمعيت توليد مثل ،‌تعداد مناسب از اعداد تصادفي و يكنواخت توزيع شده ( يكنواخت بين 1,0 توزيع شده می باشد )و بصورت مستقل به دست آمده می باشد.

6 نمونه اعداد تصادفي :                42/0و65/0و01/0و96/0و32/0و81/0

شكل ذيل فرآيند انتخاب افراد براي نمونه در جدول فوق همراه با تلاشهاي مربوطه را نشان مي دهد .

بعد از انتخاب ، جمعيت توليد مثل شامل افراد ذيل مي باشد .

1.2.3.5.6.9

اين انتخاب الگوريتم چرخ رولت تمايل صفر را فراهم مي كند .اما محدودة مينيمم را تضمين نمي كند .

4-3- نمونه گيري كلي تصادفي

نمونه گيري كلي تصادفي يك تمايل صفر و محدودة مينيمم را فراهم مي كند افراد در قسمتهاي پيوسته يك خط قرار مي‌گيرند بطوريكه هر قسمت ، فرد با مقدار برازندگيش دقيقاً‌مطابق با انتخاب چرخ رولت ، مساوي می باشد . اينجا نشانگرها بطور مساوي روي خط قرار داده شده اند به تعدادي كه افراد انتخاب شده وجود دارند به Npointer تعداد افراد انتخاب شده ، فاصله بين نشانگرها و موقعيت اولين نشانگر كه بصورت عدد تصادفي در فاصله انتخاب شده ، توجه نمائيد .

براي 6 افراد انتخاب شده ، فاصله بين نشانگرها می باشد . شكل ذيل ، فرآيند انتخاب براي مثال فوق را نشان مي دهد .

نمونه عدد تصادفي در محدوده :             1/0

بعد از انتخاب جمعيت توليد مثل ،شامل افراد زير خواهد بود .

1.2.3.4.6.8

نمونه گيري كلي تصادفي يك انتخاب توليد مثل كه نزديكتر به شرايط مطلوب می باشد را نسبت به انتخاب چرخ رولت ، را اطمينان خواهد داد .

5-3- انتخاب محلي

در انتخاب محلي هر فرد داخل يك محيط تحميلي كه همسايگي محلي ناميده مي گردد قرار گرفته اند ( در روشهاي انتخاب ديگر ، همة جمعيت يا زير جمعيت در استخر يا همسايگي انتخاب قرار مي گيرند). افراد فقط با افرادداخل اين منطقه اثر متقابل دارند . اين همسايگي بوسيله ساختار جمعيت توزيع شده ، تعريف گرديده می باشد اين همسايگي مي تواند به عنوان يك گروه اصلي والدين توليد مثل ديده گردد .

انتخاب محلي قسمتي از مدل جمعيت محلي می باشد ( قسمت 2-7 مراجعه گردد )

اولين مرحله ، انتخاب اولين نصف از جمعيت يكنواخت توليد مثل تصادفي می باشد ( يا بهره گیری از يكي از الگوريتم هاي انتخاب ذكر شده ديگر مي باشد بطور مثال نمونه گيري كلي تصادفي يا انتخاب برشي ) حالا يك همسايگي محلي براي هر فرد انتخاب شده تعريف مي گردد . داخل اين همسايگي شريك توليد مثل انتخاب شده می باشد( بهترين ، تناسب برازندگي يا يكنواختي تصادفي ) ساختار اين همسايگي بصورت :

1- خطي حلقه كامل ، نصف حلقه (شكل را نظاره نماييد )

2- دوبعدي: الف- تقاطع كامل، تقاطع نصفه ( شكل سمت چپ را نظاره كنيد )

ب: ستاره كامل، نصف ستاره ( شكل سمت راست را نظاره كنيد)

3- سه بعدي .و پيچيده تر با هر تركيبي از ساختارهاي فوق

فاصله بين همسايه هاي احتمالي با هم ، ساختار اندازة همسايگي را تعيين مي كند، جدول 3-3 مثالهايي براي اندازه همسايگي در ساختار ارائه شده و مقادير مختلف فاصله را ارائه مي دهد .

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

اندازه همسايگي ، سرعت تكثير اطلاعات بين افراد جمعيت را نيز تعيين نموده ، تا تصميم گيري بين تكثير سريع يا بقاء تنوع / تغيير پذيري زياد درجمعيت را ايجاد كند . اغلب تغيير پذيري زيادتر مطلوب مي باشد زيرا براي جلوگيري از مشكلاتي مانند همگرايي نابهنگام در يك مينيمم محلي ، انجام مي گيرد . نتايج مشابه در [VBS91] نيز بدست آمده می باشد . انتخاب محلي با همسايگي كوچك، بهتر از انتخاب محلي با همسايگي بزرگتر، اجراء مي گردد . بدون شك اتصالات داخلي بايد براي همه جمعيت نيز فراهم گردد .

همسايگي دو بعدي با ساختار نصف ستاره و با بهره گیری از فاصله 1 براي انتخاب محلي ، توصيه شده می باشد .

شما می توانید مطالب مشابه این مطلب را با جستجو در همین سایت بخوانید                     

بنابراين اگر جمعيت بزرگتر گردد ( بزرگتر از 100) ، يك فاصله بزرگتر و / يا همسايگي دو بعدي ديگر بايد بهره گیری گردد.

6-3- انتخاب برشي ( كاهشي )

در مقايسه با روشهاي انتخاب قبلي ( مدل كردن با انتخاب طبيعي ) ، انتخاب برشي يك روش انتخاب مصنوعي می باشد كه از فرزندان براي انتخاب جمعيتهاي بزرگ بهره گیری مي گردد .

در انتخاب برشي ، افراد مطابق برازندگي اشان دسته بندي مي شوند فقط بهترين افراد به عنوان والدين انتخاب مي شوند . اين والدين انتخاب شده ، توليد مثل يكنواخت و تصادفي را انجام مي دهند . پارامتر مهم در انتخاب برشي ، آستانه برش Trunc می باشد .

Trunc ، نسبت جمعيت انتخاب شده بعنوان والدين ، در محدوده مقادير از 10% تا 50% را نشان ميدهد . افراد پايين تر از آستانه برش در توليد مثل شركت نمي‌كنند . اغلب عبارت قدرت انتخاب در انتخاب برشي ، نيز مورد بهره گیری قرار مي‌گيرد .

جدول ذيل ارتباط بين دو پارامتر فوق را نشان مي دهد

1-6-3- آناليز انتخاب برشي

در [BT95] آناليز انتخاب برشي بيان شده می باشد همچنين نتايج مشابه با روش مختلف نيز در [Ck70] ، بدست آمده می باشد

قدرت انتخاب :

(14-3)                                      

عدم تنوع :

(15-3)                                             

واريانس انتخاب:

(16-3)

7-3- انتخاب مسابقه‌اي ( رقابتي )

در انتخاب مسابقه‌اي [GD91] ، عدد Tour‌ افراد، به گونه تصادفي از جمعيت انتخاب مي شوند و بهترين فرد از اين جمعيت فرعي بعنوان والدين انتخاب مي گردد . اين فرآيند بطور مكرر تكرار مي گردد تا افراد كامل انتخاب گردند . اين والدين هاي انتخاب شده ، در توليد مثل يكنواخت و تصادفي ، شركت مي كنند . پارامتر مهم در انتخاب سابقه‌اي ، مقدار Tour مسابقه‌اي می باشد مقادر Tour در محدودة 2تا Nind (تعداد افراد جمعيت ) درنظر گرفته مي گردد .

جدول و شكل ذيل ارتباط بين مقدار مسابقه‌ و قدرت انتخاب را نشان ميدهد .

1-7-3- آناليز انتخاب مسابقه‌اي

در [BT95] آناليز انتخاب مسابقه‌اي ارائه گرديده می باشد .

قدرت انتخاب :

(17-3)                  

عدم تنوع :

(18-3)                             

(‌تقريباً 50% از جمعيت در اندازه مسابقه اي Tour =5 ، كنار گذاشته مي شوند )

واريانس انتخاب :

(19-3)

8-3- مقايسه طرحهاي انتخاب

شما می توانید تکه های دیگری از این مطلب را در شماره بندی انتهای صفحه بخوانید              

همانطور كه در قسمتهاي قبلي اين فصل ، نشان داده گردید روشهاي انتخاب بطور مشابه رفتار نموده و قدرت انتخاب مشابهي را نيز فرض مي‌گيرند .

1-8-3- پارامتر انتخاب و قدرت انتخاب

شكل ذيل ارتباط بين قدرت انتخاب و پارامترهاي مناسب روشهاي انتخاب ( فشار انتخاب ، آستانه برشي ، و اندازه مسابقه ) را نشان مي دهد و. لازم به ذكر مي باشد كه با انتخاب مسابقه‌‌اي فقط مقادير مجزا بكار گرفته مي شوند و رتبه بندي خطي فقط يك محدودة كوچكتر را براي قدرت انتخاب مجاز مي داند .

اگر چه رفتار روشهاي انتخاب متفاوت می باشد اما بطور كلي روشهاي انتخاب با پارامترهاي عدم تنوع ، واريانس انتخاب ، و قدرت انتخاب مقايسه مي شوند

2-8-3- عدم تنوع و قدرت انتخاب

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

3-8-3- واريانس انتخاب و قدرت انتخاب

همچنين در انتخاب برشي با قدرت انتخاب يكسان، واريانس انتخاب نسبت به انتخاب مسابقه‌اي و رتبه بندي خيلي كوچكتر می باشد همچنين در اين قسمت نيز بطور واضح مشخص می باشد كه انتخاب با رتبه بندي و مسابقه‌اي داراي رفتار مشابهي هستند ولي در انتخاب با رتبه بندي در يك محدوده اي كه انتخاب مسابقه‌اي اقدام نمي كند مي تواند انجام گيرد كه بدليل وجود خصوصيت مجزا و جداگانه در انتخاب مسابقه‌اي مي باشد .

در منبع [BT95] ثابت شده می باشد كه توزيع برازندگي براي انتخاب با رتبه بندي و مسابقه‌اي براي يكسان می باشد .

9-3- مسئله بهينه سازي

در اينجا سعي شده می باشد با يك مثال عددي جزئيات كار با الگوريتم ژنتيك همراه با ساده ترين و معروفترين انتخاب يعني انتخاب چرخ رولت توضيح داده گردد .

مثال : تابع f(x)=x2 را در فاصله بسته اعداد صحيح [31و0] بوسيله الگوريتم ژنتيك همراه با انتخاب چرخ رولت حداكثر نمايند .

حل : مراحل زير جهت بهينه سازي تابع هدف الزامي می باشد .

  • كدگذاري يا رمزگذاري
  • انتخاب جمعيت اوليه
  • عملگردهاي ژنتيكي ( تقاطع و جهش )
  • توليد مجدد
  • شرط خاتمه

هركدام از مراحل بالا را جهت حل تابع ، مورد بررسي قرار مي دهيم .

آغاز بايد متغير x را بصورت يك رشته ( كروموزوم ) محدود كد نماييم راههاي زيادي براي كد كردن متغير x هست كه در اينجا از كدينگ باينري بهره گیری مي نماييم زیرا حداكثر x مقدار 31 مي باشد

11111=32رشته (‌فرد )

بنابراين رشته موردنظر بايد داراي 5 بيت ( ژن ) باشد بعد از اين مرحله ، الگوريتم ژنتيكي با جمعيتي از رشته ها (‌افراد ) آغاز كرده و سپس جمعيت بعدي را از روي آن توليد مي كند .

فرض كنيد جمعيت اوليه 4 باشد كه بطور تصادفي اين جمعيت بصورت زير نمايش داده شده می باشد.

بعد از اين مرحله تابع برازندگي هر رشته و درصد آن از كل، بصورت جدول زير محاسبه مي گردد.

ارزش X درصد از كل تابع برازندگي رشته شماره
13 4/14 169 01101 1
24 2/49 576 11000 2
8 5/5
برای دانلود فایل ورد متن کامل اینجا کلیک کنید
64

01000

3 19

9/30

361

10011

4 64

100%

1170

 

جمع كل

 

زیرا تابع هدف ماكزيمم می باشد آنرا به عنوان تابع برازندگي در نظر گرفته‌ايم در اينجا رشته P2 ماكزيمم برازندگي و رشته P3 كمترين مقدار برازندگي را دارد و زیرا جواب بهينه 961 می باشد بايد اعمال ژنتيكي برروي رشته ها انجام دهيم .

تقاطع : هرگاه احتمال تقاطع Pc=%50 (‌بطور متوسط 50% از رشته ها در تقاطع شركت يابند ) در نظر گرفته گردد و دو رشته p4, p2 بدليل برازندگي بيشتر انتخاب مي گردند. براي مشخص کردن نقطه برش ( بطور تصادفي ) عدد 3 انتخاب مي‌گردد(‌دامنه تغييرات اين عدد تصادفي بين [1.4] می باشد )

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

جهش :

با فرض نرخ جهش 1/0 باشد ( بطور متوسط 10% از كل جمعيت مورد جهش قرار گيرد ) در اينجا به گونه كلي 4 جمعيت و هر كدام 5 بيت پس كلاً 20 بيت وجوددارد بنابراين 2 جهش در هر جمعيت وجود خواهد داشت در ضمن اگر همه بيت ها شانس مساوي براي جهش كردن داشته باشند بنابراين تعدادي عدد تصادفي RK(K=1,2,…,20) از محدودة [1و0] نياز داريم فرض كنيد طبق جدول زير ، ژنها براي جهش انتخاب مي شوند.

عدد تصادفي شماره بيت شماره رشته موقعيت ژن
011/0 1 1 1
07/0 3 3 13

 

بعد از فرآيند، جهش جمعيت بصورت جدول(1)با ارزشهاي برازندگي آنها آمده می باشد.

جدول (1): جمعيت و ارزشهاي برازندگي آنها

تابع برازندگي ارزش x عملگرها رشته ها
841 29 جهش P1: 11101
729 27 تقاطع F2:11011
144 12 جهش P3:01100
256 16 تقاطع F4:10000
1970 74 مجموع  

 

حال براي انتخاب در بيشتر مواقع از روش چرخ رولت بعنوان روش انتخاب بهره گیری مي گردد روش چرخ رولت بصورت زير اقدام مي كند .

  • براي رشته p1، ارزش برازش از تابع هدف بهره گیری مي گردد.
  • مجموع برازش ها را در جمعيت بدست مي آوريم (P-s اندازه جمعيت)
  • براي هر رشته ، احتمال انتخاب Pk بصورت زير حساب مي كنيم ( فراواني نسبي )
  • احتمال تجمعي هر رشته را محاسبه مي كنيم .

فرآيند انتخاب با چرخاندن چرخ رولت شروع مي گردد و در هر بار يك رشته براي جمعيت جديد انتخاب مي گردد در اين صورت داريم :

مرحله (1) : يك عدد تصادفي R از محدودة [0,1] انتخاب مي كنيم

مرحله (2): اگر ، آنگاه رشته P1 بعنوان اولين رشته انتخاب مي گردد .

در غير اينصورت ، آنقدر ادامه مي دهيم تا i‌امين رشته‌اي كه شرط زير را دارد حاصل گردد

اختصار مطالب فوق در جدول (2) آمده می باشد .

جدول (2) احتمال انتخاب هر رشته و احتمال تجمعي آن

رشته جديد عدد تصادفي Ri احتمال تجمعي qi احتمال انتخابpi رشته
P1 3/0 4269/0 4269/0 P1:11101
F2 5/0 7969/0 37/0 F2:11011
P1 4/0 8699/0 073/0 P3:01100
F4 9/0 1 1299/0 F4:10000

اكنون 4 بار ( p-s اندازه جمعيت ) چرخ رولت را مي چرخانيم و در هر بار يك رشته را انتخاب مي كنيم تا يك جمعيت جديد حاصل گردد . براي مثال براي عدد تصادفي دوم داريم :


پاسخ دهید