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

انتخاب
در انتخاب ، افراد والد ( به منظور تکثیر برای نسل آینده ) انتخاب شده هستند اولین گام تابع برازندگی است هر فرد در فضای (‌استخر ) انتخاب ، یک احتمال تولید مثل (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 بدست می