مقاله درباره ، بهدست، کروموزم، متغیرها، GA، بهصورت، کروموزمهای، والدین

رابطه (1-9)، خطی فرض میکنیم که پارامترهای aij و bij نشاندهنده عرض از مبدا و شیب منحنی قیمت- مقدار میباشد. (مانند شکل 1-1):
pij=aij-bijxij . (9-1)
208520716198400
شکل 1-1: منحنی قیمت-مقدار
تابع هدف (1-2)
شامل فرایندهایی است که درگیر بازگشت یا دریافت محصولات مرجوع شده به هر دلیل می باشند. فرایند مذکور میتواند قابل تعمیم به فرایندهای پشتیبانی از مشتریان پس از تحویل نیز باشد. بهصورت جزئیتر فرایند برگشت شامل موارد بازگرداندن مواد اولیه (به تامین کننده) و دریافت رسید محصول برگشتی (از مشتری) شامل کالای معیوب، مازاد و منقضی میباشد.
محدودیتها
محدودیت (1-5) تضمین میکند که تعداد کل واحدهای مرجوع شده از هر محصول کمتر از حداکثر سطح مجاز است. محدودیت (1-6 ) نشاندهنده آناست که تعداد کل اقلام دیرتحویلشده از هر محصول پایینتر از حداکثر سطح مجاز متناظر است. محدودیت (1-7) تضمین میکند که مقدار سفارش محصول j اختصاص یافته به تامینکننده i بین مقدار مینیمم و ماکزیمم متناظر قرار میگیرد.

1-7-3 روش حل مدل پیشنهادیبرای حل این مساله تصمیمگیری چند هدفه از روش متریک Lp، جواب ایدهآل مدل را بهدست آورده (جواب ایدهآل با توجه به هر تابع هدف از مدل اصلی با توجه به محدودیتهای (1-5) تا (1-7) بهدست میآید) و سپس با ترکیب آنها به یک تابع هدف که در (1-10) آمده است، سعی میشود نزدیکترین نقطه از فضای جواب به نقطهی ایدهآل یافت شود. توابع متفاوتی برای اندازهگیری فاصله در روش Lp تعریف میشود. ما از تعریف زیر استفاده میکنیم.
Lp=j=1kbjfjx-fjxj*fjxj*p1pکه برای p=1 و k=4 رابطهی (1-10) بهدست میآید
z =b1z1-z1*z1* +b2z2-z2*z2* +b3z3-z3*z3* +b4z4*-z4z4*.(10-1)
در معادله (1-10)، b1 تا b4 وزنهای مهمی هستند که با توجه به اهداف تصمیمگیرنده انتخاب میشوند. با توجه به غیرخطی بودن z1 ، z نیز غیرخطی و شامل متغیرهای صحیح است. بنابراین یک مساله برنامهریزی صحیح غیرخطی NIP خواهیم داشت، که با روشهای متاهیوریستیک GA (الگوریتم ژنتیک) و SA (شبیه سازی گرم وسپس سرد کردن) آنرا حل میکنیم.

فصل دوماستفاده از الگوریتم ژنتیک و الگوریتم شبیهسازی تبرید برای حل مدل پیشنهادی

