دانلود ‫پروژه رفتار بیرون کشیدن نخ

انتخاب
در انتخاب ، افراد والد ( به منظور تکثیر برای نسل آینده ) انتخاب شده هستند اولین گام تابع برازندگی است هر فرد در فضای (‌استخر ) انتخاب ، یک احتمال تولید مثل (reproduction) که وابسته به مقدار هدف خودش و مقدار هدف بقیه افراد دیگر در فضای انتخاب دارد را دریافت می کند .

این برازندگی بعنوان انتخاب واقعی جلو رونده و مرحله‌ای ، انجام میگیرد .

ابتدا بعضی از عبارتهای خاص که برای مقایسه طرحهای مختلف انتخاب ، استفاده شده تعریف می‌گردد .

تعریف این عبارت از [Bak87],[BT95] بدست آمده است .

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

قدرت انتخاب
مقدار برازندگی متوسط (مورد انتظار) جمعیت و بصورت توزیع نرمال استاندارد شده بعد از بکاربردن یک روش انتخاب
واریانس انتخاب
واریانس مورد انتظار ( میانگین واریانس ) توزیع برازندگی جمعیت به صورت توزیع نرمال استاندارد شده بعد از بکاربردن یک روش انتخاب


1-3- تابع برازندگی بر اساس رتبه بندی
در تابع برازندگی بر اساس رتبه ، جمعیت مطابق با مقادیر هدف دسته بندی می شود .

این برازندگی برای هر فرد فقط وابسته به موقعیت رتبه افراد ( نه مقدار واقعی هدف ) تعیین می گردد .

تابع برازندگی بر اساس رتبه بر مشکلات مقیاس بندی تابع برازندگی متناسب ، غلبه می کند.

(‌حالت ایستایی یا سکون : وقتی که فشار انتخابی بیش از اندازه کوچک باشد ، یا همگرایی نابهنگام :وقتی که جستجوی روش انتخاب در محدوده کوچکی انجام شود بنابراین بیش از اندازه سریع خواهد بود )
همچنین محدوده ‌ تولید مثل محدود شده است بنابراین هیچکدام از افراد تعداد زاد و ولد اضافی را تولید
نمی کنند .

رتبه بندی یک مقیاس همگن در جمعیت را معرفی می کند و.همچنین یک روش مؤثر و ساده برای کنترل کردن فشار انتخابی را ارائه می دهد .

تابع برازندگی بر اساس رتبه بندی حالت قوی تر نسبت به تابع برازندگی متناسب عمل می کند و بنابراین روش نخبه گرایا برگزیده ، است .

1-1-3- رتبه بندی خطی
Nind تعداد افراد جامعه ،Pos موقعیت یک فرد در جامعه (حداقل برازندگی فرد Pos=1 و برازنده ترین فرد Pos= Nind است ) و SP هم فشار انتخاب است مقدار برازندگی برای یک فرد بصورت ذیل محاسبه می گردد.

(1-3)
در رتبه بندی خطی مقادیر فشار انتخاب بین [2-1] خواهد بود
2-1-3- رتبه بندی غیر خطی
روش جدیدبرای رتبه بندی با استفاده از توزیع غیر خطی در [poh95] معرفی شده است استفاده از رتبه بندی غیر خطی ، فشار انتخاب بیشتری رانسبت به روش رتبه‌بندی خطی ارائه می دهد.

(2-3)
x ریشه معادله چند جمله‌ای ذیل می باشد .

(3-3)
در رتبه بندی غیر خطی مقادیر فشار انتخاب بین [1,Nind-2] خواهد بود
3-1-3- مقایسه رتبه بندی خطی و غیر خطی
شکل 1-3، رتبه بندی خطی و غیر خطی را بصورت گرافیکی مقایسه می‌کند .

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

جدول ذیل، مقادیر برازندگی افراد در مقادیر مختلف فشار انتخاب ، با فرض اینکه جمعیت 11 نفر با هدف مینیمم کردن را نشان می دهد .

4-1-3- آنالیز رتبه بندی خطی
در [BT95] آنالیز انتخاب رتبه بندی خطی ارایه گردیده است .

قدرت انتخاب
(4-3)
عدم تنوع
(5-3)
واریانس انتخاب :
(6-3)
2-3- رتبه بندی چند منظوره ( چند تابع )
در تابع برازندگی بر اساس رتبه بندی و تناسبی ، فرض شده است که افراد فقط یک مقدار تابع هدف رانشان می دهند.

