مقاله درباره ، بهدست، کروموزم، متغيرها، 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