متاهیوریستیکمحاسبه جواب بهینه برای اکثر مسائل بهینهسازی که در خیلی از زمینههای کاربردی و عملی مشاهده میگردند،کاری دشوار و سخت است. درعمل، معمولا به جوابهای “خوب” که از الگوریتمهای هیوریستیک یا متاهیوریستیک (فراابتکاری) بهدست میآید، اکتفا میگردد. روشهای فراابتکاری جوابهای “قابل قبول” در زمان معقول را برای مسائل پیچیده و سخت در زمینههای مهندسی و علوم ارائه مینمایند.
چه موقع از متاهیوریستیکها استفاده میشود؟
پیچیدگی یک مساله، زمان حل، ساختار دادههای ورودی و اندازه مساله شاخصهایی برای بررسی سختی یک مساله بهحساب میآید. استفاده از متاهیوریستیکها برای حل مسائل ساده، کاری بیهوده است. اگر یک مساله قابل تجزیه به مسائل کلاسیک یا مسالهای که حل شده است، باشد، میتوان با مراجعه به پیشینه تحقیق، الگوریتم مناسبی برای آن پیدا کرد. دسته ای از مسائلی که متا هیوریستیکها برای حل آن مناسب میباشند، بهصورت زیر طبقهبندی میشود:
یک مساله ساده (طبقه p) با ابعاد خیلی بزرگ. در این مورد، الگوریتمهای چندجمله ای دقیق برای حل مساله وجود دارند، ولی بهدلیل ابعاد بزرگ، خیلی پر هزینه می باشند.
برای حل برخی مسائل از ردهی انپی-سخت استفاده میشوند.
قادر به بهینه سازی مسائل با توابع هدف یا محدودیتهای زمانبر میباشند.
2-1 الگوریتم ژنتیک (GA)استفاده از GA بهعنوان یک عضو از خانوادهی الگوریتمهای تکاملی یک راهحل مسائل NIP است که بیشتر اوقات با یک رشته اعداد دودویی یا حقیقی به نام کروموزم نشان داده میشود. هرکروموزم دارای یک مقدار تناسب است که معمولا به مقدار تابع هدف جواب مربوط است. در ابتدا در این الگوریتم یک جمعیت از جواب بهطور تصادفی تولید میشود، پس از آن برای تولید جوابهای جدید بهنام فرزندان تعدادی جواب با توجه به اعمال قانون تولید مثل انتخاب میشوند. جفتگیری از والدین با استفاده از اپراتورهایGA بهنام تقاطع و جهش انجام میشود تا زمانیکه قانون توقف صدق کند (برای مثال گذشت تعداد معینی از تکرارها).
2-1-1 مزایای الگوریتم ژنتیکذاتا موازی است، یعنی جمعیتی از نقاط بهجای یک نقطه مورد جستجو قرارمیگیرد.
با متغیرهای پیوسته و گسسته کار میکند.
نیاز به محاسبه مشتق تابع ندارد چون برای پیدا کردن جهت جستجو انتخاب تصادفی انجام میدهد.
قادر به بهینه سازی مسائل با متغیرهای زیاد است.
با متغیرهای کدشده کار میکند وکدبندی سرعت همگرایی الگوریتم را افزایش میدهد.
این الگوریتم از قوانین انتقال احتمالی بهجای قوانین انتقال قطعی استفاده میکند بدین معنا که حرکت آن در هر نقطه از الگوریتم کاملا احتمالی بوده و براساس قطعیت صورت نمیگیرد. این امر از مزایای مهم این روش بوده و از افتادن در کمینه محلی جلوگیری میکند. البته میزان احتمال بهگونهای است که احتمال حرکت به سوی هدف مساله بیشتر از احتمال حرکت به سمت مخالف جواب میباشد.
برای حل برخی مسائل از ردهی انپی-سخت نیز استفاده میشود.
قبل از دادن یک طرح کلی پیشنهاد اکتشافی مبتنی بر GA برخی از نمادهای اضافی را معرفی میکنیم.
ppsz: سایز جمعیت جواب که در طول اجرای الگوریتم ثابت است.
maxit: تعداد تکرار از پیش تعیین شده.
Pc: نرخ تقاطع (باکدام احتمال یک کروموزم ازهر نسل برای انجام تقاطع انتخاب شده است).
Pm: نرخ جهش (باکدام احتمال یک بیت از یک رشته جواب (یا یک ژن ازیک کروموزم) به منظور جهش انتخاب شده است).
ftfn: مقدار تابع تناسب که فرض شده است با مقدار تابع هدف برابر باشد.
2-1-2 طرح کلی از GA پیشنهادی
مرحله 1: مقداردهی اولیه ppszو maxit و Pc و Pmو ftfn
مرحله 2: تولید تصادفی جمعیت اولیه با توجه به ارزش ppsz
مرحله 3: تکرار تا زمانیکه maxit
مرحله 3-1: استفاده ازعملگر تولید مثل، انتخاب مجموعهای از جوابهای واجد شرایط با استفاده از قوانین چرخرولت و ساخت جمعیت جدید.
مرحله3-2 : انتخاب کروموزمهای والدین از جمعیت جدید بااحتمالPc
مرحله3-3: تقاطع (پیوند)
الف: شکل دادن جفتهای والدین، در میان کروموزمهای والدین
ب : بهکاربردن عملگر تقاطع تکنقطه ای برای تولید کروموزمهای فرزند از دو کروموزم والدین اولیه
پ: جایگزینی هر کروموزم والدین اولیه در جمعیت با کروموزمهای فرزند
مرحله 3-4 : بهکاربردن عملگر جهش در جمعیت با احتمال Pm
مرحله 3-5: محاسبه ftfn برای هر کروموزم و ذخیره بهترین مقدار در bv(best value) ، اگر از قبلی بهتر باشد.
مرحله 4: چاپ bv
در شکل (2-1) روند کلی الگوریتم ژنتیک نمایش دادهشده است.