در صورتیکه معمولاً در جهان واقعی چند مقدار (بیش از یک مشکل ) وجود دارد .

بنابراین باید چند معیار برای ارزیابی کیفیت فرد در نظر گرفته شود .

فقط بر اساس مقایسه این چند معیار ( در نتیجه چند هدف ) می‌توان در مورد برتری یک فرد نسبت به دیگری تصمیم گیری نمود .

بنابراین ، مشابه مشکلات با یک هدف ، ترتیب افراد در جمعیت از مقایسه متقابل رتبه بندی چند منظوره ، می تواند بدست آید .

بعد از اینکه این ترتیب حاصل گردید روشهای رتبه بندی با یک هدف (از قسمت 1-3) می تواند برای برگردان کردن ترتیب افراد مرتبط با مقادیر برازندگی آنها استفاده گردد .

بنابراین تابع برازندگی چند منظوره ( بهینه کردن چند تابع ) با، هم زمان مینیمم کردن Nobj‌با معیار fr( بطوریکه r=1,…..,Nobj) انجام گیرد .

این مقادیر fr بوسیله تابع هدف که به متغیرهای افراد ( متغیرهای تصمیم ) وابسته است مشخص می گردند .

یک مثال می تواند نکات قابل توجه در این نوع مسائل را روشن کند .

فرض کنید کالایی تولید می شود که می‌خواهیم هزینه های تولید پایین و همچنین کالا را سریع تولید کند .

راه حل های مختلفی در طراحی تولید وجود دارد که به پارامترهای مختلفی شامل تعداد و نوع ماشین های به کار رفته ، همچنین تعداد کارگرها بستگی دارند .

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

1-2-3- رتبه بندی پارتو
برتری یک راه حل نسبت به دیگری بوسیله مقایسه دو راه حل می تواند تصمیم گیری گردد.

که هم بصورت کلی و هم بصورت چند معیار مورد نظر می‌تواند انجام گیرد (مطابق با طرح شماتیک در معادله 7-3)
: غلبه پارتو .رتبه بندی پارتو
(7-3)
اگر P راه حل (1)، کمتر ( قسمتی کمتر ) از راه حل (2) باشد .

بنابراین ، یعنی راه حل اول بر راه حل دوم غلبه کرده است .

با توجه به مثال قبلی خواهیم داشت ، اگر هزینه ها و زمان برای راه حل اول نسبت به راه حل دوم کمتر هستند پس نتیجه می دهد که راه حل اول ، نسبت به راه حل دومی برتری دارد .

لازم به ذکر است که اگر حتی یکی از دو مقادیر برای هر دو راه حل مساوی باشند و مقداردیگر کمتر باشد ( بطور مثال هزینه ها برای هر دو راه حل یکسان و برای راه حل اول زمان کمتر باشد ) نیز رضایت بخش می باشد.

اگر هیچکدام از راه حل ها بر دیگری غلبه پیدا نکند هر دو راه حل بعنوان معادل در ترتیب پارتو در نظر گرفته می شود و رتبه یکسان برای افرادیکه بر یکدیگر غلبه پیدا نکرده اند شناسایی می شوند .

رتبه یک فرد در جمعیت (Ranki) به تعداد افرادیکه Numlnd dominated)) بر این فرد غلبه پیدا کرده بستگی خواهد داشت [Fon95] (8-3) Rang=1+Numlnd (dominated) برای همه راه حل هائیکه در طول مدت بهینه کردن بدست آمده و توسط ترکیب راه حل‌های مختلف از راه حل های بهینه پارتو ( مجموعه بهینه پارتو) مربوط به مسئله (‌بهینه‌سازی پارتو) نمی توانند بر این راه حل ها غلبه کنند رتبه 1 در نظر گرفته می شود و غیر ممکن است که در مورد این راه حل بهینه پارتو، بتوان ملاک یا معیاری را، بدون اینکه یک یا چند معیار دیگر از بین برود، را توسعه داد.

2-2-3- دستیابی به هدف یا روش عدم تساویها وقتی که از رتبه بندی پارتو ساده در معادله(7-3) استفاده نموده وهمه راه حل های بهینه پارتو معادل باشند ممکن است بتوان برای تعدادی از مسائل عملی تفکیک بیشتری را در نظر گرفت فرض کنید در مثال قبل ، بتوان ، برای تولید کالا ، توضیح کاملتری ارائه کرد .

