فهرست :

1-3- تابع برازندگی بر اساس رتبه بندی

1-1-3- رتبه بندی خطی

2-1-3- رتبه بندی غیر خطی

3-1-3- مقایسه بین رتبه بندی خطی و غیر خطی

4-1-3- آنالیز رتبه بندی خطی

2-3- رتبه بندی چند منظوره ( چند تابع )

1-2-3- رتبه بندی پارتو

2-2-3- دستیابی هدف یا روش عدم تساویها

3-2-3- اشتراک

4-2-3- اطلاعات بیشتر درمورد بهینه سازی چند منظوره

5-2-3- برآیند مجموع وزن دار شده یا عددی کردن چند منظوره

3-3- انتخاب چرخ دولت

4-3- نمونه گیری کلی تصادفی ( دارای تغییر در مواقع مختلف )

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

6-3- انتخاب برشی ( کاهشی )

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

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

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

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

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

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

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

3- انتخاب

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

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

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

1-2-3- رتبه بندی پارتو

برتری یک راه حل نسبت به دیگری بوسیله مقایسه دو راه حل می تواند تصمیم گیری گردد. که هم بصورت کلی و هم بصورت چند معیار مورد نظر می‌تواند انجام گیرد (مطابق با طرح شماتیک در معادله 7-3)

: غلبه پارتو .رتبه بندی پارتو

(7-3)

اگر P راه حل (1)، کمتر ( قسمتی کمتر ) از راه حل (2) باشد . بنابراین ، یعنی راه حل اول بر راه حل دوم غلبه کرده است . با توجه به مثال قبلی خواهیم داشت ، اگر هزینه ها و زمان برای راه حل اول نسبت به راه حل دوم کمتر هستند پس نتیجه می دهد که راه حل اول ، نسبت به راه حل دومی برتری دارد . لازم به ذکر است که اگر حتی یکی از دو مقادیر برای هر دو راه حل مساوی باشند و مقداردیگر کمتر باشد ( بطور مثال هزینه ها برای هر دو راه حل یکسان و برای راه حل اول زمان کمتر باشد ) نیز رضایت بخش می باشد.

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

رتبه یک فرد در جمعیت (Rank_i) به تعداد افرادیکه Numlnd _dominated)) بر این فرد غلبه پیدا کرده بستگی خواهد داشت [Fon95]

(8-3) Rang=1+Numlnd _(dominated)

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

2-2-3- دستیابی به هدف یا روش عدم تساویها

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

اهدافی بعنوان معیارهای شخص یا کاربر می تواند به منظور مانع این گونه راه حل های مجموعه بهینه پارتو، معرفی گردند که نتایج نامطلوب را در نظر نگیرد . یک راه حل فقط زمانی قابل پذیرش است که اهداف معیارهای کاربر را نیز پوشش بدهد . این فرآیند به روش عدم تساویها« MoI»یا برنامه ریزی هدف اتلاق می گردد. اهداف فرد بعنوان عدم تساویها از قبل، تعریف می گردد.

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