شکل 2-1: روند کلی الگوریتم ژنتیکدر ادامه گامبهگام با این روند آشنا میشویم.
2-1-2-1 تعیین تابع تناسب
یکی از مزایای روش الگوریتم ژنتیک ایناست که فقط با مقدار تابع سرو کار دارد و نیازی به دانستن رابطه بین متغیرها و تابع نیست لذا برای انتخاب تابع نیازی به دانستن معادله دقیق آن نداریم و فقط اگر روشی بیابیم که بهوسیله وارد کردن متغیرهای مساله مقدار عددی تابع را بتوانیم پیدا کنیم کفایت میکند.
مثلا اگر بتوانیم بهوسیله روشی از روشهای ترسیمی در مورد مسالهای خاص به ازای متغیرهای مختلف مقدار تابع را پیدا کنیم یا اینکه اگر نرم افزاری برای تحلیل یک مساله مهندسی وجود دارد که متغیرها را از ما میگیرد و جواب را به ما میدهد میتوانیم بدون دانستن اتفاقاتی که در طی آن به جواب میرسیم، فقط با دانستن مقدار آن به ازای متغیرهای ورودی مقدار بهین تابع را بهوسیله الگوریتم ژنتیک بهدست آوریم.
اگر تابع هدف ما دارای قیود طراحی بود که معمولا هم چنین است میتوانیم به وسیله تابع جریمه، مجموعه قیود مساوی و نامساوی را به یک رابطه تبدیل کنیم و به بهینه کردن رابطه مورد نظر بپردازیم. برای مثال اگر برای مسالهای سه قید نامساوی و یک قید مساوی مانند زیر داشته باشیم:
16×12+16×12≤1×1≥0x2≥05×1+3×2=8میتوان آنرا به صورت استاندارد زیر نوشت :
g1x=16×12+16×12-1≤0g2x=-x1≤0g3x=-x2≤0g4x=5×1+3×2-8=0بردار V را بهصورت زیر تعریف میکنیم:
V= max [0,g1x, g2x, g3x, abs(g4x)]
و تابع جریمه را بهصورت زیر تعریف میکنیم:
φ=f0+RVکه در آن φ تابع هدف نامقید بوده و R ضریب جریمه است که انتخاب آن به عهده طراح میباشد و بردار V ماکزیمم نقض قید توسط متغیرها میباشد و از این پس تابع φکه تابع پنالتی ما میباشد به عنوان تابع هزینه بهینه میگردد.
2-1-2-2 تعیین طول کروموزوم
کروموزوم یک رشته از 0 و 1 است که مقدار n متغیر تابع هدف ما را دربردارد. مثلا اگر طول هر متغیر را α بیت در نظر بگیریم طول کل کروموزوم برابر است با: L=n*α (به هر بیت از کروموزوم یک ژن گویند).
میتوان برای تعیین α از رابطه زیر استفاده کرد: α=[logb-a*10m+1] که m دقت متغیرها بر حسب تعداد رقم اعشار و a حد پایین وb حد بالای متغیرها در مبنای 10 میباشد.
در جاهایی که لازم است برای اعداد منفی باید یک بیت به علامت آنها اختصاص داد و در

متن کامل در سایت homatez.com