همیشه در حالت حداکثری یک راه حل ، هیچ چیز مشخص نمی‌گردد .فرض کنید هزینه صفر و زمان نامحدود بدست آید بنابراین هیچ راه حل دیگری نمی تواند کالاهایی در هزینه های کمتر را تولید کند .

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

کاملاً واضح است که هر دو حالت مطلوب نمی باشند اگرچه آنها به راه حل هایی بدون غلبه ( هیچ راه حل دیگری به این راه حل غلبه پیدا نمی کند ) متعلق می باشند .

اهدافی بعنوان معیارهای شخص یا کاربر می تواند به منظور مانع این گونه راه حل های مجموعه بهینه پارتو، معرفی گردند که نتایج نامطلوب را در نظر نگیرد .

یک راه حل فقط زمانی قابل پذیرش است که اهداف معیارهای کاربر را نیز پوشش بدهد .

این فرآیند به روش عدم تساویها« MoI»یا برنامه ریزی هدف اتلاق می گردد.

اهداف فرد بعنوان عدم تساویها از قبل، تعریف می گردد.

در مثال تولیدی ارائه شده ، می توان یک حد بالا برای هزینه ها و زمان تولید را در نظر گرفت بنابراین هیچ راه حلی قابل قبول نمی باشد .

مگر اینکه بطور همزمان با این دو معیار بیان شده نیز بررسی گردیده باشد .

وقتی اهداف شامل رتبه بندی چند منظوره هستند تا حدودی مقایسه دو راه حل پیچیده تر خواهد بود .

فرضیات ذیل ، ایجاد شده است .

(9-3) (عملگر«P راه حل (1)، هیچ هدفی را بدست نمی آورد .

(10-3) F>Goals ^ Solution1 P راه حل (1 )ترجیح داده می شود.

solution1 Preferd راه حل 1، همه اهداف را به دست آورد .

راه حل (1) ترجیح داده می‌شود‌.

راه 1، بعضی از اهداف را بدست آورد .

راه حل (1) ترجیح داده می شود : رتبه بندی پاراتو از یک بردار اهداف معیارهای کاربر استفاده می نماید .

بنابراین نسل جدید توسعه یافته ، متوالی و مرتب شده از راه حل ها ، در مقایسه با رتبه بندی ساده را ارائه می دهد .

بهینه سازی چند منظوره به منظورپیدا کردن یک سری راه حل، بدون غلبه از مجموعه بهینه پارتو می باشد .

اگر چه این الگوریتم تکاملی نرمال ، در نهایت به یک راه حل منحصر به فرد همگرا خواهد شد .

اما این فرآیند ، بعنوان فرآیند شناور ژنتیکی در نظر گرفته می شود .

به همین منظور باید روشهایی ایجاد گردد که گسترش مطلوب همگرایی جمعیت (‌جلوگیری از همگرایی نابهنگام) را کسب نماید .

3-2-3- اشتراک از یک طرف فرآیند شناور ژنتیکی می تواند بدلیل کاربرد اشتراک برازندگی اثر متقابل داشته باشد و از طرف دیگر الگوریتم اثری دارد که قسمت بزرگتر از راه حل بهینه پارتو را بدست می آورد .

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

بنابراین در این روش افراد بیشتر نزدیک یک فردهستند و برازندگی آن کمتر خواهد شد .

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

روشهای اشتراک برازندگی در بین افراد دیگر در [fon95], [SD94],[HN93] پیشنهاد شده است .

4-2-3- اطلاعات بیشتر در مورد بهینه کردن چند منظوره در این قسمت فقط یک معرفی کوتاه از شناسایی برازندگی چند منظوره در زمینه الگوریتم تکاملی ، ارائه می گردد.

مطلوب عملی و نکات خاص بیشتر با توجه به فرآیندهای خاص آن به‌[Ve199],[SD94],[HN93],[ZT98],[Fon95],[Hor97] ارجاع داده می شود .

همچنین یک منبع کامل از دانش و اطلاعات در مورد بهینه کردن چند منظوره در الگوریتم تکاملی در [Coe99] قابل دسترس می باشد .

یک منبع کامل علمی در مورد بهینه کردن چند منظوره بصورت عمومی ( نه بطور خاص روی الگورتیم تکاملی) نیز وجود دارد .

منبع [Mie99] بعنوان یک نقطه شروع خوب توصیه می گردد .

5-2-3- : برآیند مجموع وزن دار شده یا اسکالر کردن (‌عددی کردن) چند منظوره وقتی به روشهای مختلف و قسمتهای ترکیبی مورد استفاده برای بهینه کردن چند منظوره توجه می کنیم نباید روشهای کلاسیک برای ادغام چند معیار را فراموش کنیم (‌روش عددی کردن ، تجمع اهداف نیز ، نامیده می شود ).

مجموع وزن دار ، شناخته ترین روش است که برای هر معیار، یک مقدار وزن خالص بکار برده می شود یعنی اینکه از ترکیب خطی همه معیارهای وزنی یک تابع هدف ترکیبی Fws بدست می آید (13-3) این مجموع وزن دار شده بخصوص برای وقتی که اهمیت مختلف از معیار افراد شناخته شده و یا قابل تخمین زدن هستند ، بکار می روند .

و بیشتر در کاربردهای عملی اتفاق می‌افتد بنابراین اغلب از مجموع وزن دار شده استفاده می گردد .

اگر مسئله چند منظوره بوسیله بهینه کردن یک متغیر حل گردد تنها یک نکته از راه حل بدست آمده است و مزیتهای بدست آوردن چند راه حل با مقادیر معادل در ارتباط با بردار هدف را از دست داده است در این مرحله کاربر باید تصمیم بگیرد که آیا کاربرد ساده از مجموع وزن دار یا تقریب راه حل های بهینه پارتو برای حل مسئله مهمتر است .

3-3- انتخاب چرخ رولت ساده ترین طرح انتخاب ، انتخاب چرخ رولت است به این روش، نمونه گیری تصادفی با جایگزینی نیز گفته می شود [[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 باشد که بطور تصادفی این جمعیت بصورت زیر نمایش داده شده است.

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

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

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

برای مشخص نمودن نقطه برش ( بطور تصادفی ) عدد 3 انتخاب می‌گردد(‌دامنه تغییرات این عدد تصادفی بین [1.4] است ) و برای تقاطع قسمت راست کروموزم های پدر را برای تولید فرزندان با هم تعویض می کنیم خواهیم داشت .

P2: 1 1 0 0 0 p4: 1 0 0 1 1 F2: 1 1 0 1 1 F4: 1 0 0 0 0 در نتیجه این دو رشته جایگزین دو رشته قبلی می گردد.

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

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

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

برای رشته p1، ارزش برازش از تابع هدف استفاده می شود.

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

فرآیند انتخاب با چرخاندن چرخ رولت شروع می شود و در هر بار یک رشته برای جمعیت جدید انتخاب می شود در این صورت داریم : مرحله (1) : یک عدد تصادفی R از محدوده [0,1] انتخاب می کنیم مرحله (2): اگر ، آنگاه رشته P1 بعنوان اولین رشته انتخاب می گردد .

در غیر اینصورت ، آنقدر ادامه می دهیم تا i‌امین رشته‌ای که شرط زیر را دارد حاصل شود خلاصه مطالب فوق در جدول (2) آمده است .

جدول (2) احتمال انتخاب هر رشته و احتمال تجمعی آن اکنون 4 بار ( p-s اندازه جمعیت ) چرخ رولت را می چرخانیم و در هر بار یک رشته را انتخاب می کنیم تا یک جمعیت جدید حاصل گردد .

برای مثال برای عدد تصادفی دوم داریم : پس رشته F2 انتخاب می گردد ودیده می شود که درجمعیت جدید رشته p3 حذف و رشته p1 دوبار در جمعیت جدید ظاهر گردیده است .

حال دوباره این روند تکرار می‌گردد تا جواب بهینه که همان x=31 است حاصل گردد .

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

ارزش Xدرصد از کلتابع برازندگیرشتهشماره134/14169011011242/4957611000285/564010003199/3036110011464100%1170جمع کل عدد تصادفیشماره بیتشماره رشتهموقعیت ژن011/011107/03313 تابع برازندگیارزش xعملگرهارشته ها84129جهشP1: 1110172927تقاطعF2:1101114412جهشP3:0110025616تقاطعF4:10000197074مجموع رشته جدیدعدد تصادفی Riاحتمال تجمعی qiاحتمال انتخابpiرشتهP13/04269/04269/0P1:11101F25/07969/037/0F2:11011P14/08699/0073/0P3:01100F49/011299/0F4:10000